Skip to yearly menu bar Skip to main content


Poster

Stochastic Mirror Descent in Variationally Coherent Optimization Problems

Zhengyuan Zhou · Panayotis Mertikopoulos · Nicholas Bambos · Stephen Boyd · Peter W Glynn

Pacific Ballroom #165

Keywords: [ Optimization ] [ Non-Convex Optimization ]


Abstract: In this paper, we examine a class of non-convex stochastic optimization problems which we call \emph{variationally coherent}, and which properly includes pseudo-/quasi-convex and star-convex optimization problems. To solve such problems, we focus on the widely used \ac{SMD} family of algorithms (which contains stochastic gradient descent as a special case), and we show that the last iterate of \ac{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-convexity nor 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.

Live content is unavailable. Log in and register to view live content