Subgradient Gliding Method for Nonsmooth Convex Optimization
Zhihan Zhu, Yanhao Zhang, * · 2026
Read Subgradient Gliding Method for Nonsmooth Convex Optimization by Zhihan Zhu, Yanhao Zhang, * (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-14139.txt.
Introduction
Zhihan Zhu and two co-authors diagnose a 2026 arXiv flaw in the classic projected subgradient method. For nonsmooth convex optimization, the method can fail after a single step when no valid subgradient exists at a boundary point. Under standard step sizes, that failure can occur with probability near one, even on simple problems.
The fix, called the subgradient gliding method, stays well defined without boundary subgradients and avoids early termination. It contains the classic method as a special case and widens the allowed step-size designs. The authors prove optimal ergodic rates: order 1 over root t for convex problems, and order 1 over t for strongly convex ones. Extensions to stochastic settings need only mild control on subgradient growth, not global Lipschitz continuity.
Catalog record
| CREATOR | Zhihan Zhu, Yanhao Zhang, * |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-14139
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Subgradient Gliding Method for Nonsmooth Convex Optimization Zhihan Zhu, Yanhao Zhang, * Abstract We identify and analyze a fundamental limitation of the classical projected subgradient method in nonsmooth convex optimization: the inevitable failure caused by the absence of valid subgradients at boundary points. We show that, under standard step sizes for both convex and strongly convex objectives, the method can fail after a single iteration with probability arbitrarily close to one, even on simple problem instances. To overcome this limitation, we propose a novel alternative termed the subgradient gliding method , which remains well defined without boundary subgradients and avoids premature termination. Beyond resolving this foundational issue, the proposed framework encompasses the classical projected subgradient method as a special case and substantially enlarges its admissible step-size design space, providing greater flexibility for algorithmic design. We establish optimal ergodic convergence rates, 𝒪 ( 1 / t ) \mathcal{O}(1/\sqrt{t}) for convex problems and 𝒪 ( 1 / t ) \mathcal{O}(1/t) for strongly convex problems, and further extend the framework to stochastic settings. Notably, our analysis does not rely on global Lipschitz continuity of the objective function, requiring only mild control on subgradient growth. Numerical experiments demonstrate that, in scenarios where the classical projected subgradient method fails completely, the proposed method converges reliably with a 100 % 100\% success rate and achieves orders-of-magnitude improvements in accuracy and convergence speed. These results substantially expand the scope of subgradient-based optimization methods to non-Lipschitz nonsmooth convex problems. 2023 [1]Yong Xia 1]LMIB of the Ministry of Education, School of Mathematical Sciences, Beihang University, Beijing 100191, People’s Republic of China Mathematics Subject Classification]90C25, 90C30 keywords Nonsmooth convex optimization, Subgradient gliding method, Step size, Projected subgradient method, Stochastic subgradient pacs [ 1 Introduction To address the nonsmooth convex optimization problem x^{*}\in{\rm argmin}_{x\in\mathcal{X}}f(x), where \mathcal{X}\subset{\mathbb{R}}^{n} is a compact convex set contained in the Euclidean ball B(x^{*},R) , and f is a (possibly nonsmooth) convex function, the classical projected subgradient method (PSG) proceeds iteratively as follows: \left\{\begin{aligned} y_{s+1}&=x_{s}-\alpha_{s}g_{s},~\text{where }g_{s}\in\partial f(x_{s}),\\ x_{s+1}&={\rm argmin}_{x\in\mathcal{X}}\|x-y_{s+1}\|,\end{aligned}\right. where \|\cdot\| denotes the Euclidean norm throughout this paper. 1.1 Recent Advances on Projected Subgradient Method When the objective function f is Lipschitz continuous with a known Lipschitz constant L (i.e., \|g\|\leq L for any g\in\partial f(x)\neq\emptyset and x\in\mathcal{X} ), employing a constant step size of \alpha_{s}\equiv\frac{R}{L\sqrt{t}},~s=1,\cdots,t, (1) enables PSG to achieve the optimal ergodic convergence rate, which is given by f\left(\frac{\sum_{s=1}^{t}x_{s}}{t}\right)-f(x^{*})\leq\frac{RL}{\sqrt{t}}, see, for example, nesterov2004lectures ; nesterov2018lectures ; bubeck2015convex . While constant step sizes require predefining the number of iterations, recent studies have demonstrated that appropriately designed time-varying step sizes, as presented in nesterov2004lectures ; nesterov2018lectures ; bubeck2015convex , given by \alpha_{s}=\frac{R}{L\sqrt{s}},~s=1,\cdots,t, (2) has been proven to ensure the optimal convergence rate of PSG as well Zhu : f\left(\frac{\sum_{s=1}^{t}x_{s}}{t}\right)-f(x^{*})\leq\frac{3RL}{2\sqrt{t}}. (3) In nesterov2004lectures ; nesterov2018lectures ; beck2017first , further analysis is provided for a more practical subgradient-normalized time-varying step-size scheme: \alpha_{s}=\frac{R}{\|g_{s}\|\sqrt{s}},~s=1,\cdots,t, (4) which notably eliminates the need for prior knowledge of the Lipschitz constant. Nevertheless, convergence guarantees for PSG still rely on the Lipschitz continuity assumption of f . Furthermore, the resulting convergence rate remains sub-optimal, characterized by f\left(\frac{\sum_{s=1}^{t}\alpha_{s}x_{s}}{\sum_{s=1}^{t}\alpha_{s}}\right)-f(x^{*})\leq\frac{2RL+RL\log t}{4(\sqrt{t+1}-1)}. (5) Recently, Xia introduced a novel family of time-varying step-sizes \alpha_{s}=\frac{R}{G_{s}s^{\frac{a}{2}}},~s=1,\cdots,t, (6) for any fixed a\in[0,1] where G_{s}=\max\{G_{s-1},\|g_{s}\|s^{\frac{1-a}{2}}\}~(G_{0}=-\infty), (7) which operate without knowledge of the Lipschitz constant, while effectively preserving the weak ergodic convergence properties established in Zhu . This family of step-sizes attains the optimal ergodic convergence rate as follows: f\left(\frac{\sum_{s=1}^{t}x_{s}}{t}\right)-f(x^{*})\leq\frac{3R}{2\sqrt{t}}\cdot\max_{s=1,\cdots,t}\|g_{s}\|, (8) which provides a convergence analysis that does not rely on the Lipschitz assumption. The aforementioned work addresses the case where the objective function is convex. When the objective function f is \mu -strongly convex, incorporating strong convexity information into the step size design \alpha_{s}=\frac{2}{\mu(s+1)},~s=1,\cdots,t, (9) can achieve the optimal ergodic convergence rate of \mathcal{O}(1/t) , given by Lacoste-Julien f\left(\sum_{s=1}^{t}\frac{2s}{t(t+1)}x_{s}\right)-f(x^{*})\leq\frac{2L^{2}}{\mu(t+1)}. (10) 1.2 Fundamental Assumption and Limitation in PSG The following theorem concerning the existence of subgradients was originally established in ( Rockafellar , Theorem 23.4) and subsequently appeared in ( bubeck2015convex , Proposition 1.1) and ( nesterov2018lectures , Theorem 3.1.15) . Here, we always assume that the convex set \mathcal{X} has a nonempty interior (i.e., \text{int}(\mathcal{X})\neq\emptyset ). In fact, if the affine hull of \mathcal{X} has a lower dimension than the ambient space, the theorem remains valid when replacing the interior with the relative interior. Theorem 1.1 . If f is convex then for any x\in\text{int}(\mathcal{X}) , \partial f(x)\neq\emptyset . According to Theorem 1.1 , while a convex function on a convex set is assured to have nonempty subgradients at interior points, such existence cannot be guaranteed at boundary points. Three illustrative examples are provided below. Example 1 . The function f(x)=-\sqrt{r-k_{1}x(1)^{2}-k_{2}x(2)^{2}} , where r,k_{1},k_{2}>0 , is a convex function on the ellipsoid k_{1}x(1)^{2}+k_{2}x(2)^{2}\leq r , which lacks subgradients at boundary k_{1}x(1)^{2}+k_{2}x(2)^{2}=r . Example 2 . The function inspired by Renegar f(x)=\begin{cases}0&\text{if }(x(1),x(2))=(0,0),\\ \frac{x(1)^{2}+x(2)^{2}}{x(1)}&\text{if }x(1)>0,\\ \infty&\text{otherwise}.\end{cases} is convex over the rectangular domain 0\leq x(1)\leq 1,-1\leq x(2)\leq 1 , but it lacks subgradients along the boundary segment x(1)=0,-1\leq x(2)\leq 1,x(2)\neq 0 . Example 3 . The negative entropy function f(x)=\sum_{i=1}^{n}x(i)\log x(i) on the hypercube \mathcal{X}=\{x\in{\mathbb{R}}_{+}^{n}:0\leq x(i)\leq B,~B>0\} is (strongly) convex (with the convention that 0\log 0=0 ), but it does not admit subgradients at boundary points (i.e., x(i)=0 for some i ). Since PSG readily projects iterates onto the boundary, the algorithm cannot proceed when subgradients are absent at these boundary points. Consequently, the existing PSG methods implicitly assume the existence of subgradients at boundary points to function properly as in ( zamani2025exact , Assumption 1.1) and alber1998projected , or ensure subgradient existence by imposing additional assumptions on the feasible set \mathcal{X} ( beck2017first , Assumption 8.7) . However, these assumptions are often violated for many convex functions over convex sets, even for the simple examples mentioned above. This limitation restricts PSG’s applicability to general nonsmooth convex optimization. In Section 2, we present a more detailed analysis demonstrating that these simple examples may even induce worst-case behavior of the classical PSG. 1.3 Our Contributions: Subgradient Gliding Method This paper’s main contributions can be summarized along three closely related aspects. Limitations of the classical projected subgradient method: We first identify and analyze fundamental failure modes of the classical PSG that arise when valid subgradients do not exist on the boundary of the feasible set. In Section 2, we show that under standard step sizes for both convex and strongly convex objectives, PSG can fails after a single iteration with probability arbitrarily close to one, even on simple problem instances. These theoretical findings are further corroborated by numerical experiments in Section 6. Together, these results reveal intrinsic limitations of classical PSG that are not captured by existing convergence analyses. A novel alternative with theoretical guarantees: To overcome the above limitations, existing literature typically imposes additional assumptions to guarantee the existence of subgradients, which, however, further restrict the applicability of PSG. In contrast, we propose the subgradient gliding method (SGM), which guarantees all iterates remain strictly interior, thereby well defined even in the absence of boundary subgradients without requiring any additional assumptions. We establish optimal ergodic convergence rates of \mathcal{O}(1/\sqrt{t}) for convex problems and \mathcal{O}(1/t) for strongly convex problems (Sections 3 and 4). We further extend the framework to stochastic settings and develop corresponding convergence guarantees (Section 5). Importantly,