nips nips2008 nips2008-202 nips2008-202-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Huan Xu, Constantine Caramanis, Shie Mannor
Abstract: We consider robust least-squares regression with feature-wise disturbance. We show that this formulation leads to tractable convex optimization problems, and we exhibit a particular uncertainty set for which the robust problem is equivalent to 1 regularized regression (Lasso). This provides an interpretation of Lasso from a robust optimization perspective. We generalize this robust formulation to consider more general uncertainty sets, which all lead to tractable convex optimization problems. Therefore, we provide a new methodology for designing regression algorithms, which generalize known formulations. The advantage is that robustness to disturbance is a physical property that can be exploited: in addition to obtaining new formulations, we use it directly to show sparsity properties of Lasso, as well as to prove a general consistency result for robust regression problems, including Lasso, from a unified robustness perspective. 1
[1] L. Elden. Perturbation theory for the least-square problem with linear equality constraints. BIT, 24:472– 476, 1985.
[2] G. Golub and C. Van Loan. Matrix Computation. John Hopkins University Press, Baltimore, 1989.
[3] A. Tikhonov and V. Arsenin. Solution for Ill-Posed Problems. Wiley, New York, 1977.
[4] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58(1):267–288, 1996.
[5] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Annals of Statistics, 32(2):407–499, 2004.
[6] S. Chen, D. Donoho, and M. Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20(1):33–61, 1998.
[7] A. Feuer and A. Nemirovski. On sparse representation in pairs of bases. IEEE Transactions on Information Theory, 49(6):1579–1581, 2003.
[8] E. Cand` s, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly e incomplete frequency information. IEEE Transactions on Information Theory, 52(2):489–509, 2006.
[9] J. Tropp. Greed is good: Algorithmic results for sparse approximation. IEEE Transactions on Information Theory, 50(10):2231–2242, 2004.
[10] M. Wainwright. Sharp thresholds for noisy and high-dimensional recovery of sparsity using 1 -constrained quadratic programming. Technical Report Available from: http://www.stat.berkeley.edu/tech-reports/709.pdf, Department of Statistics, UC Berkeley, 2006.
[11] L. El Ghaoui and H. Lebret. Robust solutions to least-squares problems with uncertain data. SIAM Journal on Matrix Analysis and Applications, 18:1035–1064, 1997.
[12] A. Ben-Tal and A. Nemirovski. Robust solutions of uncertain linear programs. Operations Research Letters, 25(1):1–13, August 1999.
[13] D. Bertsimas and M. Sim. The price of robustness. Operations Research, 52(1):35–53, January 2004.
[14] P. Shivaswamy, C. Bhattacharyya, and A. Smola. Second order cone programming approaches for handling missing and uncertain data. Journal of Machine Learning Research, 7:1283–1314, July 2006.
[15] H. Xu, C. Caramanis, and S. Mannor. Robust regression and Lasso. http://arxiv.org/abs/0811.1790v1, 2008. Submitted, available from
[16] J. Tropp. Just relax: Convex programming methods for identifying sparse signals. IEEE Transactions on Information Theory, 51(3):1030–1051, 2006.
[17] F. Girosi. An equivalence between sparse approximation and support vector machines. Neural Computation, 10(6):1445–1480, 1998.
[18] R. R. Coifman and M. V. Wickerhauser. Entropy-based algorithms for best-basis selection. IEEE Transactions on Information Theory, 38(2):713–718, 1992.
[19] S. Mallat and Z. Zhang. Matching Pursuits with time-frequence dictionaries. IEEE Transactions on Signal Processing, 41(12):3397–3415, 1993.
[20] D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306, 2006.
[21] L. Devroye and L. Gy¨ rfi. Nonparametric Density Estimation: the l1 View. John Wiley & Sons, 1985. o 8