Convex Optimization with Nonconvex Oracles

Oren Mangoubi, Nisheeth K. Vishnoi

Abstract

Traditional convex optimization assumes a well-behaved "bowl-shaped" landscape. However, real-world applications often involve "noisy oracles" where measurements are nonconvex and subject to multiplicative noise—error that increases with the function's value. This paper introduces the first polynomial-time algorithm to solve this problem. By combining Simulated Annealing with Stochastic Gradient Langevin Dynamics (SGLD), the algorithm effectively "jumps" out of deep local minima in high-noise regions and settles into the global minimum as noise diminishes near the optimum.

Introduction: The Challenge of Multiplicative Noise

In many engineering and machine learning tasks, we do not have direct access to a smooth convex function $F$. Instead, we interact with a noisy approximation $\hat{F}$. While previous work often assumed additive, bounded noise, many practical scenarios—such as Monte Carlo simulations or solving complex differential equations—exhibit multiplicative noise. In these cases, the error is proportional to the function's value, transforming a simple convex bowl into a treacherous landscape filled with deep, unbounded local minima.

Comparison of optimization trajectories on a noisy landscape. (c) shows a chain getting trapped in a local minimum, while (a), (b), and (d) illustrate how varying noise and temperature facilitate exploration and descent.

Standard gradient-based methods typically fail here, getting trapped in "potholes" far from the true global minimum. This creates a "temperature dilemma": a chain that is too "cold" gets stuck immediately, while one that is too "hot" cannot concentrate at the minimum.

Methodology: SGLD and Simulated Annealing

To overcome these local traps, the authors propose a multi-epoch algorithm that leverages two key techniques:

  1. Stochastic Gradient Langevin Dynamics (SGLD): By adding Gaussian noise to gradient descent steps, the algorithm can escape small local minima. The "temperature" of this noise determines the scale of the jumps.
  2. Simulated Annealing: The algorithm operates in stages (epochs). It begins at a high temperature to bounce out of deep minima in high-value (high-noise) regions. As it approaches the global minimum, where multiplicative noise is naturally lower, the temperature is reduced to allow for precise convergence.

For non-differentiable oracles, the authors employ Gaussian Smoothing, estimating gradients by sampling points around the current position to "blur" the jagged edges of the noise.

Theoretical Framework: Stability and Hitting Times

A major challenge in proving convergence for nonconvex oracles is ensuring the algorithm doesn't get stuck indefinitely. The authors utilize the concept of the Cheeger constant to bound the "hitting time"—the time required to move from a suboptimal region to a better one.

Level sets of a function with multiple local minima. The theoretical analysis focuses on the difficulty of moving between these regions (e.g., from $x^\circ$ toward $x^*$) as a function of noise levels $\beta$.

They demonstrate that the level sets of the noisy oracle remain "stable" enough relative to the underlying convex function. This stability ensures that the algorithm can transition between sets (as shown in Figure 1) and eventually concentrate around the global optimum $x^*$. Smart initialization—starting each new epoch near the best point found in the previous one—further prevents the algorithm from drifting back into high-noise territory.

Key Results and Complexity

The paper provides the first rigorous proof that this specific multiplicative noise model can be solved in polynomial time without requiring strong convexity. Key findings include:

  • Noise Tolerance: The algorithm is robust as long as the multiplicative noise coefficient $\alpha$ is $O(1/d)$ and additive noise $\beta$ is $O(\epsilon/d)$, where $d$ is the problem dimension.
  • Efficiency: Computational complexity is polynomial with respect to dimension ($d$), search radius ($R$), and target accuracy ($1/\epsilon$).
  • Theoretical Rigor: While the work is primarily theoretical and lacks empirical testing on standard datasets like MNIST, it establishes a foundational complexity bound for a previously unsolved class of optimization problems.

Conclusion and Future Directions

While this work establishes a theoretical foundation for optimization with nonconvex oracles, several avenues for future research remain. The current complexity bounds may be conservative, and future refinements could improve practical performance. Additionally, the framework might be extendable to broader classes of nonconvex functions with specific saddle-point properties, further bridging the gap between convex theory and nonconvex reality.

Summary updated

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.
BibTeX
@misc{mangoubi2017convex,
  author = {Oren Mangoubi and Nisheeth K. Vishnoi},
  title = {{Convex Optimization with Nonconvex Oracles}},
  year = {2017},
  eprint = {1711.02621},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.02621},
}
Figure