Advances in Distribution and Sequential Learning: Sample Complexity, Regret, and Other Guarantees
Dr Xiaokui Xiao, Professor, School of Computing
COM3 Level 2
SR21, COM3 02-60
Abstract:
This seminar presents the improved algorithms and techniques developed in the thesis for learning under uncertainty; in particular, probably approximately correct (PAC) distribution learning and various forms of online learning. The improvements span a variety of “goodness” notions such as sample complexity, time and space complexity, regret, and fairness. We will focus on three results.
For PAC learning high-dimensional Bayes nets, we connect distribution learning in Kullback–Leibler (KL) divergence to online prediction under the log loss. We thus derive new and improved sample complexity bounds for proper and improper realizable and agnostic learning of bounded-indegree Bayes nets in KL divergence, with exponential-time (in the number of variates) algorithms. Building on these results, we design efficient (polynomial-time) algorithms for specific cases, viz: (i) learning tree-structured distributions, where we improve upon the best-known sample complexity in the improper case, and (ii) learning bounded-indegree chordal-structured distributions given the skeleton.
We also consider PAC distribution learning from the lens of learning-augmented algorithms, with a view of breaking sample complexity barriers by leveraging side-information. Assuming we have imperfect advice for the parameters without any promises as to the quality, we consider the classical problem of learning binary product distributions, where we have a simple algorithm with optimal sample complexity which is linear in the number of parameters. Our algorithm surpasses the linear barrier by a polynomial factor when the advice is close to the truth in L1 distance bounded by a sublinear polynomial (in the dimension), and is comparable to the linear baseline even when the advice is arbitrarily bad.
For learning stochastic bandits (assuming the rounds are played by different agents), we introduce p-mean regret: a new family of regret measures capturing trade-offs between efficiency and fairness when the plays are interpreted as allocations to different agents. We propose a simple variant of UCB1 (Auer et al. 2002) that achieves sublinear regret for all constant p <= 1 subject to a positivity assumption on the rewards.