Single Loop Gaussian Homotopy Method for Non-convex Optimization
Preprint
Abstract
The Gaussian homotopy (GH) method is a popular approach to finding better stationary points for non-convex optimization problems by gradually reducing a parameter value $t$, which changes the problem to be solved from an almost convex one to the original target one. Existing GH-based methods repeatedly call an iterative optimization solver to find a stationary point every time $t$ is updated, which incurs high computational costs. We propose a novel single loop framework for GH methods (SLGH) that updates the parameter $t$ and the optimization decision variables at the same. Computational complexity analysis is performed on the SLGH algorithm under various situations: either a gradient or gradient-free oracle of a GH function can be obtained for both deterministic and stochastic settings. The convergence rate of SLGH with a tuned hyperparameter becomes consistent with the convergence rate of gradient descent, even though the problem to be solved is gradually changed due to $t$. In numerical experiments, our SLGH algorithms show faster convergence than an existing double loop GH method while outperforming gradient descent-based methods in terms of finding a better solution.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Random Gradient-Free Minimization of Convex FunctionsFoundations of Computational Mathematics, 2015
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic ProgrammingSIAM Journal on Optimization, 2013
- Large Displacement Optical Flow: Descriptor Matching in Variational Motion EstimationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- The Effective Energy Transformation Scheme as a Special Continuation Approach to Global Optimization with Application to Molecular ConformationSIAM Journal on Optimization, 1996
- A Non-Interior-Point Continuation Method for Linear Complementarity ProblemsSIAM Journal on Matrix Analysis and Applications, 1993