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.
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:
- 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.
- 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.
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