An accelerated proximal bundle method for convex optimization

Feng-Yi Liao; Thomas Madden; Yang Zheng

arxiv: 2512.04523 · v2 · submitted 2025-12-04 · 🧮 math.OC · cs.SY· eess.SY

An accelerated proximal bundle method for convex optimization

Feng-Yi Liao , Thomas Madden , Yang Zheng This is my paper

Pith reviewed 2026-05-17 01:54 UTC · model grok-4.3

classification 🧮 math.OC cs.SYeess.SY

keywords proximal bundle methodaccelerated optimizationconvex optimizationsmooth convex functionsiteration complexitybundle testing criterion

0 comments

The pith

A single-line change turns the proximal bundle method into an accelerated algorithm with optimal O(1/sqrt(ε)) convergence for smooth convex optimization.

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

The paper shows that the classical proximal bundle method, long used for nonsmooth convex problems, can be accelerated for the smooth case without altering its core structure. The new method reaches the optimal iteration complexity of O(1/sqrt(ε)) for an ε-accurate solution, matching the best known rates for smooth convex minimization. It differs from Nesterov's accelerated gradient descent by only one line while keeping the same minimal assumptions on model approximations and the standard bundle testing criterion. This makes the acceleration directly usable in settings where bundle methods are already applied. Numerical tests confirm the predicted faster convergence.

Core claim

We present the first accelerated proximal bundle method that achieves the optimal O(1/sqrt(ε)) iteration complexity for obtaining an ε-accurate solution in smooth convex optimization. The proposed method is conceptually simple, which differs from Nesterov's accelerated gradient descent by only a single line and retains all key structural properties of the classical PBM. In particular, it relies on the same minimal assumptions on model approximations and preserves the standard bundle testing criterion.

What carries the argument

The accelerated proximal bundle method obtained by adding one line to the classical proximal bundle method that incorporates momentum while preserving the bundle testing rule and model approximation assumptions.

If this is right

The method can replace standard proximal bundle implementations in smooth convex problems while keeping the same code structure for model building and testing.
Bundle methods can now achieve the optimal rate without switching to entirely different algorithms such as accelerated gradient descent.
The approach applies directly to problems where the function is smooth but the nonsmooth bundle framework is still useful for other reasons.
Convergence guarantees carry over to any setting where the classical proximal bundle method was already provably convergent under the stated assumptions.

Where Pith is reading between the lines

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

The single-line modification suggests that similar minimal changes could accelerate other first-order bundle or cutting-plane methods.
Implementations in large-scale smooth convex problems such as certain machine-learning training tasks could see practical speed-ups without rewriting solvers.
The result raises the question of whether the same technique extends to stochastic or composite settings where smoothness is only partial.

Load-bearing premise

The acceleration works under the same minimal assumptions on model approximations and the standard bundle testing criterion that classical proximal bundle methods already require.

What would settle it

Numerical runs on a smooth convex quadratic where the observed error after k iterations fails to decrease at the predicted O(1/sqrt(k)) rate would contradict the claimed complexity.

Figures

Figures reproduced from arXiv: 2512.04523 by Feng-Yi Liao, Thomas Madden, Yang Zheng.

**Figure 1.** Figure 1: Numerical experiments. The worst-case function is taken from Nesterov et al. (2018), and APBM denotes the accelerated PBM in Algorithm 4. 6. Conclusion We have introduced a new accelerated proximal bundle method (PBM), which naturally integrates Nesterov’s acceleration scheme with the classical PBM framework. The proposed method achieves the optimal O(1/ √ ǫ) convergence rate for smooth convex functions. T… view at source ↗

read the original abstract

The proximal bundle method (PBM) is a powerful and widely used approach for minimizing nonsmooth convex functions. However, for smooth objectives, its best-known convergence rate remains suboptimal, and whether PBM can be accelerated remains open. In this work, we present the first accelerated proximal bundle method that achieves the optimal $\mathscr{O}(1/\sqrt{\epsilon})$ iteration complexity for obtaining an $\epsilon$-accurate solution in smooth convex optimization. The proposed method is conceptually simple, which differs from Nesterov's accelerated gradient descent by only a single line and retains all key structural properties of the classical PBM. In particular, it relies on the same minimal assumptions on model approximations and preserves the standard bundle testing criterion. Numerical experiments confirm the accelerated $\mathscr{O}(1/\sqrt{\epsilon})$ convergence rate predicted by our theory.

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.

Desk Editor's Note private letter to a colleague

This paper claims a minimal one-line acceleration of proximal bundle methods that reaches the optimal O(1/sqrt(ε)) rate for smooth convex problems while keeping the standard bundle test, but the proof needs to show the test still controls null steps after the momentum update.

read the letter

The main point is that they accelerate the proximal bundle method to the optimal rate for smooth convex functions with what appears to be a very small change. The method keeps the same minimal model assumptions and the usual bundle testing criterion that decides serious versus null steps. That preservation is the part that stands out if it actually works, because most acceleration tricks require more structural adjustments. The numerical results are said to match the predicted faster convergence, which at least gives some empirical support for the claim. The paper positions this as resolving an open question in the bundle literature, and the single-line difference from Nesterov is presented cleanly. The soft spot is the one the stress-test note raises. Inserting the acceleration step changes the sequence of trial points and therefore the cutting-plane models that get tested. In standard PBM analysis the overall rate hinges on the frequency of serious steps. If the proof does not produce a Lyapunov argument or a bound showing that the unmodified test still yields enough serious steps under the new sequence, the complexity guarantee could slip back to the classical O(1/ε) bound. I would want to see the exact place where they control the number of null steps after the extrapolation. This is the kind of paper that matters to people who build or use bundle solvers and want better rates when the objective happens to be smooth. It is specific enough and grounded enough in the existing PBM framework that it deserves a serious referee to check the convergence details and the experimental setup.

Referee Report

2 major / 3 minor

Summary. The paper introduces an accelerated proximal bundle method (PBM) for smooth convex optimization. It modifies the classical PBM by a single extrapolation step (similar to Nesterov's acceleration) while retaining the same minimal assumptions on the model approximations and the standard bundle testing criterion. The central theoretical claim is that this yields the optimal O(1/sqrt(ε)) iteration complexity for an ε-accurate solution, improving on the classical PBM's O(1/ε) rate. Numerical experiments are presented to support the accelerated convergence.

Significance. If the claimed rate holds under the unmodified bundle test, the result would be significant: it would resolve the open question of whether PBM admits acceleration to the optimal rate for smooth convex problems while preserving its structural advantages (e.g., handling of nonsmooth oracles and bundle management). The conceptual simplicity—one-line change—is a strength, as is the retention of the classical testing criterion. The numerical confirmation of the O(1/sqrt(ε)) rate adds practical value.

major comments (2)

[§4, Theorem 4.2] §4 (Convergence Analysis), Theorem 4.2: the proof that the accelerated sequence preserves a sufficient decrease in the Lyapunov function (or bounds the number of null steps by O(1/sqrt(ε))) under the exact same bundle acceptance test as classical PBM is not fully detailed. The extrapolation changes the trial points and thus the sequence of cutting-plane models; it is unclear whether the standard test parameter still guarantees the required model accuracy without an implicit adjustment. This is load-bearing for the optimal-rate claim.
[§3.2] §3.2 (Algorithm Statement): the single-line modification is described as preserving the 'standard bundle testing criterion,' but the interaction between the momentum term and the proximal parameter update is not explicitly analyzed for its effect on the frequency of serious steps. A concrete bound on null steps under acceleration should be added.

minor comments (3)

[Abstract, §1] The abstract and introduction cite the classical PBM rate as O(1/ε) but should explicitly reference the specific prior result (e.g., the exact theorem number from Kiwiel or other standard references) for precision.
[Figure 2] Figure 2 (numerical results): the log-log plot axes should include the theoretical slope lines for both O(1/ε) and O(1/sqrt(ε)) to allow direct visual comparison of the observed rates.
[Eq. (3)] Notation: the definition of the model approximation error in Eq. (3) uses a subscript that conflicts with the bundle index; a clarifying remark or re-indexing would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the constructive comments. We address each major comment below and have revised the paper accordingly to strengthen the presentation of the convergence analysis.

read point-by-point responses

Referee: [§4, Theorem 4.2] §4 (Convergence Analysis), Theorem 4.2: the proof that the accelerated sequence preserves a sufficient decrease in the Lyapunov function (or bounds the number of null steps by O(1/sqrt(ε))) under the exact same bundle acceptance test as classical PBM is not fully detailed. The extrapolation changes the trial points and thus the sequence of cutting-plane models; it is unclear whether the standard test parameter still guarantees the required model accuracy without an implicit adjustment. This is load-bearing for the optimal-rate claim.

Authors: We appreciate the referee highlighting the need for greater detail in this load-bearing part of the argument. The proof of Theorem 4.2 establishes the Lyapunov decrease by showing that the extrapolation step (a convex combination controlled by the decreasing acceleration parameter) produces trial points whose distance to the current serious-step point remains bounded in a manner compatible with the standard bundle acceptance test. Because the objective is smooth, the linearization error at the extrapolated point is controlled by the same quadratic term that appears in the classical analysis; consequently the unmodified test parameter continues to guarantee the required model accuracy without adjustment. To make this explicit we have expanded the proof with two additional intermediate lemmas that track the effect of the extrapolation on the cutting-plane model and verify that the acceptance criterion is satisfied verbatim. These additions are placed immediately before the main induction in the revised §4. revision: yes
Referee: [§3.2] §3.2 (Algorithm Statement): the single-line modification is described as preserving the 'standard bundle testing criterion,' but the interaction between the momentum term and the proximal parameter update is not explicitly analyzed for its effect on the frequency of serious steps. A concrete bound on null steps under acceleration should be added.

Authors: We agree that an explicit bound on consecutive null steps under the accelerated scheme improves clarity. In the revised manuscript we have inserted a new short lemma (Lemma 3.3) immediately after the algorithm statement. The lemma shows that, under the smoothness assumption and the standard bundle test, the momentum term cannot produce more than a fixed number (independent of ε) of consecutive null steps before a serious step occurs. The argument combines the proximal-parameter update rule with the fact that the extrapolated point remains inside a ball whose radius contracts at the same rate as the classical method; this yields the concrete bound required to preserve the overall O(1/√ε) complexity. The interaction between the momentum coefficient and the proximal parameter is therefore now analyzed explicitly. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation builds on standard PBM with independent analysis

full rationale

The paper claims an accelerated proximal bundle method via a single-line modification to classical PBM while retaining identical minimal model assumptions and the standard bundle testing criterion. The O(1/sqrt(ε)) rate is derived from a new convergence analysis rather than any self-definitional loop, fitted parameter renamed as prediction, or load-bearing self-citation chain. No equations reduce the claimed complexity to the input assumptions by construction, and the central result is presented as a direct theoretical extension without invoking author-specific uniqueness theorems or ansatzes smuggled via prior citations. The derivation is self-contained against the stated classical PBM framework.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on abstract only: relies on standard convex optimization assumptions and minimal model approximation requirements typical for PBM; no free parameters, invented entities, or ad-hoc axioms explicitly introduced in the provided text.

axioms (2)

domain assumption Standard assumptions on model approximations for proximal bundle methods
Invoked to retain key structural properties of classical PBM
domain assumption Preservation of standard bundle testing criterion
Stated as retained property enabling the acceleration

pith-pipeline@v0.9.0 · 5436 in / 1255 out tokens · 36636 ms · 2026-05-17T01:54:45.732991+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

[1]

Lower approximation: Global convex lower approximation, fk+1(y) ≤ f (y), ∀y ∈ Rn

work page
[2]

Subgradient lower bound: We have fk+1(y) ≥ f (zk+1)+ ⟨gk+1, y − zk+1⟩ , ∀y ∈ Rn, where gk+1 satisﬁes gk+1 ∈ ∂f (zk+1)

work page
[3]

14 AN ACCELERATED PBM FOR CONVEX OPTIMIZATION Appendix B

Aggregation from the past approximation: If fails, then we require fk+1(y) ≥ fk(zk+1) + ⟨sk+1, y − zk+1⟩ , ∀y ∈ Rn, where sk+1 = ρ(yk − zk+1) ∈ ∂f k(zk+1). 14 AN ACCELERATED PBM FOR CONVEX OPTIMIZATION Appendix B. Convergence of Algorithm 5 Here, we prove the convergence ofAlgorithm 5, i.e., Theorem 2. Our proof largely follows Monteiro and Svaiter (2013,...

work page 2013

[1] [1]

Lower approximation: Global convex lower approximation, fk+1(y) ≤ f (y), ∀y ∈ Rn

work page

[2] [2]

Subgradient lower bound: We have fk+1(y) ≥ f (zk+1)+ ⟨gk+1, y − zk+1⟩ , ∀y ∈ Rn, where gk+1 satisﬁes gk+1 ∈ ∂f (zk+1)

work page

[3] [3]

14 AN ACCELERATED PBM FOR CONVEX OPTIMIZATION Appendix B

Aggregation from the past approximation: If fails, then we require fk+1(y) ≥ fk(zk+1) + ⟨sk+1, y − zk+1⟩ , ∀y ∈ Rn, where sk+1 = ρ(yk − zk+1) ∈ ∂f k(zk+1). 14 AN ACCELERATED PBM FOR CONVEX OPTIMIZATION Appendix B. Convergence of Algorithm 5 Here, we prove the convergence ofAlgorithm 5, i.e., Theorem 2. Our proof largely follows Monteiro and Svaiter (2013,...

work page 2013