Learning with a convex loss function has been a dominating paradigm for many years. It remains an interesting question how non-convex loss functions help improve the generalization of learning with broad applicability. In this paper, we study a family of objective functions formed by truncating traditional loss functions, which is applicable to both shallow learning and deep learning. Truncating loss functions has potential to be less vulnerable and more robust to large noise in observations that could be adversarial. More importantly, it is a generic technique without assuming the knowledge of noise distribution. To justify non-convex learning with truncated losses, we establish excess risk bounds of empirical risk minimization based on truncated losses for heavy-tailed output, and statistical error of an approximate stationary point found by stochastic gradient descent (SGD) method. Our experiments for shallow and deep learning for regression with outliers, corrupted data and heavy-tailed noise further justify the proposed method.
@cite_3 proposed a method for learning a linear model based on solving a non-convex min-max problem and proved an excess risk bound of @math for heavy-tailed data with a bounded fourth-order moment for noise and a bounded fourth-order moment for input. They proposed a polynomial time algorithm based heuristics to solve the non-convex min-max problem. However, it is unclear whether the approximate solution found by the heuristics-based approach satisfy the claimed excess risk bound. There also exist a bulk of studies focusing on understanding the excess risk bound of (regularized) ERM under certain conditions for unbounded loss (e.g., small ball condition, Bernstein condition, @math -central condition, etc.) or in restricted settings (e.g., linear least-squares regression) .
@cite_3
2949125143
Subsampling methods have been recently proposed to speed up least squares estimation in large scale settings. However, these algorithms are typically not robust to outliers or corruptions in the observed covariates. The concept of influence that was developed for regression diagnostics can be used to detect such corrupted observations as shown in this paper. This property of influence -- for which we also develop a randomized approximation -- motivates our proposed subsampling algorithm for large scale corrupted linear regression which limits the influence of data points since highly influential points contribute most to the residual error. Under a general model of corrupted observations, we show theoretically and empirically on a variety of simulated and real datasets that our algorithm improves over the current state-of-the-art approximation schemes for ordinary least squares.