09/07/2020

Complexity Guarantees for Polyak Steps with Momentum

Mathieu Barre, Adrien B Taylor, Alexandre d'Aspremont

Keywords: Convex optimization,

Abstract Paper Similar Papers

Abstract: In smooth strongly convex optimization, knowledge of the strong convexity parameter is critical for obtaining simple methods with accelerated rates. In this work, we study a class of methods, based on Polyak steps, where this knowledge is substituted by that of the optimal value, $f_*$. We first show slightly improved convergence bounds than previously known for the classical case of simple gradient descent with Polyak steps, we then derive an accelerated gradient method with Polyak steps and momentum, along with convergence guarantees.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at COLT 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 14:17 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 13:12 
 0
 0
 0
 0
 2:53 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 11:47 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 14:10 
 0
 0
 0
 0
 5:14 
 0
 0
 0
 0
 15:56 
 0
 0
 0
 0
 14:49 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 5:22 
 1
 1
 0
 0
 9:31 
 0
 0
 0
 0
 12:19 
 0
 0
 0
 0
 14:13 
 0
 0
 0
 0
 13:01 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 12:14 
 0
 0
 0
 0
 5:02 
 0
 0
 0
 0
 13:45 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 5:19 
 0
 0
 0
 0
 14:57 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 13:21 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 16:24 
 0
 0
 0
 0
 14:20 
 0
 0
 0
 0
 4:55 
 0
 0
 0
 0
 8:07 
 0
 0
 1
 1
 16:17 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 12:58 
 0
 0
 0
 0
 3:02