Online Optimization Specialization (3/4): Review of 'Competing in the Dark: An Efficient Algorithm for Bandit Linear 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
  1. Brief introduction and summary to the paper
  2. 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

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 recent papers. We show how the difficulties encountered by previous approaches are overcome by the use of a self-concordant potential function. Our approach presents a novel connection between online learning and interior point methods.

Key Contribution

  • The main contribution of this paper is that the authors proposed an efficient algorithm which achieves $O(\sqrt{T})$ regret for online optimization problem in the bandit setting.
  • Provide a link between Bregman divergence and self-concordant barrier 

Definitions

Self-concordant function

Self-concordant Barrier

Algorithms

Bandit Setting vs Online Setting

In both settings, after the learner made a decision, s/he will suffer a loss. The main difference is that, in the full-information setting, the learner can observe all of the loss functions $f_t(\cdot)$, while in the bandit setting, the learner can only observe $f_t(x_t)$.

Algorithm 1 Bandit Online Linear Optimization

Theorem 1



Understand Theorem 1

The expected regret over the original set $\mathcal{K}$ is within an additive $O(\sqrt{nT})$ factor from the above guarantee.

Takeaway

  • Easy-to-hard Approach: One common way for researchers to solve a problem is the easy-to-hard approach. Similar to this paper, the authors designed their algorithms based on the knowledge in the well-studied full information setting. They utilized a reduction to the full-information setting in one way or another because any algorithm that aimed for low-regret in the bandit setting would necessarily have to achieve low regret given full information. 
  • The exploration-exploitation trade-off: The exploration-exploitation trade-off is the primary source of difficulty in obtaining $O(\sqrt{T})$ guarantees on the regret. Roughly, there are two categories of approaches to perform both exploration and exploitation.
    • Alternating Explore/Exploit: Flip an $\epsilon$-biased coin to determine whether to explore or exploit.
    • Simultaneous Explore/Exploit

Comments

Post a Comment

Popular posts from this blog

Online Optimization Specialization (1/4): Review of 'Online Convex Programming and Generalized Infinitesimal Gradient Ascent' by Martin Zinkevich

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 ...
Read more

[Paper Reading] In-sample and Out-of-sample Sharpe Ratios of Multi-factor Asset Pricing Models

Image
Title:  In-sample and Out-of-sample Sharpe Ratios of Multi-factor Asset Pricing Models Author(s):  Raymond Kan*, Xiaolu Wang, Xinghua Zheng Year:  2019, visited the version revised on 22 Feb 2021 URL:  https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3454628 Definitions Optimal portfolio weight: For a mean-variance investor who wants to hold a portfolio with a target standard deviation of $\sigma$, then their optimal portfolio has weights of  $$ w^* = \frac{\sigma}{\theta} \Sigma^{-1} \mu, $$              where $\mu = \mathbb{E}[r_t]$, $\Sigma = Var[r_t]$, and $r_t$ is the return of risky assets in excess of risk-free rate. $\theta$ is the Sharpe ratio. Sharpe Ratio: $\theta = \sqrt{\mu' \Sigma^{-1}\mu}$. In practice, the investor does not know the mean and covariance matrix of the factors; he has to estimate $\theta$ using historical data. Thus, we have the in-sample and out-of-sample Sharpe ratio as follows. In-sample...
Read more

Online Optimization Specialization (4/4): Review of 'Projection-free Online Learning'

Image
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...
Read more