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 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.
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
We consider convex optimization with nonlinear inequality constraints and develop a primal--dual multiplier framework that is consistent in continuous and discrete time. We first propose continuous-time dynamics with Nesterov-type vanishing damping $\alpha/t$, together with suitable extrapolations of the dual variable and the nonlinear constraint mapping. Under convexity assumptions and $\alpha\geq3$, we establish $\mathcal O(t^{-2})$ convergence rates for both nonlinear feasibility and the objective residual. We then derive an inexact accelerated primal--dual algorithm through a compatible discretization of a perturbed version of the dynamics. For composite convex objectives, a weighted summability condition on the primal inexactness yields the $\mathcal O(k^{-2})$ rates for feasibility and the objective residual, thereby matching the accelerated rates of their continuous-time counterparts. To the best of our knowledge, this 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 from PAL guarantees.
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. For nonsmooth Lipschitz objectives satisfying quadratic growth, the proposed bundle-level W-certificate method (BLW) achieves the optimal complexity without requiring the growth modulus or target accuracy as input. We then introduce an accelerated variant, A-BLW. Without knowing the H\"older smoothness parameters, the quadratic-growth modulus, or the target accuracy, A-BLW attains the optimal rates in the nonsmooth, weakly smooth, and smooth regimes. Central to both methods is an affine W-certificate, a condition based on the descent-slowness of an affine minorant that converts the geometry of a bundle model into an optimality-gap guarantee under quadratic growth. A stopping-time analysis further shows that the same A-BLW algorithm, without modification, achieves the corresponding best-known rates for general convex objectives and for objectives satisfying H\"older growth of order at least two. Numerical experiments illustrate the practical performance of the proposed methods.
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.
