Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm

Rishabh Dixit; Mert Gürbüzbalaban; Waheed U. Bajwa

首页> 外文期刊>IEEE Transactions on Information Theory >Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm

【24h】

Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm

机译：Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

Gradient-related first-order methods have become the workhorse of large-scale numerical optimization problems. Many of these problems involve nonconvex objective functions with multiple saddle points, which necessitates an understanding of the behavior of discrete trajectories of first-order methods within the geometrical landscape of these functions. This paper concerns convergence of first-order discrete methods to a local minimum of nonconvex optimization problems that comprise strict-saddle points within the geometrical landscape. To this end, it focuses on analysis of discrete gradient trajectories around saddle neighborhoods, derives sufficient conditions under which these trajectories can escape strict-saddle neighborhoods in linear time, explores the contractive and expansive dynamics of these trajectories in neighborhoods of strict-saddle points that are characterized by gradients of moderate magnitude, characterizes the non-curving nature of these trajectories, and highlights the inability of these trajectories to re-enter the neighborhoods around strict-saddle points after exiting them. Based on these insights and analyses, the paper then proposes a simple variant of the vanilla gradient descent algorithm, termed Curvature Conditioned Regularized Gradient Descent (CCRGD) algorithm, which utilizes a check for an initial boundary condition to ensure its trajectories can escape strict-saddle neighborhoods in linear time. Convergence analysis of the CCRGD algorithm, which includes its rate of convergence to a local minimum, is also presented in the paper. Numerical experiments are then provided on a test function as well as a low-rank matrix factorization problem to evaluate the efficacy of the proposed algorithm.

著录项

来源
《IEEE Transactions on Information Theory》 |2023年第4期|2556-2602|共47页
作者
Rishabh Dixit; Mert Gürbüzbalaban; Waheed U. Bajwa;
展开▼
作者单位

Department of Electrical and Computer Engineering, Rutgers University, New Brunswick, NJ, USA;

Departments of Electrical & Computer Engineering, Management Science and Information Systems, and Statistics, Rutgers University, New Brunswick, NJ, USA;

Departments of Electrical & Computer Engineering and Statistics, Rutgers University, New Brunswick, NJ, USA;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类通信;
关键词
Trajectory; Convergence; Optimization; Boundary conditions; Geometry; Perturbation methods; Sufficient conditions;

Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm

摘要

著录项

相关主题

期刊订阅