Averaging random projection: A fast online solution for large-scale constrained stochastic optimization

Abstract

Stochastic optimization finds wide application in signal processing, online learning, and network problems, especially problems processing large-scale data. We propose an Incremental Constraint Averaging Projection Method (ICAPM) that is tailored to optimization problems involving a large number of constraints. The ICAPM makes fast updates by taking sample gradients and averaging over random constraint projections. We provide a theoretical convergence and rate of convergence analysis for ICAPM. Our results suggests that averaging random projections significantly improves the stability of the solutions. For numerical tests, we apply the ICAPM to an online classification problem and a network consensus problem.