Oracle inequalities in empirical risk minimization and sparse recovery problems

By Vladimir Koltchinskii, École d'été de probabilités de Saint-Flour. 2011

594 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

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 Statistics and Probability

Citations in the corpus

Geometric median and robust estimation in Banach spaces (2013, methodology): “1 in [21] implies that ‖∆‖ ≤ 4‖∆J‖, and it follows from the definition of κ(2N(λ0), 3) that ‖∆‖(2) ≤ 16‖∆J‖(2) ≤ 16 ∥∥∥X(λ̂ε − λ0)∥∥∥2 nκ(2)(2N(λ0), 3) .”
Regularization, sparse recovery, and median-of-means tournaments (2017, methodology): “Before we turn to a presentation of the regularized tournament procedure and the technical machinery we require, let us describe in more detail the two applications mentioned previously, both of which originating in sparse recovery: lasso, and slope (see, [1, 3, 14, 15]).”
Learning to Learn Single Domain Generalization (2020, methodology): “The models trained using Empirical Risk Minimization [16] usually perform poorly on unseen domains.”
Exponential Screening and optimal rates of sparse estimation (2010, background): “…procedures in terms of the ℓ 0 norm (number of non-zero components) of the estimated vectors or their approximations (see Bickel et al., 2009; Bunea et al., 2007a,b; Candes and Tao, 2007; Koltchinskii, 2008, 2009a,b; van de Geer, 2008; Zhang and Huang, 2008; Zhang, 2009, and references therein).”
Bayesian fractional posteriors (2016, methodology): “Similar to the local Rademacher complexity [5] or local Gaussian complexity [6] in a frequenstist oracle inequality (FOI) for penalized empirical risk minimization procedures [33, 34], a BOI also involves a penalty term, which we refer to as local Bayesian complexity, that characterizes the local co”
Towards a Learning Theory of Cause-Effect Inference (2015, background): “2 is known as the Rademacher complexity of F , will be denoted by Rn(F), and has a typical order of O(n−1/2) (Koltchinskii, 2011).”
Learning Sets with Separating Kernels (2012, background): “If X is not locally compact, then, in order to have measurability of F n , one needs to replace the probability measure with the outer measure (see the discussion in [39, 67]).”
Sparse recovery under matrix uncertainty (2008, unknown): “The Annals of Statistics 2010, Vol. 38, No. 5, 2620–2651 DOI: 10.1214/10-AOS793 © Institute of Mathematical Statistics, 2010”
Estimation of high-dimensional low-rank matrices (2009, background): “…is shown to be attained, up to logarithmic factors, for many estimators, such as the BIC, the Lasso, the Dantzig selector, Sparse Exponential Weighting, etc.; cf., for example, Bunea, Tsybakov and Wegkamp (2007), Koltchinskii (2008), Bickel, Ritov and Tsybakov (2009), Dalalyan and Tsybakov (2008).”
SPARSITY IN MULTIPLE KERNEL LEARNING (2010, methodology): “…with kernel K , and, for some A ≥ 1, It follows from Lemma 42 of Mendelson (2002) [with an additional application of Cauchy–Schwarz inequality for the upper bound and Hoffmann–Jørgensen inequality for the lower bound; see also Koltchinskii (2008)] that, for some numerical constants C 1 , C 2 > 0, .”
From Dependence to Causation (2016, background): “Rademacher complexities have a typical order of O(n−1/2) (Koltchinskii, 2011).”
Oracle Inequalities and Optimal Inference under Group Sparsity (2010, background): “In particular, it has been shown by different authors, under different conditions on the desig n matrix, that the Lasso satisfies sparsity oracle inequalities, see [4, 6, 7, 21, 18, 36, 41] and referen ces therein.”