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

Abstract

We consider the problem of optimizing an approximately convex function over a bounded convex set in ${\mathbb{R}}^n$ using only function evaluations. The problem is reduced to sampling from an \emph{approximately} log-concave distribution using the Hit-and-Run method, which is shown to have the same ${\mathcal{O}}^{\ast }$ 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 $\epsilon$-minimizer after ${\mathcal{O}}^{\ast }(n^{7.5}{\epsilon }^{-2})$ noisy function evaluations by inducing a $\mathcal{O}(\epsilon /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.

arXiv comment27 pages

References in corpus (1)

• On Zeroth-Order Stochastic Convex Optimization via Random Walks

Cited by in corpus (14)

• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Maximization of Approximately Submodular Functions
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition
• Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs
• Gradient-free prox-methods with inexact oracle for stochastic convex optimization problems on a simplex
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
• Distributed Zero-Order Optimization under Adversarial Noise
• Spectral risk-based learning using unbounded losses
• Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
• Watch and Learn: Optimizing from Revealed Preferences Feedback