<p>Yes -- both gradient descent and the randomized weighted majority algorithm (often called multiplicative weights these days) are instantiations of the "Follow the regularized leader" framework. Gradient descent is what comes out if you regularize with the euclidean norm, and multiplicative weights is what comes out if you regularize with Shannon entropy. </p>

<p>See e.g. here (<a href="http://www.jennwv.com/courses/F11/lecture11.pdf" rel="nofollow">http://www.jennwv.com/courses/F11/lecture11.pdf</a>) for a derivation of the weighted majority algorithm from this framework. </p>

CC BY-SA 3.0
2014-12-15T01:54:41.803Z
Thanks Aaron for pointing it out. Do you have any ideas on this? http://cstheory.stackexchange.com/questions/27816/follow-the-perturbed-leader-for-nonlinear-cost-functions
Daniel
CC BY-SA 3.0
2014-12-15T01:37:17.533Z
2014-12-15T01:37:17.533Z
Aaron Roth
<p>Is there a direct conversion between gradient descent ([1], Alg 1 )
and any of the following algorithms? </p>

<p>1) Weighted Majority: <a href="http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm" rel="nofollow">http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm</a></p>

<p>2) Follow the Leader:  <a href="http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf" rel="nofollow">http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf</a> 
I keep seeing these together, but I don't see the direct conversion. </p>

<p>[1] <a href="http://moodle.technion.ac.il/pluginfile.php/195968/mod_resource/content/0/OCP_ICML03.pdf" rel="nofollow">http://moodle.technion.ac.il/pluginfile.php/195968/mod_resource/content/0/OCP_ICML03.pdf</a></p>

<optimization><convex-optimization><machine-learning>
direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority?
Daniel
# direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority?

(Asked by: username_0 on 2014-12-07)

Is there a direct conversion between gradient descent ([1], Alg 1 )
and any of the following algorithms?

1) Weighted Majority: <http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm>

2) Follow the Leader: <http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf>
I keep seeing these together, but I don't see the direct conversion.

[1] <http://moodle.technion.ac.il/pluginfile.php/195968/mod_resource/content/0/OCP_ICML03.pdf>

**Tags:** optimization, convex-optimization, machine-learning


---

## 1 answers

### Answer by username_1 on 2014-12-15. Score: 2 | Accepted answer

Yes -- both gradient descent and the randomized weighted majority algorithm (often called multiplicative weights these days) are instantiations of the "Follow the regularized leader" framework. Gradient descent is what comes out if you regularize with the euclidean norm, and multiplicative weights is what comes out if you regularize with Shannon entropy.

See e.g. here (<http://www.jennwv.com/courses/F11/lecture11.pdf>) for a derivation of the weighted majority algorithm from this framework.

> **Comments:**
> **username_0**: Thanks Aaron for pointing it out. Do you have any ideas on this? http://cstheory.stackexchange.com/questions/27816/follow-the-perturbed-leader-for-nonlinear-cost-functions  

---

