The importance of convexity in learning with squared loss

By Wee Sun Lee, Peter L. Bartlett, Robert C. Williamson. 1998

How researchers see this paper

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

Citations in the corpus

Smoothness, Low Noise and Fast Rates (2010, background): “The Finite Dimensional Case Lee et al [16] showed faster rates for squared loss, exploiting the strong convexity of this loss function, even when L∗ > 0, but only with finite VC-subgraph-dimension.”
Local Rademacher complexities (2005, background): “P. L. BARTLETT, O. BOUSQUET AND S. MENDELSON class F is convex and uniformly bounded. In particular, if |f(x)−y|∈[0,1] for all f∈F, x∈X and y∈Y, then the conditions are satisﬁed with L=2 and B=1 (see [18]). Other examples are described in [26] and in [2]. The ﬁrst result we present is a direct but i”
Tikhonov, Ivanov and Morozov regularization for support vector machine learning (2016, background): “…· Morozov regularization · Support vector machine B Luca Oneto Luca.Oneto@unige.it Sandro Ridella Sandro.Ridella@unige.it Davide Anguita Davide.Anguita@unige.it 1 DITEN - University of Genoa, Via Opera Pia 11a, 16145 Genoa, Italy 2 DIBRIS - University of Genoa, Via Opera Pia 13, 16145 Genoa, Italy”
Aggregation via empirical risk minimization (2009, background): “One can show [10,12,15,17] that, if (x, y) = (x − y)2, then for every random map A there exists a constant c depending only on the map and on δ, such that for every n, H(n,M, δ) ≥ c/√n.”
A Few Notes on Statistical Learning Theory (2002, background): “, then for every probability measure μ and every 2-loss function f , Eμf 2 ≤ 16Eμf [17, 20].”
Stochastic Gradient Descent Tricks (2012, background): “Faster convergence occurs when the loss function has strong convexity properties [9] or when the data distribution satisfies certain assumptions [24].”
Convergence of Value Aggregation for Imitation Learning (2018, methodology): “The O( 1 m ) error is due to iden- tifying the best policy (Lee et al., 1998) (as the function is strongly convex) and the O( 1√ mN ) error is the generaliza- tion error (Cesa-Bianchi et al., 2004). descent in O( 1n ), using AggreVaTe results in a sequence of policies with degrading performance,…”
Regularization in kernel learning (2010, background): “, [19]), that there exists an absolute constant C such that, for a convex class F , every Lf ∈ LF satisfies EL(2)f ≤ Cb(2)ELf .”
A Stochastic View of Optimal Regret through Minimax Duality (2009, background): “Ω(T−1/2)) rates occur when the loss is not strictly convex, or when the minimizer of the expected loss is not unique [15, 17].”
Optimization Methods for Large-Scale Machine Learning (2016, background): “istical problems. However, even faster convergence rates for reducing these terms with respect to ncan be established under specic conditions. For instance, when the loss function is strongly convex [91] or when the data distribution satises certain assumptions [154], it is possible to show that E(n”
Rademacher averages and phase transitions in Glivenko-Cantelli classes (2002, background): “2) If there is a constant such that for some , then for every there is a constant such that for every and every The first part of the claim is due to Lee, Bartlett, and Williamson [11], [12], while the second is presented in [15].”