On the Efficiency of ERM in Feature Learning

• URL: http://arxiv.org/abs/2411.12029v1
• Date: Mon, 18 Nov 2024 20:05:05 GMT
• Title: On the Efficiency of ERM in Feature Learning
• Authors: Ayoub El Hanchi, Chris J. Maddison, Murat A. Erdogdu,
• Abstract summary: We study the performance of empirical risk minimization on regression problems with square loss over the union of the linear classes induced by feature maps. We show that when the set $mathcalT$ is not too large and when there is a unique optimal feature map, these quantiles coincide, up to a factor of two, with those of the excess risk of the oracle procedure. We obtain new guarantees on the performance of the best subset selection procedure in sparse linear regression under general assumptions.
• Score: 31.277788690403522
• License:
• Abstract: Given a collection of feature maps indexed by a set $\mathcal{T}$, we study the performance of empirical risk minimization (ERM) on regression problems with square loss over the union of the linear classes induced by these feature maps. This setup aims at capturing the simplest instance of feature learning, where the model is expected to jointly learn from the data an appropriate feature map and a linear predictor. We start by studying the asymptotic quantiles of the excess risk of sequences of empirical risk minimizers. Remarkably, we show that when the set $\mathcal{T}$ is not too large and when there is a unique optimal feature map, these quantiles coincide, up to a factor of two, with those of the excess risk of the oracle procedure, which knows a priori this optimal feature map and deterministically outputs an empirical risk minimizer from the associated optimal linear class. We complement this asymptotic result with a non-asymptotic analysis that quantifies the decaying effect of the global complexity of the set $\mathcal{T}$ on the excess risk of ERM, and relates it to the size of the sublevel sets of the suboptimality of the feature maps. As an application of our results, we obtain new guarantees on the performance of the best subset selection procedure in sparse linear regression under general assumptions.

Related papers

• Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms [22.79595679373698]
  Mixed linear regression is a well-studied problem in statistics and machine learning. In this paper, we consider the more general problem of learning of mixed linear regression from samples. We show that the AM and EM algorithms lead to learning in mixed linear regression by converging to the population loss minimizers.
  arXiv  Detail & Related papers  (2024-06-03T09:43:24Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Adaptive LASSO estimation for functional hidden dynamic geostatistical model [69.10717733870575]
  We propose a novel model selection algorithm based on a penalized maximum likelihood estimator (PMLE) for functional hiddenstatistical models (f-HD) The algorithm is based on iterative optimisation and uses an adaptive least absolute shrinkage and selector operator (GMSOLAS) penalty function, wherein the weights are obtained by the unpenalised f-HD maximum-likelihood estimators.
  arXiv  Detail & Related papers  (2022-08-10T19:17:45Z)
• Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions [28.30744223973527]
  We give a computationally efficient algorithm that is the first to enjoy the statistically optimal log(T/sigma) regret for realizable K-wise linear classification. We develop a novel characterization of the geometry of the disagreement region induced by generalized linear classifiers.
  arXiv  Detail & Related papers  (2022-05-25T21:31:36Z)
• Mitigating multiple descents: A model-agnostic framework for risk monotonization [84.6382406922369]
  We develop a general framework for risk monotonization based on cross-validation. We propose two data-driven methodologies, namely zero- and one-step, that are akin to bagging and boosting.
  arXiv  Detail & Related papers  (2022-05-25T17:41:40Z)
• Minimax rate of consistency for linear models with missing values [0.0]
  Missing values arise in most real-world data sets due to the aggregation of multiple sources and intrinsically missing information (sensor failure, unanswered questions in surveys...). In this paper, we focus on the extensively-studied linear models, but in presence of missing values, which turns out to be quite a challenging task. This eventually requires to solve a number of learning tasks, exponential in the number of input features, which makes predictions impossible for current real-world datasets.
  arXiv  Detail & Related papers  (2022-02-03T08:45:34Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning [36.015585972493575]
  This paper considers batch Reinforcement Learning (RL) with general value function approximation. The excess risk of Empirical Risk Minimizer (ERM) is bounded by the Rademacher complexity of the function class. Fast statistical rates can be achieved by using tools of local Rademacher complexity.
  arXiv  Detail & Related papers  (2021-03-25T14:45:29Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Interpolating Predictors in High-Dimensional Factor Regression [2.1055643409860743]
  This work studies finite-sample properties of the risk of the minimum-norm interpolating predictor in high-dimensional regression models. We show that the min-norm interpolating predictor can have similar risk to predictors based on principal components regression and ridge regression, and can improve over LASSO based predictors, in the high-dimensional regime.
  arXiv  Detail & Related papers  (2020-02-06T22:08:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.