Aaron Zoll

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 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