Benjamin Grimmer

A Complete Characterization of Optimal Subgradient Methods for Lipschitz Convex Minimization

Categories Nonsmooth Optimization, Semi-definite Programming Tags ,

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. We provide a complete characterization of every optimal fixed-step method. Moreover, we show … Read more

Inexactly Smooth Performance Estimation and New Optimized Gradient Methods

Categories Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

  We consider a general class of “inexactly smooth” convex functions, providing a universal model capturing as special cases $L$-smooth, $M$-Lipschitz, and H\”older smooth functions, and any combination thereof. Such functions possess a calculus closely following that of smooth functions. Our main results provide inexactly smooth functions with interpolation theorems that are necessary and sufficient … Read more

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

Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

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 have a nontrivial initial burn-in phase. We present a parameter-free approach for restarting … Read more

Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets

Categories Convex Optimization Tags , , ,

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 $L$-smooth, $L$-strongly convex objective. This model includes Frank-Wolfe methods and their many variants. Over the problem class of $\alpha$-strongly convex constraint sets $S$, we demonstrate that one can … Read more

An Elementary Proof of the Near Optimality of LogSumExp Smoothing

Categories Convex Optimization, Data Science Algorithms, Nonsmooth Optimization Tags , , , ,

We consider the design of smoothings of the (coordinate-wise) max function in $\mathbb{R}^d$ in the infinity norm. The LogSumExp function $f(x)=\ln(\sum^d_i\exp(x_i))$ provides a classical smoothing, differing from the max function in value by at most $\ln(d)$. We provide an elementary construction of a lower bound, establishing that every overestimating smoothing of the max function must … Read more

Subgame Perfect Methods in Nonsmooth Convex Optimization

Categories Convex Optimization, Nonsmooth Optimization

This paper considers nonsmooth convex optimization with either a subgradient or proximal operator oracle. In both settings, we identify algorithms that achieve the recently introduced game-theoretic optimality notion for algorithms known as subgame perfection. Subgame perfect algorithms meet a more stringent requirement than just minimax optimality. Not only must they provide optimal uniform guarantees on … Read more

A Practical Adaptive Subgame Perfect Gradient Method

Categories Convex Optimization, Second-Order Cone Programming Tags , , , , , ,

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 Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on … Read more

The Optimal Smoothings of Sublinear Functions and Convex Cones

Categories Convex and Nonsmooth Optimization Tags , , , ,

This paper considers the problem of smoothing convex functions and sets, seeking the nearest smooth convex function or set to a given one. For convex cones and sublinear functions, a full characterization of the set of all optimal smoothings is given. These provide if and only if characterizations of the set of optimal smoothings for … Read more

A Universally Optimal Primal-Dual Method for Minimizing Heterogeneous Compositions

Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

This paper proposes a universal, optimal algorithm for convex minimization problems of the composite form $g_0(x)+h(g_1(x),\dots, g_m(x)) + u(x)$. We allow each $g_j$ to independently range from being nonsmooth Lipschitz to smooth, from convex to strongly convex, described by notions of H\”older continuous gradients and uniform convexity. Note that, although the objective is built from … Read more

Some Unified Theory for Variance Reduced Prox-Linear Methods

Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

This work considers the nonconvex, nonsmooth problem of minimizing a composite objective of the form $f(g(x))+h(x)$ where the inner mapping $g$ is a smooth finite summation or expectation amenable to variance reduction. In such settings, prox-linear methods can enjoy variance-reduced speed-ups despite the existence of nonsmoothness. We provide a unified convergence theory applicable to a … Read more