acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Sample Approximations of (Local) Moduli of Continuity

Abstract

The modulus of local (Lipschitz) continuity of a neural network is a basic quantitative measure of its robustness. Exact mixed-integer methods and relaxation-based semidefinite upper bounds do not scale beyond small networks, while sampling gradient norms at random inputs is widely used as a lower bound, but has received little analysis. We revisit the connection between generalized derivatives and moduli of local continuity for networks definable in an o-minimal structure, showing that any dense-domain selection of the Clarke Jacobian recovers the modulus, and we analyze sampling estimators rigorously: they are almost surely lower bounds and, under an explicit exploration condition that uniform sampling satisfies and that our adaptive variant satisfies once its exploration bonus is bounded below, consistent, asymptotically unbiased, and exact after finitely many samples for ReLU networks; moreover, no adaptive black-box point-query scheme improves upon uniform sampling by more than a constant factor uniformly over all networks. Such lower bounds do not certify robustness; they measure the looseness of certified upper bounds and exhibit concrete sensitive inputs. We then present a non-uniform sampling variant based on upper-confidence-bound policies over an adaptively refined partition of the input domain, whose gains depend on the structure of the gradient field, and evaluate it against LipMIP, LipSDP, and uniform sampling, including on a small transformer to which the former two do not apply.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
moduli of local continuity, estimation, stochastic sample approximation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_FdmZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper mainly proposes a theorem showing that, for definable networks, the Lipschitz constant can be recovered from any selection of the Clarke Jacobian on a dense set, which justifies lower-bound estimation of the Lipschitz constant of a neural network by sampling the gradient. The authors also prove that sampling gives an almost sure lower bound that converges almost surely to the true Lipschitz constant under an exploration condition. Lastly, they propose a UCB-like adaptive approach to improve the sampling efficiency. They compare their approach with an exact method (LipMIP) and a certified upper bound (LipSDP) on MNIST, and compare uniform and adaptive sampling on a tiny transformer.

Critical strengths
  • As stated by the authors, although estimation methods based on gradient sampling are widely used, they have received little attention and rigorous study.
  • Theorem 4.2 relaxes the classical conditions to ones that are compatible with most of the common neural networks used in the literature.
  • The counterexample (Example 4.4) shows the necessity of the definability assumption.
  • The authors clearly acknowledge the different limitations of the approach.
Critical weaknesses

The main weaknesses of the paper concern the evaluation of the proposed algorithms and the importance of the contribution:

  • Theorem 4.2, which is the main result of the paper, is somewhat limited. In particular, even if it is closer to the real application case than Theorem 2.2, it does not cover gradients computed by automatic differentiation, as acknowledged by the authors.
  • Algorithm 3 is an incremental contribution, close to other hierarchical optimistic algorithms, but it is not compared with them. Moreover, the algorithm is evaluated with σ0=0\sigma_0 = 0, whereas the consistency analysis requires σ0>0\sigma_0 > 0. On MNIST, Algorithm 3 brings no improvement over uniform sampling (same or lower values at about twice the runtime).
  • Scalability is evaluated mostly in depth, with very narrow layers (at most 32 hidden units on MNIST). As the computational cost is tractable, tests with wider architectures such as [784, 512, 512, 2] would have been welcome. With such narrow networks, the number of linear regions is limited and the gradient landscape is not very complex.
Questions for authors
  • How does Algorithm 3 compare with the other methods cited by the authors (e.g., StoSOO, DIRECT)? This would help to evaluate the contribution of the proposed method.
  • It would also be interesting to evaluate Algorithm 3 with σ0>0\sigma_0 > 0 on ReLU networks (where starvation can occur), and then with smooth activations such as GELU.
  • What is the accuracy of the networks tested on MNIST? What are the results with wider architectures?
  • Bound-propagation methods compute certified upper bounds on the local ℓ∞\ell_\infty Lipschitz constant and scale far beyond LipMIP and LipSDP (e.g., Shi et al., "Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation", NeurIPS 2022, available in auto_LiRPA). How do the sampled lower bounds compare with these upper bounds, in particular on the deeper and wider networks where LipMIP does not finish?
3 comments
AuthorsOpenReview ↗

Thank you! (Part 1/2)

We thank the reviewer for a generous assessment, and for requests that are both precise and practicable.

W1. This is correct, and no theorem of that deterministic form could hold: Remark 4.5 recalls a function f≡0f\equiv0 at which automatic differentiation returns nonzero matrices at certain points. What the algorithms require is rather different, and it does cover automatic differentiation. The output of automatic differentiation agrees with the ordinary Jacobian outside a null set (Bolte and Pauwels, 2020; 2021). Inputs drawn from a density, or drawn uniformly from a cell given the history of the sampling, avoid that set almost surely. The results of Appendix B therefore apply to automatic differentiation as modelled, each under its own hypotheses on sampling and exploration; in particular, consistency of the adaptive method still requires the positive floor of Proposition B.13. This is, of course, a statement in idealised real arithmetic, not a bound on floating-point error. The revision states it after Remark 4.5 and in contribution (ii).

W2a. We agree that Algorithm 3 belongs to this family, as Section 2.3 records, and we do not present it as the main contribution of the paper. So far as we know, the quantitative regularity assumptions on which the guarantees for HOO, StoSOO and DIRECT rest have not been established for the gradient-norm field of a ReLU network, which is piecewise constant with jumps. The comparison must therefore be empirical, and we distinguish their analyses from our guarantee of persistent exploration.

Algorithm 3 differs from these methods in three respects:

  • it scores a cell by the maximum of its samples, as extreme bandits do;
  • it scales the bonus by the empirical spread;
  • it subdivides only at geometrically spaced times, which keeps the number of cells of order log⁡t\log t; this is what the proof of Proposition B.13 uses.

For ReLU networks, plain gradient ascent on ∥Jf(x)∥\|J_f(x)\| is uninformative, since its gradient vanishes almost everywhere; for smooth networks it would be a sensible further comparator.

AuthorsOpenReview ↗

Thank you! (Part 2/2)

W2b. This is a fair criticism, and Section 3.3 and Remark B.14 acknowledge it. We should add that smooth activations do not by themselves rule out a zero empirical spread, since the gradient-norm objective may have plateaux; the floor is therefore needed for GELU networks too. We are running the experiments to compare these. If they do not finish by tomorrow, we hope to be able to replace the supplementary material for the coming week, yet (?).

W2c. We agree: on MNIST, Algorithm 3 shows no demonstrated advantage for its additional cost, and the paper says as much. One structural observation may go some way to explaining this. With 500 000 samples and partition step 2 there are about 19 halvings, so each cell is refined along at most 19 of the 784 coordinates. We have not profiled where the additional time is spent; on the transformer, the measured overhead was 1.1%.

W3. We agree that wider networks are a more demanding test. Theorem B.16 ties the difficulty of sampling to the volume of the near-maximal set rather than to width as such, so the effect of width is an empirical question.

Q1–Q3. Please see W2a, W2b and W3 respectively.

Q4. We thank the reviewer for the reference. Shi et al. (NeurIPS 2022) is now cited in Section 2.3 as the scalable certified counterpart to our lower bounds. We are running the experiments to compare these.

Thank you for the detailed response. I will keep my current score, which is already positive.

Reviewer_3KEoOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper rigorously analyzes gradient-sampling methods for estimating local Lipschitz constants of neural networks, establishing their lower-bound, consistency, and finite-sample properties while characterizing fundamental limits of adaptive sampling. It also proposes an adaptive UCB-based sampling method and evaluates it against uniform sampling and certified methods such as LipMIP and LipSDP, including on transformer architectures.

Critical strengths
  1. A theoretic sound method to obtain potentially tight lower Lipschitz bound.
  2. It is nice that it can be applied to Lipschitz constant estimation of a general model architecture (e.g., transformer) over a convex domain.
Critical weaknesses
  1. The comparison with LipSDP is not precise, as the two methods serve different purposes: the proposed method provides a lower bound on the Lipschitz constant, whereas LipSDP provides a certified upper bound. Such a comparison would be more informative if the experimental results could demonstrate that the proposed method yields a tighter estimate of the true Lipschitz constant. However, this may be difficult to establish in practice, since computing the exact Lipschitz constant of a neural network is generally computationally intractable (and can be NP-hard).
  2. For small datasets (e.g., MNIST and CIFAR) and small-scale MLP/CNN architectures, estimating the model's Lipschitz constant may be of somewhat limited practical significance, given recent progress in constructing large-scale (with millions or even billions of parameters) Lipschitz-bounded neural networks with tight certified Lipschitz bounds and strong certified robustness [1,2]. In the experiments, the model for validation is quite small.
  3. The almost-sure lower-bound and consistency results appear to have limited practical significance, particularly since (r_t) is not guaranteed to decrease with the number of samples. A more practically relevant theoretical question is the sample complexity versus estimation accuracy?
  4. The experimental evaluation on transformers is rather limited. This is particularly important because applicability to transformer architectures could be a key advantage of the proposed method: most existing SDP-based certification methods do not readily extend to the attention mechanism and layer normalization. For the transformer, the layer normalization is not Lipschitz if the hidden unit is close to zero. The estimation results in Table 2 suggest the transformer is quite smooth. Are the hidden units far away from zero?
  5. In Fig. 5, why the Lipschitz constant from SA converges to 0?

Refs:

[1] Araujo et al. A unified algebraic perspective on lipschitz neural networks. ICLR 2023.

[2] Wang and Manchester. Direct parameterization of Lipschitz-bounded deep networks. ICML 2023.

Questions for authors

See the weakness.

6 comments
AuthorsOpenReview ↗

Response (1/2)

We thank the reviewer for the report and for the references.

W1. We agree that LipSDP and sampling answer different questions, and the revision now says so in the abstract, in contribution (iv), and at the start of the discussion of Table 1. The table also has a new column recording the role of each value. The comparison the reviewer has in mind, namely how close the sampled estimate comes to the true constant, is reported wherever the true constant is known:

  • where LipMIP finishes (Table 1), the sampled lower bounds lie within 0.06%, 4–5% and 32–33% of the exact constant, while LipSDP exceeds it by 35–36%;
  • in Figure 5, the sampled value coincides with the exact LipMIP value up to depth 3.

Where LipMIP times out, one can report only a bracket between the best lower and upper bounds. A wide bracket does not by itself reveal whether the upper bound is loose or the sampling weak, and we make no claim that sampling improves upon LipSDP.

W2. We are grateful for the references to [1] and [2], which are now cited in Section 2.3. We regard the two lines of work as complementary. Most networks in use, transformers in particular, are not constructed to be Lipschitz-bounded. For those that are, the certificate is a global bound, whereas a sampled lower bound on a given region shows at least how much of that budget the trained network actually uses there. Our estimators and our theory apply to such networks without change. [[TODO E4: if completed, "We have also added a wider MNIST network, described in our reply to Reviewer FdmZ."; otherwise delete this sentence.]] The difficulty of sampling is governed by the volume of the near-maximal set and by the cost of each derivative evaluation, and depth, width and input dimension may all affect both.

W3. We agree that consistency on its own is a weak guarantee, and the revision makes the quantitative results explicit.

For uniform sampling, Theorem B.16 gives exactly P(L−rt≥ε)=(1−p(ε))t\mathbb P(L-r_t\ge\varepsilon)=(1-p(\varepsilon))^t, where p(ε)p(\varepsilon) is the proportion, by volume, of inputs at which the norm of the Jacobian exceeds L−εL-\varepsilon. It follows (part 3) that an error below ε\varepsilon with probability at least 1−δ1-\delta is attained if and only if t≥ln⁡(1/δ)/ln⁡(1/(1−p(ε)))t\ge\ln(1/\delta)/\ln\bigl(1/(1-p(\varepsilon))\bigr). In particular, ln⁡(1/δ)/p(ε)\ln(1/\delta)/p(\varepsilon) samples suffice and (1−p(ε))ln⁡(1/δ)/p(ε)(1-p(\varepsilon))\ln(1/\delta)/p(\varepsilon) are necessary. Since p(ε)p(\varepsilon) is unknown in practice, this describes the difficulty of the problem rather than furnishing a stopping rule.

In the other direction, consider a family of four-neuron ReLU networks at fixed confidence. Theorem B.19 and the new Corollary B.20 show that on this family every black-box method using point queries needs a number of queries inversely proportional to the volume of the maximising region, whatever estimate it reports, and that uniform sampling attains this up to a constant factor. This is not an optimal rate in δ\delta, nor a rate for Algorithm 3 on any particular network.

As to rtr_t not being guaranteed to decrease: rtr_t is a running maximum, so it never decreases, and the error L−rtL-r_t never increases. What one cannot have is a rate independent of the network, and the results above show that no black-box method can supply one. The qualitative results also have a practical consequence: Remark B.14 shows that, without the floor σ0\sigma_0, Algorithm 3 can remain below LL indefinitely.

AuthorsOpenReview ↗

Response (2/2)

W4. With ϵ>0\epsilon>0, the standard layer normalisation γ⊙(x−μ)/σ2+ϵ+β\gamma\odot(x-\mu)/\sqrt{\sigma^2+\epsilon}+\beta is smooth and globally Lipschitz, with ∥D LN(x)∥2→2≤∥γ∥∞/σ2(x)+ϵ≤∥γ∥∞/ϵ,\|D\,\mathrm{LN}(x)\|_{2\to2}\le\|\gamma\|_\infty/\sqrt{\sigma^2(x)+\epsilon}\le\|\gamma\|_\infty/\sqrt\epsilon, so our assumptions are met. The quantity that matters is the centred variance σ2(x)\sigma^2(x) of the vector being normalised, rather than the size of any individual hidden unit; large learned gains γ\gamma matter as well.

We accept that the transformer experiment is a small proof of concept, with a single context and a four-coordinate slice of a single embedding. We are running a larger experiment and hope to add the results shortly.

W5. Each depth in Figure 5 corresponds to a different untrained network, not to a further iteration on the same one. The modulus decreases sharply with depth, and at large depths the values are hard to distinguish from zero on a linear axis. These small values reflect the networks rather than the estimator. Up to depth 3, the sampled values coincide with the exact values from LipMIP, and the certified upper bound from LipSDP decreases with depth as well. The caption now says so.

Thanks for the response.

  • W1. I do not think the percentage-based comparison is entirely fair. The proposed approach provides a lower bound, which naturally yields a lower percentage than an upper-bound method. Moreover, the SDP-based approach provides a global Lipschitz bound, whereas the proposed method estimates a local Lipschitz bound. It is okay to compare these two approaches; however, the claims and interpretation of the comparison should clearly reflect these differences.

Personally, I find the proposed approach appealing for two main reasons: local Lipschitz estimation and architecture independence. I am considering raising my score to 3 if experimental results on a moderately larger Transformer can be provided and the following question is adequately addressed.

  • Line 1804: All experiments were run on CPU. Could the authors explain why the proposed approach was not evaluated on GPU? I understand that the SDP-based approach may need to run on CPU due to the SDP solver. However, the proposed approach is sampling-based and appears naturally suited to GPU parallelization. If there is a technical reason why GPU acceleration is not applicable, it would be helpful to clarify it. Otherwise, I believe a comparison against a simple GPU-based lower-bound baseline is needed. For example:

    • Baseline (random sampling): At each iteration, sample a large batch of points xx and small random perturbations δ\delta, and estimate L^=∣f(x+δ)−f(x−δ)∣/(2∣δ∣)\hat{L}= |f(x+\delta)-f(x-\delta)|/(2|\delta|). The largest value observed across all samples and iterations can then be used as a lower bound.

For a fair computational comparison, this baseline could be implemented on GPU and run for the same wall-clock time as the proposed CPU-based method. This would help demonstrate whether the proposed sampling strategy provides a meaningful advantage over naive GPU-parallelized alternatives.

Reviewer_VPZXOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Understanding how a neural network's output can change under a small input perturbation is fundamental for evaluating robustness. The local Lipschitz constant within a region X measures the largest ratio of variation in outputs to variation in inputs between points in X. Any upper bound on this constant provides a loose certified robustness guarantee. Computing the exact local Lipschitz constant is often NP-hard. The central study of this article are principled lower-bounds to accompany known loose upper bounds of the local Lipschitz constants. As such the focus of this article is significantly removed from the practical considerations of adversarial robustness.

One way to measure the looseness for the Lipschitz constant upperbounds is to take samples of nearby inputs, record their Jacobian norms and take the maximum. Although this gives a lower bound on the Lipschitz constant, prior to this article, this approach wasnt accompanied with a formal characterization of tightness or approximation. Uniform sampling scales poorly with dimensions and hence the authors investigate the design and analysis of adaptive non-uniform sampling techniques.

To start: on an open convex region, the Lipschitz constant equals the supremum of the norms of matrices in the Clarke generalized Jacobian. At a nonsmooth point, this generalized Jacobian is the convex hull of limiting ordinary Jacobians from nearby differentiable points. The authors show that, for "definable" Lipschitz functions, we recover the same supremum using any dense subset. ReLU feedforward networks have been shown to satisfy the definability assumption, extensions of this idea also covers softmax and other normalization approaches. Hence, this machinery might present a framework for a unified analysis of estimating local Lipschitz constants.

From my understanding, definability matters because it rules out pathological cases where a derivative at one point is separated from nearby smooth derivatives. Continuity on the smooth regions then lets us take these approximations from any dense subset. This result while theoretically meaningful does not provide an algorithmic prescription for finding local Lipschitz constants which leads to a study of the sampling algorithms.

Uniform sampling presents a brute force attempt at measuring the local Lipschitz constant. For finitely many random samples. If p(epsilon) is the fraction of the input region where the derivative norm exceeds L minus epsilon, then N independent uniform samples miss that region with probability (1 - p(epsilon))^N. The region where the Jacobian norm is close to its supremum might have vanishingly small volume. The sampling based estimators generally cannot tell whether it has found that region or whether a larger value is still out there.

The adaptive method divides the input domain into boxes and samples from the box with the highest index. This index adds an exploration bonus to the largest value observed in the box, using the sample count and empirical variation. The method periodically splits promising boxes into smaller ones. The consistency guarantee requires a positive exploration floor. Otherwise, a box whose initial samples all have the same derivative norm could stop receiving attention. The experimental results are mixed: adaptation helps in some low-dimensional examples but may not necesarily improve over uniform sampling.

Critical strengths
  • As a researcher interested in certified robustness and measurement of sensitivity, I'm grateful to the authors for introducing me to new ideas (e.g. o-minimal structures, definable functions) that appear relevant. The field could benefit from this perspective to design newer algorithms and improved theoretical guarantees.

  • The analysis of the generalized Clark Jacobian was interesting. Recovering the actual limiting Jacobian matrices from any dense subset is stronger than recovering only their convex hull or the supremum of their norms. The proof approximates the entire matrix along one sequence, including derivatives at points outside the continuously differentiable regions. With the additional definability assumption, this seems to meaningfully extend the classical result that removing a set of measure zero leaves the Clarke generalized Jacobian unchanged. Here the role of the measure-zero set is replaced by sets whose complements are dense in the domain.

  • The sampling analysis presents a natural explanation: Convergence depends on the volume of the region where the derivative norm is close to its supremum, so eventual convergence may still require far more samples than is feasible in practical settings. The authors do clearly distinguish a sampled lower bound from the certified upper bound. They also acknowledge that the estimator cannot tell us when it is safe to stop.

  • I appreciate that the experiments report where the method fails as well as where it helps. Comparisons with exact constants on small networks show how close the estimates get. The difficulty of scalable estimation of local Lipschitz constants a fundamental challenge for the field of robustness and is not unique to this article.

Critical weaknesses

The writing style made it unnecessarily difficult for me to review this paper. The concerns below affect how easily readers can understand the contribution and therefore build on it!

  1. The abstract (lines 15–22) and contribution (ii) in the introduction pack several results into single sentences. Long qualifications interrupt the central claims, making it very hard to tell which assumptions are needed for which guarantees. I had to reread these passages and the full article repeatedly to parse these statements. Below I highlight the original text and a suggested rewrite that I believe is simpler (even if longer).
Original (lines 15–22)A potential rewrite
We revisit the connection between generalized derivatives and moduli of local continuity for networks definable in an o-minimal structure, showing that any dense-domain selection of the Clarke Jacobian recovers the modulus, and we analyze sampling estimators rigorously: they are almost surely lower bounds and, under an explicit exploration condition that uniform sampling satisfies and that our adaptive variant satisfies once its exploration bonus is bounded below, consistent, asymptotically unbiased, and exact after finitely many samples for ReLU networks; moreover, no adaptive black-box point-query scheme improves upon uniform sampling by more than a constant factor uniformly over all networks.We revisit the connection between generalized derivatives and local Lipschitz constants for networks definable in an o-minimal structure. We show that the constant can be recovered from any dense subset of the input domain, even when only one matrix from the Clarke Jacobian is selected at each point. We also analyze random sampling estimators. These are almost surely lower bounds. Under an explicit exploration condition, they are consistent and asymptotically unbiased; for ReLU networks, they become exact after finitely many samples. Uniform sampling satisfies this condition. Our adaptive variant also satisfies it when its exploration bonus is bounded below as required by the theorem. Finally, we establish a worst-case limitation: no adaptive black-box method using point queries can improve on uniform sampling by more than a constant factor uniformly over all networks.
  1. The final sentence of the abstract combines the method description with several comparisons. I think these comparisons stem from different questions. Uniform sampling is a comparative test for whether adaptation can improve the estimate. Exact LipMIP values lets us quantify the estimation error, while certified LipSDP upper bounds show the remaining gap between lower and upper bounds. Please separate these roles rather than list all three methods together.
Original (lines 24–28)A potential rewrite
We then present a non-uniform sampling variant based on upper-confidence-bound policies over an adaptively refined partition of the input domain, whose gains depend on the structure of the gradient field, and evaluate it against LipMIP, LipSDP, and uniform sampling, including on a small transformer to which the former two do not apply.We then propose a non-uniform sampling method. It adaptively divides the input domain into smaller regions and uses an upper-confidence-bound policy to choose where to sample. Its gains depend on the structure of the gradient field. We compare adaptive and uniform sampling to assess whether adaptation improves the sampled lower bound. Where available, exact constants from LipMIP let us measure the estimation error. Certified upper bounds from LipSDP show the remaining gap between the lower and upper bounds. We also evaluate the sampling methods on a small transformer, where LipMIP and LipSDP do not apply.
  1. Section 2 says, “Lemma A.13 extends this to the smooth locus of a definable function” (lines 81–82). Neither “smooth locus” nor “definable” has been explained at this point, so the reader cannot readily understand the scope of the extension. The smooth locus is defined as U_f in Appendix A, but this needs an explanation or direct reference at first use.

  2. Section 4 introduces “an o-minimal expansion of the real field” and says that “definable” means “definable in R with parameters” (lines 268–269). A reader who is unfamiliar with this technical machinery is still in the dark about what definable or o-minimal expansion means. I would argue that the ICLR venue is far more familar with the concept of induced matrix norms (which are explicitly defined in the appendix of this submission) vs the concept of o-minimal structure (for which the reader is directed to the appendix of a different arxiv article). I think this article could greatly benefit from background subsection that explicitly defines the technical machinery

  3. Section 4 requires a “nonempty definable open convex set” and a “definable (α, β)-Lipschitz function” (lines 270–271). But the norms are “not necessarily definable” (line 269), and neither D nor its domain is “required to be definable or measurable” (line 277). Although I can somewhat follow parts of the individual arguments, but these qualifications do not explain why there are so many subtly different qualificaitons.

  4. Example 4.4 does show failure without definability. However, it explains why the example is excluded with “as this would violate the Smooth Monotonicity Theorem 7.2.5 from Van den Dries (1998)” (lines 291–292). This sends the reader to another technical result without explaining the mechanism. Connecting the example to the smooth regions guaranteed by definability would make the reason clearer. That explanation should be central to the main discussion.

  5. Section 3.1 says that autograd gives an “element of the Clarke subdifferential (or rather of a conservative set-valued gradient field, cf. Bolte & Pauwels (2021))” (lines 179–180). I am not sure if these are the same mathematical objects? Also remark 4.5 refers to “selection Jacobians” and “a conservative mapping for f” (lines 298–299), again without introducing these concepts to the reader (at least the appendix should contain these explanations).

  6. The preceding sentence says that “Theorem 4.2 may no longer be true due to sporadic behavior on null sets” (lines 296–297). On first read, it seemed like a violation of the the theorem, but the issue here is the assumptions of the theorem might be violated by AD.

Questions for authors
  • Can the authors give a specific application where recovering the full set of limiting Jacobians helps beyond recovering its convex hull or largest norm?

  • Is the upper-confidence-bound (UCB) index a statistically valid upper bound on the largest derivative norm within a box, or a heuristic for choosing where to sample? Please make this distinction clear.

1 comment
AuthorsOpenReview ↗

Thank you!

We are grateful to the reviewer for so detailed a reading, and for proposing rewrites; they made the revision a good deal easier.

Abstract and contribution (ii). We have adopted the proposed rewrite of both passages of the abstract almost verbatim. Contribution (ii) now attaches each guarantee to its own hypotheses. The almost-sure lower bound requires only an oracle that agrees with the Jacobian almost everywhere, as automatic differentiation does, together with inputs drawn from densities. Consistency, asymptotic unbiasedness and, for ReLU networks, exactness after finitely many samples require in addition the exploration condition. Uniform sampling always satisfies that condition. Algorithm 3 satisfies it when its exploration bonus has a positive floor, by the specific argument of Proposition B.13. The worst-case limitation holds at fixed confidence, over a family of ReLU networks.

The roles of the baselines. These are now kept apart in the abstract (in the reviewer's words), in contribution (iv), and in the opening paragraph of the discussion of Table 1. The table itself has a new column recording whether each value is exact (LipMIP), a certified upper bound (LipSDP) or a sampled lower bound (Algorithms 1 and 3). Where LipMIP times out, the solver's bound and its best solution are reported separately.

Terms used before their definition. Section 2.1 now defines the smooth locus UfU_f where it first appears, as the open set of points near which ff is C1C^1, and refers forward to the new Section 2.2 for definability.

Background on o-minimality. We agree that a reader of ICLR should not have to consult the appendix of another paper. Section 2.2 now gives the geometric definition of an o-minimal structure, which requires no model theory. It indicates which layers are definable, and in which structure. It then states the two consequences on which our proofs rely: the monotonicity theorem; and the fact that the smooth locus is open and dense with a null complement, and that on it the Clarke Jacobian reduces to {Jf(x)}\{J_f(x)\}.

The many qualifications. The reviewer is right that, as stated, these looked somewhat arbitrary. A new paragraph in Section 4, "What each hypothesis is for", assigns each its role.

  • Definability of ff and XX provides the smooth locus, and allows a segment to be perturbed so as to cross its complement only finitely often.
  • Convexity keeps such segments within XX.
  • The norms enter only through continuity, the triangle inequality and duality, and so need not be definable.
  • DD need be neither definable nor measurable. The proof uses only the inclusion D(x)⊆Jfc(x)D(x)\subseteq J_f^c(x), which is a genuine constraint at nonsmooth points, and the density of the set on which DD is nonempty. Together these force D(x)={Jf(x)}D(x)=\{J_f(x)\} on a dense part of the smooth locus.

Example 4.4. The text now explains the mechanism rather than merely citing a theorem. In the example, f′f' takes values near ±1\pm1 on every interval, so ff is C1C^1 on no interval and the selection D≡0D\equiv0 is admissible everywhere. A definable ff, by contrast, is C1C^1 on finitely many open intervals covering R\mathbb R up to finitely many points. On these, Jfc={f′}J_f^c=\{f'\}, so a good DD must report f′f' on a dense set, and continuity then recovers sup⁡∣f′∣\sup|f'|. The proof of Theorem 4.2 is the nn-dimensional version of this argument.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to reviewers

We thank the reviewers for their careful and constructive reports. We have revised the paper accordingly; a version with the changes highlighted is included in the supplementary material, and the numbering of every theorem, figure and table cited in the reviews is unchanged. The two principal criticisms concern the presentation and the scope of our claims and experiments, and we have tried to meet both.

On presentation, the abstract now follows closely the rewrite that Reviewer VPZX was kind enough to propose, and the contributions are listed together with the hypotheses on which each depends. A new Section 2.2 gives a self-contained account of o-minimal structures. Section 2.1 distinguishes the three notions of derivative that appear in the paper: the ordinary Jacobian, the Clarke Jacobian, and the output of automatic differentiation. Appendix A.7 records the definitions of conservative mappings and selection derivatives.

On the scope of the theory, we now describe the UCB index for what it is, a heuristic allocation score rather than a confidence bound. The sample complexity of uniform sampling is stated explicitly (Theorem B.16, part 3). The worst-case limitation is now stated at its proper scope, namely at fixed confidence over a family of ReLU networks, and a new Corollary B.20 extends it from the sampled maximum to arbitrary estimators. Corollary A.29 sets out what the recovery of the limiting Jacobians adds to the recovery of their norms.

In the course of the revision we also found, and have corrected, two errors in Appendix B. In the counterexample of Remark B.14, the coefficient of the second ReLU should be −3-3 rather than −1-1. In the proof of Lemma B.9, the nested sequence should begin at a box of the initial partition rather than at X‾\overline X. Neither affects any stated result.

On the experiments, Table 1 now records whether each value is exact, an upper bound or a lower bound, and the caption of Figure 5 explains the small values at large depth.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.