We could also generalize this to a general update function U:X×Y→Y, where X may be the simplex over experts or some other set. Then we just require that U be convex in each argument and Lipschitz in the first. And the complexity is certainly polynomial in the number of calls to the fixed point oracle. This seems to be what I needed to improve the T2/3 in my COLT paper to T1/2. (I explicitly used the fixed point in the analysis, but didn’t think of this algorithm.)
We could also generalize this to a general update function U:X×Y→Y, where X may be the simplex over experts or some other set. Then we just require that U be convex in each argument and Lipschitz in the first. And the complexity is certainly polynomial in the number of calls to the fixed point oracle. This seems to be what I needed to improve the T2/3 in my COLT paper to T1/2. (I explicitly used the fixed point in the analysis, but didn’t think of this algorithm.)