A Computationally Viable Numerical Gradient-based Technique for Optimal Covering Problems
Authors: Gokul Rajaraman
Debasish Chatterjee
Venue: NeurIPS 2025 poster ()
Keywords: Optimal cover
Optimal n-net
Sensitivity of nonlinear programs
Numerical gradient algorithm
Primary area: optimization
TL;DR: We present a viable algorithm for the problem of optimally covering a compact set with a fixed number of balls using results from sensitivity analysis and nonsmooth and nonconvex optimization.

Abstract: The problem of optimally covering a given compact subset of $\mathbb{R}^N$ with a preassigned number $n$ of Euclidean metric balls has a long-standing history and it is well-recognized to be computationally hard. This article establishes a numerically viable algorithm for obtaining optimal covers of compact sets via two key contributions. The first is a foundational result establishing Lipschitz continuity of the marginal function of a certain parametric non-convex maximization problem in the optimal covering problem, and it provides the substrate for numerical gradient algorithms to be employed in this context. The second is an adaptation of a stochastically smoothed numerical gradient-based (zeroth-order) algorithm for a non-convex minimization problem, that, equipped with randomized restarts, spurs global convergence to an optimal cover. Several numerical experiments with complicated nonconvex compact sets demonstrate the excellent performance of our techniques.

A Computationally Viable Numerical Gradient-based Technique for Optimal Covering Problems
Gokul Rajaraman
Debasish Chatterjee
Department of Mechanical Engineering
Centre for Systems and Control ITT Bombay
IIT Bombay Mumbai 400076, India 22b45178iitb ac.
Mumbai 400076, India dchatterGiitb. ac in
Abstract
The problem of optimally covering a given compact subset of R with a preas- signed number of Euclidean metric balls has long-standing history and it is well-recognized to be computationally hard. This article establishes a numeri- cally viable algorithm for obtaining optimal covers of compact sets via two key contributions. The first is a foundational result establishing Lipschitz continuity of the marginal function of certain parametric non-convex maximization prob- lem in the optimal covering problem, and it provides the substrate for numerical gradient algorithms of stochastically smoothed numerical gradient-based (zeroth-ordes algorithm for non-convex minimization problem, that, equipped with randomized restarts, spurs global convergence to an optimal cover. Several numerical experiments with complicated nonconvex compact sets demonstrate the excellent performance of our techniques.
employed in this context. The second is an adaptation
Introduction
Optimal covering of sets is an important problem that arises naturally in several fields of science and technology, including learning and approximation theory, computer science, signal processing, information theory, combinatorics, communication, sensor networks, multi-agent systems, cyberphys- ical systems, etc. sensor network, for instance, given a collection sensors having preassigned sensing radius and set that must be enveloped by the sensors, an important engineering question find an optimal collection of points for placing the sensors ensure complete coverage of the given set. An identical problem arises for the coverage of given geographical region with cell-phone towers in order to maximize network availability in the region. In information theory, assuming that one can accurately decode messages from certain set within preassigned maximal error tolerance for each, it is important to determine the number of 'signals' that are necessary for accurate decoding of all the messages; this is once again a problem of optimal covering of the set of messages with collection of 'signals".
The covering problem appears in various forms, and perhaps its most common variant is captured by the following situation. For a given non-empty (and possibly uncountable) compact set M R O, one finds finite set FF C IR that is at most e-distant from any point in M. Such a minimal set is an g-nel and its cardinality the so-called E-covering number of the set M; see, e.g., (Kolmogorov and Tihomirov, 1961) for early detailed exposé of related topics and (Alimov and Tsar' kov, 2021, Chapters 15 and 16) for a more recent treatment. closely related and equally relevant variant of covering is its resource-constraince n metric balls, one must find the minimal radius and a placement the n centers of the balls such that their union covers M. Such collection of the centers is commonly known Chebyshev net
and preassigned
budgeted version: Given number
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

of cardinality (Alimov and Tsar'kov, 2021, Definition 15.3). We address this particular problem in our current work.
Formally, given a non-empty and compact M C TRN, we seek to solve the optimization problem
c(M,n)
min max min ll - zill- (NNN)))))RRN NEM il.....
(1)
For an n-tuple of centers (.. Xn) RN*= and y E M, ming-1,.... lly xi| determines the distance of y from (z=) Consequently, the number maX ming=11..... |y - xill is the maximum distance of points in M from the collection Uh=1 {ma), and the outer minimization in (1) optimizes this maximum distance over the centers (æ1,-... J. The quantity c(M,n) n) is known as the covering radius of the set M with n metric balls as defined in (Alimov and Tsar kov, 2021, p. 300); solving (1) yields an optimal n-point representation
Chebyshev n-net - of M, and
<(M,n) n) is the error guarantee in such a representation.
Chebyshev n-nets are especially useful for estimating errors in function learning in the presence of certain regularity properties. For instance, consider a target function f . + R that is known to be Lipschitz continuous with modulus Lo but is otherwise unknown, and suppose that Chebyshev n-net Fof M and the set of values {f(z) x E F of f on F are available. Then a tight estimate of the value of f finding y+ E arg min x ||= - y|l and then calculating (V+). By an identical reasoning, for Hölder continuous f of modulus C > 0 and rate a E 10. 1f, the corresponding error bound is Cc(M, n)). Similar arguments in optimization problems involving uniformly continuous objective functions permit the derivation of quantitative estimates of true optima from estimates over finitely many points.
generic y E M may be obtained, within absolute error margin of [ac,M, n), by
In several applications of covering, the centers of the metric balls may be restricted to lie within M, in which case, the problem (I) should be modified to
é' (M, = min
min 1I (#L--.,))MM yEM I.....
x; ||-
This constrained version is relevant in settings where the representative points must strictly belong to the set under consideration. The triangle inequality immediately yields the sandwich relation ((M..) & <(M,n) & n). Our efforts are focused on the numerical viability of (1) for compact M; similar methods can be adapted with minor modifications to address (2) if M is convex.
Contributions
The problem (1) is challenging (NP-hard) even in the n 1. Indeed, this situation is the so- called Chebyshev center problem (Alimov and Tsar'kor kov, 2021, p. 296) and is of central importance in optimal function learning (Binev et al., 2024), signal processing (Micchelli and Rivlin, 1977; Eldar et af., 2008; Wu et al., 2013). approximation theory (Alimov and Tsar' kov, 2019; Foucart and Liao, 2024), and host of other disciplines. Despite its complexity, it turns out that the Chebyshev center problem admits a numerically viable solution technique (with excellent approximation properties) by leveraging certain convexity attributes present therein, and has been recently studied in (Paruchuri and Chatterjee, 2023). The case of n > 1 considered in the current article is significantly more difficult: of course, it is challenging (NP-hard), and in addition, does not appear to be amenable to any simplification via convexity. Moreover, while the Chebyshev center of M is unique for the Euclidean norm, the Chebyshev n-net problem may not yield unique solutions."
Since (1) is well-known to be computationally challenging, we focus attention on the develop- ment of viable algorithm based numerical gradients (i.e., zeroth-order algorithm) with good approximation properties to solve (1):
To this end, we demonstrate that the inner max- max-min problem in (1) admits reformulation that yields good regularity properties parametrically in (æ1...., I,,) corresponding to the outer minimization
IIn sensor and communication networks, for instance, the radius of sensingfoommuniatiion of each sensor dependent on the power at hand, which lends a measure of flexibility in altering the indicated radius. 'For instance, the Chebyshev center of M is identical to the Chebyshev center of the convex hull of M, but that false general for Chebyshev n-nets for n >
"In few cases of M, dosed-form expressions for Chebyshev n-nets are known; see, e.g., (Ushakov and Lebedev, 2015).
2

---

under mild hypotheses; this is our first main result Theorem 3.2. The indicated regularity property enables and justifies the deployment of a numerical gradient-based (zeroth-order) algorithm in the variables (xI...., IIn) to arrive at a solution to (1) itself. To our knowledge, ours is the only instance of a gradient do not necessarily possess special structure.
approach to finding Chebyshev n-nets for compact subsets of TR-V that
In order obtain the indicated regularity properties, the key technical tools employed here are derived from the field of sensitivity of optimization problems (Fiacco, 1983; Fiacco and Ishizuka, 1990) or variational analysis (Dontchev and Rockafellar, 20.4). We establish the crucial Lipschitz continuity of the (parametric) inner max-min problem in (1) with respect to (#1,.... , Fx)) around optimal points of the outer minimization; this lays down the foundation for the deployment of a range of numerical gradient- based algorithms for the outer minimization.
Numerical gradient-based algorithms for nonlinear programs not expected to converge global optimizers in general. Here we lift off-the-shelf a recent zeroth-order algorithm that stochastically smoothes the numerical gradients and explores the decision landscape in search for global optima; the precise complexity bound appears in our second main result Theorem 3.6. More refined algorithms involving, e.g., momenta for convergence to global optimizers topics of subsequent investigations. This is the first instance, to the best of our knowledge, that powerful tools from sensitivity theory have been employed in conjunction with numerical gradient-based algorithms to address the Chebyshev n-net problem.
The efficacy of our algorithm depends on the availability of accurate solutions to the inner max-min problem (after an appropriate reformulation) for each fixed (æ1..... xn). The indicated parametric max-min problem happens to be non-convex despite our reformulation, and the speed of execution of our algorithm depends on how quickly these globally optimal solutions are made available. Our numerical experiments indicate that despite the lack of convexity, our algorithm (including resets) gives excellent performance even for relatively complicated nonconvex sets M see $4 for details. Scalability of our algorithm with increasing dimensions N and number n of centers remains a challenging issue: while the numerical gradient-based algorithm for the outer minimization scales in these variables as ON n2) the inner max-min is non-convex and remains the chief computational bottleneck in our algorithm.
Since the Chebyshev n-net problem is understood to be hard, several randomized algorithms to approximately solve (1) have been developed; see, e.g.. (Har-Peled, 2011, $5.3) for an account. While many of these randomized techniques involve independent and identically distributed sampling," more complicated history-dependent stochastic iterative algorithms have been advanced in the literature for special cases see, e.g., (Ushakov and Lebedev, 2015) (and the references therein) for the case of = 3. Other techniques to solve the optimal nenet and related problems relevant to theoretical computer science and computational geometry may be found in (Malysheva, 2020; Yu, 2021; Voronov et al., 2023). It is, of course, possible to employ zeroth-order methods (such as simulated annealing (Robert and Casella, 2004)) that do not rely any regularity of the inner max-min in (1), However, the Lipschitz regularity of the parametric max max-min -in (Thcorem 3,2) paves the way for fine-tuned algorithms that exploit this regularity compared to typically slow annealing techniques; such, Theorem 3.2 constitutes the key point of departure of our contributions from the current literature.
Organization
This article unfolds follows. Several preparatory results contained in $2; they are employed in the two main results centered around our key Algorithm 1 in $3. Numerical experiments are presented in $4 and the technical data corresponding to both our theoretical results and numerical experiments are collected in $A-
2 Preliminaries
is intuitive to expect that an optimizer (et....,I7, of (1) should be restricted to a bounded set that contains M. Recall that c(M, 1) is the Chebyshev radius of M, and an optimizer 2" of (1)
Methods relying on independent and identical sampling typically suffer from sharply worsening performance the dimension rises due concentration of measure effects; see (Das al., 2022) for details.
3

---

for n 1 is the Chebyshev center of M. In other words, the Chebyshev center of M provides the best single-point representation of the set M, minimizing the worst-case distance to all points in M. There is neat relationship between the n-net problem (1) and the Chebyshev center of M established in the following proposition, a proof of which is SB.
Proposition 2.1. If ( -.11...,,;pp ..) is an optimizer of (1) and if x" is Chebyshev center of M, then
|| - - < 2c(M.1) for all i E (1....nn.
(3)
In other words, without loss of generality, all optimizers of (1) can be restricted ball of twice the Chebyshev radius, centered at the Chebyshev center. Henceforth, we denote this ball by ((M) whereby, follows that (4 (,1,...;,E.) E B(M)"
This result is useful for generating initial guesses and bounding our search space when implement- ing our algorithm, which will be discussed in subsequent sections. Inspection of (1) reveals that min.-1.....n lyy z is non-convex in (ZI...., Zn) for fixed and vice versa.
As indicated in $1, reformulate the problem in way suitable for the construction of a numerically viable algorithm to extract near optimal solutions. To this end, we first note that the geometric implication of the problem guarantees strict feasibility for any compact M. Moreover, for fixed set of centers, the inner maximization always has a finite optimal value owing to the compactness of M.. We now present straightforward reformulation of (1) using slack variable, which, despite its simplicity, provides the problem with a richer structure for computational viability. Since the square of the norm ensures continuous differentiability, property that will become important subsequently, we work with the squared norm by noting that
min lyy x2|l2 m E
E by x211² for all I...., n).
which immediately leads to
c(M,n))²
min
max
max YER
t
(21 Fn ERN JEM
(4)
subject to
t t- x,
00 for all i 1,...,
It is natural to seek unification of both inner maximizations into single maximization over the Cartesian product of their respective domains. The following proposition, whose proof in $B, establishes that this unification is valid for the given problem.
Proposition 2.2. For a given set of centers (II,)..,Itn) E RRN ((((,)))) is an optimizer of
max maxxmaax& maxf E R | 11y - x2112 < 0f all i 1, m y yEM}
(5)
and (t*, y²) ) is an optimizer of max{1 (1,)) E M and L- Ily- r.11² 0 for all i 1,....;1
(6)
then t t* That is, both (5) and (6) are feasible and have the same optimal value.
In view of of Proposition 2.2, from this point forward, we adopt the following reformulation for the n-covering radius:
cM,n)²
min ( ERRNn
g (II1,..,,Ia))
where
9 (TI,...,, == max (1,)) E Mnd y xil1? < O for all 1,...,
Evaluating & entails solving a nonconvex problem, and the gradient of is difficult calculate analytically, especially without imposing further structure on the inner maximization. There are several 'gradient-free' algorithms such as simulated annealing via Markov chain Monte Carlo to ensure probabilistic convergence to global minima, simplicial algorithms (e.g., the Nelder-Meade) for deterministic convergence global minima, of G, etc. Although these algorithms do not require further structure on M and may be easy to implement since they only employ point evaluations of
'The Chebyshev center is necessarily unique for due strict convexity of the Euclidean norm.

---

G, numerical heape//suuurradeebbbbeeeeee algorithms tend to furnish solutions more efficiently and scale well relative to the size of the problem data, provided the objective function satisfies certain regularity conditions. An algorithm centered around numerical gradients is our target.
To advance in this direction, we impose the condition that M is the intersection of O-sublevel sets of finitely many known continuously differentiable functions in the following way. Let OI...., On E RN be open sets containing M, let ( : Oj IR for j l,... be continuously differentiable functions, and suppose that M is realized as
M = {y E ERRN N (v)(t) & O for j = 1, ...... m}--
This allows us to write G the negative of the optimal value function of standard parametric optimization problem
-9 (z1,.... .,)) min (1,z)
t
- ly - 2ill 2 < 0 for all = 1,..., Pi-n(y) <0 for all i = n + 1...., + k
(8)
subject to
120, 0,
(t.
Example 2.3. The problem (8), for a given choice of (x (.1....... J..) need not have strict local optimizers in general. To see this, let M C C be disc of radius R > 0 centered at the origin and let n = 1. The evaluation of 9 at the origin leads to non-isolated optimizers for (8) since any pair of the form (R² v²" with ||y" = R is an optimizer.
Remark 2.4. Note that it is not necessary to explicitly impose the condition & > 0 in (8), as the optimal value remains unchanged and is always positive. However, we shall see below that including this constraint ensures compactness of the feasible region - a property whose significance will be addressed subsequently. One can observe that if the functions s for = 1,..... k, convex (which in turn implies that M is convex), then the problem (8) becomes DC (Difference of Convex functions) program since the objective and the constraints are differences of two convex functions. The reader is referred to (An et al., 2014) for a comprehensive overview of DC programming and algorithms to solve problems with DC objectives and constraints upto criticality; see, e-g.. (Mordukhovich, 2018, Chapter 7) for theoretical insights. Although our results do not require the functions to be convex, when they are, DC programming algorithms may be used achieve faster convergence criticality in numerical implementations.
3
Main results
We now outline some technical notations and definitions in the context of the problem (8) to set the
stage for our analysis. The Lagrangian L RRN NgNxn x (R x R x [0, +20 - R of (8) is
L(x, (t, = - -Ah++841 1)t + Σ A (t --
166-1ly-2 Bll 21113) + Σ App)-n()),
(9)
where x denotes (n)).
The feasible region is denoted by the set-valued map Steas RR Nxn = R x RN
Steas (x) = -{{ (t.))
lyy 3.ll
< for all 1 . n,
(v) < 0 for all = n + 1,
n + k,
(10)
t 0
and the set of global optimizers is the set-valued map Sopt : IR Nx = X
Sapa (T) = { {1,,) v) E Stons (.) 1= }.
(11)
For choice of xr let (f. 7) E Sopt (z). We define the set of active constraint indices (α, (F, ()) as
T(a, (1,9)) = Eie m || n. 1| = 0} fi E (n + +,, I,.... n + k) 1p:-n( (7) 0).
(12)
5

---

The constraint > 0 is not included since t remains strictly positive at optimality, The set of Karush-Kot Baiish-Khhn---- Kuhn-Tucker (KKT) vectors of (8) for a pair (I, (t) E Rx"x= x (IR R2 denoted by
V V(..g) ((. (f.g), = 0,
A (T - = for i = 1,...,n x.1l²)
(Z. (f,0)) E [0, +00
(13)
AcP = for = n + ,,..,, +++ and An+k+1č= =0
Definition 3.1 (MFCQ for (8)) For E NR the irangaaarrii-Frommove constraint qualification
condition said hold (t, 7) E (z) if there exists a direction w E RN++1 such that the inner product of w with the gradient of each active constraint is strictly negative. To wit, the following conditions must hold:
(3.1-i) (1 20 T) w <0 for all i E (1,......) n) n [ (F. ū)), and n k} n I (z, (f, g)).
(3.1-ii) V (V) <0 for all E {n
We now present our first main result establishing Lipschitz continuity of G.
Theorem 3.2. Consider the problem (8) and grant the notations established above. Fix I E &R and suppose that the MFCQ condition (defined in Definition 3.1) holds for every (I, ū) E (T). Then the function G is locally Lipschitz continuous T. Consequently, its restriction 9 BlB(M) to
B(M)" (cff. Proposition 2.1) is Lipschitz. Moreover, for any E RNXx, xn, we have
ac (z, (f, 0). A) u u - -liminf (g(E + hv) g( 140 h
min (L.g) (2) (EA(z,((.)) dx
inf
1
ac,
< -- --limsup (g(s - hv) - g <
440 Te
max (T.)) AEA(Z.(..)
inf
dr (T. (T, 1), A). vv. (14)
Proof. We observe that both the objective and constraint functions are continuously differentiable. At each R.xxn, the feasible region Sias(()) is non-empty by definition. Letting N NT)) denote a neighborhood of F, we note that the mapping Steas is uniformly compact near I since the set Une Steas (z) always satisfies the containment relation
Steas (x) C [0. max max max 11 x4 x M.
(E) i=1.....n
(EN
Furthermore, a set independent of the base point containing UneN(a) Steas can be realized each component of i is restricted to the interior of the ball described Proposition 2.1, in which case we obtain the uniform containment (z)N(z) Steas (z) C (0,, 1) x M₁; the set the right- hand side is, of course. bounded. Therefore, (Fiacco and Ishizuka, 1990, Theorem 4.2) reproduced for completeness in $C as Theorem C.I - applics directly to our problem since the MFCQ conditions hold for every (f, y) E Sopt (i) by hypothesis. Consequently, 9 is locally Lipschitz continuous at æ, and its lower and upper Dini derivatives satisfy the bounds described (14). Invoking (Cobzaş et al., 2019, Theorem 2.1.6) gives us Lipschitz continuity of 9 BRRMM)". and proof is complete.
From this point forward, shall operate under the blanket assumption that MFCQ holds every (T, ū) E Sept(i) (7) for all ū E NR - property that can, in principle, be verified once the functions PP....., Ppk, are specified.
Remark 3.3. We highlight that reformulating (1) into (8) using the variable and representing M through continuously differentiable functions . SP,, was crucial for establishing Theorem 3.2. The existing literature does not appear have employed regularity properties of marginal functions for the design of optimal covering algorithms, which is point of departure of our contribution.
Remark 3.4. Observe that, in principle, every closed subset of IR admits representation as the zero-level set of a smooth function (Calderón and Zygmund, 1961) that is realized as a smooth regularization of the distance-to to-ancee-t-the-stt function. However, such a function may be difficult to encode in finitary way for computational purposes. In this light, while our assumption that the set M realized as the intersection of zero-sublevel sets of finitely many continuously differentiable functions may appear to be restrictive, it is a reasonably weak assumption, and this family of sets includes sublevel sets of polynomials in particular.

---

We now turn to the minimization of G. In view of Proposition 2.1, it suffices to restrict the search space B(M)) since all global minimizers of & are guaranteed lie within this set. Moreover, by Theorem 3.2, we see that (l)())) is I.-Lipschitz. Now we leverage recent advances in nonconvex and nonsmooth optimization using randomized smoothing by (Lin et al., 2022; Liu et al., 2024) to design our numerical algorithm. Specifically, we adopt an optimality framework based on generalized Goldstein stationary points (Goldstein, 1977) and develop an algorithm that provably converges to such a point based solely on oracle evaluations G. Furthermore, we establish polynomial bound on the number of such oracle calls required for convergence. We proceed by laying out set of definitions. For a detailed exposition, we refer the reader to (Lin et al., 2022).
Definition 3.5. Given point RR>x and direction RN-xn the generalized directional derivative of G is defined as Dg(x;;) v) = lim sup 200 gradient (Clarke, 1990) of G is defined as the set
((pttr)-G(u) Then, the generalized
0g(x)= == {g RRR NRNx xn (g,u) & DG(a; v), for E {
(15)
Let 8(x, = (y E NNn l - =|| < 5}. Given a 8 E O, the Goldstein õ-subdifferential (Goldstein, 1977) g at x is defined as (xg(x) = conv (U (UnEB(a.)) 0g(u)) Given 8 3 0 and 7, > 0, a point x E Nx is called a (7, ggeneralize Goldstein stationary point (Liu et al., 2024) of BBB(M)) if min { Proje (2 ( g E 0,9(11) < c, where Proje(M)- (v)
denotes the orthogonal projection of y onto B(M)".
We now present our algorithm - an adaptation of techniques from (Lin et al., 2022; Liu et al., 2024) with minor modifications suited the minimization of G restricted to B(M)).
Algorithm 1 gradOptNet: a numerical gradient-based optimal covering algorithm
1: Input: Initial point zo E [B(M)", stepsize 7 > 0, smoothing parameter 8, iteration number
T > 1, and parameters b1 b2, and q.
2: for ( 0,
do
3:
if mod((, q) = 0 then
4:
Sample 11....... ..., WW,,, uniformly from the unit sphere in R-xxn,
5:
Let Ii.: Nn (g(0) + 5ws,)) G( 8wx,))) Wa for each E fl,....bul b1).
6:
Set U/ = o Li=to Ri.--
>i
7:
else
8:
Sample w .,.... .., Whzt uniformly from the unit sphere in R-Nxn. w1,t
9:
Let gi.t Na (g( + ow;,) G(x, -8w,,)) wi, for each E {I,...,62]] 62].
10:
Let git-1
Nu (g( + dd.,t) G( ōw,,)) wiy for each E {l..... b2}.
20
11: Set 2/2
b2 Ee (9i, Ii.1-1) + 44-1-
12: end if
13: Update #1+1 = PrOjE(M)" (ot -U)).
14:
end for
15:
return TR. where R E (0, JO.,, T - 1} is uniformly sampled
Theorem 3.6. Consider the problem (8) and grant the notations established above. Let L denote
the Lipschitz constant of Gla(Myn- With by O |NIL3
by = = = (vNmL) (
and 7 =
ZNnI. the Algorithm requires almost (M,
calls of & to obtain a (7, e)-
generalized Goldstein stationary point of G in expectation.
Proof. In view of Theorem 3.2, we have Lipschitz continuity of 9 GlB(,M)>. We observe that Algorithm 1 corresponds to a variant of (Liu et al., 2024, Algorithm 3), adapted to the setting in which the objective function deterministic. Noting that the diameter of (MM) is 4/n'e(M, 1), we invoke (Liu et al., 2024, Corollary 5.4) to obtain the complexity bound in the assertion.
Remark 3.7. Theorem 3.2 provided the substrate to enable numerical gradient-based algorithms to solve (1). Since the outer minimization problem in (1) is non-convex, numerical maddient-based
7

---

algorithms can only guarantee convergence to stationary points as in 3.6. We attempt to obtain global solutions to (1) in two steps. First, Algorithm involves the calculation of difference quotients and their randomized smoothing; the smoothing is necessary for obtaining 'averaged' descent directions to solve non-convex optimization problems up to stationarity, and this performed along with variance reduction scheme proposed in (Liu et al., 2024). Second, global convergence to minimizers (as opposed to stationary points) is facilitated by the employment of several randomized 'restarts' (parallel initializations) in the indicated local scheme.
4 Numerical experiments
This section details the numerical experiments carried out using Algorithm 1. Heuristic observations in (Liu et al., 2024, Section 6) align with our observations: faster convergence is observed when the variance reduction step is omitted (i.e., 9 = 1, rendering by immaterial). We also observe better performance when b1 is increased in response larger values of or N. Accordingly, for all our experiments. For the ease visualization, we present examples with = and n < 10 in $4; illustration with N is presented in Example D.2 in SD. At each point, G is evaluated using the NL.P solver BARON (Sahinidis, 1996), known for its global optimization capabilities. To the best of our knowledge, existing benchmarks ground truth results available in the literature, and therefore, our comparisons of computation time and accuracy are with techniques like simulated annealing that do leverage the Lipschitz continuity of Ç for outer minimization.
set q 1
Example 4.1. Consider the case where N = 2, k 1, and the set M is the solid ellipse
32 - 4 - -
M = = (y1, 82)
R
(2(1))
(16)
The application of Algorithm with multiple parallel initializations (to enhance global convergence efficiency), led to the results presented in Fig. for number of balls vt 2, 3, 4, 5, 7, and 8.
-2
-2
-2
-3
n-2 coverin AM
3-3 covcring
MM
n- covering of AA
(a) (M 2.169
((M,3) 2.016456
(c) e(M 4) 1.667632
0
0
-1
+2
-3
coverin JM
covering
coverin
(d) 5) =
1.494066
(e) e(M, 7) = 1.220183
(f) <MM 8) = 1.140047
Figure Covering of the ellipse (16) for varying values of n.
The results exhibit visually interpretable structure primarily due to the inherent symmetry of the set M. This naturally motivates the expectation of symmetric structures in the optimal coverings- property that is indeed observed in the solutions reported in Fig. 1. The evolution of the objective

---

value for the case n 4 against the iterations of Algorithm 1, with - 0.05. 6 = 0.01, = 24, and
q = 1 is shown in Fig. 4 featuring 4 restarts. For each n. Algorithm 1 executed with 10 restarts yielded final radius values with relative standard deviation < 1%, indicating excellent robustness. Table I tabulates and compares the computation time and solution quality for Algorithm vs Simulated Annealing (Metropolis Hastings sampling and geometric cooling rate) for the example with n = 4..
c(M, 4)
Method
Number of evaluations of g
Trial 1
Trial 2
Trial
gradOptNet (Ours)
1.682
1.706
1.698
4800
Simulated Annealing
2.227
2.574
2.301
10000
Table I: Comparison of computation time and solution quality across methods.
Remark 4.2. We emphasize that the ability of the inner solver used to evaluate G to attain global optimality is crucial for the effectiveness of Algorithm 1. If a solver lacking global optimality guarantees (such as IPOPT) is employed, it may fail to produce a valid covering of M. This phenomenon is treated in Example D.I.
Example 4.3. Let us consider an example where .M is asymmetric and nonconvex, and to this end, consider the case where N = 2. k = 4, and the set M is the region
M = {11, v2) E 2 (v) < 0 for j = 1,2,3, 4) where, with y = (y1, 32).
91 (v) = 2y² y2, (v( == 1/2 2 ( - 1))²
(17)
(v) :- 1/2 5 + 0.1)², and (4()) = 001 y1
Once again, Algorithm 1 was employed with multiple parallel initializations, and the results presented in Fig. 2 were obtained for n = 1, 2, 3, 4, 5,6. 6.
1.0
1.0
0.8
0.5
0.5
0.6
0.5
0.5
0.4
0.2
0.0
0.0
0.0
-02
-0.2
-022
-02
0.6
-.44
-0.2
0.4
0.6
-.44
0.0
02
0.4
n=1 covering of
covering of AM
n= covering AM
(a) c(M, 1) = 0.490713
(b) c(M, 2) = 0.288713
(c) e(M, 3) = 0.207196
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.0
-3.2
-0.2
-0.2
0.4
covering of
covering AE
covering
(d) ()) = 0.168091
(e) (M, = 0.152269
(i) <MM 6) = 0.143661
Figure Covering of the region (17) for n 1,2, 5, and 6.
Similarly, for each n, Algorithm executed with 10 restarts converged to final radius values with relative standard deviation 1%. Additional experimental details are provided in $D.
9

---

Concluding remarks
In this work established a computationally viable approach the optimal covering problem. We started with the definition of the problem (1) and applied a sequence of reformulations under mild structural assumptions derive version (7) more amenable to analysis. central contribution of our work is a novel result establishing Lipschitz continuity of the optimal value function G arising from the nonconvex inner problem, which forms the foundation for applying numerical gradient-based based (zeroth-order) algorithm for the outer minimization. This algorithm leverages recent advances nonsmooth and nonconvex optimization and, via randomized smoothing, offers non- asymptotic convergence guarantees for obtaining approximate stationary points. We demonstrated the effectiveness of our method through experiments on compact subsets of TR.2 and R33 Future directions include accelerating the computation of & for convex sets via DC programming techniques and developing strategies to improve global convergence guarantees for the outer minimization. We also observe that G (Z1...., In) is permutation invariant function. This property can be used to restrict the search space further, which may help accelerate convergence.
References
A. R. Alimov and I. G. Kovr'kov. Chebyshev centres, Jung constants, and their applications. Russian Mathematical Surveys, 74(5):775-849, 2019. doi: https: http:///ooooo////..///. org/10. wwtgg1..41133 00..3441rr88833
A. R. Alimov and I. G. Tsar'kov. Geometric Approximation Theory. Springer Monographs in Mathematics. Springer, Cham, 2021. doi: https://doi. 10t.g///..000/71000000 0-000000--00000 90000-99951222
1.2
L. An, H. V. Ngai, and D. Tao. DC programming and DCA for general DC programs. Advances in Intelligent Systems and Computing, 282:15-35, 01 2014. doi: https://doi. org/10.10077 978-3 3-9-1----00 06569-6669690 4_2.5
Binev, A. Bonito, DeVore, and G. Petrova. Optimal learning. Calcolo, Quarterly on Numerical Analysis and Theory of Computation, 61(1), 2024. doi: https://doi. org/10.1 1000// 000022-023-0064--1
A.-P. Calderón and A. Zygmund. Local properties of solutions of elliptic partial differential equations. Polska Akademia Nauk. Instytut Matematyczny, Studia Mathematica, 20:171-225, 1961. doi:
https://doi. 2rg/10.00 1.000.004/samm 20044/mm-0--20 20-2-000-2211 2-1--2212555 6
F. H. Clarke. Optimization and Nonsmooth Analysis, volume 5 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, 1990. doi:
18
S. Cobzaş, R. Miculescu, and A. Nicolae. Lipschitz Functions, volume 2241 of Lecture Notes in Mathematics. Springer, Cham, 2019. doi: 6. 18
S. Das, A. Aravind, A. Cherukuri, and D. Chatterjee. Near-optimal solutions of convex semi-infinite programs via targeted sampling. Amnals of Operations Research, 318(1):129-144 146,, 2022. doi: https://doi. org/10. 10. 1007 00777/11479-0000 04810-488.....
A. L. Dontchev and R. T. Rockafellar. Implicit Functions and Solution Mappings. Springer Series in Operations Research and Financial Engineering. Beiinge--Verlag edition, 2014. doi: https: //doi. otg/10.00111..1 10. 1001090079998 9978//971111 1- 1-188-----9----- --34939-137--3
Y. C. Eldar, A. Beck, and M. Teboulle. A minimax Chebyshev estimator for bounded error estimation. IEEE Transactions on Signal Processing, 56(4):1388-1397 2008. doi: https://doi org/10. 10.
1109/TSP. 2007 200.P...07..80000000. 908945. 2
A. V. Fiacco. Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, volume 165 of Mathematics in Science and Engineering. Academic Press, Inc., Orlando, FL, 1983. 3
A. V. Fiacco and Y. Ishizuka. Sensitivity and stability analysis for nonlinear programming. Annals of Operations Research, 27(1):215-235, 1990. doi: https: //doi./ddo///ooo/oo wttp.//00..0000/////055550000000
6. 19
10

---

S. Foucart and C. Liao. S-procedure relaxation: a case of exactness involving Chebyshev centers. In Explorations in the mathematics of data science- the inaugural volume of the Center for Approxi- mation and Mathematical Data Analytics, Applied Numerical and Harmonic Analysis, pages 1-18. Birkhänser/Springer, Cham, 2024. doi: 2
A. A. Goldstein. Optimization of lipschitz continuous functions. Mathematical Progranminng, 13: 14-22, 1977. doi: 10.1007/BBF11584320, doi: httpp::/ddo.oogg//// 1tt.://.......1....0/0//////0000 1007/BB05588822. 7, 18
S. Har-Peled. Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2011. doi: https://doi. org/
10. 10000000r//13.. 3
A. N. Kolmogorov and V. M. Tihomirov. E-entropy and e-capacity of sets in functional space. American Mathematical Sociery Translations (2), 17:277-364, 1961. 1
Lin, Z. Zheng, and M. I. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. In Advances in Neural Information Processing Systems, volume 35, 2022.
Z. Liu, C. Chen, L. Luo, and B. K. H. Low. Zeroth-order methods for constrained nonconvex nonsmooth stochastic optimization. In Proceedings of the 41st International Conference Machine Learning, volume 235, pages 00842-30872, 2024. 7,8
O. S. Malysheva. Optimal position of compact sets and the Steiner problem in spaces with Euclidean Gromov-Hausdorf metric. Sbornik: Mathematics, 138-119)1382-139, 2020. doi: https: / doi. org/10 10. 1070/SM9361. 3
C. A. Micchelli and J. Rivlin. A survey of optimal recovery. In Optimal Estimation in Approxima- fion Theory, pages 1-54. Plenum, New York, 1977.
B. Mordukhovich. Variational Analysis and Applications. Springer Monographs Mathematics. Springer, Cham, 2018. doi: https://ddot httt::://di..org/101110000 1rg//..000//////98.
5
P. Paruchuri and D. Chatterjee. Attaining the Chebyshev bound for optimal learning: A numerical algorithm. Systems & Control Letters, 181:105648, 2023. ISSN 0167-6911. doi: https:
//doi.org/10. org/10.1016/3 sysconle...... www.connee..2.... 2023..0648... 2
C. P. Robert and G. Casella. Monte Carlo Statistical Methods. Springer Texts in Statis- tics. Springer-Verlag New York, second edition, 2004, doi: https://doi.org:
978-1-4757-4145-22
N. V. Sahinidis. BARON: general purpose global optimization software package. Journal of Global Optimization, 8(2):201-20) 1996. ISSN 1573-2916. doi: httpps//dont org/10. BF00138693,
V. N. Ushakov and P. D. Lebedev. Algorithms for constructing an optimal cover for sets in three- dimensional Euclidean space. Trudy Instituta Matematiki Mekhaniki, 21(2)2276-888, 2015. doi: https://doi. org/10 10. 1134//008114381100000000 2,
V. A. Voronov, A. D. Tolmachev, D. S. Protasov, and A. M. Neopryatnaya. Searching for distance graph embeddings and optimal partitions of compact in Fuclidean space. In M. Khachay, Y. Kochetov, A. Eremeev, O. Khamisov, V. Mazalov, and P. Pardalos, editors, Mathematical Optimization Theory and Operations Research; Recent Trends, pages 391-403. Springer Nature Switzerland, 2023. 3
D. Wu, J. Zhou, and A. Hu. A new approximate algorithm for the Chebyshev center. Automatica, 49 (8):2433-2488, 2013. doi: https://doi http://dd..o.og....// wtgg/0..116//// automatica. 2013. 04. 029.
H. Yu. Cube packings Euclidean spaces. Mathematika, 67(2):288-29) 295, 2021. doi: https:
htt///...111///11 1112/mtk. 12074.

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model seel-speciiicttion, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include theoretical results.
12

---

All the theorems, formulas, and proofs in the paper should be numbered and cross
referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: The user requires BARON license to run the BARON solver.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Guidelines:
13

---

The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
public/guide htt///uiddee///oee wttps//oooeSmmmmiioooooeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: CooeeSumiiiieeee cttpbliccpppulcc//cccccccccc gecoeeeSSeeeemmmiii ssi ssionPoiccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Although the global optimum is unknown, indeed report the consistent convergence of multiple restarts to radius values with relative standard deviation < 1% in Examples 4.1 and 4.3 of $4 which indicates method's robustness.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
14

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eπror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurips wttpcccwpppcccceeeeeccecccccccee samblii/Ethiccuuudeeeieen ines?
/
Answer: [Yes]
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This article presents work aimed at presenting novel approach to tackle the optimal covering problem. The applications this work could have social impacts in various domains. However, we do not wish to highlight any such potential societal impacts in the article.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate
15

---

to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We have curated the experiments on our own and have not used any dataset scraped from the Internet.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are relcased, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi tacodeeoo.ee.. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
16

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code//model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Guidelines:
17

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non-standard components.
Please refer to our LLM policy (https: /ttp:///nnuuu.ppeeeee wttparrppp.ccccofeeeeeeeeeec cc//onnferenccs/22255////// for what should or should not be described.
A Foundational Definitions and Results
Here we outline few important definitions from sensitivity analysis and nonsmooth optimization.
Definition A.I. A set-valued mapping S A = B is mapping S A 2 where for each A, S(z) is subset of B. They have been extensively used to study the feasible regions and solution maps of optimization problems
Definition A.2. The set valued map S A B is said to be uniformly compact near T if the set UrEN(#) (xx) is bounded for some neighborhood (()) of æ.
Definition A.3. A mapping f R" R is said to be locally Lipschitz if at each point R" there exists a neighborhood O and > such that [f(x) - f(x2)] & _|| - z2ll for all # 22 E O. Definition A.4. mapping f U C R -> IR is L-L.ipscitzz there exists
such that for every T1. E U, we have (2 - [x22) & L| -22ll. The number L is called the Lipschitz constant of f.
Corollary A.5 ((Cobzaş al., 2019)). Let f: TR- I. be a locally Lipschitz function and U g be compact. Then the restriction of f to U denoted by fly is L-Lipschitz.
We define Dini-derivatives to generalize the notion directional differentiability for non-smooth functions.
Definition A.6. Let : R and x E R The upper and lower Dini-derivatives of f along the direction IR" are defined as
1
D+ [(;;h) sup sup ( + hv) f(x) and
h
640
(18)
1
D f(x;h) = lim inf (f(x + hw) f(x))
h40
h
respectively.
Definition A.7. Given point R" and direction R", the generalized directional derivative of nondifferentiable function is defined Df v) lim sup, 1000 generalized gradient (Clarke, 1990) of ff is defined as the set
-(x+tt)-((g) Then, the
0f(x) = {g R" 1gg DG(x;v), for all R.) =|l
(19)
Definition A.8. Let B(x, {y R" [1
8}. Given 8 the Goldstein 8-
subdifferential (Goldstein, 1977) of f at is defined as
0sf(x) = conv
U ((,,))
as(w)
(20)
B Proofs of Propositions 2.1 and 2.2
Proposition 2. 1. We know that for every i E {1, .l,...,n) [n] there exists M such that I x; & e(M,n). Consequently, || - = < -| - yl + 11 x; which leads to
|| zill < c(M,n) m) + c(M.1),
and since e(M,n') E(M, n) for every n' n.
||2" x; (c,M
and the assertion follows.
18

---

Proposition 2.2. Strict feasibility of both problems is always ensured since any point in M with t readily satisfies all the constraints. follows immediately that (tt y²) is feasible point of (6), which implies t < Moreover, since
max (1 R & & I1y" x,ll for all i 1, ..).
it follows that t' < t Consequently, e t"
C Lipschitz continuity of optimal value functions of parametrized nonlinear programs
Consider parametrized nonlinear program of the form
min (0(x,2)
(21)
subject to
(,(2, 2) 0 for I,...,P.
where the functions 91. Ip are continuously differentiable from I2 x R to R. The Lagrangian for (21) is given by
C(r, ::oo))===((0000) 2) +
Σ {xgr(1, 2).
(22)
The feasible region is denoted by the set-valued map Steas 1B77 = IR"
Steas (z) = { E
RR" [F
< 0 for i = 1,... .
(23)
The optimal value function 4 IR parameter z E RT. That is,
I
{
{ is the optimal value of the NLP for given
S i
min
(0 2).
(24)
SES
By convention, ((F) = +oo if the problem is infeasible. The set of global optimizers is the set-valued map Sopt I RR,
Sopt (8) == {2 E Steas()) go 2) = (
(25)
For a choice 7 of r, let E Sopt (T). We define the set of active constraint indices at (ž, 2) as
T(r, 3) = {i (1.....,1 PP] 9r (T. 2) = =]-
(26)
The set of Karush-Kuhhn Kuhn--uckher Tucker (KKT) vectors of (8) for pair (z, E R R is denoted by
A(r, 3) = (A E [0, oo V=C(ā, E, A) = 0, Az 2) O for i = l.....,p) p)
(27)
The Mangasarian-Fromee if there exists direction E R² such that the inner product of with the gradient of each active constraint is strictly negative. To wit, the following condition must hold:
constraint qualification (MFCQ) is said to hold at a point 2 E Sopt (Ø)
V 2) w < O for all i E [αz,
(28)
We now state the result (Fiacco and Ishizuka, 1990, Theorem 4.2) that establishes the conditions under which the optimal value function is Lipschitz continuous.
Theorem C.1. Consider the problem (21) and grant the notations established above. Fix BY and suppose that (C.1-a) the MFCQ condition holds for every E (opr(T), and (C.1-b) the mup Steae is uniformly compact near T. Then the function is locally Lipschitz continuous at 5. Moreover, for any U E R?, we have
Oc (5, 2, .
inf min
- lim (0(E hw) -x)))
SE (at) (EA(E, dr
hjo T
1 ( hv) (())
OL
limsup hjo
inf SESopt (2) AEA(2.5)
(ō, E, A,
h
dz
19

---

D Experimental details
In this section, we provide further details of the experimental procedure along with a 3D illustration of covering in Example D.2. As emphasized in $1, the main computational bottleneck arises from having to reliably solve the inner problem (8) for the evaluation of & globally. This is the reason a solver with global optimality guarantees is employed. To illustrate the phenomenon mentioned in 4.2, we provide the following example.
Example D.I. For the solid ellipse (16) in Example 4.1. Here we employed Algorithm maintaining all parameters from Example 4.1, except that was evaluated using IPOPT instead of BARON in Algorithm 1. Fig. illustrates the failure of Algorithm in producing an adequate cover of M with 2, and 3. when IPOPT was employed.
0
0
-2
-1
-3
-2
-1
solution with
Figure 3: Covering fails if IPOPT is employed in place of BARON for n = 1,2,3.
For our experiments, we used the demo mode BARON, which imposes limits on the problem dimensions and number of constraints. To facilitate faster convergence and support for larger-scale problems, more advanced license may be used, For more details, visit https://mint baron-lice mineliienses. Table 2 reports the time taken to compute G in Example 4.1 for varying using BARON demo mode on an AMD Ryzen 4800H 2.90 GHz CPU. Note that the total number of
com/
Table 2: Computation time for 9 for varying n
Computation time (ms)
2
129
135
143
146
154
160
164
173
evaluations of per iteration of Algorithm depends on by and bz-
Fig 4 shows the temporal evolution of the objective in Example 4.1 and features 4 restarts (initializa- tions). An example with nonconvex, asymmetric in @ is provided in Example D.2. Note that only the isometric view is provided for each case.
20

---

Objective value C (x) ELM, .)2
Restart
14
Rostart 2
Restart
Restart
10
20
40
80
100
Iteration
Figure 4: The evolution of 9 against iteration count for the problem in Example 4.1 for 4.
Example D.2. As an illustration of the 3D case, we present an example where M is an asymmetric and nonconvex subset of RR3 Consider the case where 3, and the set the region
M = { (v), 1/2 Ma)
E R (v) & O for j = 2, where, with y == (3), 1/2 Va),
( (y)
(1 vी 0.3y2), (2(() = -yss + 1), and (P)(v) = 1/2 (0.5(1) 1)2 + 0.2y
(29)
Algorithm was employed with multiple restarts, and pictures of the outcomes are presented in Fig. 5 for the cases n 1, 2, 3, and 4.
covernng
COON
(a) c(M = 2.344070
(b) c(M, 2) 1.692330
(c) c(M,)) = 1446102
(d) c(M, 4) 1.371257
Figure Covering of the region (29) for n 1, 1,2,3, and
21


Reviews:
[{"review_id": "XKLnwqHZhM", "reviewer": "Reviewer_Ecfy", "summary": "The manuscript describes an algorithm to construct a Chebyshev net\nwith $n$ balls for a point set in $\\mathbb{R}^N$. Formally, the\noptimization problem for the optimal cover amounts to a min max min\nproblem. The authors suggest a convex relaxation of the inner\nminimization in the spirit of quadratic inequality constraints.\n\nThe central theorem 3.2 establishes regularity properties that justify\nthe problem relaxation with Lagrangian (9).\nThe mansucript presents simple examples of covering an ellipse and a\n2-dim. non-convex shape.", "questions": "It would be good to receive some\nexamples of coverings in high dimensions ($N \\approx 100$) with 1000\nto 10000 balls. How does the algorithm scale in this parameter range.\nOne might consgtruct concrete covers by finite size scaling in such a\nparameter range and this would be a real application with relevance\nfor ML.\n\nThe authors should say something about the scaling in high dimensions,\ni.e., point clouds in N dimensions like in coding theory.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe corage problem plays an important role in statistical learning\ntheory (usually expnential covers) as well as in computational\ngeometry. The manuscript has a distinct computational geometry flavor\nbut it might be relevant for approximations in machine learning.\n\nTheoretically the manuscript describes the algorithm quite well. It is\nmathematically solid as far as I can judge.\n\nThe algorithm is demonstrated by constructing two simple coverings. Scaling \n\nWeaknesses:\n\nI find the topic not central to machine learning or neural\ncomputation. It provides theoretical concepts and an algorithm which\nhas a weak relation to approximation theory, e.g., \\epsilon covers.\n\nThe numerical demonstrations are only illustrations but do not refer\nto reaL computational problems in ML. The examples in two dimensions\nwith 8 or 6 covers might not even be interesting for computational\ngeometry.", "was_revised": true, "final_justification": "For me the strong focus of the paper on optimization is a critical issue from a ML viewpoint. \nI lowered my score to borderline accept because I was not satisfied with the explanation of the 10 variable limit in the experiments. \nAlso coverings in statistical learning are considered in high dimensions. \nBoth reasons indicate that the manuscript summarizes a somewhat premature research result. \n\nIf space permits acceptance then I would support it.", "rebuttal": "# Strength:\n\nWe thank the reviewer for their positive comments regarding the paper's rigor and clarity.\n\n# Weakness:\n\n> I find the topic not central to machine learning or neural computation. It provides theoretical concepts and an algorithm which has a weak relation to approximation theory, e.g., \\epsilon covers.\n\nWe acknowledge the reviewer's concern regarding the centrality of the topic to neural computation and machine learning. Though perhaps not central to conventional machine learning, we believe our contributions are well situated in the topic of optimization that features prominently in the CfP of NeurIPS 2025.\n\n> The numerical demonstrations are only illustrations but do not refer to real computational problems in ML. The examples in two dimensions with 8 or 6 covers might not even be interesting for computational geometry.\n\nWe agree with the reviewer's comments that the examples provided in numerical experiments appear illustrative. We provide our reasons for this situation in our answer to Q1 below.\n\n# Questions:\n\n> Q1: It would be good to receive some examples of coverings in high dimensions ($N \\approx 100$) with 1000 to 10000 balls. How does the algorithm scale in this parameter range. One might construct concrete covers by finite size scaling in such a parameter range and this would be a real application with relevance for ML.\n\nWe appreciate the reviewer's question regarding scaling in higher dimensions. For our submission, we could only provide low-dimensional illustrations due to limitations of the proprietary solver BARON (the solver for the inner problem). According to the MINLP website, when BARON runs in demo mode it:\n\n * Supports up to 10 variables and constraints\n * Allows 50 nonlinear operations\n\nHence, it would not be feasible for us to demonstrate higher-dimensional examples in this rebuttal period. Having said that, please note that our key contribution is the algorithmic framework supported by Theorems 3.2 and 3.6, with the examples as proof-of-concept. We have shared our code, which will be open-source, enabling high-dimensional tests with an appropriate BARON license.\n\n\n> Q2: The authors should say something about the scaling in high dimensions, i.e., point clouds in N dimensions like in coding theory.\n\nTheorem 3.6 provides an expected convergence guarantee for the outer minimization in terms of the number of calls of $\\mathcal{G}$. It scales with $N$ and $n$ as $\\mathcal{O}(N^{\\frac{3}{2}}n^2)$ and this is independent of their ranges. However, the inner problem remains nonconvex even after reformulation, and the hardness of solving it globally is inescapable. We have illustrated the failure of a subpar solver for the same as elucidated in Reviewer 7X5g's comments in the weakness section."}, {"review_id": "HivtY5gaf4", "reviewer": "Reviewer_3wcR", "summary": "This paper considers an optimally covering problem, which is generally NP-hard and computationally challenging. To challenge this problem, this paper proposes a new approach which consists of (according to the authors claim in the paper) (i) A new reformulation of the problem which realizes a smooth objective function, (ii) a new gradient-based algorithm is proposed to minimize the objective function in (i), and its computational complexity is analyzed, and (iii) numerical experiments verifies the actual efficiency of the proposed framework.", "questions": "I would like to ask the authors how they think about my suggestion written in Weakness.\n\nFrom the reasons I wrote above (including the fact that I am not an expert), I begin with a neutral rate. I would like to reconsider my rating depending on the additional information in the discussion stages.", "limitations": "The authors do not explicitly state any limitations. \nI did not notice any other limitations.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "First of all, I have to confess that I am not an expert in this field, and I may be misunderstanding something.  I also have to say that I did not necessarily get into the mathematical detail of the theorems.\n\nStrength: As far as I went through from the abstract to the conclusions, I felt that this paper is very well-organized (well-written). Although I myself is not an expert on this topic, the introduction is clearly written such that the situation in the research field becomes visible. If we completely believe the authors' claim on their contributions, the algorithm is new, which is based on a new reformulation (and thus the development of the new algorithm is not straightforward), and the algorithm is good both theoretically and numerically.\n\nWeakness: Since I could not get into the technical detail, I cannot think of any defects. One thing I noticed is that no information on the actual computational time in the numerical experiments is given. The reason is clarified in the beginning of the numerical experiments section, where it is claimed that no direct comparison of computation time is feasible (since there is no competing existing algorithm). Still, I think some information on actual computation time might be informative for those who hope to employ their algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "# Strength:\nWe thank the reviewer for their positive comments regarding the clarity of the paper.\n> If we completely believe the authors' claim on their contributions, the algorithm is new, which is based on a new reformulation (and thus the development of the new algorithm is not straightforward), and the algorithm is good both theoretically and numerically. \n\nTo the best of our knowledge, the reformulation established in our submission and algorithm are indeed novel, they are supported by strong theoretical guarantees, which are the key contributions of our work. Even the $n = 1$ case of this problem is NP-hard, and there is currently only one algorithm to compute such *optimal* solutions in a finitary way [1]. Once our framework is established, as and when new and improved global optimization solvers are developed, they can be leveraged to obtain optimal covers more efficiently.\n\n# Weakness:\n\n> W1. Some information on actual computation time might be informative for those who hope to employ their algorithm.\n\nWe agree that the inclusion of details of actual compute time would benefit the paper. Table 1 in the paper reports per-point computation times for $\\mathcal{G}$ on an AMD Ryzen 7 4800H CPU. Since $q=1$ in our experiments, the time taken for Algorithm 1 roughly scales as $2b_1sT$, where $s$ is the per-point computation time. Please note that lines 5,9, and 10 of Algorithm 1 are parallelizable as computation for each $i$ is independent, reducing the time to $2sT$. Due to demo license constraints of the proprietary solver BARON, cluster-scale parallelization was not leveraged for the initial submission. If accepted, we would like to tabulate the computation time details along with a comparison against a gradient-free method like simulated annealing for the outer problem after leveraging the parallelization capabilities of Algorithm 1.\n\n# Experimental Result: \n\nHere we tabulate and compare the computation time and solution quality for Algorithm 1 vs Simulated Annealing for the 2D ellipse example with $n=4$, both on an AMD Ryzen 7 4800H CPU without leveraging the parallelizability.\n\n| Method              | Covering radius obtained (Trial 1) | Covering radius obtained (Trial 2) | Covering radius obtained(Trial 3) | Number of evaluations  of inner problem |\n|---------------------|:--------------------------:|:--------------------------:|:-------------------------:|:---------------------------------------:|\n|  Algorithm 1 (Ours) |            1.682           |            1.706           |           1.698           |                   4800                  |\n| Simulated Annealing |            2.227           |            2.574           |           2.301           |                  10000                  |\n\nWe see from the table that for the same initializations, simulated annealing - a method that doesn't leverage regularity properties of $\\mathcal{G}$ requires more calls of $\\mathcal{G}$ to attain convergence and is relatively suboptimal compared to our method. If accepted, we will add this comparative study to the revision.\n\n[1] P. Paruchuri and D. Chatterjee. Attaining the Chebyshev bound for optimal learning: A numerical algorithm. Systems & Control Letters, 181:105648, 2023."}, {"review_id": "MJQF8LmnxG", "reviewer": "Reviewer_7X5g", "summary": "This paper considers the problem of covering a (possibly nonconvex) bounded set using fixed number, say $n$ balls of smallest possible radius. The quantity of interest are centers of those $n$ balls (called as Chebyshev net of size $n$) and their radius. The main contribution is to reformulate the problem into a  min-max type problem where the inner maximization is nonconcave. The resulting outer value function is nonconcave, nonsmooth and Clarke ``irregular\" in variables that represent the location of ball-centers. They show that under mild assumption, the outer Clarke irregular function is Lipschitz continuous. Hence, they can apply zeroth-order methods developed in the recent literature for such nonconvex nonsmooth problems.", "questions": "It is necessary for the convergence that the domain of $x$ remains bounded. It is proved that it suffices to search on a bounded space $\\mathbb{B}(\\mathcal{M})$ which is based on Chebyshev center and radius for case of $n =1$. However, not much is said about the computation of these. Can you expand on how to find such a point?\n\nIn line 60, you mentioned a second version in equation (2) where the $n$ centers must belong $\\mathcal{M}$ itself. However, not much is said about this problem later on. How would Algorithm 1 change is this problem needs to be solved. Does that also mean projection is required onto set $\\mathcal{M}^n$ instead of line 13 of Algorithm 1. Moreover, if $\\mathcal{M}$ is nonconvex, does the convergence analysis borrowed from Liu et al. 2024 still hold if one needs to project onto a nonconvex set?\n\nTheorem 3.6 proves (or borrows) the convergence result for $\\min_x \\mathcal{G}$ problem. However, it does not explicitly state the impact of $b_1, b_2$. Although, it is clear that bigger $b_1,b_2$ will give more smoothing and possibly better estimates of descent direction. Also, I am wondering what are the conditions required on step-size $\\gamma$. Usually that is critical to get any convergence/complexity guarantees. Without it, the development looks incomplete to me.\n\nI see that you are treating the variable $x =(x_1, \\dots, x_n)$ as a full vector in dimension $Nn$. However, due to the obvious structure of the problem, it probably makes sense to consider block-wise updates and sample $b_1/n$ in unit spheres in $\\mathbb{R}^N$, a total of $n$-times. Would that benefit in scaling this approach?", "limitations": "I think the authors clearly mentioned some of the limitations, as those in experiment on Example D.1 where they use IPOPT instead of ``global optimizer\" BARON to solve the inner maximization problem.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The paper makes minimal assumptions about the structure of the set $\\mathcal{M}$ that needs to be covered. They provide novel insights on how one can prove Lipschitz continuity outer value function $\\mathcal{G}(x_1, \\dots, x_n)$ using such representation, along with classical results from analysis. This may be of independent interest in other applications. The paper is written with great clarity. I didn't see any obvious typos. All the relevant points are discussed in some detail along with the analysis.\n\nOn the weakness side: The formulation requires solving nonconvex maximization to evaluate value function $\\mathcal{G}(x)$. Indeed we have $\\mathcal{G}(x) = \\max t$ s.t. $h(x, y, t) \\le 0$ where $h$ is  nonconcave in $y$. One requires global solution of this problem in order to evaluate $\\mathcal{G}$ accurately. This is required since zero-th order schemes for problem $\\min_x \\mathcal{G}(x)$ with randomized smoothing requires high quality estimate to estimate numerical \"average\" descent directions. Without the global solves of such problem, the method may fail as illustrated in their own experiment in appendix. The good thing is reader is well-cautioned about it in the main paper.\nAnother weakness is that the algorithmic contribution in this paper are minimal. They are used as blackbox. Some important details and considerations for convergence of these algorithms are missing as well. I have some questions in this regard below.", "was_revised": true, "final_justification": "The remarks addressed my concerns.", "rebuttal": "# Strength:\nWe thank the reviewer for their positive comments on the paper’s clarity and theoretical insights. \n\n# Weakness:\nWe thank the reviewer for their constructive feedback.\n>One requires global solution of this problem in order to evaluate $\\mathcal{G}$ accurately. This is required since zero-th order schemes for problem with randomized smoothing requires high quality estimate to estimate numerical \"average\" descent directions.\n\nThe reviewer is correct about the evaluation of $\\mathcal{G}$ being computationally costly and Algorithm 1 being reliant on the quality of the solver for the 'inner' optimization problem in (7). However, notice that the problem is intrinsically difficult (even the $n = 1$ case is NP-hard), and consequently this computational expense is not unexpected.\n\n> Another weakness is that the algorithmic contribution in this paper are minimal. They are used as blackbox. Some important details and considerations for convergence of these algorithms are missing as well. \n\nWe agree with the reviewer's comments regarding our algorithmic contributions --- the framework backed by the theoretical results Theorem 3.2 and Theorem 3.6 is indeed our key contribution. Theorem 3.2 establishes the regularity property of $\\mathcal G$ that is needed for Theorem 3.6 to operate and solve the problem. We leveraged recently established algorithms for nonsmooth, nonconvex optimization for computational purposes. However, once our framework is established and as future algorithms improve complexity bounds under similar assumptions, they can be integrated directly into our problem to obtain optimal covers more efficiently.\n\n# Questions:\n> Q1: It is necessary for the convergence that the domain of $x$ remains bounded...\n\nIndeed, we restrict ourselves to a bounded decision space that depends on the Chebyshev center and radius. A (in fact, the only) numerically viable algorithm for computing these quantities is provided in [1]. However, in our experiments, initializing the centers inside $\\mathcal{M}$ and tuning step size $\\gamma$ ensured that the iterates of $x$ remained within $\\mathbb{B}(\\mathcal{M})^n$ (i.e the projection step was bypassed).\n\n> Q2: In line 60, you mentioned a second version in equation (2) where the centers must belong $\\mathcal{M}$ itself...\n\nWe appreciate the reviewer's question. For convex $\\mathcal{M}$, projection onto $\\mathcal{M}^n$ would be the only change required in Algorithm 1. The case of nonconvex $\\mathcal{M}$ is a scope for future work since it would be a nonsmooth, nonconvex minimization over a nonconvex set and this complicates the projection. If accepted, we will mention that convexity of $\\mathcal{M}$ is required to solve the version in equation (2) using the same algorithm with minimal changes.\n\n> Q3: Theorem 3.6 proves (or borrows) the convergence result for... \n\nTheorem 3.6 adapts Corollary 5.4 of [2] with certain modifications suited to the problem. We refer the reviewer to Theorem 5.3 of [2] for the sought result concerning the expected value of the norm of the generalized gradient and its dependence on parameters $\\gamma, b_1$, and $b_2$. The same modifications will make the result apply to our problem. We will add this result for completeness in the revision.\n\n> Q4: I see that you are treating the variable $x=(x_1,\\ldots,x_n)$ as a full vector in dimension $Nn$...\n\nOur response here is based on what we currently understand from the question: Since the number of decision variables does not change under this alteration, we do not foresee immediate benefits to operating with matrices for improving scalability. Please let us know if you are referring to the fact that the function $\\mathcal{G}(x_1,\\ldots,x_n)$ is permutation invariant with respect to its input: we seek the reviewer's elaboration on how the proposed treatment might benefit us.\n\n\n[1] P. Paruchuri and D. Chatterjee. Attaining the Chebyshev bound for optimal learning: A numerical algorithm. Systems & Control Letters, 181:105648, 2023.\n\n[2] Z. Liu, C. Chen, L. Luo, and B. K. H. Low. Zeroth-order methods for constrained nonconvex nonsmooth stochastic optimization. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 30842–30872, 2024."}, {"review_id": "hjfpxSHxIb", "reviewer": "Reviewer_xqmn", "summary": "The paper studies the optimal covering problem, where the goal is to obtain the optimal way to cover a compact subset of Euclidean space with a given number of Euclidean balls, where the optimality is formulated based on the maximum distances of the centers of the balls to the subset. The paper proposes a reformulation of the original problem to make it possess desirable regularity properties, and thus propose an algorithm based on numerical gradient to solve the problem. The efficiency of the algorithm is quantified, and numerical experiments are provided. The experiments demonstrate that the proposed algorithm indeed achieves good performances.", "questions": "I am not that familiar with the tackled problem. As briefly mentioned in Strengths and Weaknesses, I find the empirical results relatively weak. To me the presented empirical results largely show that the algorithm was able to find reasonable results, without showing that it finds really good results or has good convergence properties due to the lack of a ground truth solution or relevant baselines. While the authors argued that no competing algorithms are available in the literature in Section 4, the authors also mentioned some previous approaches in Section 1. It would be ideal if the authors can improve the part on numerical results using as baselines some previous approaches, thus providing empirical evidence that the proposed algorithm is indeed a significant improvement upon the previous ones either in terms of computational efficiency or accuracy or both.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Sufficient background is provided, motivating the research problem and demonstrating its importance.\n\n2. The proposed algorithm is theoretically grounded, and is proven to yield reasonable performances.\n\nWeaknesses:\n\n1. As acknowledged by the authors, the proposed algorithm is still computationally costly.\n\n2. The empirical results largely serve to demonstrate the correctness of the proposed algorithm, without showing its efficiency.", "was_revised": true, "final_justification": "My sole concern was about the lack of a ground truth solution or a relevant baseline, thus limiting the empirical evidence. The authors did provided empirical baselines that demonstrated the good properties of the proposed algorithm. As such, I raise my score to 5.", "rebuttal": "# Strength:\n\nWe thank the reviewer for their positive comments regarding the quality of the paper.\n\n\n# Questions:\n\n> Q1: To me the presented empirical results largely show that the algorithm was able to find reasonable results, without showing that it finds really good results or has good convergence properties due to the lack of a ground truth solution or relevant baselines.\n\nThe problem tackled in our submission is quite difficult; optimal solutions in only a few isolated cases with excellent symmetry are known today. We set out to establish the algorithmic framework contained in our submission with solid theoretical backing from Theorems 3.2 and 3.6, and that constitutes our primary contribution; the numerical implementations were presented as proof-of-concept. Please note that Theorem 3.6 provides guarantees in expectation of the convergence of the outer problem in Theorem 3.6 by leveraging our Lipschitz continuity result in Theorem 3.2 along with the recent developments made in nonsmooth nonconvex optimization in [1]. An alternative generalized framework for obtaining solutions for the same has not appeared in the literature. We acknowledge that indeed, our experimental results are illustrations and are currently outside the scope of our submission.\n\n> Q2: While the authors argued that no competing algorithms are available in the literature in Section 4, the authors also mentioned some previous approaches in Section 1. It would be ideal if the authors can improve the part on numerical results using as baselines some previous approaches, thus providing empirical evidence that the proposed algorithm is indeed a significant improvement upon the previous ones either in terms of computational efficiency or accuracy or both.\n\nTo the best of our knowledge, no other algorithm gives theoretical guarantees for optimality for the problem under consideration. It is well-known to be hard, even in the $n = 1$ case -- this is the Chebyshev center problem. However, it is possible to compare our numerical gradient-based outer minimization that exploits the Lipschitz continuity of $\\mathcal{G}$ given in Theorem 3.2 against other techniques like simulated annealing that do not leverage this regularity. For this, we present below the same experimental result in our reply to Reviewer 3wcR (Reviewer #2).\n\nHere we tabulate and compare the computation time and solution quality for Algorithm 1 vs Simulated Annealing for the 2D ellipse example with $n=4$, both on an AMD Ryzen 7 4800H CPU. Due to demo license constraints of the proprietary solver BARON, cluster-scale parallelization was not leveraged for the initial submission.\n\n| Method              | Covering radius obtained (Trial 1) | Covering radius obtained (Trial 2) | Covering radius obtained (Trial 3) | Number of evaluations  of inner problem |\n|---------------------|:--------------------------:|:--------------------------:|:-------------------------:|:---------------------------------------:|\n|  Algorithm 1 (Ours) |            1.682           |            1.706           |           1.698           |                   4800                  |\n| Simulated Annealing |            2.227           |            2.574           |           2.301           |                  10000                  |\n\nWe see from the table that for the same initializations, simulated annealing -- a method that does not leverage regularity properties of $\\mathcal{G}$ -- requires more calls of $\\mathcal{G}$ to attain convergence and is relatively suboptimal compared to our method. If accepted, we will add this comparative study to the revision.\n\n[1] Z. Liu, C. Chen, L. Luo, and B. K. H. Low. Zeroth-order methods for constrained nonconvex nonsmooth stochastic optimization. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 30842–30872, 2024."}]

Author rebuttal:

Meta-review: The authors provide an approximation algorithm to optimally cover a given compact subset of $R^N$ with $n$ (fixed in advance) metric balls. This is a well-known and somewhat fundamental problem. The theoretical results they provide are rigorous and use novel insights. They also include compelling experimental results, albeit somewhat limited. There is some question whether this work belongs at Neurips but ultimately it seems it would be a valuable contribution.
Decision: Accept (poster)