Stochastic Sample Approximations of (Local) Moduli of Continuity

## Abstract

Abstract Modulus of local continuity is used to evaluate the robustness of neural networks and fairness of their repeated uses in closed-loop models. Here, we revisit a connection between generalized derivatives and moduli of local continuity, and present a non-uniform stochastic sample approximation for moduli of local continuity. This is of importance in studying robustness of neural networks and fairness of their repeated uses.

## 1 Introduction

There is a substantial interest in *scalable* verification of properties of neural networks.
On one hand, some *qualitative* properties of a neural network can be established
by straightforward inspection of its compute graph.
For example, a ReLU-based network [3] will not be differentiable at points given by the break-points of the ReLU activation function, but will be locally Lipschitz.
On the other hand, establishing *quantitative* properties of the neural network, such as the precise Lipschitz constant and related metrics such as Consistent Robustness Analysis (CRA), is often non-trivial.

The modulus of local continuity (e.g., the Lipschitz constant), a key quantitative property of a neural network, is important both for evaluating the robustness [4, 5, 6, 7] of neural networks and for evaluating properties [8, 9, 10] of their repeated uses in closed-loop models.
Recently, much of the research has focussed on two classes of methods.
“LipMIP” and its variants [11, 12, 13, 14, e.g.] utilized mixed-integer programming formulations of the neural network, either directly for ReLU-based networks, or using some piece-wise linear approximation [15].
“LipSDP” and its variants
[16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, e.g.]
utilize relaxations in the form of semidefinite programming (SDP).
Substantial progress has been made recently in scaling these approaches.
State-of the-art implementations [23, 24, 27] can scale to shallow network with each of the hidden layers having hundreds of neurons.
Still, this is substantially less than the neural networks utilized in many practical applications.

Here, we revisit a connection between generalized derivatives and moduli of local continuity, and present a non-uniform stochastic sample approximation for these.
At its simplest, the connection is well known
[29, 30, 31]. Sampling values from the Clarke subdifferential at inputs sampled uniformly at random is a benchmark traditionally used for comparison of both LipSDP and LipMIP. For instance, [23] sampled 500,000 points uniformly at random from the input space and computed the maximum norm, lower bound.
We propose algorithms for estimating the modulus of continuity using non-uniform sampling from the input space utilizing upper-confidence-bound (UCB) policies.
The resulting estimator is consistent, asymptotically unbiased, and asymptotically optimal within a class of sampling policies.

## 2 Related Work

In this section we recall the basic theoretical setup for estimating Lipschitz constants, and review various ways this estimation has been done in practice.
We roughly follow the notation and definitions as in [32].
In particular, we assume $\|\cdot\|_{\alpha}$ and $\|\cdot\|_{\beta}$ are norms on $\mathbb{R}^{n}$ and $\mathbb{R}^{m}$ respectively.

###### Definition 1 .

[32, Definition 1]
The local $(\alpha,\beta)$-Lipschitz constant of a function $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ over a set $X\subseteq\mathbb{R}^{n}$ is defined as the following quantity:

$$ $L^{(\alpha,\beta)}(f,X)\ :=\ \sup_{x,y\in X}\frac{\|f(y)-f(x)\|_{\beta}}{\|x-y\|_{\alpha}}\quad(x\neq y)$ $$

Moreover, if $L^{(\alpha,\beta)}(f,X)$ is finite, we say that $f$ is $(\alpha,\beta)$-Lipschitz over $X$.

The starting point for estimating Lipschitz constants in terms of Jacobians $J_{f}(x)$ is the following well-known fact for smooth functions defined on convex(^1^11The paper [32] omits the assumption that $X$ is *convex*; although this assumption gets used in the proof of [32, Theorem 1] when considering the function “$f(x+t(y-x))$” for arbitrary $x,y\in X$.)
domains:

###### Lemma 2 .

If $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is $C^{1}$ and $(\alpha,\beta)$-Lipschitz over an open convex set $X$, then:

$$ $L^{(\alpha,\beta)}(f,X)\ =\ \sup_{x\in X}\|J_{f}(x)\|_{\alpha,\beta}$ $$

where $\|\cdot\|_{\alpha,\beta}$ is the induced matrix norm on $\mathbb{R}^{m\times n}$

In practice, many functions, including neural networks involving ReLU activations, are not smooth but are still Lipschitz.
At the points where such functions are non-smooth, one does not have a well-defined Jacobian; instead, one must resort to one of several (possibly set-valued) *generalized derivatives*, for instance the *Clarke Jacobian* $J_{f}^{c}$ (cf. Definition [27](https://arxiv.org/html/2509.15368v1#Thmthm27)). In this case, Lemma [2](https://arxiv.org/html/2509.15368v1#Thmthm2) can be generalized as follows:

###### Theorem 3 .

[32, Theorem 1]
Suppose $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is $(\alpha,\beta)$-lipschitz over an open convex set $X$. Then the following equality holds:

$$ $L^{(\alpha,\beta)}(f,X)\ =\ \sup_{x\in X,G\in J_{f}^{c}}\|G^{T}\|_{\alpha,\beta}$ $$

The modulus of local continuity can be estimated using a number of approaches. The most general methods may utilize finite-difference schemes, where one samples pairs of points close by, and evaluates the difference. In neural networks, one may leverage [29] frameworks such as PyTorch and TensorFlow to estimate generalized derivatives, usually Clarke subgradients.
More recent methods specific to neural networks leverage the computation graph of the neural network and either integer programming [11, 12, 13, 14] with linear relaxations,
or polynomial optimization [17, 19] with SDP relaxations [16, 16, 23, 24, 25, 26, 28]. [22, 25, 26] focus on the decomposition of the large SDP variable utilizing some notion of sparsity.
There are a variety of other approaches as well [33, 32, 34, 35], including
interval methods and branch and bound without convex relaxations [36, 37, 38, 39], but their empirical performance is broadly speaking similar.
Our work on the non-uniform sampling is also related (but not drawing on directly) to the Adaptive Sequential Elimination of [40].
Approaches such as [41, 42] are also related, but not directly applicable, due to their assumptions of (global) Lipschitz properties.

More broadly, the estimation of robustness properties [16] draws upon a long history of the study of neural networks in the control theory community [43, 44, e.g.], and a long history of control-theoretic contributions to machine learning [36, e.g.].

###### Definition 1 .

###### Lemma 2 .

###### Theorem 3 .

## 3 Our Approach

Figure: Figure 1: A running example. Left: training data. Middle: Neural network before (top) and after training (bottom). Right: Elements of Clarke subdifferential evaluated on the domain of the neural network prior to training (top) and after training (bottom). Maximum value sampled from the Clarke subdifferentials is marked with the red dot.
Refer to caption: images/compact_setup.png

We present a non-uniform stochastic sample approximation for estimating moduli of local continuity. First, we describe a straightforward stochastic approximation for the modulus of (local) Lipschitz continuity [29] by approximating the maximum norm of the (generalized) Jacobian matrix the neural network:
$J_{f}(x)$. Subsequently, we extend this to non-uniform, adaptive sampling.

###### Remark 4 .

Notice that many recent papers on the estimation of moduli of local continuity consider gradients and Jacobians, while they work with ReLU-based networks, which are non-smooth.
In keeping with the literature, we will use $J_{f}(x)$ to denote the generalized Jacobian, computed using the Clarke subdifferential for modulus of local Lipschitz continuity, or some other generalized derivatives for other moduli of local continuity.

###### Remark 4 .

### 3.1 Sampling Clarke subdifferential

Neural networks are a special case of non-smooth, non-convex functions, known as functions definable in o-minimal structures [45]. This class of functions comes with a chain rule for certain generalized derivatives, out of which the Clarke generalized derivative [46] is the most popular, and stability of definability, which guarantees that a composition of definable functions remains definable. (See the supplementary material.)
This enables
commonly used frameworks such as PyTorch and TensorFlow to have a formula for all elementary activation functions and to apply automatic differentiation of the neural network by matrix multiplication.
This way, one can evaluate elements of the Clarke subdifferential by a single call to the autograd library.
By doing so for many inputs and looking at the maximum of the sampled values, one can estimate the modulus of local Lipschitz continuity. See Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1).

Figure: Algorithm 1 Standard Stochastic Approximation, cf. [29]

### 3.2 Generalizations

One can generalize Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1) in two directions: first, to other moduli of local continuity, and second, to other forms of sampling.
Algorithm [2](https://arxiv.org/html/2509.15368v1#alg2) is parametrized by the modulus of local continuity and divides the $d$ dimensional input space into $k^{d}$ subregions and equally samples results from each one.
This is illustrated in Figure [2](https://arxiv.org/html/2509.15368v1#S3.F2).
Notice that the change in sampling is not a very important one, yet: Experiments of Section [5](https://arxiv.org/html/2509.15368v1#S5) (esp. Figure [4](https://arxiv.org/html/2509.15368v1#S4.F4)) show that there is no particular correlation between the number of partitions and the precision of the approximation.

Figure: Algorithm 2 Generalized Stochastic Approximation with Uniform Partitioning of the Domain

### 3.3 Non-uniform sampling with UCB

Non-uniform sampling, including importance sampling [47, 48, 49] and adaptive importance sampling [50], is
a standard tool from statistics, which
concentrates samples in regions where the estimate can be improved the most based on what has been sampled so far, without neglecting the other regions completely.
In multi-armed bandit problems [51, 52], the so-called upper-confidence bound policies [53, 54] have a long history as means of non-uniform sampling that has been shown to be asymptotically optimal in a variety of setttings.
The infinity-armed bandit problem [55, 56] can
be seen as an online sampling algorithm to estimate the maximum of a distribution.
We suggest to see the estimation of a modulus of local continuity as an infinity-armed bandit problem [55, 56], although without the commonly considered assumptions of Lipschitz continuity [57, 58], Bernoulli-distributed rewards [55, 59], and unique optimal arm [60].

Figure: Figure 2: The running example continued. Left: Elements of Clarke subdifferential evaluated on the domain of the trained neural network. Middle: uniform partitioning of the domain. Right: non-uniform partitioning of the domain utilizing the upper-confidence bounds.
Refer to caption: images/compact_results.png

In particular, Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) starts with an undivided domain $D$ of the neural network $f(x)$ as a single subregion.
In each of $N$ iterations, one sample is randomly chosen from the subregion with the highest current UCB score (also known as an index), computed as:

$$ $\begin{cases}s_{max}+c\cdot\sqrt{\frac{\ln(t+1)}{s_{n}}}\cdot s_{\sigma},&\text{if }s_{n}>10\\ \infty,&\text{if }s_{n}\leq 10\\ \end{cases}$ $$

where $s_{max}$ is the maximum encountered within the subregion so far, $s_{n}$ is the number of samples taken from the subregion so far, and $s_{\sigma}$ is the variance.
After an exponentially increasing ($t_{m}$, $t_{m}^{2}$, $t_{m}^{3},\ldots$) number of iterations,
a subregion that maximizes the UCB score ([3.3](https://arxiv.org/html/2509.15368v1#S3.Ex4)) is subdivided. When the domain is polyhedral, the subregions are kept polyhedral, and subdivided by axis-aligned hyperplanes. In particular, when subdividing subregion $s$, its longest side is halved by a perpendicular, axis-aligned hyperplane. $s_{n}=10$ threshold is set to get initial samples for each new subregion.

Figure: Algorithm 3 Generalized Stochastic Approximation with Non-uniform Partitioning of the Domain

## 4 An Analysis

It is clear by Theorem [3](https://arxiv.org/html/2509.15368v1#Thmthm3) that Algorithms 1-3 will always return a lower bound for the Lipschitz constant provided that “$J_{f}(x)$” is contained in the Clarke Jacobian $J_{f}^{c}(x)$. Our analysis addresses the following two questions:

- 1.
What degree of flexibility do we have in replacing $J_{f}^{c}$ in Theorem [3](https://arxiv.org/html/2509.15368v1#Thmthm3) with some other set-valued “generalized derivative”?
- 2.
What are the statistical properties of Algorithm 3?

### 4.1 Modifying Theorem 3

It has been observed many times [61, 62] that nearly all neural networks used in practice are definable in some o-minimal structure. Under this assumption, we describe in Theorem [6](https://arxiv.org/html/2509.15368v1#Thmthm6) below to what extent the role of the Clarke Jacobian in Theorem [3](https://arxiv.org/html/2509.15368v1#Thmthm3) can be replaced with a suitable alternative. See Appendix [A](https://arxiv.org/html/2509.15368v1#A1) for an elaboration of the current subsection, including a proof of Theorem [6](https://arxiv.org/html/2509.15368v1#Thmthm6).

We make the following assumptions:

- •
$\mathfrak{R}=(\mathbb{R};<,+,\cdot,\ldots)$ is an o-minimal expansion of the real field and “definable” means “definable in $\mathfrak{R}$ with parameters”. The reader is free to focus on the special case where $\mathfrak{R}=(\mathbb{R};<,+,\cdot)$ is the usual real field, in which case “definable” is a synonym for “semialgebraic”
- •
$\|\cdot\|_{\alpha}$ and $\|\cdot\|_{\beta}$ are norms on $\mathbb{R}^{n}$ and $\mathbb{R}^{m}$ respectively, not necessarily definable (in the sense of $\mathfrak{R}$)
- •
$X\subseteq\mathbb{R}^{n}$ is a definable open convex set
- •
$f:X\to\mathbb{R}^{m}$ is a definable $(\alpha,\beta)$-Lipschitz function

We introduce the following provisional terminology:

###### Definition 5 .

We say a set-valued map $D:X\rightrightarrows\mathbb{R}^{m\times n}$ is good for $f$ if:

- •
$D(x)\subseteq J_{f}^{c}(x)$ for every $x\in X$, and
- •
there exists $X_{0}\subseteq X$ such that:
–
$X\setminus X_{0}$ is a null set with respect to Lebesgue measure on $\mathbb{R}^{n}$, and
–
$D(x)$ is nonempty for every $x\in X_{0}$

[Note that we do not require $D$ or $X_{0}$ to be definable.]

Under these assumptions, we have the following variation of Theorem [3](https://arxiv.org/html/2509.15368v1#Thmthm3):

###### Theorem 6 .

If $D$ is good for $f$, then:

$$ $L^{(\alpha,\beta)}(f,X)\ =\ \sup_{x\in X,G\in D(x)}\|G\|_{\alpha,\beta}$ $$

###### Example 7 .

Apart from $D=J_{f}^{c}$, here are some examples of $D$ satisfying conditions of Theorem [6](https://arxiv.org/html/2509.15368v1#Thmthm6):

- •
$D$ can be the partially-defined single-valued map returning $J_{f}(x)$ at all points $x\in X$ for which $f$ is Fréchet-differentiable; more generally, given $r\geq 1$, $D$ can return $J_{f}(x)$ at all points $x\in X$ for which $f$ is $C^{r}$-smooth
- •
$D$ can be an arbitrary selection of $J_{f}^{c}$ defined a.e. in $X$
- •
when $m=1$, $D$ can be the Fréchet, limiting, or Clarke subdifferential; e.g., [63].

Note that Theorem [6](https://arxiv.org/html/2509.15368v1#Thmthm6) can fail if we do not assume that $f$ is definable:

###### Example 8 .

Let $f:\mathbb{R}\to\mathbb{R}$ be a Lipschitz function with Lipschitz constant $1$ such that $J_{f}^{c}(x)=[-1,1]$ for every $x\in\mathbb{R}$; such functions occur generically according to [45, 64] although they cannot be definable (as this would violate the Smooth Monotonicity Theorem [65, 7.2.5]). Set $D(x):=\{0\}$ for every $x\in\mathbb{R}$; then $D$ is good for $f$, however $\sup_{x\in\mathbb{R},G\in D(x)}\|G\|_{\alpha,\beta}=0\neq 1$.

As our idealized model for “$J_{f}(x)$” gets closer to how automatic differentiation (AD) is actually implemented by PyTorch or TensorFlow, then Theorem [6](https://arxiv.org/html/2509.15368v1#Thmthm6) may no longer be true due to sporadic behavior on null sets:

###### Remark 9 .

Suppose $D$ is either (1) the output of AD as modeled by selection Jacobians [66], or (2) a conservative mapping for $f$ [62]. Then $D=\{J_{f}(x)\}$ a.e. on $X$ and so $L^{(\alpha,\beta)}(f,X)\leq\sup_{x\in X,G\in D(x)}\|G\|_{\alpha,\beta}$. However, equality can fail in this case as [66, 62] provide easy examples where $f\equiv 0$, although $D(x)$ can contain nonzero vectors.

The consistency of the estimate obtained by Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) is clear from the fact that we are sampling from any point in the domain $D$ with a positive probability and the strong law of large numbers [48, cf. Theorem 4.7.3].
The estimate is not unbiased, but only
asymptotically unbiased
[48].
The asymptotic optimality of Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) within a certain class of sampling schemes is less trivial, but follows from well-known analyses [67] of UCB policies for the infinity-armed bandit problems.

Figure: Figure 3: The running example continued. Left: Samples obtained using the standard stochastic approximation (Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1)). Middle: samples obtained using uniform partitioning of the domain (Algorithm [2](https://arxiv.org/html/2509.15368v1#alg2)). Right: samples obtained using non-uniform partitioning of the domain utilizing the upper-confidence bounds (Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3)).
Refer to caption: images/compact_evaluated_pts.png

Figure: Figure 4: Illustrative results. Left: relative error of Algorithm [2](https://arxiv.org/html/2509.15368v1#alg2) is robust with respect to the number of subregions. Right: performance of Algorithms [1](https://arxiv.org/html/2509.15368v1#alg1) and [2](https://arxiv.org/html/2509.15368v1#alg2) is very similar, when considering one and the same subdiffrential. Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) strictly improves upon both Algorithms [1](https://arxiv.org/html/2509.15368v1#alg1) and [2](https://arxiv.org/html/2509.15368v1#alg2).
Refer to caption: images/equal_partition_error_2000.png

###### Definition 5 .

###### Theorem 6 .

###### Example 7 .

###### Example 8 .

###### Remark 9 .

## 5 Experimental results

As a proof of concept, we have implemented our approach in PyTorch using their automatic differentiation engine (torch.autograd).
In our experiments, we have used ReLU-based neural nets (composed of torch.nn.Linear and torch.nn.ReLU layers). To describe their dimensions, we use the notation such as of $[2,w_{1},w_{2},1]$, where there are two scalars on the inputs, a linear layer with $w_{1}$ output features, ReLU activation, a linear layer with $w_{1}$ input features and $w_{2}$ output features, ReLU activation, and a linear layer with $w_{2}$ input features and 1 output feature. For the purposes of visualization, we often focus on the two-dimensional input.
We generate synthetic datasets to match, one of which is displayed on the left in Figure [1](https://arxiv.org/html/2509.15368v1#S3.F1), with points randomly generated hyperspheres with points generated randomly with mean $-1.0$, while the remainder of the hypercube is filled with values generated at random with mean $1.0$.

In Figures [1](https://arxiv.org/html/2509.15368v1#S3.F1)–[3](https://arxiv.org/html/2509.15368v1#S4.F3), we focus on the running-example neural network [2, 16, 16, 1] presented in Figure [1](https://arxiv.org/html/2509.15368v1#S3.F1).

In Figure [4](https://arxiv.org/html/2509.15368v1#S4.F4) (on the right), we summarize the experiments where all the generated datasets had 3 hyperspheres of random radius $0.1\times r_{domain}\leq r_{sphere}\leq 0.4\times r_{domain}$ randomly centered on the input space.
For each number of hidden layers in the right plot in Figure [4](https://arxiv.org/html/2509.15368v1#S4.F4), 30 test runs were evaluated, for each test run a new neural net was trained on a random data set with 800 points. Training was performed with torch.nn.MSELoss() as loss function, torch.optim.Adam() as optimizer with learning rate $5\times 10^{-4}$ for 500 epochs.
All 3 algorithms were limited to 60000 evaluations, For Algorithm [2](https://arxiv.org/html/2509.15368v1#alg2), 2 divisions per dimension were set, resulting in $2^{7}$ subregions; for Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) the exploration parameter $c$ ([3.3](https://arxiv.org/html/2509.15368v1#S3.Ex4)) was set to 10 and the subdivision time multiplier was set to 2.

In Figure [4](https://arxiv.org/html/2509.15368v1#S4.F4) (on the left),
we ran Algorithm [2](https://arxiv.org/html/2509.15368v1#alg2) with different partition parameter on the one trained neural net of depth 4 and width 8, for each parameter value 100 runs were evaluated.
The 2D heat maps of the gradients that are present in the figures were generated by evaluating the $400^{2}$ grid. The red dot in the plots presented as Maximum is within the $0.001\%$ error of the actual value computed by LipMIP.

In Figure [5](https://arxiv.org/html/2509.15368v1#S5.F5), we evaluate using untrained neural nets. Stochastic Approximation and LipSDP were run without parallelization, and 5 cores were allocated for Gurobi engine in LipMIP.

In Table [1](https://arxiv.org/html/2509.15368v1#S5.T1),
we evaluate using neural nets trained on binary MNIST (classification between 1 and 7),
following the benchmarking procedure suggested by [11].
Column “setup” presents the dimensions of the net, and acceptable error of Algorithms [1](https://arxiv.org/html/2509.15368v1#alg1) and [3](https://arxiv.org/html/2509.15368v1#alg3) (when applicable). For each net, we ran 5 evaluations on trained net and best result in terms of relative error for each method was chosen. For the last two experiments, run time of LipMIP [11] was limited. Considering that LipSDP produces an upper bound, the lowest (best) result is presented. For Algorithms [1](https://arxiv.org/html/2509.15368v1#alg1) and [3](https://arxiv.org/html/2509.15368v1#alg3), the highest result is presented. Rows 2 and 4 present experiments, where Algorithms [1](https://arxiv.org/html/2509.15368v1#alg1) and [3](https://arxiv.org/html/2509.15368v1#alg3) could compare the outcomes against the LipMIP result. (This is of interest, because one may often have many similar nets and may wish to estimate of their moduli of continuity one by one, using as few iterations as possible.) Because LipMIP computes the modulus of $\langle c,f\rangle$, modified versions of Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) were used, where the modulus of local continuity was approximated from $\langle c,f\rangle$, rather than from the whole output of $f$.
Rows 6 and 7 present experiments, where the scalability of Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) strictly exceeds the scalability of LipMIP.
Rows 6 and 7 present experiments, where the scalability of Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) strictly exceeds the scalability of LipMIP.
By “?” in the “Relative error” column, we indicate that we do not have the exact modulus of local continuity. The comparison against LipSDP shows that our estimates improve upon LipSDP and its variants, whose upper bound is very loose (at least 356% higher in row 7), without requiring a longer run-time.

Figure: Figure 5: Illustrative comparison against LipMIP and LipSDP. Left: with the number of hidden layers (each of width 64), the modulus of local Lipschitz continuity decreases sharply. LipSDP overestimates the modulus by a substantial margin, while stochastic approximation with 50000 samples tracks the true values computed using LipMIP. Right: within a given run-time limit of 60 seconds, Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) with 50000 samples scales to depth-11 networks (704 neurons), where LipSDP utilizing Mosek scales to depth 9 (576 neurons) and LipMIP utilizing Gurobi scales to depth 3 (192 neurons).
Refer to caption: images/scalability_value_50k.png

**Table 1: Comparison of methods on Binary MNIST following the benchmarking procedure suggested in the LipMIP paper [11].**
| Setup | Method | Value | Time (s) | Relative Error (%) |
| --- | --- | --- | --- | --- |
| [784, 8, 2] | LipMIP | 77.08519 | 1.523 | 0 |
| LipSDP | 100.76831 | 7.610 | +30.7 |  |
| Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1) (5000) | 77.07964 | 0.312 | -0.007 |  |
| Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) (5000) | 77.07964 | 1.330 | -0.007 |  |
| [784, 8, 2]<br>Approximation tolerance 1% | LipMIP | 77.08519 | 1.523 | 0 |
| LipSDP | 100.76831 | 7.610 | +30.7 |  |
| Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1) (5000) | 77.07964 | 0.0132 | -0.007 |  |
| Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) (5000) | 77.07964 | 0.0004 | -0.007 |  |
| [784, 8, 8, 2] | LipMIP | 79.24930 | 6.214 | 0 |
| LipSDP | 104.73195 | 8.987 | +32.155 |  |
| Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1) (10000) | 79.01881 | 0.776 | -0.291 |  |
| Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) (10000) | 79.01880 | 2.696 | -0.291 |  |
| [784, 8, 8, 2]<br>Approximation tolerance 1% | LipMIP | 79.24930 | 6.214 | 0 |
| LipSDP | 104.73195 | 8.987 | +32.155 |  |
| Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1) (10000) | 79.01881 | 0.051 | -0.291 |  |
| Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) (10000) | 79.01880 | 0.408 | -0.291 |  |
| [784, 20, 20, 2] | LipMIP | 349.67096 | 6.048 | 0 |
| LipSDP | 479.54083 | 12.48653 | +37.140 |  |
| Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1) (150000) | 277.22370 | 11.931 | -20.719 |  |
| Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) (150000) | 290.12729 | 44.975 | -17.028 |  |
| [784, 8, 8, 8, 2] | LipMIP (timeout) | 114.48170 | 120.0 | ? |
| LipSDP | 125.98295 | 8.987 | ? |  |
| Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1) (100000) | 89.87323 | 9.255 | ? |  |
| Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) (100000) | 89.87323 | 20.522 | ? |  |
| [784, 8, 8, 8, 8, 8, 2] | LipMIP (timeout) | 519.65584 | 300.0 | ? |
| LipSDP | 429.07478 | 11.472 | ? |  |
| Algorithm [1](https://arxiv.org/html/2509.15368v1#alg1) (100000) | 94.14903 | 12.417 | ? |  |
| Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) (100000) | 94.14903 | 24.549 | ? |  |

## 6 Conclusions and Limitations

We have elaborated upon the connections between “generalized derivatives” and estimating Lipschitz constants in the setting of *tame optimization* [45].

We have also presented non-uniform sampling within the context of estimating the modulus of continuity using, and showed that it improves the scalability of the stochastic sample approximations therein, improving also over some well-established methods not based on stochastic sample approximations (LipMIP, LipSDP).
The advantage of non-uniform sampling (Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3)) is clear especially when there are both areas of vanishing (sub)gradients
[68] and areas with high variance of the subgradients in the domain. This is common [69] such as in the case of deeper and wider nets.

A key limitation of our method, as well as any other method for the verification of properties of neural networks known presently, is scalability. While our algorithms
can be applied to a neural network in any dimension, and
our results (e.g., Table
[1](https://arxiv.org/html/2509.15368v1#S5.T1) and Figure [5](https://arxiv.org/html/2509.15368v1#S5.F5)) suggest some improvement in run-time for instances where all methods are applicable, this is far from the scale of foundational models utilized in many applications.
One may wish to bound the rates of convergence of the UCB-based policies and to improve the per-iteration run-time.
In order to improve the per-iteration run-time (the number of sample paths per second), one may wish to implement the approach in JAX or Enzyme [70].

The performance of the Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) is also affected by the choice of the UCB exploration parameter $c$. Poor choice may lead to a higher number of iterations required to find a close approximation because the subregion of the input domain that contains the result may not be explored for a long time. It is not clear what value to choose without a general idea of the gradient space. A possible way to deal with this is to sample a small amount of gradients before running Algorithm [3](https://arxiv.org/html/2509.15368v1#alg3) to get an idea of the mean and standard deviation of the gradients across the input domain and then choose $c$ accordingly.

Related methods have extensive applications, e.g., in the safety filters for AI systems, and
in the design of controllers for such closed loops with guarantees of ergodic behaviour.

## References

- [1]
G. Cybenko, “Approximation by superpositions of a sigmoidal function,” Mathematics of control, signals and systems, vol. 2, no. 4, pp. 303–314,
1989.
- [2]
A. R. Barron, “Universal approximation bounds for superpositions of a
sigmoidal function,” IEEE Transactions on Information theory, vol. 39,
no. 3, pp. 930–945, 1993.
- [3]
A. S. Householder, “A theory of steady-state activity in nerve-fiber networks:
I. definitions and preliminary lemmas,” The bulletin of mathematical
biophysics, vol. 3, no. 2, pp. 63–69, 1941.
- [4]
O. Bastani, Y. Ioannou, L. Lampropoulos, D. Vytiniotis, A. Nori, and
A. Criminisi, “Measuring neural net robustness with constraints,” in Advances in Neural Information Processing Systems (D. Lee, M. Sugiyama,
U. Luxburg, I. Guyon, and R. Garnett, eds.), vol. 29, Curran Associates,
Inc., 2016.
- [5]
T. Huster, C.-Y. J. Chiang, and R. Chadha, “Limitations of the lipschitz
constant as a defense against adversarial examples,” in ECML PKDD 2018
Workshops: Nemesis 2018, UrbReas 2018, SoGood 2018, IWAISe 2018, and Green
Data Mining 2018, Dublin, Ireland, September 10-14, 2018, Proceedings,
(Berlin, Heidelberg), p. 16–29, Springer-Verlag, 2018.
- [6]
Z. Yang, T. Pang, and Y. Liu, “A closer look at the adversarial robustness of
deep equilibrium models,” Advances in Neural Information Processing
Systems, vol. 35, pp. 10448–10461, 2022.
- [7]
M.-M. Zühlke and D. Kudenko, “Adversarial robustness of neural networks
from the perspective of lipschitz calculus: A survey,” ACM Computing
Surveys, 2024.
- [8]
J. Mareček, M. Roubalik, R. Ghosh, R. N. Shorten, and F. R. Wirth,
“Predictability and fairness in load aggregation and operations of virtual
power plants,” Automatica, vol. 147, p. 110743, 2023.
- [9]
Q. Zhou, R. Ghosh, R. Shorten, and J. Mareček, “Closed-loop view of the
regulation of ai: Equal impact across repeated interactions,” in 2024
IEEE 40th International Conference on Data Engineering Workshops (ICDEW),
pp. 176–181, 2024.
- [10]
R. Nazarov, A. Quinn, R. Shorten, and J. Marecek,
“humancompatible.interconnect: Testing properties of repeated uses of
interconnections of ai systems,” 2025.
- [11]
V. Tjeng, K. Y. Xiao, and R. Tedrake, “Evaluating robustness of neural
networks with mixed integer programming,” in International Conference
on Learning Representations, 2019.
- [12]
R. Anderson, J. Huchette, W. Ma, C. Tjandraatmadja, and J. P. Vielma, “Strong
mixed-integer programming formulations for trained neural networks,” Mathematical Programming, vol. 183, no. 1, pp. 3–39, 2020.
- [13]
H. Zhang, S. Wang, K. Xu, L. Li, B. Li, S. Jana, C.-J. Hsieh, and J. Z. Kolter,
“General cutting planes for bound-propagation-based neural network
verification,” Advances in neural information processing systems,
vol. 35, pp. 1656–1670, 2022.
- [14]
R. Schwan, C. N. Jones, and D. Kuhn, “Stability verification of neural network
controllers using mixed-integer programming,” IEEE Transactions on
Automatic Control, vol. 68, no. 12, pp. 7514–7529, 2023.
- [15]
Gurobi Optimization, LLC, “Gurobi machine learning,”
https://gurobi-machinelearning.readthedocs.io/en/stable/userguide.html.
- [16]
M. Fazlyab, M. Morari, and G. J. Pappas, “Safety verification and robustness
analysis of neural networks via quadratic constraints and semidefinite
programming,” IEEE Transactions on Automatic Control, vol. 67, no. 1,
pp. 1–15, 2022.
- [17]
T. Chen, J. B. Lasserre, V. Magron, and E. Pauwels, “Semialgebraic
optimization for lipschitz constants of relu networks,” Advances in
Neural Information Processing Systems, vol. 33, pp. 19189–19200, 2020.
- [18]
F. Latorre, P. Rolland, and V. Cevher, “Lipschitz constant estimation of
neural networks via sparse polynomial optimization,” in International
Conference on Learning Representations, 2020.
- [19]
T. Chen, J. B. Lasserre, V. Magron, and E. Pauwels, “Semialgebraic
representation of monotone deep equilibrium models and applications to
certification,” Advances in Neural Information Processing Systems,
vol. 34, pp. 27146–27159, 2021.
- [20]
K. D. Dvijotham, R. Stanforth, S. Gowal, C. Qin, S. De, and P. Kohli,
“Efficient neural network verification with exactness characterization,” in
Proceedings of The 35th Uncertainty in Artificial Intelligence
Conference (R. P. Adams and V. Gogate, eds.), vol. 115 of Proceedings
of Machine Learning Research, pp. 497–507, PMLR, 22–25 Jul 2020.
- [21]
T. Chen, Robustness verification of neural networks using polynomial
optimization.
PhD thesis, Université Paul Sabatier-Toulouse III, 2022.
- [22]
A. Xue, L. Lindemann, A. Robey, H. Hassani, G. J. Pappas, and R. Alur,
“Chordal sparsity for lipschitz constant estimation of deep neural
networks,” in 2022 IEEE 61st Conference on Decision and Control (CDC),
pp. 3389–3396, 2022.
- [23]
Z. Wang, B. Hu, A. J. Havens, A. Araujo, Y. Zheng, Y. Chen, and S. Jha, “On
the scalability and memory efficiency of semidefinite programs for lipschitz
constant estimation of neural networks,” in The Twelfth International
Conference on Learning Representations, 2024.
- [24]
J. Yang, S. Ðurašinović, J.-B. Lasserre, V. Magron, and J. Zhao,
“Verifying properties of binary neural networks using sparse polynomial
optimization,” arXiv preprint arXiv:2405.17049, 2024.
- [25]
P. Pauli, D. Gramlich, and F. Allgöwer, “Lipschitz constant estimation for
general neural network architectures using control tools,” arXiv
preprint arXiv:2405.01125, 2024.
- [26]
Y. Xu and S. Sivaranjani, “ECLipse: Efficient compositional lipschitz
constant estimation for deep neural networks,” in The Thirty-eighth
Annual Conference on Neural Information Processing Systems, 2024.
- [27]
J. Lan, Y. Zheng, and A. Lomuscio, “Tight neural network verification via
semidefinite relaxations and linear reformulations,” in AAAI,
pp. 7272–7280, 2022.
- [28]
U. Syed and B. Hu, “Improved scalable lipschitz bounds for deep neural
networks,” 2025.
- [29]
T.-W. Weng, H. Zhang, P.-Y. Chen, J. Yi, D. Su, Y. Gao, C.-J. Hsieh, and
L. Daniel, “Evaluating the robustness of neural networks: An extreme value
theory approach,” in International Conference on Learning
Representations, 2018.
- [30]
I. Goodfellow, “Gradient masking causes clever to overestimate adversarial
perturbation size,” 2018.
- [31]
T.-W. Weng, H. Zhang, P.-Y. Chen, A. Lozano, C.-J. Hsieh, and L. Daniel, “On
extensions of clever: A neural network robustness evaluation algorithm,” in
2018 IEEE Global Conference on Signal and Information Processing
(GlobalSIP), pp. 1159–1163, IEEE, 2018.
- [32]
M. Jordan and A. G. Dimakis, “Exactly computing the local lipschitz constant
of relu networks,” Advances in Neural Information Processing Systems,
vol. 33, pp. 7344–7353, 2020.
- [33]
T. Avant and K. A. Morgansen, “Analytical bounds on the local lipschitz
constants of relu networks,” IEEE Transactions on Neural Networks and
Learning Systems, vol. 35, no. 10, pp. 13902–13913, 2024.
- [34]
G. Bonaert, D. I. Dimitrov, M. Baader, and M. Vechev, “Fast and precise
certification of transformers,” in Proceedings of the 42nd ACM SIGPLAN
International Conference on Programming Language Design and Implementation,
PLDI 2021, (New York, NY, USA), p. 466–481, Association for Computing
Machinery, 2021.
- [35]
S. Jafarpour, M. Abate, A. Davydov, F. Bullo, and S. Coogan, “Robustness
certificates for implicit neural networks: A mixed monotone contractive
approach,” in Learning for Dynamics and Control Conference,
pp. 917–930, PMLR, 2022.
- [36]
R. R. Bunel, I. Turkaslan, P. Torr, P. Kohli, and P. K. Mudigonda, “A unified
view of piecewise linear neural network verification,” Advances in
Neural Information Processing Systems, vol. 31, 2018.
- [37]
B. Karg and S. Lucia, “Stability and feasibility of neural network-based
controllers via output range analysis,” in 2020 59th IEEE Conference on
Decision and Control (CDC), pp. 4947–4954, 2020.
- [38]
C. Wei and J. Z. Kolter, “Certified robustness for deep equilibrium models via
interval bound propagation,” in International Conference on Learning
Representations, 2022.
- [39]
E. Abad Rocamora, M. F. Sahin, F. Liu, G. Chrysos, and V. Cevher, “Sound and
complete verification of polynomial networks,” in Advances in Neural
Information Processing Systems (S. Koyejo, S. Mohamed, A. Agarwal,
D. Belgrave, K. Cho, and A. Oh, eds.), vol. 35, pp. 3517–3529, Curran
Associates, Inc., 2022.
- [40]
M. Aziz, J. Anderton, E. Kaufmann, and J. Aslam, “Pure exploration in
infinitely-armed bandit models with fixed-confidence,” in Algorithmic
Learning Theory, pp. 3–24, PMLR, 2018.
- [41]
D. R. Jones, C. D. Perttunen, and B. E. Stuckman, “Lipschitzian optimization
without the lipschitz constant,” Journal of optimization Theory and
Applications, vol. 79, pp. 157–181, 1993.
- [42]
J. M. X. Gablonsky and C. T. Kelley, Modifications of the direct
algorithm.
PhD thesis, North Carolina State University, Raleigh, North Carolina,
2001.
- [43]
D. Psaltis, A. Sideris, and A. Yamamura, “A multilayered neural network
controller,” IEEE Control Systems Magazine, vol. 8, no. 2, pp. 17–21,
1988.
- [44]
T. Parisini and R. Zoppoli, “A receding-horizon regulator for nonlinear
systems and a neural approximation,” Automatica, vol. 31, no. 10,
pp. 1443–1451, 1995.
- [45]
A. D. Ioffe, “An invitation to tame optimization,” SIAM J. Optim.,
vol. 19, no. 4, pp. 1894–1917, 2008.
- [46]
F. H. Clarke, “Generalized gradients and applications,” Transactions of
the American Mathematical Society, vol. 205, pp. 247–262, 1975.
- [47]
H. Kahn, “Random sampling (monte carlo) techniques in neutron attenuation
problems–ii.,” Nucleonics, vol. 6, no. 6, pp. 60–65, 1950.
- [48]
C. P. Robert, G. Casella, and G. Casella, Monte Carlo statistical
methods, vol. 2.
Springer, 1999.
- [49]
S. T. Tokdar and R. E. Kass, “Importance sampling: a review,” Wiley
Interdisciplinary Reviews: Computational Statistics, vol. 2, no. 1,
pp. 54–60, 2010.
- [50]
M. F. Bugallo, V. Elvira, L. Martino, D. Luengo, J. Miguez, and P. M. Djuric,
“Adaptive importance sampling: The past, the present, and the future,” IEEE Signal Processing Magazine, vol. 34, no. 4, pp. 60–79, 2017.
- [51]
J. Gittins, K. Glazebrook, and R. Weber, Multi-armed bandit allocation
indices.
John Wiley & Sons, 2011.
- [52]
T. Lattimore and C. Szepesvári, Bandit algorithms.
Cambridge University Press, 2020.
- [53]
T. L. Lai, “Adaptive treatment allocation and the multi-armed bandit
problem,” The annals of statistics, pp. 1091–1114, 1987.
- [54]
P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the
multiarmed bandit problem,” Machine Learning, vol. 47, no. 2,
pp. 235–256, 2002.
- [55]
D. A. Berry, R. W. Chen, A. Zame, D. C. Heath, and L. A. Shepp, “Bandit
problems with infinitely many arms,” The Annals of Statistics,
vol. 25, no. 5, pp. 2103–2116, 1997.
- [56]
Y. Wang, J.-Y. Audibert, and R. Munos, “Algorithms for infinitely many-armed
bandits,” Advances in Neural Information Processing Systems, vol. 21,
2008.
- [57]
R. Kleinberg, A. Slivkins, and E. Upfal, “Multi-armed bandits in metric
spaces,” in Proceedings of the Fortieth Annual ACM Symposium on Theory
of Computing, STOC ’08, (New York, NY, USA), p. 681–690, Association for
Computing Machinery, 2008.
- [58]
S. Bubeck, G. Stoltz, and J. Y. Yu, “Lipschitz bandits without the lipschitz
constant,” in Algorithmic Learning Theory (J. Kivinen,
C. Szepesvári, E. Ukkonen, and T. Zeugmann, eds.), (Berlin, Heidelberg),
pp. 144–158, Springer Berlin Heidelberg, 2011.
- [59]
E. X.-Y. Gong and M. Sellke, “Asymptotically optimal quantile pure exploration
for infinite-armed bandits,” in Advances in Neural Information
Processing Systems (A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt,
and S. Levine, eds.), vol. 36, pp. 18551–18581, Curran Associates, Inc.,
2023.
- [60]
R. De Heide, J. Cheshire, P. Ménard, and A. Carpentier, “Bandits with many
optimal arms,” Advances in Neural Information Processing Systems,
vol. 34, pp. 22457–22469, 2021.
- [61]
D. Davis, D. Drusvyatskiy, S. Kakade, and J. D. Lee, “Stochastic subgradient
method converges on tame functions,” Foundations of computational
mathematics, vol. 20, no. 1, pp. 119–154, 2020.
- [62]
J. Bolte and E. Pauwels, “Conservative set valued fields, automatic
differentiation, stochastic gradient methods and deep learning,” Mathematical Programming, vol. 188, pp. 19–51, 2021.
- [63]
J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota, “Clarke subgradients of
stratifiable functions,” SIAM Journal on Optimization, vol. 18, no. 2,
pp. 556–572, 2007.
- [64]
J. Borwein and X. Wang, “Distinct differentiable functions may share the same
clarke subdifferential at all points,” Proceedings of the American
Mathematical Society, vol. 125, no. 3, pp. 807–813, 1997.
- [65]
L. Van den Dries, Tame topology and o-minimal structures, vol. 248.
Cambridge university press, 1998.
- [66]
J. Bolte and E. Pauwels, “A mathematical model for automatic differentiation
in machine learning,” Advances in Neural Information Processing
Systems, vol. 33, pp. 10809–10819, 2020.
- [67]
R. Munos, “Optimistic optimization of a deterministic function without the
knowledge of its smoothness,” in Advances in Neural Information
Processing Systems (J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and
K. Weinberger, eds.), vol. 24, Curran Associates, Inc., 2011.
- [68]
S. Hochreiter, “The vanishing gradient problem during learning recurrent
neural nets and problem solutions,” International Journal of
Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 6, no. 02,
pp. 107–116, 1998.
- [69]
B. Hanin, “Which neural net architectures give rise to exploding and vanishing
gradients?,” Advances in neural information processing systems,
vol. 31, 2018.
- [70]
W. Moses and V. Churavy, “Instead of rewriting foreign code for machine
learning, automatically synthesize fast gradients,” in Advances in
Neural Information Processing Systems (H. Larochelle, M. Ranzato,
R. Hadsell, M. F. Balcan, and H. Lin, eds.), vol. 33, pp. 12472–12485,
Curran Associates, Inc., 2020.
- [71]
M. Aschenbrenner, L. van den Dries, and J. van der Hoeven, Asymptotic
differential algebra and model theory of transseries, vol. 195 of Annals of Mathematics Studies.
Princeton University Press, Princeton, NJ, 2017.
- [72]
R. T. Rockafellar and R. J.-B. Wets, Variational analysis, vol. 317.
Springer Science & Business Media, 2009.
- [73]
A. Fischer, Peano-differentiable functions in o-minimal structures.
PhD thesis, Universität Passau, 2005.
- [74]
K. A. Ross, Elementary analysis.
Undergraduate Texts in Mathematics, Springer, New York, second ed.,
2013.
The theory of calculus, In collaboration with Jorge M. López.
- [75]
F. H. Clarke, Optimization and nonsmooth analysis, vol. 5 of Classics in Applied Mathematics.
Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
PA, second ed., 1990.
- [76]
H. Rademacher, “Über partielle und totale differenzierbarkeit von
funktionen mehrerer variabeln und über die transformation der
doppelintegrale,” Mathematische Annalen, vol. 79, no. 4, pp. 340–359,
1919.
- [77]
J. Warga, “Fat homeomorphisms and unbounded derivate containers,” J.
Math. Anal. Appl., vol. 81, no. 2, pp. 545–560, 1981.

## Appendix A Technical Appendices and Supplementary Material

In this appendix we give a proof of Theorem [6](https://arxiv.org/html/2509.15368v1#Thmthm6) (Theorem [41](https://arxiv.org/html/2509.15368v1#Thmthm41) below) which is an o-minimal variant of [32, Theorem 1] (Theorem [3](https://arxiv.org/html/2509.15368v1#Thmthm3) above). Theorem [6](https://arxiv.org/html/2509.15368v1#Thmthm6) follows from the following nontrivial but well-known facts about functions $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$:

- 1.
if $f$ is definable in an o-minimal expansion of the real field (in short: $f$ *is definable*), then $f$ is $C^{1}$ almost everywhere (cf. Lemma [24](https://arxiv.org/html/2509.15368v1#Thmthm24))
- 2.
(Rademacher’s Theorem) if $f$ is locally Lipschitz, then $f$ is Fréchet-dfferentiable almost everywhere (cf. Lemma [29](https://arxiv.org/html/2509.15368v1#Thmthm29))
- 3.
(Warga’s Theorem) for locally Lipschitz $f$, the Clarke Jacobian $J_{f}^{c}$ of $f$ is “blind” to sets of measure zero (cf. Lemma [31](https://arxiv.org/html/2509.15368v1#Thmthm31))

Taking these facts for granted, here we otherwise give a self-contained account in order to see where the assumption of definability is relevant and where it is not. In particular, via a Path Lemma [32](https://arxiv.org/html/2509.15368v1#Thmthm32) we are able to avoid the Lebesgue integral in favor of the Riemann integral in the proof of [32, Theorem 1] (Corollary [34](https://arxiv.org/html/2509.15368v1#Thmthm34) below) in the case that $f$ is definable.

We set the following assumptions/conventions throughout the appendix (more assumptions will be added along the way):

- •
$\mathfrak{R}=(\mathbb{R};<,+,\cdot,\ldots)$ is an o-minimal expansion of the real field and “definable” means “definable in $\mathfrak{R}$ with parameters”
- •
we assume the reader is familiar with the concepts of *o-minimality* and *definability*; our main references for these concepts include [65] and [71, Appendix B].
The reader is free to consider the special case where $\mathfrak{R}=(\mathbb{R};<,+,\cdot)$ is the real field, and thus “definable” means “semialgebraic”
- •
$f:\mathbb{R}^{n}\rightharpoonup\mathbb{R}^{m}$ is a partial function
- •
$X\subseteq\operatorname{dom}(f)\subseteq\mathbb{R}^{n}$
- •
for points $x,y\in\mathbb{R}^{n}$, we denote the line segment from $x$ to $y$ by:
$[x,y]\ :=\ \{(1-t)x+ty:t\in[0,1]\}$
- •
recall [72, Chapter 5] that a *set-valued map* $D:A\rightrightarrows B$ is by definition a function $D:A\to\mathcal{P}(B)$ (where $\mathcal{P}(B)$ denotes the powerset of $B$). When convenient, we identify $D$ with its *graph* $\operatorname{gph}D:=\{(a,b):b\in D(a)\}\subseteq A\times B$. If $A\subseteq\mathbb{R}^{m}$ and $B\subseteq\mathbb{R}^{n}$, then we say $D$ is *definable* if $\operatorname{gph}D\subseteq\mathbb{R}^{m+n}$ is definable.
- •
we roughly follow the notation and definitions as in [32]

### Norms on vector spaces over ℝ \mathbb{R}

The concept of *Lipschitz constant* is relative to a choice of norms on the spaces $\mathbb{R}^{m},\mathbb{R}^{n}$. Here we recall some basic definitions and properties concerning norms.

###### Definition 10 .

Suppose $V$ is a vector space over $\mathbb{R}$. A norm $\|\cdot\|$ on $V$ is a function:

$$ $\|\cdot\|\ :\ V\to[0,+\infty)$ $$

which satisfies for all $x,y\in V$ and $\lambda\in\mathbb{R}$:

- 1.
(Positive definiteness) $\|x\|=0$ iff $x=0$
- 2.
(Absolute homogeneity) $\|\lambda x\|=|\lambda|\|x\|$
- 3.
(Triangle inequality) $\|x+y\|\leq\|x\|+\|y\|$

###### Lemma 11 .

Suppose $\|\cdot\|$ is a norm on $\mathbb{R}^{n}$.

- 1.
If $x_{i}$ is a sequence in $\mathbb{R}^{n}$ such that $x_{i}\to x$, then:
$\|x\|\ =\ \lim_{i\to\infty}\|x_{i}\|\ \leq\ \sup\{\|x_{i}\|:i\geq 0\}$
- 2.
If $X\subseteq\mathbb{R}^{n}$, then:
$\sup_{x\in X}\|x\|\ =\ \sup_{x\in\operatorname{conv}(X)}\|x\|$

###### Proof.

(1) Follows from the fact that $\|\cdot\|:\mathbb{R}^{n}\to\mathbb{R}$ is a continuous function.

(2) The direction “$\leq$” is clear. For the “$\geq$” direction, suppose $x\in\operatorname{conv}(X)$, then there is $k\geq 1$ and $x_{1},\ldots,x_{k}\in X$ and $\lambda_{1},\ldots,\lambda_{k}\in[0,1]$ such that $x=\sum_{1\leq i\leq k}\lambda_{i}x_{i}$ and $\sum_{1\leq i\leq k}\lambda_{i}=1$. Suppose $i_{0}\in\{1,\ldots,k\}$ satisfies $\|x_{i_{0}}\|=\max\{\|x_{i}\|:i=1,\ldots,k\}$. Then:

$$ $\textstyle\|\sum_{1\leq i\leq k}\lambda_{i}x_{i}\|\ \leq\ \sum_{1\leq i\leq k}\lambda_{i}\|x_{i}\|\ \leq\ \sum_{1\leq i\leq k}\lambda_{i}\|x_{i_{0}}\|\ =\ \|x_{i_{0}}\|\qed$ $$

The following lemma includes a template for the type of construction which occurs in the definition of *Clarke Jacobian*:

###### Lemma 12 .

Given $S\subseteq X$ and $J:S\to\mathbb{R}^{m}$, define:

$$ $D_{J}\ :\ X\rightrightarrows\mathbb{R}^{m},\quad x\ \mapsto\ D_{J}(x)\ :=\ \{\lim_{i\to\infty}J(x_{i}):x_{i}\to x,x_{i}\in S\}$ $$

Then:

$$ $\sup_{x\in S}\|J(x)\|_{\beta}\ =\ \sup_{x\in X,G\in\operatorname{conv}(D_{J}(x))}\|G\|_{\beta}$ $$

###### Proof.

It is clear that the direction “$\leq$” holds. Conversely, first note that by Lemma [11](https://arxiv.org/html/2509.15368v1#Thmthm11)(2) we have:

$$ $\sup_{x\in X,G\in\operatorname{conv}(D_{J}(x))}\|G\|_{\beta}\ =\ \sup_{x\in X}\sup_{G\in\operatorname{conv}(D_{J}(x))}\|G\|_{\beta}\ =\ \sup_{x\in X}\sup_{G\in D_{J}(x)}\|G\|_{\beta}$ $$

Next, let $x\in X$ and $G\in D_{J}(x)$ be arbitrary, and take $x_{i}\in S$ such that $x_{i}\to x$ and $J(x_{i})\to G$. Then by Lemma [11](https://arxiv.org/html/2509.15368v1#Thmthm11)(1) we have

$$ $\|G\|_{\beta}\ \leq\ \sup\{\|J(x_{i})\|_{\beta}:i\geq 0\}\ \leq\ \sup_{x\in S}\|J(x)\|_{\beta}$ $$

Since $x,G$ were arbitrary, this yields the “$\geq$” direction.
∎

As is common, we shall identify $\mathbb{R}^{n}$ with its dual space. A norm $\|\cdot\|$ on $\mathbb{R}^{n}$ induces a dual norm $\|\cdot\|_{*}$ on the dual space $\mathbb{R}^{n}$:

$$ $\|\cdot\|_{*}\ :\ \mathbb{R}^{n}\to[0,+\infty),\quad y\ \mapsto\ \|y\|_{*}\ :=\ \sup_{\|x\|\leq 1}\langle x,y\rangle$ $$

In our finite-dimensional setting we have $\|\cdot\|_{\ast\ast}=\|\cdot\|$. We will also make use Hölder’s inequality for dual norms:

###### Lemma 13 .

[32, Proposition 1]
Suppose $\|\cdot\|$ is a norm on $\mathbb{R}^{n}$. Then for every $x,y\in\mathbb{R}^{n}$ we have:

$$ $\langle x,y\rangle\ \leq\ \|x\|\cdot\|y\|_{*}$ $$

Using the double dual norm and Hölder’s inequality, we get:

###### Lemma 14 (Continuous triangle inequality) .

Suppose $g:[0,1]\to\mathbb{R}^{m}$ is Riemann integrable and $\|\cdot\|$ is a norm on $\mathbb{R}^{m}$. Then $\|g\|:[0,1]\to\mathbb{R}$ is Riemann integrable and:

$$ $\textstyle\|\int_{0}^{1}g(t)dt\|\ \leq\ \int_{0}^{1}\|g(t)\|dt$ $$

###### Proof.

The first statement is clear. Using the double dual norm and linearity, it suffices to show:

$$ $\textstyle\|\int_{0}^{1}g(t)dt\|\ =\ \sup_{\|y\|_{*}\leq 1}\langle y,\int_{0}^{1}g(t)dt\rangle\ =\ \sup_{\|y\|_{*}\leq 1}\int_{0}^{1}\langle y,g(t)\rangle dt\ \leq\ \int_{0}^{1}\|g(t)\|dt$ $$

Let $y$ be arbitrary such that $\|y\|_{*}\leq 1$, then it suffices to show:

$$ $\textstyle\int_{0}^{1}\langle y,g(t)\rangle dt\ \leq\ \int_{0}^{1}\|g(t)\|dt$ $$

For this, it suffices to show for every $t\in[0,1]$:

$$ $\langle y,g(t)\rangle\ \leq\ \|g(t)\|$ $$

However this follows from Hölder’s inequality [13](https://arxiv.org/html/2509.15368v1#Thmthm13) for dual norms:

$$ $\textstyle\langle y,g(t)\rangle\ \leq\ \|y\|_{*}\|g(t)\|\ \leq\ \|g(t)\|$ $$

since $\|y\|_{*}\leq 1$.
∎

For the rest of this appendix, we further assume:

- •
$\|\cdot\|_{\alpha}$ and $\|\cdot\|_{\beta}$ are norms on $\mathbb{R}^{n}$ and $\mathbb{R}^{m}$ respectively (we don’t require these norms to be definable, e.g., the graph of the function $\|\cdot\|_{\alpha}:\mathbb{R}^{n}\to\mathbb{R}$, as a subset of $\mathbb{R}^{n+1}$, is not assumed to be definable in $\mathfrak{R}$, likewise for $\|\cdot\|_{\beta}$)

We may also define the matrix norm $\|\cdot\|_{\alpha,\beta}$ on $\mathbb{R}^{m\times n}$ induced by $\|\cdot\|_{\alpha}$ and $\|\cdot\|_{\beta}$:

$$ $\|\cdot\|_{\alpha,\beta}\ :\ \mathbb{R}^{m\times n}\to[0,+\infty),\quad A\ \mapsto\ \sup_{\|x\|_{\alpha}\leq 1}\|Ax\|_{\beta}$ $$

There is also an analogous Hölder-type inequality for matrix norms:

###### Lemma 15 .

[32, Proposition A.2]
For every $A\in\mathbb{R}^{m\times n}$ and $x\in\mathbb{R}^{n}$ we have:

$$ $\|Ax\|_{\beta}\ \leq\ \|A\|_{\alpha,\beta}\|x\|_{\alpha}$ $$

###### Definition 10 .

###### Lemma 11 .

###### Proof.

###### Lemma 12 .

###### Proof.

###### Lemma 13 .

###### Lemma 14 (Continuous triangle inequality) .

###### Proof.

###### Lemma 15 .

### The Lipschitz property

###### Definition 16 .

[32, Definition 1]
The local $(\alpha,\beta)$-Lipschitz constant of $f$ over $X$ is the (possibly infinite) quantity:

$$ $L^{(\alpha,\beta)}(f,X)\ :=\ \sup_{x,y\in X}\frac{\|f(x)-f(y)\|_{\beta}}{\|x-y\|_{\alpha}}\quad(x\neq y)$ $$

Moreover, if $L^{(\alpha,\beta)}(f,X)$ is finite, we say that $f$ is $(\alpha,\beta)$-Lipschitz over $X$.
We say that $f$ is locally $(\alpha,\beta)$-Lipschitz over $X$ if for every $x\in X$, there exists a neighbourhood $U$ of $x$ such that $f$ is $(\alpha,\beta)$-Lipschitz over $X\cap U$.

The following is well-known:

###### Lemma 17 .

If $X$ is compact and $f$ is locally $(\alpha,\beta)$-Lipschitz over $X$, then $f$ is $(\alpha,\beta)$-Lipschitz over $X$.

###### Definition 16 .

###### Lemma 17 .

### Directionally differentiable, Fréchet differentiable, and C 1 C^{1}

For the rest of this appendix, we further assume:

- •
$X$ is open

###### Definition 18 .

Given $x\in X$ and $v\in\mathbb{R}^{n}$, we say that $f$ is directionally differentiable at $x$ in the direction $v$ if there exists $\ell\in\mathbb{R}^{m}$ such that:

$$ $\lim_{t\downarrow 0}(f(x+tv)-f(x))/t\ =\ \ell$ $$

in which case we define the directional derivative $f^{\prime}(x;v)$ of $f$ at $x$ in the direction $v$ to be $f^{\prime}(x;v):=\ell$. We say that $f$ is directionally differentiable at $x$ if $f$ is directionally differentiable at $x$ in the direction $v$ for every $v\in\mathbb{R}^{n}$.

Here is the basic relationship between a directional derivative and the Lipschitz constant:

###### Lemma 19 .

If $f$ is directionally differentiable at $x$ in the direction $v$, then:

$$ $\|f^{\prime}(x;v)\|_{\beta}\ \leq\ L^{(\alpha,\beta)}(f,X)\|v\|_{\alpha}$ $$

###### Proof.

We may suppose $v\neq 0$. For every $\varepsilon>0$ we can find $t>0$ sufficiently small such that $\|f^{\prime}(x;v)\|_{\beta}$ is within $\varepsilon$ from the quantity:

$$ $\frac{\|f(x+tv)-f(x)\|_{\beta}}{t}\ =\ \|v\|_{\alpha}\frac{\|f(x+tv)-f(x)\|_{\beta}}{\|(x+tv)-x\|_{\alpha}}$ $$

Since the quantity on the righthand side contributes to the definition of $L^{(\alpha,\beta)}(f,X)\|v\|_{\alpha}$ as a certain supremum, the inequality follows.
∎

###### Definition 20 .

We say that $f$ is Fréchet-differentiable at $x$ if there exists a linear map $L:\mathbb{R}^{n}\to\mathbb{R}^{m}$ such that $f(x)+L(y-x)$ is a first-order approximation of $f$ at $x$, i.e., we have:

$$ $\lim_{y\to x}\frac{\|f(y)-f(x)-L(y-x)\|_{\beta}}{\|y-x\|_{\alpha}}\ =\ 0$ $$

in which case we define the Jacobian $J_{f}(x)$ of $f$ at $x$ to be the (necessarily unique) linear map $J_{f}(x)=L$; we shall identify the Jacobian $J_{f}(x)$ with a matrix in $\mathbb{R}^{m\times n}$ which represents $L$ with respect to the standard basis.

###### Lemma 21 .

If $f$ is Fréchet-differentiable at $x$, then $f$ is directionally differentiable at $x$ and for every $v\in\mathbb{R}^{n}$, we have:

$$ $J_{f}(x)v\ =\ f^{\prime}(x;v)$ $$

Here is a relationship between the Jacobian at a point and the Lipschitz constant:

###### Lemma 22 .

If $f$ is Fréchet-differentiable at $z\in X$, then:

$$ $\|J_{f}(z)\|_{\alpha,\beta}\ \leq\ L^{(\alpha,\beta)}(f,X)$ $$

###### Proof.

By Lemmas [21](https://arxiv.org/html/2509.15368v1#Thmthm21) and [19](https://arxiv.org/html/2509.15368v1#Thmthm19) we have:

$$ $\|J_{f}(z)\|_{\alpha,\beta}\ =\ \sup_{\|v\|_{\alpha}\leq 1}\|J_{f}(z)v\|_{\beta}\ =\ \sup_{\|v\|_{\alpha}\leq 1}\|f^{\prime}(z;v)\|_{\beta}\ \leq\ \sup_{\|v\|_{\alpha}\leq 1}L^{(\alpha,\beta)}(f,X)\|v\|_{\alpha}\ =\ L^{(\alpha,\beta)}(f,X)\qed$ $$

###### Definition 23 .

Given $x\in X$, we say that $f$ is $C^{1}$ at $x$ if there exists an open neighbourhood $U$ of $x$ in $X$ such that $f$ is Fréchet-differentiable at each $y\in U$ and moreover, the function $y\mapsto J_{f}(y):U\to\mathbb{R}^{m\times n}$ is continuous.

We let $\operatorname{Diff}(f)\subseteq X$ denote the set of points $x\in X$ such that $f$ is Fréchet-differentiable at $x$ and we let $\operatorname{Diff}^{1}(f)$ denote the set of points $x\in X$ such that $f$ is $C^{1}$ at $x$. Clearly $\operatorname{Diff}^{1}(f)\subseteq\operatorname{Diff}(f)$.

Here is the main fact we will use about definable functions:

###### Lemma 24 .

If $f:X\to\mathbb{R}^{m}$ is definable, then:

- 1.
$\operatorname{Diff}(f)$ and $\operatorname{Diff}^{1}(f)$ are definable
- 2.
$\dim(X\setminus\operatorname{Diff}^{1}(f))<n$, and thus $X\setminus\operatorname{Diff}^{1}(f)$ is nowhere dense and has Lebesgue measure zero

###### Remark about proof.

(1) is an easy exercise in definability. (2) is nontrivial and follows from *Smooth Cell Decomposition* [65, 7.3.2]. Here the dimension $\dim$ is taken in the sense of definable sets in an o-minimal structure [65, 4.1] which agrees with and generalizes the usual notion of *dimension* for $C^{1}$ manifolds, at least in the case that the manifold is presented as an embedded submanifold of $\mathbb{R}^{n}$ and the underlying set of the manifold is a definable subset of $\mathbb{R}^{n}$.
The claim about Lebesgue measure follows from the fact that for any connected embedded $C^{1}$ submanifold $M\subseteq\mathbb{R}^{n}$ (definable or not), if $\dim M<n$, then $M$ has Lebesgue measure zero.
∎

###### Definition 18 .

###### Lemma 19 .

###### Proof.

###### Definition 20 .

###### Lemma 21 .

###### Lemma 22 .

###### Proof.

###### Definition 23 .

###### Lemma 24 .

###### Remark about proof.

### A supremum of Jacobians bound a difference quotient

The lemma here is routine although we show how to use the Riemann integral instead of the Lebesgue integral when we are in the definable setting. Here is the setup:

- •
Fix distinct points $x,y\in\mathbb{R}^{n}$ such that $[x,y]\subseteq X$
- •
let $L:=[x,y]\setminus\{x,y\}$ be the “open” line segment from $x$ to $y$
- •
$f:X\to\mathbb{R}^{m}$ is $(\alpha,\beta)$-Lipschitz
- •
$f$ is either $C^{1}$ on $L$, or definable and Fréchet-differentiable on $L$

###### Lemma 25 .

In the above setup we have:

$$ $\|f(y)-f(x)\|_{\beta}\ \leq\ \sup_{z\in L}\|J_{f}(z)\|_{\alpha,\beta}\cdot\|y-x\|_{\alpha}$ $$

###### Proof.

First define the function:

$$ $h\ :\ [0,1]\to\mathbb{R}^{m},\quad t\ \mapsto\ f((1-t)x+ty)$ $$

We know that:

- •
$h$ is continuous
- •
$h$ is differentiable on $(0,1)$ with derivative $h^{\prime}(t)=J_{f}((1-t)x+ty)(y-x)$, computed via the chain-rule for Fréchet-differentiable functions
- •
in particular, by Lemma [22](https://arxiv.org/html/2509.15368v1#Thmthm22), $h^{\prime}$ is bounded because $f$ is Lipschitz over the compact set $[x,y]$; c.f. Lemma [17](https://arxiv.org/html/2509.15368v1#Thmthm17)
- •
on $(0,1)$, $h^{\prime}$ is continuous at all but finitely many points: by assumption either $f$ is $C^{1}$, or if $f$ is definable then this follows by the *Monotonicity Theorem* [65, 3.1.2] (in fact, $h^{\prime}$ is actually continuous on $(0,1)$ by [73, 5.7])

Next, define the function:

$$ $g\ :\ [0,1]\to\mathbb{R}^{m},\quad t\ \mapsto\ g(t)\ :=\ \begin{cases}J_{f}((1-t)x+ty)(y-x)&\text{if $t\in(0,1)$}\\ 0&\text{if $t=0,1$}\end{cases}$ $$

Then $g$ is bounded and continuous at all but finitely many points, hence $g$ is Riemann integrable.
Moreover, $h^{\prime}(t)=g(t)$ on $(0,1)$ and so by the *Fundamental Theorem of Calculus* [74, 34.1] we have:

$$ $\textstyle f(y)-f(x)\ =\ h(1)-h(0)\ =\ \int_{0}^{1}g(t)dt$ $$

Next, note that we have the following bound on $g(t)$, for $t\in(0,1)$, by Lemma [15](https://arxiv.org/html/2509.15368v1#Thmthm15):

$$ $\|g(t)\|_{\beta}\ =\ \|J_{f}((1-t)x+ty)(y-x)\|_{\beta}\ \leq\ \|J_{f}((1-t)x+ty)\|_{\alpha,\beta}\|y-x\|_{\alpha}\ \leq\ \sup_{z\in L}\|J_{f}(z)\|_{\alpha,\beta}\cdot\|y-x\|_{\alpha}$ $$

Moreover, the overall bound holds for all $t\in[0,1]$.
The main inequality now proceeds as follows:

$$ $\displaystyle\|f(y)-f(x)\|_{\beta}\$ $\displaystyle=\ \textstyle\|\int_{0}^{1}g(t)dt\|_{\beta}$ $\displaystyle\leq\ \textstyle\int_{0}^{1}\|g(t)\|_{\beta}dt\quad\text{by Lemma~\ref{norm_integral_triangle_inequality}}$ $\displaystyle\leq\ \textstyle\int_{0}^{1}\sup_{z\in L}\|J_{f}(z)\|_{\alpha,\beta}\cdot\|y-x\|_{\alpha}dt$ $\displaystyle=\ \sup_{z\in L}\|J_{f}(z)\|_{\alpha,\beta}\cdot\|y-x\|_{\alpha}\qed$ $$

The following is now immediate from Lemmas [22](https://arxiv.org/html/2509.15368v1#Thmthm22) and [25](https://arxiv.org/html/2509.15368v1#Thmthm25):

###### Corollary 26 (Lemma 2 ) .

If $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is $C^{1}$ and $(\alpha,\beta)$-Lipschitz over an open convex set $X$, then:

$$ $L^{(\alpha,\beta)}(f,X)\ =\ \sup_{x\in X}\|J_{f}(x)\|_{\alpha,\beta}$ $$

In the case that $f$ is definable, then we may weaken the $C^{1}$ assumption in Corollary [26](https://arxiv.org/html/2509.15368v1#Thmthm26) to Fréchet-differentiable and the same argument works; although in this case, this statement will be superseded by Lemma [33](https://arxiv.org/html/2509.15368v1#Thmthm33) below.

###### Lemma 25 .

###### Proof.

###### Corollary 26 (Lemma 2 ) .

### The Clarke Jacobian

In this subsection we assume:

- •
$f:X\to\mathbb{R}^{m}$ is locally $(\alpha,\beta)$-Lipschitz

###### Definition 27 .

[75, §2.6]
Define the Clarke Jacobian $J_{f}^{c}$ of $f$ over $X$ to be the set-valued map:

$$ $J_{f}^{c}\ :\ X\rightrightarrows\mathbb{R}^{m\times n},\quad z\ \mapsto\ J_{f}^{c}(z)\ :=\ \operatorname{conv}\{\lim_{j\to\infty}J_{f}(z_{j}):z_{j}\to z,z_{j}\in\operatorname{Diff}(f)\}$ $$

The following is immediate from the definition:

###### Lemma 28 .

If $x\in\operatorname{Diff}(f)$, then $\{J_{f}(x)\}\subseteq J_{f}^{c}(x)$; moreover, if $f$ is $C^{1}$ at $x$ then equality holds.

Note that if $f$ is definable, then Lemma [24](https://arxiv.org/html/2509.15368v1#Thmthm24) guarantees that $\dim(X\setminus\operatorname{Diff}(X))<n$ and thus $X\setminus\operatorname{Diff}(f)$ has Lebesgue measure zero. The general case is handled by:

###### Lemma 29 (Rademacher) .

[76]
The set $X\setminus\operatorname{Diff}(f)\subseteq\mathbb{R}^{n}$ has Lebesgue measure zero.

###### Lemma 30 .

For every $x\in X$, $J_{f}^{c}(x)$ is nonempty, compact, and convex.

###### Proof.

Convexity is clear and compactness follows from the fact that lipschitz functions have bounded Jacobian (Lemma [22](https://arxiv.org/html/2509.15368v1#Thmthm22)). Nonemptiness follows from Rademacher’s Theorem.
∎

It is also convenient to consider the following “variant” of $J_{f}^{c}$; suppose $N\subseteq X$ has Lebesgue measure zero and define:

$$ $J_{f}^{c,N}\ :\ X\rightrightarrows\mathbb{R}^{m\times n},\quad z\ \mapsto\ J_{f}^{c,N}(z)\ :=\ \operatorname{conv}\{\lim_{j\to\infty}J_{f}^{c}(z_{j}):z_{j}\to z,z_{j}\in\operatorname{Diff}(f)\setminus N\}$ $$

###### Lemma 31 (Warga) .

[77, Theorem 4]
For any set $N\subseteq X$ of Lebesgue measure zero, we have $J_{f}^{c,N}=J_{f}^{c}$.

###### Exercise .

Assuming $f$ and $N$ are definable, give a proof of Lemma [31](https://arxiv.org/html/2509.15368v1#Thmthm31) which does not use measure theory (use the fact that $\dim N<n$).

###### Definition 27 .

###### Lemma 28 .

###### Lemma 29 (Rademacher) .

###### Lemma 30 .

###### Proof.

###### Lemma 31 (Warga) .

###### Exercise .

### The path lemma

Here is the setup:

- •
$X\subseteq\mathbb{R}^{n}$ is a definable open convex set

###### Lemma 32 (Path Lemma) .

Suppose $x,y\in X$ and $B\subseteq\mathbb{R}^{n}$ is a definable set such that $\dim B<n$.
For every $\varepsilon>0$, there exists $k\geq 0$ and points $x_{0}=x,x_{1},\ldots,x_{k},x_{k+1}=y$ in $X$ such that:

- •
$\sum_{0\leq i\leq k}\|x_{i+1}-x_{i}\|_{\alpha}-\|y-x\|_{\alpha}\leq\varepsilon$, and
- •
$\{(1-t)x_{i}+tx_{i+1}:t\in(0,1)\}\cap B=\varnothing$ for each $i=0,\ldots,k$

###### Proof.

Let $v=(x+y)/2$ denote the midpoint between $x$ and $y$, and consider the definable set:

$$ $P\ :=\ \{v+w:\langle w,y-x\rangle=0\}\cap X\ \subseteq\ \mathbb{R}^{n}$ $$

So $P$ is the intersection of $X$ with the affine space passing through the midpoint $v$ and orthogonal to the segment $y-x$; it follows $\dim P=n-1$ since $X$ is open. We want to show that there are enough points of $P$ which are arbitrarily close to $v$ such that the pair of line segments $[x,z]$ and $[z,y]$ each have finite intersection with $B$. For this, we can consider the “bad” points of $P$:

$$ $P_{1}\ :=\ \{z\in P:\dim(([x,z]\cup[z,y])\cap B)=1\}$ $$

Then $P_{1}$ is a definable set by *Definability of dimension* [65, 4.1.5]; it suffices to show that $\dim P_{1}<n-1$. For this, first trim the set $B$ down:

$$ $B^{\prime}\ :=\ B\cap\bigcup_{z\in P_{1}}[x,z]\cup[z,y]$ $$

and consider the definable surjection:

$$ $f\ :\ B^{\prime}\to P_{1},\quad b\ \mapsto\ f(b)\ :=\ \text{the unique $z\in P_{1}$ such that $b\in[x,z]\cup[z,y]$}$ $$

Note that by construction we have:

$$ $P_{1}\ =\ \{z\in P_{1}:\dim f^{-1}(z)=1\}$ $$

and thus by the *Dimension Formula* [65, 4.1.6(ii)] we have:

$$ $1+\dim P_{1}\ =\ \dim f^{-1}[P_{1}]\ =\ \dim B^{\prime}\ <\ n$ $$

and thus $\dim P_{1}<n-1$.
∎

Note: the lemma is still true without assuming that $X$ is definable.

###### Lemma 32 (Path Lemma) .

###### Proof.

### A special case of the main theorem

###### Lemma 33 .

If $f:X\to\mathbb{R}^{m}$ is definable, then:

$$ $L^{(\alpha,\beta)}(f,X)\ =\ \sup_{x\in\operatorname{Diff}(f)}\|J_{f}(x)\|_{\alpha,\beta}$ $$

###### Proof.

Set $L_{0}:=L^{{}^{(\alpha,\beta)}}(f,X)$ and $L_{1}:=\sup_{x\in\operatorname{Diff}(f)}\|J_{f}(x)\|_{\alpha,\beta}$. The inequality $L_{0}\geq L_{1}$ is clear by Lemma [22](https://arxiv.org/html/2509.15368v1#Thmthm22). To show $L_{0}\leq L_{1}$, we may assume that $L_{1}$ is finite. Let $x,y\in X$ be arbitrary distinct points and let $\varepsilon>0$ be arbitrary; it suffices to show:

$$ $\frac{\|f(y)-f(x)\|_{\beta}}{\|y-x\|_{\alpha}}\ \leq\ L_{1}+\varepsilon$ $$

Set $\varepsilon^{\prime}:=\varepsilon\|y-x\|_{\alpha}/L_{1}$ and apply the Path Lemma [32](https://arxiv.org/html/2509.15368v1#Thmthm32) to obtain $k\geq 0$, points $x_{0}=x,x_{1},\ldots,x_{k},x_{k+1}=y$ in $X$ such that:

- •
$\sum_{0\leq i\leq k}\|x_{i+1}-x_{i}\|_{\alpha}-\|y-x\|_{\alpha}<\varepsilon^{\prime}$, and
- •
$\{(1-t)x_{i}+tx_{i+1}:t\in(0,1)\}\cap B=\varnothing$ for each $i=0,\ldots,k$, where $B:=X\setminus\operatorname{Diff}(f)$; note that $\dim B<n$.

Then we have:

$$ $\displaystyle\|f(y)-f(x)\|_{\beta}\$ $\displaystyle\leq\ \sum_{0\leq i\leq k}\|f(x_{i+1})-f(x_{i})\|_{\beta}\quad\text{by Triangle inequality}$ $\displaystyle\leq\ \sum_{0\leq i\leq k}L_{1}\|x_{i+1}-x_{i}\|_{\alpha}\quad\text{by Lemma~\ref{basic_lemma_Jacobian_bounds_diff_quot}}$ $\displaystyle<\ L_{1}\|y-x\|_{\alpha}+L_{1}\varepsilon^{\prime}\quad\text{by choice of $x_{i}$'s}$ $$

Thus:

$$ $\frac{\|f(y)-f(x)\|_{\beta}}{\|y-x\|_{\alpha}}\ <\ L_{1}+\frac{L_{1}\varepsilon^{\prime}}{\|y-x\|_{\alpha}}\ =\ L_{1}+\varepsilon\qed$ $$

As an application, can now prove Theorem [3](https://arxiv.org/html/2509.15368v1#Thmthm3) in the case that $f$ is definable:

###### Corollary 34 .

If $f$ is definable, then:

$$ $L^{(\alpha,\beta)}(f,X)\ =\ \sup_{x\in X,G\in J_{f}^{c}(x)}\|G\|_{\alpha,\beta}$ $$

###### Proof.

Immediately follows from Lemmas [33](https://arxiv.org/html/2509.15368v1#Thmthm33) and [12](https://arxiv.org/html/2509.15368v1#Thmthm12).
∎

###### Lemma 33 .

###### Proof.

###### Corollary 34 .

###### Proof.

### Good maps and the equivalence lemma

In this subsection, to simplify notation, given a set-valued map $D:X\rightrightarrows\mathbb{R}^{m\times n}$, we set:

$$ $s(D)\ :=\ \sup_{x\in X,G\in D(x)}\|G\|_{\alpha,\beta}$ $$

###### Definition 35 .

We say a set-valued map $D:X\rightrightarrows\mathbb{R}^{m\times n}$ is good for $f$ if:

- •
$D(x)\subseteq J_{f}^{c}(x)$ for every $x\in X$, and
- •
$D(x)$ is nonempty for almost every $x\in X$

###### Example 36 .

Here are the two main examples of good maps for $f$:

- •
the full Clarke Jacobian $J_{f}^{c}:X\rightrightarrows\mathbb{R}^{m\times n}$ is good for $f$
- •
the usual Jacobian:
$J_{f}\ :\ X\rightrightarrows\mathbb{R}^{m\times n},\quad x\ \mapsto\ J_{f}(x)\ :=\ \begin{cases}\{J_{f}(x)\}&\text{if $x\in\operatorname{Diff}(f)$}\\
\varnothing&\text{otherwise}\end{cases}$
is also good for $f$, by Rademacher’s Theorem [29](https://arxiv.org/html/2509.15368v1#Thmthm29)

If $D_{0},D_{1}$ are good maps for $f$, then we define:

$$ $D_{0}\ \leq\ D_{1}\quad:\Longleftrightarrow\quad D_{0}(x)\ \subseteq\ D_{1}(x)\quad\text{for every $x\in X$}$ $$

The binary relation $\leq$ endows the collection of all good maps for $f$ with the structure of a *partial order*; in fact, this partial order is always a *join-semilattice* (with join operation given by the union $D_{0}\vee D_{1}:=D_{0}\cup D_{1}$). The following is obvious:

###### Lemma 37 .

If $D_{0}\leq D_{1}$ are good maps for $f$, then $s(D_{0})\leq s(D_{1})$.

Under the assumption of definability, good maps have the following property:

###### Lemma 38 .

If $f$ is definable and $D$ is good for $f$, then $D(x)=\{J_{f}(x)\}$ for almost every $x\in X$.

###### Proof.

Since $f$ is $C^{1}$ at $x$ for almost every $x\in X$ by Lemma [24](https://arxiv.org/html/2509.15368v1#Thmthm24), it follows that $J_{f}^{c}(x)=\{J_{f}(x)\}$ for almost every $x\in X$ by Lemma [28](https://arxiv.org/html/2509.15368v1#Thmthm28), and thus $D(x)=\{J_{f}(x)\}$ for almost every $x\in X$ by the definition of *good map*.
∎

It follows immediately that when $f$ is definable, then the partial order $\leq$ is a lattice:

###### Lemma 39 .

If $f$ is definable and $D_{0},D_{1}$ are good maps for $f$, then $D:=D_{0}\cap D_{1}$ is a good map for $f$.

###### Lemma 40 (Equivalence lemma) .

If $f$ is definable and $D_{0},D_{1}$ are two set-valued maps which are good for $f$, then $s(D_{0})=s(D_{1})$.

###### Proof.

It suffices to show that $s(D)=s(J_{f}^{c})$, where $D$ is an arbitrary good map for $f$. Define $D^{\prime}:=D\cap\{J_{f}(x)\}$, which is also good map for $f$ by Lemma [39](https://arxiv.org/html/2509.15368v1#Thmthm39) and Example [36](https://arxiv.org/html/2509.15368v1#Thmthm36); it suffices to show $s(D^{\prime})=s(J_{f}^{c})$, by Lemma [37](https://arxiv.org/html/2509.15368v1#Thmthm37). To set notation, consider:

- •
$S:=\operatorname{domain}(D^{\prime})=\{x\in X:D^{\prime}(x)\neq\varnothing\}$, so $S\subseteq\operatorname{Diff}(f)$
- •
$N:=X\setminus S$, so $N$ has Lebesgue measure zero
- •
$J:=J_{f}|_{S}$; thus $J:S\to\mathbb{R}^{m\times n}$ fits the setup of Lemma [12](https://arxiv.org/html/2509.15368v1#Thmthm12)
- •
thus we may further define $D_{J}:X\rightrightarrows\mathbb{R}^{m\times n}$ to be $D_{J}(x):=\{\lim_{i\to\infty}J(x_{i}):x_{i}\to x,x_{i}\in S\}$

Then:

$$ $\displaystyle s(D^{\prime})\$ $\displaystyle=\ \sup_{x\in S}\|J(x)\|_{\alpha,\beta}\quad\text{by definition}$ $\displaystyle=\ \sup_{x\in X,G\in\operatorname{conv}(D_{J}(x))}\|G\|_{\alpha,\beta}\quad\text{by Lemma~\ref{sup_equivalence_template}}$ $\displaystyle=\ s(J_{f}^{c,N})\quad\text{by definition}$ $\displaystyle=\ s(J_{f}^{c})\quad\text{by Lemma~\ref{Clarke_Jacobian_blind_null}}\qed$ $$

###### Definition 35 .

###### Example 36 .

###### Lemma 37 .

###### Lemma 38 .

###### Proof.

###### Lemma 39 .

###### Lemma 40 (Equivalence lemma) .

###### Proof.

### The main theorem

We may now prove the main Theorem [6](https://arxiv.org/html/2509.15368v1#Thmthm6):

###### Theorem 41 .

If $f$ is definable and $D$ is good for $f$, then:

$$ $L^{(\alpha,\beta)}(f,X)\ =\ \sup_{x\in X,G\in D(x)}\|G\|_{\alpha,\beta}$ $$

###### Proof.

By the Equivalence Lemma [40](https://arxiv.org/html/2509.15368v1#Thmthm40) it suffices to prove the stated equality for at least one $D$ which is good for $f$.
Let $D$ be the good map $\{J_{f}(x)\}$ (cf. Example [36](https://arxiv.org/html/2509.15368v1#Thmthm36));
then the equality holds for this $D$ by Lemma [33](https://arxiv.org/html/2509.15368v1#Thmthm33).
∎

###### Theorem 41 .

###### Proof.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: Please see weaknesses.
soundness: 3
strengths: The paper is written very well. The results are also clearly presented.

The results on binary MNIST clearly depict the improvements over LipSDP and LipMDP.

I am glad that the paper does not limit itself to simple two layer neural networks and instead, in Figure 5, compares with the aforementioned methods across a number of hidden layers.
summary: This paper presents a novel method for estimating the Lipschitz constant in neural networks, addressing the known scaling limitations of methods like LipMIP and LipSDP. The core contribution is Algorithm 3 in the paper, which frames the problem in an infinity-armed bandit setting without commonly considered assumptions, using an Upper-Confidence-Bound (UCB) policy to partition the input domain and concentrate samples in useful regions. The paper compares with LipSDP and LipMDP on RELU-activation based neural networks trained on synthetic data and on binary MNIST.
weaknesses: A potential related work missing: In [1], a extreme value analysis method is used to compute Lipschitz constants and could be relevant to this paper.

[1] Improving Neural Network Robustness via Persistency of Excitation, Sridhar et al, ACC 22

Scale: I am uncertain how easily this method can scale up to neural networks in use today from imagent scale models to LLMs, VLMs, and VLAs. Perhaps the authors can address the question of further scale?

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: Based on the identified weaknesses, I would appreciate clarification from the authors on the following points:
1: Could the authors discuss how the key hyperparameters (e.g., exploration constant c and subdivision threshold) affect the performance of the proposed method? Providing sensitivity analysis or practical guidance on selecting these values would help assess the robustness of the approach.

2: Could the authors analyze or comment on the computational efficiency of the method, particularly in high-dimensional settings?

3: While the focus is theoretical, demonstrating the method on more diverse datasets or tasks (e.g., larger vision benchmarks, NLP models, or time-series data) would strengthen the empirical validation. Can the authors provide results on additional datasets or comment on expected performance in such settings?
soundness: 3
strengths: 1: The authors propose a non-uniform sampling strategy based on UCB scores. This approach allows the sampling process to better adapt to different regions of the input space compared to uniform sampling.

2: The authors provide solid theoretical analysis demonstrating that their algorithm is more dynamic and consistent.
summary: In this paper, the authors investigate the connection between generalized derivatives and local continuity, and further propose an algorithm for estimating the modulus of local continuity. Building on existing methods for evaluating local Lipschitz continuity, they extend the formulation to more general notions of local continuity. The authors also partition the input space of dimension 
$ d $ into $k^{d} subregions to support structured sampling. Finally, they incorporate a non-uniform UCB-based sampling strategy that concentrates samples in regions with higher estimated importance. The paper provides both theoretical analysis and empirical results demonstrating that the proposed approach yields more consistent and accurate estimates.
weaknesses: 1: The proposed non-uniform sampling method relies heavily on hyperparameters such as the exploration coefficient "c" and the subdivision threshold. A detailed discussion or sensitivity analysis of these parameters would be important to assess the robustness and practical usability of the method.

2: For high-dimensional input spaces, partitioning the domain into more subregions may introduce significant computational overhead. The paper does not address the scalability implications of this partitioning strategy in high-dimensional settings.

3:Although the paper focuses primarily on theoretical contributions, evaluating the method on larger datasets or across different modalities, such as natural language processing or time-series data, would strengthen the empirical evidence and demonstrate broader applicability.

---

confidence: 3
contribution: 1
initial_rating: 2
presentation: 2
questions: - Can you clearly highlight the theoretical contribution that is unique to this work?
- Does the method scale to larger architectures (e.g., Transformers, ViTs, LLMs)?  
- Are there new bottlenecks when moving to large-scale models?
- Can we show measurable improvements in robustness-aware training or certified robustness?  
- Does the approach improve performance on standard certification benchmarks? 
- What is the computational complexity relative to baselines?
soundness: 2
strengths: The topic is relevant to robustness and verification. The idea of casting Lipschitz estimation as a pure-exploration bandit problem is natural and can reduce unnecessary sampling in flat regions. The comparison with LipSDP/LipMIP is appreciated, and the experimental section shows improvements in some settings. The theoretical discussion linking Clarke Jacobians and definability is mathematically sound.
summary: The paper proposes non-uniform stochastic sampling methods, inspired by UCB bandit policies, to estimate local moduli of continuity (Lipschitz constants) of neural networks. The authors revisit the connections between generalized derivatives and Lipschitz constants in the o-minimal framework, claiming improved sample efficiency and scalability over standard uniform sampling, LipMIP, and LipSDP.
weaknesses: The novelty is limited. The core contribution is an adaptation of standard UCB sampling to the well-known stochastic Lipschitz estimation baseline. The theoretical section is lengthy but does not yield new guarantees of interest to the ML community beyond established facts (consistency, asymptotic unbiasedness, and asymptotic optimality from standard bandit theory). The o-minimal component feels disconnected from the algorithmic contribution and is unlikely to be valued by ICLR readers.

Experiments are insufficient to justify significance. Evaluations are conducted on small MLPs and a binary MNIST setting. There is no evidence that the method scales to modern architectures (CNNs, Transformers, diffusion models) or yields practical benefit in certified training or downstream robustness tasks. Reported gains, while present, remain modest. The computational overhead of the adaptive strategy is not fully analyzed.

The paper lacks a compelling narrative demonstrating why this improvement matters for robustness, certified training, or verification workflows in practice. As written, it reads as an incremental technical refinement rather than a contribution that changes understanding or capabilities.


Decision: Reject