Efficient Stochastic Oracle Based Algorithms for Stochastic Programming and Large Scale Convex Optimization

基于随机规划和大规模凸优化的高效随机 Oracle 算法

• 批准号: 0914785
• 负责人: Alexander Shapiro
• 金额: $ 32.74万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-15 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914785&HistoricalAwards=false
• 关键词: Efficient; Stochastic; Oracle; Based; Algorithms

The proposed research is aimed at developing computational techniques for handling two classes of complex convex problems. The first is Stochastic Programming, where objective and the constraints are given implicitly, as expectations over stochastic uncertain data, and thus are difficult to compute.The second class is formed by large-scale well-structured deterministic convex programs like those of Linear or Semidefinite Programming, the difficulty coming from huge problem sizes; e.g., LP's with just few thousands of variables and constraints and dense constraint matrices (arising, e.g., in Compressed Sensing and Machine Learning), or typical Semidefinite programs of similar sizes, are often beyond the grasp of the state-of-the-art solvers. The proposed research is intended to treat both these problem classes simultaneously, reducing them to variational inequalities with monotone operators represented by unbiased easy-to-compute stochastic oracles. These oracles arise naturally in the context of Stochastic Programming and can be constructed (e.g., via randomizing matrix-vector multiplications) in the case of large-scale LP's and SDP's. In order to solve the resulting stochastic variational inequalities it is proposed to employ recently developed algorithms (Robust Mirror Descent Stochastic Approximation and Stochastic Mirror Prox) which, under favorable circumstances, exhibit nearly dimension-independent and theoretically unimprovable in the large scale case rate of convergence.The last two decades have witnessed dramatic progress in techniques for solving convex optimization problems -- progress which by some estimates led to 1.000.000-fold performance growth, the factor nearly equally contributed by advances in algorithms and by increase in hardware power. In spite of this progress, a significant gap between what is needed by applications and what can be routinely solved by the state-of-the-art convex programming algorithms still persists, especially when the problems to be processed are intrinsically difficult. The proposed research is aimed at bridging the above gap by developing novel, more powerful than the existing alternatives, computational techniques based on systematic replacement of difficult to compute in the large scale case quantities, like matrix-vector products involving huge matrices, with relatively easy to compute randomized estimates of these quantities. Coupled with carefully designed stochastic type algorithms, this allows to solve huge problems, unaccessible by currently available deterministic algorithms, in a reasonable time with a reasonable accuracy by observing only a small portion of the data. This can be of paramount importance, e.g., for various applications of machine learning techniques where the amount of available data by far too large for direct processing. Some preliminary theoretical and numerical results are very encouraging and suggest that the proposed avenue of research ishighly promising, and if successful the proposed research will advance optimization theory and practice by enriching the algorithmic know-howrelated to processing complex optimization problems.

这项研究的目的是开发处理两类复杂凸性问题的计算技术。第一类是随机规划，其中目标和约束是隐式给定的，就像随机不确定数据上的期望一样，因此很难计算。第二类是由结构良好的确定凸规划形成的，比如线性规划或半定规划，困难来自于巨大的问题规模；例如，只有几千个变量和约束和密集约束矩阵的线性规划(LP)，或者类似规模的典型半定规划，往往超出了最先进的求解器的能力。所提出的研究旨在同时处理这两类问题，将它们归结为由无偏易计算的随机预言所表示的单调算子的变分不等式。这些预言自然出现在随机编程的环境中，并且可以在大规模LP和SDP的情况下构造(例如，通过随机化矩阵-向量乘法)。为了解决由此产生的随机变分不等，建议使用最近开发的算法(稳健镜像下降随机逼近和随机镜像投影)，它们在有利的情况下表现出几乎与维度无关，并且在大规模收敛速度理论上不可改进。过去20年见证了解决凸优化问题的技术的巨大进步--据某些估计，该进步导致性能增长1.000.000倍，算法的进步和硬件能力的提高对这一因素的贡献几乎相等。尽管取得了这一进展，但在应用程序所需要的东西与最先进的凸规划算法可以常规解决的东西之间仍然存在着显著的差距，特别是当要处理的问题本质上是困难的时候。拟议的研究旨在通过开发新的、比现有替代方案更强大的计算技术来弥合上述差距，该计算技术基于系统地替换大规模情况下难以计算的量，如涉及巨大矩阵的矩阵-向量积，这些量的随机估计相对容易计算。再加上精心设计的随机型算法，这允许通过只观察一小部分数据，在合理的时间内以合理的精度解决当前可用的确定性算法无法解决的巨大问题。这可能是极其重要的，例如对于机器学习技术的各种应用来说，其中可用的数据量对于直接处理来说太大了。一些初步的理论和数值结果非常令人鼓舞，表明所提出的研究途径前景光明，如果成功，所提出的研究将丰富与处理复杂优化问题相关的算法知识，从而促进优化理论和实践的发展。