Introduction
In the fields of machine learning and optimization, quantifying the discrepancy between two functions is a fundamental task. Whether comparing an empirical loss to a population loss in Empirical Risk Minimization (ERM) or tracking the evolution of loss functions in non-stationary online optimization, researchers rely on various metrics to measure functional variation. However, these metrics—ranging from the supremum norm to gradient variation and the distance between minimizers—are often fragmented across sub-fields.
This paper proposes a unified mathematical framework called $(\varepsilon, \delta)$-closeness. By focusing on how the sub-optimality gaps of two functions relate to one another, this measure captures the intrinsic similarity between functions in a way that simplifies theoretical derivations and unifies disparate results in statistical learning theory.
The $(\varepsilon, \delta)$-Closeness Framework
The core contribution of this work is the definition of $(\varepsilon, \delta)$-closeness. Two lower-bounded functions $f$ and $g$ are considered $(\varepsilon, \delta)$-close if the sub-optimality gap of one is bounded by a scaled version of the other's gap, plus an additive constant:
$$f(x) - \inf f \leq e^\varepsilon (g(x) - \inf g) + \delta$$
This definition introduces two critical parameters:
- $\delta$ (Additive factor): Represents the intrinsic, unavoidable discrepancy between the two functions.
- $e^\varepsilon$ (Multiplicative factor): Provides "leeway." It allows for a larger difference between the functions when a parameter is highly sub-optimal.
This multiplicative leeway is a significant departure from the standard supremum norm (which effectively forces $e^\varepsilon = 1$). The authors demonstrate that allowing $e^\varepsilon > 1$ is precisely what enables the derivation of "fast" statistical rates without the need for overly complex traditional proof techniques.
A Universal Metric for Optimization
The $(\varepsilon, \delta)$-closeness definition acts as a theoretical bridge between different optimization metrics. Depending on the properties of the functions being compared, it naturally reduces to several well-known measures of variation:
- Functional Variation: For general functions, it bounds the standard supremum norm.
- Gradient Variation: For differentiable functions, it provides a bound on the difference between gradients.
- Minimizer Distance: For strongly convex and smooth functions, it bounds the physical distance between the functions' respective minimizers.
Geometrically, this measure implies a "sandwiching" effect: if two functions are $(\varepsilon, \delta)$-close, their sub-level sets are neatly nested and scaled according to the $\varepsilon$ and $\delta$ parameters.
Applications in Statistical Learning
The utility of this framework is most evident in its ability to simplify and unify complex proofs in learning theory:
- Empirical Risk Minimization (ERM): The authors use $(\varepsilon, \delta)$-closeness to recover standard convergence rates effortlessly. For general functions, empirical and population losses are shown to be $(0, O(\sqrt{d/n}))$-close, yielding the standard $O(\sqrt{d/n})$ rate. For strongly convex functions, they prove the losses are $(\log 2, O(d/n))$-close, instantly yielding the fast $O(d/n)$ rate.
- Local Rademacher Complexity: The framework translates classical, highly technical local Rademacher complexity bounds—which traditionally require complex "peeling" techniques—into the more intuitive language of $(\varepsilon, \delta)$-closeness.
- Online Optimization: In non-stationary environments, bounding the $(\varepsilon, \delta)$-closeness between consecutive loss functions $F_{t-1}$ and $F_t$ allows researchers to derive performance bounds that are agnostic to which specific variation metric was originally used.
Conclusion
While this theoretical note focuses on classical assumptions like strong convexity and smoothness, it provides a powerful new abstraction for understanding functional similarity. By unifying disparate metrics into a single $(\varepsilon, \delta)$ pair, the paper offers a clearer path for deriving convergence rates and understanding the geometric relationship between functions. Future research may extend this unified measure to the non-convex landscapes typical of deep learning or to complex reinforcement learning environments where tracking function variation over time remains a significant challenge.
Summary updated