Set structured global empirical risk minimizers are rate optimal in general dimensions
From MaRDI portal
Publication:2054522
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) -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.
Recommendations
Cites work
- scientific article; zbMATH DE number 193111 (Why is no real title available?)
- scientific article; zbMATH DE number 3797051 (Why is no real title available?)
- scientific article; zbMATH DE number 893887 (Why is no real title available?)
- scientific article; zbMATH DE number 1420699 (Why is no real title available?)
- A central limit theorem under metric entropy with \(L_ 2\) bracketing
- A new approach to least-squares estimation, with applications
- A new perspective on least squares under convex constraint
- Adaptive estimation of convex polytopes and convex sets from noisy data
- Approximation and estimation of \(s\)-concave densities via Rényi divergences
- Approximation dans les espaces m�triques et th�orie de l'estimation
- Asymptotical minimax recovery of sets with smooth boundaries
- Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class
- Concentration inequalities and asymptotic results for ratio type empirical processes
- Convergence of estimates under dimensionality restrictions
- Convergence rates of least squares regression estimators with heavy-tailed errors
- Efficient maximum likelihood estimation in semiparametric mixture models
- Empirical and Poisson processes on classes of sets or functions too large for central limit theorems
- Entropy estimate for high-dimensional monotonic functions
- Estimating a regression function
- Global rates of convergence in log-concave density estimation
- Global rates of convergence of the MLEs of log-concave and \(s\)-concave densities
- Hellinger-consistency of certain nonparametric maximum likelihood estimators
- Information-theoretic determination of minimax rates of convergence
- Isotonic regression in general dimensions
- Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
- Mathematical foundations of infinite-dimensional statistical models
- Maximal inequalities via bracketing with adaptive truncation
- Minimax Two-Dimensional Image Reconstruction
- Minimax theory of image reconstruction
- New Donsker classes
- Nonparametric estimation of multivariate convex-transformed densities
- On concentration for (regularized) empirical risk minimization
- On matrix estimation under monotonicity constraints
- Optimal aggregation of classifiers in statistical learning.
- Optimal rates of convergence for convex set estimation from support functions
- Optimal upper and lower bounds for the true and empirical excess risks in heteroscedastic least-squares regression
- Probability inequalities for likelihood ratios and convergence rates of sieve MLEs
- Rates of convergence for minimum contrast estimators
- Risk bounds for model selection via penalization
- Risk bounds for statistical learning
- Simultaneous adaptation to the margin and to complexity in classification
- Smooth discrimination analysis
- The method of sieves and minimum contrast estimators
- Weak convergence and empirical processes. With applications to statistics
Cited in
(9)- Isotonic regression with unknown permutations: statistics, computation and adaptation
- Inference for Local Parameters in Convexity Constrained Models
- Phase transitions for support recovery under local differential privacy
- Posterior contraction and testing for multivariate isotonic regression
- Local convergence rates of the nonparametric least squares estimator with applications to transfer learning
- Multiplier \(U\)-processes: sharp bounds and applications
- Coverage of credible intervals in Bayesian multivariate isotonic regression
- Structural risk minimization over data-dependent hierarchies
- Minimax rates for conditional density estimation via empirical entropy
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)
