Adaptive Restart for Accelerated Gradient Schemes

Details Adaptive Restart for Accelerated Gradient Schemes Adaptive Restart for Accelerated Gradient Schemes

2012-04-18

arxiv.org/abs/1204.3982v1

Mathematics

Optimization and Control

17 pages, 7 figures

Scientific paper

In this paper we demonstrate a simple heuristic adaptive restart technique that can dramatically improve the convergence rate of accelerated gradient schemes. The analysis of the technique relies on the observation that these schemes exhibit two modes of behavior depending on how much momentum is applied. In what we refer to as the 'high momentum' regime the iterates generated by an accelerated gradient scheme exhibit a periodic behavior, where the period is proportional to the square root of the local condition number of the objective function. This suggests a restart technique whereby we reset the momentum whenever we observe periodic behavior. We provide analysis to show that in many cases adaptively restarting allows us to recover the optimal rate of convergence with no prior knowledge of function parameters.

Affiliated with

Also associated with

No associations

Rating

Adaptive Restart for Accelerated Gradient Schemes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Adaptive Restart for Accelerated Gradient Schemes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Restart for Accelerated Gradient Schemes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-411058