Abstract
This paper provides a rigorous mathematical framework for optimizing "approximately convex" functions—functions that exhibit a global convex structure but are perturbed by local "ripples," noise, or discontinuities. While Simulated Annealing (SA) is a widely used heuristic for such problems, it often lacks formal performance guarantees. The authors bridge this gap by proving that a randomized algorithm based on SA and Hit-and-Run sampling can efficiently find global minima in polynomial time using only zeroth-order information (function evaluations). By extending the theory of log-concave sampling to approximately log-concave distributions, the paper establishes new complexity bounds for both deterministic and stochastic zeroth-order optimization.
Introduction
In mathematical optimization, convexity is a highly desirable property because it ensures that any local minimum is also a global minimum. However, many practical applications involve functions that are only "mostly" convex. These functions may contain small local traps, stochastic noise, or minor discontinuities that cause standard gradient-based methods to fail by getting stuck in the first local dip they encounter.
Simulated Annealing (SA) has long been the preferred heuristic for navigating such landscapes. By maintaining a "temperature" that allows the search to move away from local minima early in the process, SA explores the global structure before converging. This paper, "Escaping the Local Minima via Simulated Annealing," provides the theoretical foundation necessary to turn this heuristic into a provably efficient algorithm for approximately convex functions.
Problem Formulation: Beyond Perfect Convexity
The authors target the problem of zeroth-order optimization, where the optimizer can only query the function value $f(x)$ at any point $x$ within a convex set $\mathcal{K}$, rather than having access to gradients or Hessians.
The core challenge is the presence of non-convex perturbations. The paper defines an "approximately convex" function as one that stays within a small distance (relative to the dimension $n$) of a hidden convex function. In such a landscape, local search methods are ineffective. The goal is to find an $\epsilon$-minimizer of $f$ in a number of queries that scales polynomially with the dimension $n$ and the desired accuracy.
The Proposed Method
The authors propose a randomized algorithm that integrates two primary mechanisms:
- Simulated Annealing: The algorithm employs a cooling schedule. At high temperatures, the search distribution is nearly uniform over the search space; as the temperature decreases, the distribution concentrates around the global minimum.
- Hit-and-Run Sampling: To sample from the distribution at each temperature stage, the algorithm uses a "Hit-and-Run" random walk. This involves picking a random direction from the current point, defining a line through the search space, and sampling a new point along that line.
Technical Innovations
To make this approach robust, the authors introduced several key innovations:
- Approximate Log-Concavity: They proved that the Hit-and-Run walk "mixes" (reaches its target distribution) quickly even when the target distribution is only approximately log-concave. This is a significant extension of previous sampling theory which required strict log-concavity.
- Unidimensional Rejection Sampler: Standard Hit-and-Run implementations often use binary search to find the next point on a line, a method that fails if the function is non-convex or discontinuous. The authors developed a new rejection sampler that can navigate local "bumps" on the 1D line without getting stuck.
- Warm Starts: To maintain polynomial complexity, the algorithm uses samples from the previous (warmer) temperature stage to "warm start" the next stage, ensuring the random walk does not have to start from scratch as the distribution narrows.
Theoretical Results and Complexity
The paper's primary contribution is the establishment of formal complexity bounds for this class of optimization:
- General Complexity: For an approximately convex function in $n$ dimensions, the algorithm requires at most $O^*(n^{4.5})$ function evaluations to reach an $\epsilon$-minimizer.
- Stochastic Optimization: In scenarios where function evaluations are noisy (stochastic zeroth-order optimization), the complexity is $O^*(n^{7.5} \epsilon^{-2})$. At the time of publication, this represented the state-of-the-art complexity for this problem class.
These results demonstrate that the algorithm is "essentially immune" to local minima, provided the non-convexity remains within the defined theoretical bounds.
Applications and Implications
While theoretical in nature, the paper outlines several practical domains where this framework applies:
- Private Data Computation: Analyzing sensitive datasets (e.g., medical records) where noise is intentionally added to preserve privacy (Differential Privacy).
- Two-Stage Stochastic Programming: Solving complex decision-making problems under uncertainty.
- Online Learning: Optimizing regret bounds in environments with non-smooth reward functions.
Limitations and Future Work
The authors note that while the complexity is polynomial, the exponents ($n^{4.5}$ and $n^{7.5}$) suggest that the algorithm may still be slow for extremely high-dimensional problems, such as deep learning models with millions of parameters. Additionally, the requirement for a membership oracle for the convex set $\mathcal{K}$ limits the algorithm to bounded search spaces.
Future research directions include tightening the stochastic bounds by removing the "artificial" $n^2$ factor introduced by the union bound over the net, potentially through more advanced chaining arguments. The authors also suggest further exploration of functions where non-convexity is high in the periphery but decays as the search approaches the optimum.
Summary updated