Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance

By Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis R. Bach, Alessandro Rudi. 2019

58 citations recorded by the source corpus.

We consider learning methods based on the regularization of a convex empirical risk by a squared Hilbertian norm, a setting that includes linear predictors and non-linear predictors through positive-definite kernels. In order to go beyond the generic analysis leading to convergence rates of the excess risk as $O(1/\sqrt{n})$ from $n$ observations, we assume that the individual losses are self-concordant, that is, their third-order derivatives are bounded by their second-order derivatives. This setting includes least-squares, as well as all generalized linear models such as logistic and softmax regression. For this class of losses, we provide a bias-variance decomposition and show that the assumptions commonly made in least-squares regression, such as the source and capacity conditions, can be adapted to obtain fast non-asymptotic rates of convergence by improving the bias terms, the variance terms or both.

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Functions satisfying self-concordance include commonly used losses such as the Huber loss [44], smoothed hinge loss [72] and under a generalized definition of selfconcordance, the logistic loss [2].”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, methodology): “[23] Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis Bach, and Alessandro Rudi.”
Finite-sample Analysis of M-estimators using Self-concordance (2018, methodology): “In a nutshell, [36] proves asymptotically near-optimal bounds Õ(deff/n) on the “variance” term corresponding to the excess risk L(θ̂λ,n)−L(θλ), and the additional “bias” term L(θλ) − L(θ), under condition (47), and without extra conditions in the vein of those in [2].”