Efficient learning with robust gradient descent

DOI10.1007/S10994-019-05802-5MaRDI QIDQ2320583zbMATH OpenOpenAlexFDO

Authors Matthew J. Holland, Kazushi Ikeda

Publication date 23 August 2019

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.00182

zbMATH Keywords

robust learningstatistical learning theorystochastic optimization

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Minimizing the empirical risk is a popular training strategy, but for learning tasks where the data may be noisy or heavy-tailed, one may require many observations in order to generalize well. To achieve better performance under less stringent requirements, we introduce a procedure which constructs a robust approximation of the risk gradient for use in an iterative learning routine. Using high-probability bounds on the excess risk of this algorithm, we show that our update does not deviate far from the ideal gradient-based update. Empirical tests using both controlled simulations and real-world benchmark data show that in diverse settings, the proposed procedure can learn more efficiently, using less resources (iterations and observations) while generalizing better.

Review text

Gradient descent is a very popular optimization method with wide applications to many machine learning problems. However, gradient descent may not generalize well if the training data is noisy or heavy-tailed. To address this defect, this paper proposes an efficient robust gradient descent method. The idea is to use a robust estimate of the risk gradient rather than the risk itself, which is achieved by a soft-truncation of errant values. The proposed algorithm enjoys the computation ease of gradient descent, and is backed up by both theoretical and experimental analyses.

Recommendations

• Robust supervised learning with coordinate gradient descent
• Excess risk bounds in robust empirical risk minimization
• Robustness and generalization
• Robust regression using biased objectives
• Robust estimation via generalized quasi-gradients

Cites work

• 10.1162/153244303321897690
• Adaptive subgradient methods for online learning and stochastic optimization
• Asymptotic Statistics
• Challenging the empirical mean and empirical variance: a deviation study
• Efficient distribution-free learning of probabilistic concepts
• Efficient learning with robust gradient descent
• Empirical risk minimization for heavy-tailed losses
• Fat-shattering and the learnability of real-valued functions
• Geometric median and robust estimation in Banach spaces
• scientific article; zbMATH DE number 428352 (Why is no real title available?)
• scientific article; zbMATH DE number 1416652 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• scientific article; zbMATH DE number 3281211 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Learning from MOM's principles: Le Cam's approach
• Loss minimization and parameter estimation with heavy tails
• Necessary and Sufficient Conditions for Differentiating under the Integral Sign
• Numerical Optimization
• Regularization, sparse recovery, and median-of-means tournaments
• Robust classification via MOM minimization
• Robust Estimation via Robust Gradient Estimation
• Robust regression using biased objectives
• Robust Statistics
• Scale-sensitive dimensions, uniform convergence, and learnability
• Stochastic dual coordinate ascent methods for regularized loss minimization
• Sub-Gaussian mean estimators
• The multivariate L ₁ -median and associated data depth

Cited in

(10)

• Efficient learning with robust gradient descent
• A machine learning efficient frontier
• scientific article; zbMATH DE number 1804101 (Why is no real title available?)
• Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
• Dynamical systems approach to outlier robust deep neural networks for regression
• scientific article; zbMATH DE number 7625199 (Why is no real title available?)
• Robust distributed multicategory angle-based classification for massive data
• Robust supervised learning with coordinate gradient descent
• Algorithms with gradient clipping for stochastic optimization with heavy-tailed noise
• Robust and computationally efficient gradient-based estimation

Describes a project that uses

Uses Software

• AdaGrad
• Adam

This page was built for publication: Efficient learning with robust gradient descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2320583)