I will describe here the very first (to my knowledge) acceleration algorithm for smooth convex optimization, which is due to Arkadi Nemirovski (dating back to the end of the 70’s). The algorithm relies on a -dimensional plane-search subroutine (which, in theory, can be implemented in calls to a first-order oracle). He later improved it to only require a -dimensional line-search in 1981, but of course the breakthrough that everyone knows about came a year after with the famous 1982 paper by Nesterov that gets rid of this extraneous logarithmic term altogether (and in addition is based on the deep insight of modifying Polyak’s momentum).

Let be a -smooth function. Denote . Fix a sequence , to be optimized later. We consider the “conjugate” point . The algorithm simply returns the optimal combination of the conjugate point and the gradient descent point, that is:

Let us denote and for shorthand. The key point is that , and in particular . Now recognize that is a lower bound on the improvement (here we use that is better than ). Thus we get:

In other words if the sequence is chosen such that then we get

This is good because roughly the reverse inequality also holds true by convexity (and the fact that so ):

So finally we get , and it just remains to realize that is of order so that .

## By Ankara Avukat May 18, 2019 - 3:37 pm

Ankara Boşanma Avukatı

## By şehirler arası nakliyat May 16, 2019 - 7:13 am

Thank you for your site information

## By bartinnakliyat May 13, 2019 - 5:30 pm

Bartın evden eve nakliyat

https://www.bartinnakliyat.com/

## By novusenerji May 13, 2019 - 5:29 pm

Kalorimetre

https://www.novusenerji.com.tr/

## By lohusahamile May 13, 2019 - 5:28 pm

lohusa giyim

https://www.lohusahamile.com/

## By bizedualaryeter May 13, 2019 - 5:27 pm

dilek duaları

https://www.bizedualaryeter.com/

## By bitcoin May 13, 2019 - 5:27 pm

bitcoin

https://www.bitcofly.com/

## By bdtegitim May 13, 2019 - 5:26 pm

Bilişsel Davranışçı Terapi Eğitimi

https://bdtegitim.com/

## By psikolog May 13, 2019 - 5:24 pm

psikolog

https://www.aktifpsikolog.com

## By NUMAN KOÇAK May 13, 2019 - 4:20 pm

thank you

## By https://woodworkingte.blogspot.com/ May 8, 2019 - 6:02 pm

thank you

## By Yüz Temizleyici Jel Tavsiyeleri May 8, 2019 - 5:30 am

thnx for sharing your good web-site

## By boojum January 11, 2019 - 3:09 pm

In the statement, where you write

x_{t+1} =_{x \in P_t} f(x) where $P_t$ is the span, is there a missing \min?

## By Sebastien Bubeck January 11, 2019 - 3:56 pm

Yes “argmin” was missing, thanks!

## By Sohail Bahmani January 9, 2019 - 2:39 pm

Hi Sebastien,

Just a typo: in the very last sentence the $g_s$ in the sum should be $\delta_s$.

## By Sebastien Bubeck January 9, 2019 - 5:42 pm

Thanks Sohail, fixed!