Published on Sun Sep 10 2017

Efficient Online Linear Optimization with Approximation Algorithms

Dan Garber

We revisit the problem of online linear optimization. We present new algorithms with significantly improved oracle complexity for both the full information and bandit variants of the problem. These are the first results to obtain both an average oracles complexity of

0
0
0
Abstract

We revisit the problem of \textit{online linear optimization} in case the set of feasible actions is accessible through an approximated linear optimization oracle with a factor multiplicative approximation guarantee. This setting is in particular interesting since it captures natural online extensions of well-studied \textit{offline} linear optimization problems which are NP-hard, yet admit efficient approximation algorithms. The goal here is to minimize the \textit{-regret} which is the natural extension of the standard \textit{regret} in \textit{online learning} to this setting. We present new algorithms with significantly improved oracle complexity for both the full information and bandit variants of the problem. Mainly, for both variants, we present -regret bounds of , were is the number of prediction rounds, using only calls to the approximation oracle per iteration, on average. These are the first results to obtain both average oracle complexity of (or even poly-logarithmic in ) and -regret bound for a constant , for both variants.

Wed Jun 13 2018
Machine Learning
Minimizing Regret of Bandit Online Optimization in Unconstrained Action Spaces
We consider online convex optimization with a zero-order oracle feedback. The objective is to minimize the regret, that is, the difference between the sum of the costs she accumulates and that of a static optimal action. We adapt the presented algorithm to the setting with two-point feedback.
0
0
0
Fri Apr 20 2012
Machine Learning
Regret in Online Combinatorial Optimization
The regret of the decision maker is the difference between her realized loss and the best loss she would have achieved by picking, in hindsight, the best possible action. We address online linear optimization problems when the possible actions of the decision maker are represented by binary vectors.
0
0
0
Wed May 23 2018
Machine Learning
Efficient online algorithms for fast-rate regret bounds under sparsity
We consider the online convex optimization problem. In the adversarial setting, we develop an algorithm that achieves several rates of convergence with different dependencies on the objective. We establish new risk bounds that are adaptive to the sparsity of the problem.
0
0
0
Mon Mar 14 2016
Machine Learning
An optimal algorithm for bandit convex optimization
We consider the problem of online convex optimization against an arbitrary adversary with bandit feedback. This bound is known to be tight up to logarithmic factors. Our analysis introduces new tools in discrete convex geometry.
0
0
0
Wed Apr 08 2015
Machine Learning
The Computational Power of Optimization in Online Learning
We consider the fundamental problem of prediction with expert advice where the experts are "optimizable" In this setting, we give a novel online algorithm that attains vanishing regret with respect to experts in total computation time. We also study the implications of our results to learning in repeated zero-sum games.
0
0
0
Mon Nov 28 2011
Machine Learning
Regret Bound by Variation for Online Convex Optimization
The regret of online linear optimization can be bounded by the total variation of the cost vectors. We show that the regret bound for online bandit convex optimization is optimal when the variation of cost functions is independent of the number of trials.
0
0
0