text: 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.
  @cite_14: Convex programming involves a convex set F ⊆ Rn and a convex cost function c : F → R. The goal of convex programming is to find a point in F which minimizes c. 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 before seeing the cost function for that step. This can be used to model factory production, farm production, and many other industrial optimization problems where one is unaware of the value of the items produced until they have already been constructed. We introduce an algorithm for this domain. We also apply this algorithm to repeated games, and show that it is really a generalization of infinitesimal gradient ascent, and the results here imply that generalized infinitesimal gradient ascent (GIGA) is universally consistent.
summary: 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.