The paper sets sample complexity bounds for identifying LTI systems from a finite set.
problem Identifying an LTI system from a finite set of possible systems using trajectory data.
method Maximum likelihood estimator and information theory tools.
result Upper and lower bounds for sample complexity are derived, independent of stability assumption.
New findings show modern neural networks have finite sample complexity in o-minimal structures.
problem Understanding the learnability of modern neural networks in a broad context.
method Analyzing feedforward neural networks definable in o-minimal structures.
result Modern neural networks, including MLPs, CNNs, GNNs, and transformers, have finite sample complexity in the agnostic PAC setting.
New model-free DR-RL algorithm with finite sample complexity.
problem Limited model-free DR-RL methods with convergence guarantees or sample complexities.
method Integrates Multi-level Monte Carlo (MLMC) technique with threshold mechanism.
result First model-free DR-RL approach with finite sample complexity for total variation and Chi-square divergence.
New method reduces sample complexity for robust reinforcement learning.
problem Finite sample analysis in robust reinforcement learning.
method Stochastic approximation framework with controlled bias, using MLMC techniques and geometric truncation.
result Order-optimal sample complexity of i l d e O ( ε − 2 ) ilde{\mathcal{O}}(ε^{-2}) i l d e O ( ε − 2 ) for robust policy evaluation. Paper extends conformal prediction to complex survey data.
problem Applying distribution-free prediction intervals to complex survey data.
method Design-based conformal prediction for non-exchangeable data.
result Empirical guarantees of finite-sample coverage for complex survey data.
MF-TRPO optimizes MFGs with finite sample guarantees.
problem Computing approximate Nash equilibria in MFGs.
method Extends TRPO to MFGs, providing convergence guarantees.
result Theoretical guarantees on MF-TRPO's convergence.
Efficiently learns polytrees with known skeleton in polynomial time and sample complexity.
problem Learning polytrees with known skeleton structure.
method Proposes an efficient algorithm for learning d d d -polytrees in polynomial time and sample complexity when the skeleton is known. result Establishes finite-sample guarantees for efficient learning of d d d -polytrees. We investigate the statistical complexity of estimating the parameters of a discrete-state Markov chain kernel from a single long sequence of state observations. In the finite case, we characterize (modulo logarithmic factors) the minimax sample complexity of estimation with respect to the operator infinity norm, while…
Paper provides convergence guarantees for off-policy NAC with finite sample complexity.
problem Convergence analysis of off-policy natural actor-critic algorithm.
method Finite-sample analysis with Importance Sampling and Q-trace algorithm.
result Converges to global optimal policy with sample complexity O ( ε − 3 log 2 ( 1 / ε ) ) \mathcal{O}(ε^{-3}\log^2(1/ε)) O ( ε − 3 log 2 ( 1/ ε )) . Improved sample complexity for target Q-learning in finite MDPs with generative oracle.
problem Sample complexity of target Q-learning in finite MDPs with a generative oracle.
method Analyzed target Q-learning algorithm in tabular case with a generative oracle, improved sample complexity.
result Improved sample complexity for target Q-learning in various scenarios.
This work analyzes IRM and ERM from sample complexity perspective, revealing different behaviors under various distribution shifts.
problem Choosing between IRM and ERM for OOD generalization.
method Sample complexity analysis comparing IRM and ERM under different data generation mechanisms.
result IRM is preferred over ERM for certain distribution shifts, leading to better OOD generalization.
This paper sets a lower bound for sample complexity in inverse reinforcement learning.
problem Finding a reward function that generates a desired optimal policy in MDPs.
method Information-theoretic lower bound using geometric construction and Fano's inequality.
result An O ( n log n ) O(n \log n) O ( n log n ) sample complexity lower bound for IRL problems. This work analyzes actor-critic methods for faster convergence.
problem Finite-time analysis and sample complexity of two-time-scale actor-critic methods.
method Non-asymptotic analysis under non-i.i.d. setting, proving convergence to first-order stationary point.
result Actor-critic method finds a first-order stationary point with i l d e O ( ε − 2.5 ) \mathcal{ ilde{O}}(ε^{-2.5}) i l d e O ( ε − 2.5 ) sample complexity. Estimates intrinsic dimension of data for GANs.
problem Estimating intrinsic dimension of high-dimensional data.
method Uses Wasserstein distances for estimation.
result Provides sample complexity bounds for GANs.
New bounds for score matching in polynomial exponential families.
problem Understanding the sample complexity of score matching for polynomial exponential families.
method Non-asymptotic sample complexity analysis for score matching.
result First finite sample bounds for score matching in polynomial exponential families.
An algorithm solves optimization problems with large sample sets, improving worst-case complexity.
problem Continuous nonlinear-equality-constrained optimization problems with large numbers of terms.
method Progressively sampled finite sets to solve related problems with growing sample sizes.
result Better worst-case sample complexity compared to solving with full sets of samples.
In the information-based paradigm of inference, model selection is performed by selecting the candidate model with the best estimated predictive performance. The success of this approach depends on the accuracy of the estimate of the predictive complexity. In the large-sample-size limit of a regular model, the predicti…
We study the sample complexity of private synthetic data generation over an unbounded sized class of statistical queries, and show that any class that is privately proper PAC learnable admits a private synthetic data generator (perhaps non-efficient). Previous work on synthetic data generators focused on the case that …
Study shows DQN's performance degrades with temporal dependence in data.
problem Temporal dependence in replayed data affects DQN's performance.
method Modelled τ τ τ -mixing data, derived risk bounds, and empirical validation. result Temporal dependence leads to a degradation in DQN's performance rate.
We resolve the open problem of optimal sample complexity for multicalibration and deterministic predictors.
problem Optimal sample complexity for multicalibration and deterministic predictors
method Minimax-optimal multicalibration algorithm and generalization to OI predictors
result Minimax-optimal multicalibration algorithm and deterministic predictors with optimal sample complexity
Compact learning results across various loss functions.
problem Understanding sample complexity in transductive learning.
method Analyzing finite projections and sample complexities for different loss functions.
result Exact compactness of sample complexity holds broadly across realizable and agnostic learning.
The OLS estimator optimally identifies stable linear systems with a finite number of samples.
problem Identifying stable linear systems with a finite number of samples.
method Finite-time analysis of the Ordinary Least Squares (OLS) estimator for stable linear systems.
result The OLS estimator achieves optimal sample complexity for stable systems, matching existing lower bounds up to universal factors.
Paper analyzes NAC with neural networks for efficient policy optimization.
problem Improving sample and iteration complexity in policy optimization.
method Entropy regularization, averaging, neural network approximation, and optimization techniques.
result Entropy regularization and averaging ensure stability and sharp sample complexity bounds.
New bounds for SMC show its advantage over MCMC in multimodal distributions.
problem Estimating expectations under multimodal distributions with slow global mixing.
method Proves finite sample complexities for SMC with local mixing times, addressing bias through sequential resampling.
result SMC provides fully polynomial time approximation for multimodal problems.
The paper explores when linear system identification is hard or easy, especially for under-actuated systems.
problem Statistical hardness of learning linear systems, especially under-actuated or under-excited systems.
method Using tools from minimax theory and recent statistical tools for finite sample analysis of system identification.
result The controllability index of linear systems affects the sample complexity of identification, making some systems hard to learn.
Improved privacy-preserving methods for estimating multiple samples from distributions.
problem Estimating multiple samples from distributions while maintaining privacy.
method Developed new multi-sampling techniques for differentially private data estimation.
result Achieved significant reduction in sample complexity for multi-sampling from finite domains and Gaussian distributions.
Paper reduces sample complexity for bilinear systems identification to nearly constant.
problem Identifying discrete-time bilinear systems under bounded disturbances.
method Uses trajectory-dependent regressors and polynomial mean-square state growth analysis.
result Proves sample complexity of O ~ ( 1 / ε ) \widetilde{\mathcal O}(1/ε) O ( 1/ ε ) for estimation error ε ε ε . We prove extension theorems for several geometric properties such as asymptotic property C (APC), finite decomposition complexity (FDC), strict finite decomposition complexity (sFDC) which are weakenings of Gromov's finite asymptotic dimension (FAD). The context of all theorems is a finitely generated group G G G with a …
New learning rule for quantum measurement classes overcomes uniform convergence issues.
problem Characterizing learnability of POVM hypothesis classes in quantum settings.
method Introduced a new learning rule called denoised ERM to address uniform convergence issues.
result Characterized learnability conditions and sample complexity bounds for POVM classes.
In this short note we observe that the sample complexity of PAC machine learning of various concepts, including learning the maximum (EMX), can be exactly determined when the support of the probability measures considered as models satisfies an a-priori bound. This result contrasts with the recently discovered undecida…
This paper analyzes the sample complexity of SPS method for scalar linear regression.
problem Analyzing the sample complexity of the Sign-Perturbed Sums (SPS) identification method.
method The paper provides high probability upper bounds for the sizes of SPS confidence intervals under different sets of assumptions.
result The sizes of SPS confidence intervals shrink at a geometric rate around the true parameter, if observation noises are subgaussian.
This manuscript studies statistical properties of linear classifiers obtained through minimization of an unregularized convex risk over a finite sample. Although the results are explicitly finite-dimensional, inputs may be passed through feature maps; in this way, in addition to treating the consistency of logistic reg…
New bounds for private learning of high-dimensional Gaussian distributions.
problem Learning high-dimensional Gaussian distributions under differential privacy constraints.
method Analytic tools for constructing global covers from local covers, modified hypothesis selection techniques.
result Near-optimal sample complexity bounds for general Gaussians, conjectured to be near-optimal in the general case.
Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete d × N d \times N d × N matrix is finitely rank- r r r completable if there are at …
This work improves Q-learning for average-reward MDPs, reducing sample and communication complexities in federated settings.
problem Improving sample complexity of Q-learning for average-reward MDPs.
method Simple Q-learning algorithm with carefully chosen parameters for both single-agent and federated scenarios.
result Established first federated Q-learning algorithm for average-reward MDPs with provable efficiency in sample and communication complexities.
For a finite function class we describe the large sample limit of the sequential Rademacher complexity in terms of the viscosity solution of a G G G -heat equation. In the language of Peng's sublinear expectation theory, the same quantity equals to the expected value of the largest order statistics of a multidimensional $…
New model-free RL algorithm tackles robust average-reward problems with finite sample complexity analysis.
problem Long-term decision-making in environments with varying dynamics.
method Proposes Robust Halpern Iteration (RHI) algorithm based on a black-box sampling oracle and multi-level Monte-Carlo estimator.
result Achieves ε-optimal robust policy with sample complexity of O(1/ε^(2+o(1))) under generative model setting.
This study approximates distances between Gaussian processes and covariance operators using RKHS.
problem Approximating distances between Gaussian processes and covariance operators from finite samples.
method Using reproducing kernel Hilbert space (RKHS) covariance and cross-covariance operators, the study shows how to consistently and efficiently estimate Sinkhorn divergence from finite samples.
result Convergence rates are dimension-independent and of the same order as Hilbert-Schmidt distance.
New algorithms reduce rejection sampling complexity for shape-constrained distributions.
problem Generating exact samples from shape-constrained distributions efficiently.
method Sublinear query complexity algorithms for rejection sampling.
result Sublinear complexity algorithms for sampling from shape-constrained distributions.
Paper provides finite-sample guarantees for Wasserstein DRO without dimensionality curse.
problem Tackles empirical success of Wasserstein DRO in operations and ML with performance guarantees.
method Develops non-asymptotic framework for analyzing out-of-sample performance and generalization bound.
result First finite-sample guarantee for generic Wasserstein DRO problems without curse of dimensionality.
Demonstration-regularized RL reduces sample complexity for policy identification.
problem Improving reinforcement learning's sample efficiency with expert demonstrations.
method KL-regularization of behavior cloning using expert demonstrations.
result Demonstration-regularized RL achieves optimal policy identification with reduced sample complexity.
New algorithm reduces sample complexity for planning in MDPs.
problem Planning in MDPs with unknown transitions.
method MDP-GapE, a trajectory-based MCTS algorithm.
result Proves upper bound on sample complexity in terms of sub-optimality gaps.
Study batch reinforcement learning methods for personalized medical treatments.
problem Batch reinforcement learning for personalized medical treatments.
method Direct policy learning and model-based learning approaches.
result Model-based learning is impossible with finite model classes but feasible with relaxed conditions.
This paper analyzes sampling from heavy-tailed distributions using discretized Itô diffusions.
problem Sampling from heavy-tailed distributions with finite variance.
method Mean-square analysis of discretized Itô diffusions with weighted Poincaré inequalities.
result Explicit iteration complexity for obtaining samples close to target distributions in Wasserstein-2 metric.
New methods stabilize Q-learning with linear approximations.
problem Stabilizing Q Q Q -learning with linear function approximation. method Target network and truncation.
result Provably stable Q Q Q -learning with linear function approximation. New algorithm reduces sample and communication complexities in federated Q-learning.
problem Optimal Q-function learning in federated Q-learning with limited communication.
method Introduced Fed-DVR-Q algorithm for order-optimal sample and communication complexities.
result Complete characterization of sample-communication complexity trade-off.
Study on distributional TD learning with linear approximations for better return estimation.
problem Estimating the return distribution of a policy in reinforcement learning.
method Finite-sample analysis of distributional TD learning with linear function approximation, using the linear-categorical Bellman equation and exponential stability arguments for products of random matrices.
result Sample complexity of linear distributional TD learning matches that of classic linear TD learning, indicating similar difficulty in estimating return distribution versus its expectation.
Unified method for MMD variance estimation improves accuracy and computational efficiency.
problem Variance estimation for MMD in nonparametric testing.
method Unified finite-sample characterization of MMD variance through U-statistic and Hoeffding decomposition; exact acceleration method for univariate case.
result Unified estimators improve accuracy and computational efficiency for MMD variance.