[C32] - Stochastic mirror descent in variationally coherent optimization problems

Z. Zhou, P. Mertikopoulos, N. Bambos, S. Boyd, and P. W. Glynn. In NeurIPS '17: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.


In this paper, we examine a class of non-convex stochastic optimization problems which we call variationally coherent, and which properly includes pseudo-, quasi-, and star-convex optimization problems. To solve such problems, we focus on the widely used stochastic mirror descent (SMD) family of algorithms (which contains stochastic gradient descent as a special case), and we show that the last iterate of SMD converges to the problem’s solution set with probability 1. This result contributes to the landscape of non-convex stochastic optimization by clarifying that neither pseudo-, quasi-, or star-convexity is essential for (almost sure) global convergence; rather, variational coherence, a much weaker requirement, suffices. Characterization of convergence rates for the subclass of strongly variationally coherent optimization problems as well as simulation results are also presented.

Nifty tech tag lists fromĀ Wouter Beeftink