On the Sample Complexity of Lipschitz Constant Estimation
Authors: Julien Walden Huang
Stephen J. Roberts
Jan-Peter Calliess
Venue: Accepted by TMLR ()

Abstract: Estimating the Lipschitz constant of a function, also known as Lipschitz learning, is a fundamental problem with broad applications in fields such as control and global optimization. In this paper, we study the Lipschitz learning problem with minimal parametric assumptions on the target function. As a first theoretical contribution, we derive novel lower bounds on the sample complexity of this problem for both noise-free and noisy settings under mild assumptions. Moreover, we propose a simple Lipschitz learning algorithm called $\textit{Lipschitz Constant Estimation by Least Squares Regression}$ (referred to as LCLS). We show that LCLS is asymptotically consistent for general noise assumptions and offers finite sample guarantees that can be translated to new upper bounds on the sample complexity of the Lipschitz learning problem.  Our analysis shows that the sample complexity rates derived in this paper are optimal in both the noise-free setting and in the noisy setting when the noise is assumed to follow a Gaussian distribution and that LCLS is a sample-optimal algorithm in both cases. Finally, we show that by design, the LCLS algorithm is computationally faster than existing theoretically consistent methods, and can be readily adapted to various noise assumptions with little to no prior knowledge of the target function properties or noise distribution.

Published in Transactions on Machine Learning Research (09/2023)
On the Sample Complexity of Lipschitz Constant Estimation
Julien Walden Huang
gubeen.ounng@esjc.or.cco
University of Oxford
Stephen Roberts University of Oxford
sjrob@roobots.or.co
Jan-Peter Calliess University of Orford
Reviewed on OpenReview: https: // openreview. net/ forun? id= U12TYA
Abstract
Estimating the Lipschitz constant of function, also known as Lipschitz learning, is funda- mental problem with broad applications in fields such as control and global optimization. In this paper, we study the Lipschitz learning problem with minimal parametric assumptions on the target function. As a first thcoretical contribution, we derive novel lower bounds on the sample complexity of this problem for both noise-free and noisy settings under mild assumptions. Moreover, we propose a simple Lipschitz learning algorithm called Lipschitz Constant Estimation by Least Squares Regression (referred to as LCLS). We show that LCLS is asymptotically consistent for general noise assumptions and offers finite sample guarantees that can be translated to new upper bounds the sample complexity of the Lipschitz learning problem. Our analysis shows that the sample complexity rates derived in this paper are optimal in both the noise-free setting and in the noisy setting when the noise assumed to follow a Gaussian distribution and that LCLS a sample-optimal algorithm in both cases. Finally, we show that by design, the L.CSS algorithm is computationally faster than existing thcorctically consistent methods, and can be readily adapted to various noise assumptions with little no prior knowledge of the larget function properties or noise distribution.
1 Introduction
Many applications are based the Lipschitz continuity of objective target function and depend explicitly on the value of a Lipschitz constant. Examples include: robustness analysis which utilises Lipschitz constants to characterise worst-case behaviour in control settings (Limon et al. (2017), Canale et al. (2014) 4))
system identification which leverages the Lipschitz continuity property to obtain worst-case prediction error bounds for interpolation methods (Milanese and Novara (2004) [eliakov] (2006), Calliess et al. (2020)), global optimization algorithms which rely on precise Lipschitz constant estimates to ensure speedy convergence [Jones et al.] (1933), González al. (2016), Malherbe and Vayatis (2017)), multi-armed bandit problems which utilise the Lipschitz constants to obtain asymptotic lower bounds and design algorithms (Magureanu ct al. (2014)) or reinforeement learning which utilises the Lipschitz constant to construct safe initial policies [Chakrabarty et al. (2020)). ). For these applications it is critical that the Lipschitz constant estimate used is sufficiently precise in order to ensure satisfactory performance in their specified goal. A main practical drawback therefore the dependency on the assumption of prior knowledge of the Lipschitz constant or, in the case that this assumption is not made, the necessity of having to learn precise Lipschitz constant estimate from data.
Consequently, a number of Lipschitz constant estimation methods (also called Lipschitz learning algorithms) have been developed. For target functions belonging to families of parametric models, Lipschitz learning

---

Published in Transactions on Machine Learning Research (09/2023)
approaches generally utilise the structure of the model class to obtain precise estimates (e.g. see extensive literature on the estimation of Lipschitz constants of Neural networks (Virmaux and Scaman (2018) (aazlab
et al. )0. For frameworks that don't consider a particular parametric family, a majority of the existing approaches are black-box mothods that utilise and extend Strongin's classical estimator (Strongin (1973) ):
: 1 |,;-,,]|
[i- where E RR is multiplicative factor and (I; fi) is data sample with fs fx;). In
particular, we highlight: (Wood and Zhang (1996)) builds on Strongin's estimator by fitting an approximate reverse Weibull distribution to the Lipschitz estimate in the one-dimensional case and using the location parameter as a Lipschitz estimate, (Sergeyev) (1995)) utilises Strongin's 's approach to compute local Lipschitz constant estimates and extends the approach to the multidimennsional case by using space filling curves in order to solve a global optimization problem and more recent approach (Strongin et al. (2019) proposes dual Strongin Lipschitz estimates: with two differing 'local' and "global" multiplicative factors. We remark that the class of Lipschitz learning algorithms' described so far does not consider the possibility of observational noise and can explode in value if it exists. In this case, we can consider the Lispchitz constant estimator proposed by both NNovar et al. (2013)) ) and (Calliess et al. (2020)) which specifically extends Strongin's estimate to deal with bounded observational noise.
Alternative Lipschitz learning approaches that do not directly utilise Strongin's 's estimate have also been de- veloped. These generally can consider the case of observational noise and include: (Beliakov) (2005)) ) which utilises a short optimisation problem and cross calidatiionsamppl splitting to obtain Lipschitz constant es- timates, (Bubeck et al. (2011) which employs a similar idea to Strongin's estimate in order to propose a Lipschitz constant estimator in the context of the Lipschitz multi-armed bandit problem, (González et al. (2016)) which generates Lipschitz constant estimates using the mean function of the gradient function es- timate of a fitted Gaussian Process (GP) and directly computable using the -ssssscciated covariance function, and (Calliess (207)) which obtains Lipschitz constant estimates by optimising Lipschitz interpo- lation method. Unfortunately, while this class of Lipschitz learning algorithms tends to work well in practice, they generally do not guarantee asymptotic convergence and are of limited theoretical interest.
Despite the wide range of proposed Lipschitz learning algorithms, there has been little thcoretical investiga- tion into the Lipschitz constant estimation problem other than various consistency proofs of Strongin-basee based estimators. It is generally understood that this learning problem, without making further restrictive as- sumptions on the underlying space of target functions, is inevitably subject to the curse of dimensionality, However, to the best of our knowledge, this intuition has not been explored formally. A first goal of this paper is therefore to provide a theoretical investigation into the Lipschitz learning problem by deriving lower bounds on the sample complexity in the case of both a noiscless and noisy sampling scttings. We confirm the general intuition on the difficulty of the Lipschitz learning problem by demonstrating that the problem has a sample complexity lower bound that scales at least exponentially on the function input dimension in both the noiseless case and the noisy sampling case when the noise is assumed to be Gaussian.
Our theoretical results imply that a precise estimation of the Lipschitz constant requires a significant number of samples. This is computationally problematic for classical Strongin strongin-bassed Lipschitz learning algorithms due to the fact that the computational complexity of these methods can be shown to be quadratic in the number of samples: O( While the non-Strongin based estimators discussed above could potentially be less computationally expensive, they only provide heuristic or experimental convergence guarantees and are generally difficult to study from a theoretical perspective. Therefore, in light of our lower bounds on sample complexity, we propose novel algorithm for Lipschitz learning called LCLS (short for Lipschitz Constant estimation by Least Squares regression) that has a linear computational complexity in the number of sample points and for which we can derive theoretical guarantees on asymptotic convergence and finite sample behaviour in general noisy sampling setting. The optimality of the lower bounds on the sample complexity of the Lipschitz learning problem in both the noiseless sampling setting and in the noisy sampling setting under Gaussian noise assumptions derived in the first part of the paper follow from these theoretical results.
In practice, the proposed LCLS algorithm provides a theoretically motivated and computationally quick way of estimating the Lipschitz constant. With minimal fine-tuning, LCLS can be plugged into any com- putational method that utilises a Lipschitz constant estimate see above discussion under any sampling noise assumptions. We provide an example of such a procedure in the context of nonparametric regres-
2

---

Published in Transactions on Machine Learning Research (09/2023)
sion for system identification in control by combining the LCLS algorithm with classical nonlinear set- wembership/Lipseee Lipschitz interpolation framework and illustrating the empirical performance of the combined regression method through a series of short experiments.
A more comprehensive list of the contributions this paper is given below.
1.1 Contributions and Outline of Paper
In this paper, we provide a rigorous treat ment of the Lipschitz constant estimation problem discussed above. In particular, we make the following contributions:
1. In Section 2 we provide novel theoretical lower bounds the sample complexity of the general
Lipschitz learning problem (for p E (1,2)) in the noiscless sampling sctting (scc Theorem 2.2 and of a slightly modified version of the problen the target function f : C R + R satisfies a regularity condition C² K) defined in Assumption We note that these bounds can be equivalently stated as lower bounds on the convergence rate of the general Lipschitz learning problem (see Corollaries 2.3 and 2.6p. As far as the authors are aware, the sample complexity and convergence bounds derived in this paper are the first theoretical results pertaining to the convergence of the general Lipschitz learning problem. We show in Section 3 that our proposed lower bound on the sample complexity rate is optimal in both the noiscless sampling setting and the noisy sampling setting under a Gaussian assumption.
D in the noisy sampling setting (see Theorem 2.5 w when
2
2. In Section 3.1 we propose least squares- based Lipschitz learning (LCLS) approach that utilises partition of the imput space X and local least squares estimates in order to generate Lipschitz con- stant estimate. As discussed in the introduction, our motivation for developing the LCLS algorithm rests on the following two desiderata for an estimator:
it should be both theoretically and computationally tractable, and,
directly applicable across all noise settings considered in the literature and implementable with- out any prior knowledge of target function properties or of the noise structure.
3. In Sections and
investigate theoretical properties of the proposed algorithm:
Asymptotic convergence for general partition choice in noiseless and general noisy sampling sct-ups (Section 3.2 see Theorem 3.7
Finite sample guarantees in the noiseless and general noisy sampling set-ups when the partition is constructed using regular hypercubes (Section 3.3 see Theorem 3.10 Corollary 3.16 These guarantees can be used to provide an upper bound on the sample complexity of the Lipschitz learning problem and show that the complexity rates derived in the first part of the paper match in both the noiseless and noisy setting under Gaussian assumption. (Section 3.3
see Remark
3.11 3.12.
Theorem 3.15
4. In Section 3.4 we illustrate and compare the empirical performance of the LCLS algorithm against Strongin- based Lipschitz learning algorithms on a set of test functions. We consider both the noise- less and noisy sampling settings. We find that while the benchmark Strongin-based algorithms converges slightly faster in terms of number of samples, our proposed algorithm converges faster in terms of computation time for all functions in the test set (see Figure 4 This is despite the fact that we consider noise settings for which the benchmark algorithms are specifically designed in experiments.
In Section 4 we explore the application of the various theoretical results and the LCLS algorithm derived in this paper to the fields of Global Optimisation and Nonparametric Regression for System Identification. More specifically, Lipschitz optimisation algorithms that follows from one of the theoretical results stated in Section 2 and a new nonparametric regression method constructed by combining the LCLS algorithm of Section with a classical nonlincar set membership framework (see Milanese and Novara (2004)
propose lower bound on the sample complexity of adaptive
Which can be shown be equivalent for the majority existing Lipschitz learning algorithms.
3

---

Published in Transactions on Machine Learning Research (09/2023)
2
Assumptions and Sample Complexity Lower Bound
In this section, we provide the standing assumptions of the paper and state the main results pertaining to theoretical lower bounds on the sample complexity of Lipschitz learning algorithms.
2.1 Basic Assumptions
Let p P N, de LENN N, a function f C Rd - R is said to be Lipschitz continuous with respect to a norm II-Ilp if there exists positive real value (ff E R such that -() s Lp(f)|ız ullp, for all x, y X. The smallest constant satisfying this condition denoted (f) called the (best) Lipschitz constant and can be interpreted as the tightest bound on the rate of change of f. Furthermore, for any 2 0, we define the class of Lipschitz continuous functions as
(L( = th: (h:X- + R//h Lipschitz A (g)h) = LJ.
The Lipschitz learning problem therefore considers the estimation of (,( when ʃ an unknown target function. As described in the introduction, we consider a general version of this problem where f considered black-box and can can only be accessed through queries to a, possibly noisy, oracle. As not assumed to belong any parametric family, other assumptions are needed in order to derive thcoretical bounds on the sample complexity. For our results, we make the following two assumptions on the input space X and the regularity of f.
Assumption (Domain) The domain X of the larget function is a conver and compact subset of Rd.
Assumption 2 (Functional) The target function f E (² and there erists an upper bound K E R4 on the second-ordes partial derivatives of f, i.e. Tz,02z S K for all a X and i E {l...., Furthermore, f can be extended on an open set X such that X C.X.
For a given K E R,, we denote by (² the class of functions that satisfies Assumption 2 with an upper bound K on the second degree partial derivatives. is important to point out that this bound does need to tight and that if Assumption holds then any f (²(()) automatically belongs to C2 K) for some K E Rt. Finally, we assume that we have access to the target function f through an oracle Q X - R defined formally below for each sampling setting which can be queried in order to generate observations of f. In particular, this oracle can be freely used by any Lipschitz learning algorithm described in the following definition.
Definition 2.1 (Lipschitz Learning Algorithmms) We define (x, as the set of all [1-ll-- learning algorithms that utilise most E N queries to the Oracle with inputs in X. The sampling procedure is considered to be part of the Lipschitz learnáng algorithm and vL (X) denote the set of generated sample points by = (0///
We note that Definition 2.1 defines general class of Lipschitz learning algorithms without any structural specifications and that the inclusion of the sampling procedure in the algorithm is common for applications in both control and global optimisation.
2.2 Noiseless Sampling Setting
Assumptions
1 2 are sufficient to formulate lower bound on the sample complexity rate of the Lipschitz learning problem in the case where one has access to an oraclo Ω that can be queried to obtain noiseless observations of the underlying target function. Formally, the noiseless Oracle is described by
Ω: R
20therwise, a theoretical characterisation of the Lipschits learning problem feasible. Note: in the noiseless case, the oracle and the target function are equivalent.
4

---

Published in Transactions on Machine Learning Research (09/2023)
x 2 f(z).
The lower bound on the sample complexity of any Lipschitz learning algorithm is given in the following theorem.
Theorem 2.2 (Sample Complexity Bound - Noiseless) Let M E R+, d d (1,2} and suppose
X = [0, Mja. Assume that Assumplion holds and that noiseless Ornole D2 (described ahove) is available.
- 2 O, Ve E (0, MK), if
inf (X) (E
sup
BL( - LiKe
then
2 C(d,p) MK
In this paper, we find Cdd.p)
however this value has not been optimized.
20d
Theorem 2.2 provides a lower bound on the minimum number of oracle queries that are needed in order for a Lipschitz learning algorithm to ensure a precise estimate the Lipschitz constant for all underlying target functions in (x, As speculated in the introduction, it shows that the Lipschitz Learning problem is a computationally expensive one that depends hcavily on the input dimension. The lower bounding expression is given function of the size of the input space (M), the assumed bound the second order partial derivatives (K) and the precision parameter (c) but is independent of the true Lipschitz constant (L*) of the target function. The product M K can be understood as a bound on the maximum change in the gradient values of functions in (²,, In Section 3 the proposed LCLS algorithm will be shown capable of estimating the Tipschitz constant of all functions f in (2, K) using (((MK) yd) queries to the noiseless sampling oracle Q implying that the lower bound on the sample complexity rate stated in Theorem 2.2 is optimal.
An equivalent reformulation of Theorem 2.2 in the form of lower bound on the convergence rate of Lipschitz learning algorithms is provided in the following corollary.
Corollary 2.3 (Convergence Rate Bound Noiseless) Assume the same setting as Theorem 2.2 Then, VL* 2 0,
MK
inf p (e - ((d
sup
where C(d,p) is defined in Theorem 2.2
Corollary 2.3 generally more practical to use then Theorem 2.2 when considering convergence properties
of applications of Lipschitz constant estimators. In Section
we show how Corollary 2.3 can be applied
in conjunction with recent theoretical results (Bachoc et al. 2021 to derive lower bounds on the sample complexity of adaptive Lipschitz optimisation algorithms.
2.3 Noisy Setting
In many practical cases, the sampling oracle cannot be assumed reliable and only approximate observations of the target function are obtainable. In this case, we model Ω X - as being corrupted by additive noise and a new lower bound on the sample complexity of Lipschitz learning algorithms can be derived. In order do so, additional assumptions must be made on the additive observational noise process.
Assumption 3 (Noisy Oracle Gaussion Noise) Let a² 0. We define noisy sampling oracle
X IR.
x fa :- f(x) +
where 7 are independent Gaussian random variables (x X) with mean 0 and varianee σ², Note: Yo an abuse of notation as the noise is not dependent on the input x. In other words: if x: X sampled twice, then 2 + 22 r--
5

---

Published in Transactions on Machine Learning Research (09/2023)
As the class of Lipschitz learning has been loosely defined so far, with no parametric or functional assump- tions, a slight reformulation of the Lipschitz learning problem is needed in order to derive lower bounds on the sample complexity. Consider the function class (X, K) as defined above and p E N. It is known (e.g. see Lemma B.2 that for all f E (² (f(() = max ( p 1,2 and [,( Σ maxx (IV] otherwise, where y is the Hölder conjugate of p. Then, instead directly considering the estimation error [f()) Iipl with a Lipschitz learning algorithm i(f) E (2)) as done in Thcorem 2.2 one can consider the problem of obtaining xD( X' such that [[/ T.şl is minimised. In this case, we say that the algorithm L(f) belongs to the class (xp(X) of Lipschitz Learning search algorithms which is defined formally as follows:
Definition 2.4 (Lipschitz Learning Search Algorithms) We define (xp(X) as the set of all Illlp-Lipschite learning search algovithems that ulilise al most E N queries to the Oracle QE with impuls in X in order to produce an estimate & that aims to minimise: Loss(i, == V L21-
This lype of paradigm is similar to the one considered in the literature on minimax global optimisation where generally aims to obtain the minimising argument å X of target function rather than directly estimating the minimum (e.g. Bull (2011)). We stress that if good estimate of xf can be obtained, then it is relatively straightforward to obtain accurate Lipschitz constant estimate by computing local gradient or slope estimate of the target function near zL1() In fact, the majority of Lipschitz algorithms either directly or implicitly operate by maximising gradient slope estimates (e.g. [Strongin] (1973), Calliess et al.] 2 the LCLS algorithm proposed in this paper) and could therefore be trivially modified to generate search estimate: ,L(())
Using Assumption the following lower bound on the sample complexity rate can be derived in the noisy sampling setting.
Theorem 2.5 (Sample Complezity Bound Noisy) Let M E R4, dEN, {1,2} and suppose X' := [0, Mjd. Assume that Assumplions
hold, that one has access to a noisy oracle Ω X - TR. as specified in Assumption 3) and that the sample imputs are uniformly and independently sampled on X. Define Ln.p (x)
in Desinilion 2.4 If there erists ō (0, such that
lim inf sup P(Loss( LiS) ( 5 56 c
(2) (xC)(
then,
2M 242 log(
MK
n Ω
ed44
In contrast to the sample complexity bounds obtained in the noiseless sampling setting, the bounds proposod in Theorem 2.5 only hold asymptotically and can therefore not be utilised in order to obtain finite sample
guarantees. Furthermore, the Lipschitz learning (search) algorithms considered in Theorem 2.5 are assumed to be passive as the sampling inputs are sampled randomly) as opposed to the active algorithms considered
in Theorem 2.2 Nonetheless, the obtained bounds provide insight into the necessary sampling requirements
needed to ensure convergence for the Lipschitz learning (search) problem in the noisy sampling setting. In Section 3.3 we will show that the LCLS algorithm matches the convergence rate stated in Theorem 2.5 under the same assumptions implying that the rate (o2 M (dd+xd+11pp log( MK
is optimal.
Finally, as in the noiseless sampling setting, an equivalent reformulation of Theorem 2 is provided in the form of a probabilistic lower bound on the convergence rate of Lipschitz learning (search) algorithms.
Note: are aware of any existing active Lipschitz learning algorithms Lipschitz constant estimation usually computed secondary task to main objective (e-g. optimisation, nonparametric regression).
6

---

Published in Transactions on Machine Learning Research (09/2023)
Corollary 2.6 (Sample Complexity Bound- Noisy) Assume the same setting as Theorem 2.5 all ó E (0. 1), there exists C > O such that.
Then, for
log(MKn) nM*K20²
# ) )
lim inf (x (ECP(X..))))
sup P(Loss(e L1)) CMK
Theorem 2.5 and Corollary 2.6 are particularly interesting the context of system identification for control applications (e.g. Milanese and Novara (2004), Calliess et al. (2020h) where robustness properties depend explicitly estimating fcasible Lipschitz constant from noisy data. These frameworks often ignore the modeling error arising from the Lipschitz constant estimation which is problematic when the goal is to provide worst-case guarantees. One source of usefulness for the two bounds stated in this subsection is therefore to provide a theoretical understanding of the worst-case estimation of Lipschitz constants in this context and therefore to make possible a more realistic robustness analysis of Lipschitz constant-based system identification methods in practice. A short. ralust comparison of the convergence rate given Corollary 2.6 with the convergence of existing Lipschitz learning algorithms used for system identification purposes is given in Figure 3
Remark 2.7 (Comparison to Nonparametric Estimation) The optimal convergence rotes of nomporumetric estimation in the noisy sampling setting with Gaussian noise are well-known (Tsybakor (2005)). In par- ticular, the uniform convergence rate of the nonparametric estimation of first-order portial derivatives on K) for some K > 0 is given by 2 ((logln) yatz (
which corresponds exactly to the lower bounds de- rived in Corollary 2.0 This implics that although Lipschitz learning seems more straightforward than partial derivative estimation, asymptotically their sample complezities are equivalent. Note that this observation is somewhat unsurprising as similar results hold in the contert of global optimisation Buul 2011
neN
Wang et al.
2018)).
3 Lipschitz Constant estimation by Least Squares regression (LCLS)
The theoretical results of Scction imply that a significant number of samples must be used in order to obtain a precise estimation of the best Lipschitz constant. As noted the introduction, this problematic computationally for classical Strongin-baad based Lipschitz learning algorithms due the fact that the computa- tional complexity of these methods can be shown to be quadratic in the number of samples. Using existing non-Strongin based methods could resolve this computational problem, however obtaining convergence guar- antees would then be difficult as this class of methods is generally complicated to study from a theoretical perspective. Therefore, in the goal of obtaining a Lipschitz learning approach that can provide asymptoti- cally consistency guarantees, has low computational complexity and for which we can derive upper bounds on the sample complexity (in the goal of comparing with the sample complexity lower bounds derived in Scction 2 we define a new estimator: Lipschitz Constant estimation by Least Squares regression (LCLS)..
3.1 Overview
The general intuition behind the Lipschitz learning algorithm proposed in this paper follows from the simple observation that the coefficients from a least squares regression can be interpreted as a local approximation of the gradient and that the maximum q-norm of the gradient of f on X' coincides (for certain values of P N) with the best Lipschitz constant associated to the p-norm, where g is the Hölder-conjugate of p, i.c. p
I ++ 1. 1. Therefore, by using a partition H of the input space X' that is sulficiently refined to properly
capture the gradient variation of ff and computing the maximum q-norm of the least squares coefficients associated to each subset of H. a precise estimate of the Lipschitz constant is obtainable. Practically, in order to ensure that the refinement of the partition suffices the proposed estimation framework is designed
With respect ||
Sce Lemma B.2 in Appendix for formal statement.
TI the case where the upper bound K given in Assumption known beforehand it possible directly partition at the required refinement. level (See Theorem 3.10 for example).

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm 1 General LCLS
Algorithm 2 Hypercube LCT. pn [0, M/
Input: (Oracle), (Hr)zen (Partition Sequence)
Input: Ω (Oracle). K (Bound from
2 (covering con-
Output: {Lr} (Lipschitz Estimates)
stant)), o² (noise variance), (c, (precision)
procedure: LCLS (12, (H))
Output: f. (Tipschitz Constant Estimation)
initialise: I ++]
procedure: LCLS (f2, K, 77 (c,
repeat
initialise: - 0 + (Cr(d) MX).
L 5-0
NI (Cz(d, q) a ara22)
for H E Hz do
(X f(t)
t- D generated by
< hypercube partition [0, M] with side-length M
3 + (Xf x - ff
for H E H do
(x H f + D generated by Ω
L max (133) 11 Li)
3M - (X" x
-1x"T 3"
end I+-1 I+1 return (LrTTE
L + max 11a, L)
end return L
Figure 1: Algorithm 1 details the implementation of the L.CSS algorithm for a general input space and partition choice. Algorithm| details the theoretical smplementation given in Theorem 3.10 of the LCLS algorithmm when the input space is a hypercube [0, M and the portitions are regular. In practice, IE N and Nr E IR+ can be set heuristically in order to improve convergence. We note that the generated data points X used by the two algorithms are selected arbitrarily in each Hr. In order to ensure convergence of the LCLS algorithm, X will need to verify Assumption 4 for all I LEN N and H Hr.
as an iterative method that utilises sequence of increasingly fine convex partitions (Hr) that are given input. A brief technical description of an iteration of the algorithm be described as follows: For a given iteration, indexed by I E N, set of observations Df {LHH, fH, (t..)..( is generated by an oracle Q X + R (defined in Section 2 for each subset H of the partition Hi and used individually to compute the coefficients {BF) HeH of ordinary least squares regression for each subset H E Hr. The Lipschitz constant estimate can then be directly computed: L == maxHER, (1137 [11] where q is the Hölder-conjuguu of p.
Definition 3.1 (Notation Overview) For a partition H₂ of X and set of samples Dj = {(xss Fe) described above, we ulilise the following nolation.
1. The subset of samples that belongs to H Hr is denoted Dff == ((H FH. (E...... Note: samples can only belong to one subset H. If sample point is on the border between two sets, then il can be included in either design malris.
2. We denote the design matrices of the least squares regressions XI ER (d+1)) and the observation vectors I
HH
N.
Jm.
THe ?H1
a Ha
JHa
x
where Vk N/) and where
Fuwp
>f (HHs [Ho) a sample point contained in D# with J == 5((H.) and by abuse of notation; YHH Yzu,'
3. We denote by "0,,""" E Rd+1 (where 6/ E I is the intercept) the least squares coefficients associated to H E Hi and computed using X# and jH.
The LCLS algorithm is described here in its most general form in order to allow flexibility in the choice of the input space partitions and sampling scheme. Algorithm [ provides an algorithmic description of this approach. A more specific implementation of the LCLS algorithm which utilises a regular hypercube
@The method described in this algorithm corresponds the specific case where the (K, variables are known.
8

---

Published in Transactions on Machine Learning Research (09/2023)
partition of the imput space is given in Algorithm 2 and discussed later in this section in Theorem 3.10 and ensuing discussions. As one might expect, the structure of (Hr))en is key part of the LCLS estimator. Tn practice, these partitions can be defined using domain or functional knowledge in order to better estimate the gradient variation and therefore speed up the convergence of the algorithm. The distribution the sample points given by (NF) )eEN should also be considered carefully and can be selected a partition dependent way to take advantage of any prior knowledge of f or of the underlying noise distribution. We note that the relation between the structure of rHr) and (NF MEE is essential in the proofs of Theorem 3.7 and Theorem 3.10
The following variables are used to formally describe a partition belonging to (Hi)IeN-
Notation 3.2 Let 6(A) sup,, yEA l denole the diameler funccion and Bx(x) the d-dimensional boll centered in E X and with radius with respect to I1-1|2-
Definition 3.3 (Partition Variables) Let H. E (Hi)sen- We define the following two Hy related quantities: the maximum diamelers of Hy; [A A == 8(H) and the misiimmm diamelers of the biggest subset- inscribed balls of H.y {8f H 8 == 2 m E R+ e H such that Bx(z) H}.
The quantitics {a]) and {8 HeR, are used Definition 3.5 and in Theorem 3.7 to define sufficient conditions on the structure of the (H1)sen partitions in order for the general version the LCLS algorithm converge.
We conclude this subsection by giving a result on the computational complexity of the proposed algorithm.
Proposition 3.4 (Computational Complezity of LCLS) The computational complerity of the Lipschitz Con- stant Least Squares Estimator is (d& Neamples) where Reamples denotes the number of observations sampled by the algorithm and the d E N is the input dimension of the target function.
The computational complexity derived in Proposition 3.4 is significantly smaller than the complexity of Strongin- based approaches which is O (n camples) The difference in computation speed is illustrated em-
pirically on set of test functions in Section 3.4
3.2 General Theoretical Analysis
An investigation of the theoretical behaviour and performance of the proposed LCLS algorithm is carried out in this section. This analysis provides an understanding of the design constraints required for the con- struction of the input space partitions and for the choice of sampling schemes in order to ensure satisfactory performance see Remark 3.8] We begin by stating an asymplotic convergence result for the general form of the algorithm in the noiseless and general noisy sampling settings before stating and discussing finite sample results for a more concrete application of LCLS when the partition of the input space is constructed to of regular hypercubes.
The following definition defines two quantities (ar)reN, (by) function of {A Hen, {54 Hetry ((N } (eHz)Ien and ([Hrl)zeN in order to alleviate notation They will be used to describe the conditions on the structure of the input partition sequence needed in order to ensure asymptotic consistency.
Definition 3.5 For ony sequence of conver and compuct partilions, (Hi)reNs construct the following sequences:
(aI)IeNs as maxHER,
(bi)IeN, by = maxHeR,
(R
Before stating the first main result of this section, condition on the sampling procedure used by the LCLS algorithm and generalisation of the Oracle noise assumption of Section 2 are given.
Here. denotes the cardinality operator.
9

---

Published in Transactions on Machine Learning Research (09/2023)
Definition 3.6 Let H C X be compact and conver and denote by D {( tE the subset of generated or archived data samples H. We say that is (c, (c.))-covereed for > 0, e|o, 1| if there cxists an e-cover of H (with respect to I1-l12) with at least nN samples of Df in each of the balls associated to an element in the e-cover.
Assumption (Sampling) For a given n (0,1), the sampling scheme selected for LCLS such that VA E and AH HI, H. is ( -oocveeddd
The sampling condition stated in Assumption is used order to ensure the stability of the least squares coelficient as the sequence of partitions becomes increasingly refined and can be satisfied by using quasi- Monte Carlo schemes in practice. In essence, ensures that the samples are sufficiently well distributed in each subset H of the partition Hr, avoiding extreme cases such as when single sample input gets repeatedly sampled. A possible (conservative) value for 1) in the regular hypercube implementation of the vol(B, (((B,()) (0)) with ( denoting the volume of the d- 25042
LCLS algorithm of Section 3.3 given by 7
dimensional unit ball. In the proof of Theorem 3.15 under a uniform and independent sampling (on X') (0)) with high probability when the number of assumption, Assumption 4 is shown to hold for r 234+13d
observations is sufficiently large.
The second assumption of this section generalises the Gaussian noise assumption made in Assumption 3 include all distributions with zero mcan and finite variance and weaken the assumption of independence.
Assumption (Noisy Oracle General) Let a² and denole by D(0, o²) the set of all probability distributions on R with zero mean and finite variance o² O. We define a general noisy sampling oracle as
Ω: X
2 fn = f(x) +
where ~ Dr,, E o() are uncorrelated random variables (x X).
The general nature of Assumption ensures that the convergence results obtained for the proposed LCLS algorithm hold for a wide range of noise distributions and therefore removes the necessity of having to verify sub-Gaussian noise assumption when applying LCLS in practice.
Theorem 3.7 formalizes the consistency of the proposed Lipschitz learning framework for the general noisy sampling setting.
Theorem 3.7 (General Convergence Rate) If Assumptions the following condilions are verified:
5 (for given n E (0. 1)) hold and
VL E E, Hj is a convez partition of X, lim ar 0, lim b, =,=0, lim maXH (A = O,
then v DE D(0,0²), f (2
L,(
P I.
I+000
where L((f)= forp=1,2, Lp Li()) for forp>2 2. P denotes convergence in probability and (Li(f))EEN is the sequence. of Lipschitz constant estimates generated by the LCLS estimator.
Remark 3.8 (Design Constraints) Condition of Theorem 3.7 specifies the design constraints needed in the construction of the partition sequence (H1)IeN and the number of sample points ([N)) ((N(")HR))))) HENNz)Ie required per hypercube in order to ensure convergence. In particular:
1. lim = 0 provides the limitations on the shape of the sets in each partilion Hy as I goes to infinity. In particular, as I + 0o, (2 << 8/1 < AF
In the noisy sampling setting, lim bj = specifies a condition on the number of samples needed per lypercube. As + co, N >>
[Hal
This is made precise in the neat section in Remark 3.11
(8
10

---

Published in Transactions on Machine Learning Research (09/2023)
8. lim Max (A/) ensures that the partitions are increasingly refined.
In practice, applying the theoretical conditions used in Theorem 3.7 produces an overly conservative estimator in terms of required number of queries made to the oracle see Section 3.4 for an illustration of the empirical convergence of the LCLS estimator. This is due to the fact that the LCLS estimator makes minimal functiona assumptions and therefore has to explore all of &' to generate precise Lipschitz estimate. In order to avoid this issue, the number of samples per hypercube as mcasured by (bz) IEN can be set heuristically in order to improve the empirical performance.
In the noiseless sampling setting, the stopping and sampling rules given in Theorem 3.7 and Remark 3.8 can be modified in order to obtain a quicker convergence. This is detailed in the following corollary.
(for a given n (0, 11) hold, a noiseless oracle : X E is available and the following conditions are verified:
Corollary 3.9 (Noiseless Sampling) If Assumplions
1. VI E N, Hy is a convex partition of X,
2. lim 0g 0, lim MaxHER, (A 0,
3. VT E N, H E Hr, N 2 d 1,
then f (X,,
Li(f) Lp(f)
1400
where Lp(f) = Li( for p = 1,2, L,(f) 2 Li(f) for p > 2 and the right arrow denotes deterministic
convergence.
While, the conditions on the design constraints of the partition sequence needed to ensure asymptotic convergence of the LCTS algorithm remain the same as Theorem 3.7 the sampling conditions specified in Corollary 3.9 imply that a much smaller number of samples are required per hypercube. More precisely, the only sampling condition stated in Corollary 3.9 is related to the minimum number of samples needed to ensure that the local linear regressions computed by the LCLS algorithm are well-defined.
Using the general results developed in this section, we now explore a more specific application to the [0, M] input space. Theorem 3.10 provides finitc-sample sample complexity bounds for the LCLS in the general noise sampling setting that can be utilised when limited information on the noise distribution is available. As a consequence of Theorem 3.10 sample complexity rates in the noiseless and Gaussian noise sctting can also
be derived and compared to the lower bounds proposed in Theorem 2.2 and Theorem 2.5
This is discussed
in Remark 3.11 Remark 3.12 and Theorem 3.15
3.3 LCLS with Regular Partitions and Sample Complexity Upper Bound
In the previous section, we considered a general form of the LCLS algorithm and stated the conditions on the design constraints of the input partition sequence and the sampling scheme required to ensure convergence. Here, assume that the input space is the d-dimensional hypereube [0, Mjd and consider the case where every imput partition H., is a regular hypercube partition of side-length M The associated sampling scheme is then defined based on the sampling condition given in Assumption and the desired precision of the Lipschitz constant estimate.
Under these additional constraints, the following finite sample guarantee can be obtained for the LCL. algorithm.
Theorem 3.10 (Finite Sample Guarantee) Let X == [o and (HI)leNs, denote the regular partition of sub-hypereubes of X with side-length 4. If Assumplions
(for given n E (0,1)) hold and if dc > 0, 8 (0, 2), the LCLS algorithm is set with hypercube partition indered by I2 (d) vixe) and with
HH E H, NW 2 (C2(d, 4) 111 for Ca g) E ER,, then A D E D(O,
(f) - (f)) inf 1EC*(X.K)
(1)
11

---

Published in Transactions on Machine Learning Research (09/2023)
where 1p(f)= (ff) for 1,2 and L, 2 L, for p 2. Here Ci(d) 8d? /dd - - and C2(d,
2a dmaaa (2:1) however these constants have not been optimized.
The theoretical guarantees of Theorem 3.10 can be extended to inchude any X' C Rd that satisfies Assumption Indeed, trivially there exists a hypercube (a, bjd C Rd with a, b E IR such that X C b) which can be partitioned according to the iterative regular hypercube partitioning approach. The partition sequence inputted into the LCLS algorithm then consists of the regular hypercube subsets partitions of (a. bjd that intersect with L. In this case, under Assumptions ( 4 a modified version Theorem 3.10 holds: the condition on remains the same, but the lower bound condition on N/ can be weakened to become N# 2 (C2(d, 9) a (=-)))) 4H E H,, I E N, where r I( E =
Since Theorem 3.10 holds under Assumption 5 ie.. for any D E (((0,²2), n E N and any f E ( MJ0 K) it also holds for (uDDEeD(,,o)) SuP)Ec"((O.M))) ([),M])).)))) Therefore, using Theorem 3.7 we can obtain the following general sample complexity rate for the LCLS algorithm.
Remark 3.11 (Sample Complerity Noisy) For p p= 1,2, assuming that the lower bounds: I 12 (Ci(d) MK) and AH E Hr N 2 (C2(d, ④) o² M²)) are salisfied with on equality, the total namber no of points required
Viee
to ensure Pp Ż - <) 2 1 is given by
o² (Gid) n1 V
2d+2
M2 -0 -0
-0111
[MKK 2d+2 1
81 = H C2(d, a)
M2,2
This sample complexity differs significuntly from the lower bound on the sample complerity derived in Theorem This expected given the more general noise assumptions made Theorem 3.10
2.5
By slightly modifying the necessary conditions used in Theorem 3.10 we can also compare the sample
complexity of the LCLS algorithm implied by Theorem 3.10 in the noiseless sampling setting to the lower bound on the sample complexity of the noiseless Lipschitz learning problem stated Theorem 2.2 In order do so, we define
N(T) max min(ID]) DM contains a disjointed 8/ -cover of H} НеHr
which is constant V/ E N when (Hy)ren defined as sequence regular hypercube partitions on [0, Mjd. this case, we remove the dependence on I and write N == N(I). We note that the following two incqualities hold: (1) n & (tight) and (2) N vd" (loose).
Remark 3.12 (Sample Complezity Noiseless) In the case of noiseless sampling, the lower bound on N stated Theorem 3.10 can replaced by condition 3 of Corollary 3.9 and the definition of given above, i.e. VI E N. E Hy, N max(d 1, Proceeding as in Remark 3. 3.11 we have in this case:
MK n2 HHr = max(d++ +1, (C
VTC J² = -0
(0 MK (M (M)K))))
This convergence rate corresponds eractly to the lower bound on the noiseless sample complexity rate stated in the Theorem 2.2 and therefore implies that the sample complexity rate (Mr)) is optimal (up to constont factors dependent on d and p) in the sense that it characterises the minimum ramber of samples that are needed to oblain an e-precise Lipschilz consland estimate for any I E (x,
As in Section 2 can reformulate the sample complexity rates of the LCLS algorithm given in Remarks 3.11 and 3.12 as convergence rates and therefore as upper bounds on the convergence rate of the general Lipschitz learning problem. This is done in the following corollary.
12

---

Published in Transactions on Machine Learning Research (09/2023)
Corollary 3.13 (Convergence Rate Comparison)
1. (Noiseless) Assume the same setting as Remark 3.12 Then,
MK 4n
inf sup (2) (X,
|L -200 S C(d.p)
where C(d,p) p) can be determined from Remark
3.12
2. (Noisy) Assume the same setting Remark
3.11 Then, v distribution D E D(0,
M 742
K +=
sup inf PD; (p:() - - < <C 5, 2d
2 8
LE (2,))
where C(o², 8, d) can be determined from Remark 3.11
An interesting consequence of Corollary 3.13 is that it provides a way of generating a sequence of feasible To Lipschitz constant estimates that converge to the best Lipschitz constant a polentially loose upper bound on the second degree partial derivatives known. More precisely, one can consider the Lipschitz constant estimates:
Impps)== = C(d,))
MK Vn
in the noiseless sampling setting
-uupff:= = L(f)+ d)
M MarK in the general noisy sampling setting
where i(f) denotes the Lipschitz constant estimate generated by the LCLS algorithm. Such an approach is useful in practice as Lipschitz constant-based computational frameworks often rely on the assumption that the estimated Lipschitz constant used feasible. This briefly discussed further in Section where a direct application of the LCLS algorithm in the context of nonparametrie regression for system identification is developed.
Remark 3.14 (Knowledge of K and Assumplion 2) The theoretical resulls of the LCLS algoritim of this section have been stated under Assumption 2 and the knowledge of tight upper bound the second-order partial derivatives: K. This tightness is in fact not necessary and all result pertaining to LCLS hold for any upper bound K' 2 K. In this case, the LCLS algorithm simply ensures convergence for a larger class of functions, (2 K) C (2 K"), then required at a slighlly slower rale of convergence. Porthermore, while knowing an upper bound on is necessary in order for the theoretical properties of the LCLS algorithm to hold, the algorithm can still be implemented heuristically in practice without
We conclude this section by stating the asymptotic sample complexity rates of the LCLS algorithm under Gaussian noise assumptions and providing finite sample guarantee.
Theorem 3.15 (Asymptolic Sample Complerity Ganssian Noise) Let M E R4, d E, (1,2) and IIN) denote the regular partition of sub-hgpercubes of X with side-length M. 7. Assume that Assumption holds, that one has access to noisy oracle ÿt X R as specified in Assumplion 3 and that the sample inputs wriformly and independently sampled X. Setting the LCLS algorithm with a hypereube partition indexed by I = [C] MK for e > 0 (see below for definition of C2(d)), there exists C > 0 such. that if
2² Md kdt2 log( MK
n 2 C
ed44
Then,
lim -
sup (x,)
((Loss(ELn()) 110) x))
where (br()) denoles the the center of the hypercube associaled to orgmar 11 lla computed in Algorithm
Here, Ci(d) 164 Val Vad maxt 4.00
with vol(B; (0)1
2
V1
23a+133
10T.e which upper bound the best. Lipschitz constant and satisfy the Lipschitz contimuity condition. 11 woll Bi (0) denotes the d-dimensional unit ball.
13

---

Published in Transactions on Machine Learning Research (09/2023)
The asymptotic sample complexity rates derived in Theorem 3.15 match exactly the rates derived in Theorem This implics that O(" 000 MM k log( " is the optimal asymptotic sample complexity rate of the Lipschitz learning (search) problem and that the LCLS algorithm is sample optimal in the noisy setting when the noise is assumed to follow a Gaussian distribution. As done in Corollary 2.6 we can modify Theorem 3.15 order
2.5
gd44
show that the optimal asymptotic convergence rate O(MK (Iog(MKn) #41 We note that Theorem [
3.15 holds more generally for any sub-Gaussian noise assumption on the sampling noisc. In particular, the same convergence rate holds in the settings where this noise is assumed to be bounded which are often considered in Lipschitz-constant based applications (Canale et al. (2014), Sergeyev et. al. (2020))-
Replacing the random uniform sampling assumption of Theorem 3.15 with Assumption as done in Theorem 3.10 a small modification of the proof of Theorem 3.15 yields the following result on the finito-sample guarantees of the LCLS algorithm in the noisy sampling setting with sub-Gaussian noise.
Corollary 3.16 (Finite Sample Guarantee Gaussian Noise) Consider the setting of Theorem 3.15 As-
sume that Assumplions (2),
i (for a given rj (0, 11) hold, that one has uccess noisy orucle Q X - R
specified in Assumption SS. Ve (0, C 5 (0, 2), setting I = [C] MK and AH E H,
N 2 C (1)
log( 231
implies
log( )
sup P((L((f) -,,f0 >) 8.
(EC
Here, C1 defined as in Theorem 3.15 and (1, 2 2 however these constants have not been optimiized.
As done for the general noise setting in Corollary 3.13 convergence rates for the LCLS in the Gaussian noise setting can be obtained by reformulating the finite sample guarantees stated in Corollary 3.16 Then, following the approach described above, a sequence of feasible Lipschitz constant estimates converging the best Lipschitz constant be constructed;
Gouss::= == -(f) + C. Muta KuT in the Gaussian noise setting
up
VVno"log(MKn)
where L(f) denotes the LCLS algorithm with the hyperparameters set in Corollary 3.16 and C E R4 is constant that can be computed from (idd), C* (d, n)). We observe that this sequence of feasible Lipschitz constant estimates converges significantly faster than the one constructed above for the general noisy setting.
3.4 Empirical Performance:
The focus so far in this section has been on developing the theoretical properties of the LCLS algorithm. While that discussion is useful in itself as provides performance guarantees for LCLS as well as upper bounds on the sample complexity of the general Lipschitz lcarning problem, we are also interested in how the proposed algorithm performs empirically. In particular, we would like to compare the convergence speed of the LCLS algorithm to other theoretically well-behaved methods and to verify whether the theoretical computational advantage of LCLS (see Proposition 3.4 is observed in practice. In this subsection, inves- tigate these questions by illustrating the convergence rate and computation time of the proposed Lipschitz constant estimation method and comparing it against existing Strongin-based algorithms on a set of test functions with interesting properties in noiscless, bounded noise and unbounded noise sampling settings.
3.4.1 Experimental Setup
Table provides an overview of the four test functions that are used in the experiments discussed in this section. The choice of these functions represents different testing points that are of interest: Function (a) reaches the maximum of the normed gradient in a single unique point of the input space, Function (b) is a classical optimisation testing function which we have also defined to have large second degree partial
14

---

Published in Transactions on Machine Learning Research (09/2023)
Function
Error (Log Scale)
Estimation
Computation time
smonghn LCLS
mattoon Vallue
True UsScMiz Constare
String
LCLS
usde
(a)
Number of Sample Point Llog Scalo]
Number of Sample Points
Number of Semple Points
255
raber Varrper
Esto mation valiee
LCLS
Estimation
Jaschizz Lontamm
smorgin
to.s
(b)
Numbher of Samplin Paints (L Seale)
Number of Sample Points
Number of Sample Points
Nawmra ret
strongt UELS
Extimetion Erron
Essimation value
300 Number Sample
DE
120
200
200
300
(c)
Sample (Log Scale)
Semple Points
3 E E
Gronga L2LS
Esstire Son Eeror
Shorgin LCLS
ESt motion E 3.
Time
Fue LipcNIz COSSO
socngin
30t
2000
anto
Nd0
(d)
Number Sample Points (Log Scale)
Number of Sample Points
Number of Sample Points
Figure 2: Comparison between the performance of the LCT.S algorithm (in orange) and the classical Strongin algorithm (in green) in the noiseless setting. Each row corresponds to a different test function ((a) (d)) and each column represents different point of comparison between the two algorithms. From left to right: Column 1: Illustration of the target function where applicable. Column 2: Error of Lipschitz constant estimate the bound on the sample
complexity rate derived in Corollary 2.3 plotted (in black). Column Behaviour of the sequence of Lipschitz constant estimates. Column 4: Computation time required for each algorithm.
Function
Expression See Lemmn
Lipschitz Const.
Key Property
(a)
3.054
Lipschitz constant reached in a unique point. Large second degree partial derivatives (K).
(b)
(z) +
cos x cos (T2)
8.5776
(c)
cos(521)
5
Simple test function.
(d) See Lemiaa
A.1
30.5399
Higher dimensional input (R2).
Table 1: Test Functions. Note: Functions (a), (d) are based on the function set utilised in proofs of the sample complexity lower bounds of Section
derivatives, Function (c) is a trigonometric function which provides an illustration of convergence for simple (arget functions and finally, Function (d) is higher dimensional version of Function (a) with dimensional inputs. We do not explore higher dimensional versions (>3) of Function (a) as the convergence speed with respect to computation time of the Strongin-based benchmark algorithms is already very slow for Function (d) see Figure and ensuing discussion.
15

---

Published in Transactions on Machine Learning Research (09/2023)
Function
Error (Log Scale)
Estimation
Computation time
Estimation Error
Est matton Vallue
2030
M-Stron 18)
M-Strun 12.401
The Conslant
N-Stenn (1.35)
MdGioon 11:369
Uii
600
rebac Number Sample Points
(a)
Number Sample Points Scale)
Number of Sample Points
1000
Estimaaiion Valluee
1300
Miltren (1.6)
Tre Lipsch consiatt (0)
M-Siron (1.26)
LLLS
N Giar Chik
29 Number Sample Points
760 200n ww wbis navs 1990
(b)
Number Sample Points (Log Scale)
Number of Sample Points
Estrr stion trror
sztimation value
Mision (1.0]
Mediron
touan 12.20
LEUS
LCLS
1900
Stran,
(1.26)
JUN
32
(c)
Sample (Lag Scale)
Number Sample Points
Number Sample Points
Fuu Liachir Comstat
Esiimation Ereor
Stran, (B4
MStron 11:01
un
LELS
LCLS
LCL5
12
2
03
05
15
(d)
Namber Sample Points (Log Stale)
Number of Sample Points
Number of Sample Roints
Figure 3: Comparison between the performance of the LCLS algorithm (in orange) and the modified-Sttongle algo- rithm with a correctly (in green) and incorrectly (in blue) specified hyper-paranneter in the noisy selting, ach row corresponds different test function ((a) (d)) and each column represents a different point of comparison between the two algorithms. From left to right: Column 1: Ilustration of the target function where applicable. Column 2: Error of Lipschitz constant estimate- the bound the sample complexity rate derived Corollary [2.6 is plotted (in black). Column 3: Behaviour of the sequence of Lipschitz constant estimates. Column 4: Computation time required for each algorithm.
As benchmarks utilise the classical Strongin Lipschitz learning algorithm (Strongin 1973 in the noiseless setting and the popular modified Strongin-based Lipschitz constant estimator in the bounded noise setting (see in particular Novara et al. (2013), Calliess et al. (2020) and Khajenejadd et al. (2021) for applications in control problems). We note that this modified Strongin estimator strongly dependent on a precise estimate order properly specify ē E R4 hyper-parameter. Indeed,
of the smallest. upper bound of the noise if is smaller than b, then the Lipschitz constant estimates generated by the modified Strongin estimator converge to +oo the number of observations increases. In contrast, if ē is bigger then b then the generated Lipschitz constant estimates will converge to underestimate of L and never be feasible.
Benchmarking algorithms:
(Noiseless Selting) Strongin Eslimator:
1 f, 1 25,
L max 14j
16

---

Published in Transactions on Machine Learning Research (09/2023)
Esir Ssttration Valuee
Extimation Value
Estimatiion Value
Estimation
Lisch constant
-wo NiStron, 1h)
Stron.
Ettooon (8)
(1.21)
(2a0h)
(a)
(b)
(c)
(d)
Figure 4: Illustration of convergence speed relative to computation time in the bounded noise setting using the set of test functions given Table I We compare LCLS algorithm (in orange) and the modified-Strongee algorithm with correctly (in green) and incorrectly (in blue) specified hyper-parameter. We observe that the LCLS algorithm performs better on all test functions.
(Noisy Selling) Modified Strongin Estimator:
f fyl 2e
: max (F)
| xzyl
where is a hypeer-paromeler that eslimates the lighlest upper bound b on the noise. We consider modified Strongin Lipschitz estimators with correctly specified hyper-poramett (e 6) and hasper-parameter that is slightly larger than the true upper bound (E= 1.26) benchmarks.
3.4.2 Discussion
In Figure 2 we illustrate the performance of the LCLS algorithm against the classical Strongin algorithm on the proposed set of test functions. We plot the thcoretical lower bounds on the sample complexity rate found in Section
2 in order to provide an intuition for the theoretical bounds. As one would expect, due to the
fact that the Strongin algorithm was specifically designed for the noiseless setting, our proposed approach converges more slowly in terms of number of samples on all four test functions. However the difference in convergence speed is not significant and mitigated by the substantial divergence in computation time. We also note that the plotted sample complexity rate implied by the lower bound of Section does not appear be tight which is unsurprising as it represents a min-max type bound.
Remark 3.17 (Link between the proof of Theorem 3.7 and convergence of LCLS) From the proof of Theorem 7.7 we have that the convergence of the LCLS algorithm depends on two fuctors:
1. (I E N) the diameter of the subsets of the regular partition (upper bounded theoretically using Taylor expansion).
2. (N1, I T NN the number of samples in each subset (upper bounded theorelically using mullivariate Chebyshev inequality).
The relation between these two factors is essential for ensuring quick convergence of the LCLS algorithm. In particular, for cases where the second derivatives of the targel function. are large, N, can be decreased and I increased so that the LCLS algrithum considers finer partition of X (without having to increase the number of sample points). This type of modification improves the lincar approzimation of the gradient of f at the cost of increasing the noise in the local least squares estimates (see Function (b) Easom function in Figure 3)
In Figure 3 observe the performance of the LCLS algorithm in the bounded noise setting. Here, the convergence speed relative to sample size of the LCTS method differs more significantly from the convergence speed of the correctly specified modified Strongin benchmark algorithm. This is again unsurprising as the correctly specified modified Strongin algorithm makes use of additional information on the noise distribution and the choice of a uniform noise distribution in the experiment is beneficial towards its convergence speed
12 truncated Gaussian distribution had been used instead, the convergence speed of the modified Strongin estimator could have been arbitrarily slowed by decreasing the variance of the distribution.
17

---

Published in Transactions on Machine Learning Research (09/2023)
Extimation Valuee
Comiian Value
Est intiattion Villure
The (pscitz Condontt
hellioe LCLs Urbd hor
Uppchitz Canalent
Lipechtz Canalant
True Uppcciiz Cansomn
LCLD rakoc
LCLD fakus
LCIS fr Marie
Uibd relce
Unbd nelse
LCLS Unnd Mone
Ue
Ue
Nam bett of Semppe Puirils
Numbie of San gale Puints
Nam leet of Semppe Poirts
Number of Sample Points
LCLS 2o Noac
LLLS ad noke
LiL nd netse
LCLS- unitd wode
Keae
LCLS Unitd houm
Time tsl
Time
121 etc zee un 17
Number Sample Points
12. ca Lin 340
Sampll
gln
540
ole 2/ LK ca 1.
Sampll 307
Number of Sample Points
(a)
(b)
(c)
(d)
Figure 5: Illustration of the LCLS algorithm in bounded (in light orange) and unbounded noise settings (in dark orange) using the of test functions given in Table We observe no significant impact of the unboundedness of
the noise distribution on the Lipschitz constant estimates produced by LCLS.
We note that the modified Strongin algorithm with a slightly incorrectly specified lightest upper bound fails to show any sign of convergence and that the difference in computation time is more significant than in the noiscless sctting. The relation between computational complexity and convergence rate of the LCLS and modified Strongin Lipschitz constant estimators is illustrated more precisely in Figure 4 by plotting the convergence rate relative to computation time. We observe that the LCTS estimator performs better on all functions in the test set despite the fact that the modified Strongin estimator utilises additional information on the noise distribution. In particular, for Function (d) which takes inputs in R2, the LCLS algorithm needs 8.5 seconds to generate estimates with an estimation error < 0.5, while the Strongin approach needs approximately 4000 seconds. This suggests that for application scttings with high sampling capacity and time constraints, the LCLS method should be used even when the modified Strongin algorithm can be properly specified.
In Figures maximum of the second degree partial derivatives than the Strongin-based methods. This can be observed by noting the difference in convergence performance for Function (b) relative to the other test functions 13 and due to the fact that the LCI.S algorithm depends on the maximum to define a sufficiently refined partition of the input space in order to 'localise" the computations and generate local Lipschitz constant estimates, see Remark and Theorem 3.10 for precise characterisation of the relationship. In some sense, the stronger dependency on the maximum of the second degree partial derivatives of the target function can be interpreted as trade-off for the improvement in computation time obtained by the LCLS algorithm.
2 B and the performance of the LCLS method seems to be more dependent on the value of the
The last illustration, provided in Figure 5 shows the convergence and computation time of the LCT.S algorithm in the unbounded noise setting. We do not provide a benchmark as no alternative theoretically backed approaches exist in this setting: the approaches of Beliakov (2005) and Callicss (2017) could be used but do not have any asymptotic convergence guarantees. Instead, we compare the convergence rate to the one obtained by LCLS in the bounded noise setting and observe the fact that no significant performance loss has occurred when the noise is unbounded on any of the test functions.
We conclude this section by remarking that throughout the experiments, our proposed method has been relatively unaffected by the changes in sample sctting assumptions and can be used with minimal fine-tuning. Indeed, only the relation between the nunber of samples in each subset and the diameter of each of these subsets needs to be modified (see Remark (..77. This relation can be set a theoretically principled manner by considering the results given in Remarks 3. 3.12 and Corollary 3.16 or treated as a and set more heuristically. The flexibility of the LCLS algorithm is in contrast to existing asymptotically
19See also Figure and ensning discussion.
18

---

Published in Transactions on Machine Learning Research (09/2023)
consistent Lipschitz learning algorithms such as the benchmark approaches used in this section which either only consider noiseless sampling settings require prior knowledge of the noise distribution in order to be applied.
4 Connections to Machine Learning and Related Fields
The thcorctical results derived in Scction 2 are fundamental in nature. They can be used as benchmark when developing novel Lipschitz constant estimalors or more generally to provide a better theorelical un- derstanding of algorithms that depend explicitly on Lipschitz constant estimates of an underlying target function. Utilising Corollaries 2.3 and 2.6 the worst-casc cstimation crrors of Lipschitz constant estimation can be better understood and their negative impact on overall performance mitigated. This is particularly important Lipschitz constant dependent algorithms often rely on heuristic or experimental arguments which might not always hold in practice to justify the Lipschitz constant estimation step.
In some settings, the LCLS estimator developed in Section + can be directly applied to improve existing computational frameworks in which case the finite sample guarantees derived in Theorem 3.10 1.10 Corollary 3.13 can be used. particular, when a (loose) bound on the second order partial derivatives of the target lunction known, & sequence of feasible Lipschitz constants converging to the best Lispchitz constant at a known convergence speed is obtainable. Unfortumately, while this approach is possible in all the sampling sct-ups considered in this paper, the convergence rates obtained for the noisy sampling sct-up (sce Corollaries 3.13 and 3.16 can be too slow to be useful in some practical applications. In these cases, the LCLS estimator can be applied directly to estimate the Lipschitz constant without feasibility guarantees.
In the section below, we bricfly discuss how the results and algorithms derived in this paper can be used in the fields of system identification ion and global optimisation.
4.1 Global Optimisation:
A major subfield of global optimisation research focuses on sequential search methods that explicitly utilise the Lipschitz constant of the target function to remove large sets in the search space and enhance the efficiency of exploration (Shubert) 1972), Mladinco (1986)). As good estimate of the Lipschitz constant is not always available in practice, work arounds must be be found (Jones et al. (1993)). In particular, a number of these optimisation frameworks make use of Lipschitz constant estimator (Kvasov and Sergeyev (2012) and references therein, D'Agostino (2022) ). The computation of these estimates is generally done heuristically without convergence analysis or crror-cetiificate of the Lipschitz constant estimates. Therefore, the minimax bounds derived in Theorem 2.2 of Section 2 provide a context for the expected performance of these methods. More preciscly, given recent work by Malherbe and Vayatis (2017) and Bachoo et al. (2021) which derives optimal sample complexity rates for Lipschitz Optimisation when a Lipschitz constant is known, it becomes possible to derive a lower bound on the sample complexity of adaptive Lipschitz Optimisation algorithms that separate the optimisation procedure and the Lipschitz constant estimation. We derive such a lower bound below an example of how this can be done.
Following the set-up of certified online learning algorithms described in Bachoc et al. 2021 we assumne that we have access to a black-bo box target function f that can be queried to obtain noiseless observations. The goal of certified global optimisation is to design an algorithm that systematically queries f in order to generate an output sequence ((r,, I (x ) (n)) where on the n-th query point, fxx;) is the generated estimate of max (z) after n queries and Gn 2 is an error certificate that guarantees: max f(z) - f(x;)) S G..
R4, we then define the sample complexity 14 N(A,f.e) of certified global optimisation algorithm A as the smallest number of queries needed in order to obtain an error certificate smaller than for all belonging to function class C, or in other words:
Given accuracy
f.c) := minfn e Nuf+oollG, < <c}.
Notoe: this differs slightly from the definition used in Bachoe al.
2021
19

---

Published in Transactions on Machine Learning Research (09/2023)
LCLS-KI
LACKI
LACKI- LACKI-Wrong
NN-KI
LCLS-0 diicue of teuth Thering data
UKCH Crourd truth Tuiring data
Whoogg drourdl bruch Thaning Data
MI-10 Crece al truth Thaning
25
Figure 6: Muutrtationn of several nonparametric methods applied noisy data. The target function x cos((1 + 2x and the noise is distributed according to a truncated Ganssian distribution (std: 1, upper/lower /lower bound: 2/22). The predictions of the trained methods are plotted in orange and the training data in light blue (800 observations). From left to write: LCLS-KI, Kinky inference using the Lipschitz constant estimate generated by the LCLS algorithm. LACKI: Adaptive Kinky Inference proposed by Calliess et al. (2020) with correctly set error bounds. LACKI-wrong: LACKI method with error bounds set at the wrong observational error bound (i.e. at 1.3x the true error bound). NN-KI: Kinky inference method using the Lipschitz constant of fitted Neural Network model with sigmoid activation proposed by Milanese and Novara 2004).
Utilising this thcoretical set-up, we can then combine the theoretical results of Bachoc et al. (2021 with Corollary 2.3 in order to obtain the following statement on the worst case lower sample complexity bound of the adaptive Lipschitz optimisation problem.
Proposition 4.1 (Sample Complexity Adaptive Lipschitz Optimisation) Assume that X is the hypercube and consider the set A of adaptive Lipschitz optimisation algorithms which combine classical Lipschitz opti- misntion methods with a separabla feasible Lápschilzz conslant estimator. There erists conslants C1, C2 > such that 4 2 0, A A and E (0, Eu) where En E (0, 20.2"11
sup (EC=(XXK)NF,(F)) fc)
3 2 Ciaa(M, L" K)((1 + C2 max(min(
1 C2' [11 + loga (2))) + 3(L, K,,) ) 7a(M, (), B(L,, )a -
(2)
where m := max fly), Vx Md, K is as defined in Assumption and
aa(M,L", K) = yd represents the problem's 's general dependency on the input space size, true best Lipschitz constant of the target function and desired precision of the optimisation algorithm and second degree partial derivatives.
cc)" = (1+ logz("2 2 1/ Ks represents the dependency on the true best Lipschitz constant of the largel function, the second degree partial derivalives and and desired precision of the oplimisation algorithm.
Ta(M,L',e) ;= consland of the largel function and desired precision of the oplimisation algorithm and second degree partial derivatives.
V--M represents the dependency the input space size, true best Lipschitz
L-(dd-1)
To our knowledge, (2) is the first lower bound on the sample complexity of adaptive Lipschitz optimisation frameworks (see Malherbe and Vayatis (2017) for a possible sample complexity upper bound provided by the adaL.IPO algorithm). Tt. depends orders of differentiation of f. The structure of the proof of Proposition 4.1 as well as the two terms contained in the max expression of the lower bound can be interpreted as a comparison between the sample complexity arising from the optimisation procedure and the one arising from the Lipschitz constant estimation. In particular, "a(L", .M.e) is computed by considering the subset of linear functions of C² ()) (L*) which A(L*.K,e)
the input space, desired precision and upper bounds the first. two
is trivial to optimise in the case where the Lipschitz constant is known but becomes complicated to certify if the Lipschitz constant cstimation is difficult.
15 other words, only knowledge of the Lipschitz constant estimate used the optimisation part of the algorithm.
20

---

Published in Transactions on Machine Learning Research (09/2023)
Mean Abs. Prediction Error
LACK
044
LACK Wrong
0.3
0.1
00
A 2,
4,
À
Figure 7: Mean absolute error of the nonparametric methods discussed in Figure and the neural network utilised to estimate the Lipschilz constant in the NN-KI method. The larget functions are given by /A : r cos(2Arz)) + Ar, for A = 1, 4, 10 and associated maximum second derivative: K == max (x)x) 40, 158, 632, 2526. The values shown in the plot are computed on a test set containing 500 independently sampled observations.
Unfortunately, the proposed bound is loose as the sampling scheme for the Lipschitz optimisation algorithm can differ significantly from the sampling scheme of Lipschitz constant estimator and is of moderate interest as it only considers subset of adaptive Lipschitz optimisation algorithms. It does however provide an example of how the lower bounds derived in Section of this paper can be utilised to theoretically analyse existing computational frameworks that rely on Lipschitz learning and future work will consider refining the lower bound given in
Finally, we note that the lower bounds derived in Section 2 can also be considered in the application of recently proposed batch Bayesian optimisation frameworks (González al. (2016), Alvi et al. (2019)). Indeed, while these methods provide interesting experimental results, the convergence bound stated in Corollary 2.3 shows that in the worst case the Lipschitz constant estimate generated from the fitted Gaussian Process can differ significantly from the true Lipschitz constant severely impacting the performance of the algorithm in high dimensional settings. At best, the Lipschitz constant estimate used in these papers: max ||zv (z)]l must be replaced by max [x)]())]] + C(d, p) MK in order to ensure that the estimated value is a feasible Lipschitz constant. Here by denoles the mean function of the gradient function estimate associated to the fitted GP which can be computed efficiently using the covariance function of the GP.
Yn
4.2 Nonparametric Regression for System Identification:
A popular system identification method in control settings known as Nonlinear Set Membership (Milanese and Novara (2004)) and also referred to as Lipschitz interpolation (Beliakov (2006)) or Kinky inference (aalliess et al. (2020)) by subsequent authors, explicitly utilises the Lipschitz constant of an underlying Lipschitz continuous target function to define the smallest set of all possible systems that is consistent with the observed data and to provide optima point estimates. the relevant literature, a number of approaches have been used to estimate the Lipschitz constant however these either rely on heuristic estimation such
(Milanese and Novara 20044), Calliess (2017)) or on knowledge of often unavailable syper-paramesd tight bounds on the noise Novara al. (2013) Callicss et al. (2020)) which undercstimate the true Lipschitz constant. Utilising the LCLS algorithi developed in Section 3 would therefore be interesting alternative approach to constructing an adaptive Nonlinear Set Membership framework. As noted at the beginning of the section, we directly utilise the Lipschitz estimate produced by the LCLS estimator as the worst-case error guarantecs stated in Corollaries 3.13 and 3.16 are too conservative to be useful in the considered use case.
In Figure 6 we illustrate the performance of hybrid LCLS Kinky Inference method in comparison to other nonparametric methods that depend explicitly on the Lipschitz constant of the target function. The variation of the plotted nonparametric predictors is direct function of the Lipschitz constant estimated from the data when the Lipschitz constant estimate underestimates the true Lipschitz constant flatter prediction curves that do not fully capture the nonlincarity of the target function are produced while Lipschitz constant estimates that overestimate the true Lipschitz constant produce overly input sensitive predictions. In fact,
16 Milanese and Novara 2004
21

---

Published in Transactions on Machine Learning Research (09/2023)
the kinky inference framework converges to nearest neighbour estimator as the Lispchitz constant goes to infinity (Maddalena and Jones (2020)).
In Figure 0 we observe that under the truncated Gaussian noise assumptions, the proposed LCLS-KI approach seems to perform best in comparison to the other nonparametric methods as long as the bound on the second derivative K (see Assumption 2 is not too large relative to the number of observations in the training data. As noted in Section 3.4 this is due to the fact that the LCLS algorithm is more dependent on K than other classes of Lipschitz learning algorithms and can significantly underestimate the true Lipschitz constant when K is too large. Therefore, when the second order derivatives moderate and upper bounds on the noisc on the noise are not procisely known, the LCLS-KI algorithm provides an interosting alternative to existing nonlinear set membership/ Lippchitzz interpolation methods. Applications of LCLS-KI to the common- use case of such methods, e.g. in learning based model predictive control (Canale et al. (2014) Limon et al. (2077), could be pursued in future work.
5 Conclusions
In this work, we have established precise lower and upper bounds on the sample complexity of the estimation of Lipschitz constants under minimal parametric constraints on the target function. Instead, our bounds rely on the assumption of C2 regularity of the target function which, given a compact input space, implies the existence of an upper bound on the sccond degree partial derivatives (this type of assumption is unavoidable as if the second degree partial derivatives are not assumed bounded, then the sample complexity can not be guaranteed to be finite and any theoretical characterisation of the general Lipschitz learning problem is trivial). The obtained bounds on the sample complexity are shown to be optimal in the noiseless sampling setting and in the noisy sampling setting for a slightly modified but generally equivalent version of the problem under Gaussian noise. These results can be used to provide a theoretical baseline for the Lipschitz learning problem and help drive the design of future black-box Lipschitz constant estimators.
In order to derive the upper bound on the sample complexity, we have proposed new algorithm for Lipschitz learning based on local least squares regression that is sample-optimal in the noiseless setting and in the noisy setting with Gaussian noise. We have thoroughly investigated the theoretical properties of this algorithm showing asymptotic consistency, guaranlees on finite sample behaviour and computational complexity in both noiseless and general noisy sampling settings.
A scries of brief empirical experiments illustrate how these thcoretical results could translate into practice and how the LCLS algorithm can compare to existing classical Lipschitz constant estimators. The proposed method provides suitable solution for Lipschitz constant estimation when theoretically principled and computationally flexible approach is desired.
Forthcoming work on LCLS will focus on extending the algorithm to recursively compute local Lipschitz constants on observed data and to provide theoretical guarantees on this extension. In addition, future work on theoretical Lipschitz learning could look to improve the sample complexity bound in the noisy setting derived in Section 2 under stronger assumptions on the target function and by restricting the class of Lipschitz learning algorithms.
6 Acknowledgements
We gratefully acknowledge support from the Oxford-Man Institute of Quantitative Finance (OMI) and thank the reviewers whose feedback improved both the quality and the clarity of this paper.
References
Absan Alvi, Binxin Ru, Jan-Peten Calliess, Stephen Roberts, and Michael A Osborne. Asynchronous batch Bayesian optimisation with improved local penalisation. In International Conference on Machine Learning, pages 253 262. PMLR, 2019.
22

---

Published in Transactions on Machine Learning Research (09/2023)
François Bachoc, Tom Cesari, and Sébastien Gerchinovitz. Instance-dependent bounds for zeroth-order Lipschitz optimization with error certificates. Aduances in Neural Information Processing Systems, 34: 24180 24192, 2021.
Gleb Beliakov. Monotonicity preserving approximation of multivariate scattered data. BIT numerical math- ematics, 45(4):653-61) 667, 2005.
Gleb Beliakov. Interpolation of Lipschitz functions. Journal of computational and applied mathematics, 196 (1):20-44, 2006.
Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu. Lipschitz bandits without the Lipschitz constant. In International Conference on Algorithmic Learning Theory, pages 144-158. Springer, 2011.
Adam D Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12(10), 2011.
Jan-Peter Calliess. Lipschitz optimisation for Lipschitz interpolation. In 2017 Americun Control Conference (ACC), pages 3141 3146. IEEE, 2017.
Jan-Peter Calliess, Stephen J Roberts, Carl Edward Rasmussen, and Jan Maciejowski. Lazily adapted constant kinky inference for nonparametric regression and model-reference adaptive control. Automatica, 122:109216, 2020.
M Canale, L Fagiano, and MC Signorile. Nonlincar model predictive control from data: a set membership approach. International Journal of Robust and Nonlinear Control, 24(1):123 139, 2014.
Ankush Chakrabarty, Devesh K Jha, Gregery T Buzzard, Yebin Wang, and Kyriakos G Vamvoudakis. Safe approximate dynamic programming via kernelized Lipschitz estimation. IEEE transactions neural networks and learning systems,
2020.
Danny D' A'gosstioo. An efficient global optimization algorithm with adaptive estimates of the local Lipschitz constants. arXiv preprint 2XXx:2211104411 2022.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation ofLipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
K Ferentios. On teebycheff's type inequalities. Trabajos de Estadistica de Investigacion Operativa, 33(1): 125, 1982.
Javier González, Zhenwen Dai, Philipp Hennig, and Neil Lawrence. Batch Bayesian optimization via local penalization. In Artificial intelligence and statistics, pages 648-657. PMLR, 2016.
Donald R Jones, Cary Perttunen, and Bruce E. Stuckman. Tipschitzian optimization without the Lipschitz constant. Journal of optimization Theory and Applications, (9(1):157 181, 1993.
Mohammad Khajenejad, Zeyuan Jin, and Sze Zheng Yong. State and unknown terrain estimation for planetary rovers via interval observers. Advanced Intelligent Systems, page 2100040, 2021.
Dmitri E Kvasov and Yaroslav D Sergeyev. Lipschitz gradients for global optimization in one-point-basee partitioning scheme. Journal of Computational and Applied Mathematics, 236(16):404244000 2012.
Daniel Limon, J Calliess, and Jan Marian Maciejowski. Learning-based nonlinear model predictive control.
IFAC- P.--PapersOOniine, 50(1):7769 (767)-776-77776, 2017.
Emilio T Maddalena and Colin N Jones. NSM converges to k-NN regressor under loose Lipschitz estimates. IFFE Control Systems Letters, 4(4):880 885, 2020.
Stefan Magureamu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms, In Conference on Learning Theory, pages 975-999, PMLR, 2014.
23

---

Published in Transactions on Machine Learning Research (09/2023)
Cédric Malherbe and Nicolas Vayatis. Global optimization of Lipschitz functions. In International Conference on Machine Learning, pages 2314-23233 PMLR, 2017.
Mario Milanese and Carlo Novara. Set membership identification of nonlinear systems. Automatica, 40(6): 957-975, 2004.
Regina Hunter Mladineo. An algorithm for finding the global maximum of a multimodal, multivariate function. Mathematical Programming, 34(2):188 200, 1986.
Carlo Novara, Lorenzo Fagiano, and Mario Milanese. Direct feedback control design for nonlinear systems. Automatica, 49(4):849 860, 2013.
losif Pinelis and Aleksandr Ivanovich Sakhanenko. Remarks on inequalities for large deviation probabilities. Theory of Probability & Its Applications, 30(1):143-148, 1986.
Yaroslav Sergeyev. An information global optimization algorithm with local tuning. S1AM Journal on Oplimization, 5(4):858 870, 1995.
Yaroslav D Sergeyev, Antonio Candelieri, Dmitri E Kvasov, and Riccardo Perego. Safe global optimization of expensive noisy black-box functions in the 6-Lipschitz framework. Soft Compuling, 24(23) 17735, 2020.
Bruno O Shubert. A sequential method seeking the global maximum of function. SIAM Journal Numerical Analysis, 93))379--888 1972.
Charles J Stone. Optimal global rates of convergence for nonparametric regression. The onnols of statistics, pages 1040-1053, 1982.
RG Strongin. On the convergence of an algorithm for finding a global extremum. Eng. Cybernetics, 11: 549 555, 1973.
Roman Strongin, Konstantin Barkalov, and Semen Bevzuk. Acceleration of global search by implementing dual estimates for Lipschitz constant. In International Conference on Numerical Computations: Theory and Algorithms, pages 478-486. Springer, 2019.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incor- porated, 1st edition, 2008. ISBN 0387790319.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Newral Information Processing Systems, 31, 2018.
Yining Wang, Sivaraman Balakrishnan, and Aarti Singh. Optimization of smooth functions with noisy observations: Local minimax rates. Advances Neural Information Processing Systems, 31, 2018.
GR Wood and BP Zhang, Estimation of the Lipschitz constant of a function. Journal of Global Optimization, 8(1):91-103, 1996.
Yihong Wu. Lecture notes on information--hhoordicc methods for high-dimensional statistics. Lecture Noles for ECE598YW (UIUC), 16, 2017.
24

---

Published in Transactions on Machine Learning Research (09/2023)
Appendix: Contents
A Proofs:
Lower bounds Sample Complexity
26
B Proofs: Thcorctical Propertics of LCLS
30
B. Technical Lemmas
30
B.2 Proof of Main Thcoretical Propertics of LCLS
34
C Proofs: Sample Complexity of Adaptive Lipschitz Optimisation
44
25

---

Published in Transactions on Machine Learning Research (09/2023)
A Proofs: Lower bounds on Sample Complexity
F) Lemma A.1 (Properties F) For C1, C2 E R, define the function 9o - + I.
(0 = Cie 1- E E 3
CC Ei= 2j <1
o otherwise.
The following properties of go can be shown;
1. max [V R 0.80.
2. AAEEERR
do (1) ~ 7.750, dE,T,
Proof Let go be as described above. It follows from construction that go is a radial function and that there exists u [0, t0o) + I2, such that Vz E R2, "(Ein x²²) = (o(x) (and in other terms, Vr E [0, +00), u(r) == go O,., ). We can compute the maximum magnitude (in I1-I12) of the gradient of go as follows;
d
max FERd
[go(z)]l2 = max ||
20juu
Σ 2
2222'
Σ
2
1l2
maxt SER
2n
Σ
||
=ERd
max 2u rER+
(r²)r(= 22'(13)))
0555 0oz
max
20 201C2r
(1
C Oz
C2
CIVC2
05
max
2r
e
r2)2
Computing maxogrs1 (2r e (1-r-)² gives maxogrsi (2r e (1-r2)²
W33 (v3-3)
Since go continu-
ously differentiable and the support of Vgo compact, we have that there exists I E Rd such that va
[V Il2 = C Ci atzs (V3-3)=
vi = V..
Similarly, we have that for i E d}, x E Rd;
8 g0 (r) = 2u
d
Σ 1
4a²u"
Σ x
du
8 (x)) either (1) x = 0 or (2) xタ = 0, Vi + j. In the first case;
Here is clear that for x² E argmax
we can compute max 12 (r) = 8G = C.. In the second case, setting x = re,, we consider the computation of maxyeR. 2n (r²) + 4: (r²))() We have
2r'()2) + 4 ( = 2C,Cee + 3C3 -1
(1 - C2r2)4
and can compute
3C3
max FEX+
12u
47 u(())) + C2 max
relx
1e 1-mdd
(1- C2r2y1
R 7.750
Therefore, we have max
80 (x) ~ 7.75C Cz. Finally, we check vi + (1, d}, max dale,
8 (x)1
max |42 E 2- Clearly, we can set x = re: + sej for r, E R.., Computing this quantity gives;
4rse 1-
8v2e-22v2
max ZERd
4r, "
x
C2O2
max (r,a)ER, xR,
(1 C2(22 2))3
C.
(V2 - 2)3
1=1
We obtain vi # jE (1, d.. max Du,e,
8 (x)) ~ 1.85C C2 < max ga
8 (z)l.
26

---

Published in Transactions on Machine Learning Research (09/2023)
Proof of Theorem 2.2
(Sample Complexity Bound Noiseless).
Let p = 2. If we can show that there exists a set F C (X, K) (F.,) of functions that can be constructed
such that
vř E Lnp(d), sup [f( - 1,(1)>
fer
when < (C(d.p) MK M equivalent stalement;
Ma)a then Theorem 2.2 follows directly. This expression can be simplified to the
vi (2),)), E F such that |E()) --)))( >c.
Consider the following functional family. For C1 E ER, C2 R..
Cie 1-02 30 rd (og <1 }.
FolC1, C2) = {g: R2 + R|2 E x.
otherwise.
For any I.", we can consider the family (C1, C2) by adding linear component, e.g. L'n to 9, Fo(C,, C2). In this case, we have by the construction of Fo C2) that for all J E Fu(C1, C2) with support in X and of E (I, C2), E X, max V/ (1))l2 max (1) Lt and ) 88 (x) max (.E(L......)) 02,zy The second relation is obvious while the first Baie
maxgER=AAJ((L. (I.(....
follows from the fact that all dh E F(C1, C2) are radial functions which implies that all gradients of ge are either pointing towards or away from z with equal magnitude along any hypersphere of fixed radius. There- fore, by the properties g shown in Lemma A.1 for any choice of linear component L Id + IR ((x) ar +b for a E Rd, b E R such that ||a||2 L", there exists X' E X' such that max [V RR,
1|V9((>*)]l> and (x"("") and have the same direction (if they have opposite direction it suffices to take x² that is diametrically opposed the same hypersphere). With this construction,
Vf (x)ll2 = (x") + all2 = [x)(( + ||all2 = max VVg (x) + I.- zERd
max ZERS
We can therefore restrict our proof to considering the case where L = O.
In the first part the proof, we will show that for carefully selected values Ci E R contains MKyd yd disjointed Illla-hyperspherss B {B..)e (xX)) y of radius Vcg such that; YB, Bg E B,
if + j and a set F C Fo of associated functions with the following properties; Ygs, E F associated to B, E B,
B, C X, B, =
supp(g=.) = -B,,
2. max,ex VV (x)]l2 2 2e (+L' if #0)
89
3. j E (1,..., d}, max dere,
(x) < K.
To do so we consider the gradient and second order partial derivatives of the functions in F. Let g E F, applying Lemma A.I. we have
max,eRs Vg(x) = O.CIVC (f
)'((2) 7.75CIC2.
max AJE(L,..
da,a,
Using these values, we can define the values of Cf and C discussed earlier in the proof. Firstly, in order 8'1 have g E (Rd R K), we need max i. de.e; (x)) $ K. This implics the relation C1 7.75Ca' Sccondly, we set C2 such that max [[ 0.8C V2 2c. Plugging in the relation for C₁ given above;
K
0.1K
K
51c²
= 2e #
)2 = Cy and C =
V
20c
K
27

---

Published in Transactions on Machine Learning Research (09/2023)
Setting 1 = V we have
20c
supplg
Σ 1 <1)= Bi(c) I E TR C2
where (2) denotes the d-dimensional ball of radius defined with respect | and centered in E X. The last step before defining F is to count how many sphere of radius I can fi in X [0, M] Here, we use lower bound that is obtained by considering the regular hypercube partition of X' of side-length I, defined by; := =L and [ = M. Let B denote the set of balls of radius that can be inscribed in subset belonging to the hypercube partition of X. Then, for all B, B3 E B, B, C X and B, BB 0. Furthermore, MK) (+ constant).
N.
we have [ = ( yd
20c
The associated set F of functions can be constructed by utilising the set 2 of ball centers zi for B, B and the values Cf, C2 computed above to define
F fg= E F, 2)U
where f = O. Suppose that 1 (Mx)* and consider an arbitrary f. E (.tp( By construction, there exists a ball B in the set B with associated ball center = E Z (as defined above) such that no observations are sampled in B. Therefore, if the unknown target function f [g2. then ((x)) G R(x) 0. This implies that can freely set the target function to either gº or fo with change to the Lipschitz constant estimate generated by L. It then suffices to select 9. if L generates a prediction that is smaller than e and fo otherwise. As the choice of was arbitrary, this implies that:
20d
vî. E C., E F such that [L()) - <iff>>c
and therefore:
inf Le (E
sup
((f)) 4,(0) >
Utilising norm equivalences and Temma B.2 obtain that in the case: p 1, the sample complexity of the Lipschitz learning problem can be lower bounded by (C(d) (C) M where C'd))
can apply similar arguments to the ones given above to
20d
Proof of Theorem 2.5
(Sample Complexity Bound - Noisy).
Let > 0 be sufficiently small such that 40c < M (which implies that the packing number N(X, 20c > 0). K Consider the maximal packing B, of X of radius 20s with respect to ||-I12 and the associated class of functions Fo defined in Lemma A.T which we denote F. in this proof in order to explicitly mark the dependence on (we only consider Fi, defined above for L - 0). We recall that for all B e B, and associated fs Fe: maxzen a || [/ 2e and max [n(()) = 0. Therefore, by construction of Fe, we have for any distinct pair of functions f1, E Fe,
K
K
Vr E X, max (Loss(æ, fi), Loss(R, f2)) max [1] I'I. L c
with == 2e. This implies that
inf sup P(Loss(pL1)) 1() > LEC (2) (2))(2.K)
inf sup P(f + f).
ĀEh feF.
17 Which define the subset of X where is non-zero. 18This is often referred "packing" X' by balls radius and the maximum cardinality such set called the "packing number" denoted ((X.I).
28

---

Published in Transactions on Machine Learning Research (09/2023)
where H. denotes the class of algorithms that utilise the data samples C in order to select the correct in Fe. In order to lower bound the right hand side of the above equation, Fano's Lemma can be applied. To do so, we first estimate log((Fel) and JaEF, KL (PF, (lps,) where Py denotes the density defined on (X', of noisy sample (x, fe) associated f f F. (defined more precisely below). The first term: (og((F.)) follows directly from the proof of Theorem 2.2 where obtained that |Fel |B.]| 2
MK which implies 20c
MK
log(IFe)) 2 d log(
20c
Let Fe. Denoting the density of the uniform measure on X' An and the density of the Gaussian measure I with mean R and variance o² Vu,o², have Vo X, y R, py(x, v) (2))) Then, the second term can be upper bounded follows:
SrL
Píi (x:()) d(x,y) (f.
sup KL (PA (P%))= J.FE..
Pn (r, log
xxx
=
S ")(())==V)) log (((w))
(x)du(x)da
(1) 1
[f(()) 22(x))2>x(x)dd
)falo), (v)
20
x
(1)
1 f fall (ol(
(a(ddd
where Be denotes arbitrary ball in the packing defined by Be. (i) follows from the well-known KT- divergence of univariate Gaussians and (ii) follows by construction of F.. By the proof of Theorem 3.7 we Furthermore, Soa((B.) (=(x)dx
have for all B Be and associated SB E Fes sup [f((x)] Ci 51.² K-
C (B. = 2 Mdd
20c for some constants ,, E == c(d) > 0. Therefore, there exists constant c 0 such that MK
d+4
KL (pn (1m) MdKa+2 f.hE..
sup
Applying Fano's Lemma, we obtain for arbitrary ordering of Fe:
inf (x) (X) (X))(X.K)
sup
((Loss((L()) L(f) (5) > E)
2 1 log(2) nssu
SI.EEF KL (p))) log( (F.))
21 log(2) + n 2 Makat
21
dlogg MK
20c
Therefore, for sufficiently small and any arbitrary 8 E (0, 1),
inf sup P(Loss(z'M), M0) e) sd 1 log(2) + n MaKa-2 d dllog(
cat1
S 8.
MK
(x") (X,)
20r
M xatt log( MK cail
Taking the limit as goes to 0, we have that if a ,444
then lim 1
log(2) +n 2 yagdiz 8. This implies that
M log( 20r
neD FMddKl log( MK
must necessarily hold in order for inf inf (X) (X) SUDpEC4(X)))) ML) ()) ,/ e) S 8 to hold and concludes the proof.
29

---

Published in Transactions on Machine Learning Research (09/2023)
B Proofs: Theoretical Properties of LCLS
Proof of Proposition 3.4 (Computational Complexity of LCLS).
Follows directly from the computational complexity of the linear least squares regression algorithm which is O samppe)ss)
B.1
Technical Lemmas
The proof of Theorem 3.7 relies on the following technical lemmas.
Lemma B.1
(Fundamental logarithm inequalities) For all O,
S log(x) S x
Lemma B.2 Let X' be as described in Assumption 7 I verifies Assumption 2 then f is L Lipiscchil
with respect to I|-lpp- Furthermore, for = 2, L = max,ex((lVf())ll and for p 2, Lp S max (VVx)((V(( where q is the Hölder conjugate of p.
Proof Li-Lipschitz follows directly from the fact that X' is compact and f E (X).
Vp E N, I, I x follows from the multidimensional mean-value theorem and an application of the Hölder inequality.
Consider : Va E X consider the Frechet derivative of f at x; lim ((o++)))-(o)-V/CC)))) (uh)) vh E Rd. Then, choosing h = Vf(x) for 2 and h = such (Note that this reasoning is well defined because (x) and X is an open set that contains X which implies that f(x th) is well-defined for any h E Rd and small enough t).
For = 1, we show LØ 2 max
that [f(x) c. = [V) for p = 1 gives 1 2 (
Lemma B.3 Let E (0, 1), then Vx 2 -
1
2r
log
1-
1) be arbitrary, we have Proof Let x > 2og T
2r
2r
(1
2)
log(
log(
1-
I-
Then,
2r
8
2x
- logl 1
(1
log
2
log 1-
1-
Utilising the fact that " $1+0+9 2 for all 1, we have that the above expression is greater or equal to:
2x
1
1
1
log(
log
)
2 1
log(
21
log(
1-
2
2
where last incquality follows from the fact that x > 2oo
1
30

---

Published in Transactions on Machine Learning Research (09/2023)
Lemma B.4 Consider sequence of partitions rer) used by LCLS and assume that for a given E (0, the sampling distribution satisfies Assumption
Then,
AA E HA E HI, (xx xf) 1l2 S
16
n6f N
Proof Let Amaz (M) denote the maximum eigenvalue of a matrix M if exists. E AH E Hr, we have I| (XF xf) 12 (X)" x
where mmin (Xp x denotes the smallest singular value of X XH.
Therefore, focus showing the following relation that implies the Lemma statement:
Mmin (X1 T x
> 7N 8H2
16
Let X be the design matrix without the first column of ones, ie. XI
we have
Fil
1 1
Omin (X x = min (X (x# )==
min ||
u122 = min
||
u
||u||==1
X7
0 N
min 1=l2==
u112
min | 1=
w112 o mmin (XP X
X
Therefore we can consider the smallest singular value of X instead of X which allows for a direct use of Assumption
We have
N (n.. u)?
mmin (Xj T x
Amin (X X
min ||=/==1
u XP XH
min wEEe |||a|==1
Let unin Rdd denote the eigenvector associated to Amin (XI X!1) with || 112 = 1. Then, Wiin satisfies Ei (THo 2
min
E (2H,,
x
Using "ynine we can construct orthonormal basis of {umin U2, fa of Rd (such a basis can be constructed using the Gramm-Schmitt algorithm). Then, since DJ contains nN points in each ball associated to
8 an element of an 8 cover of H, we have that there exists at least nN pairs of datapoints (I FH.)).
(en,,,n)) DH such that Has)ve(L.....)) d), as R with Jan|
of and (Nn, In,) a ununn I
84 then
This implies that max(](n, unann KMH, umin)) 2 J Indeed, if KaHH umnnn <
4
8
8
5/
HK amann )1 KEH, - TH. + & FH unnnn) K TH umnnd + (1 Uminn
2
4
4
Using this inequality n/ times we can conclude, Tmin (Xf X#) = E (TH,, 4
umii))
12
2 nN
6
Lemma B.5 Consider the constructions of Defimition 3.3
The following relationship holds for all I E N, v(X) + 1)2d
V(X)(( + 1)2d < 17 <
maxHER, (A
# minser, (d.)d
where VXX) denotes the volume of X.
31

---

Published in Transactions on Machine Learning Research (09/2023)
Proof Follows directly from the definition of {o) THERr (A/ and volume formula for the d- dimensional ball.
Lemma B.6 Let the notation and assumptions be as described in Theorem 3.1 7 x² E arggna [\=))) Then, VI N,
and define x' E X
4v 4vddn 01.
||V](>>>>>
max HER
where ny m 1 -2.0
Proof Note: such an x² exists by compactness of and the fact that f E (2))
By definition, (84.3/) (XF X T f Computing the expectation of this expression yields
E [0 / E (x -2 ]
[x x T | + B (X - T , = (X X 8/
AH E Hi, let CH E H (closure of H) be such that [Vf = max ||| V f[ which exists by compactness of H and the fact that f e (2)). Then, using the second order Taylor expansion of f around Ch: every coordinate fH, of fl can be re-expressod as
fH. = f((H) + (aH, - cH) Vf(cH) + (zH, - cH) Hess(cH THe (z (H))( cH).
(3)
where THe [0, 1] and Hess denotes the Hessian matrix of f. To alleviate notation, let l1-Ila denote a pseudo-norm norm on Rd+1 defined by; x E Rd+1, || == v d+ x if < oc and || = (2... 1) l otherwise. Then, using the definition of X#,
B [
| 11, = 1|
lla 1xxx x#) f 11
[(Cn) oJ ((CH)
(an: -H) Hess(rn,))) Ken - cH)
=I(x"" xxx-'x (x
+X
(IH, cn) Hess(rn.) cH)
)ll
[[(en)
f(CH) cH ((en))
(an, -c)) Hess(rH)) MaH cH]
0
0
+ +xX xxt) T
(xHz - cτ) (es))()H)((HH, en) )
+
[((en)
=:((m)
Plugging this expression into the theorem statement yields:
|| fl fl
max SEH,
[1L]|//111,)) [IV](("))) max [|
0 < [VVf(')|| ( {ll (f(CH) [1a) max (I & [VV HEH,
max f(e)(ll) HER,
Helfy
max HER,
(II((HT)))) max [I)(})) HER,
where the last equality follows from the fact that there exists H E H, such that x" E H. As f E (2X,K), d²g (x) < K. This implies that [[Hes([)]]] dk Vr X and by have Vi.j d), Ve E X that 1002
32

---

Published in Transactions on Machine Learning Research (09/2023)
matrix norm equivalence; |[Hes([)]lla Hel]Hess(())la & dvak, Vo R Therefore, since matrix p-norms are sub-mulliplicative;
(IH, -1) Hess(ru, Mrn cH)
| S n S - x llall
(I o2)" Hess(rHa)) (IRg - cH) ||2
where ng m 2.00)
2,00 Using Lemma B.4 we have
[(x| xf) x 12 |IX ((X)'
x 112 V Amar ((F ((/)))))))))))
x/1)-1)
VII(X X 8 N
where Amar denotes the maximum eigenvalue of (X x/1--. Furthermore, the components of the vector on the right-hand side can be upper bounded by using
and matrix-vector inequalities;
((EH, -i) Hess(rH)) cH)l = (1 - e1) (all|esss((r, (xH, cn )|(
$ (le,, ea) ||l| Hess( - = AP2 Vddk.
Combining these two upper bounds conclude:
AvddKng
A /1 64
A K
||V
max HEHI
max HENS
v 01.
Lemma B.7 If the Assumptions of Theorem 3.7 hold, then VI N, the difference between the Lipschitz estimate generated by the T.CLS method with noisy sampling fnr and the Lipschilz estimate generated by the LCLS method with noiseless sampling LJ can be upper bounded by;
maxx
maax 111
P([T.r - L, 2
5) - II (1 HEH;
(4)
ne
N#58
Proof Let I N. AH E H2 denote by 3/'1 the least squares coefficients computed using (XI, f" (instead of (X x }H),, i.e. the noiseless least squares coefficients. Then,
E B 3/1T E (X# x s
Therefore, we can write (with ng m
P ([Lr L > c) =P PP(1
-
max HERI
[1[
max HEHS
11131
|1.)
2/2
E
P
max HEH,
[3
11ob
max HEH,
{
(1 11
116
<P
max HEH,
{I
[34]
11, - 11.8/ 11
>
c
2
max HEHI
[|
[331
2
e)
T
max
{
[3]]]
-B/1122 > 2ng
HEH,
=1
max E HEHI
[3/1
3111
<
6
< 1
II
P
|E 13 - 3/112 < 2
2mg
H HEH,
=1-
II
(1-P) P
|I 13
Bf ||
))m)
HEHI
33

---

Published in Transactions on Machine Learning Research (09/2023)
In order to upper bound the term given in product: var([b]. (/")) - x/")-1 which follows from the fact that the components of of are assumed to be uncorrelated with mean 0 and variance o². We also denote by Tr(M) the trace a matrix M Rdxd Then, by applying an extension of Chebyshev's inequality finite dimensional vectors Ferentios 1982 have
- 2n,)) use the covariance matrix:
and Lemma B.4
Chebychew's Inequality S
on x
P
E
11 2
c
2m
2
2
xt)
112
Lemma
13.4
4ngo²d
16
26 n
2
2
nof
NH
n72
NHO8²
Plugging this expression into the product given above concludes the proof.
22 d -1100) 1.0) d
P([L, 1,1 2) S1-
II HEH,
n12
N 87
22
B.2 Proof of Main Theoretical Properties of LCLS
Proof of Theorem 3.7 (General Convergence Rate).
We recall that VI E N, the Lipschitz estimate L, is obtained by considering the partition H, and computing maxHeH, {|
Let be arbitrary. We need to show for p 1,2:
lim P(LL, - Lr > =) 42
and for p>> 2
lim P(IL, - Lr <) 0 with Lp E R21; 10000
Since ff verifies assumption 2 and X' convex and compact, Lemma
B.2 guarantocs the existence of xº E X
such that [|V](>")]l, 1, for p p= 1,2 and Lp == [>>](> = max [S(x))> 2 Lg for 2.
Therefore, for all p 1, we can consider the statement;
lim P(IIVf(=*)le []|>6)= 1-000
Let and consider P(IIVf(=*)1l L,}>e) > c). This expression can be split into two terms:
P(Il f(="((("))ll) -
-
< P [|[]
max #EHr
{|E
64 |1
é
IP
max HER,
{IE
1l
Lr
2
(1T)
In the following, show that both (I) and (II) converge to 0 when I goes to infinity.
(I): From Lemma B.6 || f(="))l maxmem, E
34 1l
Avddn, v
as Plugging this upper bound into
the above expression, we have
AVddngK E 2 >
P [1V
max { #ER7
3 |1+Hl
e
P
2
/i
34

---

Published in Transactions on Machine Learning Research (09/2023)
By hypothesis 2. limy- a₁ = 0 and therefore there exists 1 E sufficienlly large such that 4vddn, K and therefore PP ddn,
01, S
01 >
= 0.
(II): We show that I[( max { [| ]llo] Lr| > { converges to 0 I goes infinity. Let L denote
the Lipschitz estimate generated by LCLS with noiscless samples. Then, applying Lemma B.7 we have the following upper bound on PP() maxHeH, [[[ } L. > ;):
160 (mo22maxx(3_)
P(I max (1E|1//11g)) - E, 2 = P([L, L, ) S1 m [.13
II (1
N7HO722
HEH,
n72
NHO
MEH,
2
$ 1 7y² minHEN, (1
As by Theorem hypothesis 2 lim maxHEM; (A = 0, applying Lemma B.5 implies that lim |7,l oc. Therefore using the fact that lim by = 0, we have lim, maX (NNSTZ)
fim minnery N7 = O.
2 maxt m 7:3
To alleviate notation, let (aI)SeN be the sequence defined by == nca mingeny N7 then
lim minnen, o logarithm incqualities, obtain:
implies that 3/ e N such that VI 2 ar < 0.5. Utilising fundamental
1 1 (1-1a0 a1) Mr < [H log(
I [74
01
<
3H111
a1
1- a1
a0
2
2002 m
176
25 250 m
11
)6r
1 0.
1)2
mingeH, // N//5712
1162
Proof of Corollary 3.9 (Noiseless Oracle).
As in the proof of Theorem 3.7
we can consider the statement; p E N,
lim P(IIVS(='II, - Lrl e) =0
1
where x² arrgmaxzex (x))) Since the data samples contain no noise, L, maxHeH,
(| and
P(II 1| Ż, > F(IlVf(
Ilg
max
3 11 >).
WEH;
Then, applying Lemma B.6 and using lim 0 as in the proof of Theorem 3.7 gives the desired convergence result. (Note: that the least squares estimation well defined as N 2 d 1 and Assumption 4 holds.)
Proof of Theorem 3.10
(Finite Sample Guarantee).
We show the equivalent statement; PP((Lpp Ly| > e) S 6. where as in proof of Theorem 3.7 Lp = -VV[(*))))
with x² == argmax,ex V f (z)]lp and Lp L, for p = 1,2, Lp 2 Lu for p >
In the hypercube set-up, we have AL E N>1, 4H E H., A = vdM 8 = 1 and HH = 14 Let e > 0, 8 E
(0. }}: From the proof of Thcorem 3.7 we have that three following incqualitics need to be satisfied in order for
(1 to hold. From (I) we need 4vddn, N
in order for P(II / (x** llo maxHeR, (
|| I > ) 0.
This implics that;
8dl @PVdn, MK
35

---

Published in Transactions on Machine Learning Research (09/2023)
From (II), we have the following two inequalities that need to be satisfied;
28 gmaxt 1
(1)
< 0.5
nne minHeh, N/ 5H2 878
(2) 2 dmax
174
minwen, NT 5/r2 <
1722
The first implies that
2 m 0²
1
< min N HEHr
M
and the second expression gives
25 qmax 1.1 02
I
|Hrl
< min N HEH:
2
Since 17y] 14, I E N,1 and E (0, }), we have that if the mingen, NB satisfies (2) then (1) is true as well. Therefore, we have AH E Hl:
(). 0² 1242
min NJ.
"
5M22
NEHI
Setting Ci(d) = 8e2 - 1.00 and (2 2 maxt 11 concludes the proof.
Proof of Theorem 3.15
(Asymptotic Sample Complexity Gaussian Noise).
Consider the setting described by Theorem 3.15 with [Ci(d) MK when e >> O. As described in the proof
of Theorem 3.10: the the hypercube set-up we have VH E Hr, A JdM 8
and [Ht = ld.
For all 0, let A. denote the event that every H E H, contains number of samples N equal greater than C(d) log( MK "o²²² for a constant C(d) that depends on d (see (*) for the explicit definition of C(d) vol Bi (0)) where (ol(Br(0)) denotes the volume of the d-dimensional unit 23d+13d
and is ( of -))-evrdddd where 1)
ball. More precisely,
log( MK 2 R2
5H 8 -nvcooored). is
A = (AH E H2: NN 2 C(d)
e
Let us assume that there exists ē >> 0 such that Ve E (0,6), P(A.) > 0 (this will follow from (**) given at the end of the proof). Then,
sup biL) .f) ()) (2C=(X,K)
PLL clAc) + P(A))
sup fEC²(X,K)
Therefore, in order to show Theorem 3.15 it suffices to show that both terms of the right-hand expression given above converge to as e goes to 0. The first part of the proof considers sup)ec"(x,K) (())) elA.). We will show that for all > 0, there exists e" such that Ve E (0,E"),
sup P(Loss(zLi()) .f) dA. <8 (xC*(X,K)
Notation B.8 To alleviate notation, omit the conditional dependence A in the following computa- tions.
36

---

Published in Transactions on Machine Learning Research (09/2023)
16 Fix an arbitrary 8 > and define AH Hr. 3/ := [6/ 1 (Xl" - f/ As the noise and
the sampling distribution are independent. and every input sample is selected independently, we have
=
H
31 x = E 3 1 G
where G. denotes the set all sample inputs utilised by the LCLS algorithm... (Note that Bf a random variable as the sample inputs are randomly sampled). We have
P[Toss(x221)) {]){)) =) = P (1=s 1
<P(L -111)11(0))) 2 ;) + P ((2,0) ( 2 -)
<P
TP | |
max HEH,
[3
G7 (1
4
TP
max HEEH
{
[3 G7 11 1u157 1)
+P [ 11g
|E
3/
(
67
+ P | 11+) 4)
31
c7
11, - 4
[ = I by Lemma B.2 (for p 1, 2) and 34tr00 denotes parameters of the
where x² = aaramax,,xxx x
linear regression associated to the hypercube argmaxweH) 118* 14- By the arguments given at the beginning of Lemma B.7 we have
max {
[1 Li00
S ny max {IE HEH,
B" GY
1
HEHI
where we recall ny norm equivalence,
- Similarly, by construction of LCLS, the reverse triangle incquality and
IE
a1l L.
G7 11a - 113 11371111111
$ nn BB
G7
112 S
max ng
{
B8 G77
BF 112)
MEH,
Therefore,
P(Loss(D o) S
max |V
{|TE
[3 GX
11a)
c
HERI
4
(i)
+P (IIVF(oL110))) E
3
G
l1.
> i)
+2P
max
E
3H
G
[12) -3f1123
NEH:
4ng
(ii)
(iI)
The terms (1). (ii) in the above expression can be shown to be equal to O with similar arguments. For (i), Lemma B.6 can be utilised (as A. is assumeed to hold) to obtain:
4VddKn, AR S
4Vddnn,
fV
max [ HEH,
3
G7
11.)
max MEHI
VT
8/
01
and it follows from applying the same approach as the one used in the proof of Lemma to hold), that
B.6
(as A. is assumod
[ a|
100
G3
11g
4vddKn,
A
4Vddn, al.
/
37

---

Published in Transactions on Machine Learning Research (09/2023)
Note that 77 is defined in the omitted conditioning on A.. Then, we have by definition of I [Ci(d) MK]
4 Avddn, K
AVdd
K M
Ayad c vi Ci(d) 4'
v I
16d Vang,
where the last line follows from the fact Ci(d)
Therefore, conditional on A., we have
vn
[Vf('"))l,
max B"
{
G 11a3
c
= =P (|I7 - BB [ G7 111b
> -)
= 0.
NEHI
4
In order to show that (iii) converges to 0 as e goes to 0, we define for all H E Hr: E" == [1 Gf1
1/112 S 4n, ), consider an arbitrary ordering of H2 = (Hi.... Hiiht and apply similar arguments as the ones utilised in the proof of Lemma B.7 to obtain
P
max HEHt
E
3/ G7
112) > 4ng
=1 -PP(YH
|A.
Hi, E Ac)
Hil
= 1 =1 (F.")
A.))
II P ( Ac; F.", ....9 F!)
The computation of the local linear regressions parameters is done independently with no data overlap im- plying that the conditioning expression: {E" ".., E...1) (for i = 1.... (Hrl) can only impact the probability by affecting the number of samples contained in H₃: N/ which are utilised in the local linear regression. As the probabilities are also each conditioned on A. which provides a fixed lower bound on N for all H E Hr and the remaining arguments for this part of the proof will only utilisc this fact, we use slight abuse of notation in order to alleviate notation and omit the dependencies on {EH: g.... EHI-1} (for i II,.. (H])) in the remainder of this part of the proof. Therefore, we can consider
1- II (1-P HERI
(137 P013 - -10 10..3TT 2
E Ang (114))
In order to upper bound P(I133 - (6), 3/ 212 > an. (A)) more refined bound than the general Cheby- shev inequality used in the proof of Lemma B.7 is utilised. Irstead, we apply Corollary 3 of (Pinelis and Sakhanenko (1986)) to obtain an alternative bound (see (iv) below).
Remarking that 0 <<< (d))M implies 1 = C1 (d) MK S V222 (d) all E (0,
MK e
we set ē == C(( Then, for
3
P |13 - 16,.311 3 2
c (1.) = (I(X7" T x "1
c 2112 Angg
(1)
4mg
( 12
(iv)
2e "MIia xx 1.4
As the Gaussian vector (XF" T tower rule to observe that
x 7t has covariance matrix o T
x#)-1, we can utilise the
E
[[
x#
* A.] E [ x - X
# H
G A.]
x | s x| x/> A x
16do2
= E
n88 Ni
38

---

Published in Transactions on Machine Learning Research (09/2023)
where Ny := C(d) log( MK jor R²
is given by A. (with ((d) explicitly determined below). The last inequality follows from Lemma B.4 which can be applied by definition of A.. This implics:
3 R
P |1 - 104 1/ 2 4 Ao
I
2 ng
2e
2 nngr
S 2e
2
Therefore, denoting C2(d) = C and plugging the above expression into the initial upper bound, obtain
P (Loss((zh10), > c(Ar) 22- II (1- 2e Ca(d) 22n2 =2 - 2(1 22 C2(d) (2xa) y1Hrl,
НEHI
Then, setting 2 2-2(1 - 2e C2(() = | < 8, we obtain that if
R²k²
2
N1 2 Cd)
log(
18x
then ((Los)(z410),1) c(Ac) S ö. As HH is monotonically increasing and converges to infinity as goes to 0, there exists 62 > 0 such that Ve E (0, [Hi] 2 2oog( [-z). This implies that can apply Lemma
B3 to obtain:
2
4/Hr
log
Therefore, we have that the following stronger condition on Ny implies (r >
e) S
O²K² log(
K²K²
log( 4
Ni 2
Ny 2 Cd)d
1- 12
log( 1-
We can rewrite this lower bound with [H,r] expressed in terms of e:
K2
4|Hs
R²k²
C MK d log(
log(
Ca(d)e
log(
C2(d)
1-
0² K2
d log (og((C(())) log( 8 -- MK
Cz(d)e
where Ca(d) (d). Finally, there exists ε3 > 0 such that Ve (0, 73),
C2(d)
MK
log(
which implies
Ñ1 2 Cr (d) 020K0'22 log(
MK (((oss(z//t)),)) ,)) 58
where C (d) Tt(d] C(d) = C (d) (+).
2d
Therefore, as C (d) only depends d (note that n depends only on d) we set
Selecting min(11, (2, (3), we have Vc E (0.7)
P(Loss(zhil)) ff elA.) < 8.
sup (x))(X,
As the choice of 8 > 0 was arbitrary, this concludes the first part of the proof.
39

---

Published in Transactions on Machine Learning Research (09/2023)
(*x) We now show lim P(AA) 0 with C* defined above in (+). e (0, (i(d)MK) be arbitrary and define the following events:
log( MK
jo²
A
HA E EHr : 2 (d)
c
A HA H, H is -)-eovered)
8
We recall:
log( MK )o² K2
A H is -n)ooooddddd } {At A A
84
A
HA H, NØ 2 (d)
c
ct
8
We can write:
P(49) -1 = -1 P(
which is well defined as we will show that IP(A)) > 0 for sufficiently small Therefore, can show that
lim 4)) = lim PP()) =1
c-0+
c-0+
then the proof of (+*) is concluded.
(I) We begin by showing lim,-oo IP(A.) = 1. For all E Hz, we define
cH (n) = H contains 2 (d) log( MK k2 for total sample points equal to n
where denotes the total number of samples which was assumed to satisfy: > d log ( for fixed constant C > 0 (defined explicitly below). Then, considering arbitrary ordering of Hi = (HI.... H Hi we have
cdtt
[Hd
P(A.) = P (AH E E (m))
II
P (n)
(n))
As the inputs are sampled independently and the elements of Hy are disjointed by construction, we have Vi E (
(n) gl (n), (n)) = (EM (1))) log( MK )0 1
Jo²K3
1)C
It trivial to see that ViE E {l,..., H.I, PI (n)) is increasing in n. Thus, we have
[Hil
( (H log( MK )o² )o)) _
P(A))
II
For é > 0 satisfying e < (d) we have T (d) Therefore, using H7 = fd < (4)
we
have
(3) MK 0² (2 C (d) log( MK
2 K2
|7
ed
= ((CC( Md log( MK
(2C((d))C'(L)
ed+4
C
40

---

Published in Transactions on Machine Learning Research (09/2023)
k212 where the last inequality follows from the theorem assumption: n 2 - k logt MK) C := 2(22( (d)) (d), setting C 2 Ci, and utilising the upper bound derived above, obtain
Therefore, defining
cats
[Ht
log( MK Jo²K3 II P e (n- (7,//(
[Hrr]
II P 1 (n- 2))
(
II P E. ())
e4
We now consider for all H E H4 the computation of P(EE (2)) for which we will derive a lower bound.
For all E Hi, denote M (n) = Hi E (0....n 22 E H)l the random variable 19 that counts the number of sample inputs H. As every sample imput is sampled uniformly on X' and for all H Hr vol(H) = ( 2 (2C)())Ka we have that the probability of a sample imput being in H E H, can be eat(ff) modelled using Bernouilli random variable with success probability p cal(X) 2 (2C)(d)Mk)e Therefore, (n) can be modelled as a sum of independent Bernoulli variables with success probability From Lemma 1 of [Stone )1822), we have
BLM
2.
P(M) S
S
2
In order apply this result, we observe that as C C 2 (by construction), the following relations hold:
E 2 -1
o² log( MK
C
2 (d)
log( MK) o²²K²
MK
el
(id)d2u4T
where the rightmost term corresponds to the bound stated in the definition of the E.d (²) events. This implics that E (b) can be lower bounded as follows:
P cl ))== HPMM/ n
( 2 (d)
=P
MM
log( MK
) R22
et
-
( m S (d)
log( MK x2
21-P MM M
B[M
2
2 KIM
Plugging this expression into the initial bound, we obtain:
[7
2 RIM M 4
II
H
As B[M*(()) R log( MK
2a and |H d (i.e. both terms increase polynomially with respect
to 2), the above expression be shown to go to 1 goes to O. This implics that if C 2 Cz, then
lim P(A.) = 1.
(II) We now show that lime-o+ (P(A))AA) 1. By the law of total probability, we can derive:
(P(A(A)))
Σ
P P(ANI)/)) P (LNH)HeR) = (N/) HHHHHlA)
(N EVC
H P(H is ( (.veerdddd P ((N/)THEM = (!
Σ II WEH,
(N (V)(n)
19 essence, Mf((n) (m) = N/ hut makes explicit the dependency on n.
41

---

Published in Transactions on Machine Learning Research (09/2023)
where V2(n): == ([N]") HHN,, E Ngat : Enema NY n with c(e) == (d) log o k²
defined as the
bound stated in A!- The second equality follows from the definition of 68 8 n))covered and the disjointness
of the partition. Note that (i(n) non-emply, i.e. n 2 c(e)]Hzl, due to the inequality: C Ci set in (I).
For an arbitrary (Nf) NEH, (n), we now focus on lower bounding IHER, P(H is ( -n)-creeedd |N#).
In order to do so, for each H E Hr we define cf:: the minimal cover of H with balls of radius of with respect to Il- and the associated set of hyperbalis: B,"
Let I N, H E Hi be arbitrary, without loss of generality, can assume that Cf < H as H is hypercube. This implies that for all B By vol(B n H) 2 2 BB) 2 (B (
where vol B1 (0)) corresponds to the volume of the unit ball and is constan 20 that depends on d. Utllising {B HeHH we construct the set B as follows
BF = BBf C CH: BB E BJ such that B H B
We have UnEgy B H, |87| |c and for all B BH, vol(B) 2 vol (0)) 16) ). Furthermore, by Theorem 14.2 of Wu (017
we have
2 87
8fdd vol B1 (0))
23dzd
18 -cf1 S
(BI
Clearly, if each set in By contains v/ sample inputs, then H is ( coveere.
8
For all B E BH, we define the event:
BB (N) = (B" contains 2 nN inputs if N samples are in H.J.
Then, we can apply the same arguments the ones given in (I) to obtain:
P H is
( g
841
[) 2 P yBB E 8" gRd (NP)) > II P (ER" (N - 118"IN77
B"EB"
II
BBB" (
2dd
= II
8B" 1 (
BREBH
B EB
Following the same approach as in (I): we consider the random variables M MB" (N) l(i [I,...,N N) : I, B }1 where H, are samples
where the last equality follows from the fact that by assumption, 1) = voll B: (0)) 25
that are selected uniformly on H. For all R" T" nd (N) can be modelled as the sum of independent
Bernouilli variables with success probability; p vol(H)
BB "
Bo (0)) D of
val (0)) and satisfying
64"
16a
MB"
N
NH
2 p 2 No vol ( (0)
E
24d+1
Using this inequality, we observe:
vol (B
NW & N vol (B)
E BBMB" NH (2 )}
N
23d+13d
24d-1
Therefore, leveraging the same arguments as the ones utilised in (I), apply Lemma 1 of Stone (9822 to obtain:
IP B
NH
2
wot (0)
2
24442
2n fact, a closed form for vol(B.()) (0)) is known, vol (B.(B))
2
r +1)
42

---

Published in Transactions on Machine Learning Research (09/2023)
By construction, we have that for all <> 0 and I= I(e( N, (N/" THEN, E (i( which implies that for all H E Hi, Nf 2 c(e). Combining this bound with the lower bound derived above, we obtain for all H E Hr:
P(H is
II
P
EBS
(NH)) 2
II B EB"
2 2)
wolt 24 (0)
20042
B" B"EB"
18"
(1-(2)
1
(200
(
2 ((()
volli (o))
240
1-
(
2 o(e)
voll (O)
24d
As the lower bound derived above does not depend on {NT' Vi(n),, we plug it into the initial expression to obtain
8f
Σ
II P(H is -))oeerrdd) P(IN/) = (N/ (NHHH)))
(RH) (Vi(a)
HEHH
Bdgg catc
II HERr
2 E(c)
wal (0))
243
Σ
P((N))eR (Nff)ee
Iee Att
(E
23dzd vollB (0))
( B
II (1-2)
a(e)
noll (o (0))
1 2
unlf (0)) ((e)
2l142
20042
HEW,
MK where the last inequality follows from: for all satisfying e < Ci(d)M,, we have S (C) MK implying [Hr] = 1d < (2C) It is relatively straightforward to see that the lower bound derived above
ed
converges to 1 as goes to 0. Therefore:
12 lim P(A[IA))
2
lim 1 -0
2 c(e)
woll By (0)) 26d42
Bal(B (e))ee
1.
This shows:
lim P(4))= lim (t)
lim -1
+
--0 -+
and concludes the proof of Theorem 3.15
Proof of Corollary 3.16 (Finite Sample Guarantee - Gaussian Noise).
The assumptions of Corollary 3.16 imply that the event A, defined in the proof of Theorem 3.15
holds with
constants specified in the statement of the corollary: E E (0, and (i 164 max 4.03
vi
Therefore, the same arguments the ones used in the first part of the proof of Theorem 3. in order to obtain Ve E (0, C.ddMK)
15
can be applied
3
sup P(LL(()) 42(0) SP (2))
SP
max HEH,
E
aH G7
331122
112
4rg
where we note that as we consider P(L,()) L;(f) > c) instead of (P(Los(( > c), factor 2 disappears.
This implies that we can consider the statement Vo E (0, 1):
_ ) 58 ))=0
P max [ 3 G7
34 [1a)
NIH,
4m
43

---

Published in Transactions on Machine Learning Research (09/2023)
in order to show Corollary 3.16
( Let c (0, 3. ) and 8 (0, be arbitrary. Again applying the arguments of Theorem 3.15 with 6,
obtain that the above expression holds if S := min((1, 62, Es) where é1, 62, 0 depend on d and E.
We consider each of the epsilon separately:
(e1). By construction, é1 Ci(a) and by assumption: e (0, G Therefore, < é1 holds.
(e2). 62 is set such that the relation: [Hr] 2 2 2lo((=-3) holds (in order to apply Lemma B.3 Substituting Hyl = 7d and S 2 into the expression yields:
Hz 2 2 log( T-8) = 1dt log((2).
As E (0,
M and defined to be I = [Ci(d) MK 2 and the above holds. Therefore, c < 62
3
holds.
(e3). eg is defined such that the following relation holds:
o²K²
log( 4 log( 1-8)
HH E Hi, N 2 C2(d)e
where N/ is guaranteed number of samples in H E Hr By the assumptions of Corollary 3.16 we have N/ for all H E Hi. By construction, (d) 24
Ön Cn1 d) k² log( a
Ca(dy Therefore:
log( 2
O²K²
4 |Hll
do K2
451
NH 2
log(
NA 2 C2(d)c
log(
(2)
log(
log( 1
holds by design for all (0, G Therefore, c3 holds.
Thus, we have shown: Ve E (0, G((dMK E ())
P((T.1() -1,(()));((1) S. (EC2(X,K)
sup
C
Proofs: Sample Complexity of Adaptive Lipschitz Optimisation
In this section we prove the lower bound on the sample complexity of certified adaptive Lipschitz optimisation algorithms given Section 4
Proof of Proposition 4.1 (Sample Complexity of Adaptive Lipschitz Optimisation).
Fix 0, L 2 0 and let A be non-adaptive certified optimisation algorithm which takes given Lipschitz constant L> > L a hyperparameter.. Using the notation given in Section 4 with n-queries to the oracle, A outputs a triplet ((zn: (x;,,, (n))eEN where In is the n-th query point, f(x;) is the generated estimate of max fx) after n queries and C. 2 is an error certificate that guarantees: maxzex f(x) f(x)) & Go- From Theorem
Bachoc et al. (2021) with 6o 2d (this follows from the fact that X is a hypercube), we have that for all f E (h= : + lh is Lipschitz cont. and 15(1) < LJ:
CaL d1 1a)dd ((A.f.)) 1 1og (22)
S (f(x*)--f() f(x) + e)d
dr
(5)
where ca 0 (It is important to note that the term =d is not optimised (Bachoc et al. (202)) and could be improved in future work). Now, consider adaptive Lipschitz optimisation algorithm with
44

---

Published in Transactions on Machine Learning Research (09/2023)
separable Lipschitz constant estimator (f(.) If (ff) can be guaranteed to be feasible (e.g. see discussion
after Corollary 3.13) then equation (5) holds for A and Vʃ E C K) Fp(T") with I. replaced by (J)
The precision at which (f) estimates L*()) therefore directly impacts the lower bound on N A, f.).. 21
From the Corollary 2.3 given in Scction 2 we have that An E N, any Lipschitz learning algorithm L E Cn.p
that guaranlees leasible Lipschitz constants must satisly
MK
L()- - C
sup [EC*(XXK)FF
V/
for some C> > O. This implies that for all A E A, there exists a non-empty set GA C ()
such that v GA, La(f*) L C MK Vn
Then, denoting I(f) == 1+ caL'd
Ix (()+)) in order
de
to alleviate notation, we have AA A,
) (
Ie LA(f)
e(A,e) :
sup (EC
N(A,fee) (ECMXXKK)F,
sup
{(1-
L
{T())-
L C
MK
sup
SECA
VN(AAC)
Re-arranging the terms in the above expression, obtain:
C MK sup (VI() S (L((((())) + MK (A,e))
C
SE9A
which can be solved to give the lower bound
MK (V (1++ sup {VI()) -1 (N(A,)) 20 C1 L.
MK
where Ci > 0 is a constant. In order to conclude the proof, lower bound sup { (/T(f} is needed. To do so, we note that I(f) is minimised when f is constant. We therefore consider the set of functions Fo defined
in the proof of Theorem 2.2 From the proof of Theorem 2.2 we have that if (NA, c) I
MK
)d( (()))) then
D (L')
L S Cg MK which implies Fol (1=)²² 0.8 (2)
C 9Λ- Using f(x))
(L')² u.sK Af E Fo
0.8K 7.75 (x))).
0.8
2 (A,e)
0.8K 7.75
obtain the lower bound:
caLad
Vx
(I() 2
JEGA
sup
1+
logz( (4)
(c
(L')²
0.8K )d
Therefore, if N(A,c) S We obtain
MK d Ca ( the above expression can be plugged into the lower bound on c/N(A,c).
L
MK 1 Cs
VN((A6) C1
1)
L-
(1 + [logz
(2)) ck +
(for some constant C3 > 0) which corresponds to the first half of the lower bound stated in the Proposition 4.1 In order to derive the second part the expression, we consider the case where N(A,c) > (MK yd (C:)d
this case, an alternative lower bound on supsega {I(f) needs to be derived. In order to do so, we consider the following class of functions,
(g: X Rd + RRVa E X,
C2 MK 2 (/((A))
)a where E
(L')² 0.8
K
});
0.8K
7.75
which belongs to GA by construction. However, as obtaining a tight lower bound on sup { [V(()) is technically infeasible for this class, we simplify the problem by removing the functional input from
21 Note: this only possible as are considering adaptive Lipachita optimization algorithms which are separable.
45

---

Published in Transactions on Machine Learning Research (09/2023)
Fo Fo 0.8k 7.75
0.8 / )²) and considering the simple linear function f X c
IR R. (x) L' which
belongs trivially to GA. In this case, we can compute the lower-bound
(LM 1)d ca(d 1) L g sup {I()) 2 cd (1 + [log( (2)) d (d 11 ( + 1)d-1
I L=d+1 M
SE9A
2
(1 + [log2( ( jed_
where the last incquality follows from the fact that LM 2 since (0) Plugging this expression into the lower bound on (A((,e), we obtain
MK L '
L L' 1)c eK
CN((Ac)) 2 C1
+ Ca
V M + [[gg((2)]]
1)
(for constant C4 0) which corresponds to the second half of the lower bounding expression. Note: in the statement of the proposition we simply set C2 min(C3, C4) as the used constant.
46


Reviews:
[{"review_id": "s1jvxjlCtv", "reviewer": "Reviewer_orNs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths ### \n\nThe paper studies a very well-motivated problem, provides lower bounds that were previously unknown. \n\nIn my opinion, while the upper bound can be thought of as \"natural\" (the intuition being that a grid search over the $d$-dimensional space for an $\\epsilon$-accurate estimate would naturally require $O{(1/\\epsilon)}^d$ samples), the fact that this is also the lower bound is quite interesting. \n\nThese lower bounds are studied in the noisy setting too, which was one of the justifications to study this problem in the first place. \n\nI also found the paper to be written in a very clear and engaging style. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### Motivation ### \n\nThe precise estimation of the Lipschitz constant is an important subroutine with applications in multiple problem domains, e.g., continuous optimization, where this constant is often assumed to be known to set step sizes. Prior work on this (rather fundamental) task typically makes assumptions about the setup, such as knowledge of the problem structure and the oracle access to the function being completely noise-free. Further, the majority of algorithms for this task lacked associated theoretical guarantees of correctness and sample complexity. \n\n\n### Contributions ### \n\nThis paper's contributions are multi-fold: First, it provides lower bounds for the task of Lipschitz estimation under both noise-free and noisy zeroth-order oracle access. These bounds are also agnostic to the structure of the function in question. Second, the paper gives an estimation algorithm, which in the noise-free setting, matches the lower bound given by the paper, thereby establishing its optimality. Finally, the paper provides experimental evidence outperforming (in terms of runtime) the classical Strongin estimation algorithm in many common settings. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would be happy to accept the work as it is: a small typo that can be corrected is on page 3, the definition of Lipschitz function has the inequality flipped. ", "broader_impact_concerns": "N/A ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BSDBytele6", "reviewer": "Reviewer_cH4u", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and easily comprehensible.\n\n2. The proposed algorithm achieves optimal sample complexity in the noiseless case and provides a near-optimal guarantee in the presence of noise.\n\n3. Compared to non-Strongin based estimators, the proposed algorithm exhibits linear time complexity with respect to the sample size, making it significantly more efficient than the baselines.\n\n4. The experimental results validate the efficiency of the proposed algorithms.\n\nWeaknesses:\n\n1. Assumption 2 requires prior knowledge of a tight upper bound on the second-order partial derivatives, which may be considered unreasonable. When dealing with an unknown target function, obtaining the upper bound on the second-order partial derivatives is no easier than estimating the Lipschitz constant itself.\n\n2. Although the proposed algorithm achieves a near-optimal guarantee, the sample complexity still exponentially depends on the dimensionality $d$, which is not acceptable. In this scenario, both the LCLS algorithm and non-Strongin based estimators exhibit exponential running times. It becomes meaningless to compare time complexities when both are unacceptable. A more desirable outcome would be a polynomial sample complexity with stricter assumptions.\n\n3. Assumption 4 raises the question of why the significantly corrupted noise ($Q(\\delta)$) does not depend on the sample size $n$. For zero-mean noise, the average corruption typically scales as $1/\\sqrt{n}$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This study focuses on the problem of estimating the Lipschitz constant, given prior knowledge of a tight upper bound on the second-order partial derivatives. The author introduces novel algorithms known as LCLS (Lipschitz Constant Estimation by Least Squares Regression) and establishes a finite sample complexity guarantee for both noiseless and noisy scenarios. Additionally, the author proposes a theoretical lower bound for the sample complexity, demonstrating that the LCLS algorithm achieves optimal (or near-optimal) sample complexity in the absence (or presence) of noise. Lastly, the author applies the LCLS algorithm within an existing framework based on Lipschitz constants.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In Assumption 4(1), it seems more appropriate to state that the probability is related to $\\delta$. Perhaps it should be modified to \"probability $P \\leq \\delta,\" which would clarify the intended meaning.\n\n2. In the experiments, the chosen dimension $d$ is relatively small ($d=3$). As previously mentioned in Weakness 2, both the LCLS algorithm and non-Strongin based estimators exhibit exponential running times with respect to the dimension $d$. To obtain a more comprehensive understanding of the time complexity, it would be beneficial to test the algorithm's performance with larger dimension sizes.", "broader_impact_concerns": "There is no concern about the broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NsvWLOkGvq", "reviewer": "Reviewer_79hU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like this paper. I think it easily merits being accepted to the journal.\n\nThe paper studies an interesting problem in a largely compelling way. The story of the paper is nice -- that lower bounds for lipschitz learning haven't been proven in the past, and the authors can show the existence algorithms with essentially optimal sample complexity and can even present an algorithm with faster runtime than existing work. Further, the newly proposed algorithm has a fundamentally different structure from the Lipschitz learning algorithms they mention from the prior work (I'm no expert in Lipschitz learning, so I'm supposing that the authors cited all the relevant prior work). The algorithm presented is flexible, allowing for a high sample complexity that achieves the rigorous worst-case bound, while also providing flexibility for more reasonable implementations in practice (i.e. by using fewer partitions or fewer samples per partition).\n\nThe paper is also well written. The authors spend a good deal of time and effort explaining and interpreting their results. The writing is clear and easy to follow. I've got some minor confusions or edits which I'll list in the \"Requested Changes\" section, but nothing severe.\n\nAt a high level, it's hard to say more than that -- a well motivated problem given new upper and lower bounds, involving a new algorithm with a faster runtime while maintaining near-optimal sample complexity, all bundled up in a well written paper.\n\nThat said, I do have one particular gripe involving the proof of the lower bound of the sample complexity in the noisy oracle setting. The proof of the noisy oracle sample complexity lower bound requires a technical assumption on the noise being \"noisy enough\", but the statement tracks as a bit too general to me to be possible, but also shouldn't be necessary. The assumption is \"Assumption 4\" on the top of page 6. Roughly speaking, the assumption says the following:\n> There exists a ball $\\mathcal{B}$ of small radius in the hypercube $[0,M]^d$ and a threshold $Q>0$ such that: for all oracle noise distributions $\\mathcal{D}$ with zero-mean and variance $\\sigma^2$, and for all Lipschitz learning algorithms $\\mathcal{Alg}$, we know that at least one of the two following statements hold:\n> 1. All the queries made by $\\mathcal{Alg}$ in the ball $\\mathcal{B}$ are sufficiently perturbed (as measured by $Q$) with probability 1; or\n> 2. There exists an $L$-Lipschitz function $f$ such that, conditioned on the event that the queries made by $\\mathcal{Alg}$ in the ball $\\mathcal{B}$ are sufficiently perturbed (as measured by $Q$), the probability that $\\mathcal{Alg}$ returns an estimate $\\hat L$ within additive error $\\varepsilon$ of $L$ is at most constant (i.e. and not arbitrarily close to 1).\n\nThis assumption is very technical, and is maybe plausible? The fact that this technical dichotomy has to hold for all noise distributions with zero mean and bounded variance is a very strong claim. It feels plausible that there exists pedantic noise distributions that violate this assumption though (for instance, if $\\cD$ takes value zero with overwheliming probability, but is very large with very low probability). The paper does claim that this technical assumption is written this way to allow for more generality in their lower bounds. However, it's hard to approach and is plausibly wrong. The second bullet point is especially harsh -- saying that every Lipschitz-learning algorithm has a function which is hard to $\\varepsilon$-learn in the ball $\\mathcal{B}$ with bounded noise.\n\nI have two inclinations about this assumption:\n1. It's not clear the assumption needs to hold _for all_ zero-mean bounded-variance noise distributions. Most lower bounds just pick a single noise distribution and show a lower bound that's tight for that choice of additive noise.\n1. It would really help to give a concrete example (with formal proof) of a natural setting where this assumption holds. I don't see how to prove the second bullet point rigorously, and that feels like a vital part of the broader lower bound claim.\n\nThis is a bit of a sticking point to me, since it does feel a bit like moving the goalpost of what the authors need to prove a lower bound against. The reason I'm sorta okay overall though is that this is a sticking point for merely part of their contributions. For instance, the lower bound against noiseless oracles has no such annoying assumption.\n\nAgain, overall, I like the result a lot, and recommend accepting it. It just has this one assumption that really gets me. Oh, also, there's a nice and thorough experiments section!", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem where we have (potentially noisy) oracle access to a function $f : \\mathcal{X} \\rightarrow \\mathbb{R}$ (where $X \\subset \\mathbb{R}^d$) and we want to learn the Lipschitz constant for $f$ to additive error $\\varepsilon$. We are guaranteed that all second order partial derivatives exist and are bounded as $|\\frac{\\partial^2 f}{\\partial x_i \\partial x_j}| \\leq K$. Upper and lower bounds on the oracle complexity of this problem are studied.\n\n**Lower bounds**: Two different setting are considered for building lower bounds. One setting is the noiseless oracle, where we can exactly compute $f(x)$ for any $x\\in\\mathcal{X}$. When $\\mathcal{X} = [0,M]^d$, i.e. when the domain of $f$ is the hypercube with side length $M$, the authors show a lower bound of roughly $n \\geq (\\frac{MK}{\\varepsilon})^d$. In the noisy oracle setting, where the output of the oracle is perturbed by iid zero-mean bounded-variance noise, the authors show a lower bound of roughly $n \\geq (\\frac{MK}{\\varepsilon})^{2d}$ under a pretty opaque \"Assumption 4\" (discussed in more detail later in this review).\n\n**Upper Bounds**: An algorithm called LCLS is proposed. The algorithm works by partitioning the input space $\\mathcal{X}$ into a very large number of partitions, sampling points within each partition, solving a least squares problem in each partition using the responses from the oracle to compute a local Lipschitz constant, and returning the largest Lipschitz constant computed amongst all the partitions. \n\nThe authors prove this algorithm matches the lower bound in the noiseless case, and nearly matches the lower bound in the noisy case. While the state-of-the-art algorithms have runtime scale quadratically in the number of points sampled, LCLS has a linear runtime. So, while existing algorithms achieve sample complexities similar to LCLS, the necessary number of samples is very large ($n = \\Omega( (\\frac{MK}{\\varepsilon})^d )$), so this improvement in the runtime while maintaining optimal sample complexity is the key contribution for the upper bound.\n\nExperiments are provided to explore the empirical performance of LCLS.\n\nThe above results were stated for the Lipschitz constant with respect to the $p=2$ norm. For the $p=1$ norm Lipschitz constant, similar results are presented.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I'll list a combination of requested changes, typos, and just questions I have. They'll be ordered based on where in the paper the questions occur.\n\n1. [Page 3, second bullet point under \"2.\"] You stated \"without any prior knowledge...\" as a valuable upside, but you haven't really given a concrete example of what that means. What sorta prior knowledge does Strongin require?\n1. [Page 3, last sentence of bullet point \"4.\"] I don't understand what you mean by the last sentence. \"specifically designed\" for what?\n1. [Page 4, second line] Add \"any\" before \"$L \\geq 0$\"\n1. [Page 5, after \"In this paper\"] Make the exponent of $d$ into $d^{\\frac1p - \\frac12}$. Since you only consider $p\\in\\\\{1,2\\\\}$, it's just cleaner this way.\n1. [Page 6, last line of Theorem 2.5] Again simplify the exponent. Also, $Q^*$ isn't defined. It seems to be only defined in the proof, but also it's defined in a way that depends on the noise distribution and the location of the ball? Makes me think that maybe it's more of a change to Assumption 4? Not sure how you'd rather clarify that.\n1. [Page 6, Remark 2.6] Could you explain what would change quantitatively if the noise was (e.g.) subgaussian? Would the dependence on $\\delta$ become logarithmic while everything else stays the same, or would it be more drastic with the exponent of $2d$ returning to be $d$?\n1. [Page 8, Figure 1] Add $I\\in\\mathbb{N}$ subscript to $\\\\{\\hat L_I\\\\}$\n1. [Page 8, Defn 3.2] Make \"we define\" into the start of a new sentence.\n1. [Page 8, Prop 3.3] Add $d^2$ into the big-Oh runtime of LCLS. It's personal preference I guess, but it strikes me as odd to not mention the impact of $d$ here in the runtime.\n1. [Page 9, second line] Add the dimension dependence to Strongin's big-Oh as well.\n1. [Page 9, Defn 3.5] Define $D_I^H$\n1. [Page 9, Defn 3.5] This requirement of containing a multitude of many disjoint covers isn't very intuitive, but it sorta is? I'd add a few lines explaining this requirement, and the usual scale of both $N_I^H$ and $\\eta$.\n1. [Page 9, fist line after Assumption 5] Say \"used\" not \"necessary\". Necessary is a technically stronger claim, and I don't think you show it to be necessary. It's merely sufficient, afaik.\n1. [Page 9, footnote 6] Don't use the appendix to define notation used in the body of the paper. I've no issue with the appendix summarizing all the notation that appears in the body, and introducing new notation unique to the appendix, but it shouldn't be defining things for the body.\n1. [Page 10, Remark 3.7] I overall really like this remark btw! It's really nice to have this sorta explanation! But the second bullet point a bit unintuitive still here. It's worth writing in the remark that the second bullet point is really only for the noisy setting, and even then it's still worth explaining why the number of samples taken within partition $H$ should depend on the number of partitions. That feels rather unintuitive to me.\n1. [Page 10, Corol 3.8] Drop the $\\forall D_{\\gamma}^n$ bit -- this is the noiseless setting.\n1. [Page 11, Definition of $N(I)$] The curly brackets don't make use of the symbol $n$. Maybe make it intro $\\min \\\\{|D\\_I^H| ~ : ~ D\\_I^H \\text{contains a ...} \\\\}$?\n1. [Page 12, before Section 3.4] At this point of reading, I felt unclear if we had any good reason to assume we know a good value for $K$. If we don't know the Lipschitz constant, how can we know a good bound on the second derivative, especially when the empirical performance of LCLS does seem to depend on our knowledge of $K$?\n1. [Page 12, Section 3.4.1] Add more confidence intervals to these plots. It's a randomized algorithm, so I should be able to see those standard deviations, or maybe the 25th and 75th quartiles, on these plots.\n1. [Page 12, Section 3.4.1] Optimization is misspelled, using \"s\" instead of \"z\"\n1. [Page 13, Figure 2] The middle column should probably still use a log x-axis to legibility? Not suer sure why you have both the first and second columns, frankly.\n1. [Page 13, Table 1] Point out somewhere (maybe in the table? maybe not in the table? not sure) that functions (a) and (d) are based on the lower bound construction\n1. [Page 14, Figure 3] Use more points on the x-axis. There's waaaay too few, especially for the right two columns.\n1. [Page 14, Figure 3] Consider interpreting somewhere why the computation time is only sometimes different for the two Strongins. It's not your algorithm, so it's not a big deal, but it's confusing to see.\n1. [Page 14, Figure 3] LCLS completely violates the lower bound which it should be tracking on function (b). Interpret what went wrong. Also, this baaadly needs confidence intervals, the error plot for function (b) looks nonsensical.\n1. [Page 15, Figure 4] I think the green and blue labels should be M-Stron instead of LACKI\n1. [Page 16, sentence starting with \"In some sense\"] In what sense is this true? Does this really feel like necessary cost? I don't see the idea of this being \"necessary\" for any algorithm family other than LCLS. It's necessary for LCLS, sure, but the sentence feels like it's talking about what's necessary for any algorithm to achieve linear-in-$n$ runtime.\n1. [Page 16, sentence starting with \"The last illustration\"] Add commas around \", provided in Figure 5,\"\n1. [Page 16, same paragraph as above] Still feels like you should include the algorithms of Beliakov and Calliess in those plots though. Might be worth using those algorithms in practice for the time being if they way outperform LCLS.\n1. [Page 18, Prop 4.1] There's an extra parenthesis\n1. [Page 18, Prop 4.1] If you can find a way to format it visually nicely, put the sup before the big equation\n1. [Page 18, Prop 4.1] $\\gamma$ and $\\beta$ have the exact same words in their definitions.\n1. [Page 19, Figure 6] Caption says \"red\" instead of \"orange\"\n1. [Page 19, Last paragraph] \"performs\" should be \"perform\"\n1. [Page 22, Lemma C.1] I think the $z_i$ should all be remove from $g_0$?\n1. [Page 24, paragraph starting with \"For any $L^*$\"] How do you know that $\\max\\_{x \\in \\mathbb{R}^d} \\|\\| \\nabla g\\_z^{L^*} \\|\\|_2 = L^*+  \\max\\_{x \\in \\mathbb{R}^d} \\|\\| \\nabla g\\_z^{0} \\|\\|_2$. I believe it as a triangle inequality, but equality needs a bit more justification.\n1. [Page 24, paragraph starting with \"In this proof,\"] What is $A$? Is it supposed to be $M$?\n1. [Page 24, Bullet point 3] Double dipping on the symbol $i$. Let it be either $i,j\\in[d]$ or let it be the entry of $\\bar z\\_i$, but not both.\n1. [Page 24, paragraph starting with \"Since every\"] Should be \"analytic\" not \"analytical\"\n1. [Page 24, paragraph starting with \"Since every\"] This paragraph feels like an intuition paragraph, and isn't super rigorous. If that's right, then say so upfront at the start of the paragraph.\n1. [Page 24, paragraph starting with \"Since every\"] What is $A$? Is it supposed to be $M$?\n1. [Page 25, paragraph starting with \"As noted in\"] This is not nearly formal enough. Add rigor here, since this feels important. Why couldn't an algorithm information-theoretically just output the common Lipschitz constant that all of these function have? Add some sorta formal argument about picking one of these functions uniformly at random, except picking the zero function with sufficiently high probability that any accurate algorithm has to account for it, and continue as such.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles an important problem and produces a strong set of theoretical results.  Various reviewer comments were made about the assumptions, curse of dimensionality, and writing, but the reviewers were ultimately satisfied with the responses and unanimously agreed that this is a strong paper, particularly due to achieving minimax optimality in various cases of interest.

In addition, two reviewers indicated 'Clear Accept' and one of those two indicated 'Possibly Featured Certification but unsure due to somewhat limited scope'.  I judge that the scope is not a major limitation (i.e., it seems to be roughly at the level one would expect for a paper of this nature), so in view of the unanimous positive comments, I believe that this paper can be considered for Featured Certification.

I will enter 'Accept with minor revision' in order to encourage the authors to revisit the detailed reviewer comments and make any final edits.
Decision: Accept (poster)