13 papers
On Minimax Optimality and Uniqueness of Fixed-Step First-Order Methods for Smooth Convex Optimization
Benjamin Grimmer, Sunghyeon Jo, Chanwoo Park
This paper considers the design of optimal fixed-step first-order methods for high-dimensional minimization of -smooth convex functions. For optimizing worst-case performance me…
Implicit Primal-Dual Guarantees in Unconstrained First-Order Minimization
Benjamin Grimmer, Alex L. Wang
This work considers the design of first-order convex optimization algorithms and convergence proofs. In particular, we consider nonsmooth Lipschitz and smooth problems accessed thr…
A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms
TaeHo Yoon, Benjamin Grimmer
In this work, we reveal a rich combinatorial structure underlying exact minimax optimal algorithms for classical nonexpansive fixed-point problems. This viewpoint unifies all extre…
Nonsmooth Riemannian optimization with inexact manifold primitives via bundle methods
Mateo Díaz, Benjamin Grimmer, Ian McPherson
Optimization on Hadamard manifolds -- the natural Riemannian setting for globally geodesically convex problems -- relies on exponential maps to retract tangent vectors and parallel…
Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets
Benjamin Grimmer, Ning Liu
We consider the oracle complexity of constrained convex optimization given access to a Linear Minimization Oracle (LMO) for the constraint set and a gradient oracle for the -smo…
Subgame Perfect Methods in Nonsmooth Convex Optimization
Benjamin Grimmer, Alex L. Wang
This paper considers nonsmooth convex optimization with either a subgradient or proximal operator oracle. In both settings, we identify algorithms that achieve the recently introdu…
H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms
TaeHo Yoon, Ernest K. Ryu, Benjamin Grimmer
For nonexpansive fixed-point problems, Halpern's method with optimal parameters, its so-called H-dual algorithm, and in fact, an infinite family of algorithms containing them, all…
A Practical Adaptive Subgame Perfect Gradient Method
Alan Luner, Benjamin Grimmer
We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect G…
Some New Insights from Highly Optimized Polyhedral Passages
Raj Gosain, Benjamin Grimmer
A shape possesses Rupert's property if a hole can be cut through it such that a second identical copy of the shape can cleanly pass straight through the interior of the first. Such…
A Universally Optimal Primal-Dual Method for Minimizing Heterogeneous Compositions
Aaron Zoll, Benjamin Grimmer
This paper proposes a universal algorithm for convex minimization problems of the composite form . We allow each to independently range…
Some Unified Theory for Variance Reduced Prox-Linear Methods
Yue Wu, Benjamin Grimmer
This work considers the nonconvex, nonsmooth problem of minimizing a composite objective of the form where the inner mapping is a smooth finite summation or expe…
Beyond Minimax Optimality: A Subgame Perfect Gradient Method
Benjamin Grimmer, Kevin Shu, Alex L. Wang
The study of convex optimization has historically been concerned with worst-case convergence rates. The development of the Optimized Gradient Method (OGM), due to \citet{drori2012P…
Goldstein Stationarity in Lipschitz Constrained Optimization
Benjamin Grimmer, Zhichao Jia
We prove the first convergence guarantees for a subgradient method minimizing a generic Lipschitz function over generic Lipschitz inequality constraints. No smoothness or convexity…