Nikhil Vyas
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Nikhil Vyas has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
- Jonathan Lenchner
IBM T.J. Watson Research Center
3 shared publications - Kenneth W. Regan
University at Buffalo (SUNY)
3 shared publications - Ronald Fagin
IBM Research
3 shared publications - Ryan Williams
Massachusetts Institute of Technology, Cambridge, USA
3 shared publications - Sham Kakade
Harvard University
3 shared publications Blaise Genest
1 shared publication
Latest Publications
- Top Cited PapersOpen Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 45-53
Quasi-Linear Size PCPs with Small Soundness from HDX
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 45-53
Top Cited PapersOpen AccessQuasi-Linear Size PCPs with Small Soundness from HDX
- Open Access
Connections between Schedule-Free Optimizers, AdEMAMix, and Accelerated SGD Variants
Recent advancements in deep learning optimization have introduced new algorithms, such as Schedule-Free optimizers, AdEMAMix, MARS and Lion which modify traditional momentum mechanisms. In a separate line of work, theoretical acceleration of stochastic gradient descent (SGD) in noise-dominated regime has been achieved by decoupling the momentum coefficient from the current gradient's weight. In this paper, we establish explicit connections between these two lines of work. We substantiate our theoretical findings with preliminary experiments on a 150m language modeling task. We find that AdEMAMix, which most closely resembles accelerated versions of stochastic gradient descent, exhibits superior performance. Building on these insights, we introduce a modification to AdEMAMix, termed Simplified-AdEMAMix, which maintains the same performance as AdEMAMix across both large and small batch-size settings while eliminating the need for two different momentum terms. The code for Simplified-AdEMAMix is available on the repository: https://github.com/DepenM/Simplified-AdEMAMix/.
Open AccessConnections between Schedule-Free Optimizers, AdEMAMix, and Accelerated SGD Variants
Recent advancements in deep learning optimization have introduced new algorithms, such as Schedule-Free optimizers, AdEMAMix, MARS and Lion which modify traditional momentum mechanisms. In a separate line of work, theoretical acceleration of stochastic gradient descent (SGD) in noise-dominated regime has been achieved by decoupling the momentum coefficient from the current gradient's weight. In this paper, we establish explicit connections between these two lines of work. We substantiate our theoretical findings with preliminary experiments on a 150m language modeling task. We find that AdEMAMix, which most closely resembles accelerated versions of stochastic gradient descent, exhibits superior performance. Building on these insights, we introduce a modification to AdEMAMix, termed Simplified-AdEMAMix, which maintains the same performance as AdEMAMix across both large and small batch-size settings while eliminating the need for two different momentum terms. The code for Simplified-AdEMAMix is available on the repository: https://github.com/DepenM/Simplified-AdEMAMix/.
- Open Access
- 29 January 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Multi-Structural Games and Number of Quantifiers
We study multi-structural games, played on two sets $\mathcal{A}$ and $\mathcal{B}$ of structures. These games generalize Ehrenfeucht-Fra\"{i}ss\'{e} games. Whereas Ehrenfeucht-Fra\"{i}ss\'{e} games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the $r$-round game if and only if there is a first-order sentence $\phi$ with at most $r$ quantifiers, where every structure in $\mathcal{A}$ satisfies $\phi$ and no structure in $\mathcal{B}$ satisfies $\phi$. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders.- 29 January 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Open AccessMulti-Structural Games and Number of Quantifiers
We study multi-structural games, played on two sets $\mathcal{A}$ and $\mathcal{B}$ of structures. These games generalize Ehrenfeucht-Fra\"{i}ss\'{e} games. Whereas Ehrenfeucht-Fra\"{i}ss\'{e} games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the $r$-round game if and only if there is a first-order sentence $\phi$ with at most $r$ quantifiers, where every structure in $\mathcal{A}$ satisfies $\phi$ and no structure in $\mathcal{B}$ satisfies $\phi$. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders. - Open Access
Loss-to-Loss Prediction: Scaling Laws for All Datasets
While scaling laws provide a reliable methodology for predicting train loss across compute scales for a single data distribution, less is known about how these predictions should change as we change the distribution. In this paper, we derive a strategy for predicting one loss from another and apply it to predict across different pre-training datasets and from pre-training data to downstream task data. Our predictions extrapolate well even at 20x the largest FLOP budget used to fit the curves. More precisely, we find that there are simple shifted power law relationships between (1) the train losses of two models trained on two separate datasets when the models are paired by training compute (train-to-train), (2) the train loss and the test loss on any downstream distribution for a single model (train-to-test), and (3) the test losses of two models trained on two separate train datasets (test-to-test). The results hold up for pre-training datasets that differ substantially (some are entirely code and others have no code at all) and across a variety of downstream tasks. Finally, we find that in some settings these shifted power law relationships can yield more accurate predictions than extrapolating single-dataset scaling laws.
Open AccessLoss-to-Loss Prediction: Scaling Laws for All Datasets
While scaling laws provide a reliable methodology for predicting train loss across compute scales for a single data distribution, less is known about how these predictions should change as we change the distribution. In this paper, we derive a strategy for predicting one loss from another and apply it to predict across different pre-training datasets and from pre-training data to downstream task data. Our predictions extrapolate well even at 20x the largest FLOP budget used to fit the curves. More precisely, we find that there are simple shifted power law relationships between (1) the train losses of two models trained on two separate datasets when the models are paired by training compute (train-to-train), (2) the train loss and the test loss on any downstream distribution for a single model (train-to-test), and (3) the test losses of two models trained on two separate train datasets (test-to-test). The results hold up for pre-training datasets that differ substantially (some are entirely code and others have no code at all) and across a variety of downstream tasks. Finally, we find that in some settings these shifted power law relationships can yield more accurate predictions than extrapolating single-dataset scaling laws.
- Open Access
On Privileged and Convergent Bases in Neural Network Representations
In this study, we investigate whether the representations learned by neural networks possess a privileged and convergent basis. Specifically, we examine the significance of feature directions represented by individual neurons. First, we establish that arbitrary rotations of neural representations cannot be inverted (unlike linear networks), indicating that they do not exhibit complete rotational invariance. Subsequently, we explore the possibility of multiple bases achieving identical performance. To do this, we compare the bases of networks trained with the same parameters but with varying random initializations. Our study reveals two findings: (1) Even in wide networks such as WideResNets, neural networks do not converge to a unique basis; (2) Basis correlation increases significantly when a few early layers of the network are frozen identically. Furthermore, we analyze Linear Mode Connectivity, which has been studied as a measure of basis correlation. Our findings give evidence that while Linear Mode Connectivity improves with increased network width, this improvement is not due to an increase in basis correlation.
Open AccessOn Privileged and Convergent Bases in Neural Network Representations
In this study, we investigate whether the representations learned by neural networks possess a privileged and convergent basis. Specifically, we examine the significance of feature directions represented by individual neurons. First, we establish that arbitrary rotations of neural representations cannot be inverted (unlike linear networks), indicating that they do not exhibit complete rotational invariance. Subsequently, we explore the possibility of multiple bases achieving identical performance. To do this, we compare the bases of networks trained with the same parameters but with varying random initializations. Our study reveals two findings: (1) Even in wide networks such as WideResNets, neural networks do not converge to a unique basis; (2) Basis correlation increases significantly when a few early layers of the network are frozen identically. Furthermore, we analyze Linear Mode Connectivity, which has been studied as a measure of basis correlation. Our findings give evidence that while Linear Mode Connectivity improves with increased network width, this improvement is not due to an increase in basis correlation.
- Open Access
On Provable Copyright Protection for Generative Models
There is a growing concern that learned conditional generative models may output samples that are substantially similar to some copyrighted data $C$ that was in their training set. We give a formal definition of $\textit{near access-freeness (NAF)}$ and prove bounds on the probability that a model satisfying this definition outputs a sample similar to $C$, even if $C$ is included in its training set. Roughly speaking, a generative model $p$ is $\textit{$k$-NAF}$ if for every potentially copyrighted data $C$, the output of $p$ diverges by at most $k$-bits from the output of a model $q$ that $\textit{did not access $C$ at all}$. We also give generative model learning algorithms, which efficiently modify the original generative model learning algorithm in a black box manner, that output generative models with strong bounds on the probability of sampling protected content. Furthermore, we provide promising experiments for both language (transformers) and image (diffusion) generative models, showing minimal degradation in output quality while ensuring strong protections against sampling protected content.Open AccessOn Provable Copyright Protection for Generative Models
There is a growing concern that learned conditional generative models may output samples that are substantially similar to some copyrighted data $C$ that was in their training set. We give a formal definition of $\textit{near access-freeness (NAF)}$ and prove bounds on the probability that a model satisfying this definition outputs a sample similar to $C$, even if $C$ is included in its training set. Roughly speaking, a generative model $p$ is $\textit{$k$-NAF}$ if for every potentially copyrighted data $C$, the output of $p$ diverges by at most $k$-bits from the output of a model $q$ that $\textit{did not access $C$ at all}$. We also give generative model learning algorithms, which efficiently modify the original generative model learning algorithm in a black box manner, that output generative models with strong bounds on the probability of sampling protected content. Furthermore, we provide promising experiments for both language (transformers) and image (diffusion) generative models, showing minimal degradation in output quality while ensuring strong protections against sampling protected content. - Open Access
- 4 November 2022
- Published by Springer Nature in Theory of Computing Systems
- Vol. 67 (1) , 149-177
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in $\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes $\mathcal { C}$ , by showing that $\mathcal { C}$ admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class ${\mathcal C}$ . Say that a symmetric Boolean functionf(x1,…,xn) issparseif it outputs 1 onO(1) values of ${\sum }_{i} x_{i}$ . We show that for every sparsef, and for all “typical” $\mathcal { C}$ , faster#SAT algorithms for $\mathcal { C}$ circuits imply lower bounds against the circuit class $f \circ \mathcal { C}$ , which may bestrongerthan $\mathcal { C}$ itself. In particular: #SAT algorithms fornk-size $\mathcal { C}$ -circuits running in 2n/nktime (for allk) implyNEXPdoes not have $(f \circ \mathcal { C})$ -circuits of polynomial size. #SAT algorithms for $2^{n^{{\varepsilon }}}$ -size $\mathcal { C}$ -circuits running in $2^{n-n^{{\varepsilon }}}$ time (for someε> 0) implyQuasi-NPdoes not have $(f \circ \mathcal { C})$ -circuits of polynomial size. Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC0∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC0[Williams JACM’14] andACC0∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.- 4 November 2022
- Published by Springer Nature in Theory of Computing Systems
- Vol. 67 (1) , 149-177
Open AccessLower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in $\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes $\mathcal { C}$ , by showing that $\mathcal { C}$ admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class ${\mathcal C}$ . Say that a symmetric Boolean functionf(x1,…,xn) issparseif it outputs 1 onO(1) values of ${\sum }_{i} x_{i}$ . We show that for every sparsef, and for all “typical” $\mathcal { C}$ , faster#SAT algorithms for $\mathcal { C}$ circuits imply lower bounds against the circuit class $f \circ \mathcal { C}$ , which may bestrongerthan $\mathcal { C}$ itself. In particular: #SAT algorithms fornk-size $\mathcal { C}$ -circuits running in 2n/nktime (for allk) implyNEXPdoes not have $(f \circ \mathcal { C})$ -circuits of polynomial size. #SAT algorithms for $2^{n^{{\varepsilon }}}$ -size $\mathcal { C}$ -circuits running in $2^{n-n^{{\varepsilon }}}$ time (for someε> 0) implyQuasi-NPdoes not have $(f \circ \mathcal { C})$ -circuits of polynomial size. Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC0∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC0[Williams JACM’14] andACC0∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class. - Open Access
Multi-Structural Games and Number of Quantifiers
We study multi-structural games, played on two sets $\mathcal{A}$ and $\mathcal{B}$ of structures. These games generalize Ehrenfeucht-Fra\"{i}ss\'{e} games. Whereas Ehrenfeucht-Fra\"{i}ss\'{e} games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the $r$-round game if and only if there is a first-order sentence $\phi$ with at most $r$ quantifiers, where every structure in $\mathcal{A}$ satisfies $\phi$ and no structure in $\mathcal{B}$ satisfies $\phi$. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders.Open AccessMulti-Structural Games and Number of Quantifiers
We study multi-structural games, played on two sets $\mathcal{A}$ and $\mathcal{B}$ of structures. These games generalize Ehrenfeucht-Fra\"{i}ss\'{e} games. Whereas Ehrenfeucht-Fra\"{i}ss\'{e} games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the $r$-round game if and only if there is a first-order sentence $\phi$ with at most $r$ quantifiers, where every structure in $\mathcal{A}$ satisfies $\phi$ and no structure in $\mathcal{B}$ satisfies $\phi$. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders. - Open Access
- 29 June 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-13
Multi-Structural Games and Number of Quantifiers
We study multi-structural games, played on two sets ${\mathcal{A}}$ and ${\mathcal{B}}$ of structures. These games generalize Ehrenfeucht-Fraïssé games. Whereas Ehrenfeucht-Fraïssé games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the r-round game if and only if there is a first-order sentence ϕ with at most r quantifiers, where every structure in ${\mathcal{A}}$ satisfies ϕ and no structure in ${\mathcal{B}}$ satisfies ϕ. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders.- 29 June 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-13
Open AccessMulti-Structural Games and Number of Quantifiers
We study multi-structural games, played on two sets ${\mathcal{A}}$ and ${\mathcal{B}}$ of structures. These games generalize Ehrenfeucht-Fraïssé games. Whereas Ehrenfeucht-Fraïssé games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the r-round game if and only if there is a first-order sentence ϕ with at most r quantifiers, where every structure in ${\mathcal{A}}$ satisfies ϕ and no structure in ${\mathcal{B}}$ satisfies ϕ. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders. - Open Access
Fast Low-Space Algorithms for Subset Sum
We consider the canonical Subset Sum problem: given a list of positive integers $a_1,\ldots,a_n$ and a target integer $t$ with $t > a_i$ for all $i$, determine if there is an $S \subseteq [n]$ such that $\sum_{i \in S} a_i = t$. The well-known pseudopolynomial-time dynamic programming algorithm [Bellman, 1957] solves Subset Sum in $O(nt)$ time, while requiring $\Omega(t)$ space. In this paper we present algorithms for Subset Sum with $\tilde O(nt)$ running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in $\tilde O(nt)$ time and $O(\log(nt))$ space with access to $O(\log n \log \log n+\log t)$ random bits. This significantly improves upon the $\tilde O(n t^{1+\varepsilon})$-time, $\tilde O(n\log t)$-space algorithm of Bringmann (SODA 2017). We also give an $\tilde O(n^{1+\varepsilon}t)$-time, $O(\log(nt))$-space randomized algorithm, improving upon previous $(nt)^{O(1)}$-time $O(\log(nt))$-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a $\mathrm{poly} \log(nt)$-space, $\tilde O(n^2 t)$-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter $1\le k\le \min\{n,t\}$, we present a randomized algorithm running in $\tilde O((n+t)\cdot k)$ time and $O((t/k) \mathrm{polylog} (nt))$ space. As an application of our results, we give an $\tilde{O}(\min\{n^2/\varepsilon, n/\varepsilon^2\})$-time and $\mathrm{polylog}(nt)$-space algorithm for "weak" $\varepsilon$-approximations of Subset Sum.Open AccessFast Low-Space Algorithms for Subset Sum
We consider the canonical Subset Sum problem: given a list of positive integers $a_1,\ldots,a_n$ and a target integer $t$ with $t > a_i$ for all $i$, determine if there is an $S \subseteq [n]$ such that $\sum_{i \in S} a_i = t$. The well-known pseudopolynomial-time dynamic programming algorithm [Bellman, 1957] solves Subset Sum in $O(nt)$ time, while requiring $\Omega(t)$ space. In this paper we present algorithms for Subset Sum with $\tilde O(nt)$ running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in $\tilde O(nt)$ time and $O(\log(nt))$ space with access to $O(\log n \log \log n+\log t)$ random bits. This significantly improves upon the $\tilde O(n t^{1+\varepsilon})$-time, $\tilde O(n\log t)$-space algorithm of Bringmann (SODA 2017). We also give an $\tilde O(n^{1+\varepsilon}t)$-time, $O(\log(nt))$-space randomized algorithm, improving upon previous $(nt)^{O(1)}$-time $O(\log(nt))$-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a $\mathrm{poly} \log(nt)$-space, $\tilde O(n^2 t)$-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter $1\le k\le \min\{n,t\}$, we present a randomized algorithm running in $\tilde O((n+t)\cdot k)$ time and $O((t/k) \mathrm{polylog} (nt))$ space. As an application of our results, we give an $\tilde{O}(\min\{n^2/\varepsilon, n/\varepsilon^2\})$-time and $\mathrm{polylog}(nt)$-space algorithm for "weak" $\varepsilon$-approximations of Subset Sum.