pith. sign in

arxiv: 2303.14896 · v3 · pith:3XWGHVT3new · submitted 2023-03-27 · 🧮 math.OC

Proximal bundle methods for hybrid weakly convex composite optimization problems

Jiaming Liang , Renato D.C. Monteiro , Honghao Zhang This is my paper

Pith reviewed 2026-05-24 09:16 UTC · model grok-4.3

classification 🧮 math.OC
keywords proximal bundle methodsweakly convex optimizationcomposite optimizationiteration complexitystationarity measurehybrid optimizationbundle methods
0
0 comments X

The pith

Proximal bundle methods establish iteration complexity for hybrid weakly convex composite optimization via a unified framework with verifiable stationarity.

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

The paper establishes iteration-complexity bounds for proximal bundle methods on hybrid weakly convex composite optimization problems. It does this in a unified way through a proximal bundle framework that encompasses multiple common bundle update schemes. The framework relies on an easily verifiable stationarity measure rather than harder-to-check conditions such as Moreau stationarity. A reader would care because the result supplies concrete convergence rates for a practical class of nonsmooth optimization problems.

Core claim

The proximal bundle framework establishes the iteration-complexity of proximal bundle methods for hybrid weakly convex composite optimization problems in a unified manner, which includes various well-known bundle update schemes and uses a stationarity measure that is easily verifiable in contrast to Moreau stationarity.

What carries the argument

The proximal bundle framework (PBF), a structure that unifies multiple bundle update schemes and substitutes an easily verifiable stationarity measure for harder-to-check alternatives.

If this is right

  • Proximal bundle methods apply to hybrid weakly convex composite problems with explicit iteration complexity guarantees.
  • Multiple existing bundle update schemes inherit the same complexity bound through the unified framework.
  • The verifiable stationarity measure supplies a practical stopping criterion that does not require checking Moreau stationarity.
  • The analysis covers both smooth and nonsmooth components within the hybrid problem class.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the unification holds, then prior analyses of individual bundle schemes for these problems can be replaced by a single proof.
  • Implementations could adopt the verifiable measure as a default stopping rule, simplifying code for weakly convex problems.
  • The same framework might extend to related classes such as weakly convex problems with additional structure like monotonicity.

Load-bearing premise

The proximal bundle framework correctly captures the behavior of the bundle update schemes it claims to unify, and its verifiable stationarity measure is enough to prove the stated iteration complexity without further unstated restrictions on the problem class.

What would settle it

A concrete hybrid weakly convex composite problem instance where a proximal bundle method requires asymptotically more iterations than the claimed bound to reach the paper's stationarity measure would falsify the result.

read the original abstract

This paper establishes the iteration-complexity of proximal bundle methods for solving hybrid (i.e., a blend of smooth and nonsmooth) weakly convex composite optimization (HWC-CO) problems. This is done in a unified manner by considering a proximal bundle framework (PBF), which includes various well-known bundle update schemes. In contrast to hard-to-check stationary conditions (e.g., the Moreau stationarity) used by other methods for solving HWC-CO, PBF uses a stationarity measure that is easily verifiable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper establishes the iteration-complexity of proximal bundle methods for solving hybrid weakly convex composite optimization (HWC-CO) problems. This is done in a unified manner by considering a proximal bundle framework (PBF), which includes various well-known bundle update schemes. In contrast to hard-to-check stationary conditions (e.g., the Moreau stationarity) used by other methods for solving HWC-CO, PBF uses a stationarity measure that is easily verifiable.

Significance. If the full proofs and assumptions in the manuscript establish the claimed complexity bounds and the correctness of the PBF unification without hidden restrictions, the work would offer a practical contribution to nonsmooth optimization by replacing difficult-to-verify stationarity measures with verifiable ones and providing a common analysis framework for multiple bundle schemes.

minor comments (1)
  1. The abstract does not specify the precise iteration complexity bound (e.g., dependence on epsilon or problem parameters) achieved by the PBF; including this would strengthen the summary of the main result.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their summary of the manuscript and for recognizing the potential practical contribution of replacing difficult-to-verify stationarity measures with verifiable ones, along with providing a common analysis framework. We appreciate the assessment that the work could be significant if the proofs hold. No specific major comments were listed in the report beyond the overall uncertainty regarding verification of the proofs and assumptions, so we respond to that point below. We remain available to address any detailed questions on the analysis.

read point-by-point responses

  1. Referee: If the full proofs and assumptions in the manuscript establish the claimed complexity bounds and the correctness of the PBF unification without hidden restrictions, the work would offer a practical contribution...

    Authors: The manuscript contains complete proofs establishing the iteration complexity bounds for the proximal bundle framework (PBF) under the explicitly stated assumptions for hybrid weakly convex composite optimization problems. The PBF is defined in a manner that unifies multiple bundle update schemes without additional hidden restrictions; all conditions are verifiable from the problem data and the algorithm parameters as described. We believe the analysis is rigorous and self-contained. If the referee identifies any specific part of the proofs or assumptions that requires clarification, we would be glad to provide additional details or expansions in a revision. revision: no

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

This is a theoretical complexity analysis paper establishing iteration bounds for proximal bundle methods on HWC-CO problems via a unifying PBF framework. The abstract and available material describe standard mathematical derivations from problem assumptions to complexity results, using a verifiable stationarity measure instead of Moreau stationarity. No self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations that reduce claims to inputs by construction are present or detectable. The central result rests on independent analysis of the framework's properties rather than circular reductions. This is the expected outcome for a self-contained theoretical paper in optimization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the paper relies on standard assumptions from convex and weakly convex optimization theory; no free parameters, invented entities, or ad-hoc axioms are identifiable from the provided text.

axioms (1)
  • domain assumption Standard properties of weakly convex functions and proximal operators in composite optimization
    Invoked implicitly to define the HWC-CO problem class and stationarity measure

pith-pipeline@v0.9.0 · 5607 in / 1295 out tokens · 26981 ms · 2026-05-24T09:16:48.949294+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Atenas, C

    F. Atenas, C. Sagastiz´ abal, P. JS Silva, and M. Solodov. A unified analysis of descent sequences in weakly convex optimization, including convergence rates for bundle metho ds. SIAM Journal on Optimization , 33(1):89–115, 2023

    work page 2023

  2. [2]

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

    work page 2017

  3. [3]

    Davis and D

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

    work page 2019

  4. [4]

    Davis and B

    D. Davis and B. Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal on Optimization , 29(3):1908–1930, 2019

    work page 1908

  5. [5]

    D ´ ıaz and B

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

    work page 2023

  6. [6]

    Drusvyatskiy and C

    D. Drusvyatskiy and C. Paquette. Efficiency of minimizing composit ions of convex functions and smooth maps. Mathematical Programming, 178:503–558, 2019

    work page 2019

  7. [7]

    Du and A

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

    work page 2017

  8. [8]

    Frangioni

    A. Frangioni. Generalized bundle methods. SIAM Journal on Optimization , 13(1):117–156, 2002

    work page 2002

  9. [9]

    Fuduli, M

    A. Fuduli, M. Gaudioso, and G. Giallombardo. Minimizing nonconvex no nsmooth functions via cutting planes and proximity control. SIAM Journal on Optimization , 14(3):743–756, 2004

    work page 2004

  10. [10]

    Hare and C

    W. Hare and C. Sagastiz´ abal. Computing proximal points of non convex functions. Mathematical Programming, 116(1-2):221–258, 2009

    work page 2009

  11. [11]

    Hare and C

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

    work page 2010

  12. [12]

    W. Hare, C. Sagastiz´ abal, and M. Solodov. A proximal bundle me thod for nonsmooth nonconvex functions with inexact information. Computational Optimization and Applications , 63(1):1–28, 2016

    work page 2016

  13. [13]

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

    work page 2000

  14. [14]

    K. C. Kiwiel. Methods of descent for nondifferentiable optimization , volume 1133. Springer, 2006

    work page 2006

  15. [15]

    On fr´ echet subdifferentials

    A Ya Kruger. On fr´ echet subdifferentials. Journal of Mathematical Sciences , 116(3):3325–3358, 2003

    work page 2003

  16. [16]

    Lemar´ echal

    C. Lemar´ echal. An extension of davidon methods to non differe ntiable problems. In Nondifferentiable optimization, pages 95–109. Springer, 1975

    work page 1975

  17. [17]

    Liang and R

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

    work page 2021

  18. [18]

    Liang and R

    J. Liang and R. D. C. Monteiro. A unified analysis of a class of prox imal bundle methods for solving hybrid convex composite optimization problems. Mathematics of Operations Research , 49(2):832–855, 2024

    work page 2024

  19. [19]

    T. Lin, C. Jin, and M. I Jordan. Near-optimal algorithms for minim ax optimization. In Conference on Learning Theory, pages 2738–2779. PMLR, 2020

    work page 2020

  20. [20]

    M. M. Makela and P. Neittaanmaki. Nonsmooth optimization: analysis and algorithms with appl ications to optimal control . World Scientific, 1992

    work page 1992

  21. [21]

    R. Mifflin. A modification and an extension of Lemar´ echal’s algorith m for nonsmooth minimization. In Nondifferential and variational techniques in optimizatio n, pages 77–90. Springer, 1982

    work page 1982

  22. [22]

    D. Noll, O. Prot, and A. Rondepierre. A proximity control algorit hm to minimize nonsmooth and nonconvex functions. Pacific Journal of Optimization , 4(3):569–602, 2008

    work page 2008

  23. [23]

    Nouiehed, M

    M. Nouiehed, M. Sanjabi, T. Huang, J.D. Lee, and M. Razaviyayn . Solving a class of non-convex min- max games using iterative first order methods. In Advances in Neural Information Processing Systems , pages 14905–14916, 2019

    work page 2019

  24. [24]

    de Oliveira, C

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

    work page 2014

  25. [25]

    D. M. Ostrovskii, A. Lowy, and M. Razaviyayn. Efficient search o f first-order nash equilibria in nonconvex-concave smooth min-max problems. SIAM Journal on Optimization , 31(4):2508–2538, 2021

    work page 2021

  26. [26]

    Rafique, M

    H. Rafique, M. Liu, Q. Lin, and T. Yang. Weakly-convex–concav e min–max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software , 37(3):1087–1121, 2022

    work page 2022

  27. [27]

    Ruszczy´ nski

    A. Ruszczy´ nski. Nonlinear optimization. Princeton university press, 2011

    work page 2011

  28. [28]

    K. K. Thekumparampil, P. Jain, P. Netrapalli, and S. Oh. Efficient a lgorithms for smooth minimax optimization. In Advances in Neural Information Processing Systems , pages 12680–12691, 2019

    work page 2019

  29. [29]

    J.-B. H. Urruty and C. Lemar´ echal. Convex analysis and minimization algorithms II . Springer-Verlag, 1993

    work page 1993

  30. [30]

    Vlˇ cek and L

    J. Vlˇ cek and L. Lukˇ san. Globally convergent variable metric m ethod for nonconvex nondifferentiable unconstrained minimization. Journal of Optimization Theory and Applications , 111:407–430, 2001

    work page 2001

  31. [31]

    P. Wolfe. A method of conjugate subgradients for minimizing non differentiable functions. In Nondif- ferentiable optimization, pages 145–173. Springer, 1975. A Technical results about subdifferentials This section presents two technical results about ε-subdifferentials that will be used in our analysis. The first result describes a simple relationship involvi...

    work page 1975

  32. [32]

    It follows from Lemma 4.5(a) that for every u∈ domh, ˆΓk(ˆxk) + 1 2λ∥ˆxk− ˆyk− 1∥2≤ ˆΓk(u) + 1 2λ∥u− ˆyk− 1∥2− 1 2λ∥u− ˆxk∥2

    for every k≥ 1. It follows from Lemma 4.5(a) that for every u∈ domh, ˆΓk(ˆxk) + 1 2λ∥ˆxk− ˆyk− 1∥2≤ ˆΓk(u) + 1 2λ∥u− ˆyk− 1∥2− 1 2λ∥u− ˆxk∥2. (113) The facts that x∗ k is the minimizer of (

    work page

  33. [33]

    and the objective function is (1 /λ )-strongly convex imply that φ m(ˆyk; ˆyk− 1) + 1 2λ∥yk− ˆyk− 1∥2≥ φ m(x∗ k; ˆyk− 1) + 1 2λ∥x∗ k− ˆyk− 1∥2 + 1 2λ∥ˆyk− x∗ k∥2. Using (

    work page

  34. [34]

    with u =x∗ k, the above inequality, ( 67), and ( 69), we have ˆδk≥ φ m(ˆyk; ˆyk− 1) + 1 2λ∥ˆyk− ˆyk− 1∥2− ˆΓk(ˆxk)− 1 2λ∥ˆxk− ˆyk− 1∥2 ≥ φ m(x∗ k; ˆyk− 1) + 1 2λ∥x∗ k− ˆyk− 1∥2 + 1 2λ∥ˆyk− x∗ k∥2− ˆΓk(x∗ k)− 1 2λ∥x∗ k− ˆyk− 1∥2 + 1 2λ∥x∗ k− ˆxk∥2 = [ φ m(x∗ k; ˆyk− 1)− ˆΓk(x∗ k) ] + 1 2λ∥ˆyk− x∗ k∥2 + 1 2λ∥x∗ k− ˆxk∥2 ≥ 1 2λ∥ˆyk− x∗ k∥2 + 1 2λ∥x∗ k− ˆxk∥2...

    work page