1
$\begingroup$

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

$\endgroup$

migrated from math.stackexchange.com Dec 15 '14 at 0:44

This question came from our site for people studying math at any level and professionals in related fields.

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.