Sequential complexities and uniform martingale laws of large numbers

• 成果类型: Article
• 署名作者: Rakhlin, Alexander; Sridharan, Karthik; Tewari, Ambuj
• 署名单位: University of Pennsylvania; University of Michigan System; University of Michigan
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-013-0545-5
• 发表日期: 2015
• 页码: 111-153
• 关键词: glivenko-cantelli problem; Empirical Processes; CONVERGENCE; learnability; rates

摘要

We establish necessary and sufficient conditions for a uniform martingale Law of Large Numbers. We extend the technique of symmetrization to the case of dependent random variables and provide sequential (non-i.i.d.) analogues of various classical measures of complexity, such as covering numbers and combinatorial dimensions from empirical process theory. We establish relationships between these various sequential complexity measures and show that they provide a tight control on the uniform convergence rates for empirical processes with dependent data. As a direct application of our results, we provide exponential inequalities for sums of martingale differences in Banach spaces.