Accelerating Min-Max Optimization with Application to Minimal Bounding Sphere

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.