This paper analyzes momentum Q-learning with finite-sample guarantees.
problem Improving Q-learning performance with momentum schemes.
method Proposes MomentumQ algorithm integrating Nesterov and Polyak's momentum schemes, analyzes convergence for function approximations.
result Establishes finite-sample convergence rates for MomentumQ, demonstrating better performance than vanilla Q-learning.
The paper provides guarantees for high-dimensional DML estimators in observational studies.
problem Estimating treatment effects in observational settings with many covariates.
method Debiased machine learning (DML) with finite-sample guarantees.
result Bounding the deviation of finite-sample distribution from asymptotic Gaussian approximation.
Method constructs nonparametric prediction intervals with finite-sample guarantees.
problem Nonparametric instrumental variable regression with finite-sample coverage.
method Conformal inference framework applied to NPIV, combining with various estimators.
result Distribution-free, finite-sample coverage over chosen IV shifts.
Split conformal prediction provides finite-sample guarantees for black-box models without distributional assumptions.
problem Weak performance guarantees for modern predictive models under minimal assumptions.
method Develops finite-sample guarantees for split conformal prediction, a method that uses nested prediction sets and order statistics.
result The coverage of prediction sets based on order statistics stochastically dominates the Beta distribution.
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.
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.
FaiREE provides fair classification with guarantees for small datasets.
problem Fairness in classification often requires large sample sizes and distributional assumptions.
method FaiREE offers finite-sample and distribution-free fairness guarantees.
result FaiREE achieves optimal accuracy and satisfies various fairness notions.
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.
The paper develops robust tests for detecting independence in synchronous stochastic systems with finite sample guarantees.
problem Detecting independence in synchronous stochastic systems with finite sample guarantees.
method Combines confidence region estimates with permutation tests and dependence measures to detect nonlinear dependence.
result Consistent hypothesis tests for detecting independence under mild assumptions.
Develops methods to adjust prediction set coverage based on post-selection analysis.
problem Adjusting prediction set coverage after initial analysis to better fit specific needs.
method Post-selection conformal inference to adjust miscoverage levels.
result Allows for trade-off between coverage and prediction set quality.
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. A theorem for debiasing machine learning with finite sample guarantees.
problem Calculating confidence intervals for machine learning functionals.
method Debiased machine learning based on bias correction and sample splitting.
result Nonasymptotic debiased machine learning theorem with finite sample guarantees.
The paper shows how to learn causal representations with few environments and finite samples.
problem Learning causal representations from limited data and environments.
method Explicit, finite-sample guarantees with a logarithmic number of interventions.
result Consistent recovery of latent causal graph, mixing matrix, and unknown intervention targets.
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.
Unified theoretical guarantees for distribution-free changepoint detection and testing.
problem Distribution-free changepoint inference with finite-sample validity and consistency.
method Distribution-free changepoint localization using conformal p-values with theoretical guarantees.
result Unified distribution-free guarantees for changepoint detection, localization, and testing.
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/ ε )) . 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.
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.
Develops a method to detect changes in linear systems with temporal correlations.
problem Detect abrupt changes in time series data with temporal correlations.
method Data-dependent threshold for online change point detection in linear dynamical systems.
result Achieves a pre-specified upper bound on the probability of false alarms and provides a finite-sample-based bound for detection probability.
Estimates time-varying parameters from two OLS estimates.
problem Time-varying linear regression with hidden dynamics.
method Combines two OLS estimates for stable linear dynamics.
result Finite sample guarantee on estimation error.
Study non-monotonic loss functions in CRC, achieving valid risk control with large calibration samples.
problem Non-monotonic loss functions in CRC, violating existing theory's monotonicity assumption.
method Finite grid selection, calibration sample size analysis, Lipschitz continuity, monotonicity, distribution shift.
result Valid CRC achieved with large calibration samples, optimal excess risk rate of log ( m ) / n \sqrt{\log(m)/n} log ( m ) / n . New method predicts state evolution for non-first-order algorithms on nonconvex problems.
problem Analyzing nonconvex optimization problems with random data.
method Developed a state evolution for a broader class of algorithms including first-order and saddle point updates.
result Established rigorous state evolution predictions and finite-sample guarantees for non-first-order methods.
New framework calibrates decision robustness using inverse conformal risk control.
problem Inadequate robustness levels in decision-making due to ad hoc choices.
method Constructs valid estimators to trace miscoverage-regret Pareto frontier.
result Provides distribution-free, finite-sample guarantees on robustness levels.
Minimum Description Length prevents overfitting in noisy data.
problem Learning from noisy data with overfitting risk.
method Minimum Description Length learning rule with tempered guarantees.
result Tempered agnostic finite sample learning guarantees and asymptotic behavior characterization.
Study best-response learning dynamics in zero-sum polymatrix games under full and minimal information settings.
problem Learning dynamics in zero-sum polymatrix games under different information settings.
method Two-timescale learning dynamics combining smoothed best-response updates and TD-learning for estimating local payoff functions.
result Polynomial-time finite-sample guarantees for convergence to an ε-Nash equilibrium in the minimal information case.
Paper presents robust boosting methods for label noise.
problem Boosting methods degrade in noisy environments.
method Robust Minimax Boosting (RMBoost) with theoretical guarantees.
result RMBoost provides strong classification accuracy and robustness.
New DP EM algorithm with statistical guarantees for mixture models.
problem Preserving privacy in EM algorithms for mixture models.
method Proposed a DP EM algorithm with statistical guarantees.
result Near optimal estimation error for GMM in DP model.
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.
We provide finite-sample analysis of a general framework for using k-nearest neighbor statistics to estimate functionals of a nonparametric continuous probability density, including entropies and divergences. Rather than plugging a consistent density estimate (which requires k → ∞ k \to \infty k → ∞ as the sample size $n \to \in…
Optimal sparse recovery with decision stumps achieves strong feature selection guarantees.
problem Sparse recovery of active features from high-dimensional data.
method Analysis of single-depth decision trees (decision stumps) for feature selection in linear regression.
result Tight sample performance guarantees for O ( s log p ) O(s \log p) O ( s log p ) , improving upon previous bounds. Optimal transport improves multivariate prediction uncertainty quantification.
problem Uncertainty quantification in multivariate learning tasks, especially in regression and classification.
method Introducing a novel Conformal Prediction procedure using optimal transport to handle multivariate score functions and construct flexible prediction regions.
result Ensures finite-sample, distribution-free coverage guarantees for multivariate prediction sets.
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.
Unified framework for generalized Venn and Venn-Abers calibration for reliable prediction.
problem Asymptotic guarantees of popular distribution-free methods in model calibration.
method Unified framework extending Vovk's approach to generic loss functions, transforming predictors into set-valued predictions.
result Finite-sample set predictions shrink to a single conditionally calibrated prediction, capturing epistemic uncertainty.
Nearest neighbor (k-NN) graphs are widely used in machine learning and data mining applications, and our aim is to better understand what they reveal about the cluster structure of the unknown underlying distribution of points. Moreover, is it possible to identify spurious structures that might arise due to sampling va…
This work obtains novel finite sample guarantees for Principal Component Analysis (PCA). These hold even when the corrupting noise is non-isotropic, and a part (or all of it) is data-dependent. Because of the latter, in general, the noise and the true data are correlated. The results in this work are a significant impr…
The paper develops a theory for iterative self-improvement of models, proving conditions for better performance with easy-to-hard curricula.
problem Lack of theoretical foundation for iterative self-improvement in practical settings.
method Modeling self-improvement as maximum-likelihood fine-tuning on reward-filtered distributions and proving finite-sample guarantees.
result Explicit feedback loop and conditions for better performance with easy-to-hard curricula.
Study learns state representations from observations for control, proving guarantees.
problem Learning state representations from high-dimensional observations for control.
method Cost-driven approach, learning latent state model to predict costs.
result Proves finite-sample guarantees for near-optimal state representation and controller.
New method extends conformal prediction to multivariate settings using optimal transport.
problem Limited applicability of conformal prediction to multivariate real-valued scores.
method Use optimal transport to define vector-ranks and multivariate quantile regions for finite-sample coverage.
result Constructs the first multivariate conformal predictive distributions with finite-sample calibration.
Paper adapts ACI for online multi-step time-series forecasting with coverage guarantees.
problem Achieving reliable error bounds in online multi-step time-series forecasting.
method Adaptive conformal inference (ACI) adapted for multi-step forecasting with dynamic significance levels.
result Proposes a multi-step ACI algorithm with finite-sample coverage guarantees for non-exchangeable data.
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.
Exact inference method for Wasserstein distance with finite-sample coverage.
problem Asymptotic approximation methods for Wasserstein distance lack finite-sample validity.
method Selective Inference inspired approach for exact inference.
result Valid confidence interval for Wasserstein distance with finite-sample coverage.
Study tests whether trade-off functions are above or below benchmarks using finite samples.
problem Testing trade-off functions between unknown distributions.
method Identifies a condition for nontrivial testing, constructs a test with error guarantees, and inverts the test for confidence bands.
result Finite-sample testing is possible under specific structural assumptions about rejection regions.
The paper investigates the convergence of Vendi scores under finite samples and introduces a truncated version for better performance.
problem The Vendi score's convergence is hindered by computational limitations when using large sample sizes.
method The authors introduce the t-truncated Vendi score to address this issue by truncating the eigenspectrum of the kernel matrix.
result The t-truncated Vendi score converges to its asymptotic limit with a smaller number of samples, improving upon the standard Vendi score.
Enhances anomaly detection using multiple reference datasets.
problem Lack of performance with multiple reference datasets.
method Generalizes existing techniques CWoLa and SALAD for multiple reference datasets.
result Improved performance across various settings.
Quick Shift is a popular mode-seeking and clustering algorithm. We present finite sample statistical consistency guarantees for Quick Shift on mode and cluster recovery under mild distributional assumptions. We then apply our results to construct a consistent modal regression algorithm.
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. SPI uses synthetic data to improve predictive inference efficiency.
problem Inefficient predictive inference with scarce calibration data.
method Integrates synthetic data to align nonconformity scores and improve coverage guarantees.
result SPI yields substantially tighter and more informative prediction sets.
The paper develops a method to create non-asymptotic confidence ellipsoids for linear regression without strong noise distribution assumptions.
problem Constructing reliable confidence regions for linear regression with finite sample sizes and general noise distributions.
method The paper introduces the SPS EOA algorithm to create non-asymptotically guaranteed confidence ellipsoids for linear regression problems.
result The sizes of SPS outer ellipsoids are shown to decrease at the optimal rate for linear regression problems.