On a Gradient Approach to Chebyshev Center Problems with Applications to Function Learning
Authors: Abhinav Raghuvanshi
Mayank Baranwal
Debasish Chatterjee
Venue: Accepted by TMLR ()

Abstract: We introduce $\textsf{gradOL}$, the first gradient-based optimization framework for solving Chebyshev center problems, a fundamental challenge in optimal function learning and geometric optimization. $\textsf{gradOL}$ 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, $\textsf{gradOL}$ ensures numerical stability and scalability, making it suitable for large-scale settings. Under strong convexity of the ambient norm, $\textsf{gradOL}$ provably recovers optimal Chebyshev centers while directly computing the associated radius. This addresses a key bottleneck in constructing stable optimal interpolants. Empirically, $\textsf{gradOL}$ achieves significant improvements in accuracy and efficiency on 34 benchmark Chebyshev center problems from a benchmark \textsf{CSIP} library. Moreover, we extend $\textsf{gradOL}$ to general convex semi-infinite programming (CSIP), attaining up to $4000\times$ speedups over the state-of-the-art \textsf{sipampl} solver tested on the indicated \textsf{CSIP} 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. $\textsf{gradOL}$ thus offers a unified solution framework for Chebyshev centers and broader CSIPs.

Published in Transactions on Machine Learning Research (12/2025)
On a Gradient Approach to Chebyshev Center Problems with Applications to Function Learning
Abhinav Raghuvanshi
200040008
Indian Institute of Technology, Bombay
Mayank Baranwal
mbbreenwalWttti.cmmm
Tata Consultancy Services Research, Mumbai Indian Instttute of Technology, Bomboy
Debasish Chatterjee
dchatter@kitb. o.c.i......
Indian Institute of Technology, Bombay
Reviewed on OpenReview: https: optp//veeneewew..o net/ forun? id= LPZVsDhyyj
Abstract
We introduce gradOL, the first gradient-based optimization framework for solving Chebyshev center problems, fundamental challenge in optimal function learning and geometric opti- mization. grad0L 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, gradOL ensures numerical sta- bility and scalability, making it suitable for large-scale settings. Under strong convexity of the ambient norm, gradOL provably recovers optimal Chebyshev centers while directly computing the associated radius. This addresses a key bottleneck in constructing stable optimal interpolants. Empirically, gradOL achieves significant improvements in accuracy and efficiency on 34 benchmark Chebyshev center problems from benchmark CSIP library. Moreover, we extend grad0L to general convex semi-infinite programming (CSIP), attaining up 4000x speedups over the state-of-the-art SIPAMPL solver tested on the indicated CSIP 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. gradOL thus offers unified solution framework for Chebyshev centers and broader CSIPs.
1 Introduction and Problem Formulation
Optimal interpolation and learning have been long-standing open problems in signal processing and the theory of function learning. The problem was posed in Micchelli & Rivlin (1977) in the context of signal processing, and while tractable solutions were sought by a multitude of researchers over the subsequent decades, satisfactory solutions continued remain elusive. In the language of approximation theory, the optimal interpolation (learning) corresponds the so-called Chebyshev center problem, which involves constructing single function from given class that best justifies given data set. Beyond function learning, the Chebyshev center problem has found extensive applications in diverse fields, such as robust optimization for managing uncertainty Bon- & Nemirovski (1998), sensor network localization for estimating node iositions Doherty & Ghaoui 2001), and facility location problems to optimize placement strategies Drezner & Hamacher (2004). Moreover, its utility extends to tasks like data fitting classification Tax Duin (1999), control system design for ensuring stability under bounded uncertainties Zhou et al. (9996). and
parameter estimation in error-bounded scenarios Boyd Vanderberghe (2004), underscoring its fundamental importance in both theoretical and practical domains.

---

Published in Transactions on Machine Learning Research (12/2025)
Let us briefty recall the optimal interpolation problem in the context of function learning: At its core, Banach space Il-1), one is given closed and bounded subset. K C F,, and charged with the task of determining ball of smallest radius containing K. The center & of such a ball is a Chebyshev center of K. In other words, a Chebyshev center of is an optimizer of the variational problem
minimize fEE
sup Il gll.
gek
Depending on certain properties (e.g., strict convexity) of the norm II-II, a set K may not have a single Chebyshev center. The optimal value of is the Chebyshev radius тK K. We refer the reader to the review Allimov & Tsar'kov kov (2019) and the authoritative text (Alimov & Tsar 2021 Chapter 16) for background on the Chebyshev center problem, and the recent work [Binev al. (2024) for an historical account of optimal interpolation interpreted from the viewpoint of the Chebyshev center. While the problem is posed above in its most general, infinite-dimensionn form, any computational method must necessarily operate on fiiteeddiensional version (Alimov & TTar 2021, Section 16.1). This paper is dedicated to solving this important finitediiennsinnal problem, for which we present an algorithm to find a solution that is exact up to the precision the computing machine.
Function learning and the Chebyshev center
In the context of function learning and interpolation theory, the Chebyshev center problem encodes the idea of optimal learning in hypothesized model class: Here stands for the space of functions whose subsets are the hypothesis classes, and the set K represents the subset of the model class of functions satisfying given data set. The corresponding optimization problem [1] faces difficult numerical challenges because first, for each fixed f E 3, the inner maximization over y in subset of the Banach space E, and its solutions cannot be parametrically expressed in closed form in f, and socond, the outer minimization over f in (1) is also over an infiniteddimension Banach space I in general. Consequently,
on polentially infiiileddinensional
numerically intractable. To ensure computational tractability, one "discretizes" the various dimensoadi objects in [1] above, and works in a finite dimensional setting[] the resulting mathematical optimization is an instance of the so-called relative Chebyshev center problem: A relative Chebyshev center of closed and bounded subset K with respect to nonempty X C I is given by an optimizer of
minimize feX
sup Ilf 9l1, gek
(2)
where the set is chosen to be a reasonably fine finite discretization approximating the Banach space I and the model class K is restricted to a suitable finite dimensional set of functions (nearly) satisfying the given data. Consequently, it addresses the optimal function learning problem via optimal interpolation from finite datasets. Nevertheless, even the resulting simplified problem (2) continues to be numerically challenging since even in finite-dimensions, the complexity increases exponentially in the state dimension (Alimov & Tsar kov 2021 Chapter 15, p. 362). Indeed, the (fnite-dimmensional) Chebyshev center problem is known to 2021 Chapter 15) in general.
be NP-hard [Alimov & Tsarr Tssr'kov
Chebyshev center via convex semi-infinite programs
Some NP-hard problems may permit numerically viable and robust approximations, and it turns out that such is the case with the (finite dimensional) Chebyshev center problem. At its core, given a nonempty and compact set K R.,", the centerpicce of numerical algorithm must operate to solve the finitoddimensional variational problem
FK = inf sup I|u - x|| xeX uek
where X is either R" or a nonempty convex subset thereof. Function learning from finite data can be framed
in the language of (3) (see Paruchuri & Chatterjee (2023) Note that is always feasible, and the set
1 For computational tractability, as pointed out in Alimov Tsar'kov 2021
Scction 16.1), imperative to restrict
attention to finitary objects; consequently, considering finite dimensionll avatars of the various objects in (1) the best. that ran be done.
2

---

Published in Transactions on Machine Learning Research (12/2025)
K contains more than two distinct points, then the Chebyshev radius of K is non-zero. Introducing slack
variable se se,, we note that the value rx of (3) is precisely equal to the value of
minimize (8,8)
||u - x|| - -80 for all E K.
(4)
subject to
(s,x) E Rxx,
dimee-ndieaiionnl convex optimization problem with a compact (and infinite) family of convex incquality constraints. It follows that solving (4) gives a solution to (3) in the sense that if (s*,x") solves [4) then FK = s" and x² is a Chebyshev center of K. The recent work Das al. [ (2022) established a viable approach to obtaining exact solutions to CSIPs, and Paruchuri] & Chatterjee (2023) developed the connection between optimal function learning and CSIPs to provide a numerically viable solution to the Chebyshev center problem. While these two works established general principles and high-level algorithms, robust numerical algorithms for solving the Chebyshev center problem were outside their scope. This article is devoted to the development of a gradient based algorithm for solving the Chebyshev center problem, which is enabled by reformulating the underlying semi-infinite program into an entirely finitary max-min structure, which in turn serves as a numerically viable algorithm. for optimal function learning
which is a convex semi-infinite program (CSIP)
Why Are Chebyshev Center Problems Practically Important? Illustrative Examples
Chebyshev center problems, at their core, capture the principle of constructing an "optimally central" object within a set K, which translates directly into optimal function lcarning when the set represents candidato hypotheses consistent with observed data. Beyond their foundational role in approximation theory, several concrete examples illustrate their broad impact:
Robust Control Systems: In designing a controller for physical system (e.g., an aircraft or a robot), the exact parameters of the system often uncertain due to manufacturing tolerances environmental changes. The set K can represent the set of all possible system responses. The Chebyshev center corresponds to single controller design that guarantees the bost possible performance (e.g., stability) in the worst-case scenario, across all possible system variations in K.
Sensor Network Localization: Consider estimating the position of a sensor node based on signals from several fixed beacons. Each signal constrains the node's location to be within certain region. The inter- section of these regions forms the set K of all possible locations. The Chebyshev center of K provides the optimal location estimate, minimizing the maximum possible error between the estimate and true location. Financial Portfolio Optimization: An investor might model set K of plausible future market scenarios, each represented by a vector of asset returns. The goal is to construct a single investment portfolio (the center) that minimizes the maximum regret. across all scenarios in K. This approach creates a portfolio optimally hedged against worst-case market outcome.
Contributions
Chebyshev center problems and more broadly, CSIPs, are notoriously challenging to solve, even in moder- ately high-dimensional settings. The core difficulty lies in their scmi-infinite nature: the feasible region is defined by infinitely many constraints, rendering even approximate solutions computationally demanding. In response, prior work has often focused on tractable relaxations, such as the relared Chebyshev center (RCC) problem Eldar al. (2007); Xia al. (2021). which approximates the original formulation.
Consequently, developing a scalable, pradient-based solver for the original (non-relaxed) Chebyshev center problem has remained longstanding open challenge in optimization and function learn- ing. Despite the importance of the problem, there has been little progress on algorithms that can directly tackle the original formulation using modern optimization toolkits. This paper introduces gradOL, the first framework to successfully address this gap. To the best our knowledge, no existing methods have successfully exploited gradient-based optimization to directly solve the Chebyshev center problem, a task for which we leverage modern automatic differentiation techniques. Relying on the fundamental insights of Borwein 1987). the key results of Paruchuri & Chatterjee (0223 can be leveraged to establish that the value

---

Published in Transactions on Machine Learning Research (12/2025)
of
4 is precisely equal to the value of
sup M0r1 e K (x,x))Rxx
inf [|u; - x1I & s, i= i= i=l....,,
Observe that (5) is entirely finitary, The inner minimization a standard convex optimization problem with n+ 1 constraints, while the outer maximization is global and over n + 1 many variables, each of which is n-dimensional. Since there is realistic possibility of obtaining an expression of the map
k m (uI..... un+1) - S(u,....,
where, 3(u1....... Mn+1) is defined as:
inf (xxx)aRxx |s| [|u xII & for I....,, n 1 ER,
but it can be evaluated will by employing standard convex optimization solvers, zeroth-order numerical methods are natural candidates for solving [5) However, the availability of autodiff libraries, c-g., pytorch and zygote, raises the pertinent question of whether employing first-order (sub-)gradden) methods (leveraging
automatic differentiation) to solve the outer maximization in 5 would be feasible. Below we sunmarize our primary contributions:
1. Efficient solver for Chebyshev center problems:
We present robust and numerically efficient im- plementation of a gradient-basee optimization technique for the Chebyshev center problem. Our complete Julia package, gradOL, employs the latest automatic differentiation libraries to compute (sub~) gob-))gradients ensuring high accuracy and scalability. Specifically:
The optimal value obtained via solver corresponds directly to the Chobyshev radius.
When the ambient norm on R" is strongly convex, our algorithu also produces optimizers that attain the Chebyshev radius through the formulation in (5) This particularly valuable optimal function learning, where the construction of numerically viable optimal interpolants has remained notable challenge over decades.
2. Theoretical foundation for gradient-based learning: The inner minimization in 5 is subject to constraints, raising two key challenges: (a) whether the gradient of the inner objective, as required by the outer maximization step, is well-defined, and (b) how to compute this gradient efficiently when it exists. While our proposed gradDL algorithm directly addresses the computational aspect in (b) through auto- matic differentiation, we also provide rigorous theoretical foundation that justifies the of gradient- based learning in the first place. Specifically, we establish that the map + 'S(u) is locally Lipschitz, thereby ensuring the existence of generalized gradients.
3. Benchmark testing and performance: The gradOL package has been tested extensively on curated collection of 34 benchmark Chebyshev center problems from the CSIP library Vaz (2001). As reported in the subsequent sections, gradOL demonstrates consistent improvements over existing techniques, providing very accurate and vastly more efficient solutions in all cases.
4. The case of general CSIPs: Since the Chebyshev center problem is a special case of CSIPs, our gradient- pradient-based approach naturally extends to solving general CSIPs. We applied grad0L to an extended library of 33 additional benchmark CSTPs. Notably, gradOL shows seneral orders of magnitude improvement in speed in almost all cases, and the values reported by gradOL are no worse than the best reported values in all but two cases.
2 Preliminaries
For Chebyshev center problems, both geometric and optimization- based methods have been proposed. In the case of certain convex sets, the Chebyshev center problem can be formulated as a linear program (LP) when the feasible region is defined by linear inequalities, making it computationally efficient to solve. Recent developments have focused on numerical algorithms that combine targeted sampling tochniques and convex semi-infniit optimization to compute the Chebyshev radius and center more efficiently. These methods are particularly relevant in optimal learning scenarios, especially when working with compact hypothesis spaces within Banach spaces (Paruchuri & Chatterjee 2023
4

---

Published in Transactions on Machine Learning Research (12/2025)
A key result from the theory of CSIPs
A CSIP fmile-dimensional convex oplimization problem with infinitely many constraints. Consider
minimize yEy
fo(y)
f(y, u) & 0 for all v u
(6)
subject to
3 c Rd. c Rm
along with the following data:
(6) aa)
Q c R is an open convex set, y c Q is closed and convex set with non-empty interior, and W is a compact set,
6 b) fo : + R continuous convex function,
6 c) f f:
is a continuous function such that f(.0) is convex for every v U, and
6 d) the admissible set Nee fy y fl. & 0} has non-empty interior.
The following recent result (Das et al. 2022. Theorem 1, Proposition 2) provides numerically viable mechanism to solve CSIPs with low memory requirements, and constitutes the backbone of the gradient technique established in this article.
Theorem 2.1. Consider the CSIP (6) along with its associated data 6
a
(6)d) d)
Define the function
ud (U1..... = (0))
inf (b(0) f(y. 0 1, ...... d}
ycyy
Then the (optimal) value of the CSIP (6)
equals
sup (E)
3i (UI.....,dd).
(8)
Moreover, if 66) admits unique solution and if (uf....,, marimizes 8, then optimizer of
(s(0)) f(y. 1f) < fort l.....d yey
inf
also optimizes 66
Theorem 2.1 is applicable the CSIP (4) corresponding to the Chebyshev center problem indeed, one picks d 1 n, Ω RxR" V = R" y c Q is some closed and convex set containing + x K, and the functions Ω xs,x) + fo(s.)) and Q K ((s.x),
((s,x),, u) -|-- x||| - in 66) to obtain [4) It is well-known that if the underlying norm ||-|| in (4) is strictly convex, e.g., if it is the Euclidean norm, then the Chebyshev center is unique. Consequently, the CSIP
(4) admits a unique solution, and in the light 5 and an optimizer of the Chebyshev center problem may be extracted as indicated Theorem 2.1 of course, the corresponding (optimal) value
of Thcorem 2.1, the value of (6) equals that of (5) (as noted before
is the Chebyshev radius.
In the case of the CSIP the function & becomes
kn+1 (u1 Mn+1) ( inf (xxx)eRxx
{s |lu; -x|1 & 0 for i= I,....n 1).
(9)
Our main contribution the algorithm grad0L leverages insights from Theorem 2.1 to develop (sub- Igradient-based optimization algorithm, gradDL, which employs automatic diffcrentiation for numerical gra- dient estimation. gradOL is designed to employ numerical gradients to maximize &. A key challenge in maximizing (#1...., 1x+11) + "(u)....,,n-1 un+1) lies the absence of closed-form analytical formulae for ' and therefore its gradients. The success gradient algorithms for optimization hinges on the local Lipschitz property of the corresponding objective function, so natural to find conditions under which this property holds for & in

---

Published in Transactions on Machine Learning Research (12/2025)
Remark 2.2 (Convexity in the inner variable vs. outer maximization). Although the original problem is convex, it is semi-infinite. Theorem 2.1 yields finitary max-min reformulation with the same optimal value. For any fixed 4, the inner minimization remains convex program; in contrast, the outer maximization over a is generally non-concave and can be non-smooth. This the source of the stationarity-typa guarantees discussed in Remark 3.2.
Automatic Differentiation for Gradient Computation
Our method leverages automatic differentiation (AD) [Baydin et al. 2018), which computes exact gradients by propagating derivatives through the computational graph the routine. The value function in ( is defined implicitly through an inner optimization, and its gradient has no closed form. AD differentiates through the full sequence of operations that produce 8, yielding an exact VS and enabling the gradOL algorithm.
3 A Differentiable Max-Min Formulation and the gradOL Algorithm
Ensuring local Lipschitzness of the function & for general CSIPs with inequality constraints presents signif- icant difficulties, but certain structures of Chebyshev center problems make them amenable to apply results from the shelf for proving local Lipschitzness of the corresponding &. Proposition A.. in Appendix A pro- vides a set of sufficient conditions for (-) to be continuous. order to satisfy the hypotheses of Proposition A.1 it is possible to rephrase the Chebyshev center problem (3) the smooth variant
inf sup |||
(10)
xeX uek
such that its optimal value is the square of the Chebyshev radius and its corresponding CSIP ( features the twice contimuously diffcrentiable objective function fo(s,x) s and constraint function f((sx), [|u [
Consider the CSIP corresponding to (10) given by
inf
{s I|u - -x| for all K).
(11)
(x.x)exxX
for which we have the following result. Recall that K may be replaced by its closed convex hull, (o)v in the Chebyshev center problem; consequently, we shall assume in the sequel that K conv(K) without losing generality.
Theorem 3.1. Consider the problem 11
with K c R" non-empty and compact and suppose that X is compact and conver set conlaining K. Define the function
kn+1g e (u1.... un+1) = 1l - ((T)
inf xxx
(s ||u x|1 < for 1,.
(12)
Then the mapping & is R- Ravaledd, Lipschitz continuous, and the value of 10 is precisely equal to supae gmsl ((7).
Proof. The mapping &G is R-valued since the admissible set is non-empty, Indeed, since K is non-empty and compact, it is bounded. Consequently, & admits an upper bound of diam == supx I|x - -x"ll, while 0 is an obvious lower bound of S. To wit, & R-valued.
For s' > diam(K) and arbitrary x' we have ||x u|| - for all K, which means that 111 is strictly feasible. Therefore, the strict feasibility condition (6)d] in the context of (6) holds in the case of
(11) The remaining hypotheses of Theorem 2.1 are clearly satisfied for (11) and its assertion guarantees
that the value of (10) is supp (z)).
It remains to prove Lipschitz continuity of G, which we present in sequence of steps:
Recall that by assumption closed and convex.

---

Published in Transactions on Machine Learning Research (12/2025)
The optimization problem the right-hand side of (12) admits solution for every E K Indeed, this is an immediate consequence of rassss theorem in view of continuity of the objective and constraint functions and compactness of the admissible set.
Step 1:
Step 2: The sel-valued map Sopt kn+1 3 R" defined by
Ku+1 3 + Sopt (Tr) arg min (s ||x uill? s for i 1, I.....n+1l.
(s.x)eRxX
is mapping. Indeed, that Sopt is non-emply valued follows from Step 1. Moreover, since K # Ø by hypothesis, for any y K and for u (#I,...,uH+1) the pair (max/=t....nt1] llu -yll² yll²,y) E R x X is in the admissible set of the indicated optimization problem. Morcover, the objective function of the optimization problem is such that if (s',x') and (s",x") are two optimizers, then of course s' =s", which means that two optimizers can differ only in the second component. But then due to strong convexity of the norm I|-II, the constraints for k I...., + give us
12 + 2- ux|l < 2 -u 1|x" -xll Vs
implying that neither (s',x') nor (s',x") is an optimizer (because one obtains a better value for the pair (max}=1.....+11 ||2 +x')|| (x'+'')))) RxX, which is admissible due convexity of K), contradicting our premise. Uniqueness of optimizers follows, and therefore, Supt is mapping.
Step 3: Fix ie E kn+l and consider the convex nonlinear program
inf {s || x|12 s for L, L.....,+1
(13)
(s,x)cRxx)
on the hight-hand side of [12)
The family of 1n++) constraints in the preceding program admits the Jacobian
-1 2(x-u1)
-1 2
(derivative) matrix x(
for x K, and clearly u = (1 07-1)² R+++1 satisfics (TT:x)
2(x-
U= - 1)" Therefore, the Sangasarian-Fromorve constraint qualification (MFCQ) condition holds for [3) for the entire family of constraints, and consequently, also for the active constraints. Tn addition, the set-valued map Steas defined by
n+1
km+1 u + Steas (T). Steas ④
= 1=1
((sx))
- C
(14)
is uniformly compact because its image contained in the compact set [0, diam K] X c R X due to the
definition of [13) Fiacco & Ishizuka 1990 Theorem 4.2) reproduced in Proposition A.1 in Appendix AA therefore, applics to (13) and guarantees local Lipschitz continuity of 3 around W7
Step 4: The map & is Lipschitz continuous. This follows from (Cobzaş et al., 2019 Theorem 2.1.6), but we provide a quick proof here. Since 7 was selected in Step arbitrarily, we get the local Tipschitz property of 3 around every maximum and minimum ga+1 and let M sup ((ū) infregn-1 3(7'). If & is not Lipschitz on (Ba') +00. That means there exist sequences (ūR)ReN. (7,)) K such --
kn*1, and consequently,
is continuous. Since k=+1 compact, attains its
k=+1, then supa, enll Nai
that limg-ros [
+0o. Since k=+1 is compact, it follows that there exist subscquences (ī YeN and De,e that couverge to some and J' in g"+1, respectively. But then, since & is bounded on k the numerator of the preceding limit bounded by 2M, which gives
|
[|
0) 76=
[8 - B(0') +oo, contradicting local Lipschitz continuity of & around 0', and |M thus asserting Lipschitz continuity of 9 on k
But this leads to lim

---

Published in Transactions on Machine Learning Research (12/2025)
Theorem 3.1 relies on the set K being compact subset of R". While K could be discrete for this result to hold, the application of gradient based techniques such as gradOL is reliant on the set k being a reasonably "nice" (e.g., convex) subset of Re",, which is true in a majority of applications.
The algorithm gradOL
Our chicf contribution, the algorithm gradOL described below, operates within an iterative framework, constructing "(',..... as a computational graph rooted at the variable nodes (u1.....*++)) For each given 7 = ,n+1),, the inner constrained minimization over (s,x) is solved using an unconstrained log-barrier method. This process iteratively updates (5), starting from an initial guess (5o. while preserving the computational graph dependency on H, thereby explicitly representing (s,x) as a function of u. Once the inner optimization reaches optimality, ((Ø) can be computed, and its numerical gradients are obtained via backpropagation through the computational graph, climinating the need for explicit gradient derivation. We now present the gradOL algorithm.
Let a 0 be a "barrier parameter" [Boyd & Vanderberghe 2004], and let ((-) be a (safe) log function, e-g. ((r) = log((mxx (max((t))) for a small E > 0. Given a current estimate ug = (#1.... Un+1) E K at iteration k, we solve the inner problem
min (xxx)RXxX
0
Σ
( ||x ||x-
- (mT)).
-a:--il? mill2)
=
(15)
Let (x2,22) be minimizer of (15) Next, for the outer step, we take step from in in the direction that increases target function ' (ūx). In our illustrative gradient-based scheme, compute Vn'9(ūx), and perform an update to obtain Mx+1- The step size (learning rate) may be constant or adaptive. Note that a reasonable initial estimate for (s,x) can be obtained using standard off-the-shelf convex optimization solvers like CVX or Convex.jl. In our framework, we utilize them to reduce the number of iterative updates required. The use of automatic differentiation libraries (e.g. Zygote Julia or Autograd PyTorch) facilitates gradient estimation, while off-the-shelf solvers enhance computational speed via warm starts. For general CSIP, the objective in 15) is replaced with fx(x), while the log- log-barrier is used to enforce the constraints (f(x,4;)
A Algorithm gradOL
1: Input: Initial guess ūg = (uI...., Un+1); barrier paramcter a > 0; max epochs M; tolcrance >
2: for k 0, 1, .,2....,,-1. M-1 do
Declare (u1...., um+1) as variable nodes computational graph; Initial guess (so,
(Inner) minimization step:
(s (Tx). (T++) E arg min aas -
n++ -1- unll²)
(s.x)eRXR*
(Sem) (#x). (ux)) is obtained iteratively using off-the-shelf solvers, such as Convex.jl, while re- taining the computational graph
5: (Outer) Update of īx:
Define the objective function terms of ūk.
((ūR)) = fo (5 (Tx) (ūx))
Compute the gradient Vn, ((zg) using the automatic differentiation library.
Update uk+1 = ūy + (7 possibly applying
to keep u2+1 in kn+1
6: Check convergence: If [ uell < 6, then stop.
7: end for
8: Return: (T((TTT))
Remark 3.2 (On the computational complexity of gradOL). The function & potentially non-smooth, non-concave, and subject constraints, which makes deriving convergence guarantecs for gradOL highly nontrivial and outside the main scope of this work. Nonetheless, by suitably adapting the proof techniques developed in Liu et al. 2024), our preliminary analysis shows that gradOL converges generalized Gold-
8

---

Published in Transactions on Machine Learning Research (12/2025)
Table grad0L performance comparison on Chebyshev Center and CSIP benchmarks
Chebyshev Center (34 instances)
CSIP (33 instances)
Method
Solved
Avg. Runtime (ms)
Solved
Avg. Runtime (ms)
Iterative Sampling
9
3,880.95
20
1,695.37
MISA-Simulated Annealing
19
23,768. 12
20
16,417.43
SIPAMPL
50,906.00
28
72.336.00
gradOL
34
638.79
33
303.77
stein stationary point of (6()) with complexity
o Bc TA 4G2
where E denotes the allowable error in evaluating G. The constants G, B, and capture, respectively, the regularity of the objective function, the size of the feasible set, and the details of the smoothing procedure (sce Liu et al. (2024)). Here, + 1 is the dimension of the uncertainty variable, and e denotes the error in approximaling the gradient V3, obtained through automatic differentiation frameworks such as zygote. The term A represents the computational cost of the inner minimization solver (e.g., CLARABEL in our case). which scales as O(va log(1/e)) with the barrier parameter a. Importantly, gradOL achieves a dependence of only vn+ I in the outer maximization step this is the best-known scaling, as existing methods often incur linear or even exponential dependence on n. sketch of the proof for this preliminary result deferred to Appendix B due space constraints.
4 Numerical Experiments and Benchmarking
We implement grad0L in Julia (version 1.8.1 g and benchmark its performance on Ubuntu 24.04 system. The hardware configuration consists of an AWS t2.large instance with 2 vCPUs, backed by an Intel Xeon processor. The instance has GiB of RAM. Using Julia's Benchmark Tools library, we measure the mean runtime of gradOL across 10 iterations for each of the 67 hard CSIP problems listed in (Vaz 2001). All computations run on the CPU without GPU accelcration, ensuring that the reported performance reflects only the algorithm and its implementation.
We benchmark gradOL against the industry standard SIPAMPL package Vaa et al. 2004). the best-known solver in the literature for solving CSIPs, presented in Table 2 In addition, grad0L is also compared with the recently reported samulated-anncaling based approach (Paruchuri & Chatterjee) 2023) (a.k.a. the MSA-Simulated Annealing) and an iterative sampling based approach (details in Supplementary). In our experiments, we set the tolerance ö in Algorithm 1 between x 10-4 and x 10-3 and limit the maximum iterations M to 103. The barrier parameter a was chosen to be sufficiently large (s 10a). Since the algorithm performs outer maximization by computing V the learning rate should ideally depend on S. We provide systematic hyperparameter analysis of gradOL under varying learning rates and barrier parameters, detailed in Appendix E
For 65 of the 67 problems, the optimal values produced by gradOL deviates by less than 1 from previously reported results. The largest absolute errors appear in watson10 (2.753 x x0011 and honstedel (1.697 x 10-1). In particular, gradOL achieves an exact match (within the provided accuracy) for the objective function values in 5 problems. Our results highlight gradOL's efficiency, solving each CSIP problem in milliseconds aver- age. More specifically, gradOL achieves a remarkable improvement in runtimes (upto æ 4 x 103) compared to the SIPAMPL solver on these benchmarks. The reduced computation time and consistent benchmark perfor- mance highlight the algorithm's 's scalability and real-world potential. Table compares the performances of gradOL with the aforementioned algorithms on the benchmark problem instances. Notably, gradOL is signifi-
SSurrce code included the supplementary.
9

---

Published in Transactions on Machine Learning Research (12/2025)
cantly better than all other algorithms, underscoring the importance of gradient-based solvers for Chebyshev center problems and CSIPs alike.
5
Conclusion
This work introduces gradOL, novel algorithm for efficiently solving Chebyshev center problems, packaged within robust Julia implementation. Extensive testing on 34 Chebyshev center problems, and more gener- ally, 67 CSIPs demonstrated its superior accuracy and superb computational efficiency over existing solvers. While gradOL proves to be highly effective, certain CSIP instances challenge gradient-based methods, high- lighting areas for improvement, especially centering around adaptation of the learning rate to the problems under consideration. Future work will focus on enhancing robustness for such cases, extending the theo- retical framework, exploring hybrid optimization approaches, and improving scalability to high-dimensional scttings, aiming to establish gradOL as versatile tool for broader optimization tasks.
References
A. R. Alimov and G. Tsar'kov. Chebyshev centres, Jung constants, and their applications. Russian Mathematical Surveys, 74(5):775-844 -499 2019, doi: https://doi. org.e/...0011.01 4213/rm9839
A. R. Alimov and I. G. Tsar'kov Geometric Approzimatioon Theory, Springer Monographs in Mathematics. Springer, Cham, 2021. doi: http:://oo..og///000007777222200
A.G. Baydin, B.A. Pearlmutter, A.A. Radul, and J.M. Siskind. Automatic differentiation machine learning: A survey. Journal of Machine Learning Research, 18(153):1 43, 2018.
A. Ben-Tal and A. Nemirovski. Robust convex optimization. Mathemalics of Operations Research, 23(4): 769 805, 1998.
P. Binev, A. Bonito, R. DeVore, and G. Petrova, Optimal learning. Calcolo, 61, 2024. article number 15, doi: o1tpp/////./////rr././//00000/01
J. M. Borwein. Direct thcorems in semi-infinite convex programming. Mathematical Programming, 21: 301-318, 1981. doi: http::///ooo..o/////00000////51/
S. Boyd and L. Vanderberghe. Convez Optimization. Cambridge University Press, 2004.
S. Cobzag, R. Miculescu, and A. Nicolae. Lipschitz Functions, volume 2241 of Lecture Notes in Mathematics. Springer, Cham, 2019. doi:
S. Das, A. Aravind, A. Cherukuri, and D. Chatterjee. Near-optimal solutions of convex semi-infinite, programs via targeted sampling. Annals of Operations Research, 318(1):129 146, 2022. doi: https://doi.oorg/10 0220//000047-02---488800
L. Doherty and L. El Ghaoui. Convex position estimation in wireless sensor networks. In Proceedings IEEE INFOCOM 2001. Conference on computer communications. Twentieth Annual Joint conference of the IEEE computer and commanications society (Cat. No. 01CH37213), volume 3, pp. 1655-1663. IEEE, 2001.
Z. Drezner and H. W. Hamacher. Facility Location: Applications and Theory. Springer Science & Business Media, 2004.
Youina C Eldar, Amir Beck, and Marc Teboulle. Bounded error estimation: A chebyshev center approach. In 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, pp. 205-208. IEEE, 2007.
S.-C Fang and S.Y. Wu. An inexact approach solving linear semi-infinite programming problems. Optimization, 28:291-299 -299, 1994.
10

---

Published in Transactions on Machine Learning Research (12/2025)
Table 2: Comparison of algorithmic performance with benchmark solutions for CSIPs.
Problem
Value reported
grad0L value
Time reported (ms)
gradDL. time (ms))
conpel.
Price & Coope
1996
3.4310 x 10-1
3.3631 10-1
4.067
coopeM]
Price & Coope
1996
1.0000 10"
1.0000 10"
3,052
coope
Price & Coope
1996
0,0000 10"
66,5800 x 10"3
1.19 x 10a
3.209
langl
Fang & Wu
1984
4.7927 x 10"1
4.7939 x 10"1
2.173 x 10
28.737
fang2
Fang & Wi
1951
6.9315 x 10"1
6.7982 x 10-1
2.307 10
63.094
fang3
Pang Ar Wm
1934
1.7185 10
1.7183 10
2,128 10
33.526
lerrisl
Ferris
Plil
1989
4.8800 x 10-3
4.9828 x 10
5.99 10a
2.296 x 10
ferris2
Ferris
Phtt
1989
-.7886 10
-.7965 10
7.46 10a
8.177
grerner
Gnerner
1997
10
2.6209 10
8.25 10
1044
goerner5
1997
2.7275 10
2.5906 10
104
1.665 10a
goerneré
Goerner
1097
1,0770 10-3
5,9995 10-5
4.658 10
47.247
honstedel
Honstede
1979
1.2124 10"
1.0424 10
3.984
kortanek1
Kortanck & No
1993
3,2212 10"
3.2184 10"
4.802 104
6,018
kortanek2
Kortanek & No
1993
6.8629 x 10-1
6,8628 X 10-1
1.11 x 10
9.324 x 102
kortanek3
Korlanck & No
1993
1,4708 x 10
2.2281 X 10
1.5 x 10a
95.012
kortanek44
Kortanck & No
1993
5.2083 x 10-3
3.7413 x 10-5
2,666 104
1.443
leon1
Leon et 81 2000
4.5050 X 10
2,4607 X 10
1.29 X LO
7.283
loon2
Leon eb ni 2000
4.1880 x 10
1,0002 X 10
1111 10
12.273
leon3
Leun ml ml. 2000
5,2190 x 10
1,0002 X 10-5
5.12 10a
4.778 x 102
leond
Leon et 6l
2,6028 x 10-3
1.3479 X 10-4
1,381 10a
6.175 x 10
1con5
Leon et 51 2000
1,4257 x 10
4.5963 X 10
4.722 10
14.99
Leon
1.5540 10
1,1692 X 10
10S
7.378
lcon?
2.0997 10
2.5904 10
4.37 X 103
21.41
leon8
2000
5.4222 10
1,0002 10
2.139 10S
5.146 x 10
leon9
2000
L.6388 10
L.6388 10
1,696 10
8.694
leon10
2000
5.3825 10
5.3776 10
2.65 10a
19.612
leoul1
ml ml. 2000
4,8414 10
2.3620 10
1.28 X 10a
15.384
leon
Leon et a1 2000
2.3607 X 10
2.3531 X 10-1
1.26 103
3.972
leon14
Lenn eb al.
2000
6.6667 x 10-1
6.6640 X 10-1
1.4 103
5.151
15on15
Leon et al 2000
6.0667 x 10
66.6557 x 10
9.5 x 10a
4.234
1eon16
Leon ot ml 2000
1.7263 x 10"
1.7177 X 10"
2.2 x 102
3.04
leon17
Leun eb ml
2000
-2,0000
1.9998
1.9
3.4
18on18
Leon et al 2000
1.7500 10
1.7000 10
3.63 1
3.303
19on19
Leon et al 2000
7,8584 10
7.7543 x 10
2.12 10S
4.003
leon20
el.
2000
3.2380 10
3.2316 10
1.68 103
11.713
leon21
2000
-9,9661 10
-9.6700 10a
3.73 10
4.399 x 10
leon22
Leon et a1
2000
-1.042 10
1.0172 10a
5,9 102
4.211 x 102
leon23
Loon ot m1
2000
-3.0857 10
3.0857 10"
5.1 102
16.434
leon24
Leun el ml
2000
-1.1998 x 10a
- -10370 x 101
1.54 10a
7.526
lin1
Lin 05 al
1098
-.8244 x 10"
L.8300 x 10"
2.98 x 10a
3,785
reemtsen
Rnemisen
1991
1.5249 x 10-1
1,5231 x 10
x 1.2689
4.974 x 102
roemtsen2
Roemisen
1991
5.8359 x 10
5.6952 x 10
1.0145 x 10
17.249
reemisen3
Reemisen
199
7.3547 x 10-1
7.3548 x 10
1.6633 x
15.484
reemtsend
Reemisen
1901
1,1401 x 10-2
1,0001 x 10-5
4.5109 x
64.185
reemtsen5
Reomisen
1391
x 10-2
2,8761 x 10-2
1.4513 105
1,950
potchinkov3
Potchinkow
1997
3,4226 x 10-3
5,788
potchinkuyPP.
Polchinnov
1199
9.2940 10-7
2.595
powelll
Todd
-1.0000 10
-L,000 10
9.2 10
3.096
hettich2
Hettich
1979
5.3800 10
5.3742 10
2.68 x T03
3.98
hetticld
Hettich
1979
1.0000 10"
1.0001 10"
3.6 x 102
8.137
hettich5
lettich
1979
5,3800 x 10-1
5,3505 x 10-1
1.1995 x 10
10.909
hettich6
Hettich
1979
2,8100 x 10
2,8163 x 10
5.501 104
1.735
hettich7
Hotbich
1979
1.7800 x 10
1,7776 x 10
4.976 104
7.776
hettich8
Hetlich
1979
2.996 x 10
2,290 10a
1.139 x 10a
hettich9
Lettich
1979
3.4700 x 10-3
3,4791 x 10-3
8,465 x 10
3,837
hettich
Hettich
1579
1.0252 x 10
7,844 x 1
8.695 x 1
pricnk
Prine
1902
-3.0000 10
-3.0000 10
5.1 x
3.191
stilll Stall
(2001)
1.0000 10"
9.9771 10-1
3.9
4.888
userman
1,2802 x 10
4.028
1a
Watson
1983
6.4904 10-1
6.5012 10
1.78 10a
10.116
watson4h
Watson
1983
6.1688 10-1
6.1610 10-1
2.22 x 103
37.654
walsonde
Waison
I983
6.1661 x 10
6.1564 x 10-1
2.82 10a
10.029
watson5
Watson
183
4.3012 10"
4.2966 10"
8.4 10a
17.097
watson7
Watson
1,0000 10"
9.9777 x 10
1.23 x 103
7.534
watson8
Walson
1983
2.4356 10"
2.4356 1
2.189 1
1.627 x 1
watson
Watson
1983
2. 2.7527 x 10
77,0000 x 5
6.952
zhoul Zhou &
Til
1956
2.3605 x 10
2.3505 x 10
3.09 x 10a
42.561
Not. reported in original literature but obtained via SIPAMPL.
This Chebyshev center problem.
11

---

Published in Transactions on Machine Learning Research (12/2025)
M. C. Ferris and A. B. Philpott. An interior point algorithm for semi-infinite linear programming. Mothe- matical Programming, 43:257-2766 276, 1989.
V. Fiacco and Yo. Ishizuka. Sensitivity and stability analysis for nonlinear programming. Anmals of Operations Research, 27(1-4):215 235, 1990. doi:
S. Goerner. Ein Hybridverfahren zur Loesung nichtlinearer semi-infiniter Optimierungsprobleme.. PhD thesis, Berlin University, 1997.
R. Hettich. A comparison of some numerical methods for semi-infinite programming. In R. Hettich (ed.); Semi-infinite Programmming, volume 15 of Lecture Notes in Control and Information Sciences, pp. 112 125. Springer Verlag, Berlin, 1979.
W. V. Honstede. An approximation method for semi-infinite problems. In Hettich (ed.), Semi-infinile Programming, volume 15 of Lecture Notes in Control and Information Sciences, pp. 126 136. Springer Verlag, Berlin, 1979.
K. O. Kortanck and No. A central cutting plane algorithm for convex semi-infinite programming problems. SIAM Journal on Optimization, 3(4):901 918, 1993.
T. Leon, S. Sanmatias, and E. Vercher. On the numerical treatment of linearly constrained semi-infinite oplimization problems. European Journal of Operalional Research, 121:78-90 09777191127 2000.
C.-J. Lin, S.-C. Fang, and S.-Y. Wu. An unconstrained convex programming approach to linear semi-infinite programming. SIAM Journal on Optimization, 8(2):443 446, May 1998.
Zhuanghua Liu, Cheng Chen, Luo Luo, and Bryan Kian Hsiang Low. peroth-order methods for constrained nonconvex nonsmooth stochastic optimization. In Forty-first International Conference on Machine Learn- ing, 2024.
C. A. Micchelli and T. J. Rivlin. A survey of optimal recovery. In Optimal Estimotion in Approzimation Theory, pp. 1 1-54. Plenum, New York, 1977.
P. Paruchuri and D. Chatterjee. Attaining the Chebyshev bound for optimal learning: leammni a numerical algorithm. Systems & Control Letters, 181, 2023. paper no. 105648, doi: 2023. 105648
A. W. Potchinkov. Design of optimal linear phase fir filters by semi-infinite programming technique. Signal Processing, 58:165 180, 1997.
C. J. Price. Nonlinear Semi-infinite Programming. PhD thesis, University of Canterbury, New Zealand, August 1992.
C. J. Price and D. Coope. Numerical experiments in semi-infinite programming. Computational Optimiza- tion and Applications, 6:169-189. 189, 1996.
R. Reemtsen. Discretization methods for the solution of semi-infinite programming problems. Journal of Optimization Theory and Applications, 71(1), 1991.
G. Still. Discretization in semi-infinite programming: the rate of convergence. Mathematical Programming, 91:53 69, 2001.
M. J. Tax and R. P. W. Duin. Support vector domain description. Pottern Recognition Letters, 20(11-13): 1191-1199, 1999.
M. L. Todd. Interior-point algorithms for semi-infinite programming. Mathematical Programming, 65:217- 245, 1994.
A. I. Vaz, E. M. G. Fernandes, and M. P. S. F. Gomes. Sipampl: Semi-infinite programming with ampl. ACM Transactions Mathematical Software, 30(1):54-75) 2004. doi: 10.1145/974781.97477
12

---

Published in Transactions on Machine Learning Research (12/2025)
A. Ismael F. Vaz. CSIP (Convex Semi-Infinite Programming) Solver. hww..oor...ni..ott..ai.iee..e..e csip.html 2001. University of Minho, Portugal.
Andreas Wächter and Lorenz T. Biegler. On the implementation of an interior-point filter line-search al-
gorithm for large-scale nonlinear programming. Mathematical Programming. 106(1):25-37, 2006. doi:
10.1007/110007-004-055553 URL htttps//00o..oog/0....0000000000
G. A. Watson. Numerical experiments with globally convergent methods for semi-infinite programming problems. 1983. URL
Yong Xia, Meijia Yang, and Shu Wang. Chebyshev center of the intersection of balls: complexity, relaxation and approximation. Mathematical Programming, 187(1):287-33) 2021.
J. L. Zhou and A. L. Tits. An SQP algorithm for finely discretized continuous minimax problems and other minimax problems with many objective functions. SIAM Journal on Oplimizalion, 6(2):461-48)) 1996.
Zhou, C. Doyle, and K. Glover. Robust and Optimal Control, volume Prentice Hall, 1996.
13

---

A Lipschitz solutions to multiparametric programming problems
Let y N" and let L2(R" xRRRR) denote the family of symmetric bilinear maps from R X into R. Recall that mapping y RR" IR is locally Lipschila if al each point IR" there exists a neighborhood 6 a and L > 0 such that -=(==))((==") & L I|' =''ll whenever z',z" E 6. The constant L depends on and 6 in general, and L is the Lipschitz modulus of the map 4. In particular, if y is twice continuously differentiable, then y is locally Lipschitz.
Recall that a set-valued map F: : Ry' is mapping F : - 2 in the standard sense; i.e., F assigns to each vector E R² subset RY Such a set-valued map is uniformly compact around E R if there is a neighborhood O containing such that Up Fly") bounded.
Consider the parametric nonlinear program
minimize
()
fi(5.0) 0 for i 1, I....,P. &ER
A1
subject to
along with the data
A1 a)
C R" is a non-emply and compact sel,
A1 b) fo R x R
is a contimuously difforentiable (objective) function,
A1 c) : x Rm R is continuuusly differentiable (constraint) function for each i = I.....
The feasible set for A is the set-valued map Steas O = R', the value of Al is the function O 9 - Sopt (0) = value of R, and the optimizers are given by the set-valued map Sopt O = R2' defined by
(0) Ey E R' (y, Sva)
Proposition A.1 ( FFacco & Ishizuka, 1990 For 0 ① and point & (O), let ((g) = i {I..... filE. 0) = denote the set of active constraints
Theorem 4.2)). Consider Al along with its associated data.
at (0.E). Suppose that there erists a vector u e RR such that (V& filE. u) < 0 for each i E (()) F and that
the sat-valued map Steas()) is uniformly compact around 0. Then the function (-a(.) corresponding to A1 is locally Lipschitz around 0.
B Convergence Analysis
In this section, we provide brief analysis of the convergence properties of the gradOL. We rely on the framework of randomized smoothing and generalized Goldstein stationarity. Below, cite the relevant definitions and auxiliary results from Liu et al. (024).
B.1 Definitions and Notations
Notation. Let c R=+1 be a convex and compact set with diameter bounded by B. As before, we denote the Euclidean norm by || |].
Note that the outer-level objective is to maximize (8()) (see (9) with respect to the uncertainty variable ă. To retain generality while simplifying notation, we introduce slight abuse of notation and define F = -8. We also relabel the uncertainty variable ii as preserving the structure of the original problem while only modifying symbols. Since gradOL seeks to maximize B(T)) over 77, this transformation yields the equivalent minimization problem
minF(x). XEX
Laangearrin-PPromoviz 4n other words, the Mangasarian Fromovitz constraint qualification conditions hold E.

---

Published in Transactions on Machine Learning Research (12/2025)
Smoothed Objective. Consider the problem minF(x), where F is locally Lipschitz established in xel
Theorem 3.1 but potentially nonconvex and nonsmooth. We utilize the d-smoothed approximation:
F (x == Eu-Umir(B(O.1)) [F(x + Su)
As established in Liu et al. 2024), F& is differentiable with a Lipschitz continuous gradient. Specifically, if F is G-Lipschitz, then Fs La-smooth with constant Ls eGvn+I for some dimensionn-dependent constant c.
Generalized Gradient Mapping. For a parameter 0, a point x It and a gradient vector o E R the generalized gradient mapping is defined as:
x arg min (u. v) 1 lly x112)
G(,,u,y) y
yE3r
2y
This mapping serves as proxy for stationarity in constrained optimization.
B.2 Preliminaries and Assumptions
Lemma B.1 (Gradient Bound). If Ru+1 - R is L-Lipschitz, then [|Vh(x)]I & wherever the gradient erists.
Assumption (Inexact Gradient). At any query point XR, the algorithm receives an inexact gradient estimator UR satisfying:
|| (Fx(x)) &
Assumption (Tipschitz Continuity). The function Fs is G-Lipschitz on X. Consequently, by standard [VFx(x)]] & G for all x e x.
propertics (Lemma B.1
B.3 Main Convergence Result
We analyze the output F(XR), where is drawn uniformly from(O....,TTIIII. of gradOL and T is the number of iterations.
Theorem B.1. Let step size y cGVV4I' Under the stated assumptions, if the number of iterations T satisfies
Bc
T > 8(22 - 4G2 - 8e2)'
assuming the denominator is positive, then the iterates satisfy the expected stationarity bound E[]]G(XR, (Fa(XR), y)ll E
Proof. Step 1: Descent Lemma with Inexact Gradients. Since F La-smooth with L, cGv the standard descent. lemma implies:
8
La || 121 2
Fo(x++1) & Fo(x)) + (VFs(x;) -x))
Lay²
Fo(x,) - ((G))-((VFs())) G(x, + |[ 11, 211
Substituting if into the inner product:
(VFs(x,), G(X,, Dt, v)) -u,, G(x, x)) (v, VF5(xFF(() ((x,,
Using the property of the gradient mapping that -ur, G(x,, y)) & -1 y)12 (Lemma C.2 Liu et al. 2024h) ) we have:
Fo(x41) & Fo(x,) - (x- (y-Lor²) |[Gxx, 7)12 y(u, VF5(1)),Gx,, br>))
Lov2)
15

---

Published in Transactions on Machine Learning Research (12/2025)
Step 2: Error Decomposition. We bound the inner product term using Cauchy-Schwanl and Young's inequality:
(u, - ((x,)) 7)) = (ur VFs(x)). G(x, VFo(x)).))
+ ||, Vlo(x) 1r,) G(4, (x)
& (1r VFo(x)), G(x, (Fo(x)).))) +| Vxs(x;)]1
Using Cauchy-Schwarz Schwarz and Young's inequality the RHS above
(u+ VFa(x)), G(x,, Ur, y)) 22ll. VFs(x:)
3
2 1I vF.
Taking expectations and applying Assumption
( 2 2
3y e² + EII (x)(x)))))11)
E[I u,,)) < E[Fo(x;) - Fo(x++1)) +
2
Step 3: Telescoping Sum. Summing from 0 to 7 1, dividing by T, and using y 1/48 (specifically y
such that the coefficient on the LHS becomes y/2:
cG cGvn+T
Y [[]]G((RR.UR UR. x)1 &
Fs(xo) Fx(XT)
3y e² Y E[]]G(RR VFo(ER).
T
Rearranging and bounding Fo(xo) Fo(XT) & GB:
2GB
E[][G(xR. UR. UR. r)]
<
+ 3e + E[]]G((xR (F((()).
A2
Ty
Step 4: Final Bound. We bound the true gradient mapping term the RHS using the Lipschitz constant G (using [[((,, v), & [|VF]| & G using Lemma B.1). Substituting this into A2
2GB
E[[[G(XR, UR. 1)
+ 3e G².
Ty
Finally, we relate the true mapping back the approximate mapping:
E[]]G(XR, (Fs(x))>>11
2E[[[RR - -FF((x))11 (EII)G(ERR
22 +2
12B
+ 32 + G²) Ty
4GB + 4G + Se?.
Ty
We obtain the sufficient condition for the squared norm to be bounded by e2:
4GB + 4G² + +82 2 T
4GB
Ty
7(E2 -G2 8)2)
Substituting y cGvneT yields the stated result.
C Iterative Sampling Routine
By sampling N many u(s) from we replace the infinite constraint in (11) by maxinization over con- strained minimization problems, solve the resulting convex program to get si, and record fy Repeating M times yields an empirical distribution of fv; we accept N once the fraction of trials within ö of the true optimum f reaches 80%.
16

---

Published in Transactions on Machine Learning Research (12/2025)
Algorithm 2 Iterative Sampling for CSIP
Require: N, M E N, tolcrance > 0, true value f"
1: for ==........ do
Draw ii.d. samples {u)) jim1 c K
Solve
fN
min (s.x)
s.t. I|u x112 -
4: end for Compute empirical confidence
1
PN
10 f*
M
6: if PN > 0.8 then
7: N is sufficient
8: else
Increase N and repeat
10: end if
D Hyperparameters
Hyperparameters for gradDL are chosen after experimenting with the benchmark problems. We observe that runtimes are somewhat robust to some of the given parameters, which can be chosen as per the problem at hand.
Table 3: Hyperparameters for gradOL
Category
Value
Learning rate (17)
1 x 10-1
Tolerance (8)
1 x 10-3
Max Epochs (M)
x 10
Barrier Parameter (ar)
1 x 105
For MSA-Simulated Annealing, use Ipopt Optimizer Wächter & Biegler 2006) for the inner minimization, the hyperparameters are given in hyperparameters are given
As described in the routine we adapt for Iterative Sampling in C the
Table 4: MSA Simulated Anncaling
Table 5: Iterative Sampling
Category
Value
Category
Value
Maximum iterations
1 10
Maximum iterations (M)
1 x 102
Initial lemperature
1.0
Number of Random Samples (N)
10 1x 10a
Cooling rate
9.95 x 10
Confidence Threshold
8 x 10-1
Tolerance (8)
1 10
E
Ablation Study
We report separate ablation tables for five representative Chebyshev center problems, examining variations in learning rates and barrier parameters. The comparisons in Table [ highlight the sensitivity gradOL to these hyperparameters. Notably, gradOL relics on only two scalar hyperparametors, cach offering an intuitive sense of how the algorithm's behavior changes as the parameters are adjusted. In particular, reducing the learning rate from its default. setting (n 10-pccyy leads to slower convergence. Conversely, while
17

---

Published in Transactions on Machine Learning Research (12/2025)
larger values of 17 may accelerate convergence, they often induce instability in the form of oscillatory zig-zag optimization trajectories.
On the other hand, the choice of the barrier paramcter a directly affects the accuracy of the gradient estimates required for the outer maximization of B. In particular, a must be sufficietlyy large to ensure that the inner minimization solved with high fidelity, thereby yielding reliable gradient information for the outer problem. This effect is also reflected in ablation study.
Our ablation study considers five benchmark representation problems: leon9, kortanek1, leon10, reemtsen3, and hettich2. Unless otherwise specified, we use the default parameter setting (17, a) = 10%). We then conduct a simple grid search over learning rates 0.01, 0.1, 0.5 and penalty paramoters 104. 106.
As shown in Table 6 the results corroborate the expectation that larger values of yield accurate gradient estimates, while smaller learning rates improve convergence at the cost of increased runtime. The problems exhibit stronger sensitivity to indicating that the ability to compute accurate gradients (con- trolled by a) largely determines whether the optimization succeeds. In contrast, the adverse effects of roducing the learning rate can, in principle, be offset by longer runtimes. However, when a is insufficiently small, the optimizer may fail to identify the correct solution and can miss the optimum entirely.
Table 6: (Oblained Value / Runtime) for different Chebyshev Center problems leon9
kortanek1
10-2
10-1
5 10
"
10-2
10-1
5 x 10-1
a
a
0.1623
0.1644
x 10-6 8.32 102 ms
3.2175
3.1198
3.1198
104
104
4.259 102
56.573 ms
2.028
2.528
2.7552
0.1421
0.16338
0.1421
2.9032
3.2184
3.0004
10a
103
55.837 ms8
8.694mm
8.466 x 102 ms
1.782 mss
6.018 ms
7.011 ms
0.0856
0.0849
0.1128
2.8152
3.2211
3.2052
106
106
842.124 ms
55.451 mas
54.495 mss
1.784 ms
1.819 mss
1.802 ms
Optimal Value = 0.16338
Optimal Value = 3.2212
leon10
reemtsen3
7
10-2
10-1
5 10
7
10-2
10-1
5 x 10
x 10-6
1 10-6
1 10-6
0.7125
1 x 10-6
1 x 10-6 40.726 mss
104
104
6.926 ms
6.051 ms
6.104 ms
4.46 x 10 ms
3.87 x 102 ms
0.4778
0.5377
1 x 10-6 6.166 ms
0.7352
0.7354
1 x 10-6
105
105
20.704 ms
19.612 mss
1.16 10 ms
15.484 ms
3.89 102 iss
0.5372
x 10
x 10 6.439 ms
0.7351
0.7352
x 10
105
10c
143.222 ms
11.366 ms
1.34 10
1.307 10 ms
52.71 x 10 ms
Optimal Value
0.5382
Optimal Value 0.7354
hettich2
10-2
10-1
5 x 10
a
0.48513
0.47269
0.0001
104
2.544 ms
2.017 ms
2.174 ms
0.5355
0.53742
0.5372
105
7.826 ms
3.98 ms
67.937 ms
0.5307
0.5378 1.4 10 ms
0.53834
106
3.702 x 10 ms
8.579 10 ms
Optimal Value = 0.538
18


Reviews:
[{"review_id": "vNmxzApBBv", "reviewer": "Reviewer_L2BP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript clearly defines and motivates the research problem, the Chebyshev center problem by situating it within the context of prior work. The theoretical analysis is aptly initiated from the foundation of the finitary problem, as defined by Paruchuri & Chatterjee (2023). A key theoretical contribution of the paper is the detailed proof of the Lipschitz continuity of the inner objective function with respect to the outer variable. This proof is crucial as it forms the theoretical foundation for the proposed gradOL algorithm. Building upon this theoretical groundwork, the work effectively employs automatic differentiation tools for gradient computation and provides a complete description of the algorithm. The study then conducts extensive benchmarking on a series of Chebyshev center problems, convincingly demonstrating the algorithm's accuracy and marked efficiency. Furthermore, the applicability of the method is successfully extended to the more general class of Convex Semi-Infinite Programming (CSIP) problems, with experimental results robustly validating its high performance in this broader context.\n\nThis manuscript presents a highly competent and valuable contribution to the field of optimization. The problem addressed in this paper is classical, while the proposed solution demonstrates a notable degree of innovation. The theoretical foundation is laid out with commendable rigor, particularly in establishing the Lipschitz continuity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper provides a detailed and accurate proof of the Lipschitz continuity, which is both the core theoretical conclusion of the paper and the crucial foundation for the core algorithm of the research. The proof is presented with such thoroughness and precision that its validity is clear. This high standard of rigor enhances the confidence in the paper's theoretical findings.\n\nThe algorithmic evaluation is rigorous, as it employs a substantial set of justified metrics across a sufficient number of comparable problems and includes comparisons with a wide array of existing methods. This is supported by detailed tables of experimental results and specific discussions thereof.\n\nOverall, in my opinion,  the claims made in the submission supported by accurate, convincing and clear evidence.", "audience_yn": "Yes", "audience_explanation": "The paper introduce a novel approach to solve Chebyshev center problem. The Chebyshev center problem is a significant and long-standing problem in many fields.First, the Chebyshev center problem is valuable in functional learning. And beyond the field, the manuscript itself also mentions the application of the Chebyshev center problem can involve:\nrobust optimization for managing uncertainty, sensor network localization for estimating node positions and location problems to optimize placement strategies.\n\nThis reviewer believe that the research can attract the interests of some people.", "requested_changes": "There are some issues that need to be addressed before it can be considered for publication. If the following problems are well-addressed, this reviewer believes that the essential contribution of this paper are important for the optimization, control and so on.\n\nThere is at least one Spelling error in the manuscript, such as, in page 6, under the Theorem 2.1, “\\\\( ]0,+\\infty[ \\\\)” would be “\\\\( [0,+\\infty] \\\\)”. And “functionsn” would be “functions”. Please check the manuscript carefully. This manuscript requires careful editing and particular attention to English spelling.\n\nAnd in page 7, Theorem 3.1, “the value of (10)” may not be equal to “\\\\( (\\\\sup_{\\\\bar{u} \\\\in K^{n+1}} \\\\mathscr{G}(\\\\bar{u}) )^{\\\\frac{1}{2}} \\\\)”.  “the value of (10)” is the square of the Chebyshev radius but that value in Theorem 3.1 seems to be the Chebyshev radius itself. And also please check other parts of the manuscript to find whether there are similar issues.\n\nRegarding the computational complexity of gradOL, I appreciate that a full convergence analysis is beyond the scope of this work. However, since the paper have provided a preliminary complexity bound, it would be valuable if you could include a brief sketch of the analysis or the key ideas adapted from Liu et al. (2024) to support the plausibility of this claim.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lL14Nao57W", "reviewer": "Reviewer_LH3U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper leverages modern automatic differentiation techniques to exploit gradient-based optimization to directly solve the Chebyshev center problem arising in optimal function learning and convex semi-infinite programming (CSIP). The main contributions claimed include: 1) Firstly introduce the gradient-based framework gradOL for Chebyshev center problems while previous methods being mostly sampling, relaxation or non-gradient.\n2) Theoretically proves optimality the Chebyshev center problem of under strong convexity. \n3) Empirically demonstrate the accuracy and efficiency of gradOL on broad benchmarks.\n\nKey strengths: novel idea of leveraging autodiff for CSIP/Chebyshev center; broad empirical results; practical implementation; relevance to optimization and learning community\n\nKey weaknesses: assumptions (e.g., strong convexity) may limit generality; lack of ablation studies: The sensitivity to hyperparameters (learning rate $\\eta$, barrier parameter $\\alpha$) is discussed qualitatively but not systematically analyzed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "1) The paper reports extensive benchmarking indicating significant speedups and good performance.\n\n2) The paper provides proofs of Lipschitz continuity and convergence under strong convexity (as claimed) in Theorem 3.1.", "audience_yn": "Yes", "audience_explanation": "The Chebyshev central problem addressed in this paper has numerous applications, including data fitting and robust optimization (as the paper states). Furthermore, this paper introduces a novel and practical gradient-based solver, which is likely to pique the interest of researchers in machine learning, optimization, and computational mathematics within the TMLR community.", "requested_changes": "1) Add ablation studies on the influence of hyperparameters.\n\n2) Clarify the precise assumptions under which your method is guaranteed to work (e.g., strong convexity, smoothness, differentiability of supremum-operator). Discuss scenarios where these assumptions may not hold and how method behaves. Ideally, discuss these in a separate section.\n\n3) It needs to be clarified in the abstract or introduction that what is being solved is not the original Chebyshev center problem, but an approximation of its finite-dimensional version.\n\n4) Table 1 can be placed at the end of the article or in the appendix.\n\n5) Add preliminary about automatic differentiation in the Preliminaries.\n\nAll suggestions above will simply strengthen the work in my personal view.", "broader_impact_concerns": "No direct ethical risks are apparent.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DLDQLVaYkh", "reviewer": "Reviewer_bE3N", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a gradient-based algorithm to solve the Chebyshev center problem via a novel equivalent finite-dimensional formulation of the original problem and the auto-differentiation algorithm. The local Lipschitz continuity of the objective function is also proved to justify the use of the (sub)gradient-based optimization algorithm. In contrast, most of the existing works in the literature solve some relaxed version of the original problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper states the claims with theorems with proof, detailed algorithmic framework, and clear presentation.", "audience_yn": "Yes", "audience_explanation": "People who are working on the gradient-based optimization and function learning may find this paper interesting", "requested_changes": "1. Why the authors include ``optimal function learning\" in the title since the main problem considered in this paper is just the Chebyshev Center problem. \n\n2. The key advancement lies in the new formulation of the problem, i.e., Eq. (5), which is a consequence of the recalled Theorem 2.1 in the paper. This should be mentioned early in the introduction and in the abstract. \n\n3. The sections are not separated properly. For example, the reformulation of the problem (Eq. (9)) could be put in Section 2. In addition, the section titles are too abstract and should be made more explicit. \n\n4. The Lipschitz continuity is valid when the inner optimisation problem is solved exactly. Will the implemented optimization solver in Algorithm 1 influence this property?", "broader_impact_concerns": "NA", "additional_comments": "NA", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)