Fetching the paper…
Reading the bibliography…
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.
On the mathematical foundations of theoretical statistics
R.A. Fisher · 1922
Earlier work this paper cites.
Sufficiency and statistical decision functions
Raghu Raj Bahadur et al · 1954
Earlier work this paper cites.
Convex trace functions and the wigner-yanase-dyson conjecture
Elliott H Lieb · 1973
Earlier work this paper cites.
Martingales with values in uniformly convex spaces
Gilles Pisier · 1975
Earlier work this paper cites.
A geometrical characterization of banach spaces in which martingale difference sequences are unconditional
Donald L. Burkholder · 1981
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
Arkadii Nemirovskii, David Borisovich Yudin, and Edgar Ronald Dawson · 1983
Earlier work this paper cites.
Aggregating strategies
Volodimir G Vovk · 1990
Earlier work this paper cites.
The weighted majority algorithm
Nick Littlestone and Manfred K Warmuth · 1994
Earlier work this paper cites.
Convex analysis on the hermitian matrices
Adrian Stephen Lewis · 1996
Earlier work this paper cites.
Introductory lectures on convex programming volume i: Basic course
Yurii Nesterov · 1998
Earlier work this paper cites.
Competitive on-line linear regression
Volodimir Vovk · 1998
Earlier work this paper cites.
Relative loss bounds for on-line density estimation with the exponential family of distributions
Katy S. Azoury and Manfred K. Warmuth · 2001
Earlier work this paper cites.
Lectures on modern convex optimization: analysis, algorithms, and engineering applications , volume 2
Ahron Ben-Tal and Arkadi Nemirovski · 2001
Earlier work this paper cites.
Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems
Arkadi Nemirovski · 2004
Cited alongside, same era.
Two inequalities for the first moments of a martingale, its square function and its maximal function
Adam Osękowski · 2005
Cited alongside, same era.
Prediction, Learning, and Games
Nicolo Cesa-Bianchi and Gabor Lugosi · 2006
Cited alongside, same era.
Logarithmic regret algorithms for online convex optimization
Elad Hazan, Amit Agarwal, and Satyen Kale · 2007
Cited alongside, same era.
Online learning: Random averages, combinatorial parameters, and learnability
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari · 2010
Cited alongside, same era.
Adaptive subgradient methods for online learning and stochastic optimization
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak and David Steurer · 2014
Later among the works it cites.
Matrix concentration inequalities via the method of exchangeable pairs
Lester Mackey, Michael I Jordan, Richard Y Chen, Brendan Farrell, Joel A Tropp, et al · 2014
Later among the works it cites.
Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations
Brendan McMahan and Francesco Orabona · 2014
Later among the works it cites.
Simultaneous model selection and optimization through parameter-free stochastic learning
Francesco Orabona · 2014
Later among the works it cites.
Online learning via sequential complexities
A. Rakhlin, K. Sridharan, and A. Tewari · 2014
Later among the works it cites.
Adaptive online learning
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
John Duchi, Elad Hazan, and Yoram Singer · 2011
Cited alongside, same era.
On the universality of online mirror descent
Nati Srebro, Karthik Sridharan, and Ambuj Tewari · 2011
Cited alongside, same era.
Freedman’s inequality for matrix martingales
Joel Tropp et al · 2011
Cited alongside, same era.
Near-optimal algorithms for online matrix prediction
Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz · 2012
Cited alongside, same era.
Sharp martingale and semimartingale inequalities
Adam Osękowski · 2012
Cited alongside, same era.
Relax and randomize: From value to algorithms
Alexander Rakhlin, Ohad Shamir, and Karthiks Sridharan · 2012
Cited alongside, same era.
User-friendly tail bounds for sums of random matrices
Joel A Tropp · 2012
Cited alongside, same era.
Dylan J Foster, Alexander Rakhlin, and Karthik Sridharan · 2015
Later among the works it cites.
On equivalence of martingale tail bounds and deterministic regret inequalities
Alexander Rakhlin and Karthik Sridharan · 2015
Later among the works it cites.
Online convex optimization with unconstrained domains and losses
Ashok Cutkosky and Kwabena A Boahen · 2016
Later among the works it cites.
Analysis in Banach spaces
Tuomas Hytönen, Jan van Neerven, Mark Veraar, and Lutz Weis · 2016
Later among the works it cites.
From coin betting to parameter-free online learning
Francesco Orabona and Dávid Pál · 2016
Later among the works it cites.
Online learning without prior information
Ashok Cutkosky and Kwabena A. Boahen · 2017
Later among the works it cites.
Personal communication
Adam Osękowski · 2017
Later among the works it cites.
Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
Ashok Cutkosky and Francesco Orabona · 2018
Closest in time.