⚡ electrical engineering

An accelerated proximal bundle method for convex optimization

This paper introduces the first accelerated proximal bundle method that achieves the optimal $\mathscr{O}(1/\sqrt{\epsilon})$ iteration complexity for smooth convex optimization while maintaining the core structural properties and simplicity of the classical proximal bundle method.

Original authors: Feng-Yi Liao, Thomas Madden, Yang Zheng

Published 2026-04-28

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Feng-Yi Liao, Thomas Madden, Yang Zheng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy mountain range. You can’t see the whole landscape; you can only feel the slope of the ground right beneath your feet.

In the world of mathematics and AI, this is called "Convex Optimization." Finding that lowest point is crucial for training everything from self-driving cars to ChatGPT.

This paper introduces a new way to find that "bottom" much faster than before. To understand it, let's look at the three characters in our story.

1. The Slow Hiker (Gradient Descent)

Imagine a hiker who only looks at the ground directly under their boots. They feel the slope and take one step downward. It works, but it’s slow. If the mountain is huge, they’ll be walking for days. In math, this is Gradient Descent, and it’s reliable but "suboptimal" (too slow).

2. The Smart Hiker (Nesterov’s Acceleration)

Now, imagine a hiker who has a bit of "momentum." Instead of just looking down, they remember how fast they were already moving. If they’ve been heading downhill for a while, they don't just step; they glide forward with speed. This is Nesterov’s Accelerated Gradient Descent. It’s much faster, but it has a weakness: it only works if the ground is "smooth" (like a paved road). If the ground is rocky, jagged, or broken (what mathematicians call "nonsmooth"), the momentum might make the hiker trip or fly right past the bottom.

3. The Architect (The Proximal Bundle Method)

This is where the Proximal Bundle Method (PBM) comes in. Instead of just feeling the ground, this hiker carries a notebook. Every time they take a step, they draw a little map of the slope they just felt. They "bundle" these little maps together to build a mental model of what the mountain looks like. This allows them to handle "rocky" terrain (nonsmooth functions) much better than the gliding hiker.

The Problem: For a long time, scientists knew the "Architect" was great for rocky terrain, but they couldn't figure out how to give them "momentum" without making them lose their balance. The Architect was steady, but slow.

The Breakthrough: The "Super-Architect"

The authors of this paper have finally solved this. They created the Accelerated Proximal Bundle Method.

Think of it like giving the Architect a high-tech drone.

Instead of just building a map based on where they are standing, the Architect uses the drone to look ahead (this is the "extrapolation" or "momentum" part). They combine the steady, careful map-building of the PBM with the high-speed gliding of Nesterov’s method.

Why is this a big deal?

The Speed Limit: In math, there is a theoretical "speed limit" for how fast you can find the bottom of a smooth mountain. For decades, the PBM was driving well below that limit. This paper proves that their new method hits that "optimal" speed limit.
Simplicity: They didn't have to invent a massive, complicated new machine. They basically took the existing "Architect" and added one clever line of instruction to allow for momentum.
Versatility: It works beautifully on smooth, paved roads, but it keeps the "map-building" intelligence that allows it to handle rocky, jagged terrain.

Summary for the Non-Math Person

If finding the bottom of a valley is the goal:

Old ways were either a slow walker or a fast glider who trips on rocks.
This paper provides a fast, gliding architect who builds a map as they go, allowing them to zoom toward the bottom without ever losing their footing.

Technical Summary: An Accelerated Proximal Bundle Method for Convex Optimization

1. Problem Statement

The paper addresses the optimization of smooth convex functions $f: \mathbb{R}^n \to \mathbb{R}$ that are $M$ -smooth. While the Proximal Bundle Method (PBM) is a cornerstone for nonsmooth convex optimization, its convergence rate for smooth objectives has historically been suboptimal at $O(1/\epsilon)$ iterations.

The central research question is whether the PBM framework—which relies on inexact proximal updates via convex under-estimators—can be accelerated to achieve the optimal iteration complexity of $O(1/\sqrt{\epsilon})$ , similar to Nesterov’s Accelerated Gradient Descent (AGD).

2. Methodology

The authors propose the Accelerated Proximal Bundle Method (APBM). The methodology is built upon three pillars:

Inexact Proximal Point Interpretation: The authors observe that the PBM's double-loop structure (using a ProxDescent subroutine) can be interpreted as an inexact implicit (sub)gradient update. Specifically, the candidate point $z_{j+1}$ generated by the bundle model satisfies an inexactness condition where the error is controlled by the descent criterion.
Integration of Nesterov’s Momentum: Instead of a standard gradient step, the authors replace the gradient update in Nesterov’s AGD with the PBM ProxDescent oracle. This allows the algorithm to maintain three coupled sequences ( $\{x_k\}$ , $\{y_k\}$ , and $\{z_k\}$ ) that incorporate momentum and extrapolation.
Algorithmic Framework: The proposed Algorithm 4 utilizes a standard bundle strategy (using convex under-estimators $\tilde{f}_j$ and a descent test $\beta$ ) but applies it within an accelerated outer loop. This ensures the method remains "bundle-like" by using the same minimal assumptions on model approximations and testing criteria used in classical PBM.

3. Key Contributions

First Accelerated PBM: The paper presents the first PBM that achieves the optimal $O(1/\sqrt{\epsilon})$ iteration complexity for smooth convex optimization.
Theoretical Bridge: It establishes a formal connection between the PBM and the Accelerated Hybrid Proximal Extragradient (A-HPE) framework by Monteiro and Svaiter (2013). They prove that the bundle descent criterion naturally satisfies the error requirements of the A-HPE framework.
Generalization of AGD: The authors demonstrate that their APBM is a graceful generalization of Nesterov’s AGD. Under specific parameter settings ( $\beta \leq 1/2$ and $\rho \geq M$ ), the PBM oracle terminates in a single iteration, reducing the algorithm exactly to standard AGD.
Robustness to Step-size: Unlike standard AGD, which requires a step-size tied to the Lipschitz constant ( $1/M$ ), the APBM allows for a larger step-size ( $1/\rho$ ) by adjusting the descent parameter $\beta$ .

4. Results

Convergence Rate: The authors prove that for $M$ -smooth convex functions, the sequence $\{x_k\}$ satisfies:
$f(x_k) - f^* \leq \frac{2\rho \cdot \text{dist}^2(x_0, S)}{k^2}$
This confirms the $O(1/k^2)$ rate in function value, which translates to the optimal $O(1/\sqrt{\epsilon})$ iteration complexity.
Numerical Validation:
- Worst-case function: Experiments on a specific non-strongly convex function confirm that APBM achieves the $O(1/k^2)$ rate, whereas classical PBM remains at $O(1/k)$ .
- Logistic Regression: In practical smooth optimization, APBM with a large step-size (small $\rho$ ) significantly outperforms standard AGD in terms of speed and accuracy.

5. Significance

This work is significant because it closes a long-standing gap in the theory of bundle methods. By proving that PBM can be accelerated without changing its fundamental structural properties (like the descent test or the type of under-estimators), the authors provide a powerful tool that combines the robustness of bundle methods with the efficiency of Nesterov-type acceleration. This opens new avenues for applying accelerated techniques to more complex, potentially nonsmooth, or structured optimization problems where bundle methods are traditionally preferred.