Robust supervised learning with coordinate gradient descent
From MaRDI portal
Abstract: This paper considers the problem of supervised learning with linear methods when both features and labels can be corrupted, either in the form of heavy tailed data and/or corrupted rows. We introduce a combination of coordinate gradient descent as a learning algorithm together with robust estimators of the partial derivatives. This leads to robust statistical learning methods that have a numerical complexity nearly identical to non-robust ones based on empirical risk minimization. The main idea is simple: while robust learning with gradient descent requires the computational cost of robustly estimating the whole gradient to update all parameters, a parameter can be updated immediately using a robust estimator of a single partial derivative in coordinate gradient descent. We prove upper bounds on the generalization error of the algorithms derived from this idea, that control both the optimization and statistical errors with and without a strong convexity assumption of the risk. Finally, we propose an efficient implementation of this approach in a new python library called linlearn, and demonstrate through extensive numerical experiments that our approach introduces a new interesting compromise between robustness, statistical performance and numerical efficiency for this problem.
Recommendations
- Efficient learning with robust gradient descent
- Robustness of learning algorithms using hinge loss with outlier indicators
- Efficient algorithms and lower bounds for robust linear regression
- Robust machine learning by median-of-means: theory and practice
- Robust estimation via generalized quasi-gradients
Cites work
- scientific article; zbMATH DE number 3870398 (Why is no real title available?)
- scientific article; zbMATH DE number 5654889 (Why is no real title available?)
- scientific article; zbMATH DE number 3954047 (Why is no real title available?)
- scientific article; zbMATH DE number 3684698 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 1304261 (Why is no real title available?)
- scientific article; zbMATH DE number 7370601 (Why is no real title available?)
- scientific article; zbMATH DE number 7307489 (Why is no real title available?)
- scientific article; zbMATH DE number 6253925 (Why is no real title available?)
- scientific article; zbMATH DE number 5251637 (Why is no real title available?)
- scientific article; zbMATH DE number 3303655 (Why is no real title available?)
- scientific article; zbMATH DE number 3320125 (Why is no real title available?)
- A General Qualitative Definition of Robustness
- A generalized Catoni's M-estimator under finite \(\alpha\)-th moment assumption with \(\alpha \in (1,2)\)
- Analysis of Extreme Values
- Asymptotic Statistics
- Bandits With Heavy Tail
- Block coordinate descent algorithms for large-scale sparse multiclass classification
- Challenging the empirical mean and empirical variance: a deviation study
- Concentration inequalities. A nonasymptotic theory of independence
- Convex optimization: algorithms and complexity
- Coordinate descent algorithms
- Coordinate descent algorithms for lasso penalized regression
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficient algorithms and lower bounds for robust linear regression
- Efficient learning with robust gradient descent
- Empirical risk minimization for heavy-tailed losses
- Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
- Geometric median and robust estimation in Banach spaces
- Introduction to algorithms.
- Introductory lectures on convex optimization. A basic course.
- Learning Halfspaces with Malicious Noise
- Learning from untrusted data
- Local Rademacher complexities
- Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
- Loss minimization and parameter estimation with heavy tails
- Mean estimation and regression under heavy-tailed distributions: A survey
- Mean estimation with sub-Gaussian rates in polynomial time
- Minimization of functions having Lipschitz continuous first partial derivatives
- Model Selection and Estimation in Regression with Grouped Variables
- On depth and deep points: A calculus.
- On faster convergence of cyclic block coordinate descent-type methods for strongly convex minimization
- On the convergence of block coordinate descent type methods
- Random generation of combinatorial structures from a uniform distribution
- Risk bounds for statistical learning
- Robust Estimation of a Location Parameter
- Robust Estimation via Robust Gradient Estimation
- Robust Statistics
- Robust classification via MOM minimization
- Robust covariance and scatter matrix estimation under Huber's contamination model
- Robust estimators in high-dimensions without the computational intractability
- Robust machine learning by median-of-means: theory and practice
- Robust multivariate mean estimation: the optimality of trimmed mean
- Robust principal component analysis?
- Robust regression via mutivariate regression depth
- Robust sub-Gaussian estimation of a mean vector in nearly linear time
- Scikit-learn: machine learning in Python
- Sparse recovery by reduced variance stochastic approximation
- Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries
- Sub-Gaussian estimators of the mean of a random vector
- Sub-Gaussian mean estimators
- The 1972 Wald Lecture Robust Statistics: A Review
- The ``automatic robustness of minimum distance functionals
- The multivariate L 1 -median and associated data depth
- The space complexity of approximating the frequency moments
Cited in
(4)
This page was built for publication: Robust supervised learning with coordinate gradient descent
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172182)
