An Adaptive High Order Method for Finding Third-Order Critical Points of Nonconvex Optimization

It is well known that finding a global optimum is extremely challenging for nonconvex optimization. There are some recent efforts \cite{anandkumar2016efficient, cartis2018second, cartis2020sharp, chen2019high} regarding the optimization methods for computing higher-order critical points, which can e...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-08
Main Authors: Zhu, Xihua, Han, Jiangze, Jiang, Bo
Format: Article
Language:English
Subjects:
Algorithms
Critical point
Iterative methods
Optimization
Saddle points
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is well known that finding a global optimum is extremely challenging for nonconvex optimization. There are some recent efforts \cite{anandkumar2016efficient, cartis2018second, cartis2020sharp, chen2019high} regarding the optimization methods for computing higher-order critical points, which can exclude the so-called degenerate saddle points and reach a solution with better quality. Desipte theoretical development in \cite{anandkumar2016efficient, cartis2018second, cartis2020sharp, chen2019high}, the corresponding numerical experiments are missing. In this paper, we propose an implementable higher-order method, named adaptive high order method (AHOM), that aims to find the third-order critical points. This is achieved by solving an ``easier'' subproblem and incorporating the adaptive strategy of parameter-tuning in each iteration of the algorithm. The iteration complexity of the proposed method is established. Some preliminary numerical results are provided to show AHOM is able to escape the degenerate saddle points, where the second-order method could possibly get stuck.
ISSN:2331-8422