Generalization bounds for non-stationary mixing processes

详细信息    查看全文

• 作者：Vitaly Kuznetsov ; Mehryar Mohri
• 关键词：Generalization bounds ; Time series ; Mixing ; Non ; stationary processes ; Markov processes ; Asymptotic stationarity ; Fast rates ; Local Rademacher complexity ; Unbounded loss
• 刊名：Machine Learning
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：106
• 期：1
• 页码：93-117
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence (incl. Robotics); Control, Robotics, Mechatronics; Computing Methodologies; Simulation and Modeling; Language Translation and Linguistics;
• 出版者：Springer US
• ISSN：1573-0565
• 卷排序：106

文摘

This paper presents the first generalization bounds for time series prediction with a non-stationary mixing stochastic process. We prove Rademacher complexity learning bounds for both average-path generalization with non-stationary \(\beta \)-mixing processes and path-dependent generalization with non-stationary \(\phi \)-mixing processes. Our guarantees are expressed in terms of \(\beta \)- or \(\phi \)-mixing coefficients and a natural measure of discrepancy between training and target distributions. They admit as special cases previous Rademacher complexity bounds for non-i.i.d. stationary distributions, for independent but not identically distributed random variables, or for the i.i.d. case. We show that, using a new sub-sample selection technique we introduce, our bounds can be tightened under the natural assumption of asymptotically stationary stochastic processes. We also prove that fast learning rates can be achieved by extending existing local Rademacher complexity analyses to the non-i.i.d. setting. We conclude the paper by providing generalization bounds for learning with unbounded losses and non-i.i.d. data.