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.
Abstract
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 Estimation Problems (PEPs) has shown that structured, tight convergence proofs typically exist. Under mild conditions, we further show 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. These implicit optimal dual certificates, which take the form of affine lower bounds, also provide insight into the role of auxiliary sequences in momentum methods.
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 obje...
The main contribution is a finite-time mechanism for converting stationarity of the truncated minimax problem into a KKT certificate for the original constrained problem and establishing explicit convergence rates for the proposed method in terms of the KKT residual.
This work proposes a computationally efficient algorithm that achieves the optimal $O(1/\sqrt{T})$ convergence rate, matching the lower bound, and closes the existing gap in one dimension, providing the first sharp rate guarantee in this setting.
A. Carpentier, Chloé Rouyer, Alexandre B. Tsybakov et al.· 0 citations
This work considers convex optimization with nonlinear inequality constraints and develops a primal-dual multiplier framework that is consistent in continuous and discrete time and is the first Nesterov-type primal-dual multiplier framework for convex optimization with nonlinear inequality constraints.
Three inexact AL schemes are developed that preserve the standard AL subproblem structure and attain the optimal primal-dual complexity in the convex setting, improving prior AL bounds of $\mathcal O(\epsilon^{-4/3})$, $\mathcal O(\epsilon^{-7/4})$, and $\mathcal O(\epsilon^{-2})$, and removing the logarithmic factor f...
Arnesh Sujanani, Saeed Ghadimi, Henry Wolkowicz· 0 citations
We study deterministic first-order minimization of a convex function without prior knowledge of the objective's growth, smoothness regime, or associated parameters. We develop anytime, parameter-free bundle-level methods that adapt simultaneously to these unknown properties and attain best-known oracle complexities. Fo...
Liwei Jiang, Ke Tang, Zhe Zhang· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
