On the Sample Complexity of Data-Driven Inference of the $\mathcal{L}_2$-gain
Lately, data-driven control has become a widespread area of research. A few recent big-data based approaches for data-driven control of nonlinear systems try to use classical input-output techniques to design controllers for systems for which only a finite number of (input-output) samples are known. These methods focus on using the given data to compute bounds on the $\mathcal{L}_2$-gain or on the shortage of passivity from finite input-output data, allowing for the application of the small gain theorem or the feedback theorem for passive systems. One question regarding these methods asks about their sample complexity, namely how many input-output samples are needed to get an approximation of the operator norm or of the shortage of passivity. We show that the number of samples needed to estimate the operator norm of a system is roughly the same as the number of samples required to approximate the system in the operator norm.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
New Bounds on Quantum Sample Complexity of Measurement Classes
This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum …
Learning linear structural equation models in polynomial time and sample complexity
The problem of learning structural equation models (SEMs) from data is a fundamental problem in causal inference. We develop a new algorithm --- which is computationally and statistically efficient and works in the high-…
Causal InferenceComputational EfficiencyA Note on Target Q-learning For Solving Finite MDPs with A Generative Oracle
Q-learning with function approximation could diverge in the off-policy setting and the target network is a powerful technique to address this issue. In this manuscript, we examine the sample complexity of the associated …
Q-LearningIs Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
Q-learning, which seeks to learn the optimal Q-function of a Markov decision process (MDP) in a model-free fashion, lies at the heart of reinforcement learning. When it comes to the synchronous setting (such that indepen…
Natural QuestionsQ-LearningSample-Efficient Learning of Mixtures
We consider PAC learning of probability distributions (a.k.a. density estimation), where we are given an i.i.d. sample generated from an unknown target distribution, and want to output a distribution that is close to the…
Density EstimationPAC learning