At each time-step $t$ we are given two probability estimators $p_0(t)$ and $p_1(t)$. We output a predicted probability $p(t)$ that we will next observe $1$, and then receive an outcome $y_{t+1} \in \{0, 1\}$. We accept a loss equal to the entropy of the received symbol under $p(t)$.

We choose $p(t)$ to have the form $\lambda p_0(t) + (1-\lambda)p_1(t)$ for $\lambda \in [0, 1]$. is it possible to find a good value for $\lambda$, online, in constant space, and using constant time per step?

In particular, is it possible to achieve regret competitive with or better than the estimator

$$p(t) = \frac{(p_0(<t) * p_0(t) + p_1(<t) * p_1(t))}{p_0(<t) + p_1(<t)}$$


$$p_i(<t) = \prod_{j=0}^{t-1}\left(\left[y_{j+1} = 1\right]p_i(j) + \left[y_{j+1} = 0\right]\left(1 - p_i(j)\right)\right),$$

without having $\lambda$ tend to $0$ or $1$ unless this is optimal?

Presumably we can use stochastic gradient descent, but is there a way to make more efficient use of data?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.