# Accelerating Min-Max Optimization with Application to Minimal Bounding Sphere

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

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

- [Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization](https://mlsanity.com/paper/2504.02833/) (2025)

## Abstract (arXiv)

We study the min-max optimization problem where each function contributing to the max operation is strongly-convex and smooth with bounded gradient in the search domain. By smoothing the max operator, we show the ability to achieve an arbitrarily small positive optimality gap of δ in tildeO(1/√δ) computational complexity (up to logarithmic factors) as opposed to the state-of-the-art strong-convexity computational requirement of O(1/δ). We apply this important result to the well-known minimal bounding sphere problem and demonstrate that we can achieve a (1+varepsilon)-approximation of the minimal bounding sphere, i.e. identify an hypersphere enclosing a total of n given points in the d dimensional unbounded space ℝd with a radius at most (1+varepsilon) times the actual minimal bounding sphere radius for an arbitrarily small positive varepsilon, in tildeO(n d /√varepsilon) computational time as opposed to the state-of-the-art approach of core-set methodology, which needs O(n d /varepsilon) computational time.