Concentration Inequalities and Empirical Processes Theory Applied to the Analysis of Learning Algorithms

By Olivier Bousquet. 2002

116 citations recorded by the source corpus.

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): “where K < 10(5) is a numeric constant derived from [20] and [6].”
Variance-based Regularization with Convex Objectives (2016, neutral): “ion that G2 = {g2 | g∈ G} for any function class G. Thus we may take ψsup n (r) = C √ rRsup n (F)log 3 2 n, which has ﬁxed point r sup n = C2R sup n (F)2 log3 n. Since f2 ≥ 0, Theorem 6.1 of Bousquet [13] yields that for all f∈ F, E(f−E[f])2 ≤ 2Eb Pn (f−E[f])2 +C Rsup n (F) 2 log3 nM+ M2 n (t+loglo”
Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy (2018, background): “Generally speaking, statistical accuracy V n depends on n (although it depends on ϑ too, but for simplicity in notation we just consider the size of the samples), and is of order , 2013, Bousquet, 2002, Bartlett et al., 2006].”
Large-Scale Machine Learning with Stochastic Gradient Descent (2010, background): “The equivalence E = Eapp +Eest +Eopt ∼ Eapp + ( log n n )α + ρ , for some α ∈ [1 2 , 1 ] , (8) provides a more realistic view of the asymptotic behavior of the excess error (e.g. Massart (2000), Bousquet (2002)).”
Fast Rates for Regularized Objectives (2008, background): “It is also possible to ensure rates of 1/n by relying on low noise conditions [7, 9], but here we make no such assumption.”
Finite-Dimensional Projection for Classification and Statistical Learning (2008, unknown): “Elementary arguments not reproduced here (see [30], Lemma 4.”
Large-Scale Machine Learning (2020, background): “N ] | {z } Eopt Approximation error E app : reduced by choosing a larger model Estimation error E est : reduced by 1 Increasing N, or 2 Choosing smaller model [2, 5, 7] Optimization error E opt : reduced by 1 Running optimization alg.”
The Implicit and Explicit Regularization Effects of Dropout (2020, methodology): “1 of (Bousquet, 2002)), we have with probability 1 ́ δ, for all W P Rcˆd, }W}2,1 ď A EP rr `σpW,x, yqs ď EPnr `σpW,x, yqs ` 106r‹ ` 48B n plog 1{δ ` log log nq”
Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning (2016, methodology): “Lemma 3 (Lemma 2.11 in [17]) .”
Stochastic Gradient Descent Tricks (2012, unknown): “[13, 4]).”
Distance-Based Classification with Lipschitz Functions (2004, methodology): “For example, Hein and Bousquet (2003) studied the Kuratowski embedding of a metric space into its space of continuous functions to construct a large margin algorithm.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “mining gaps dependent on an observed variance of the risk or by considering uniform bounds restricted to families of prediction functions that achieve a risk within a certain threshold of the optimum [55,102,26]. 11 R n(h) over h2H C), but, after some point, it typically increases the gap between ex”
On the Performance of Kernel Classes (2003, methodology): “The version we use is from Bousquet (2002). Theorem 1.”
NEW APPROACHES TO STATISTICAL LEARNING THEORY (2006, background): “(Bousquet (2002a)) Let ~ be a countable set of functions from 2( x y to lR and assume that all functions f in :F satisfy SUPx,y P f - f (x , y) <_ b.”
Statistical properties of kernel principal component analysis (2004, methodology): “10 of Bousquet (2002). So, we can unroll the same reasoning as in the first part of the present proof, except that the covariance operators are replaced by their empirical counterparts and we consider directly the empirical Rademacher complexities without expectation over the sample.”