Global Non-convex Optimization with Discretized Diffusions
An Euler discretization of the Langevin diffusion is known to converge to the global minimizers of certain convex and non-convex optimization problems. We show that this property holds for any suitably smooth diffusion and that different diffusions are suitable for optimizing different classes of convex and non-convex functions. This allows us to design diffusions suitable for globally optimizing convex and non-convex functions not covered by the existing Langevin theory. Our non-asymptotic analysis delivers computable optimization and integration error bounds based on easily accessed properties of the objective and chosen diffusion. Central to our approach are new explicit Stein factor bounds on the solutions of Poisson equations. We complement these results with improved optimization guarantees for targets other than the standard Gibbs measure.
This paper studies nonconvex optimization problem using Euler discretization on Ito diffusions, and derives the convergence rate of the investigated discretized diffusions. Specifically, the authors apply Poisson equation to analyze the convergence of discretized diffusions in terms of expected function value and prove a convergence rate of O(1/\epsilon^2) under several seemingly stringent assumptions. In addition, the authors also give some examples that are not covered by existing Langevin theory but can be illustrated by the theory in this paper. I notice that the authors mentioned one recent work in the literature, i.e., [26], which is highly related to this submission. However, I didn’t find a careful comparison between this submission and [26] in the related work or the main theory section (Section 3). Since the O(1/epsilon^2) convergence results seems worse than the O(1/\epsilon) rate proved in [26],yet  this work makes more assumptions beyond the smooth and dissipativity assumptions, it is very important to discuss the connection and difference between this submission and [26] thoroughly.      The strengths of this paper are given as follows: 1. This paper studies a Euler discretization on general Ito diffusions, which is beyond the framework of conventional Langevin dynamics. 2. This paper presents some examples to showcase the applications of the main theory.   The weakness of this paper: 1. In [22], the convergence rate of SGLD contains a spectral gap which is exponential in dimension d and inverse temperature \gamma. Similarly, the result for GLD (the full gradient version) in [26] has also such a dependence on d and \gamma. Furthermore, there is a lower bound for the metastable exiting time of SDE for nonconvex functions in Bovier et al., (2004), which has exponential dependence on d and \gamma too. However, this paper seems to hide many factors including the spectral gap in the main theory. The authors should explicitly indicate these dependences and make a fair and thorough comparison with previous work. 2. The results for nonconvex optimization is claimed to be \mathcal{O}(1/\epsilon^2), while the complexity in [26] is \tilde(O)(1/\epsilon) for the same algorithm (GLD). The authors should explain why their result looks inferior to the existing work.  3. In Section 5, the authors just simply combine the argument in Theorem 3.1 and Proposition 3.4 in [22]. Some important discussions are missing, such as the optimal choice of the inverse temperature parameter \gamma, and how it affects the convergence rate. I believe the choice of \gamma will affect both the ergodicity and discretization results. Besides, the authors attempt to improve the expected suboptimality using non-Gibbs distributions. However, a simple quadratic example is not convincing enough, and the impacts of using non-Gibbs distributions on the ergodicity were not well explained. 4. The convergence rate highly depends on the parameter n, I would like to see some discussions on this parameter (use some examples or provide an upper bound).  5. In condition 3, the authors mention \tilde \mu_n(u_f) = \zeta_1. I noticed that the notation \tilde \mu_n(u_f) has appeared before in (2.6), are they the same? 6. A typo in Line 72: it is the inverse of spectral gap, i.e., \lambda^{-1} that is exponential in d and \gamma.  7. The organization can be improved, the authors are better to clearly state the assumptions on objective function, rather than write them with plain text.   Reference:  Bovier, A., Eckhoff, M., Gayrard, V. and Klein, M. (2004). Metastability in reversible diffusion processes i: Sharp asymptotics for capacities and exit times. Journal of the European Mathematical Society 6 399–424.  ===== After I read the authors' response, my concern on the comparison with [26] was addressed. Please incorporate the comparison with [26] in your response into the camera ready.