Accelerating Min-Max Optimization with Application to Minimal Bounding Sphere
This provides a faster algorithm for min-max optimization and geometric approximation problems, with incremental improvements in computational efficiency for researchers and practitioners in optimization and computational geometry.
The paper tackles the min-max optimization problem for strongly-convex and smooth functions, achieving an arbitrarily small optimality gap δ in computational complexity of Õ(1/√δ), improving over the state-of-the-art O(1/δ). It applies this to the minimal bounding sphere problem, obtaining a (1+ε)-approximation in Õ(nd/√ε) time, compared to the previous O(nd/ε).
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 $\tilde{O}(1/\sqrtδ)$ 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 $\mathbb{R}^d$ with a radius at most $(1+\varepsilon)$ times the actual minimal bounding sphere radius for an arbitrarily small positive $\varepsilon$, in $\tilde{O}(n d /\sqrt{\varepsilon})$ computational time as opposed to the state-of-the-art approach of core-set methodology, which needs $O(n d /\varepsilon)$ computational time.