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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-xu12a, title = {Statistical Optimization in High Dimensions}, author = {Xu, Huan and Caramanis, Constantine and Mannor, Shie}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1332--1340}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, 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 = {https://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.} }
Endnote
%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 %P 1332--1340 %U https://proceedings.mlr.press/v22/xu12a.html %V 22 %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.
RIS
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 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-xu12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 1332 EP - 1340 L1 - http://proceedings.mlr.press/v22/xu12a/xu12a.pdf UR - https://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 -
APA
Xu, H., Caramanis, C. & Mannor, S.. (2012). Statistical Optimization in High Dimensions. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:1332-1340 Available from https://proceedings.mlr.press/v22/xu12a.html.

Related Material