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

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

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 is highly promising, and if successful the proposed research will advance optimization theory and practice by enriching the algorithmic know-how related to processing complex optimization problems.