Statistical Optimization in High Dimensions

• 成果类型: Article
• 署名作者: Xu, Huan; Caramanis, Constantine; Mannor, Shie
• 署名单位: National University of Singapore; University of Texas System; University of Texas Austin; Technion Israel Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2016.1504
• 发表日期: 2016
• 页码: 958-979
• 关键词: robust; RISK

摘要

We consider optimization problems whose parameters are known only approximately, based on noisy samples. In large-scale applications, the number of samples one can collect is typically of the same order of (or even less than) the dimensionality of the problem. This so-called high-dimensional statistical regime has been the object of intense recent research in machine learning and statistics, primarily due to phenomena inherent to this regime, such as the fact that the noise one sees here often dwarfs the magnitude of the signal itself. While relevant in numerous important operations research and engineering optimization applications, 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. Our algorithms are motivated by three natural optimization objectives: minimizing the number of grossly violated constraints; maximizing the number of exactly satisfied constraints; and, finally, developing algorithms whose running time scales with the intrinsic dimension of a problem, as opposed to its observed dimension-a mismatch that, as we discuss in detail, can be dire in settings where constraints are meant to describe preferences of behaviors. The key ingredients of our algorithms are dimensionality reduction techniques from machine learning, robust optimization, and concentration of measure tools from statistics.