Lipschitzian SLLNs for random functions

Technical Breakdown§

This paper establishes strong laws of large numbers (SLLNs) for sequences of random functions under a Lipschitz pseudometric. The key innovation is the relaxation of traditional compactness or convexity assumptions by leveraging either a topological condition (separability of the function space with respect to the Lipschitz pseudometric) or a model-theoretic condition (functions that are definable in a structure that is NIP, extending o-minimality). The results ensure almost sure convergence of the empirical averages to the population average uniformly over the function class, measured in the Lipschitz pseudometric.

Mathematical Formulation§

Let $(\Xi, \mathcal{A}, P)$ be a probability space and $\mathcal{F}$ a collection of functions $f: \Xi \times \mathbb{R}^d \to \mathbb{R}$ that are locally Lipschitz in the second argument. Define the Lipschitz pseudometric on $\mathcal{F}$ as $$d_L(f,g) = \sup_{\xi \in \Xi} \inf\{M \geq 0 : |f(\xi,x)-g(\xi,x)| \leq M \|x\| \text{ for all } x\}.$$ The main theorem states that under either the topological or model-theoretic condition, for i.i.d. draws $\xi_1,\dots,\xi_n$ from $P$, $$\mathbb{E}[f(\xi,\cdot)]\qquad\text{and}\qquad \frac{1}{n}\sum_{i=1}^n f(\xi_i,\cdot)$$ converge almost surely in the Lipschitz pseudometric. This implies uniform convergence of the functions and, by extension, of their Clarke subdifferentials.

Implementation Details§

While the paper is theoretical, a key implication for practitioners is that stochastic optimization methods (e.g., stochastic subgradient descent) for nonsmooth objectives will have the expected limiting behavior over broad function classes. The following conceptual snippet checks the Lipschitz condition for a random function:

import numpy as np

def empirical_lipschitz_constant(f, xi, x_samples):
    """Estimate the Lipschitz constant of f(xi, .) at xi."""
    x_samples = np.asarray(x_samples)
    diffs = []
    for x in x_samples:
        for y in x_samples:
            if not np.allclose(x, y):
                ratio = abs(f(xi, x) - f(xi, y)) / np.linalg.norm(x - y)
                diffs.append(ratio)
    return np.max(diffs) if diffs else 0.0

# Example: random piecewise linear function
def f(xi, x):
    return np.abs(np.dot(xi, x))  # locally Lipschitz
theta = np.random.randn(5)
xi_sample = np.random.randn(5)
x_grid = [np.random.randn(5) for _ in range(100)]
L = empirical_lipschitz_constant(f, xi_sample, x_grid)
print(f"Estimated Lipschitz constant: {L:.3f}")

Significance§

The paper resolves limitations of prior negative results (e.g., Tian & Royset, 2025) by identifying broad classes of functions where sample averages converge uniformly so that failure phenomena like non-robustness or lack of identification do not occur. This has direct implications for optimization, statistical learning, and sensitivity analysis.