Before revision:  We provide a }  O(d ^2) regret bound where d is the covering dimension of the hypothesis class. The algorithms are based on a novel technique which we call Steiner potential since in the linear case it reduces to controlling the value of the Steiner polynomial of a convex region at various scales.
After revision:  We provide a } O(d \log \log T + d \log d) regret which matches the \Omega(d \log \log T) lower bound up to the d \log d additive factor. If we replace pricing loss by the symmetric loss, we obtain an algorithm with nearly optimal regret of O(d \log d) matching the \Omega(d) lower bound up to \log d. These algorithms are based on a novel technique which we call Steiner potential since in the linear case it reduces to controlling the value of the Steiner polynomial of a convex region at various scales.