# Robust empirical risk minimization via Newton's method

arXiv: https://arxiv.org/abs/2301.13192 · HTML: https://mlsanity.com/paper/2301.13192/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 30 Jan 2023.

## Builds on (most cited first, 16 of 16)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Faster Algorithms for High-Dimensional Robust Covariance Estimation](https://mlsanity.com/paper/1906.04661/) (2019)
- [Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries](https://mlsanity.com/paper/1605.07129/) (2016)
- [Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond](https://mlsanity.com/paper/1912.11071/) (2019)
- [Regularization, sparse recovery, and median-of-means tournaments](https://mlsanity.com/paper/1701.04112/) (2017)
- [A spectral algorithm for robust regression with subgaussian rates](https://mlsanity.com/paper/2007.06072/) (2020)

## Built on by (most cited first, 1 of 1)

- [Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing](https://mlsanity.com/paper/2403.10547/) (2024)

## Abstract (arXiv)

A new variant of Newton's method for empirical risk minimization is studied, where at each iteration of the optimization algorithm, the gradient and Hessian of the objective function are replaced by robust estimators taken from existing literature on robust mean estimation for multivariate data. After proving a general theorem about the convergence of successive iterates to a small ball around the population-level minimizer, consequences of the theory in generalized linear models are studied when data are generated from Huber's epsilon-contamination model and/or heavytailed distributions. An algorithm for obtaining robust Newton directions based on the conjugate gradient method is also proposed, which may be more appropriate for high-dimensional settings, and conjectures about the convergence of the resulting algorithm are offered. Compared to robust gradient descent, the proposed algorithm enjoys the faster rates of convergence for successive iterates often achieved by second-order algorithms for convex problems, i.e., quadratic convergence in a neighborhood of the optimum, with a stepsize that may be chosen adaptively via backtracking linesearch.