# Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 56 references that are in the map.
- First posted on arXiv 30 Nov 2021.

## Builds on (most cited first, 10 of 10)

- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Minimizing the Maximal Loss: How and Why?](https://mlsanity.com/paper/1602.01690/) (2016)
- [Convergence of constant step stochastic gradient descent for non-smooth non-convex functions](https://mlsanity.com/paper/2005.08513/) (2020)
- [Gradient Sampling Methods for Nonsmooth Optimization](https://mlsanity.com/paper/1804.11003/) (2018)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [Optimal Convergence Rates for the Proximal Bundle Method](https://mlsanity.com/paper/2105.07874/) (2021)
- [A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes](https://mlsanity.com/paper/2003.11457/) (2020)
- [A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems](https://mlsanity.com/paper/2110.01084/) (2021)
- [Long term dynamics of the subgradient method for Lipschitz path differentiable functions](https://mlsanity.com/paper/2006.00098/) (2020)
- [Rate of Convergence of the Bundle Method](https://mlsanity.com/paper/1609.00842/) (2016)

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

- [On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning](https://mlsanity.com/paper/2405.10289/) (2024)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions](https://mlsanity.com/paper/2507.19465/) (2025)

## Abstract (arXiv)

For strongly convex objectives that are smooth, the classical theory of gradient descent ensures linear convergence relative to the number of gradient evaluations. An analogous nonsmooth theory is challenging. Even when the objective is smooth at every iterate, the corresponding local models are unstable and the number of cutting planes invoked by traditional remedies is difficult to bound, leading to convergences guarantees that are sublinear relative to the cumulative number of gradient evaluations. We instead propose a multipoint generalization of the gradient descent iteration for local optimization. While designed with general objectives in mind, we are motivated by a ``max-of-smooth'' model that captures the subdifferential dimension at optimality. We prove linear convergence when the objective is itself max-of-smooth, and experiments suggest a more general phenomenon.