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.
Estimates barycenter in geodesic spaces with finite sample bounds.
problem Estimating the barycenter of a distribution in geodesic spaces.
method Finite sample error bounds, Hoeffding- and Bernstein-type concentration inequalities, efficient algorithms.
result Statistical guarantees for efficient barycenter computation.
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. This work uses sampling theory to analyze smoothness and error bounds of finite neural networks.
problem Analyzing the function space of finite neural networks and providing error bounds.
method Applying sampling theory to finite neural networks with non-expansive activation functions, considering both deterministic and random sampling.
result Novel error bounds for univariate neural networks under band-limited input assumption, highlighting the advantage of deterministic uniform sampling.
The paper analyzes off-policy TD-learning using generalized Bellman operators and provides finite-sample bounds.
problem High variance in off-policy TD-learning due to importance sampling.
method Derives finite-sample bounds for off-policy TD-like algorithms using generalized Bellman operators.
result First-known finite-sample guarantees for several off-policy TD algorithms.
Paper analyzes PSGLD for adaptive IRL with finite-sample bounds.
problem Estimating cost function of a forward learner using noisy gradients.
method Passive stochastic gradient Langevin dynamics (PSGLD) algorithm.
result Explicit bounds on 2-Wasserstein distance between PSGLD sample measure and stationary measure.
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.
Unified framework for finite-sample RL algorithms using Lyapunov theory.
problem Finite-sample convergence guarantees of asynchronous RL algorithms.
method Reformulate RL algorithms as Markovian SA, develop Lyapunov analysis.
result Mean-square error bounds and convergence for various RL algorithms.
We improve maximum likelihood for location estimation in finite samples.
problem Estimating a parameter from samples with unknown or varying distribution.
method Use smoothed Fisher information for finite sample size and varying distributions.
result Recover optimal estimation theory for finite n n n and arbitrary f f f . Kernel smoothing on unknown manifolds with bounds and asymptotic normality.
problem Data on unknown manifolds without boundaries.
method Finite sample bounds and asymptotic normality for kernel smoothing and its derivatives.
result Established finite sample bounds and asymptotic normality for kernel smoothing.
The paper analyzes GTD algorithms with finite-sample bounds.
problem Convergence rate analysis of GTD family of algorithms.
method Formulated as stochastic gradient algorithms and analyzed using saddle-point error.
result Obtained finite-sample bounds on GTD performance.
In this paper, we study non-asymptotic deviation bounds of the least squares estimator in Gaussian AR( n n n ) processes. By relying on martingale concentration inequalities and a tail-bound for χ 2 χ^2 χ 2 distributed variables, we provide a concentration bound for the sample covariance matrix of the process output. With this, …
This study analyzes LTS in sparse models with finite sample error bounds.
problem Robust regression in high-dimensional sparse models with limited data.
method Non-asymptotic analysis of LTS error bounds.
result Established finite sample error bounds for LTS in sparse models.
The study tightens bounds on binomial probabilities and minimums using KL-divergence.
problem Tightening bounds on binomial probabilities and minimums of i.i.d. Binomials.
method Applied Sanov's theorem to derive upper and lower bounds on binomial tail probabilities and minimums, expressed in terms of KL-divergence.
result High probability upper and lower bounds on the minimum of i.i.d. Binomial random variables, finite sample, asymptotically tight.
Study bounds variance modulation function for K-spider distributions.
problem Bounding variance modulation function for K-spider distributions.
method Used folded moments and total probabilities of spider legs.
result Gave an interval for the variance modulation function.
The study sets lower bounds on MMSE for inferring sensitive features from noisy data.
problem Estimating sensitive features from noisy observations of correlated features.
method Adversarial evaluation framework based on MMSE estimation with theoretical lower bounds.
result Derives closed-form bounds for linear models, showing optimality in noise variance.
The MDL two-part coding index of resolvability \textit{index of resolvability} index of resolvability provides a finite-sample upper bound on the statistical risk of penalized likelihood estimators over countable models. However, the bound does not apply to unpenalized maximum likelihood estimation or procedures with exceedingly small penalties. In this paper,…
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. In Bayesian inference, the posterior distributions are difficult to obtain analytically for complex models such as neural networks. Variational inference usually uses a parametric distribution for approximation, from which we can easily draw samples. Recently discrete approximation by particles has attracted attention …
Detect changes in noisy dynamical systems using empirical approximations and finite-sample bounds.
problem Change detection in noisy dynamical systems
method Partition-based empirical approximations and finite-state stationary distribution stability
result Finite-sample bound for empirical stationary density
Sparse feature selection improves batch RL efficiency.
problem High-dimensional batch RL with many features.
method Sparse linear function approximation, Lasso, group Lasso, fitted Q-evaluation, fitted Q-iteration.
result Sparse feature selection makes batch RL more sample efficient.
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…
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 introduces a frequency-domain estimator for low-order systems from noisy data.
problem Estimating frequency responses of low-order systems from noisy measurements.
method Uses a quadratic data-fitting term regularized by the nuclear norm of a Loewner matrix, subject to a convex stability constraint.
result Proves a finite-sample error bound and extends it to all frequencies through rational interpolation.
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.
New bounds show current methods overestimate system parameter errors.
problem Current bounds overestimate parameter errors in system identification.
method Utilized asymptotic normality and second-order decomposition.
result Obtained finite-sample bounds matching optimal rates up to constants.
The study establishes minimax bounds for estimating operators from noisy samples.
problem Estimating unknown operators between Hilbert spaces from noisy data.
method Developed a minimax theory for uniformly bounded Lipschitz operators, proving lower and upper bounds.
result Sharp characterizations of minimax risk for generic Lipschitz operators, showing a curse of sample complexity.
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.
Improved mean estimation for symmetric distributions with finite-sample guarantees.
problem Estimating the mean of a symmetric distribution from samples.
method Using Fisher information rate for finite-sample guarantees.
result Finite-sample convergence close to subgaussian with variance 1/(n * I_r), where I_r is r-smoothed Fisher information.
Unified bounds for iterative algorithms with Gaussian data matrices.
problem Establishing non-asymptotic bounds for iterative algorithms with Gaussian data.
method Explicit coupling between iterates and Gaussian process with deterministic covariance.
result Tight, dimension-free bounds for generalized first-order methods.
Paper analyzes online tensorial ICA convergence with stochastic approximation.
problem Online tensorial ICA convergence analysis.
method Stochastic approximation for nonconvex optimization.
result Sharp finite-sample error bound of O ~ ( d / T ) \tilde{O}(\sqrt{d/T}) O ~ ( d / T ) . End-to-end algorithm for controlling bilinear systems with probabilistic noise.
problem Controlling bilinear systems with noisy data.
method Proposes an end-to-end algorithm using statistical learning theory and robust controller design.
result Derived finite sample identification error bounds and structurally suitable for control.
The paper analyzes the efficiency of gradient estimation methods in noisy function evaluations.
problem Estimating gradients of smooth functions using noisy function evaluations.
method Information-theoretic lower bounds and finite difference method analysis.
result The finite difference method is not minimax optimal, suggesting room for improvement in gradient estimation.
New algorithm detects changes in heavy-tailed data streams.
problem Detecting changes in heavy-tailed data streams.
method Clipped Stochastic Gradient Descent (SGD) combined with union bound.
result First algorithm with finite-sample false-positive rate guarantees for heavy-tailed data.
In this paper, we analyze the finite sample complexity of stochastic system identification using modern tools from machine learning and statistics. An unknown discrete-time linear system evolves over time under Gaussian noise without external inputs. The objective is to recover the system parameters as well as the Kalm…
New bounds derived for KG algorithm's performance in finite time.
problem Best arm identification problem in multi-armed bandit.
method Theoretical analysis of finite-time performance, deriving bounds for sample allocation, error probability, and regret.
result Upper and lower bounds for the probability of error and simple regret of the KG algorithm.
Study provides bounds for estimating intrinsic dimension using Gaussian kernels.
problem Estimating intrinsic dimension from data.
method Finite-sample concentration and anti-concentration bounds for Gaussian kernel sums.
result Explicit dependence on sample size, bandwidth, and geometric parameters.
This study examines biases in flow matching samplers using finite-sample estimation.
problem Biases in flow matching samplers when using finite-sample surrogates.
method Finite-sample plug-in estimation and hierarchy of empirical FM models.
result Exact empirical minimizer and smoothed plug-in regime identified for affine conditional flows.
We identify linear models from nonlinear systems with initialization constraints.
problem Identifying linear models from nonlinear systems with initialization constraints.
method Multiple trajectories-based deterministic data acquisition algorithm followed by regularized least squares.
result We provide a finite sample error bound on the learned linearized dynamics.
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.
Develops robust MDPs for unknown disturbances with performance guarantees.
problem Unknown disturbance distribution in MDPs.
method Empirical distribution, sublevel set of distance function, weak convergence, concentration inequality.
result Robust optimal value function converges to true optimal value function with increasing sample sizes.
Estimating entropy and mutual information consistently is important for many machine learning applications. The Kozachenko-Leonenko (KL) estimator (Kozachenko & Leonenko, 1987) is a widely used nonparametric estimator for the entropy of multivariate continuous random variables, as well as the basis of the mutual inform…
Study improves understanding of non-differentiable penalties in high-dimensional settings.
problem Theoretical understanding of non-differentiable penalties like generalized LASSO and nuclear norm in high-dimensional settings.
method Proportional high-dimensional regime analysis with finite sample upper bounds on expected squared error.
result LO provides accurate estimation of out-of-sample risk in high-dimensional settings.
CNFs learn distributions from samples with error bounds.
problem Learning probability distributions from finite samples.
method Continuous normalizing flows with linear interpolation and flow matching objective function.
result Non-asymptotic error bounds for distribution estimator in Wasserstein-2 distance.
New Thompson sampling algorithm reduces regret for exponential family bandits.
problem Minimizing regret in multi-armed bandit problems with exponential family rewards.
method Proposes ExpTS and ExpTS + ^+ + algorithms using novel sampling distributions. result Minimizes both finite-time and asymptotic regret for exponential family rewards.
Learnable multiclass hypothesis classes don't always have a sample compression scheme of fixed size.
problem The limitation of sample compression schemes for multiclass hypothesis classes.
method Analysis of DS dimension and sample compression schemes.
result Learnable multiclass hypothesis classes do not always have a sample compression scheme of fixed size.
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 learn linear models from nonlinear systems using multiple trajectories and regularization.
problem Identifying linear models from data when the underlying dynamics are nonlinear.
method Multiple trajectories data acquisition followed by regularized least squares.
result Learn linearized dynamics with arbitrarily small error given enough samples.