Provable Training Set Debugging for Linear Regression
Preprint
Abstract
We investigate problems in penalized $M$-estimation, inspired by applications in machine learning debugging. Data are collected from two pools, one containing data with possibly contaminated labels, and the other which is known to contain only cleanly labeled points. We first formulate a general statistical algorithm for identifying buggy points and provide rigorous theoretical guarantees under the assumption that the data follow a linear model. We then present two case studies to illustrate the results of our general theory and the dependence of our estimator on clean versus buggy points. We further propose an algorithm for tuning parameter selection of our Lasso-based algorithm and provide corresponding theoretical guarantees. Finally, we consider a two-person "game" played between a bug generator and a debugger, where the debugger can augment the contaminated data set with cleanly labeled versions of points in the original data pool. We establish a theoretical result showing a sufficient condition under which the bug generator can always fool the debugger. Nonetheless, we provide empirical results showing that such a situation may not occur in practice, making it possible for natural augmentation strategies combined with our Lasso debugging algorithm to succeed.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- A class of algorithms for mixed-integer bilevel min–max optimizationJournal of Global Optimization, 2015
- Corrupted Sensing: Novel Guarantees for Separating Structured SignalsIEEE Transactions on Information Theory, 2014
- An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptionsComputers & Operations Research, 2014
- Robust Lasso With Missing and Grossly Corrupted ObservationsIEEE Transactions on Information Theory, 2012
- Introduction to the non-asymptotic analysis of random matrices2012
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)IEEE Transactions on Information Theory, 2009
- A Matrix Handbook for Statisticians2007
- Computing LTS Regression for Large Data SetsData Mining and Knowledge Discovery, 2006
- Topics in Matrix Analysis1991
- On Deriving the Inverse of a Sum of MatricesSIAM Review, 1981