Accelerating Min-Max Optimization with Application to Minimal Bounding Sphere
share
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 Õ(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+ε)-approximation of the minimal bounding sphere, i.e. identify an hypersphere enclosing a total of n given points in the d dimensional unbounded space R^d with a radius at most (1+ε) times the actual minimal bounding sphere radius for an arbitrarily small positive ε, in Õ(n d /√(ε)) computational time as opposed to the state-of-the-art approach of core-set methodology, which needs O(n d /ε) computational time.
READ FULL TEXT