On a Gradient Approach to Chebyshev Center Problems with Applications to Function Learning

We introduce textsfgradOL, the first gradient-based optimization framework for solving Chebyshev center problems, a fundamental challenge in optimal function learning and geometric optimization. textsfgradOL hinges on reformulating the semi-infinite problem as a finitary max-min optimization, making it amenable to gradient-based techniques. By leveraging automatic differentiation for precise numerical gradient computation, textsfgradOL ensures numerical stability and scalability, making it suitable for large-scale settings. Under strong convexity of the ambient norm, textsfgradOL provably recovers optimal Chebyshev centers while directly computing the associated radius. This addresses a key bottleneck in constructing stable optimal interpolants. Empirically, textsfgradOL achieves significant improvements in accuracy and efficiency on 34 benchmark Chebyshev center problems from a benchmark textsfCSIP library. Moreover, we extend textsfgradOL to general convex semi-infinite programming (CSIP), attaining up to 4000× speedups over the state-of-the-art textttSIPAMPL solver tested on the indicated textsfCSIP library containing 67 benchmark problems. Furthermore, we provide the first theoretical foundation for applying gradient-based methods to Chebyshev center problems, bridging rigorous analysis with practical algorithms. textsfgradOL thus offers a unified solution framework for Chebyshev centers and broader CSIPs.