Online Learning with Stochastically Partitioning Experts

Abstract

We study a variant of the experts problem in which new experts are revealed over time according to a stochastic process. The experts are represented by partitions of a hypercube 𝔹 in d-dimensional Euclidean space. In each round, a point is drawn from 𝔹 in an independent and identically distributed manner using an unknown distribution. For each chosen point, we draw d orthogonal hyperplanes parallel to the d faces of 𝔹 passing through the point. The set of experts available in a round is the set of partitions of 𝔹 created by all the hyperplanes drawn up to that point. Losses are adversarial, and the performance metrics of interest include expected regret and high probability bounds on the sample-path regret. We propose a suitably adapted version of the Hedge algorithm called Hedge-G, which uses a constant learning rate and has O(√(2^d T log T)) expected regret, which is order-optimal. Further, we show that for Hedge-G, there exists a trade-off between choosing a learning rate that has optimal expected regret and a learning rate that leads to a high probability sample-path regret bound. We address this limitation by proposing AdaHedge-G, a variant of Hedge-G that uses an adaptive learning rate by tracking the loss of the experts revealed up to that round. AdaHedge-G simultaneously achieves O(log(log T)√( T log T)) expected regret and O(log T √(T log T)) sample-path regret, with probability at least 1-T^-c, where c > 0 is a constant dependent on d.