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

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

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.