Pith. sign in

REVIEW 4 major objections 3 minor 1 cited by

Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization I: Convex Optimization

T0 review · 4 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims a new accelerated method solves convex piecewise-smooth minimization under quadratic growth in the optimal number of gradient evaluations, about k·√(L/µ)·log(1/ε), matching a new lower bound, without knowing the pieces, th

desk verdict The APEX framework and certificate construction are genuinely new, but the optimal-rate theorem leans on an unproved O(L) empirical-smoothness bound that the paper's own Example 1.1 undercuts; needs repair before the headline claim is credible. read the letter →

arxiv 2601.14680 v3 pith:5YL3S6GY submitted 2026-01-21 math.OC

Zhenwei Lin , Zhe Zhang This is my paper
classification math.OC MSC 90C2590C6065K05
keywords convexoptimizationpiecewise-smoothfunctionsbundle-levelmethodsacceleratedfirst-orderquadraticgrowthoraclecomplexitylowerboundsterminationcertificates
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to close a known divide in convex optimization: smooth strongly convex problems admit linear convergence, nonsmooth problems generically do not, and piecewise-smooth problems sit in between. For convex functions that are smooth on a finite, unknown collection of pieces and satisfy quadratic growth near the minimizer, it proposes APEX, an accelerated bundle-level method, and claims the number of gradient evaluations needed is at most order k·√(L/µ)·log(1/ε) — where k is the number of pieces, L the per-piece smoothness constant, and µ the growth modulus — improving prior bundle-level guarantees by roughly a factor of k·√(L/µ) and matching a new lower bound the paper proves for every deterministic first-order method. It further claims a termination certificate accurate to a constant factor (prior certificates were off by a factor of L/µ), which it converts into a restarted, nearly parameter-free variant needing neither the optimal value nor the curvature constant as input. A sympathetic reader should care because, if these claims hold, unknown piecewise structure costs exactly a factor of k in iteration count rather than a return to generic nonsmooth rates, and the certificate makes the guarantee verifiable in practice.

What carries the argument

The load-bearing object is the One-Step inner loop: each outer iteration fixes the accelerated point and weight α_t while running m projections onto level sets cut by supporting planes, letting the three-point lemma apply to arbitrary inner pairs rather than adjacent iterates. The per-iteration smoothness surrogate L_t is the smallest ratio of residual decrease to squared distance over inner pairs; all guarantees flow through its weighted harmonic mean L̄(N), and the claim L̄(N) = O(1)L once m reaches the piece count k produces the advertised rate. The W-certificate — a point set in a radius-ι ball whose piecewise-linear surrogate drops at most ν per unit radius — certifies f(ȳ)−f* ≤ max{ιν,

What would settle it

Take a two-piece convex function with quadratic growth whose minimizer lies on the piece boundary, run APEX's exact iterate rule with m = 2 cuts, and compute the harmonic-mean smoothness constant L̄(N) plus the empirical iteration count to reach ε-accuracy. If L̄(N) is not O(1)L, or the count degrades toward the unaccelerated k²L/µ scaling, the central optimality claim collapses. The paper's Example 1.1 shows exactly such L-spikes for a naive step-size rule on a two-piece objective; the decisive check is whether APEX's own inner geometry — comparing non-adjacent pairs with m = k cuts — keeps t

Watch

Extended reading notes

Core claim

The central discovery is that acceleration and piecewise-structure exploitation are compatible: APEX holds the accelerated averaging point fixed while running m inner level-set projections from a fixed reference point, so the analysis telescopes across non-adjacent inner iterates. With at least as many cutting planes as pieces, the effective smoothness constant — a weighted harmonic mean of residual-decrease-to-squared-distance ratios among inner pairs — is asserted to stay O(1)·L, giving the optimal rate O(k√(L/µ)·log(1/ε)). A hard instance of k decoupled chain quadratics establishes the matching lower bound Ω(k√(L/µ)·log(1/ε)) for deterministic first-order methods, and an O(1)-accurate W-c

Load-bearing premise

The entire optimal-rate argument depends on one premise: that keeping at least as many cutting planes as the function has smooth pieces keeps the local smoothness estimates the algorithm relies on bounded by the true smoothness constant — a property the paper's own example shows is not automatic when iterates cross piece boundaries.

Editorial extensions

If this is right

  • The oracle count for convex piecewise-smooth optimization under quadratic growth drops from order k²L/µ to order k√(L/µ)·log(1/ε): the same speed-up over unaccelerated bundle-level methods that momentum provides in the fully smooth case.
  • The matching lower bound shows no deterministic first-order method can do better, so APEX and its restarted variants are optimal up to constant factors for this problem class.
  • Termination becomes certifiable: the W-certificate bounds the true optimality gap to a constant factor, so users can stop early with a printed accuracy guarantee instead of trusting gradient norms, which are unreliable near nonsmooth boundaries.
  • The near-parameter-free variant needs no optimal value and no curvature constant — only a cut count reaching the piece count — and its complexity pays only a log-log penalty for guessing the curvature, making the optimal rate attainable on quadratic model-predictive control, two-stage stochastic linear programming, and ReLU-network objectives.
  • In the paper's experiments on maxima of quadratics and two-stage stochastic linear programs, the method used far fewer gradient evaluations than the comparison methods in nearly all tested regimes, with the advantage widening as the required accuracy tightened.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The fixed-outer-point, multi-cut inner loop is a transferable template: any setting where adjacent-iterate smoothness estimates are unreliable — stochastic gradients, inexact oracles, thin exceptional sets — could receive the same harmonic-mean treatment; the paper develops it only for deterministic piecewise-smooth objectives.
  • The matching lower bound makes the price of not knowing the partition precise: a factor of k in the iteration count. This invites testable heuristics that learn pieces online, since the paper's own experiments hint that far fewer than k cuts often suffice.
  • The certificate-transfer lemma implies W-certificates can be carried cheaply along short trajectories rather than rebuilt, which suggests warm-started, stochastic, or incremental variants where certificates are re-verified near previous certified points.
  • Because the observed rate tracks pieces actually visited rather than the total piece count, a refined theory in terms of trajectory-local piece complexity looks within reach; the paper notes the sufficient condition but does not formulate such a bound.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper proposes APEX, an accelerated bundle-level method for minimizing convex (k,L)-piecewise-smooth functions under a quadratic-growth condition, when the locations of the smooth pieces are unknown. The advertised contribution is an O(k sqrt(L/mu*) log(1/eps)) oracle complexity for reaching an eps-optimal solution, a matching lower bound, a constant-factor-accurate W-certificate, and an almost parameter-free restarted variant (rAPEX). The algorithm maintains m cutting planes per outer loop, uses a level-based projection subproblem, and defines an empirical quantity Lbar(N) in (3.2) that is later asserted to be O(L) when m>=k. Sections 4-6 develop certificate generation and the restart/guess-and-check machinery. Section 7 constructs a max-of-k quadratics lower-bound instance. The numerical section reports comparisons on MAXQUAD and two-stage stochastic programming examples. The main theorems are Theorem 5.1, Theorem 6.1, and Theorem 6.2, which state the optimal-rate claims.

Significance. If the rate claims were fully established, this would be a substantial advance: it would improve the condition-number dependence from the O(k^2 L/mu*) of the bundle-level method in [74] to O(k sqrt(L/mu*)), and it would provide a verifiable certificate and a parameter-free restart scheme for an important structured nonsmooth class. The lower bound in Section 7 is a useful contribution and the numerical results are encouraging. The paper also contains several inventive components: the W-certificate transfer lemma (Lemma 6.1), the adaptive QG-estimate quartering in Algorithm 6, and the double-loop acceleration design. However, the central optimality claim is not supported by the proof as written, because the step that converts the run-dependent quantity Lbar(N) into the true problem constant L is asserted rather than proved, and the paper's own Example 1.1 indicates that boundary crossings can make similar empirical quantities unbounded.

major comments (4)
  1. [Section 3, Eq. (3.11) and the remark after Proposition 3.2] The claim that, for (k,L)-PWS with m>=k, 'one again obtains \bar L(N)=O(1)L' is the only bridge from the algorithm-defined empirical quantities to the advertised complexity, but it is not proved. Inequality (3.11) requires a quadratic upper bound on f(\bar x_{t,r_t}) linearized at x_{t,l_t+1}. Since \bar x_{t,r_t}=(1-\alpha_t)\hat x_{t-1}+\alpha_t x_{t,r_t}, this point can lie in a different smooth piece even when x_{t,l_t+1} and x_{t,r_t} lie in the same piece. The condition m>=k gives a pigeonhole statement about the m+1 inner iterates, not about the specific pair chosen in Line 13, and Example 1.1 demonstrates that boundary crossings can make empirical Lipschitz ratios arbitrarily large. Consequently Theorem 5.1 Part 3 and Theorems 6.1-6.2 do not follow from the supplied proof; the claimed matching to the lower bound is unsupported. A proof of (3.11) with an absolute constant, valid f
  2. [Section 3, Eq. (3.2); Section 5, Theorem 5.1 Part 2] The quantities \bar L(N) and L_avg are defined from the actual function-value decreases f(\hat x_t)-\tilde l and distances ||x_{t,r_t}-x_{t,l_t}|| of the run. A rate of the form O(m sqrt(L_avg/mu*) log(1/eps)) is therefore an a posteriori bound, not a worst-case oracle complexity guarantee. The abstract's statements about an 'optimal theoretical guarantee' and a 'tight oracle complexity bound' become meaningful only after an external uniform upper bound on these empirical quantities is supplied. In the current text, the only such bound is the unproved assertion discussed above. The authors should state explicitly which theorems are problem-class worst-case guarantees and which are run-dependent bounds.
  3. [Section 5, Algorithm 4, line 1] The initialization Delta_0 = ||f'(\bar y_0)||^2/(2mu*) is not a valid upper bound on f(\bar y_0)-f* for the general convex mu*-QG function class considered in the paper. The derivation in Lemma 6.3 (Eq. (6.3) onward) yields f(y)-f* <= 2||f'(y)||^2/mu, i.e. an initial gap four times larger than the one used in Algorithm 4. With the stated value, the lower bound f_0 = \bar f_0 - Delta_0 can exceed f*, breaking the invariant f_s <= f* that is used in the proof of Theorem 5.1. This is a constant-factor issue in the logarithmic term but it is nevertheless load-bearing for correctness; it should be fixed by using Delta_0 = 2||f'(\bar y_0)||^2/mu* (or a valid alternative bound).
  4. [Section 7, Proposition 7.2, Eq. (7.10)] The lower-bound proof treats each gradient evaluation as expanding support within a single block, and then splits the t iterations among k blocks. For the hard instance (7.6), however, the subdifferential at points where several components are active (in particular at x=0) contains convex combinations with support in all k blocks. If the first-order oracle returns such a full-support subgradient, the support argument leading to (7.10) fails and the serial t/k decay does not follow. The proof does not specify the subgradient selection rule at ties. The lower bound may be repairable by choosing an adversarial oracle response, but as written it is incomplete.
minor comments (3)
  1. [Section 3, Eq. (3.12)] The display for the upper bound on \bar L(N) is malformed: the term '(\alpha_t \cdot \tilde L_t)' appears after a fraction and its meaning as a weighted average or harmonic mean is unclear. Please rewrite the bound with explicit sums or an operator such as a weighted mean.
  2. [Algorithm 1, lines 1 and 11] The initialization x_{t+1,0}=x_{t,0} is immediately overwritten by x_{t+1,0}=x_{t,i} at Line 11. The line is confusing and should be removed or restricted to t=0.
  3. [Example 1.1] The domain is written as [-M,+\infty], which suggests a closed endpoint at +infinity. It should be [-M,+\infty) with a real finite upper end, or the statement should say 'bounded below by -M'.

Circularity Check

2 steps flagged · score 6.0 of 10

Optimal-rate claim reduces to an asserted L_avg=O(L) bound that restates the theorem's conclusion; the core convergence bound is definitional in the run's own ratios.

  1. self definitional [Section 3, Algorithm 1 Line 13; Eq. (3.2)-(3.3), Proposition 3.1]
    "Let Lt = min 0≤l<r≤m Lt(r, l) and ¯L(N) = PN t=1 ωtα2 t Lt1E(t) ||xt,rt −x t,lt||2 /2 PN t=1 1E(t) ||xt,rt −x t,lt||2 ,(3.2) ... There exists a constant ¯L(t)(defined in(3.2)) such that ωt [f(ˆxt)− ˜l] −ω1(1− α1/2)[f(ˆx0)− ˜l] ≤ ¯L(t)||xt −¯y||2 .(3.3)"

    L_t is defined, in Algorithm 1 Line 13, as the ratio of the observed residual decrease to α_t^2/2 times squared distance between two inner iterates; \bar L(N) is then the weighted average of these same ratios. Therefore inequality (3.3) is an algebraic identity that merely records the run's own progress: it cannot by itself yield an O(L) rate. Any advertised complexity in terms of \bar L(N) is meaningful only if an independent external bound \bar L(N)=O(L) is proved, which is exactly what is later asserted rather than derived.

  2. fitted input called prediction [Section 3, remark after Proposition 3.2; Theorem 5.1 Part 3 proof]
    "More generally, when f is (k, L)-PWS with at most k smooth segments and one maintains m≥k cuts per outer iteration, one again obtains ¯L(N) = O(1)L throughout. ... If function f is (k, L)-PWS function with k≤m, then we have L t ≤ L. Hence, ¯L(¯t) = O(1)L."

    This is the load-bearing step for the advertised O(k sqrt(L/μ*)) complexity. The theorem's conclusion 'L_avg = O(1)L' is the same statement as the remark's 'one again obtains \bar L(N)=O(1)L', and the proof of Theorem 5.1 Part 3 simply restates it as 'we have L_t ≤ L'. The underlying hypothesis (3.11) is assumed for a pair \bar x_{t,r_t}, x_{t,l_t+1} that need not lie in one smooth piece; Example 1.1 shows crossings between pieces can make empirical ratios arbitrarily large. Thus the optimal-rate result is the input assertion restated, not a consequence derived from the (k,L)-PWS definition.

full rationale

Proposition 3.1's bound is definitional: L_t is chosen as the minimal ratio of the observed residual decrease to squared distance, so \bar L(N) is the run's own average progress ratio. A rate in terms of L_avg is therefore legitimate only if an external L_t=O(L) bound is established. The paper asserts this bound in the remark after Proposition 3.2 for m≥k, and Theorem 5.1 Part 3 repeats the assertion ('then we have L_t ≤ L') to conclude L_avg=O(1)L; Theorem 6.1 then inherits it. Since (3.11) is not proved for iterates that may cross nonsmooth boundaries, and the paper's own Example 1.1 shows such crossings can spike empirical Lipschitz ratios, the advertised O(k sqrt(L/μ*) log(1/ε)) rate matching the lower bound reduces to the fitted assertion L_avg=O(L). This is a partial, but central, circularity. The W-certificate and lower-bound constructions are otherwise self-contained and not circular; I found no load-bearing self-citation beyond the normal use of prior work [74]. Separately, but not circularly, Algorithm 4's initial gap Δ0=||f'(y0)||^2/(2μ*) is a factor 4 smaller than the bound 2||f'(y0)||^2/μ* derived in Lemma 6.3, which can make the initial lower bound exceed f*; this is a correctness issue, not a circularity.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

No new physical or mathematical entities are postulated. The burden of the paper is carried by the assumption that empirical smoothness ratios L_t are controlled by the true piecewise smoothness L when m >= k, and by the initial-gap estimate in Algorithm 4. The free algorithmic parameters m, hat_mu_1, theta, and beta are not fitted to data but are necessary for the stated guarantees.

free parameters (4)
  • bundle size m
    User-chosen number of cutting planes. Theorems 6.1 and 6.2 require m >= k for the O(L) smoothness link; complexity scales linearly with m, so the advertised 'optimal' rate only matches the lower bound when m = O(k).
  • initial QG estimate hat_mu_1
    Algorithm 6 requires hat_mu_1 >= mu* for the stated complexity in Theorem 6.1; if it is too small, the algorithm does not quarter and the bound changes to the hat_mu_1-dependent rate of Theorem 5.1.
  • shrink factor theta
    Chosen in (1/2,1) for rAPEX; it controls restart thresholds and appears in constants and log bases but not in the asymptotic rate.
  • extra factor beta
    User-chosen positive constant in the AWG certificate procedure; affects constants in the oracle-call bounds.
assumptions (4)
  • domain assumption The objective f is convex, (k,L)-piecewise smooth, and satisfies mu*-quadratic growth.
    The entire problem class is defined by Definitions 1 and 2; all theorems are conditional on this assumption.
  • ad hoc to paper When m >= k, the empirical Lipschitz ratios L_t (and L_avg) are O(L); formally, inequality (3.11) holds with tilde_L_t = O(L).
    This is asserted in the remark after Proposition 3.2 and used in Theorem 5.1 Part 3. It is not derived from the PWS definition and is contradicted in spirit by Example 1.1, where crossing a piece boundary makes empirical smoothness spike.
  • ad hoc to paper The initial gap f(y0)-f* is at most ||f'(y0)||^2/(2mu*) in Algorithm 4.
    Algorithm 4 initializes Δ0 this way and calls f0 = f(y0)-Δ0 a lower bound on f*. The standard QG inequality used later in Lemma 6.3 is f(y)-f* <= 2||f'(y)||^2/mu, four times larger, so the initialization is not justified for general QG functions.
  • standard math First-order deterministic methods can be reduced to zero-respecting algorithms via the orthogonal-connection argument of Carmon, Duchi, Hinder, and Sidford.
    Proposition 7.1 and its proof follow the known two-stage lower-bound framework; the paper adapts it to the PWS function class.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization I: Convex Optimization." pith.science (2026). https://pith.science/paper/5YL3S6GY

@misc{pith2026260114680,
  author       = {Pith},
  title        = {Pith review of: Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization I: Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5YL3S6GY}},
  note         = {Machine review of arXiv:2601.14680}
}
read the original abstract

We introduce a nearly parameter-free algorithm for minimizing piecewise smooth (PWS) convex functions under the quadratic-growth (QG) condition, where the locations and structure of the smooth regions are entirely unknown. Our algorithm, APEX (Accelerated Prox-Level method for Exploring Piecewise Smoothness), is an accelerated bundle-level method designed to adaptively exploit the underlying PWS structure. For this setting, APEX achieves the best-known oracle-complexity result among existing first-order methods, improving the dependence on the condition number relative to prior bundle-level guarantees. Furthermore, APEX generates a verifiable and accurate termination certificate, enabling a robust, nearly parameter-free implementation. To the best of our knowledge, APEX is the first algorithm to simultaneously achieve the best-known first-order oracle complexity for PWS optimization and provide certificate guarantees.

Figures

Figures reproduced from arXiv: 2601.14680 by the authors.

Figure 1
Figure 1. Convergence comparison between BL, APL, and Restarted APL on a randomly gen￾erated MAXQUAD problem. 10000 20000 30000 40000 50000 Iterations 10 3 10 2 10 1 10 0 10 1 Empirical L Worst Case L = 10.2341 Average L [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 4
Figure 4. Trajectory comparison of Polyak step size [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Absolute error of upper bound and lower bound of rAPEX v.s. Iteration on MAXQUAD with k = 50, L = 10 in [PITH_FULL_IMAGE:figures/full_fig_p028_5.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal Parameter-Free First-Order Methods for Convex Optimization with Unknown Growth and Smoothness

    math.OC 2026-07 accept novelty 7.5 of 10

    Affine W-certificate bundle-level methods (BLW/A-BLW) attain optimal parameter-free rates under unknown Hölder smoothness and growth for convex first-order optimization.

Reference graph

Works this paper leans on

74 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [74]

    zt =U ⊤at

    Z. Zhang and S. Sra. Linearly convergent algorithms for nonsmooth problems with unknown smooth pieces. arXiv preprint arXiv:2507.19465, 2025. 35 Appendix A Proof of Proposition 7.1 We first give some basic notations and definitions for the proof of Proposition 7.1. Since these notations and definitions are only used for lower complexity proof, we define i...

    arXiv 2025

  2. [1]

    Bagirov, N

    A. Bagirov, N. Karmitsa, and M. M. M¨ akel¨ a. Introduction to Nonsmooth Optimization: theory, practice and software, volume 12. Springer, 2014

    2014

  3. [2]

    A. Beck. First-order methods in optimization. SIAM, 2017

    2017

  4. [3]

    Beck and M

    A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse prob- lems. SIAM Journal on Imaging Sciences, 2(1):183–202, 2009

    2009

  5. [4]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001

    2001

  6. [5]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski. Non-Euclidean restricted memory level method for large-scale convex optimization. Mathematical Programming, 102(3):407–456, 2005

    2005

  7. [6]

    B¨ ohm and S

    A. B¨ ohm and S. J. Wright. Variable smoothing for weakly convex composite functions. Journal of optimization theory and applications, 188(3):628–649, 2021

    2021

  8. [7]

    Bro and S

    R. Bro and S. De Jong. A fast non-negativity-constrained least squares algorithm. Journal of Chemometrics: A Journal of the Chemometrics Society, 11(5):393–401, 1997

    1997

Show all 74 references
  1. [8]

    J. V. Burke, A. S. Lewis, and M. L. Overton. Approximating subdifferentials by random sampling of gradients. Mathematics of Operations Research, 27(3):567–584, 2002

    2002

  2. [9]

    J. V. Burke, A. S. Lewis, and M. L. Overton. A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM Journal on Optimization, 15(3):751–779, 2005

    2005

  3. [10]

    J. V. Burke, F. E. Curtis, A. S. Lewis, M. L. Overton, and L. E. Sim˜ oes. Gradient sampling methods for nonsmooth optimization. Numerical nonsmooth optimization: State of the art algorithms, pages 201–225, 2020

    2020

  4. [11]

    Carmon, J

    Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184(1):71–120, 2020

    2020

  5. [12]

    Carmon, J

    Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points II: first-order methods. Mathematical Programming, 185(1):315–355, 2021

    2021

  6. [13]

    Carmon, A

    Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Thinking inside the ball: Near-optimal mini- mization of the maximal loss. In Conference on Learning Theory, pages 866–882. PMLR, 2021

    2021

  7. [14]

    X. Chen. Smoothing methods for nonsmooth, nonconvex minimization. Mathematical Programming, 134(1):71–99, 2012

    2012

  8. [15]

    C. D. Dang, G. Lan, and Z. Wen. Linearly convergent first-order algorithms for semidefinite pro- gramming. Journal of Computational Mathematics, pages 452–468, 2017

    2017

  9. [16]

    G. B. Dantzig. Linear programming under uncertainty. Management science, 1(3-4):197–206, 1955

    1955

  10. [17]

    Davis and D

    D. Davis and D. Drusvyatskiy. Stochastic subgradient method converges at the rateo(k −1/4) on weakly convex functions, 2018. URLhttps://arxiv.org/abs/1802.02988

    2018 arXiv

  11. [18]

    Davis and D

    D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207–239, 2019

    2019

  12. [19]

    Davis and L

    D. Davis and L. Jiang. A local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth. Foundations of Computational Mathematics, pages 1–82, 2024

    2024

  13. [20]

    Davis, D

    D. Davis, D. Drusvyatskiy, Y. T. Lee, S. Padmanabhan, and G. Ye. A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions. Advances in Neural Information Processing Systems, 35:6692–6703, 2022

    2022

  14. [21]

    de Oliveira

    W. de Oliveira. Proximal bundle methods for nonsmooth DC programming. Journal of Global Optimization, 75(2):523–563, 2019. 32

    2019

  15. [22]

    de Oliveira and C

    W. de Oliveira and C. Sagastiz´ abal. Level bundle methods for oracles with on-demand accuracy. Optimization Methods and Software, 29(6):1180–1209, 2014

    2014

  16. [23]

    de Oliveira, C

    W. de Oliveira, C. Sagastiz´ abal, and C. Lemar´ echal. Convex proximal bundle methods in depth: a unified analysis for inexact oracles. Mathematical Programming, 148(1):241–277, 2014

    2014

  17. [24]

    Q. Deng, G. Lan, and Z. Lin. Uniformly optimal and parameter-free first-order methods for convex and function-constrained optimization. arXiv preprint arXiv:2412.06319, 2024

    2024 arXiv

  18. [25]

    Devanathan and S

    N. Devanathan and S. Boyd. Polyak minorant method for convex optimization. Journal of Optimization Theory and Applications, pages 1–20, 2024

    2024

  19. [26]

    D´iaz and B

    M. D´iaz and B. Grimmer. Optimal convergence rates for the proximal bundle method. SIAM Journal on Optimization, 33(2):424–454, 2023

    2023

  20. [27]

    Drusvyatskiy and A

    D. Drusvyatskiy and A. S. Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of operations research, 43(3):919–948, 2018

    2018

  21. [28]

    Drusvyatskiy and C

    D. Drusvyatskiy and C. Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178(1):503–558, 2019

    2019

  22. [29]

    Du and A

    Y. Du and A. Ruszczy´ nski. Rate of convergence of the bundle method. Journal of Optimization Theory and Applications, 173(3):908–922, 2017

    2017

  23. [30]

    J. C. Duchi, P. L. Bartlett, and M. J. Wainwright. Randomized smoothing for stochastic optimiza- tion. SIAM Journal on Optimization, 22(2):674–701, 2012

    2012

  24. [31]

    A. A. Goldstein. Optimization of Lipschitz continuous functions. Mathematical Programming, 13: 14–22, 1977

    1977

  25. [32]

    Gurobi Optimizer Reference Manual, 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URLhttps://www.gurobi. com

    2024

  26. [33]

    X. Y. Han and A. S. Lewis. Survey descent: A multipoint generalization of gradient descent for nonsmooth optimization. SIAM Journal on Optimization, 33(1). doi: 10.1137/21M1468450. URL https://par.nsf.gov/biblio/10410938

  27. [34]

    Hare and C

    W. Hare and C. Sagastiz´ abal. A redistributed proximal bundle method for nonconvex optimization. SIAM Journal on Optimization, 20(5):2442–2473, 2010

    2010

  28. [35]

    J. E. Kelley, Jr. The cutting-plane method for solving convex programs. Journal of the society for Industrial and Applied Mathematics, 8(4):703–712, 1960

    1960

  29. [36]

    Kim and H

    J. Kim and H. Park. Fast nonnegative matrix factorization: An active-set-like method and compar- isons. SIAM Journal on Scientific Computing, 33(6):3261–3281, 2011

    2011

  30. [37]

    K. Kim, W. Zhang, H. Nakao, and M. Schanen. BundleMethod.jl: Implementation of Bundle Methods in Julia, Mar. 2021. URLhttps://doi.org/10.5281/zenodo.4574897

    2021 doi

  31. [38]

    K. C. Kiwiel. Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. Mathematical Programming, 69(1):89–109, 1995

    1995

  32. [39]

    K. C. Kiwiel. Efficiency of proximal bundle methods. Journal of Optimization Theory and Applications, 104(3):589–603, 2000

    2000

  33. [40]

    Kong and A

    S. Kong and A. S. Lewis. Lipschitz minimization and the Goldstein modulus. Mathematical Programming, pages 1–30, 2025

    2025

  34. [41]

    Kornowski and O

    G. Kornowski and O. Shamir. Oracle complexity in nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 34:324–334, 2021

    2021

  35. [42]

    Kouvaritakis and M

    B. Kouvaritakis and M. Cannon. Model predictive control. Switzerland: Springer International Publishing, 38(13-56):7, 2016. 33

    2016

  36. [43]

    G. Lan. Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimiza- tion. Mathematical Programming, 149(1):1–45, 2015

    2015

  37. [44]

    G. Lan. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020

    2020

  38. [45]

    G. Lan, Y. Ouyang, and Z. Zhang. Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization. arXiv preprint arXiv:2310.12139, 2023

    2023 arXiv

  39. [46]

    C. L. Lawson and R. J. Hanson. Solving least squares problems. SIAM, 1995

    1995

  40. [47]

    Lemarechal

    C. Lemarechal. An extension of Davidon methods to non differentiable problems. InNondifferentiable optimization, pages 95–109. Springer, 2009

    2009

  41. [48]

    Lemar´ echal, A

    C. Lemar´ echal, A. Nemirovskii, and Y. Nesterov. New variants of bundle methods. Mathematical Programming, 69(1):111–147, 1995

    1995

  42. [49]

    Li and Y

    H. Li and Y. Cui. Subgradient regularization: A descent-oriented subgradient method for nonsmooth optimization, 2025. URLhttps://arxiv.org/abs/2505.07143

    2025 arXiv

  43. [50]

    Li and G

    T. Li and G. Lan. A simple uniformly optimal method without line search for convex optimization. Mathematical Programming, pages 1–38, 2025

    2025

  44. [51]

    Liang and R

    J. Liang and R. D. Monteiro. A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes. SIAM Journal on Optimization, 31(4):2955–2986, 2021

    2021

  45. [52]

    T. Lin, Z. Zheng, and M. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160–26175, 2022

    2022

  46. [53]

    Linderoth, A

    J. Linderoth, A. Shapiro, and S. Wright. The empirical behavior of sampling methods for stochastic programming. Annals of Operations Research, 142(1):215–241, 2006

    2006

  47. [54]

    R. Mifflin. An algorithm for constrained optimization with semismooth functions. Mathematics of Operations Research, 2(2):191–207, 1977

    1977

  48. [55]

    Mifflin and C

    R. Mifflin and C. Sagastiz´ abal. OnVU-theory for functions with primal-dual gradient structure. SIAM Journal on Optimization, 11(2):547–571, 2000

    2000

  49. [56]

    Mifflin and C

    R. Mifflin and C. Sagastiz´ abal. A-algorithm for convex minimization. Mathematical Programming, 104:583–608, 2005

    2005

  50. [57]

    Mifflin and C

    R. Mifflin and C. Sagastiz´ abal. A science fiction story in nonsmooth optimization originating at IIASA. this volume, 2012

    2012

  51. [58]

    J.-J. Moreau. Proximit´ e et dualit´ e dans un espace hilbertien.Bulletin de la Soci´ et´ emath´ ematique de France, 93:273–299, 1965

    1965

  52. [59]

    Nair and G

    V. Nair and G. E. Hinton. Rectified linear units improve Restricted Boltzmann Machines. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 807–814, 2010

    2010

  53. [60]

    Nemirovski, S

    A. Nemirovski, S. Onn, and U. G. Rothblum. Accuracy certificates for computational problems with convex structure. Mathematics of Operations Research, 35(1):52–78, 2010

    2010

  54. [61]

    A. S. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization. 1983

    1983

  55. [62]

    Nesterov

    Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1): 127–152, 2005

    2005

  56. [63]

    Nesterov

    Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Programming, 140(1):125–161, 2013

    2013

  57. [64]

    Nesterov

    Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013. 34

    2013

  58. [65]

    Nesterov

    Y. Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming, 152(1):381–404, 2015

    2015

  59. [66]

    W. d. Oliveira and C. Sagastiz´ abal. Bundle methods in the XXIst century: A bird’s-eye view. Pesquisa Operacional, 34(3):647–670, 2014

    2014

  60. [67]

    B. T. Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 9(3):14–29, 1969

    1969

  61. [68]

    B. T. Polyak. Introduction to optimization. 1987

    1987

  62. [69]

    Tian and A

    L. Tian and A. M.-C. So. Testing approximate stationarity concepts for piecewise affine functions. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2213–2224. SIAM, 2025

    2025

  63. [70]

    L. Tian, K. Zhou, and A. M.-C. So. On the finite-time complexity and practical computation of approximate stationarity concepts of Lipschitz functions. In International Conference on Machine Learning, pages 21360–21379. PMLR, 2022

    2022

  64. [71]

    W¨ achter and L

    A. W¨ achter and L. T. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1):25–57, 2006

    2006

  65. [72]

    Zhang, H

    J. Zhang, H. Lin, S. Jegelka, S. Sra, and A. Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Lear...

    2020

  66. [73]

    Zhang and G

    Z. Zhang and G. Lan. Solving convex smooth function constrained optimization is almost as easy as unconstrained optimization. arXiv preprint arXiv:2210.05807, 2022

    2022

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.