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 every optimal fixed-step method can be derived from the constructive approach of~\cite{constructive_approach} and provide a polyhedral representation of the set of optimal methods through proof multipliers. From this characterization, we show that no anytime optimal fixed-step subgradient methods exist.
It is shown that any first-order method guaranteeing a bound on the primal objective gap f(x_N)-f(x_\star) assuming only a bound on $\|x_0-x_\star\|$ actually has a stronger guarantee on an explicit, computable primal-dual gap at the same rate.
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 proof of the optimality of the optimized gradient method (OGM) and establish its uniqueness among all fixed-step first-order methods. For the alternative measure of final squared gradient norm (relative to initial suboptimality), we prove the OGM-G method is optimal and uniquely so among fixed-step first-order methods. Finally, for the setting measuring the final squared gradient norm (relative to the initial squared distance to a minimizer), we show the recently proposed Lemniscate method is optimal and uniquely so. Our proofs rely on algebraic reductions for lower bound arguments rather than traditional information-theoretic bounds, which were previously only able to establish OGM's optimality but not uniqueness.
Benjamin Grimmer, Sunghyeon Jo, Chanwoo Park· 0 citations
A global iteration complexity bound is established for the smallest gradient norm among the first $k$ iterates for the smallest gradient norm among the first $k$ iterates when the initial sublevel set is bounded.
We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on $\mathbb{R}^d$. We prove that, for a finite horizon $n$ and a constant stepsize $\eta=\Theta(1/\sqrt n)$, the last iterate achieves an optimization error of order $d/\sqrt n$, showing that the extra $\log n$ factor appearing in high dimensions is unnecessary in every fixed dimension. We complement this result with a matching linear-in-$d$ lower bound and show that the sharp worst-case dimension-horizon dependence is of order $\min\{d,\log n\}/\sqrt n$. This solves, in particular, a COLT open problem posed by Koren and Segal in 2020 and shows that the correct dependence on the dimension is linear rather than logarithmic.
Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate stationarity, and its minimization usually implies stronger results than those for minimization of function values. In this work, we study gradient-norm minimization for convex functions that are $(L,\kappa)$-H\"older smooth with respect to the $\ell_p$-norms, $p \geq 1$. We develop algorithms that achieve near-optimal gradient-oracle complexity for this problem. In the smooth case, our results resolve the previously open setting $p>2$. For H\"older-smooth objectives, we close the complexity gap throughout the full $p$-range, including to the best of our knowledge, a gap in the Euclidean case. We provide two families of algorithms: the first one comes with a simple iteration and generalizes a phenomenon known as mirror duality, exploiting dual behaviours of algorithms with errors and inexact computations. The second makes use of accumulating regularizers centered at different approximate solutions, which we sequentially minimize in order to provide our near-optimal rates.
Nico Pelleriti, Maryam Shiran, David Martínez-Rubio et al.· 0 citations
We investigate the optimization problem of minimizing a nonsmooth function that satisfies a nonsmooth version of the descent lemma over a nonempty and closed but not necessarily convex set. The objective function belongs to the class of upper-$\mathcal{C}^2$ functions, whereas the constraints may promote a sparse or low-rank structure. We propose a projected subgradient method with two different globalization strategies: (a) a nonmonotone linesearch and, under additional assumptions, (b) an auto-conditioned method, where the stepsize is given by a formula depending on data from past iterations. We show that both methods converge to solutions that satisfy a stronger stationarity concept than one would expect from the subdifferential sum-rule, which is particularly important since the optimization problems of interest are inherently nonconvex. Finally, we present promising numerical results when applying the algorithm to an MPEC-style problem as well as the matrix optimization problems MAXCUT and Robust PCA.
Christian Kanzow, Jannis Krüger, Leo Lehmann· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
