Uniform Convergence with Square-Root Lipschitz Loss
This work addresses theoretical challenges in machine learning for researchers, providing a more general and applicable convergence framework, though it is incremental in extending existing theory.
The paper tackles the problem of establishing uniform convergence guarantees for Gaussian data by introducing a framework based on the Rademacher complexity and the Lipschitz constant of the square root of the loss function. It generalizes previous smoothness-based results, enabling analysis of non-smooth losses like those in phase retrieval and ReLU regression, and reinterprets optimistic rate and interpolation learning guarantees.
We establish generic uniform convergence guarantees for Gaussian data in terms of the Rademacher complexity of the hypothesis class and the Lipschitz constant of the square root of the scalar loss function. We show how these guarantees substantially generalize previous results based on smoothness (Lipschitz constant of the derivative), and allow us to handle the broader class of square-root-Lipschitz losses, which includes also non-smooth loss functions appropriate for studying phase retrieval and ReLU regression, as well as rederive and better understand "optimistic rate" and interpolation learning guarantees.