Trimmed Statistical Estimation via Variance Reduction
Authors:
- 1 February 2020
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 45 (1) , 292-322
Abstract
In this paper, we show how to transform any optimization problem that arises from fitting a machine learning model into one that (1) detects and removes contaminated data from the training set while (2) simultaneously fitting the trimmed model on the uncontaminated data that remains. To solve the resulting nonconvex optimization problem, we introduce a fast stochastic proximal-gradient algorithm that incorporates prior knowledge through nonsmooth regularization. For data sets of size n, our approach requires O(n2/3/ℇ) gradient evaluations to reach ℇ-accuracy, and when a certain error bound holds, the complexity improves to O(κn2/3 log(1/ℇ)), where κ is a “condition number.” These rates are n1/3 times better than those achieved by typical, nonstochastic methods.Keywords
This publication has 30 references indexed in Scilit:
- On the Least Trimmed Squares EstimatorAlgorithmica, 2012
- Nearly unbiased variable selection under minimax concave penaltyThe Annals of Statistics, 2010
- Clarke Subgradients of Stratifiable FunctionsSIAM Journal on Optimization, 2007
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle PropertiesJournal of the American Statistical Association, 2001
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998
- Error bounds and convergence analysis of feasible descent methods: a general approachAnnals of Operations Research, 1993
- Multivariate Estimation with High Breakdown Point1985
- Least Median of Squares RegressionJournal of the American Statistical Association, 1984
- Random sample consensusCommunications of the ACM, 1981
- Trimmed Least Squares Estimation in the Linear ModelJournal of the American Statistical Association, 1980