Timezone: »

 
Spotlight
AdaGrad Avoids Saddle Points
Kimon Antonakopoulos · Panayotis Mertikopoulos · Georgios Piliouras · Xiao Wang

Tue Jul 19 02:05 PM -- 02:10 PM (PDT) @ Room 309
in OPT: Non-Convex »

Adaptive first-order methods in optimization have widespread ML applications due to their ability to adapt to non-convex landscapes. However, their convergence guarantees are typically stated in terms of vanishing gradient norms, which leaves open the issue of converging to undesirable saddle points (or even local maxima). In this paper, we focus on the AdaGrad family of algorithms - from scalar to full-matrix preconditioning - and we examine the question of whether the method's trajectories avoid saddle points. A major challenge that arises here is that AdaGrad's step-size (or, more accurately, the method's preconditioner) evolves over time in a filtration-dependent way, i.e., as a function of all gradients observed in earlier iterations; as a result, avoidance results for methods with a constant or vanishing step-size do not apply. We resolve this challenge by combining a series of step-size stabilization arguments with a recursive representation of the AdaGrad preconditioner that allows us to employ center-stable techniques and ultimately show that the induced trajectories avoid saddle points from almost any initial condition.

Keywords: OPT: First-order · OPT: Non-Convex

Author Information

Kimon Antonakopoulos (EPFL)
Panayotis Mertikopoulos (CNRS and Criteo AI Lab)
Georgios Piliouras (Singapore University of Technology and Design)
Xiao Wang (Shanghai University of Finance and Economics)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors