Empirical entropy, minimax regret and minimax risk

DOI10.3150/14-BEJ679MaRDI QIDQ520672zbMATH OpenOpenAlexFDO

Authors Alexander Rakhlin, Karthik Sridharan, Alexandre B. Tsybakov

Publication date 5 April 2017

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.1147, https://projecteuclid.org/euclid.bj/1486177384

zbMATH Keywords

aggregationempirical risk minimizationentropyminimax regretminimax risk

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20) Nonparametric regression and quantile regression (62G08)

Abstract: We consider the random design regression model with square loss. We propose a method that aggregates empirical minimizers (ERM) over appropriately chosen random subsets and reduces to ERM in the extreme case, and we establish sharp oracle inequalities for its risk. We show that, under the $varepsilo{n}^{-p}$ growth of the empirical $varepsilon$-entropy, the excess risk of the proposed method attains the rate $n^{-2/(2+p)}$ for $pin(0,2)$ and $n^{-1/p}$ for $p>2$ where $n$ is the sample size. Furthermore, for $pin(0,2)$, the excess risk rate matches the behavior of the minimax risk of function estimation in regression problems under the well-specified model. This yields a conclusion that the rates of statistical estimation in well-specified models (minimax risk) and in misspecified models (minimax regret) are equivalent in the regime $pin(0,2)$. In other words, for $pin(0,2)$ the problem of statistical learning enjoys the same minimax rate as the problem of statistical estimation. On the contrary, for $p>2$ we show that the rates of the minimax regret are, in general, slower than for the minimax risk. Our oracle inequalities also imply the $vlog(n/v)/n$ rates for Vapnik-Chervonenkis type classes of dimension $v$ without the usual convexity assumption on the class; we show that these rates are optimal. Finally, for a slightly modified method, we derive a bound on the excess risk of $s$-sparse convex aggregation improving that of Lounici [Math. Methods Statist. 16 (2007) 246-259] and providing the optimal rate.

Recommendations

• Empirical risk minimization is optimal for the convex aggregation problem
• Fast learning rates in statistical inference through aggregation
• Sparsity in penalized empirical risk minimization
• Learning Theory and Kernel Machines
• On the optimality of the empirical risk minimization procedure for the convex aggregation problem

Cited in

(22)

• Bayesian fractional posteriors
• Set structured global empirical risk minimizers are rate optimal in general dimensions
• Suboptimality of constrained least squares and improvements via non-linear predictors
• Distribution-free robust linear regression
• On least squares estimation under heteroscedastic and heavy-tailed errors
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Empirical variance minimization with applications in variance reduction and optimal control
• Optimal functional supervised classification with separation condition
• Convergence rates for empirical barycenters in metric spaces: curvature, convexity and extendable geodesics
• Bounding the expectation of the supremum of empirical processes indexed by Hölder classes
• Isotonic regression in general dimensions
• scientific article; zbMATH DE number 63418 (Why is no real title available?)
• scientific article; zbMATH DE number 7370563 (Why is no real title available?)
• Active learning for cost-sensitive classification
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits Under Realizability
• Deep learning: a statistical viewpoint
• Entropy Maximization for Partially Observable Markov Decision Processes
• Minimax rates for conditional density estimation via empirical entropy
• Orthogonal statistical learning
• Relaxing the i.i.d. assumption: adaptively minimax optimal regret via root-entropic regularization
• Improved convergence rate of nested simulation with LSE on sieve
• A tight excess risk bound via a unified PAC-Bayesian-Rademacher-Shtarkov-MDL complexity

This page was built for publication: Empirical entropy, minimax regret and minimax risk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q520672)