山南水北

Specialization Introduction This specialization covers five selected grounding papers in online optimization. In each blog, I will discuss one paper, where I aim to include Brief introduction and summary to the paper Key takeaways of the paper Notice that all the discussion and summary in this specialization are based on the reviewed papers. None of the algorithms or theorems is proposed by myself.  Summary Paper Detail Title:  Projection-free Online Learning Author(s):  Elad Hazan, Satyen Kale URL:  https://icml.cc/2012/papers/292.pdf Abstract The computational bottleneck in applying online learning to massive data sets is usually the projection step. We present efficient online learning algorithms that eschew projections in favor of much more efficient linear optimization steps using the Frank-Wolfe technique. We obtain a range of regret bounds for online convex optimization, with better bounds for specific cases such as stochastic online smooth convex optimization...

Specialization Introduction This specialization covers five selected grounding papers in online optimization. In each blog, I will discuss one paper, where I aim to include Brief introduction and summary to the paper Key takeaways of the paper Notice that all the discussion and summary in this specialization are based on the reviewed papers. None of the algorithms or theorems is proposed by myself.  Summary Paper Detail Title:  Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization Author(s):  Jacob Abernethy, Elad Hazan, Alexander Raklin URL:  http://web.eecs.umich.edu/~jabernet/123-Abernethy.pdf Abstract We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal $O*(\sqrt{T})$ regret. The setting is a natural generalization of the stochastic multi-armed bandit problem, and the existence of an efficient optimal algorithm has been posed as an open problem in a number of rece...

Specialization Introduction This specialization covers five selected grounding papers in online optimization. In each blog, I will discuss one paper, where I aim to include Brief introduction and summary to the paper Key takeaways of the paper Notice that all the discussion and summary in this specialization are based on the reviewed papers. None of the algorithms or theorems is proposed by myself.  Summary Paper Detail Title:  Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization Author(s):  Alexander Rakhlin, Ohad Shamir, Karthik Sridharan URL:  https://icml.cc/2012/papers/261.pdf Abstract Stochastic gradient descent (SDG) is a simple and popular method to solve stochastic optimization problems which arise in machine learning. For strongly convex problems, its convergence rate was known to be $\mathcal{O}(log(T)/T)$, by running SGD for T iterations and returning the average point. However, recent results showed that using a different algorithm...

Specialization Introduction This specialization covers five selected grounding papers in online optimization. In each blog, I will discuss one paper, where I aim to include Brief introduction and summary to the paper Key takeaways of the paper Notice that all the discussion and summary in this specialization are based on the reviewed papers. None of the algorithms or theorems is proposed by myself.  Summary Paper Detail Title: Online Convex Programming and Generalized Infinitesimal Gradient Ascent Author(s): Martin Zinkevich URL:  https://www.aaai.org/Library/ICML/2003/icml03-120.php Abstract Convex programming involves a convex set $F \subseteq R^n$ and a convex function $c : F \to \mathbb{R}$. The goal of convex programming is to find a point in F which minimizes c. In this paper, we introduce online convex programming.  In online convex programming, the convex set is known in advance, but in each step of some repeated optimization problem, one must select a point in F ...