290 citations · 492 across the 36 of their papers we have counts for
19 papers · 1 filter
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…
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…
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…
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…
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…
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…
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…
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…
Wasserstein barycenters are NP-hard to compute
Jason M. Altschuler, Enric Boix-Adsera
Computing Wasserstein barycenters (a.k.a. Optimal Transport barycenters) is a fundamental problem in geometry which has recently attracted considerable attention due to many applic…
Hardness results for Multimarginal Optimal Transport problems
Jason M. Altschuler, Enric Boix-Adsera
Multimarginal Optimal Transport (MOT) is the problem of linear programming over joint probability distributions with fixed marginals. A key issue in many applications is the comple…
Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure
Jason M. Altschuler, Enric Boix-Adsera
Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the s…
Wasserstein barycenters can be computed in polynomial time in fixed dimension
Jason M. Altschuler, Enric Boix-Adsera
Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whe…
Near-linear convergence of the Random Osborne algorithm for Matrix Balancing
Jason M. Altschuler, Pablo A. Parrilo
We revisit Matrix Balancing, a pre-conditioning task used ubiquitously for computing eigenvalues and matrix exponentials. Since 1960, Osborne's algorithm has been the practitioners…
Lyapunov Exponent of Rank One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution
Jason M. Altschuler, Pablo A. Parrilo
The Lyapunov exponent corresponding to a set of square matrices and a probability distribution over is $λ(\mathcal{A},p)…