betaFeedback

WorksMathematics

Distance-Certified Polyak-type Stepsizes for Subgradient Methods under Hölder Growth

Abstract

In this paper, we consider nonsmooth convex optimization under a H{ö}lder growth condition, with quadratic growth and weak sharp minima as two important special cases. Existing subgradient methods often employ predetermined decaying stepsize schedules, whereas the classical Polyak stepsize selects its stepsize adaptively but requires knowledge of the optimal value. We introduce a new distance-certified subgradient method (\DCSG) that follows a one-step optimization principle analogous to that underlying the Polyak stepsize, without requiring the optimal value. Specifically, \DCSG{} maintains a valid upper certificate for the current squared distance to the solution set. The method selects each stepsize by minimizing the worst-case upper bound on the next squared distance over all distances consistent with this certificate. We show that the resulting minimax problem admits a closed-form solution, yielding an explicit adaptive stepsize update. Under uniformly bounded subgradients, \DCSG{} improves upon the convergence rate of the classical subgradient method and matches the state-of-the-art rates for Lipschitz convex optimization under H{ö}lder growth. In particular, it achieves linear convergence under sharp growth. Numerical experiments illustrate the performance of \DCSG.

Introduction

We consider the convex optimization problem

min⁡x∈Cf(x),(1)\min_{x\in C} f(x), \tag*{(1)}

where f:Rn→R∪{+∞}f:\mathbb{R}^n \to\mathbb{R} \cup\{+\infty\} is a closed convex function and C⊆dom⁡fC \subseteq\operatorname{dom} f is a closed and convex set. We do not assume that ff is smooth or strongly convex. Let X⋆:=arg⁡min⁡x∈Cf(x)X^\star:= \arg\min_{x\in C} f(x) denote the solution set and f⋆:=min⁡x∈Cf(x)f^\star:= \min_{x\in C} f(x) the optimal value. Throughout this paper, we assume that X⋆X^\star is nonempty and f⋆f^\star is finite. Problem (1) arises in many applications such as machine learning, compressed sensing, image processing, computer vision, and many others [1, 2, 3].

When ff is smooth, projected gradient descent and its accelerated variants [1] have been well-developed to solve (1). For nonsmooth objectives, the subgradient method is among the simplest first-order algorithms. Its development dates back to foundational work in the 1960s [4, 5], and it remains widely used because of its simple implementation and low per-iteration cost. When ff is globally Lipschitz-continuous, the classical subgradient method achieves a convergence rate of f(x^k)−f⋆≤O(1/k)f(\hat{x}_k) - f^\star\leq O(1/\sqrt{k}) after kk subgradient evaluations for a suitably averaged point x^k\hat{x}_k [1]. This rate is known to be the worst-case optimal for general nonsmooth convex optimization among the first-order oracle model [1, 6]. Faster rates are nevertheless possible for certain classes of ff with additional structural information [5, 7, 8, 9, 10, 11, 12, 13, 14].

In this paper, we consider Lipschitz convex optimization under the Hölder growth condition

f(x)−f⋆≥cdist⁡(x,X⋆)p,∀x∈C,(2)f(x) - f^\star\ge c\operatorname{dist}(x, X^\star)^p,\quad\forall x \in C, \tag*{(2)}

for some choice of c>0c > 0 and p≥1p \ge1. This is equivalent to dist⁡(x,X⋆)≤c−1/p(f(x)−f⋆)1/p, ∀x∈C\operatorname{dist}(x, X^\star) \le c^{-1/p}(f(x) - f^\star)^{1/p},\ \forall x \in C. This equivalent form bounds the distance to the solution set in terms of the objective gap and is commonly referred to as a Hölder error bound. The error-bound exponent is often denoted by θ∈(0,1]\theta\in(0, 1]; under this parameterization, we have p=1/θp = 1/\theta as used in [7, 10]. This Hölder growth property is also called the Łojasiewicz inequality [15] and is closely related to the Kurdyka–Łojasiewicz (KL) inequality [16]. Hölder error bounds have been widely studied in optimization, sensitivity analysis, and convergence-rate analysis [7, 12, 15, 16, 17, 18, 19].

The Hölder growth condition holds for many problems arising in applications. In particular, every proper closed semialgebraic convex function satisfies a local error bound of the form (2) for suitable constants c>0c > 0 and p≥1p \ge1 [16]. This additional growth structure enables many first-order algorithms to achieve faster convergence rates [5, 7, 8, 9, 10, 11, 12, 13]. Two particularly important cases are p=1p = 1 and p=2p = 2. The case p=2p = 2 is commonly known as the quadratic growth (QG) condition [12, 17], and the case p=1p = 1 corresponds to the sharp growth condition, also known as weak sharp minima [7, 18]. The QG condition has been used to establish linear convergence of proximal point and related methods [12]. Moreover, for convex functions, QG is equivalent to several other commonly used regularity conditions, including the restricted secant inequality, the subdifferential error bound, and the Polyak–Łojasiewicz condition [12, Theorem 3.1]`.

Under the Hölder growth condition (2), several techniques have been developed to accelerate the convergence of subgradient methods across a range of settings. Representative approaches include predetermined decaying stepsize schedules [7, 8, 10], restarting schemes [9, 20] and Polyak-type stepsizes [5, 21, 22, 23]. These approaches substantially improve convergence rates of subgradient methods by carefully designing the stepsizes. Nevertheless, the predetermined schedules used by restarting and decaying schemes [7, 8, 9, 10, 20] present several practical and conceptual limitations. Their stepsizes are typically tuned using global problem information, such as a uniform subgradient bound and growth parameters. To achieve the fast rates, it may require carefully chosen stage lengths and different decaying coefficients. This makes the resulting schedules relatively intricate and obscures the connection between each stepsize and the corresponding one-step progress of the subgradient method. Furthermore, these schemes commonly use a global Lipschitz bound for stepsize tuning. This choice may lead to conservative stepsize choices, and consequently, these predetermined schemes [7, 9, 10] do not capture the additional potential acceleration when the subgradients diminish near the solution set.

The classical Polyak stepsize [5] follows a different principle and does not rely on a predetermined schedule. At each iteration, it minimizes a one-step upper bound on the squared distance to the solution set using the current objective gap and subgradient norm. This allows the stepsize to adapt naturally to the local problem geometry and may permit more aggressive steps than standard constant or diminishing stepsizes [22, 23]. Recently, Wang [10] showed that the classical Polyak stepsize attains the minimax-optimal convergence rate for reducing the distance to the solution set over globally Lipschitz convex functions satisfying (2). Implementing the Polyak stepsize, however, requires exact knowledge of the optimal value f⋆f^\star, which may be unavailable. Note that avoiding exact knowledge of the optimal value requires special treatment; see, for example, dynamic target-level schemes [24, 25, 26] and restarted procedures that successively refine a lower bound on f⋆f^\star [27].

In this paper, we introduce a new distance-certified subgradient method (DC-SG) for Lipschitz convex optimization under Hölder growth. Instead of prescribing a decaying stepsize schedule in advance, DC-SG follows a one-step optimization principle analogous to that underlying the classical Polyak stepsize. Specifically, our key idea is to maintain a valid upper certificate for the current squared distance to the solution set. We select the stepsize by minimizing the worst-case upper bound on the next squared distance over all distances consistent with the current certificate. This construction uses the Hölder growth parameters, but avoids the requirement of the optimal value f⋆f^\star. We show that the resulting certificates remain valid and nonincreasing (Proposition 1) and that the minimax principle admits an explicit adaptive solution determined by the current certificate, the observed subgradient norm, and the Hölder growth parameters (Propositions 2 and 3).

Similar to the Polyak stepsize, DC-SG adapts its stepsize at every iteration and requires no predetermined schedule. Also, the implementation of DC-SG requires no global Lipschitz constant, which enters only the worst-case convergence analysis. Under uniformly bounded subgradients, we prove that DC-SG provides the last-iterate guarantee

dist⁡(xk,X⋆)≤O(k−12(p−1))\operatorname{dist}(x_k, X^\star) \le O\left(k^{-\frac{1}{2(p-1)}}\right)

when p>1p>1 (Theorem 1) and converges linearly when p=1p=1 (Theorem 2). These rates are faster than the classical subgradient guarantee and remove the additional logarithmic factor appearing in the restarted subgradient method [9]. Also, they match the state-of-the-art rates for Lipschitz convex optimization under Hölder growth [7, 10]. Finally, DC-SG automatically achieves faster rates when the norm of observed subgradients diminishes near the solution set (Corollary 2). This additional acceleration is not captured by the predetermined decaying stepsize schedules [7, 10]. We present further comparisons with the state-of-the-art in Section 4.3.

The remainder of this paper is organized as follows. Section 2 introduces the necessary notation and preliminary results. Section 3 develops the distance-certified subgradient method (DC-SG). Section 4 establishes its convergence rates and compares them with state-of-the-art guarantees. Section 5 illustrates the numerical performance of DC-SG. We conclude the paper in Section 6.

Preliminaries

Recall that the subdifferential of ff at xx is defined by

∂f(x)={g∈Rn∣f(y)≥f(x)+⟨g,y−x⟩, ∀y∈Rn}.\partial f(x) = \{g \in\mathbb{R}^n \mid f(y) \ge f(x) + \langle g, y-x\rangle,\ \forall y \in\mathbb{R}^n\}.

Given an initial point x0∈Cx_0 \in C, the projected subgradient method generates iterates according to

xk+1=PC(xk−αkgk),k≥0,x_{k+1}=P_C(x_k-\alpha_k g_k), \qquad k \ge0,

where gk∈∂f(xk)g_k \in\partial f(x_k), αk>0\alpha_k>0 is the stepsize, and PCP_C denotes the Euclidean projection onto CC. The method is listed in Algorithm 1. Different stepsize choices lead to different convergence guarantees [5, 7, 8, 9, 10, 11]. Among them, the Polyak stepsize [5] is particularly relevant to our development.

We focus on functions satisfying the following Hölder growth condition.

Definition 1 (Hölder growth). A function ff satisfies (p,c)(p,c)-Hölder growth on CC if there exist c>0c>0 and p≥1p\ge1 such that

f(x)−f⋆≥cdist⁡(x,X⋆)p,∀x∈C,(3)f(x)-f^\star\ge c\operatorname{dist}(x,X^\star)^p, \qquad\forall x \in C, \tag*{(3)}

where dist⁡(x,X⋆):=inf⁡y∈X⋆∥x−y∥\operatorname{dist}(x,X^\star):=\inf_{y\in X^\star}\|x-y\| denotes the distance from xx to the solution set.

A distance-certified subgradient method (DC-SG)

Algorithm 1 Projected subgradient method

Require: An initial point x0∈Cx_0 \in C, stepsizes αk>0\alpha_k > 0, and an iteration limit NN.

  1. for k=0,1,…,N−1k = 0,1,\ldots,N-1 do

  2. Choose gk∈∂f(xk)g_k \in\partial f(x_k).

  3. Set xk+1=PC(xk−αkgk)x_{k+1} = P_C(x_k-\alpha_k g_k).

  4. end for

We refer to (3) as the Hölder growth condition. This condition is also known as a Hölderian error bound and is closely related to the Kurdyka-Łojasiewicz (KL) inequality [16].

It is well-known that the projected subgradient method may not decrease the objective value at every iteration. Still, its progress can be measured by the distance of the iterates to the solution set. For each iteration of Algorithm 1, we define

ek:=dist⁡(xk,X⋆)2,hk:=∥gk∥,(4)e_k := \operatorname{dist}(x_k,X^\star)^2,\qquad h_k := \lVert g_k\rVert, \tag*{(4)}

which denote the squared-distance error and the norm of the selected (or observed) subgradient, respectively. The following standard lemma provides the fundamental one-step improvement, which underlies most convergence analyses of subgradient methods [1, 5, 7, 8, 9, 10, 11]. We include a brief proof to highlight its simplicity and also for completeness.

Lemma 1 (Squared-distance recursion). Let ff be a closed convex function. For every iterate xkx_k generated by Algorithm 1, we have

ek+1≤ek−2αk(f(xk)−f⋆)+αk2hk2.(5)e_{k+1} \le e_k - 2\alpha_k\bigl(f(x_k)-f^\star\bigr) + \alpha_k^2 h_k^2. \tag*{(5)}

If, in addition, ff satisfies the (p,c)(p,c)-Hölder growth condition (3), then

ek+1≤ek−2αkcekp/2+αk2hk2.(6)e_{k+1} \le e_k - 2\alpha_k c e_k^{p/2} + \alpha_k^2 h_k^2. \tag*{(6)}

Proof. Fix any x⋆∈X⋆x^\star\in X^\star. Since x⋆∈Cx^\star\in C, we have PC(x⋆)=x⋆P_C(x^\star)=x^\star. By the non-expansiveness of the projection operator, we have

∥xk+1−x⋆∥2=∥PC(xk−αkgk)−PC(x⋆)∥2≤∥xk−αkgk−x⋆∥2=∥xk−x⋆∥2−2αk⟨gk,xk−x⋆⟩+αk2∥gk∥2.\begin{aligned} \lVert x_{k+1}-x^\star\rVert^2 &= \lVert P_C(x_k-\alpha_k g_k)-P_C(x^\star)\rVert^2 \\ &\le\lVert x_k-\alpha_k g_k-x^\star\rVert^2 \\ &= \lVert x_k-x^\star\rVert^2-2\alpha_k\langle g_k,x_k-x^\star\rangle+\alpha_k^2\lVert g_k\rVert^2. \end{aligned}

Since gk∈∂f(xk)g_k \in\partial f(x_k), the subgradient inequality gives f(xk)−f⋆≤⟨gk,xk−x⋆⟩f(x_k)-f^\star\le\langle g_k,x_k-x^\star\rangle. Recalling the definition that hk=∥gk∥h_k=\lVert g_k\rVert in (4), we obtain

∥xk+1−x⋆∥2≤∥xk−x⋆∥2−2αk(f(xk)−f⋆)+αk2hk2.\lVert x_{k+1}-x^\star\rVert^2 \le\lVert x_k-x^\star\rVert^2-2\alpha_k(f(x_k)-f^\star)+\alpha_k^2h_k^2.

Taking the infimum over x⋆∈X⋆x^\star\in X^\star on both sides gives (5). If ff satisfies the (p,c)(p,c)-Hölderian condition (3), then f(xk)−f⋆≥cdist⁡(xk,X⋆)p=cekp/2f(x_k)-f^\star\ge c\operatorname{dist}(x_k,X^\star)^p = ce_k^{p/2}. Substituting this bound into (5) gives (6). □

From (5) and (6), the negative term scales linearly with αk\alpha_k, while the positive term scales quadratically. Thus, whenever xkx_k is nonoptimal, a sufficiently small stepsize guarantees ek+1<eke_{k+1}<e_k. Building on this insight, constant stepsizes and predetermined decaying stepsizes can yield complexity guarantees for finding an iterate xkx_k satisfying ek≤ϵe_k\le\epsilon for functions with Hölder growth [7, 10].

Remark 1. If ff is globally LL-Lipschitz continuous, then hk≤Lh_k\le L for every iteration. Consequently, (6) reduces to ek+1≤ek−2αkcekp/2+αk2L2e_{k+1}\le e_k-2\alpha_kce_k^{p/2}+\alpha_k^2L^2, which has been widely used in existing stepsize designs [7, 10]. However, this worst-case bound does not exploit the subgradient norm hkh_k observed at each iteration. As a result, the algorithms in [7, 10] may fail to adapt to smaller subgradients and may not achieve faster convergences. We provide further discussion in Remark 2 later.

A distance-certified subgradient method (DC-SG)

In this section, we develop a new distance-certified subgradient method for convex functions satisfying Hölder growth. We first introduce the underlying stepsize design, then derive explicit stepsize updates, and finally provide technical proofs.

Distance-certified stepsize design

The stepsize design plays a fundamental role in the convergence of the projected subgradient method in Algorithm 1. Indeed, once the oracle selects a subgradient gkg_k, the stepsize αk\alpha_k is the only remaining design choice and fully determines the resulting update. Common choices include constant stepsizes αk=α\alpha_k = \alpha [1], diminishing stepsizes satisfying ∑k=0∞αk=∞\sum_{k=0}^{\infty} \alpha_k = \infty, ∑k=0∞αk2<∞\sum_{k=0}^{\infty} \alpha_k^2 < \infty, such as αk=a/(b+k)\alpha_k = a/(b+k) with a,b>0a,b > 0 [1, 2], and geometrically decaying stepsizes [7, 8, 10].

If the optimal value f⋆f^\star is known, minimizing the right-hand side of the squared-distance recursion (5) with respect to αk\alpha_k yields the celebrated Polyak stepsize [5]

αPolyak,k=f(xk)−f⋆hk2,k=0,1,2,…(7)\alpha_{\mathrm{Polyak},k} = \frac{f(x_k)-f^\star}{h_k^2}, \qquad k=0,1,2,\ldots \tag*{(7)}

This stepsize can be interpreted as a greedy choice that minimizes the one-step upper bound on the squared-distance error. By incorporating both the current optimality gap and the observed subgradient norm, it naturally adapts to the local optimization landscape and can be more aggressive than standard constant or diminishing stepsizes [22, 23]. Following the same idea as the Polyak stepsize, suppose that ff satisfies the (p,c)(p,c)-Hölder growth condition and that the exact squared-distance error eke_k is available. Minimizing the right-hand side of (6) with respect to αk\alpha_k yields

αdist,k=cekp/2hk2,k=0,1,2,…(8)\alpha_{\mathrm{dist},k} = \frac{c e_k^{p/2}}{h_k^2}, \qquad k=0,1,2,\ldots \tag*{(8)}

We refer to this choice as an exact distance-based Polyak-type stepsize. A related idea was recently explored in [10].

In general, the exact squared-distance error eke_k is unavailable, as its computation typically requires knowledge of the solution set X⋆X^\star. Our key idea is to replace eke_k with a certified upper bound EkE_k satisfying ek≤Eke_k \le E_k and choose the stepsize that minimizes the worst-case one-step upper bound in (6) over all ek∈[0,Ek]e_k \in[0,E_k]. Specifically, for E≥0E \ge0, define

Φk(α,E):=α2hk2+max⁡0≤e≤E{e−2αcep/2},(9)\Phi_k(\alpha,E) := \alpha^2 h_k^2 + \max_{0 \le e \le E} \left\{e - 2\alpha c e^{p/2}\right\}, \tag*{(9)}

which represents the worst-case one-step upper bound in (6) over all ek∈[0,E]e_k \in[0,E]. We then select

αcert,k=arg⁡min⁡α≥0 Φk(α,Ek),k=0,1,2,…,(10)\alpha_{\mathrm{cert},k} = \underset{\alpha\ge0}{\arg\min}\ \Phi_k(\alpha,E_k), \qquad k=0,1,2,\ldots, \tag*{(10)}

which we refer to as a distance-certified Polyak-type stepsize. By construction, the value

Uk+1:=Φk(αcert,k,Ek)(11)U_{k+1} := \Phi_k(\alpha_{\mathrm{cert},k},E_k) \tag*{(11)}

provides an upper bound on the squared-distance error of the next iterate xk+1=PC(xk−αcert,kgk)x_{k+1}=P_C(x_k-\alpha_{\mathrm{cert},k}g_k), namely, ek+1≤Uk+1e_{k+1} \le U_{k+1}. We may thus choose the next certified upper bound Ek+1=Uk+1E_{k+1}=U_{k+1} and repeat (10) and (11). Starting from an initial bound U0≥e0U_0 \ge e_0, this generates a sequence of certified bounds satisfying ek≤Eke_k \le E_k for all k≥0k \ge0 and forms the basis of our distance-certified subgradient method.

In addition, the observed subgradient gkg_k can provide a further upper bound on the squared-distance error eke_k. This observation is formalized in the following lemma.

Explicit distance-certified stepsize updates

Algorithm 2 Distance-certified subgradient method (DC-SG)

Require: An initial point x0∈Cx_0 \in C, an initial bound U0≥e0U_0 \ge e_0, parameters c>0c > 0, p≥1p \ge1, and an iteration limit NN.

  1. for k=0,1,…,N−1k = 0,1,\ldots,N-1 do

  2. Choose gk∈∂f(xk)g_k \in\partial f(x_k) and set hk=∥gk∥h_k = \lVert g_k\rVert;

  3. Compute EkE_k according to (11);

  4. Compute αcert,k\alpha_{\mathrm{cert},k} according to (8);

  5. Set Uk+1U_{k+1} according to (9);

  6. Set xk+1=PC(xk−αcert,kgk)x_{k+1} = P_C(x_k - \alpha_{\mathrm{cert},k}g_k);

  7. end for

Lemma 2 (Subgradient-based distance certificate). Suppose that ff is convex and satisfies the (p,c)(p,c)-Hölder growth condition (3). For any x∈Cx \in C and g∈∂f(x)g \in\partial f(x), we have cdist⁡(x,X⋆)p≤∥g∥dist⁡(x,X⋆)c\operatorname{dist}(x,X^\star)^p \le\lVert g\rVert\operatorname{dist}(x,X^\star). Consequently, if p>1p > 1, then

dist⁡(x,X⋆)2≤(∥g∥c)2p−1.(12)\operatorname{dist}(x,X^\star)^2 \le\left(\frac{\lVert g\rVert}{c}\right)^{\frac{2}{p-1}}. \tag*{(12)}

If p=1p = 1 and x∉X⋆x \notin X^\star, then ∥g∥≥c\lVert g\rVert\ge c.

Proof. Let x⋆=PX⋆(x)x^\star= P_{X^\star}(x), so that ∥x−x⋆∥=dist⁡(x,X⋆)\lVert x-x^\star\rVert= \operatorname{dist}(x,X^\star). By the subgradient inequality and the Cauchy–Schwarz inequality, we have f(x)−f⋆≤⟨g,x−x⋆⟩≤∥g∥dist⁡(x,X⋆)f(x)-f^\star\le\langle g,x-x^\star\rangle\le\lVert g\rVert\operatorname{dist}(x,X^\star). Combining this inequality with (3) proves the first statement. If x∈X⋆x \in X^\star, (10) holds trivially. Otherwise, we have cdist⁡(x,X⋆)p−1≤∥g∥c\operatorname{dist}(x,X^\star)^{p-1} \le\lVert g\rVert. For p>1p > 1, rearranging and squaring this inequality establishes (10). For p=1p = 1, it reduces to ∥g∥≥c\lVert g\rVert\ge c.

After observing the selected subgradient gkg_k, Lemma 2 allows us to refine the upper bound UkU_k from (9) by setting

Ek:={min⁡{Uk,(hk/c)2p−1}if p>1,Ukif p=1.(13)E_k := \begin{cases} \min\left\{U_k,\left(h_k/c\right)^{\frac{2}{p-1}}\right\} & \text{if }p>1,\\ U_k & \text{if }p=1. \end{cases} \tag*{(13)}

By construction, we always have ek≤Ek≤Uke_k \le E_k \le U_k. Combining the certificate update (11) with the stepsize design (8) and the bound propagation (9), we present the distance-certified subgradient method (DC-SG), listed in Algorithm 2. We have a simple observation for this algorithm.

Proposition 1 (Monotonicity of distance certificates). Suppose that U0≥e0U_0 \ge e_0. Then the iterates generated by Algorithm 2 satisfy

ek+1≤Ek+1≤Uk+1≤Ek≤Uk,∀k≥0.e_{k+1} \le E_{k+1} \le U_{k+1} \le E_k \le U_k,\qquad\forall k \ge0.

In particular, both {Ek}\{E_k\} and {Uk}\{U_k\} are nonincreasing.

Proof. By the definition of αcert,k\alpha_{\mathrm{cert},k} in (8), we have

Uk+1=min⁡α≥0Φk(α,Ek)≤Φk(0,Ek)=Ek.U_{k+1} = \min_{\alpha\ge0}\Phi_k(\alpha,E_k) \le\Phi_k(0,E_k) = E_k.

The remaining inequalities follow directly from Lemmas 1 and 2 and the certificate update (11).

In Section 4, we show that DC-SG achieves state-of-the-art convergence rates for solving (1) with convex functions under the Hölder growth condition (3), while offering additional benefits.

Explicit distance-certified stepsize updates

The distance-certified stepsize αcert,k\alpha_{\mathrm{cert},k} is defined by minimizing the worst-case upper bound in (10). Fortunately, the scalar structure of this minimax problem allows an explicit characterization of its solution. We first observe that the stepsize optimization problem (9) is strongly convex and thus admits a unique minimizer.

Lemma 3 (Unique distance-certified stepsize). Given any Ek>0E_k > 0, define the inner worst-case function

Mk(α):=max⁡0≤e≤Ek{e−2αcep/2}(14)M_k(\alpha) := \max_{0\le e\le E_k}\left\{e - 2\alpha c e^{p/2}\right\} \tag*{(14)}

where α≥0\alpha\ge0, p≥1p \ge1. Then MkM_k is convex and nonnegative on [0,∞)[0,\infty). Consequently, for any hk>0h_k > 0, α↦Φk(α,Ek)=α2hk2+Mk(α)\alpha\mapsto\Phi_k(\alpha, E_k) = \alpha^2 h_k^2 + M_k(\alpha) is strongly convex in α\alpha and admits a unique minimizer on [0,∞)[0,\infty).

Proof. For each fixed e∈[0,Ek]e \in[0,E_k], the function α↦e−2αcep/2\alpha\mapsto e - 2\alpha c e^{p/2} is affine. Therefore, MkM_k is convex as the pointwise maximum of affine functions. Moreover, since e=0e = 0 is feasible in the inner maximization, we have Mk(α)≥0M_k(\alpha) \ge0 for all α≥0\alpha\ge0.

If hk>0h_k > 0, then α↦α2hk2\alpha\mapsto\alpha^2 h_k^2 is strongly convex. Hence, its sum with the convex function MkM_k is also strongly convex. Furthermore, Φk(α,Ek)≥α2hk2→∞\Phi_k(\alpha, E_k) \ge\alpha^2 h_k^2 \to\infty as α→∞\alpha\to\infty. Therefore, Φk(⋅,Ek)\Phi_k(\cdot, E_k) attains its minimum on [0,∞)[0,\infty), and strong convexity guarantees that the minimizer is unique.

We will show in § 4.5 that the worst-case function Φk(α,Ek)\Phi_k(\alpha, E_k) is further piecewise smooth in α\alpha. Figure 1 illustrates its typical shapes for 1≤p≤21 \le p \le2 and p=4p = 4 that are both strongly convex.

Typical worst-case upper bound functions

Figure 1. Typical worst-case upper bound functions Φk(α,Ek)=hk2α2+max⁡0≤e≤Ek{e−2αcep/2}\Phi_k(\alpha, E_k) = h_k^2\alpha^2 + \max_{0\le e\le E_k}\{e - 2\alpha c e^{p/2}\} with c=Ek=hk=1c = E_k = h_k = 1 for 1≤p≤21 \le p \le2 (Left) and p=4p = 4 (Right). Solid curves show the valid smooth branches; dashed curves extend the same formulas beyond their valid intervals. Both functions are strongly convex.

Before deriving the analytical solution, we provide some intuition for the minimax problem (10). When hkh_k is sufficiently large, the optimal stepsize will be small enough that the inner maximization attains its worst-case value at e=Eke = E_k. In this case, we have Φk(α,Ek)=α2hk2+Ek−2αcEkp/2\Phi_k(\alpha, E_k) = \alpha^2 h_k^2 + E_k - 2\alpha c E_k^{p/2}, which is quadratic in α\alpha. Minimizing this expression gives

αP=cEkp/2hk2,(15)\alpha_{\mathrm{P}} = \frac{cE_k^{p/2}}{h_k^2}, \tag*{(15)}

which has the same form as the exact distance-based Polyak-type stepsize (8), with the unknown squared-distance error eke_k replaced by its certified upper bound EkE_k. To determine when this stepsize (15) is indeed optimal, it is convenient to introduce the following normalized quantity

λk:=hk2c2Ekp−1,(16)\lambda_k := \frac{h_k^2}{c^2E_k^{p-1}}, \tag*{(16)}

which measures the size of the observed subgradient relative to the growth parameters and the current distance certificate. For p>1p>1, the certificate update (13) immediately implies λk≥1\lambda_k \ge1. For p=1p=1, the same inequality follows from Lemma 2 whenever xkx_k is nonoptimal.

The threshold on λk\lambda_k that determines whether αP\alpha_P in (15) is optimal to (10) depends on the curvature of the function e↦e−2αcep/2e \mapsto e-2\alpha c e^{p/2}, e∈[0,Ek]e \in[0,E_k]. Since this curvature changes at p=2p=2, we consider the regimes 1≤p≤21 \le p \le2 and p>2p>2 separately. For 1≤p≤21 \le p \le2, the function is convex in ee, so its maximum over [0,Ek][0,E_k] is attained at one of the endpoints. This characterization yields the following explicit stepsize and certificate update.

Proofs of thm:dc-sg-certificate-p-geq-2,thm:dc-sg-certificate-1-leq-p-leq-2 and stepsize interpretation

Proposition 2 (Explicit DC-SG update for 1≤p≤21 \le p \le2). Suppose that 1≤p≤21 \le p \le2, and consider a nonoptimal iterate xkx_k with Ek>0E_k>0. Then the distance-certified stepsize in (10) is unique, and the corresponding update has the following two cases.

  1. If λk>2\lambda_k>2 then

αcert,k=cEkp/2hk2,Uk+1=Ek−c2Ekphk2=(1−1λk)Ek.(17)\alpha_{cert,k}=\frac{cE_k^{p/2}}{h_k^2},\qquad U_{k+1}=E_k-\frac{c^2E_k^p}{h_k^2}=\left(1-\frac{1}{\lambda_k}\right)E_k. \tag*{(17)}
  1. If 1≤λk≤21 \le\lambda_k \le2, then

αcert,k=Ek1−p/22c,Uk+1=hk2Ek2−p4c2=λk4Ek.(18)\alpha_{cert,k}=\frac{E_k^{1-p/2}}{2c},\qquad U_{k+1}=\frac{h_k^2E_k^{2-p}}{4c^2}=\frac{\lambda_k}{4}E_k. \tag*{(18)}

When p>2p>2, the function e↦e−2αcep/2e \mapsto e-2\alpha c e^{p/2}, e∈[0,Ek]e \in[0,E_k], is concave in ee, and the inner maximization may attain its maximum either at the endpoint e=Eke=E_k or at an interior point. This leads to the following explicit distance-certified updates.

Proposition 3 (Explicit DC-SG update for p>2p>2). Suppose that p>2p>2, and consider a nonoptimal iterate xkx_k with Ek>0E_k>0. Then the distance-certified stepsize in (10) is unique, and the corresponding update has the following two cases.

  1. If λk>p\lambda_k>p, then

αcert,k=cEkp/2hk2,Uk+1=Ek−c2Ekphk2=(1−1λk)Ek.(19)\alpha_{cert,k}=\frac{cE_k^{p/2}}{h_k^2},\qquad U_{k+1}=E_k-\frac{c^2E_k^p}{h_k^2}=\left(1-\frac{1}{\lambda_k}\right)E_k. \tag*{(19)}
  1. If 1≤λk≤p1 \le\lambda_k \le p then

αcert,k=chk2(hk2pc2)p2(p−1),Uk+1=p−1p(hk2pc2)1p−1=p−1p(λkp)1p−1Ek.(20)\alpha_{cert,k}=\frac{c}{h_k^2}\left(\frac{h_k^2}{pc^2}\right)^{\frac{p}{2(p-1)}},\qquad U_{k+1}=\frac{p-1}{p}\left(\frac{h_k^2}{pc^2}\right)^{\frac{1}{p-1}}=\frac{p-1}{p}\left(\frac{\lambda_k}{p}\right)^{\frac{1}{p-1}}E_k. \tag*{(20)}

Propositions 2 and 3 show that, when λk\lambda_k in (16) is sufficiently large, both (17) and (19) reduce to the common Polyak-type stepsize (15). When λk\lambda_k is smaller, however, the optimal stepsize depends on the growth exponent pp, as shown in (18) and (20). The proofs of Propositions 2 and 3 rely on careful direct calculations, and we present them in Section 3.3.

For clarity, Table 1 summarizes the explicit stepsizes and the corresponding one-step contraction factors obtained in Propositions 2 and 3. Note that these results greatly refine the monotonicity established in Proposition 1 by providing explicit contraction estimates for the distance certificates, which play an essential role in the subsequent convergence analysis in Section 4.

Growth exponentRegimeStepsize αcert,k\alpha_{\mathrm{cert},k}Certificate ratio Uk+1/EkU_{k+1}/E_k
1≤p≤21 \le p \le2λk>2\lambda_k > 2cEkp/2hk2\frac{cE_k^{p/2}}{h_k^2}1−1/λk1 - 1/\lambda_k
1≤p≤21 \le p \le21≤λk≤21 \le\lambda_k \le2Ek1−p/22c\frac{E_k^{1-p/2}}{2c}λk/4\lambda_k/4
p>2p > 2λk>p\lambda_k > pcEkp/2hk2\frac{cE_k^{p/2}}{h_k^2}1−1/λk1 - 1/\lambda_k
p>2p > 21≤λk≤p1 \le\lambda_k \le pchk2(hk2pc2)p2(p−1)\frac{c}{h_k^2}\left(\frac{h_k^2}{pc^2}\right)^{\frac{p}{2(p-1)}}p−1p(λkp)1p−1\frac{p-1}{p}\left(\frac{\lambda_k}{p}\right)^{\frac{1}{p-1}}

Table 1. Table 1: Explicit distance-certified stepsizes and certificate updates. Here, λk=hk2c2Ekp−1\lambda_k = \frac{h_k^2}{c^2E_k^{p-1}}. The two sets of updates coincide when p=2p = 2.

Proofs of Propositions 2 and 3 and stepsize interpretation

We here prove the explicit formulas in Propositions 2 and 3 and then discuss their interpretation.

Proof of Proposition 2. Suppose that 1≤p≤21 \le p \le2. Since e↦e−2αcep/2e \mapsto e - 2\alpha c e^{p/2} is convex on [0,Ek][0,E_k], its maximum is attained at an endpoint. Therefore, the inner maximization (12) becomes Mk(α)=max⁡{0,Ek−2αcEkp/2}M_k(\alpha) = \max\left\{0,E_k - 2\alpha c E_k^{p/2}\right\}. Define the breakpoint stepsize αbp,k:=Ek1−p/22c\alpha_{\mathrm{bp},k} := \frac{E_k^{1-p/2}}{2c}, at which Ek−2αbp,kcEkp/2=0E_k-2\alpha_{\mathrm{bp},k}cE_k^{p/2}=0. It follows that the worst-case one-step upper bound has two branches

Φk(α,Ek)={α2hk2+Ek−2αcEkp/2,0≤α≤αbp,k,α2hk2,α≥αbp,k.\Phi_k(\alpha,E_k)= \begin{cases} \alpha^2h_k^2+E_k-2\alpha cE_k^{p/2}, & 0\le\alpha\le\alpha_{\mathrm{bp},k},\\ \alpha^2h_k^2, & \alpha\ge\alpha_{\mathrm{bp},k}. \end{cases}

The unconstrained minimizer of the first branch is α^k:=cEkp/2hk2\widehat{\alpha}_k := \frac{cE_k^{p/2}}{h_k^2}. As expected, this coincides with the Polyak-type stepsize (13). The second branch is strictly increasing. Consequently, the unique minimizer is αcert,k=min⁡{αbp,k,α^k}\alpha_{\mathrm{cert},k}=\min\{\alpha_{\mathrm{bp},k},\widehat{\alpha}_k\}. It is easy to verify that α^k<αbp,k⟺hk2>2c2Ekp−1⟺λk>2\widehat{\alpha}_k<\alpha_{\mathrm{bp},k}\Longleftrightarrow h_k^2>2c^2E_k^{p-1}\Longleftrightarrow\lambda_k>2. Thus, when λk>2\lambda_k>2, the unconstrained minimizer α^k\widehat{\alpha}_k lies in [0,αbp,k][0,\alpha_{\mathrm{bp},k}] and is therefore the optimal stepsize. When 1≤λk≤21\le\lambda_k\le2, the minimum is attained at the breakpoint αbp,k\alpha_{\mathrm{bp},k}. Substituting the corresponding stepsizes into Φk(α,Ek)\Phi_k(\alpha,E_k) gives (15a) and (15b).

Proof of Proposition 3. Consider p>2p>2. In this case, the function e↦e−2αcep/2e\mapsto e-2\alpha ce^{p/2} is concave on [0,Ek][0,E_k]. Its derivative with respect to ee is 1−αcpe(p−2)/21-\alpha cpe^{(p-2)/2}. Define the breakpoint stepsize αbp,k:=Ek1−p/2pc>0\alpha_{\mathrm{bp},k}:=\frac{E_k^{1-p/2}}{pc}>0. If 0≤α≤αbp,k0\le\alpha\le\alpha_{\mathrm{bp},k}, the inner maximum is attained at e=Eke=E_k. If α≥αbp,k\alpha\ge\alpha_{\mathrm{bp},k}, an interior maximizer is given by eα:=(1αcp)2p−2e_\alpha:=\left(\frac{1}{\alpha cp}\right)^{\frac{2}{p-2}}. Using the identity αcpeα(p−2)/2=1\alpha cpe_\alpha^{(p-2)/2}=1, we obtain

Mk(α)={Ek−2αcEkp/2,0≤α≤αbp,k,p−2p(1αcp)2p−2,α≥αbp,k.M_k(\alpha)= \begin{cases} E_k-2\alpha cE_k^{p/2}, & 0\le\alpha\le\alpha_{\mathrm{bp},k},\\ \frac{p-2}{p}\left(\frac{1}{\alpha cp}\right)^{\frac{2}{p-2}}, & \alpha\ge\alpha_{\mathrm{bp},k}. \end{cases}

Therefore, the worst-case one-step upper bound also has two branches:

Φk(α,Ek)={α2hk2+Ek−2αcEkp/2,0≤α≤αbp,k,α2hk2+p−2p(1αcp)2p−2,α≥αbp,k.\Phi_k(\alpha,E_k)= \begin{cases} \alpha^2h_k^2+E_k-2\alpha cE_k^{p/2}, & 0\le\alpha\le\alpha_{\mathrm{bp},k},\\ \alpha^2h_k^2+\frac{p-2}{p}\left(\frac{1}{\alpha cp}\right)^{\frac{2}{p-2}}, & \alpha\ge\alpha_{\mathrm{bp},k}. \end{cases}

The unconstrained minimizer of the first branch is α^k:=cEkp/2hk2\hat{\alpha}_k := \frac{cE_k^{p/2}}{h_k^2}, which again coincides with the Polyak-type stepsize (15). Moreover, we have α^k<αbp,k⟺hk2>pc2Ekp−1⟺λk>p\hat{\alpha}_k < \alpha_{\mathrm{bp},k} \Longleftrightarrow h_k^2 > pc^2E_k^{p-1} \Longleftrightarrow\lambda_k > p. Thus, when λk>p\lambda_k > p, the unconstrained minimizer α^k\hat{\alpha}_k lies in [0,αbp,k][0,\alpha_{\mathrm{bp},k}] and is thus the optimal stepsize.

The unconstrained minimizer of the second branch is α~k:=chk2(hk2pc2)p−22(p−1)\tilde{\alpha}_k := \frac{c}{h_k^2}\left(\frac{h_k^2}{pc^2}\right)^{\frac{p-2}{2(p-1)}}. A direct calculation gives α~kαbp,k=(pλk)p−22(p−1)\frac{\tilde{\alpha}_k}{\alpha_{\mathrm{bp},k}} = \left(\frac{p}{\lambda_k}\right)^{\frac{p-2}{2(p-1)}}. Hence, when 1≤λk≤p1 \le\lambda_k \le p, we have α~k≥αbp,k\tilde{\alpha}_k \ge\alpha_{\mathrm{bp},k}, so α~k\tilde{\alpha}_k lies in [αbp,k,∞)[\alpha_{\mathrm{bp},k},\infty) and is the optimal stepsize. At λk=p\lambda_k=p, both branch minimizers coincide with αbp,k\alpha_{\mathrm{bp},k}. Substituting the corresponding stepsizes into Φk(α,Ek)\Phi_k(\alpha,E_k) yields (16a) and (16b).

The explicit updates in Propositions 2 and 3 share a common two-branch structure, which is summarized in Table 2. In particular, for all p≥1p \ge1, the first branch is the Polyak-type update (15a) and (16a). This stepsize is selected when λk\lambda_k is sufficiently large, namely, when λk>2\lambda_k > 2 for 1≤p≤21 \le p \le2 and when λk>p\lambda_k > p for p>2p > 2. The complementary branch depends on the curvature of e−2αcep/2e-2\alpha ce^{p/2}. For 1≤p≤21 \le p \le2, this function is convex in ee, and its maximum over [0,Ek][0,E_k] is attained at an endpoint. When 1≤λk≤21 \le\lambda_k \le2, the optimal stepsize is capped at the breakpoint αbp,k:=Ek1−p/22c\alpha_{\mathrm{bp},k}:=\frac{E_k^{1-p/2}}{2c}, leading to (15b). We refer to this update as the capped branch. For p>2p>2, the function e−2αcep/2e-2\alpha ce^{p/2} is concave, and the inner maximum may be attained at an interior stationary point. When 1≤λk≤p1 \le\lambda_k \le p, this gives (16b). We refer to this update as the interior-maximizer branch. Figure 2 illustrates these four different minimizer regimes in Table 2.

Range of ppCommon branchComplementary branch
1≤p≤21 \le p \le2λk>max⁡{2,p}\lambda_k > \max\{2,p\}1≤λk≤max⁡{2,p}1 \le\lambda_k \le\max\{2,p\}
1≤p≤21 \le p \le2Polyak-type branch; see (17).Capped branch; see (18).
p>2p > 2Polyak-type branch; see (19).Interior-maximizer branch; see (20).

Table 2. Summary of the two branches in the explicit DC-SG updates; λk\lambda_k is defined in (16).

Four minimizer regimes in Table 2

Figure 2. The four minimizer regimes in Table 2. Each panel plots Φk(α,Ek)\Phi_k(\alpha, E_k) against the stepsize α\alpha where c=Ek=1c=E_k=1 and hk=λkh_k=\lambda_k. Solid curves show the valid branches; dashed curves extend their formulas outside the valid intervals. Filled dots mark the certified minimizers αcert,k\alpha_{\mathrm{cert},k}; open circles mark the breakpoints αbp,k\alpha_{\mathrm{bp},k}. The symbols α^k\hat{\alpha}_k and α~k\tilde{\alpha}_k denote the minimizers of the first and second smooth branches, respectively.

Despite their different forms, the distance certificate is always contracted. The explicit contraction factors derived in Propositions 2 and 3 form the basis of the convergence analysis in Section 4.

Convergence rates of DC-SG

In this section, we establish the convergence rates of our proposed DC-SG method in Algorithm 2. We also compare our DC-SG method with the state-of-the-art results.

Convergence guarantees under global LL-Lipschitz continuity

Suppose that ff is globally LL-Lipschitz continuous. Then every subgradient satisfies hk=∥gk∥≤Lh_k = \lVert g_k\rVert\le L. For convenience, define

κ:=Lc,q:=max⁡{2,p}.(21)\kappa:= \frac{L}{c}, \qquad q := \max\{2,p\}. \tag*{(21)}

Based on Propositions 2 and 3, the following result provides a unified one-step decrease for all p≥1p \ge1.

Lemma 4 (One-step certificate decrease). Let ff be convex and globally LL-Lipschitz continuous. Suppose that ff satisfies the (p,c)(p,c)-Hölder growth (3). For each iteration of DC-SG, we have

Ek+1≤Ek−min⁡{Ekq,Ekpκ2}.(22)E_{k+1} \le E_k - \min\left\{\frac{E_k}{q}, \frac{E_k^p}{\kappa^2}\right\}. \tag*{(22)}

Proof. Suppose that λk>max⁡{2,p}\lambda_k > \max\{2,p\}, i.e., the Polyak branch is active. By Propositions 2 and 3, its propagated certificate satisfies Uk+1=Ek−c2Ekphk2U_{k+1} = E_k - \frac{c^2E_k^p}{h_k^2}. Using hk≤Lh_k \le L gives

Uk+1≤Ek−c2EkpL2=Ek−Ekpκ2.(23)U_{k+1} \le E_k - \frac{c^2E_k^p}{L^2} = E_k - \frac{E_k^p}{\kappa^2}. \tag*{(23)}

Suppose that λk≤max⁡{2,p}\lambda_k \le\max\{2,p\}, i.e., the complementary branch is active. When 1≤p≤21 \le p \le2, the capped update (15b) satisfies Uk+1≤Ek/2U_{k+1} \le E_k/2. When p>2p > 2, the interior-maximizer update (16b) satisfies Uk+1≤(1−1p)EkU_{k+1} \le\left(1-\frac{1}{p}\right)E_k. Since q=max⁡{2,p}q = \max\{2,p\}, both cases imply

Uk+1≤Ek−Ekq.(24)U_{k+1} \le E_k - \frac{E_k}{q}. \tag*{(24)}

Therefore, regardless of the value of λk\lambda_k, combining (19) with (20) leads to

Uk+1≤Ek−min⁡{Ekq,Ekpκ2}.U_{k+1} \le E_k - \min\left\{\frac{E_k}{q}, \frac{E_k^p}{\kappa^2}\right\}.

By construction (11), the certificate update guarantees Ek+1≤Uk+1E_{k+1} \le U_{k+1}, the bound (18) follows. □

The recursion (18) directly yields global convergence of the certificate sequence {Ek}\{E_k\}. We first consider the case p>1p > 1. Throughout this section, define the threshold

Eth:=(κ2q)1p−1,(25)E_{\mathrm{th}} := \left(\frac{\kappa^2}{q}\right)^{\frac{1}{p-1}}, \tag*{(25)}

at which we have Ek/q=Ekp/κ2E_k/q = E_k^p/\kappa^2. Above this threshold, the certificate decreases geometrically until it enters the local region; within the local region, it converges at a sublinear rate.

Theorem 1 (Sublinear convergence when p>1p > 1). Let ff be convex and globally LL-Lipschitz continuous. Suppose that ff satisfies the (p,c)(p,c)-Hölder growth (3) with p>1p > 1. Define EthE_{\mathrm{th}} in (21).

  • If E0≤EthE_0 \le E_{\mathrm{th}}, then, for every k≥0k \ge0,

Ek≤(E01−p+(p−1)kκ2)−1p−1.(26)E_k \le\left(E_0^{1-p}+\frac{(p-1)k}{\kappa^2}\right)^{-\frac{1}{p-1}}. \tag*{(26)}
  • If E0>EthE_0 > E_{\mathrm{th}}, define K0:=⌈log⁡(E0/Eth)log⁡(q/(q−1))⌉K_0 := \left\lceil\frac{\log(E_0/E_{\mathrm{th}})}{\log(q/(q-1))}\right\rceil. Then EK0≤EthE_{K_0} \le E_{\mathrm{th}}, and, for every k≥K0k \ge K_0,

Ek≤(q+(p−1)(k−K0)κ2)−1p−1.(27)E_k \le\left(\frac{q+(p-1)(k-K_0)}{\kappa^2}\right)^{-\frac{1}{p-1}}. \tag*{(27)}

Proof. Suppose first that E0≤EthE_0 \le E_{\mathrm{th}}. Since the certificate sequence is nonincreasing, Ek≤EthE_k \le E_{\mathrm{th}} for all k≥0k \ge0. Hence, we have Ekpκ2≤Ekq\frac{E_k^p}{\kappa^2} \le\frac{E_k}{q}, and (18) reduces to

Ek+1≤Ek(1−Ekp−1κ2).E_{k+1} \le E_k\left(1-\frac{E_k^{p-1}}{\kappa^2}\right).

If Ek=0E_k=0 for some kk, (22a) follows immediately from monotonicity. Otherwise, applying Bernoulli’s inequality gives

Ek+11−p≥Ek1−p(1−Ekp−1κ2)1−p≥Ek1−p+p−1κ2.E_{k+1}^{1-p} \ge E_k^{1-p}\left(1-\frac{E_k^{p-1}}{\kappa^2}\right)^{1-p} \ge E_k^{1-p}+\frac{p-1}{\kappa^2}.

Iterating this inequality from 0 to k−1k-1 yields (22a).

Suppose next that E0>EthE_0 > E_{\mathrm{th}}. Then we have Ekpκ2>Ekq\frac{E_k^p}{\kappa^2} > \frac{E_k}{q}, and hence (18) reduces to Ek+1≤(1−1q)EkE_{k+1} \le\left(1-\frac{1}{q}\right)E_k. Therefore, the certificate either enters the local region before K0K_0 or satisfies

EK0≤E0(1−1q)K0≤Eth.E_{K_0} \le E_0\left(1-\frac{1}{q}\right)^{K_0} \le E_{\mathrm{th}}.

Applying (22a) from iteration K0K_0 and using EK01−p≥Eth1−p=q/κ2E_{K_0}^{1-p} \ge E_{\mathrm{th}}^{1-p}=q/\kappa^2 proves (22b).

Theorem 1 immediately yields the following iteration complexity.

Corollary 1 (Iteration complexity for p>1p>1). Under the setting of Theorem 1, let 0<ϵ<E00<\epsilon<E_0. DC-SG in Algorithm 2 obtains an iterate satisfying dist⁡(xk,X⋆)2≤ϵ\operatorname{dist}(x_k,X^\star)^2\le\epsilon within O(κ2ϵ−(p−1))O\left(\kappa^2\epsilon^{-(p-1)}\right) iterations. More precisely, the following statements hold.

  • if E0≤EthE_0\le E_{\mathrm{th}}, then Ek≤ϵE_k\le\epsilon whenever k≥⌈κ2p−1(ϵ1−p−E01−p)⌉k\ge\left\lceil\frac{\kappa^2}{p-1}\left(\epsilon^{1-p}-E_0^{1-p}\right)\right\rceil.

  • if E0>EthE_0>E_{\mathrm{th}} and 0<ϵ≤Eth0<\epsilon\le E_{\mathrm{th}}, then Ek≤ϵE_k\le\epsilon whenever k≥K0+⌈κ2ϵ1−p−qp−1⌉k\ge K_0+\left\lceil\frac{\kappa^2\epsilon^{1-p}-q}{p-1}\right\rceil.

When p=1p=1, (18) immediately gives linear convergence. We present the guarantee below.

Theorem 2 (Linear convergence for p=1p=1). Let ff be convex and globally LL-Lipschitz continuous. Suppose that ff satisfies the (p,c)(p,c)-Hölder growth (3) with p=1p=1. Define δ:=min⁡{12,1κ2}\delta:=\min\left\{\frac{1}{2},\frac{1}{\kappa^2}\right\}. Then, for every k≥0k\ge0,

Ek≤(1−δ)kE0.(28)E_k\le(1-\delta)^kE_0. \tag*{(28)}

Consequently, for every 0<ϵ<E00<\epsilon<E_0, we have Ek≤ϵE_k\le\epsilon whenever

k≥⌈log⁡(E0/ϵ)log⁡(1/(1−δ))⌉.(29)k\ge\left\lceil\frac{\log(E_0/\epsilon)}{\log(1/(1-\delta))}\right\rceil. \tag*{(29)}

Proof. When p=1p=1, we have q=2q=2 by definition (21). Thus, (22) becomes

Ek+1≤Ek−min⁡{Ek2,Ekκ2}=(1−δ)Ek.E_{k+1} \le E_k-\min\left\{\frac{E_k}{2},\frac{E_k}{\kappa^2}\right\}=(1-\delta)E_k.

Iterating this inequality proves (28). The complexity bound follows by solving (1−δ)kE0≤ϵ(1-\delta)^kE_0\le\epsilon. □

The case p=1p=1 corresponds to the classical sharp-growth condition, also known as weak sharp minima when the solution set is not necessarily a singleton [18]. It has long been recognized that this growth structure allows suitably designed subgradient methods to achieve linear convergence; see, for example, [5, 7, 8]. Thus, Theorem 2 recovers the expected linear rate using our DC-SG method. Note that DC-SG maintains a valid current-iterate distance certificate and does not require knowledge of the optimal value f⋆f^\star [5] or a predetermined stagewise stepsize schedule [7]. We further compare with state-of-the-art analysis in § 5.3.

Refined rates under shrinking subgradients

The results in Theorems 1 and 2 assume a global Lipschitz constant. DC-SG can achieve faster rates when the norms of selected subgradients decrease as the iterates approach the solution set. Specifically, suppose that the subgradients of ff satisfy the following upper bound

∥gk∥≤L dist⁡(xk,X⋆)s(30)\lVert g_k\rVert\le L\,\operatorname{dist}(x_k,X^\star)^s \tag*{(30)}

for some L>0L>0 and s∈[0,p−1]s\in[0,p-1]. When s=0s=0, it reduces to the globally Lipschitz case. Note that it is necessary to have s≤p−1s\le p-1 since the Hölder growth condition and the subgradient inequality imply hk≥c dist⁡(xk,X⋆)p−1h_k\ge c\,\operatorname{dist}(x_k,X^\star)^{p-1} at every nonoptimal iterate (see Lemma 2). Under this shrinking subgradient assumption (30), we obtain the following refinement of the rates in Theorems 1 and 2.

Corollary 2 (Refined rates under shrinking subgradients). Suppose that ff is convex and satisfies the (p,c)(p,c)-Hölder growth condition and that (30) holds. Let κ=L/c\kappa=L/c and q=max⁡{2,p}q=\max\{2,p\}. Then every DC-SG iteration in Algorithm 2 satisfies

Ek+1≤Ek−min⁡{Ekq,Ekp−sκ2}.(31)E_{k+1}\le E_k-\min\left\{\frac{E_k}{q},\frac{E_k^{p-s}}{\kappa^2}\right\}. \tag*{(31)}

Consequently, the following statements hold.

  • If 0≤s<p−10\le s<p-1, then we have Ek=O(k−1p−1−s)E_k=O\left(k^{-\frac{1}{p-1-s}}\right), and the iteration complexity for obtaining Ek≤ϵE_k\le\epsilon is O(κ2ϵ−(p−1−s))O\left(\kappa^2\epsilon^{-(p-1-s)}\right).

  • If s=p−1s=p-1, define δs:=min⁡{1q,1κ2}\delta_s:=\min\left\{\frac{1}{q},\frac{1}{\kappa^2}\right\}. Then we have linear convergence Ek≤(1−δs)kE0E_k\le(1-\delta_s)^kE_0.

Proof. Since ek≤Eke_k\le E_k, (30) gives hk2≤L2Eksh_k^2\le L^2E_k^s. Thus, on the Polyak-type branch, we have

c2Ekphk2≥c2EkpL2Eks=Ekp−sκ2.\frac{c^2E_k^p}{h_k^2}\ge\frac{c^2E_k^p}{L^2E_k^s}=\frac{E_k^{p-s}}{\kappa^2}.

The complementary branch continues to decrease the certificate by at least Ek/qE_k/q, similar to (24). Thus, (22) reduces to (31).

If s<p−1s<p-1, applying the argument of Theorem 1 with p−1p-1 replaced by p−1−sp-1-s establish the claimed result. If s=p−1s=p-1, then (31) reduces to Ek+1≤(1−δs)EkE_{k+1}\le(1-\delta_s)E_k. This finishes the proof. □

Whenever s>0s > 0, DC-SG achieves a strictly faster convergence rate and thus automatically adapts to shrinking subgradient norms. In particular, when p>1p > 1 and s=p−1s = p - 1, DC-SG converges linearly without requiring the sharp-growth condition. For example, the function f(x)=∥Ax∥pf(x) = \lVert Ax\rVert^{p} with A∈Rm×nA \in\mathbb{R}^{m \times n}, p>1p > 1 satisfies the condition (25) with s=p−1s = p - 1, and hence DC-SG converges linearly on this class of problems (see our experiments in § 6.1). A related acceleration phenomenon for adaptive Polyak-type stepsizes under higher-order growth was recently established in [11].

Remark 2 (Shrinking subgradients and norm-aware stepsizes). The refined rate in Corollary 2 is not specific to our DC-SG method. More generally, such an improvement can arise in subgradient methods whose one-step progress bounds use the observed norm hkh_k and do not replace it by the global upper bound LL; see also Remark 1. For example, the classical Polyak stepsize (6a) satisfies

ek+1≤ek−(f(xk)−f⋆)2hk2≤ek−c2ekphk2≤ek−1κ2ekp−s,(32)e_{k+1} \le e_k - \frac{(f(x_k)-f^\star)^2}{h_k^2} \le e_k - \frac{c^2 e_k^p}{h_k^2} \le e_k - \frac{1}{\kappa^2}e_k^{p-s}, \tag*{(32)}

where the last inequality uses (25). Thus, the Polyak stepsize enjoys the same refined polynomial exponent when s<p−1s < p - 1 and linear convergence when s=p−1s = p - 1, similar to Corollary 2. The key to obtaining (26) and (27) is to exploit (25) directly and not to relax it using the uniform bound hk≤Lh_k \le L. In contrast, standard stagewise and geometrically decaying stepsize schemes [7, 8, 9, 10] use the global constant LL in their stepsize design. Such methods do not automatically adapt to shrinking subgradient norms and may fail to attain the refined rates (see our experiments in § 6). □

Comparison with the state of the art

We compare DC-SG with several closely related subgradient methods. First, the convergence rates in Theorems 1 and 2 are faster than the classical subgradient method. Under uniformly bounded subgradients, the standard analysis with a suitably chosen diminishing stepsize of order αk=O(1/k)\alpha_k = O(1/\sqrt{k}) guarantees f(x^k)−f⋆=O(k−1/2)f(\hat{x}_k) - f^\star= O\left(k^{-1/2}\right) for a suitable averaged iterate x^k\hat{x}_k. Combining this bound with the Hölder growth (3) gives dist⁡(x^k,X⋆)=O(k−12p)\operatorname{dist}(\hat{x}_k, X^\star) = O\left(k^{-\frac{1}{2p}}\right). By contrast, Theorems 1 and 2 establish the last-iterate guarantee

dist⁡(xk,X⋆)≤Ek=O(k−12(p−1))(33)\operatorname{dist}(x_k, X^\star) \le\sqrt{E_k} = O\left(k^{-\frac{1}{2(p-1)}}\right) \tag*{(33)}

when p>1p > 1, and linear convergence when p=1p = 1. Thus, DC-SG strictly improves the polynomial exponent for every p>1p > 1 and achieves a linear rate in the sharp-growth case. Moreover, these guarantees hold directly for the last iterate xkx_k and do not require averaging.

As discussed in § 4.1, our distance-certified stepsize (8) is directly motivated by the classical Polyak stepsize (6a). Indeed, both stepsizes aim to minimize the one-step upper bound shown in Lemma 1, but they use different information. The Polyak stepsize requires exact knowledge of the optimal value f⋆f^\star, and our DC-SG uses the growth parameters (p,c)(p,c) and an initial certificate U0U_0. As shown in (27), the Polyak stepsize attains the same asymptotic rate as DC-SG under Hölder growth and similarly benefits from shrinking subgradients. Recently, [10 Theorems 1 and 2] established matching upper and lower bounds showing that the Polyak stepsize is minimax optimal for decreasing the distance to the solution set for a class of globally Lipschitz convex functions satisfying a general error bound. When specialized to (p,c)(p,c)-Hölder growth, the guarantees in Theorems 1 and 2 also attain the corresponding minimax-optimal rate asymptotically.

There are several other stepsize schedules for subgradient methods based on growth parameters and a global Lipschitz constant, including [7, 8, 9, 10]. For the sharp-growth case p=1p = 1, Goffin [8] established linear convergence using a geometrically decaying stepsize. Johnstone and Moulin [7] developed related decaying and descending-stairs stepsizes for general Hölder growth. In their notation, θ=1/p\theta= 1/p, and their methods attain the rate in (33) when p>1p > 1 and linear convergence when p=1p = 1. Yang and Lin [9] obtain comparable improvements under a local error-bound condition through a restarted subgradient method, but their complexity generally includes an additional logarithmic factor and their method requires averaging within each stage. As mentioned above, Wang [10] proved that the Polyak stepsize is minimax optimal for globally Lipschitz convex functions satisfying a general error bound and, under an additional regularity condition, established the same conclusion for a predetermined decaying scheme called DecayGD.

All these geometric, descending-stairs, restarted, and DecayGD schemes [7, 8, 9, 10] predetermine their stepsizes based on a uniform subgradient bound, growth information, and an initial distance bound (see Table 3 for a comparison). In contrast, DC-SG recomputes its stepsize adaptively at every iteration from the current certificate EkE_k and the observed subgradient norm hkh_k. In particular, neither a global Lipschitz constant nor a predetermined stage length is required in DC-SG; the Lipschitz constant enters only its worst-case analysis. Moreover, retaining the observed norm hkh_k allows DC-SG to achieve the refined rates in Corollary 2 when the selected subgradients diminish near X⋆X^\star. The existing guarantees for the predetermined schemes above [7, 8, 9, 10] are based on uniform subgradient bounds and do not capture this additional improvement; also see Remark 2.

Methodf⋆f^\starppccLLU0U_0Stepsize scheduleReference
DC-SG–✓✓–✓AdaptiveThis work
Polyak✓––––Adaptive[5]
RSG–✓✓✓✓Stagewise[9]
DS-SG–✓✓✓✓Stagewise[7]
DecayGD–✓✓✓✓Predetermined[10]

Table 3. Problem information and stepsize schedules. Here, f⋆f^\star is the optimal value, pp and cc are the Hölder growth parameters, LL is a uniform bound on the subgradient norms, and U0≥dist⁡(x0,X⋆)2U_0 \ge\operatorname{dist}(x_0, X^\star)^2 is an initial squared-distance bound. A checkmark (✓) indicates that the corresponding quantity is used in the method.

Numerical experiments

In this section, we present two experiments to demonstrate the theoretical findings in this work. We compare our proposed DC-SG in Algorithm 2 with the classical Polyak subgradient method [5], the restarted subgradient method (RSG) [9], the descending-stairs subgradient method (DS-SG) [7], and the decaying-stepsize method (DecayGD) [10].

Table 3 summarizes the problem information used in these stepsize schedules. Our DC-SG uses pp, cc, and U0U_0, and adapts its stepsize to the observed subgradient norm without requiring f⋆f^\star or LL. The Polyak method requires the exact optimal value f⋆f^\star and serves as a baseline. For comparison, RSG, DS-SG, and DecayGD use pp, cc, LL, and U0U_0 to determine their schedules. RSG and DS-SG employ stagewise schedules, whereas DecayGD uses a predetermined decaying sequence. We include DS-SG only when 1≤p≤21 \le p \le2, the range covered by its convergence guarantees.

Power objectives with exact growth constants

We first consider a family of power objectives with an explicit minimizer and exact growth constants:

min⁡x∈Cfp(x):=1p∥A(x−x⋆)∥1p,C:={x∈Rd:∥x∥2≤1},(34)\min_{x\in C} f_p(x) := \frac{1}{p}\lVert A(x-x^\star)\rVert_1^p,\qquad C := \{x\in\mathbb{R}^d : \lVert x\rVert_2 \le1\}, \tag*{(34)}

where d=50d = 50 and p∈{1,2,3}p \in\{1,2,3\}. We construct A=Q1diag⁡(σ)Q2⊤A = Q_1\operatorname{diag}(\sigma)Q_2^\top, where Q1Q_1 and Q2Q_2 are random orthogonal matrices and the singular values are logarithmically spaced between 1/21/2 and 11. Thus, ∥A∥2=1\lVert A\rVert_2 = 1 and cond⁡2(A)=2\operatorname{cond}_2(A) = 2. We choose x⋆x^\star such that ∥x⋆∥2=1/2\lVert x^\star\rVert_2 = 1/2. By construction, AA is nonsingular, and thus the solution set is X⋆={x⋆}X^\star= \{x^\star\} and the optimal value is f⋆=0f^\star= 0.

The objective in (34) satisfies the Hölder growth condition (3) with c=1p(max⁡1≤j≤d∥A−1ej∥2)−pc = \frac{1}{p}\left(\max_{1\le j\le d}\lVert A^{-1}e_j\rVert_2\right)^{-p}, where eje_j denotes the jjth standard basis vector. We use the subgradient

g(x)=∥A(x−x⋆)∥1p−1A⊤sign⁡(A(x−x⋆)),g(x) = \lVert A(x-x^\star)\rVert_1^{p-1}A^\top\operatorname{sign}(A(x-x^\star)),

with sign⁡(0)=0\operatorname{sign}(0)=0. This oracle satisfies the shrinking-subgradient condition (30) with s=p−1s=p-1. A uniform subgradient bound on CC is L=2p−1dp/2L=2^{p-1}d^{p/2}. All methods are initialized at x0=0x_0=0, and we use the initial squared-distance bound U0=1U_0=1. This bound is conservative, since e0=∥x0−x⋆∥22=1/4e_0=\lVert x_0-x^\star\rVert_2^2=1/4. We run each method for N=4000N=4000 subgradient evaluations.

The numerical results are shown in Figure 3, which are consistent with the theoretical guarantees. In all three cases, the certificate satisfies ek≤Eke_k \le E_k throughout the iterations of DC–SG and decreases geometrically. For p=1p=1, this behavior agrees with Theorem 2; for p=2,3p=2,3, it agrees with Corollary 2 under the shrinking condition s=p−1s=p-1. As shown in Figure 3, although the squared-distance error of DC–SG may oscillate, its certificate gives a monotonically decreasing upper bound, as guaranteed by Proposition 1. In this experiment, the Polyak method using with the exact optimal value f⋆=0f^\star=0 converges fastest among all methods. Our DC–SG also exhibits linear convergence for all three values of pp and maintains a valid distance certificate without using f⋆f^\star. In addition, DC–SG converges much faster than DecayGD, DS–SG, and RSG. In particular, the methods using predetermined schedules (DecayGD, DS–SG, and RSG) make substantially less progress for p=2,3p=2,3. This comparison clearly shows the benefit of using the observed subgradient norm in the stepsize selection.

Figure 3. Figure 3: Problem (29) with p∈{1,2,3}p \in\{1,2,3\}: Normalized squared distance ek/e0e_k/e_0 versus the number of subgradient evaluations for DC–SG (Algorithm 2), Polyak method, DS–SG, RSG, and DecayGD, where ek=dist⁡(xk,X⋆)2e_k = \operatorname{dist}(x_k,X^\star)^2. The black dashed curve shows the normalized DC–SG certificate Ek/e0E_k/e_0.

Regularized support vector machines

We next consider an ℓ2\ell_2-regularized support vector machine with hinge loss:

min⁡w∈Cf(w):=1m∑i=1mmax⁡{0,1−yiai⊤w}+λ2∥w∥22,C:={w∈Rd:∥w∥2≤R},(35)\min_{w\in C} f(w) := \frac{1}{m}\sum_{i=1}^{m}\max\{0,1-y_i a_i^\top w\}+\frac{\lambda}{2}\lVert w\rVert_2^2,\qquad C:=\{w\in\mathbb{R}^d:\lVert w\rVert_2\le R\}, \tag*{(35)}

where λ=10−2\lambda= 10^{-2} and R=2/λR = \sqrt{2/\lambda}. We use the Wisconsin Diagnostic Breast Cancer dataset [28], which contains m=569m = 569 samples with 30 features. We standardize each feature to have zero mean and unit variance, and append a constant coordinate to include an intercept.

The objective in (30) is λ\lambda-strongly convex and has a unique minimizer w⋆w^\star. Moreover, λ∥w⋆∥2/2<f(w⋆)≤f(0)=1\lambda\lVert w^\star\rVert^2/2 < f(w^\star) \le f(0) = 1, so w⋆∈Cw^\star\in C. Consequently, the Hölder growth condition (3) holds with p=2p = 2 and c=λ/2=5×10−3c = \lambda/2 = 5 \times10^{-3}. We use the subgradient g(w)=−1m∑i:yiai⊤w<1yiai+λwg(w) = -\frac{1}{m}\sum_{i:y_i a_i^\top w<1} y_i a_i + \lambda w. The selected subgradients need not vanish as ww approaches w⋆w^\star. Applying Theorem 1 with p=2p = 2 yields Ek=O(1/k)E_k = O(1/k) for DC-SG. We compute a reference solution using an interior-point solver, Clarabel [29]. The reference solution is used to evaluate the errors, and its objective value is also used in the Polyak method. All methods are initialized at w0=0w_0 = 0, and we use the initial squared-distance bound U0=R2=200U_0 = R^2 = 200. We run each method for N=20,000N = 20{,}000 iterations.

The numerical results are shown in Figure 4. The distance certificate from DC-SG exhibits an approximately O(1/k)O(1/k) rate over the later iterations. This behavior is consistent with Theorem 1 for p=2p = 2. The measured squared-distance error decreases faster than the certificate, indicating that the certificate provides a conservative estimate of the actual error in this example. After an initial transient, DC-SG achieves substantially higher distance accuracy than the comparison methods. At N=20,000N = 20{,}000, its normalized squared distance is 1.5×10−71.5 \times10^{-7}, while those of the other methods range from 3.0×10−53.0 \times10^{-5} to 9.1×10−59.1 \times10^{-5}. This illustrates the effectiveness of DC-SG on a nonsmooth problem with an explicit growth constant and uniformly bounded subgradients.

Figure 4. Problem (30) with λ=10−2\lambda= 10^{-2}: normalized squared distance ek/e0e_k/e_0 versus the number of subgradient evaluations, where ek=∥wk−w⋆∥2e_k = \lVert w_k - w^\star\rVert^2. We compare DC-SG, the Polyak method, DS-SG, RSG, and DecayGD. The black dashed curve shows the normalized DC-SG certificate Ek/e0E_k/e_0.

Conclusion

In this paper, we have proposed DC-SG, a new distance-certified subgradient method for convex optimization under Hölder growth. Our DC-SG method maintains a computable upper bound on the squared distance to the solution set and uses this certificate to select Polyak-type stepsizes, without requiring the optimal objective value. We have established sublinear convergence for p>1p > 1 and linear convergence for p=1p = 1, together with sharper rates under shrinking subgradients, including linear convergence when s=p−1s = p - 1. The numerical experiments support these theoretical findings. For future work, an interesting direction is to develop adaptive estimates of the growth parameters while preserving the validity of the distance certificate.

Statements on AI use. This paper started with a careful examination of the faster subgradient methods in [7] in March 2026 as an SRIP topic for the first author. Motivated by the Polyak stepsize, the authors had the idea of the one-step minimax principle for choosing the stepsize in subgradient methods under Hölder growth. We used ChatGPT 5.6 and 6 to assist with some derivations, literature searches, proof checking, and language editing. We also used Claude Opus 5 for coding and numerical experiments. The authors carefully reviewed all AI-assisted material and independently verified the mathematical arguments. The authors assume responsibility for all content.

References

  1. [1]Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004. doi: 10.1007/978-1-4419-8853-9.DOI
  2. [2]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, UK, 2004. doi: 10.1017/CBO9780511804441.DOI
  3. [3]Zhi-Quan Luo and Wei Yu. An introduction to convex optimization for communications and signal processing. IEEE Journal on Selected Areas in Communications, 24(8):1426–1438, 2006. doi: 10.1109/JSAC.2006.879347.DOI
  4. [4]Naum Z. Shor. The rate of convergence of the generalized gradient descent method. Cybernetics, 4(3):79–80, 1968. doi: 10.1007/BF01073933.
  5. [5]Boris T. Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 9(3):14–29, 1969. doi: 10.1016/0041-5553(69)90061-5.DOI
  6. [6]Arkadi S. Nemirovski and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, New York, 1983.
  7. [7]Patrick R. Johnstone and Pierre Moulin. Faster subgradient methods for functions with Hölderian growth. Mathematical Programming, 180(1–2):417–450, 2020. doi: 10.1007/s10107-018-01361-0.DOI
  8. [8]Jean-Louis Goffin. On convergence rates of subgradient optimization methods. Mathematical Programming, 13(1):329–347, 1977.DOI
  9. [9]Tianbao Yang and Qihang Lin. RSG: Beating subgradient method without smoothness and strong convexity. Journal of Machine Learning Research, 19(6):1–33, 2018. URL https://jmlr.org/papers/v19/17-016.html.
  10. [10]Alex L. Wang. Optimal subgradient methods for Lipschitz convex optimization with error bounds. arXiv preprint arXiv:2512.13863, 2025. URL https://arxiv.org/abs/2512.13863.
  11. [11]Damek Davis, Dmitriy Drusvyatskiy, and Liwei Jiang. Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth. Mathematical Programming, 2025.
  12. [12]Feng-Yi Liao, Lijun Ding, and Yang Zheng. Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. Journal of Global Optimization, 94(1):235–263, 2026. doi: 10.1007/s10898-025-01585-3.DOI
  13. [13]Feng-Yi Liao and Yang Zheng. A proximal descent method for minimizing weakly convex optimization. arXiv preprint arXiv:2509.02804, 2025. URL https://arxiv.org/abs/2509.02804.
  14. [14]Feng-Yi Liao and Yang Zheng. Revisiting proximal bundle methods: Improved rates under Hölder smoothness. arXiv preprint arXiv:2609.15806, 2026.arxiv.org/abs/2609.15806
  15. [15]Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17(4):1205–1223, 2007.
  16. [16]Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W. Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 165(2):471–507, 2017. doi: 10.1007/s10107-016-1091-6.DOI
  17. [17]Zirui Zhou and Anthony Man-Cho So. A unified approach to error bounds for structured convex optimization problems. Mathematical Programming, 165(2):689–728, 2017. doi: 10.1007/s10107-016-1100-9.DOI
  18. [18]James V. Burke and Michael C. Ferris. Weak sharp minima in mathematical programming. SIAM Journal on Control and Optimization, 31(5):1340–1359, 1993. doi: 10.1137/0331063.DOI
  19. [19]Zhi-Quan Luo and Paul Tseng. Error bounds and convergence analysis of feasible descent methods: A general approach. Annals of Operations Research, 46(1):157–178, 1993.DOI
  20. [20]Vincent Roulet and Alexandre d’Aspremont. Sharpness, restart, and acceleration. SIAM Journal on Optimization, 30(1):262–289, 2020. doi: 10.1137/18M1224568.
  21. [21]Nikhil Devanathan and Stephen Boyd. Polyak minorant method for convex optimization. Journal of Optimization Theory and Applications, 203(3):2263–2282, 2024. doi: 10.1007/s10957-024-02412-7.DOI
  22. [22]Chang He, Wenzhi Gao, Bo Jiang, Madeleine Udell, and Shuzhong Zhang. New results on the Polyak stepsize: Tight convergence analysis and universal function classes. arXiv preprint arXiv:2512.06231, 2025. URL https://arxiv.org/abs/2512.06231.
  23. [23]Moslem Zamani and François Glineur. Exact convergence rate of the last iterate in subgradient methods. SIAM Journal on Optimization, 35(3):2182–2201, 2025. doi: 10.1137/24M1717762.DOI
  24. [24]Jean-Louis Goffin and Krzysztof C. Kiwiel. Convergence of a simple subgradient level method. Mathematical Programming, 85(1):207–211, 1999. doi: 10.1007/s101070050053.DOI
  25. [25]Angelia Nedić and Dimitri P. Bertsekas. Incremental subgradient methods for nondifferentiable optimization. SIAM Journal on Optimization, 12(1):109–138, 2001. doi: 10.1137/S1052623499362111.DOI
  26. [26]Anbang Liu, Mikhail A. Bragin, Xi Chen, and Xiaohong Guan. Accelerating level-value adjustment for the Polyak stepsize. Journal of Optimization Theory and Applications, 206(3):71, 2025. doi: 10.1007/s10957-025-02750-0.DOI
  27. [27]Elad Hazan and Sham M. Kakade. Revisiting the Polyak step size. arXiv preprint arXiv:1905.00313, 2019. URL https://arxiv.org/abs/1905.00313.
  28. [28]William Wolberg, Olvi Mangasarian, Nick Street, and W. Street. Breast Cancer Wisconsin (Diagnostic). UCI Machine Learning Repository, 1993. URL https://doi.org/10.24432/C5DW2B. Dataset.
  29. [29]Paul J Goulart and Yuwen Chen. Clarabel: An interior-point solver for conic programs with quadratic objectives. Mathematical Programming Computation, pages 1–83, 2026.arxiv.org/abs/2405.12762

Paper details

vlnc:W_2bf5mwz8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents