Evolutionary Gradient Descent for Non-convex Optimization

Evolutionary Gradient Descent for Non-convex Optimization

Ke Xue, Chao Qian, Ling Xu, Xudong Fei

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 3221-3227. https://doi.org/10.24963/ijcai.2021/443

Non-convex optimization is often involved in artificial intelligence tasks, which may have many saddle points, and is NP-hard to solve. Evolutionary algorithms (EAs) are general-purpose derivative-free optimization algorithms with a good ability to find the global optimum, which can be naturally applied to non-convex optimization. Their performance is, however, limited due to low efficiency. Gradient descent (GD) runs efficiently, but only converges to a first-order stationary point, which may be a saddle point and thus arbitrarily bad. Some recent efforts have been put into combining EAs and GD. However, previous works either utilized only a specific component of EAs, or just combined them heuristically without theoretical guarantee. In this paper, we propose an evolutionary GD (EGD) algorithm by combining typical components, i.e., population and mutation, of EAs with GD. We prove that EGD can converge to a second-order stationary point by escaping the saddle points, and is more efficient than previous algorithms. Empirical results on non-convex synthetic functions as well as reinforcement learning (RL) tasks also show its superiority.
Keywords:
Machine Learning: Evolutionary Learning
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Heuristic Search and Machine Learning