sample complexity
A measure of the number of training samples required for a learning algorithm to achieve a certain level of performance, often tied to model capacity and data quality.
- A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation
- A Snapshot of Influence: A Local Data Attribution Framework for Online Reinforcement Learning
- A Snapshot of Influence: A Local Data Attribution Framework for Online Reinforcement Learning
- A learnability analysis on neuro-symbolic learning
- APOLLO: Automated LLM and Lean Collaboration for Advanced Formal Reasoning
- Agnostic Active Learning Is Always Better Than Passive Learning
- Agnostic Active Learning Is Always Better Than Passive Learning
- Anchored Diffusion Language Model
- Avoiding exp(R) scaling in RLHF through Preference-based Exploration
- Bayes optimal learning of attention-indexed models
- COLA: Towards Efficient Multi-Objective Reinforcement Learning with Conflict Objective Regularization in Latent Space
- Constrained Best Arm Identification
- Cycle-Sync: Robust Global Camera Pose Estimation through Enhanced Cycle-Consistent Synchronization
- Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport
- Deployment Efficient Reward-Free Exploration with Linear Function Approximation
- Distances for Markov chains from sample streams
- Each Complexity Deserves a Pruning Policy
- Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
- Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds
- Finite-Time Bounds for Average-Reward Fitted Q-Iteration
- Formal Models of Active Learning from Contrastive Examples
- FraPPE: Fast and Efficient Preference-Based Pure Exploration
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards
- From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD
- Generalization Bounds for Rank-sparse Neural Networks
- Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts
- How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension
- How many measurements are enough? Bayesian recovery in inverse problems with general distributions
- Improved Bounds for Swap Multicalibration and Swap Omniprediction
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
- KL-Regularized RLHF with Multiple Reference Models: Exact Solutions and Sample Complexity
- Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws
- Near-Optimal Sample Complexity for Online Constrained MDPs
- Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
- Non-Convex Tensor Recovery from Tube-Wise Sensing
- Offline Actor-Critic for Average Reward MDPs
- Offline imitation learning in $Q^\pi$-realizable MDPs without expert realizability
- On Learning Verifiers and Implications to Chain-of-Thought Reasoning
- On the Convergence of Single-Timescale Actor-Critic
- On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning
- On the Sample Complexity of Differentially Private Policy Optimization
- On the sample complexity of semi-supervised multi-objective learning
- Optimal Best Arm Identification under Differential Privacy
- Optimal Estimation of the Best Mean in Multi-Armed Bandits
- Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
- Private Statistical Estimation via Truncation
- Product Distribution Learning with Imperfect Advice
- Provable Sample-Efficient Transfer Learning Conditional Diffusion Models via Representation Learning
- Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
- Replicable Distribution Testing
- Replicable Online pricing
- Revisiting Agnostic Boosting
- Robust LLM Alignment via Distributionally Robust Direct Preference Optimization
- Robust learning of halfspaces under log-concave marginals
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
- Sample-Adaptivity Tradeoff in On-Demand Sampling
- Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
- Sharp Analysis for KL-Regularized Contextual Bandits and RLHF
- Simple and Optimal Sublinear Algorithms for Mean Estimation
- Smoothed Agnostic Learning of Halfspaces over the Hypercube
- Stabilizing LTI Systems under Partial Observability: Sample Complexity and Fundamental Limits
- State Entropy Regularization for Robust Reinforcement Learning
- State Entropy Regularization for Robust Reinforcement Learning
- Streaming Federated Learning with Markovian Data
- Technical Debt in In-Context Learning: Diminishing Efficiency in Long Context
- The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models
- Tight Generalization Bounds for Large-Margin Halfspaces
- Uniform Wrappers: Bridging Concave to Quadratizable Functions in Online Optimization
- When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective