Title: Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing,
Abstract: We consider the problem of minimizing a convex objective function $F$ when
one can only evaluate its noisy approximation $\hat{F}$. Unless one assumes
some structure on the noise, $\hat{F}$ may be an arbitrary nonconvex function,
making the task of minimizing $F$ intractable. To overcome this, prior work has
often focused on the case when $F(x)-\hat{F}(x)$ is uniformly-bounded. In this
paper we study the more general case when the noise has magnitude $\alpha F(x)
+ \beta$ for some $\alpha, \beta > 0$, and present a polynomial time algorithm
that finds an approximate minimizer of $F$ for this noise model. Previously,
Markov chains, such as the stochastic gradient Langevin dynamics, have been
used to arrive at approximate solutions to these optimization problems.
However, for the noise model considered in this paper, no single temperature
allows such a Markov chain to both mix quickly and concentrate near the global
minimizer. We bypass this by combining "simulated annealing" with the
stochastic gradient Langevin dynamics, and gradually decreasing the temperature
of the chain in order to approach the global minimizer. As a corollary one can
approximately minimize a nonconvex function that is close to a convex function;
however, the closeness can deteriorate as one moves away from the optimum.