# Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions

arXiv: https://arxiv.org/abs/1501.07242 · HTML: https://mlsanity.com/paper/1501.07242/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2015.

## Built on by (most cited first, 10 of 10)

- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [A Second-Order Method for Stochastic Bandit Convex Optimisation](https://mlsanity.com/paper/2302.05371/) (2023)
- [Learning (Approximately) Equivariant Networks via Constrained Optimization](https://mlsanity.com/paper/2505.13631/) (2025)
- [Spectral risk-based learning using unbounded losses](https://mlsanity.com/paper/2105.04816/) (2021)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles](https://mlsanity.com/paper/2504.03626/) (2025)
- [Performance-Driven QUBO for Recommender Systems on Quantum Annealers](https://mlsanity.com/paper/2410.15272/) (2024)
- [Denoising data using convex relaxations](https://mlsanity.com/paper/2605.02327/) (2026)
- [Global Convergence of Sampling-Based Nonconvex Optimization through Diffusion-Style Smoothing](https://mlsanity.com/paper/2605.16520/) (2026)

## Abstract (arXiv)

We consider the problem of optimizing an approximately convex function over a bounded convex set in ℝn using only function evaluations. The problem is reduced to sampling from an approximately log-concave distribution using the Hit-and-Run method, which is shown to have the same O^* complexity as sampling from log-concave distributions. In addition to extend the analysis for log-concave distributions to approximate log-concave distributions, the implementation of the 1-dimensional sampler of the Hit-and-Run walk requires new methods and analysis. The algorithm then is based on simulated annealing which does not relies on first order conditions which makes it essentially immune to local minima. We then apply the method to different motivating problems. In the context of zeroth order stochastic convex optimization, the proposed method produces an ε-minimizer after O^*(n7.5ε-2) noisy function evaluations by inducing a O(ε/n)-approximately log concave distribution. We also consider in detail the case when the "amount of non-convexity" decays towards the optimum of the function. Other applications of the method discussed in this work include private computation of empirical risk minimizers, two-stage stochastic programming, and approximate dynamic programming for online learning.