Boundary conditions for linear exit time gradient trajectories around saddle points: analysis and algorithm

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

doi:10.1109/TIT.2022.3213607

Publications · Journal article · IEEE Trans. Inf. Theory 2023

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, 69(4), pp. 2556–2602, 2023.

Publisher (DOI)

In brief

Gradient descent can linger for a long time near saddle points of non-convex losses. The paper characterizes the initial conditions — boundary conditions — under which gradient trajectories leave a saddle neighborhood in linear time, and uses that analysis to design a method with linear exit-time guarantees.

Topics

Spectral & nonsmooth optimization

Cite

@article{dixit2023saddle,
  title   = {Boundary conditions for linear exit time gradient trajectories around saddle points: analysis and algorithm},
  author  = {Rishabh Dixit and Mert Gürbüzbalaban and Waheed U. Bajwa},
  year    = {2023},
  journal = {IEEE Transactions on Information Theory},
  volume  = {69(4)},
  pages   = {2556--2602},
  doi     = {10.1109/TIT.2022.3213607},
}

Relatedsame topics

Robustly stable accelerated momentum methods with a near-optimal L₂ gain and H∞ performance (Math. Oper. Res., 2025)
Approximating the real structured stability radius with Frobenius-norm bounded perturbations (SIAM J. Matrix Anal. Appl., 2017)
Polynomial root radius optimization with affine constraints (Math. Program., 2017)
Polynomial stabilization with bounds on the controller coefficients (ROCOND, 2015)
Fast approximation of the H∞ norm via optimization over spectral value sets (SIAM J. Matrix Anal. Appl., 2013)

← All publications · Research program · Mert Gürbüzbalaban