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 and acknowledge you have read our privacy policy.