35 citations · 69 across the 16 of their papers we have counts for
19 papers
High-dimensional Limit of SGD for Diagonal Linear Networks
Begoña García Malaxechebarría, Courtney Paquette, Maryam Fazel +1
Understanding the behavior of stochastic gradient methods is a central problem in modern machine learning. Recent work has highlighted diagonal linear networks as a simplified yet…
Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Models
Alexander Atanasov, Blake Bordelon, Jacob A. Zavatone-Veth +2
We derive a novel deterministic equivalence for the two-point function of a random matrix resolvent. Using this result, we give a unified derivation of the performance of a wide va…
Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems
Tomás González, Cristóbal Guzmán, Courtney Paquette
We study the problem of differentially-private (DP) stochastic (convex-concave) saddle-points in the setting. We propose -DP algorithms based on stochast…
Implicit Diffusion: Efficient Optimization through Stochastic Sampling
Pierre Marion, Anna Korba, Peter Bartlett +6
We present a new algorithm to optimize distributions defined implicitly by parameterized stochastic diffusions. Doing so allows us to modify the outcome distribution of sampling pr…
Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index models
Elizabeth Collins-Woodfin, Courtney Paquette, Elliot Paquette +1
We analyze the dynamics of streaming stochastic gradient descent (SGD) in the high-dimensional limit when applied to generalized linear models and multi-index models (e.g. logistic…
Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime
Leonardo Cunha, Gauthier Gidel, Fabian Pedregosa +2
The recently developed average-case analysis of optimization methods allows a more fine-grained and representative convergence analysis than usual worst-case results. In exchange,…
Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions
Courtney Paquette, Elliot Paquette, Ben Adlam +1
Stochastic gradient descent (SGD) is a pillar of modern machine learning, serving as the go-to optimization algorithm for a diverse array of problems. While the empirical success o…
Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensions
Kiwon Lee, Andrew N. Cheng, Courtney Paquette +1
We analyze the dynamics of large batch stochastic gradient descent with momentum (SGD+M) on the least squares problem when both the number of samples and dimensions are large. In t…
Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties
Courtney Paquette, Elliot Paquette, Ben Adlam +1
We develop a stochastic differential equation, called homogenized SGD, for analyzing the dynamics of stochastic gradient descent (SGD) on a high-dimensional random least squares pr…
Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models
Courtney Paquette, Elliot Paquette
We analyze a class of stochastic gradient algorithms with momentum on a high-dimensional random least squares problem. Our framework, inspired by random matrix theory, provides an…
SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
Courtney Paquette, Kiwon Lee, Fabian Pedregosa +1
We propose a new framework, inspired by random matrix theory, for analyzing the dynamics of stochastic gradient descent (SGD) when both number of samples and dimensions are large.…
Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis
Courtney Paquette, Bart van Merriënboer, Elliot Paquette +1
Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior…
A termination criterion for stochastic gradient descent for binary classification
Sina Baghal, Courtney Paquette, Stephen A. Vavasis
We propose a new, simple, and computationally inexpensive termination test for constant step-size stochastic gradient descent (SGD) applied to binary classification on the logistic…
Potential-based analyses of first-order methods for constrained and composite optimization
Courtney Paquette, Stephen Vavasis
We propose potential-based analyses for first-order algorithms applied to constrained and composite minimization problems. We first propose ``idealized'' frameworks for algorithms…
A Stochastic Line Search Method with Convergence Rate Analysis
Courtney Paquette, Katya Scheinberg
For deterministic optimization, line-search methods augment algorithms by providing stability and improved efficiency. We adapt a classical backtracking Armijo line-search to the s…
Subgradient methods for sharp weakly convex functions
Damek Davis, Dmitriy Drusvyatskiy, Kellie J. MacPhee +1
Subgradient methods converge linearly on a convex function that grows sharply away from its solution set. In this work, we show that the same is true for sharp functions that are o…
The nonsmooth landscape of phase retrieval
Damek Davis, Dmitriy Drusvyatskiy, Courtney Paquette
We consider a popular nonsmooth formulation of the real phase retrieval problem. We show that under standard statistical assumptions, a simple subgradient method converges linearly…
Catalyst Acceleration for Gradient-Based Non-Convex Optimization
Courtney Paquette, Hongzhou Lin, Dmitriy Drusvyatskiy +2
We introduce a generic scheme to solve nonconvex optimization problems using gradient-based algorithms originally designed for minimizing convex functions. Even though these method…
Efficiency of minimizing compositions of convex functions and smooth maps
Dmitriy Drusvyatskiy, Courtney Paquette
We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rel…