5 papers · 1 filter
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…