290 citations · 492 across the 36 of their papers we have counts for
38 papers
Stepsize Hedging: an Alternative Mechanism for Accelerating Gradient Descent
Jason M. Altschuler, Pablo A. Parrilo
Can gradient descent be accelerated by just choosing better stepsizes? Surprisingly, the answer is yes. This short expository article provides an accessible introduction to this ph…
Negative Momentum for Convex-Concave Optimization
Henry Shugart, Shuyi Wang, Jason M. Altschuler
This paper revisits momentum in the context of min-max optimization. Momentum is a celebrated mechanism for accelerating gradient dynamics in settings like convex minimization, but…
Algorithmic warm starts for Hamiltonian Monte Carlo
Matthew S. Zhang, Jason M. Altschuler, Sinho Chewi
Generating samples from a continuous probability density is a central algorithmic problem across statistics, engineering, and the sciences. For high-dimensional settings, Hamiltoni…
Min-Max Optimization Is Strictly Easier Than Variational Inequalities
Henry Shugart, Jason M. Altschuler
Classically, a mainstream approach for solving a convex-concave min-max problem is to instead solve the variational inequality problem arising from its first-order optimality condi…
Optimized methods for composite optimization: a reduction perspective
Jinho Bok, Jason M. Altschuler
Recent advances in convex optimization have leveraged computer-assisted proofs to develop optimized first-order methods that improve over classical algorithms. However, each optimi…
Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
Jason M. Altschuler, Sinho Chewi, Matthew S. Zhang
Acceleration is a celebrated cornerstone of convex optimization, enabling gradient-based algorithms to converge sublinearly in the condition number. A major open question is whethe…
Negative Stepsizes Make Gradient-Descent-Ascent Converge
Henry Shugart, Jason M. Altschuler
Efficient computation of min-max problems is a central question in optimization, learning, games, and control. Arguably the most natural algorithm is gradient-descent-ascent (GDA).…
Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm
Xufeng Cai, Jason M. Altschuler, Jelena Diakonikolas
In 1960, Osborne proposed a simple iterative algorithm for matrix balancing with outstanding numerical performance. Today, it is the default preconditioning procedure before eigenv…
Shifted Composition III: Local Error Framework for KL Divergence
Jason M. Altschuler, Sinho Chewi
Coupling arguments are a central tool for bounding the deviation between two stochastic processes, but traditionally have been limited to Wasserstein metrics. In this paper, we app…
Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule
Jason M. Altschuler, Pablo A. Parrilo
We show that for separable convex optimization, random stepsizes fully accelerate Gradient Descent. Specifically, using inverse stepsizes i.i.d. from the Arcsine distribution impro…
Accelerating Proximal Gradient Descent via Silver Stepsizes
Jinho Bok, Jason M. Altschuler
Surprisingly, recent work has shown that gradient descent can be accelerated without using momentum -- just by judiciously choosing stepsizes. An open question raised by several pa…
Shifted Interpolation for Differential Privacy
Jinho Bok, Weijie Su, Jason M. Altschuler
Noisy gradient descent and its variants are the predominant algorithms for differentially private machine learning. It is a fundamental question to quantify their privacy leakage,…
Shifted Composition II: Shift Harnack Inequalities and Curvature Upper Bounds
Jason M. Altschuler, Sinho Chewi
We apply the shifted composition rule -- an information-theoretic principle introduced in our earlier work [AC23] -- to establish shift Harnack inequalities for the Langevin diffus…
Shifted Composition I: Harnack and Reverse Transport Inequalities
Jason M. Altschuler, Sinho Chewi
We formulate a new information-theoretic principle--the shifted composition rule--which bounds the divergence (e.g., Kullback-Leibler or Rényi) between the laws of two stochastic p…
Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization
Jason M. Altschuler, Pablo A. Parrilo
We provide a concise, self-contained proof that the Silver Stepsize Schedule proposed in Part I directly applies to smooth (non-strongly) convex optimization. Specifically, we show…
Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
Jason M. Altschuler, Pablo A. Parrilo
Can we accelerate convergence of gradient descent without changing the algorithm -- just by carefully choosing stepsizes? Surprisingly, we show that the answer is yes. Our proposed…
Faster high-accuracy log-concave sampling via algorithmic warm starts
Jason M. Altschuler, Sinho Chewi
Understanding the complexity of sampling from a strongly log-concave and log-smooth distribution on to high accuracy is a fundamental problem, both from a practi…
Concentration of the Langevin Algorithm's Stationary Distribution
Jason M. Altschuler, Kunal Talwar
A canonical algorithm for log-concave sampling is the Langevin Algorithm, aka the Langevin Diffusion run with some discretization stepsize . This discretization leads the Lan…
Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling
Jason M. Altschuler, Kunal Talwar
Sampling from a high-dimensional distribution is a fundamental task in statistics, engineering, and the sciences. A canonical approach is the Langevin Algorithm, i.e., the Markov c…
Flows, Scaling, and Entropy Revisited: a Unified Perspective via Optimizing Joint Distributions
Jason M. Altschuler
In this short expository note, we describe a unified algorithmic perspective on several classical problems which have traditionally been studied in different communities. This pers…
Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss
Jason M. Altschuler, Kunal Talwar
A central issue in machine learning is how to train models on sensitive user data. Industry has widely adopted a simple algorithm: Stochastic Gradient Descent with noise (a.k.a. St…
Asymptotics for semi-discrete entropic optimal transport
Jason M. Altschuler, Jonathan Niles-Weed, Austin J. Stromme
We compute exact second-order asymptotics for the cost of an optimal solution to the entropic optimal transport problem in the continuous-to-discrete, or semi-discrete, setting. In…
Kernel approximation on algebraic varieties
Jason M. Altschuler, Pablo A. Parrilo
Low-rank approximation of kernels is a fundamental mathematical problem with widespread algorithmic applications. Often the kernel is restricted to an algebraic variety, e.g., in p…
Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent
Jason M. Altschuler, Sinho Chewi, Patrik Gerber +1
We study first-order optimization algorithms for computing the barycenter of Gaussian distributions with respect to the optimal transport metric. Although the objective is geodesic…