Beyond Lipschitz: Data-Driven Robustness via Discrete Modulus of Continuity

Technical Summary: Beyond Lipschitz: Data-Driven Robustness via Discrete Modulus of Continuity

Problem Statement
The robustness of neural networks is traditionally quantified using local or global Lipschitz constants. While Lipschitz continuity provides theoretical guarantees against adversarial perturbations, the authors argue it is often an inadequate metric. It can be overly coarse, failing to capture nuanced, data-dependent behavior, or overly restrictive, potentially degrading the expressiveness and accuracy of the network. For instance, enforcing Lipschitz constraints on functions that are continuous but not Lipschitz (e.g., $\sqrt{x}$) or on functions where global Lipschitz bounds overestimate local variation (e.g., $\tanh(x)$) can hinder learning. Furthermore, existing methods for estimating Lipschitz constants often rely on specific architectures or lack tight theoretical guarantees. The paper identifies a need for a black-box, multi-scale notion of robustness that applies across architectures and is grounded in the data distribution rather than solely in model internals.

Methodology
The proposed framework centers on the Discrete Modulus of Continuity (DMOC), a data-driven, architecture-agnostic measure of regularity.

1. Theoretical Foundation:

   • The DMOC is a discrete approximation of the classical Modulus of Continuity (MOC), $\omega(f, t) = \sup_{d_X(x,x') \leq t} d_Y(f(x), f(x'))$.
   • Unlike the Lipschitz constant, which is the slope of the least homogeneous linear majorant of the MOC, the MOC (and by extension, the DMOC) provides a scale-dependent description of sensitivity. It encompasses Lipschitz, Hölder, and weaker regularities.
   • The authors define $\rho$-normalized seminorms, $|f|_\rho = \sup_{t>0} \rho(t)^{-1}\omega(f, t)$, to quantify regularity. The DMOC seminorm, $|f_N|_{\rho,N}$, is computed over a finite set of data sites $X_N$.

2. Convergence Theory:

   • The paper establishes convergence results for DMOC-induced seminorms. Theorem 2.4 provides explicit non-asymptotic bounds on the error $|f|_\rho - |f_N|_{\rho,N}$ in terms of the separation distance ($q_N$) and fill distance ($h_{D,N}$) of the data sites.
   • This theory connects the discrete estimator to its continuous counterpart, demonstrating that the accuracy of the DMOC depends on the geometric quality of the underlying data distribution.

3. Algorithms:

   • Exact Computation (Algorithm 1): Computes the DMOC by evaluating all pairwise distances in the dataset. This has a quadratic runtime complexity, $O(N^2)$, which is prohibitive for large datasets.
   • Minibatch Approximation (Algorithm 2): To enable scalability, the authors propose a minibatch algorithm. By shuffling the data and processing batches, the cost is reduced to $O(NC)$, where $C$ is the batch size. This allows evaluation on large-scale datasets like ImageNet.

4. Diagnostic Metrics:

   • To compare DMOCs between different networks or against the data, the authors introduce alignment metrics: a relative alignment score $S(w, w')$ and the Pearson correlation coefficient $r(w, w')$. These metrics quantify how well a network's input-output behavior matches the intrinsic regularity of the data.

Key Contributions

• Data-Centric Framework: The DMOC shifts the focus from model regularity to data regularity, providing a baseline against which network robustness is assessed without requiring access to model internals (black-box setting).
• Theoretical Guarantees: The paper provides explicit convergence rates for DMOC-induced seminorms based on data separation and fill distances.
• Scalability: The introduction of a minibatch algorithm mitigates the quadratic computational cost, making the method applicable to large datasets (e.g., ImageNet).
• Empirical Diagnostic Tool: The framework serves as an architecture-independent diagnostic that distinguishes trained from untrained networks and identifies underfitting and overfitting regimes.

Experimental Results
The authors evaluated the DMOC on four datasets: California Housing, Iris, MNIST, and ImageNet, using various feedforward ReLU networks and AlexNet.

• Lipschitz Estimation: As a special case, the DMOC yields tight Lipschitz estimates. On the California Housing dataset, DMOC estimates were comparable to state-of-the-art methods like ECLipsE and ECLipsE-Fast, often computed faster (e.g., finishing in 9 seconds vs. 30–96 seconds for ECLipsE on specific architectures).
• Network States:
  • Well-fitting networks: Showed strong alignment with the data's DMOC profile and high correlation scores.
  • Untrained networks: Exhibited different smoothness patterns, often underestimating expected smoothness at larger scales.
  • Overfitting networks: Tended to overshoot the data's DMOC, showing oscillatory deviations.
  • Underfitting networks: Displayed overly smooth behavior with little variation across scales, failing to capture the data's complexity.
• ImageNet: The minibatch approach successfully computed DMOCs for AlexNet, revealing that trained networks have significantly larger DMOCs than untrained ones, with resolution improving as batch size increases.

Significance and Claims
The paper claims that the DMOC offers a richer, multi-scale description of network regularity than the Lipschitz constant. By relying on input-output pairs in metric spaces, it provides a black-box, architecture-agnostic tool for assessing robustness. The authors emphasize that the DMOC is not merely a replacement for Lipschitz constants but a refinement that captures data-intrinsic regularity.

The work positions the DMOC primarily as a post-hoc diagnostic tool. It demonstrates that DMOC profiles can automatically distinguish between training states (underfitting, overfitting, well-fitting) and provide tight Lipschitz bounds. The authors modestly note that while the framework is theoretically applicable to latent representations in transformers, this has not yet been explored empirically. They also identify the current limitation of using DMOC solely for diagnosis, suggesting that incorporating it into training via regularization is a natural direction for future work.