Statistical Optimization in High Dimensions

Huan Xu; Constantine Caramanis; Shie Mannor

Statistical Optimization in High Dimensions

Huan Xu, Constantine Caramanis, Shie Mannor ;

Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1332-1340, 2012.

Abstract

We consider optimization problems whose parameters are known only approximately, based on a noisy sample. Of particular interest is the high-dimensional regime, where the number of samples is roughly equal to the dimensionality of the problem, and the noise magnitude may greatly exceed the magnitude of the signal itself. This setup falls far outside the traditional scope of Robust and Stochastic optimization. We propose three algorithms to address this setting, combining ideas from statistics, machine learning, and robust optimization. In the important case where noise artificially increases the dimensionality of the parameters, we show that combining robust optimization and dimensionality reduction can result in high-quality solutions at greatly reduced computational cost.

Related Material

Download PDF

@InProceedings{pmlr-v22-xu12a, title = {Statistical Optimization in High Dimensions}, author = {Huan Xu and Constantine Caramanis and Shie Mannor}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1332--1340}, year = {2012}, editor = {Neil D. Lawrence and Mark Girolami}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/xu12a/xu12a.pdf}, url = {http://proceedings.mlr.press/v22/xu12a.html}, abstract = {We consider optimization problems whose parameters are known only approximately, based on a noisy sample. Of particular interest is the high-dimensional regime, where the number of samples is roughly equal to the dimensionality of the problem, and the noise magnitude may greatly exceed the magnitude of the signal itself. This setup falls far outside the traditional scope of Robust and Stochastic optimization. We propose three algorithms to address this setting, combining ideas from statistics, machine learning, and robust optimization. In the important case where noise artificially increases the dimensionality of the parameters, we show that combining robust optimization and dimensionality reduction can result in high-quality solutions at greatly reduced computational cost.} }

%0 Conference Paper %T Statistical Optimization in High Dimensions %A Huan Xu %A Constantine Caramanis %A Shie Mannor %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-xu12a %I PMLR %J Proceedings of Machine Learning Research %P 1332--1340 %U http://proceedings.mlr.press %V 22 %W PMLR %X We consider optimization problems whose parameters are known only approximately, based on a noisy sample. Of particular interest is the high-dimensional regime, where the number of samples is roughly equal to the dimensionality of the problem, and the noise magnitude may greatly exceed the magnitude of the signal itself. This setup falls far outside the traditional scope of Robust and Stochastic optimization. We propose three algorithms to address this setting, combining ideas from statistics, machine learning, and robust optimization. In the important case where noise artificially increases the dimensionality of the parameters, we show that combining robust optimization and dimensionality reduction can result in high-quality solutions at greatly reduced computational cost.

TY - CPAPER TI - Statistical Optimization in High Dimensions AU - Huan Xu AU - Constantine Caramanis AU - Shie Mannor BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics PY - 2012/03/21 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-xu12a PB - PMLR SP - 1332 DP - PMLR EP - 1340 L1 - http://proceedings.mlr.press/v22/xu12a/xu12a.pdf UR - http://proceedings.mlr.press/v22/xu12a.html AB - We consider optimization problems whose parameters are known only approximately, based on a noisy sample. Of particular interest is the high-dimensional regime, where the number of samples is roughly equal to the dimensionality of the problem, and the noise magnitude may greatly exceed the magnitude of the signal itself. This setup falls far outside the traditional scope of Robust and Stochastic optimization. We propose three algorithms to address this setting, combining ideas from statistics, machine learning, and robust optimization. In the important case where noise artificially increases the dimensionality of the parameters, we show that combining robust optimization and dimensionality reduction can result in high-quality solutions at greatly reduced computational cost. ER -

Xu, H., Caramanis, C. & Mannor, S.. (2012). Statistical Optimization in High Dimensions. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in PMLR 22:1332-1340