Risk bounds for improper prediction procedures

Thesis

Statistical Learning Theory studies the problem of learning an unknown relationship between observed input-output pairs sampled independently from some unknown and arbitrary probability distribution. The quality of the inferred relationship is judged by its excess risk -- a measure of prediction capability on unseen data compared to the best predictor in some predefined reference class of functions. A learning procedure is said to be improper if it is allowed to output a prediction rule outside the chosen reference class. This thesis presents four contributions to analyzing the prediction performance of improper learning algorithms.

Our first result contributes to developing the mathematical machinery suitable for the analysis of improper learning procedures. We obtain exponential-tail excess risk bounds in terms of offset Rademacher complexity for which only in-expectation guarantees were previously obtained.

Our second result shows that offset Rademacher complexity yields upper bounds on the excess risk of iterative regularization schemes characterized by mirror descent algorithms. Moreover, by providing a unified analysis, our proposed proof technique circumvents the limitations of some previous analyses tailored to exploit the exact form of specific iterative schemes.

Our third contribution concerns the analysis of the constrained linear least squares algorithm. We find that this classical and widely studied statistical estimator is suboptimal, with dimension-dependent excess risk improvements offered via known improper procedures.

In our fourth contribution, we investigate improperness in the linear regression problem with the squared loss, without imposing any assumptions on the distribution of the covariates and imposing a minimal assumption on the conditional distribution of the response variable. We first establish the in-expectation optimality of the truncated least squares estimator and then, we show that it can fail with constant probability. We conclude by proposing a deviation-optimal procedure. The considered setup admits heavy-tailed distributions while falling outside the scope of the typically studied procedures for heavy-tailed linear regression.

Authors: Vaskevicius, T

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: linear prediction; local Rademacher complexities; improper prediction; iterative regularization; robustness; distribution-free regression; concentration; linear regression
• Subjects: Learning theory; Mathematical statistics