68 citations · 477 across the 37 of their papers we have counts for
39 papers
Universality of high-dimensional scaling limits of stochastic gradient descent
Reza Gheissari, Aukosh Jagannath
We consider statistical tasks in high dimensions whose loss depends on the data only through its projection into a fixed-dimensional subspace spanned by the parameter vectors and c…
High-dimensional limit theorems for SGD: Momentum and Adaptive Step-sizes
Aukosh Jagannath, Taj Jones-McCormick, Varnan Sarangian
We develop a high-dimensional scaling limit for Stochastic Gradient Descent with Polyak Momentum (SGD-M) and adaptive step-sizes. This provides a framework to rigourously compare o…
Pseudo-Maximum Likelihood Theory for High-Dimensional Rank One Inference
Curtis Grant, Aukosh Jagannath, Justin Ko
We develop a pseudo-likelihood theory for rank one matrix estimation problems in the high dimensional limit. We prove a variational principle for the limiting pseudo-maximum likeli…
Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Models
Taj Jones-McCormick, Aukosh Jagannath, Subhabrata Sen
Unsupervised pre-training and transfer learning are commonly used techniques to initialize training algorithms for neural networks, particularly in settings with limited labeled da…
Local geometry of high-dimensional mixture models: Effective spectral theory and dynamical transitions
Gerard Ben Arous, Reza Gheissari, Jiaoyang Huang +1
We study the local geometry of empirical risks in high dimensions via the spectral theory of their Hessian and information matrices. We focus on settings where the data, $(Y_\ell)_…
Finding planted cliques using gradient descent
Reza Gheissari, Aukosh Jagannath, Yiming Xu
The planted clique problem is a paradigmatic model of statistical-to-computational gaps: the planted clique is information-theoretically detectable if its size but…
Spectral alignment of stochastic gradient descent for high-dimensional classification tasks
Gerard Ben Arous, Reza Gheissari, Jiaoyang Huang +1
We rigorously study the relation between the training dynamics via stochastic gradient descent (SGD) and the spectra of empirical Hessian and gradient matrices. We prove that in tw…
Shattering in the Ising Pure -Spin Model
David Gamarnik, Aukosh Jagannath, Eren C. Kızıldağ
We study the Ising pure -spin model for large . We investigate the landscape of the Hamiltonian of this model. We show that for any and any large enough , the model…
Optimality of Message-Passing Architectures for Sparse Graphs
Aseem Baranwal, Kimon Fountoulakis, Aukosh Jagannath
We study the node classification problem on feature-decorated graphs in the sparse setting, i.e., when the expected degree of a node is in the number of nodes, in the fixed-…
Existence of the free energy for heavy-tailed spin glasses
Aukosh Jagannath, Patrick Lopatto
We study the free energy of a mean-field spin glass whose coupling distribution has power law tails. Under the assumption that the couplings have infinite variance and finite mean,…
Differentially private multivariate medians
Kelly Ramsay, Aukosh Jagannath, Shoja'eddin Chenouri
Statistical tools which satisfy rigorous privacy guarantees are necessary for modern data analysis. It is well-known that robustness against contamination is linked to differential…
High-dimensional limit theorems for SGD: Effective dynamics and critical scaling
Gerard Ben Arous, Reza Gheissari, Aukosh Jagannath
We study the scaling limits of stochastic gradient descent (SGD) with constant step-size in the high-dimensional regime. We prove limit theorems for the trajectories of summary sta…
Effects of Graph Convolutions in Multi-layer Networks
Aseem Baranwal, Kimon Fountoulakis, Aukosh Jagannath
Graph Convolutional Networks (GCNs) are one of the most popular architectures that are used to solve classification problems accompanied by graphical information. We present a rigo…
Graph Attention Retrospective
Kimon Fountoulakis, Amit Levi, Shenghao Yang +2
Graph-based learning is a rapidly growing sub-field of machine learning with applications in social networks, citation networks, and bioinformatics. One of the most popular models…
Circuit Lower Bounds for the p-Spin Optimization Problem
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
We consider the problem of finding a near ground state of a -spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent w…
A simple construction of the dynamical model
Aukosh Jagannath, Nicolas Perkowski
The equation is a singular stochastic PDE with important applications in mathematical physics. Its solution usually requires advanced mathematical theories like regularity…
Shattering Versus Metastability in Spin Glasses
Gérard Ben Arous, Aukosh Jagannath
Our goal in this work is to better understand the relationship between replica symmetry breaking, shattering, and metastability. To this end, we study the static and dynamic behavi…
Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
Aseem Baranwal, Kimon Fountoulakis, Aukosh Jagannath
Recently there has been increased interest in semi-supervised classification in the presence of graphical information. A new class of learning models has emerged that relies, at it…
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Two concrete problems we consider are (a) optimizing the Hamil…
Online stochastic gradient descent on non-convex losses from high-dimensional inference
Gerard Ben Arous, Reza Gheissari, Aukosh Jagannath
Stochastic gradient descent (SGD) is a popular algorithm for optimization problems arising in high-dimensional inference tasks. Here one produces an estimator of an unknown paramet…
The Overlap Gap Property and Approximate Message Passing Algorithms for -spin models
David Gamarnik, Aukosh Jagannath
We consider the algorithmic problem of finding a near ground state (near optimal solution) of a -spin model. We show that for a class of algorithms broadly defined as Approximat…
The Overlap Gap Property in Principal Submatrix Recovery
David Gamarnik, Aukosh Jagannath, Subhabrata Sen
We study support recovery for a principal submatrix with elevated mean , hidden in an symmetric mean zero Gaussian matrix. Here is a universal c…
Statistical thresholds for Tensor PCA
Aukosh Jagannath, Patrick Lopatto, Leo Miolane
We study the statistical limits of testing and estimation for a rank one deformation of a Gaussian random tensor. We compute the sharp thresholds for hypothesis testing and estimat…
Bounding flows for spherical spin glass dynamics
Gerard Ben Arous, Reza Gheissari, Aukosh Jagannath
We introduce a new approach to studying spherical spin glass dynamics based on differential inequalities for one-time observables. Using this approach, we obtain an approximate pha…