Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity
- URL: http://arxiv.org/abs/2305.14161v1
- Date: Tue, 23 May 2023 15:26:36 GMT
- Title: Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity
- Authors: Xiao Li, Lei Zhao, Daoli Zhu, Anthony Man-Cho So
- Abstract summary: Subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization.
In this work, we first extend the typical complexity results for the subgradient method to convex and weakly convex objective functions.
We provide convergence results for non-Lipschitz convex and weakly convex objective functions using proper diminishing rules on the step sizes.
- Score: 29.56022052936922
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The subgradient method is one of the most fundamental algorithmic schemes for
nonsmooth optimization. The existing complexity and convergence results for
this algorithm are mainly derived for Lipschitz continuous objective functions.
In this work, we first extend the typical complexity results for the
subgradient method to convex and weakly convex minimization without assuming
Lipschitz continuity. Specifically, we establish $\mathcal{O}(1/\sqrt{T})$
bound in terms of the suboptimality gap ``$f(x) - f^*$'' for convex case and
$\mathcal{O}(1/{T}^{1/4})$ bound in terms of the gradient of the Moreau
envelope function for weakly convex case. Furthermore, we provide convergence
results for non-Lipschitz convex and weakly convex objective functions using
proper diminishing rules on the step sizes. In particular, when $f$ is convex,
we show $\mathcal{O}(\log(k)/\sqrt{k})$ rate of convergence in terms of the
suboptimality gap. With an additional quadratic growth condition, the rate is
improved to $\mathcal{O}(1/k)$ in terms of the squared distance to the optimal
solution set. When $f$ is weakly convex, asymptotic convergence is derived. The
central idea is that the dynamics of properly chosen step sizes rule fully
controls the movement of the subgradient method, which leads to boundedness of
the iterates, and then a trajectory-based analysis can be conducted to
establish the desired results. To further illustrate the wide applicability of
our framework, we extend the complexity results to the truncated subgradient,
the stochastic subgradient, the incremental subgradient, and the proximal
subgradient methods for non-Lipschitz functions.
Related papers
- A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization.
In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
arXiv Detail & Related papers (2023-01-10T20:43:29Z) - Convergence rate of the (1+1)-evolution strategy on locally strongly
convex functions with lipschitz continuous gradient and their monotonic
transformations [20.666734673282498]
Evolution strategy (ES) is one of promising classes of algorithms for black-box continuous optimization.
In this study, an upper bound and a lower bound of the rate of linear convergence of the (1+1)-ES on locally $L$-strongly convex functions with $U$-Lipschitz continuous gradient are derived.
arXiv Detail & Related papers (2022-09-26T07:16:50Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
arXiv Detail & Related papers (2022-06-30T02:17:11Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$.
We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
arXiv Detail & Related papers (2022-06-17T06:10:20Z) - Accelerated first-order methods for convex optimization with locally
Lipschitz continuous gradient [0.0]
We first consider unconstrained convex optimization with Lipschitz continuous gradient (LLCG) and propose accelerated proximal gradient (APG) methods for solving it.
The proposed APG methods are equipped with a verifiable termination criterion and enjoy an operation complexity of $cal O(varepsilon-1/2log varepsilon-1)$.
Preliminary numerical results are presented to demonstrate the performance of our proposed methods.
arXiv Detail & Related papers (2022-06-02T10:34:26Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
We structured convex optimization problems with additive objective $r:=p + q$, where $r$ is $mu$-strong convex similarity.
We proposed a method to solve problems master to agents' communication and local calls.
The proposed method is much sharper than the $mathcalO(sqrtL_q/mu)$ method.
arXiv Detail & Related papers (2022-05-30T14:28:02Z) - Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
The optimistic method has seen increasing popularity for solving convex-concave saddle point problems.
We develop a backtracking line search scheme to select the step sizes without knowledge of coefficients.
arXiv Detail & Related papers (2022-02-19T20:31:05Z) - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
We study a linear convex-concave saddle-point problem $min_xmax_y f(x) ytopmathbfA x - g(y)
arXiv Detail & Related papers (2021-12-30T20:31:46Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
We consider the problem of finding a saddle point for the convex-concave objective $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, where $f$ is a convex function with locally Lipschitz gradient and $g$ is convex and possibly non-smooth.
We propose an adaptive version of the Condat-Vu algorithm, which alternates between primal gradient steps and dual steps.
arXiv Detail & Related papers (2021-10-28T14:19:30Z) - Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
We derive nonasymptotic complexity of exact and inexact PPA to minimize convex functions under $gamma-$Holderian growth.
Our numerical tests show improvements over existing restarting versions of the Subgradient Method.
arXiv Detail & Related papers (2021-08-10T07:15:07Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions.
In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
arXiv Detail & Related papers (2020-02-10T23:23:04Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.