In general finding ϵ-approximate fixed points will be PPAD-hard. On the other hand, it seems like we could use an online learning algorithm to get a distribution over weight vectors such that the combined expert’s expected modification to a weight vector sampled from this distribution is small, in polynomial time. I haven’t worked out the details, but some version of this might imply that the combined expert can’t expect to do better than you, if you randomly choose a weight vector from this distribution and the loss function is decided before you make this random choice.
(by the way, the same technique should work to construct a qualipolynomial-time randomized “logical inductor” satisfying a weaker property)
In general finding ϵ-approximate fixed points will be PPAD-hard. On the other hand, it seems like we could use an online learning algorithm to get a distribution over weight vectors such that the combined expert’s expected modification to a weight vector sampled from this distribution is small, in polynomial time. I haven’t worked out the details, but some version of this might imply that the combined expert can’t expect to do better than you, if you randomly choose a weight vector from this distribution and the loss function is decided before you make this random choice.
(by the way, the same technique should work to construct a qualipolynomial-time randomized “logical inductor” satisfying a weaker property)