Benjamin Grimmer

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 $L$-smooth convex functions. For optimizing worst-case performance measured via suboptimality of the final function value (relative to the initial squared distance to a minimizer), we provide an algebraic …

Some Unified Theory for Variance Reduced Prox-Linear Methods

Yue Wu, Benjamin Grimmer

Abstract. This work considers the nonconvex, nonsmooth problem of minimizing a composite objective of the form [Formula: see text] where the inner mapping [Formula: see text] is a smooth finite summation or expectation amenable to variance reduction. In such settings, prox-linear methods …

us (code pays fourni par la source)

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 through a subgradient or gradient oracle, respectively. For the general class of fixed-step first-order methods, prior work on Performance …

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 through a subgradient or gradient oracle, respectively. For the general class of fixed-step first-order methods, prior work on Performance …

us (code pays fourni par la source)

A Complete Characterization of Optimal Subgradient Methods for Lipschitz Convex Minimization

Aaron Zoll, Benjamin Grimmer

We consider the design of optimal fixed-step first-order methods for $M$-Lipschitz convex optimization given $\|x_0-x_\star\|\leq D$. Prior works have identified several distinct fixed-step methods, parameterized by a matrix of stepsizes $W$, with the (information-theoretic) minimax optimal rate $MD/\sqrt{N+1}$ of objective gap convergence. …

A Complete Characterization of Optimal Subgradient Methods for Lipschitz Convex Minimization

Aaron Zoll, Benjamin Grimmer

We consider the design of optimal fixed-step first-order methods for $M$-Lipschitz convex optimization given $\|x_0-x_\star\|\leq D$. Prior works have identified several distinct fixed-step methods, parameterized by a matrix of stepsizes $W$, with the (information-theoretic) minimax optimal rate $MD/\sqrt{N+1}$ of objective gap convergence. …

us (code pays fourni par la source)

Performance estimation for smooth and strongly convex sets

Alan Luner, Benjamin Grimmer

us (code pays fourni par la source)

The Optimal Smoothings of Sublinear Functions and Convex Cones

Thabo Samakhoana, Benjamin Grimmer

us (code pays fourni par la source)

Inexactly Smooth Performance Estimation and New Optimized Gradient Methods

Aaron Zoll, Benjamin Grimmer

We consider a general class of ``inexactly smooth'' convex functions, providing a universal model capturing as special cases $L$-smooth, $M$-Lipschitz, and Hölder smooth functions, and any combination thereof. Such functions possess a calculus closely following that of smooth functions. Our main results …

Inexactly Smooth Performance Estimation and New Optimized Gradient Methods

Aaron Zoll, Benjamin Grimmer

We consider a general class of ``inexactly smooth'' convex functions, providing a universal model capturing as special cases $L$-smooth, $M$-Lipschitz, and Hölder smooth functions, and any combination thereof. Such functions possess a calculus closely following that of smooth functions. Our main results …

us (code pays fourni par la source)

A Parameter-Free Restart Scheme with Only a Parallelizable $\log\log(1/ε)$ Overhead

Yue Wu, Benjamin Grimmer

It is well-known that first-order methods can offer accelerated convergence rates in the presence of growth structures. Restarting schemes provide a general tool for such speed-ups. These schemes typically either require unrealistic problem knowledge, incur logarithmic overhead factors in oracle complexity, and/or …

A Parameter-Free Restart Scheme with Only a Parallelizable $\log\log(1/ε)$ Overhead

Yue Wu, Benjamin Grimmer

It is well-known that first-order methods can offer accelerated convergence rates in the presence of growth structures. Restarting schemes provide a general tool for such speed-ups. These schemes typically either require unrealistic problem knowledge, incur logarithmic overhead factors in oracle complexity, and/or …

us (code pays fourni par la source)