A concentration inequality for the excess risk in least-squares regression with random design and heteroscedastic noise
We prove a new and general concentration inequality for the excess risk in least-squares regression with random design and heteroscedastic noise. No specific structure is required on the model, except the existence of a suitable function that controls the local suprema of the empirical process. So far, only the case of linear contrast estimation was tackled in the literature with this level of generality on the model. We solve here the case of a quadratic contrast, by separating the behavior of a linearized empirical process and the empirical process driven by the squares of functions of models.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionSimilar Papers 제목 키워드 기반
Regularized least squares learning with heavy-tailed noise is minimax optimal
This paper examines the performance of ridge regression in reproducing kernel Hilbert spaces in the presence of noise that exhibits a finite number of higher moments. We establish excess risk bounds consisting of subgaus…
Sharp Generalization of Transductive Learning: A Transductive Local Rademacher Complexity Approach
We introduce a new tool, Transductive Local Complexity (TLC), designed to analyze the generalization performance of transductive learning methods and inspire the development of new algorithms in this domain. Our work ext…
Generalization BoundsLearning TheoryTransductive LearningSuboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors
We study the problem of predicting as well as the best linear predictor in a bounded Euclidean ball with respect to the squared loss. When only boundedness of the data generating distribution is assumed, we establish tha…
Compressed Least-Squares Regression
We consider the problem of learning, from K input data, a regression function in a function space of high dimension N using projections onto a random subspace of lower dimension M. From any linear approximation algorithm…
regressionTime-Uniform Self-Normalized Concentration for Discounted Least Squares: Limits and Corrections
Self-normalized concentration inequalities are standard tools in bandit and reinforcement-learning analyses. A widely used weighted extension claims an analogous time-uniform guarantee for discounted least-squares estima…