Stochastic Sample Approximations of (Local) Moduli of Continuity

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.