Smoothness, Low Noise and Fast Rates

By Nati Srebro, Karthik Sridharan, Ambuj Tewari. 2010

305 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “…learning theory include the VC dimension, covering numbers, algorithmic stability, Rademacher complexity, or flat minima (see, for instance, Srebro et al., 2010; Kakade et al., 2009; Zhou, 2002; Schapire et al., 1998; Koltchinskii et al., 2002; Bousquet and Elisseeff, 2002; Vapnik and…”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, methodology): “The key observation used for analyzing the dependence on L(w) is that for any non-negative H-smooth convex function f : W 7→ R, we have [13]: ‖∇f(w)‖ ≤ √ 4Hf(w) (3) This self-bounding property tells us that the norm of the gradient is small at a point if the loss is itself small at that point.”
Variance-based Regularization with Convex Objectives (2016, background): “θberm n achieves. As evidenced by the substantial work on Rademacher- and Gaussian-complexity and symmetrization, in some instances covering-number-based arguments do not provide the sharpest scaling [2, 3, 43]; thus, in Section 3.2 we present a version of our main result that depends on localized R”
Does learning require memorization? a short tale about a long tail (2019, background): “It is known that in the convex setting SGD converges faster when all the loss functions have a joint minimizer [36, 47] and therefore it”
Data-Dependent Stability of Stochastic Gradient Descent (2017, background): “Here we focus on comparison to [35], since their results assume only smoothness of the loss function, while others impose stronger assumptions.”
Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing (2011, background): “Indeed, in the inductive setting, such terms appear only in high-probability bounds, and even then it is possible to prove oracle inequalities which depend merely on b /|S| rather than b / |S| (see for instance (Srebro et al., 2010, Theorem 1)).”
Provable and Efficient Continual Representation Learning (2022, methodology): “Additionally, inspired by Srebro et al. (2010); Bartlett et al. (2005), we obtain faster rates using a localization argument for our CRL problem (see Section 4.2).”
The Implicit and Explicit Regularization Effects of Dropout (2020, methodology): “Thus, we can apply the steps from the proof of Theorem 1 in (Srebro et al., 2010) (which invokes Theorem 6.1 of (Bousquet, 2002)), we have with probability 1 ´ δ , for all W P R c ˆ d , } W J } 2 , 1 ď A E P r (cid:96) σ p W, x, y qs ď E P n r (cid:96) σ p W, x, y qs ` 106 r To obtain the last…”
A study in Rashomon curves and volumes: A new perspective on generalization and model simplicity in machine learning (2019, background): “In other words, the Rashomon set benefits from having multiple similar models, while Rademacher complexity treats them as equivalent.”
Near-optimal max-affine estimators for convex regression (2015, result): “These theorems also provide similar results when combined with an upper bound on the Rademacher complexity such as Lemma A.3 of Srebro et al. (2012).”
Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning (2014, background): “[25], or assume prior knowledge of intrinsic (and unknown) characteristic of the problem [24, 29, 31, 33, 34].”
Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors (2011, methodology): “, the Huber-ized hinge loss) have been proposed [62] and a host of classification algorithms related to this problem exist [61]–[65], both of which may prove useful in the 1-bit CS framework in the future.”
Stein Variational Gradient Descent as Moment Matching (2018, methodology): “We now apply Theorem B.1 to each bound the difference between the expected loss Lj(gX,j) and the empirical loss L̂j(gX,j).”
One-Pass AUC Optimization (2013, methodology): “The faster convergence rate of our proposed algorithm owes to the smoothness of the square loss, an important property that has been explored by some studies of online learning (Rakhlin et al., 2012) and generalization error bound analysis (Srebro et al., 2010).”
Loss Minimization and Parameter Estimation with Heavy Tails (2013, methodology): “∈ ∈ Minsker analyzes this approach for Banach and Hilbert spaces.”