Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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
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.
