We study various discrete nonlinear combinatorial optimization problems in an online learning framework. In the first part, we address the question of whether there are negative results showing that getting a vanishing (or even vanishing approximate) regret is computational hard. We provide a general reduction showing that many (min-max) polynomial time solvable problems not only do not have a vanishing regret, but also no vanishing approximation @math -regret, for some @math (unless @math ). Then, we focus on a particular min-max problem, the min-max version of the vertex cover problem which is solvable in polynomial time in the offline case. The previous reduction proves that there is no @math -regret online algorithm, unless Unique Game is in @math ; we prove a matching upper bound providing an online algorithm based on the online gradient descent method. Then, we turn our attention to online learning algorithms that are based on an offline optimization oracle that, given a set of instances of the problem, is able to compute the optimum static solution. We show that for different nonlinear discrete optimization problems, it is strongly @math -hard to solve the offline optimization oracle, even for problems that can be solved in polynomial time in the static case (e.g. min-max vertex cover, min-max perfect matching, etc.). On the positive side, we present an online algorithm with vanishing regret that is based on the follow the perturbed leader algorithm for a generalized knapsack problem.
Another direction is to design online learning algorithms using (offline polynomial-time) approximation algorithms as oracles. provided an algorithm which is inspired by Zinkevich's algorithm @cite_14 (gradient descent): at every step, the algorithm updates the current solution in the direction of the gradient and project back to the feasible set using an approximation algorithm. They showed that given an @math -approximation algorithm for a optimization problem, after @math prediction rounds (time steps) the online algorithm achieves an @math -regret bound of @math using @math calls to the approximation algorithm per round in average. Later on, gave an algorithm with @math -regret bound of @math using only @math calls to the approximation algorithm per round in average. These algorithms rely crucially on the linearity of the objective functions and it remains an interesting open question to design algorithms for online non-linear optimization problems.
@cite_14
2154682027
We give novel algorithms for stochastic strongly-convex optimization in the gradient oracle model which return a O(1 T)-approximate solution after T iterations. The first algorithm is deterministic, and achieves this rate via gradient updates and historical averaging. The second algorithm is randomized, and is based on pure gradient steps with a random step size. his rate of convergence is optimal in the gradient oracle model. This improves upon the previously known best rate of O(log(T T), which was obtained by applying an online strongly-convex optimization algorithm with regret O(log(T)) to the batch setting. We complement this result by proving that any algorithm has expected regret of Ω(log(T)) in the online stochastic strongly-convex optimization setting. This shows that any online-to-batch conversion is inherently suboptimal for stochastic strongly-convex optimization. This is the first formal evidence that online convex optimization is strictly more difficult than batch stochastic convex optimization.