Online Learning: Sufficient Statistics and the Burkholder Method
We uncover a fairly general principle in online learning: If regret can be (approximately) expressed as a function of certain "sufficient statistics" for the data sequence, then there exists a special Burkholder function that 1) can be used algorithmically to achieve the regret bound and 2) only depends on these sufficient statistics, not the entire data sequence, so that the online strategy is only required to keep the sufficient statistics in memory. This characterization is achieved by bringing the full power of the Burkholder Method --- originally developed for certifying probabilistic martingale inequalities --- to bear on the online learning setting. To demonstrate the scope and effectiveness of the Burkholder method, we develop a novel online strategy for matrix prediction that attains a regret bound corresponding to the variance term in matrix concentration inequalities. We also present a linear-time/space prediction strategy for parameter free supervised learning with linear classes and general smooth norms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Burkholderia genome mining for nonribosomal peptide synthetases reveals a great potential for novel siderophores and lipopeptides synthesis
Burkholderia is an important genus encompassing a variety of species, including pathogenic strains as well as strains that promote plant growth. We have carried out a global strategy, which combined two complementary app…
ZigZag: A new approach to adaptive online learning
We develop a novel family of algorithms for the online learning setting with regret against any data sequence bounded by the empirical Rademacher complexity of that sequence. To develop a general theory of when this type…
On SDEs with Lipschitz coefficients, driven by continuous, model-free martingales
We prove the existence and uniqueness of solutions of SDEs with Lipschitz coefficients, driven by continuous, model-free martingales. The main tool in our reasoning is Picard's iterative procedure and a model-free versio…
Episodic memory for continual model learning
Both the human brain and artificial learning agents operating in real-world or comparably complex environments are faced with the challenge of online model selection. In principle this challenge can be overcome: hierarch…
Bayesian InferencemodelModel SelectionNonlinear Independent Component Analysis for Discrete-Time and Continuous-Time Signals
We study the classical problem of recovering a multidimensional source signal from observations of nonlinear mixtures of this signal. We show that this recovery is possible (up to a permutation and monotone scaling of th…
blind source separationContrastive LearningTime SeriesTime Series Analysis