Stochastic First-Order Methods with Random Constraint Projection
针对目标函数为期望值、约束集为大量简单集合交集的凸优化问题，提出随机一阶方法框架，通过随机投影和随机约束更新，统一分析多种算法的收敛性，证明最优性误差以O(1/√k)速率下降，可行性误差以O(log k/k)速率下降。
We consider convex optimization problems with structures that are suitable for sequential treatment or online sampling. In particular, we focus on problems where the objective function is an expected value, and the constraint set is the intersection of a large number of simpler sets. We propose an algorithmic framework for stochastic first-order methods using random projection/proximal updates and random constraint updates, which contain as special cases several known algorithms as well as many new algorithms. To analyze the convergence of these algorithms in a unified manner, we prove a general coupled convergence theorem. It states that the convergence is obtained from an interplay between two coupled processes: progress toward feasibility and progress toward optimality. Under suitable stepsize assumptions, we show that the optimality error decreases at a rate of $\mathcal{O}(1/\sqrt{k})$ and the feasibility error decreases at a rate of $\mathcal{O}(\log k/k)$. We also consider a number of typical sampling processes for generating stochastic first-order information and random constraints, which are common in data-intensive applications, online learning, and simulation optimization. By using the coupled convergence theorem as a modular architecture, we are able to analyze the convergence of stochastic algorithms that use arbitrary combinations of these sampling processes.