Uniform Convergence with Square-Root Lipschitz Loss
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.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionRetrievalSimilar Papers 제목 키워드 기반
Decentralized Feature-Distributed Optimization for Generalized Linear Models
We consider the "all-for-one" decentralized learning problem for generalized linear models. The features of each sample are partitioned among several collaborating agents in a connected network, but only one agent observ…
Distributed OptimizationExtragradient Method for $(L_0, L_1)$-Lipschitz Root-finding Problems
Introduced by Korpelevich in 1976, the extragradient method (EG) has become a cornerstone technique for solving min-max optimization, root-finding problems, and variational inequalities (VIs). Despite its longstanding pr…
Uniform Convergence of Deep Neural Networks with Lipschitz Continuous Activation Functions and Variable Widths
We consider deep neural networks with a Lipschitz continuous activation function and with weight matrices of variable widths. We establish a uniform convergence analysis framework in which sufficient conditions on weight…
Towards Sharper Generalization Bounds for Structured Prediction
In this paper, we investigate the generalization performance of structured prediction learning and obtain state-of-the-art generalization bounds. Our analysis is based on factor graph decomposition of structured predicti…
Generalization BoundsPredictionStructured PredictionPrivate Stochastic Optimization With Large Worst-Case Lipschitz Parameter
We study differentially private (DP) stochastic optimization (SO) with loss functions whose worst-case Lipschitz parameter over all data may be extremely large or infinite. To date, the vast majority of work on DP SO ass…
Stochastic Optimization