Optimistic Rates for Learning with a Smooth Loss

Abstract

We establish an excess risk bound of O(H R_n^2 + R_n \sqrt{H L*}) for empirical risk minimization with an H-smooth loss function and a hypothesis class with Rademacher complexity R_n, where L* is the best risk achievable by the hypothesis class. For typical hypothesis classes where R_n = \sqrt{R/n}, this translates to a learning rate of O(RH/n) in the separable (L*=0) case and O(RH/n + \sqrt{L^* RH/n}) more generally. We also provide similar guarantees for online and stochastic convex optimization with a smooth non-negative objective.

References in corpus (4)

• Simultaneous analysis of Lasso and Dantzig selector
• Fast rates for support vector machines using Gaussian kernels
• Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
• Adapting to Unknown Smoothness by Aggregation of Thresholded Wavelet Estimators

Cited by in corpus (27)

• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Online Learning: A Modern Introduction Using Convex Optimization
• Matrix Completion via Max-Norm Constrained Optimization
• Empirical entropy, minimax regret and minimax risk
• Fast Rates by Transferring from Auxiliary Hypotheses
• Learning tensors from partial binary measurements
• Multiple testing with the structure adaptive Benjamini-Hochberg algorithm
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• Learning with incremental iterative regularization
• Generalization bounds via distillation
• Learning to Filter with Predictive State Inference Machines
• Dropout: Explicit Forms and Capacity Control
• Decoupling Gating from Linearity
• Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
• On Uniform Convergence and Low-Norm Interpolation Learning
• Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
• Improved Learning Rates for Stochastic Optimization
• Local Rademacher Complexity Bounds based on Covering Numbers
• Everything old is new again: A multi-view learning approach to learning using privileged information and distillation
• Decision Making Problems with Funnel Structure: A Multi-Task Learning Approach with Application to Email Marketing Campaigns
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• On the Last Iterate Convergence of Momentum Methods
• Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Theoretical Analysis of Divide-and-Conquer ERM: Beyond Square Loss and RKHS
• Max-Diversity Distributed Learning: Theory and Algorithms