Set structured global empirical risk minimizers are rate optimal in general dimensions

DOI10.1214/21-AOS2049zbMATH Open1478.62081arXiv1905.12823OpenAlexW3212589533MaRDI QIDQ2054522FDOQ2054522

Authors: Qiyang Han 

Publication date: 3 December 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: Entropy integrals are widely used as a powerful empirical process tool to obtain upper bounds for the rates of convergence of global empirical risk minimizers (ERMs), in standard settings such as density estimation and regression. The upper bound for the convergence rates thus obtained typically matches the minimax lower bound when the entropy integral converges, but admits a strict gap compared to the lower bound when it diverges. Birg'e and Massart [BM93] provided a striking example showing that such a gap is real with the entropy structure alone: for a variant of the natural H"older class with low regularity, the global ERM actually converges at the rate predicted by the entropy integral that substantially deviates from the lower bound. The counter-example has spawned a long-standing negative position on the use of global ERMs in the regime where the entropy integral diverges, as they are heuristically believed to converge at a sub-optimal rate in a variety of models. The present paper demonstrates that this gap can be closed if the models admit certain degree of `set structures' in addition to the entropy structure. In other words, the global ERMs in such set structured models will indeed be rate-optimal, matching the lower bound even when the entropy integral diverges. The models with set structures we investigate include (i) image and edge estimation, (ii) binary classification, (iii) multiple isotonic regression, (iv) $s$-concave density estimation, all in general dimensions when the entropy integral diverges. Here set structures are interpreted broadly in the sense that the complexity of the underlying models can be essentially captured by the size of the empirical process over certain class of measurable sets, for which matching upper and lower bounds are obtained to facilitate the derivation of sharp convergence rates for the associated global ERMs.

Full work available at URL: https://arxiv.org/abs/1905.12823

Recommendations

• Empirical entropy, minimax regret and minimax risk
• Learning Theory
• On concentration for (regularized) empirical risk minimization
• On the optimality of sample-based estimates of the expectation of the empirical minimizer
• Risk bounds for statistical learning

zbMATH Keywords

classificationdensity estimationnonparametric regressionempirical processempirical risk minimizationnon-Donsker

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Density estimation (62G07) Nonparametric regression and quantile regression (62G08) Asymptotic properties of nonparametric inference (62G20)

Cites Work

• Weak convergence and empirical processes. With applications to statistics
• Asymptotical minimax recovery of sets with smooth boundaries
• Efficient maximum likelihood estimation in semiparametric mixture models
• Mathematical foundations of infinite-dimensional statistical models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convergence rates of least squares regression estimators with heavy-tailed errors
• Risk bounds for model selection via penalization
• Convergence of estimates under dimensionality restrictions
• Title not available (Why is that?)
• Smooth discrimination analysis
• Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
• Title not available (Why is that?)
• Approximation dans les espaces m�triques et th�orie de l'estimation
• Maximal inequalities via bracketing with adaptive truncation
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Minimax theory of image reconstruction
• Optimal aggregation of classifiers in statistical learning.
• Probability inequalities for likelihood ratios and convergence rates of sieve MLEs
• Entropy estimate for high-dimensional monotonic functions
• A central limit theorem under metric entropy with \(L_ 2\) bracketing
• Rates of convergence for minimum contrast estimators
• Hellinger-consistency of certain nonparametric maximum likelihood estimators
• Simultaneous adaptation to the margin and to complexity in classification
• Global rates of convergence of the MLEs of log-concave and \(s\)-concave densities
• Approximation and estimation of \(s\)-concave densities via Rényi divergences
• Optimal rates of convergence for convex set estimation from support functions
• Global rates of convergence in log-concave density estimation
• Nonparametric estimation of multivariate convex-transformed densities
• Information-theoretic determination of minimax rates of convergence
• On concentration for (regularized) empirical risk minimization
• Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class
• A new perspective on least squares under convex constraint
• Estimating a regression function
• Risk bounds for statistical learning
• A new approach to least-squares estimation, with applications
• New Donsker classes
• The method of sieves and minimum contrast estimators
• Adaptive estimation of convex polytopes and convex sets from noisy data
• Isotonic regression in general dimensions
• Empirical and Poisson processes on classes of sets or functions too large for central limit theorems
• Optimal upper and lower bounds for the true and empirical excess risks in heteroscedastic least-squares regression
• On matrix estimation under monotonicity constraints
• Minimax Two-Dimensional Image Reconstruction

Cited In (9)

• Coverage of credible intervals in Bayesian multivariate isotonic regression
• Local convergence rates of the nonparametric least squares estimator with applications to transfer learning
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Minimax rates for conditional density estimation via empirical entropy
• Phase transitions for support recovery under local differential privacy
• Posterior contraction and testing for multivariate isotonic regression
• Multiplier \(U\)-processes: sharp bounds and applications
• Inference for Local Parameters in Convexity Constrained Models
• Structural risk minimization over data-dependent hierarchies

This page was built for publication: Set structured global empirical risk minimizers are rate optimal in general dimensions

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