# Questions tagged [online-learning]

The tag has no usage guidance, but it has a tag wiki.

13 questions
55 views

### Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game?

It is well-known that in a $2$-player zero sum game if one player plays a regret minimizing mixed strategy, and the other player best-responds at each round to that mixed strategy, we are guaranteed ...
192 views

### Rademacher complexity beyond the agnostic setting

The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf. Here the quantity on the LHS that ...
107 views

### Average Regret Bounds for Linear Stochastic Bandits

I am reading this paper on linear stochastic bandits : http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf All the results are stated in a high-probability ...
351 views

### Follow the Perturbed Leader for nonlinear cost functions

The famous FTPL algorithm  is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of  it says "It would be great to ...
205 views

### Automatically Adapting Forgetting Factor for Online EM

I've been reading some interesting papers recently on methods for automatically and adaptively setting the learning rate in stochastic gradient descent (SGD). In particular, "No more pesky learning ...
404 views

### Online to batch sample complexity

It is well known that a mistake bound can be converted to a PAC bound. I know how to prove a sample complexity of $$O( (1/\epsilon)[M + \log(M/\delta)] ),$$ where $M$ is an upper bound on the number ...
224 views

### Which algorithm for a project about online machine learning?

I have a basic understanding of how machine learning works, but my knowledge isn't enough in order to develop a personal project I would like to start. I want to develop a system based on online ...
798 views

### The Warren Buffett Problem

Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any ...
318 views

### What are the best possible time/error tradeoffs for approximate solution of linear programs?

For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity ...
997 views

### Separation between coarse correlated equilibria and correlated equilibria

I am looking for examples of techniques for proving price of anarchy bounds that have the power to separate the price of anarchy over coarse correlated equilibria (the limiting set of no-external-...
372 views

### Online learning: Perceptron updates

It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?