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
where is a closed convex function and is a closed and convex set. We do not assume that is smooth or strongly convex. Let denote the solution set and the optimal value. Throughout this paper, we assume that is nonempty and 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 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 is globally Lipschitz-continuous, the classical subgradient method achieves a convergence rate of after subgradient evaluations for a suitably averaged point [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 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
for some choice of and . This is equivalent to . 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 ; under this parameterization, we have 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 and [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 and . The case is commonly known as the quadratic growth (QG) condition [12, 17], and the case 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 , 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 [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 . 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
when (Theorem 1) and converges linearly when (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 at is defined by
Given an initial point , the projected subgradient method generates iterates according to
where , is the stepsize, and denotes the Euclidean projection onto . 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 satisfies -Hölder growth on if there exist and such that
where denotes the distance from to the solution set.
A distance-certified subgradient method (DC-SG)
Algorithm 1 Projected subgradient method
Require: An initial point , stepsizes , and an iteration limit .
for do
Choose .
Set .
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
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 be a closed convex function. For every iterate generated by Algorithm 1, we have
If, in addition, satisfies the -Hölder growth condition (3), then
Proof. Fix any . Since , we have . By the non-expansiveness of the projection operator, we have
Since , the subgradient inequality gives . Recalling the definition that in (4), we obtain
Taking the infimum over on both sides gives (5). If satisfies the -Hölderian condition (3), then . Substituting this bound into (5) gives (6). □
From (5) and (6), the negative term scales linearly with , while the positive term scales quadratically. Thus, whenever is nonoptimal, a sufficiently small stepsize guarantees . Building on this insight, constant stepsizes and predetermined decaying stepsizes can yield complexity guarantees for finding an iterate satisfying for functions with Hölder growth [7, 10].
Remark 1. If is globally -Lipschitz continuous, then for every iteration. Consequently, (6) reduces to , which has been widely used in existing stepsize designs [7, 10]. However, this worst-case bound does not exploit the subgradient norm 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 , the stepsize is the only remaining design choice and fully determines the resulting update. Common choices include constant stepsizes [1], diminishing stepsizes satisfying , , such as with [1, 2], and geometrically decaying stepsizes [7, 8, 10].
If the optimal value is known, minimizing the right-hand side of the squared-distance recursion (5) with respect to yields the celebrated Polyak stepsize [5]
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 satisfies the -Hölder growth condition and that the exact squared-distance error is available. Minimizing the right-hand side of (6) with respect to yields
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 is unavailable, as its computation typically requires knowledge of the solution set . Our key idea is to replace with a certified upper bound satisfying and choose the stepsize that minimizes the worst-case one-step upper bound in (6) over all . Specifically, for , define
which represents the worst-case one-step upper bound in (6) over all . We then select
which we refer to as a distance-certified Polyak-type stepsize. By construction, the value
provides an upper bound on the squared-distance error of the next iterate , namely, . We may thus choose the next certified upper bound and repeat (10) and (11). Starting from an initial bound , this generates a sequence of certified bounds satisfying for all and forms the basis of our distance-certified subgradient method.
In addition, the observed subgradient can provide a further upper bound on the squared-distance error . 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 , an initial bound , parameters , , and an iteration limit .
for do
Choose and set ;
Compute according to (11);
Compute according to (8);
Set according to (9);
Set ;
end for
Lemma 2 (Subgradient-based distance certificate). Suppose that is convex and satisfies the -Hölder growth condition (3). For any and , we have . Consequently, if , then
If and , then .
Proof. Let , so that . By the subgradient inequality and the Cauchy–Schwarz inequality, we have . Combining this inequality with (3) proves the first statement. If , (10) holds trivially. Otherwise, we have . For , rearranging and squaring this inequality establishes (10). For , it reduces to .
After observing the selected subgradient , Lemma 2 allows us to refine the upper bound from (9) by setting
By construction, we always have . 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 . Then the iterates generated by Algorithm 2 satisfy
In particular, both and are nonincreasing.
Proof. By the definition of in (8), we have
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 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 , define the inner worst-case function
where , . Then is convex and nonnegative on . Consequently, for any , is strongly convex in and admits a unique minimizer on .
Proof. For each fixed , the function is affine. Therefore, is convex as the pointwise maximum of affine functions. Moreover, since is feasible in the inner maximization, we have for all .
If , then is strongly convex. Hence, its sum with the convex function is also strongly convex. Furthermore, as . Therefore, attains its minimum on , and strong convexity guarantees that the minimizer is unique.
We will show in § 4.5 that the worst-case function is further piecewise smooth in . Figure 1 illustrates its typical shapes for and that are both strongly convex.

Figure 1. Typical worst-case upper bound functions with for (Left) and (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 is sufficiently large, the optimal stepsize will be small enough that the inner maximization attains its worst-case value at . In this case, we have , which is quadratic in . Minimizing this expression gives
which has the same form as the exact distance-based Polyak-type stepsize (8), with the unknown squared-distance error replaced by its certified upper bound . To determine when this stepsize (15) is indeed optimal, it is convenient to introduce the following normalized quantity
which measures the size of the observed subgradient relative to the growth parameters and the current distance certificate. For , the certificate update (13) immediately implies . For , the same inequality follows from Lemma 2 whenever is nonoptimal.
The threshold on that determines whether in (15) is optimal to (10) depends on the curvature of the function , . Since this curvature changes at , we consider the regimes and separately. For , the function is convex in , so its maximum over 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 ). Suppose that , and consider a nonoptimal iterate with . Then the distance-certified stepsize in (10) is unique, and the corresponding update has the following two cases.
If then
If , then
When , the function , , is concave in , and the inner maximization may attain its maximum either at the endpoint or at an interior point. This leads to the following explicit distance-certified updates.
Proposition 3 (Explicit DC-SG update for ). Suppose that , and consider a nonoptimal iterate with . Then the distance-certified stepsize in (10) is unique, and the corresponding update has the following two cases.
If , then
If then
Propositions 2 and 3 show that, when in (16) is sufficiently large, both (17) and (19) reduce to the common Polyak-type stepsize (15). When is smaller, however, the optimal stepsize depends on the growth exponent , 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 exponent | Regime | Stepsize | Certificate ratio |
Table 1. Table 1: Explicit distance-certified stepsizes and certificate updates. Here, . The two sets of updates coincide when .
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 . Since is convex on , its maximum is attained at an endpoint. Therefore, the inner maximization (12) becomes . Define the breakpoint stepsize , at which . It follows that the worst-case one-step upper bound has two branches
The unconstrained minimizer of the first branch is . As expected, this coincides with the Polyak-type stepsize (13). The second branch is strictly increasing. Consequently, the unique minimizer is . It is easy to verify that . Thus, when , the unconstrained minimizer lies in and is therefore the optimal stepsize. When , the minimum is attained at the breakpoint . Substituting the corresponding stepsizes into gives (15a) and (15b).
Proof of Proposition 3. Consider . In this case, the function is concave on . Its derivative with respect to is . Define the breakpoint stepsize . If , the inner maximum is attained at . If , an interior maximizer is given by . Using the identity , we obtain
Therefore, the worst-case one-step upper bound also has two branches:
The unconstrained minimizer of the first branch is , which again coincides with the Polyak-type stepsize (15). Moreover, we have . Thus, when , the unconstrained minimizer lies in and is thus the optimal stepsize.
The unconstrained minimizer of the second branch is . A direct calculation gives . Hence, when , we have , so lies in and is the optimal stepsize. At , both branch minimizers coincide with . Substituting the corresponding stepsizes into 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 , the first branch is the Polyak-type update (15a) and (16a). This stepsize is selected when is sufficiently large, namely, when for and when for . The complementary branch depends on the curvature of . For , this function is convex in , and its maximum over is attained at an endpoint. When , the optimal stepsize is capped at the breakpoint , leading to (15b). We refer to this update as the capped branch. For , the function is concave, and the inner maximum may be attained at an interior stationary point. When , this gives (16b). We refer to this update as the interior-maximizer branch. Figure 2 illustrates these four different minimizer regimes in Table 2.
Table 2. Summary of the two branches in the explicit DC-SG updates; is defined in (16).

Figure 2. The four minimizer regimes in Table 2. Each panel plots against the stepsize where and . Solid curves show the valid branches; dashed curves extend their formulas outside the valid intervals. Filled dots mark the certified minimizers ; open circles mark the breakpoints . The symbols and 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 -Lipschitz continuity
Suppose that is globally -Lipschitz continuous. Then every subgradient satisfies . For convenience, define
Based on Propositions 2 and 3, the following result provides a unified one-step decrease for all .
Lemma 4 (One-step certificate decrease). Let be convex and globally -Lipschitz continuous. Suppose that satisfies the -Hölder growth (3). For each iteration of DC-SG, we have
Proof. Suppose that , i.e., the Polyak branch is active. By Propositions 2 and 3, its propagated certificate satisfies . Using gives
Suppose that , i.e., the complementary branch is active. When , the capped update (15b) satisfies . When , the interior-maximizer update (16b) satisfies . Since , both cases imply
Therefore, regardless of the value of , combining (19) with (20) leads to
By construction (11), the certificate update guarantees , the bound (18) follows. □
The recursion (18) directly yields global convergence of the certificate sequence . We first consider the case . Throughout this section, define the threshold
at which we have . 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 ). Let be convex and globally -Lipschitz continuous. Suppose that satisfies the -Hölder growth (3) with . Define in (21).
If , then, for every ,
If , define . Then , and, for every ,
Proof. Suppose first that . Since the certificate sequence is nonincreasing, for all . Hence, we have , and (18) reduces to
If for some , (22a) follows immediately from monotonicity. Otherwise, applying Bernoulli’s inequality gives
Iterating this inequality from 0 to yields (22a).
Suppose next that . Then we have , and hence (18) reduces to . Therefore, the certificate either enters the local region before or satisfies
Applying (22a) from iteration and using proves (22b).
Theorem 1 immediately yields the following iteration complexity.
Corollary 1 (Iteration complexity for ). Under the setting of Theorem 1, let . DC-SG in Algorithm 2 obtains an iterate satisfying within iterations. More precisely, the following statements hold.
if , then whenever .
if and , then whenever .
When , (18) immediately gives linear convergence. We present the guarantee below.
Theorem 2 (Linear convergence for ). Let be convex and globally -Lipschitz continuous. Suppose that satisfies the -Hölder growth (3) with . Define . Then, for every ,
Consequently, for every , we have whenever
Proof. When , we have by definition (21). Thus, (22) becomes
Iterating this inequality proves (28). The complexity bound follows by solving . □
The case 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 [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 satisfy the following upper bound
for some and . When , it reduces to the globally Lipschitz case. Note that it is necessary to have since the Hölder growth condition and the subgradient inequality imply 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 is convex and satisfies the -Hölder growth condition and that (30) holds. Let and . Then every DC-SG iteration in Algorithm 2 satisfies
Consequently, the following statements hold.
If , then we have , and the iteration complexity for obtaining is .
If , define . Then we have linear convergence .
Proof. Since , (30) gives . Thus, on the Polyak-type branch, we have
The complementary branch continues to decrease the certificate by at least , similar to (24). Thus, (22) reduces to (31).
If , applying the argument of Theorem 1 with replaced by establish the claimed result. If , then (31) reduces to . This finishes the proof. □
Whenever , DC-SG achieves a strictly faster convergence rate and thus automatically adapts to shrinking subgradient norms. In particular, when and , DC-SG converges linearly without requiring the sharp-growth condition. For example, the function with , satisfies the condition (25) with , 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 and do not replace it by the global upper bound ; see also Remark 1. For example, the classical Polyak stepsize (6a) satisfies
where the last inequality uses (25). Thus, the Polyak stepsize enjoys the same refined polynomial exponent when and linear convergence when , 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 . In contrast, standard stagewise and geometrically decaying stepsize schemes [7, 8, 9, 10] use the global constant 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 guarantees for a suitable averaged iterate . Combining this bound with the Hölder growth (3) gives . By contrast, Theorems 1 and 2 establish the last-iterate guarantee
when , and linear convergence when . Thus, DC-SG strictly improves the polynomial exponent for every and achieves a linear rate in the sharp-growth case. Moreover, these guarantees hold directly for the last iterate 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 , and our DC-SG uses the growth parameters and an initial certificate . 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 -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 , 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, , and their methods attain the rate in (33) when and linear convergence when . 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 and the observed subgradient norm . 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 allows DC-SG to achieve the refined rates in Corollary 2 when the selected subgradients diminish near . 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.
Table 3. Problem information and stepsize schedules. Here, is the optimal value, and are the Hölder growth parameters, is a uniform bound on the subgradient norms, and 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 , , and , and adapts its stepsize to the observed subgradient norm without requiring or . The Polyak method requires the exact optimal value and serves as a baseline. For comparison, RSG, DS-SG, and DecayGD use , , , and to determine their schedules. RSG and DS-SG employ stagewise schedules, whereas DecayGD uses a predetermined decaying sequence. We include DS-SG only when , 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:
where and . We construct , where and are random orthogonal matrices and the singular values are logarithmically spaced between and . Thus, and . We choose such that . By construction, is nonsingular, and thus the solution set is and the optimal value is .
The objective in (34) satisfies the Hölder growth condition (3) with , where denotes the th standard basis vector. We use the subgradient
with . This oracle satisfies the shrinking-subgradient condition (30) with . A uniform subgradient bound on is . All methods are initialized at , and we use the initial squared-distance bound . This bound is conservative, since . We run each method for subgradient evaluations.
The numerical results are shown in Figure 3, which are consistent with the theoretical guarantees. In all three cases, the certificate satisfies throughout the iterations of DC–SG and decreases geometrically. For , this behavior agrees with Theorem 2; for , it agrees with Corollary 2 under the shrinking condition . 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 converges fastest among all methods. Our DC–SG also exhibits linear convergence for all three values of and maintains a valid distance certificate without using . 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 . This comparison clearly shows the benefit of using the observed subgradient norm in the stepsize selection.
Figure 3. Figure 3: Problem (29) with : Normalized squared distance versus the number of subgradient evaluations for DC–SG (Algorithm 2), Polyak method, DS–SG, RSG, and DecayGD, where . The black dashed curve shows the normalized DC–SG certificate .
Regularized support vector machines
We next consider an -regularized support vector machine with hinge loss:
where and . We use the Wisconsin Diagnostic Breast Cancer dataset [28], which contains 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 -strongly convex and has a unique minimizer . Moreover, , so . Consequently, the Hölder growth condition (3) holds with and . We use the subgradient . The selected subgradients need not vanish as approaches . Applying Theorem 1 with yields 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 , and we use the initial squared-distance bound . We run each method for iterations.
The numerical results are shown in Figure 4. The distance certificate from DC-SG exhibits an approximately rate over the later iterations. This behavior is consistent with Theorem 1 for . 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 , its normalized squared distance is , while those of the other methods range from to . 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 : normalized squared distance versus the number of subgradient evaluations, where . We compare DC-SG, the Polyak method, DS-SG, RSG, and DecayGD. The black dashed curve shows the normalized DC-SG certificate .
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 and linear convergence for , together with sharper rates under shrinking subgradients, including linear convergence when . 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]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]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, UK, 2004. doi: 10.1017/CBO9780511804441.DOI
- [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]Naum Z. Shor. The rate of convergence of the generalized gradient descent method. Cybernetics, 4(3):79–80, 1968. doi: 10.1007/BF01073933.
- [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]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]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]Jean-Louis Goffin. On convergence rates of subgradient optimization methods. Mathematical Programming, 13(1):329–347, 1977.DOI
- [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]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]Damek Davis, Dmitriy Drusvyatskiy, and Liwei Jiang. Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth. Mathematical Programming, 2025.
- [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]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]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]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]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]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]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]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]Vincent Roulet and Alexandre d’Aspremont. Sharpness, restart, and acceleration. SIAM Journal on Optimization, 30(1):262–289, 2020. doi: 10.1137/18M1224568.
- [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]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]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]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]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]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]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]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]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

