The query model is a simple model of computation that has led to many deep results. One such class of results relates computational complexity measures such as query complexity/communication complexity to algebraic measures such as degree/rank.
I will present the 2013 NIPS paper by Dan Russo and Van Roy where they introduce the notion of Eluder dimension and use it to analyse the UCB and Thompson Sampling algorithms.
The fact that the polynomial (x1+...+xn)^d can be written as a poly(n,d)-sum of products of univariates is a consequence of what is popularly known as 'the duality trick' in the algebraic complexity circles.
Abstract: Generalization error is the gap between an algorithm's performance on the true data distribution (unknown to us) and its performance on the given dataset (known to us).
The problem of chasing convex functions is easy to state: faced with a sequence of convex functions {f_t}, the goal of the algorithm is to output a point x_t at each time, so that the sum of the function costs f_t(x_t), plus the movement costs ||