5

No, it's not true. Consider this game where the row player's actions are A,B,C and column's are D,E (shown are the row player's payoffs): D E A 1 0 B 0 1 C 0.6 0.6 I think that in any equilibrium, the row player plays only C. But now if the column player uses a no-regret algorithm, every sample will either be action D or E, and the ...


3

(a) If you don't assume that you're "competing" against $f\in F$, you must make some assumption about the larger function class to which $f$ belongs -- otherwise, by standard no-free-lunch theorems, you will not be able to give any meaningful risk decay rates (which is what Rademacher complexities enable you to do). Alternatively, you could assume something ...


3

Using the "doubling trick," you can turn your favorite high probability algorithm (e.g. LinUCB) to be an anytime algorithm with expected regret as a function of $T$, usually giving a $\tilde{O}(\sqrt{T})$ dependence without knowing $T$ in advance. This turns out to be tight, i.e. in Chu et al. (2011), we give lower bounds on expected regret of $\Theta(\sqrt{...


2

I'm not sure if this is what you're looking for, but people have studied consistency of surrogate risk minimization. There, we define a surrogate loss function $L$ and a link $\psi$. We first minimize surrogate loss on our dataset, yielding some surrogate hypothesis $h$. Then we define $f(x) = \psi(h(x))$. This procedure is roughly consistent if, as data $\...


1

Here is what you are looking for. It is quite new: https://arxiv.org/pdf/1810.07362.pdf


Only top voted, non community-wiki answers of a minimum length are eligible