- 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 , whereas the consistency analysis requires . 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 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 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
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.
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≡0 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:
For ReLU networks, plain gradient ascent on ∥Jf(x)∥ is uninformative, since its gradient vanishes almost everywhere; for smooth networks it would be a sensible further comparator.