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 Foam insulation May 19, 2021 - 5:11 am
Really great and useful information.
thanks for sharing.
Keep going.
By Mohsin Kabir April 28, 2021 - 5:57 am
Therefore, aluminum entryways frameworks are liked by numerous individuals.
By tile trader April 20, 2021 - 3:28 pm
Why Is It Preferred In Ceramic Bathrooms?
Ceramics, which are now frequently used in bathrooms, create effective results in changing the air of the
bathroom. Thanks to Ceramic alternatives, it will be possible for you to express elegance in the
bathrooms
By egiappsinc April 20, 2021 - 3:22 pm
Why Is Fleet Coating Made What Are Its Pros
Fleet wraps are an important step in meeting the advertising needs of small and medium-sized
businesses such as fleet. Not only for advertising purposes but also helps to protect vehicles against
reactions such as scratches and friction
By egiappsinc April 20, 2021 - 3:16 pm
Why are Special Wraps Produced for Vehicles?
Vehicle wraps has been among the popular studies recently. Moreover, vehicle wraps operations are a
process performed on vehicles of many different models. Durable and high-quality special wraps used
for vehicles make the look of the vehicles cooler.
By tile trader April 20, 2021 - 3:07 pm
What is Patterned Tiles Fashion?
Ceramic tile is a non-metal inorganic material. Tiles are the first to come
to mind when it comes to renovation and renewal. You can buy tiles and tiles suitable for your indoor
and outdoor spaces and get the comfort of using them for many years.
By cheeseteeth April 20, 2021 - 2:28 pm
Cappadocia: The Door Separating Magic And Truth
During your journey with horses in the valleys
of Cappadocia, which the Persians called “The Land of Beautiful Horses”, where Alexander
The Great put an end to their rule, you can also find traces of ancient caravans and warriors of
Alexander today.
By cheeseteeth April 20, 2021 - 12:15 pm
All-On-Four Implant Treatment and Advantages
s. In such cases, the all-on-four implant application allows you to have fixed dentures
with a single surgical procedure. In cases, the additional dental implants are not suitable for
your treatment, all-On-Four implants are designed to replace them, even if you have lost all
your upper and lower teeth.
By avaytacer seo April 20, 2021 - 11:55 am
Adana Hukuk Bürosu Ve Avukatları
Ülkemizde hemen hemen her ilde avukatlık mesleğini yürütenler
bulunmaktadır. Bunlardan biri de Adana avukatları olmaktadır.
By Sohbet April 16, 2021 - 12:25 pm
Sohbet,Mobil Sohbet Kaliteli Sohbet Chat Siteleri Online Muhabbet Odaları Sohbet, Mobil Sohbet, Mobil Chat, Sohbet Chat, Chat Sohbet, Sohbet Siteleri, Sohbet Odaları
By What Are The Purposes Of Glass Mosaic Coating? February 20, 2021 - 1:56 pm
Glass mosaic is a decorative coating material. It is produced in different sizes such as 10 * 10, 13 * 13,
20 * 20 and 20 * 40 mm. It was built as fabrication on a third-grade paper sheet. The inner side of the
glass mosaic is the side that sticks to the paper.
By What Are The Advantages Of Aluminum Doors? February 16, 2021 - 4:54 am
For this reason, aluminum doors systems are preferred by many people.
By N June 19, 2019 - 10:32 pm
Hi Sebastien,
Do you have a source for Nemirovski’s results? I was not able to find either the late 70’s result, or the 1981 improvement you mention, on his webpages.
By Sebastien Bubeck June 20, 2019 - 12:23 pm
Here is the Russian paper (or part of it at least): https://blogs.princeton.edu/imabandit/wp-content/uploads/sites/122/2019/06/Nemirovski81_Russian.pdf and a discussion of it in English (by Nemirovski): https://blogs.princeton.edu/imabandit/wp-content/uploads/sites/122/2019/06/Nemirovski81_EnglishDiscussion.pdf
By Yichi June 18, 2019 - 12:19 pm
Hi, Sebastian, thanks for sharing that!
It seems that Nemirovski’s acceleration does not need to know how smooth the function f is in advance. But we should know it as a hyperparameter if we are using Nesterov’s acceleration. So the question is if it is possible to get an accelerated gradient descent algorithm without line search if we are not given the knowledge of the smooth parameter?
By Anonymous June 20, 2019 - 12:27 pm
With line search, there are many variants of Nesterov also does this, such as
this paper by Seb
https://arxiv.org/pdf/1506.08187.pdf
Without a line search, I suspect it is not possible?
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!