Stochastic Mirror Descent in Variationally Coherent Optimization Problems
In this paper, we examine a class of non-convex stochastic optimization problems which we call variationally coherent, and which properly includes pseudo-/quasiconvex 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-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.
This paper analyzes the stochastic mirror descent (SMD) algorithm for a specific class of non-convex functions the variational coherence (VC) assumption. The authors study mirror descent by establishing a correspondence between the SMD iterates to an ordinary differential equation. They introduce a new divergence measure named Fenchel coupling and exploit its monotonicity property (due to the VC assumption) to demonstrate the SMD algorithm decreases its objective value until it gets close to the optimum.
The paper is clearly written and - omitting certain details -the proof is relatively easy to follow. The paper however has some significant problems in its presentation:
1) Interest for machine learning community: The main contribution of this paper is a proof of asymptotic convergence of SMD for certain non-convex functions. Although this is an interesting result for the optimization community, I’m however not sure this will be of a broad interest for the ML community which is typically more interested in deriving convergence rates. The authors do not give examples of ML problems where this new analysis could be relevant. There is also no experiment results. Can you please try to address this issue in the rebuttal?
2) Related work: The paper does not cover existing work in optimization for non-convex functions, not does it cover prior work relating ODEs to numerical optimization. I think existing proofs of convergence for stochastic gradient descent and proximal methods should be mentioned, e.g. Ghadimi, Saeed, and Guanghui Lan. "Stochastic first-and zeroth-order methods for nonconvex stochastic programming." SIAM Journal on Optimization 23.4 (2013): 2341-2368.
For ODEs, see references in [18] as well as
Stochastic Approximation and Recursive Algorithms and Applications
Kushner, Harold, Yin, George
I’m sure the authors are familiar with this line of work so please cite it appropriately.
Fenchel coupling
The paper uses the Fenchel coupling to quantify the distance between primal and dual variables thereby serving as an energy function to prove convergence. Can the authors comment on the difficulty of directly using the discrete primal variable to prove convergence? e.g. using a proof similar to SGD for non-convex functions (Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming, Saeed Ghadimi, Guanghui Lan)
Can the authors comment on whether other types of divergences would be appropriate for the analysis? It seems to me that the monotonicity property is due to the variational coherence assumption (as can be seen in E 3.39 in the appendix), can you confirm this? If so, then I wonder if the role of the Fenchel coupling is really that important for the analysis to hold?
Convergence rate: As mentioned earlier, the ML community would probably be more interested in a convergence rate. Can the authors elaborate on the difficulty of establishing a rate using their ODE technique?
Theorem 3.4: This result was at first puzzling to me. It says that the SMD algorithm oscillates in a region near the optimum. This is known to happen for SGD with constant step-size while using a decreasing step size (+ assumptions mentioned in the paper) will then guarantee convergence to an optimum. Can the authors clarify this?
Analysis:
Page 5 appendix above line 92, should be sum_k \alpha_k = + \infty
Line 174: you are citing a book, could you give a more precise reference?
--------------
Post-rebuttal:
I find the answers in the rebuttal convincing and updated my recommendation score accordingly. Overall, I think the paper would benefit from some clarifications which I think is easily do-able between now and the camera ready version. This includes:
 
1) Importance of the Fenchel coupling. The use of the Fenchel coupling (instead of the commonly used Bregman divergence) is a nice trick to get convergence for the type of non-convex functions considered in the paper. Also the ODE technique used in this paper could potentially push the development of similar techniques for different optimization techniques so this could really be valuable for the ML community. The submitted version of the paper did not explain this well but the answer provided in the rebuttal is convincing. I would recommend developing this aspect even more in the revised version. 
2) Interest regarding the ML community, they should develop this more in the introduction. Adding experimental results as they promised to R3 would be valuable as well 
3) As R2 pointed out, the intuition behind the analysis is not always clear. Given the rather convincing answers in the rebuttal, I think the authors can easily improve this aspect in the revised version. 
4) Minor modifications: Fix the numbering and clarify the use of certain terms whose meaning might differ for different communities, e.g. linear decrease, last iterate.