# Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization

arXiv: https://arxiv.org/abs/1309.5547 · HTML: https://mlsanity.com/paper/1309.5547/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2013.

## Built on by (most cited first, 14 of 14)

- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Proximal Oracles for Optimization and Sampling](https://mlsanity.com/paper/2404.02239/) (2024)
- [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023)
- [Optimal Methods for Convex Risk Averse Distributed Optimization](https://mlsanity.com/paper/2203.05117/) (2022)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)
- [Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers](https://mlsanity.com/paper/2410.01979/) (2024)
- [Numerical Methods for Convex Multistage Stochastic Optimization](https://mlsanity.com/paper/2303.15672/) (2023)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions](https://mlsanity.com/paper/2507.19465/) (2025)
- [Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates](https://mlsanity.com/paper/2604.06525/) (2026)
- [Local LMO is Secretly a Projection Method!](https://mlsanity.com/paper/2609.33383/) (2026)

## Abstract (arXiv)

The main goal of this paper is to develop uniformly optimal first-order methods for convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. By incorporating a multi-step acceleration scheme into the well-known bundle-level method, we develop an accelerated bundle-level (ABL) method, and show that it can achieve the optimal complexity for solving a general class of black-box CP problems without requiring the input of any smoothness information, such as, whether the problem is smooth, nonsmooth or weakly smooth, as well as the specific values of Lipschitz constant and smoothness level. We then develop a more practical, restricted memory version of this method, namely the accelerated prox-level (APL) method. We investigate the generalization of the APL method for solving certain composite CP problems and an important class of saddle-point problems recently studied by Nesterov [Mathematical Programming, 103 (2005), pp 127-152]. We present promising numerical results for these new bundle-level methods applied to solve certain classes of semidefinite programming (SDP) and stochastic programming (SP) problems.