Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing
This work provides a solution for optimization under more realistic, unbounded noise conditions, which is incremental as it extends existing techniques to a broader noise model.
The paper tackles the problem of minimizing a convex objective function when only a noisy, potentially nonconvex approximation is available, by developing a polynomial-time algorithm using simulated annealing with stochastic gradient Langevin dynamics to handle noise that scales with the function value. It achieves an approximate minimizer for this generalized noise model, addressing a limitation where prior methods required uniformly-bounded noise.
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 $αF(x) + β$ for some $α, β> 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.