Generalization for slowly mixing processes
A bound uniform over various loss-classes is given for data generated by stationary and phi-mixing processes, where the mixing time (the time needed to obtain approximate independence) enters the sample complexity only in an additive way. For slowly mixing processes this can be a considerable advantage over results with multiplicative dependence on the mixing time. The admissible loss-classes include functions with prescribed Lipschitz norms or smoothness parameters. The bound can also be applied to be uniform over unconstrained loss-classes, where it depends on local Lipschitz properties of the function on the sample path.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs
Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon ta…
Multi-Armed Banditsreinforcement-learningReinforcement LearningReinforcement Learning (RL)Active Exploration in Markov Decision Processes
We introduce the active exploration problem in Markov decision processes (MDPs). Each state of the MDP is characterized by a random value and the learner should gather samples to estimate the mean value of each state as …
Faster quantum mixing for slowly evolving sequences of Markov chains
Markov chain methods are remarkably successful in computational physics, machine learning, and combinatorial optimization. The cost of such methods often reduces to the mixing time, i.e., the time required to reach the s…
BIG-bench Machine LearningCombinatorial OptimizationGeneralization bounds for mixing processes via delayed online-to-PAC conversions
We study the generalization error of statistical learning algorithms in a non-i.i.d. setting, where the training data is sampled from a stationary mixing process. We develop an analytic framework for this scenario based …
Generalization BoundsTime SeriesRademacher complexity of stationary sequences
We show how to control the generalization error of time series models wherein past values of the outcome are used to predict future values. The results are based on a generalization of standard i.i.d. concentration inequ…
Time SeriesTime Series Analysis