upper bounds
Theoretical limits on the performance or complexity of models, providing a benchmark for what can be achieved under certain conditions.
- CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision
- Instance-Optimality for Private KL Distribution Estimation
- Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
- Learning from positive and unlabeled examples -Finite size sample bounds
- Learning-Augmented Online Bidding in Stochastic Settings
- New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
- On Evaluating Policies for Robust POMDPs
- On the sample complexity of semi-supervised multi-objective learning
- Optimal Mistake Bounds for Transductive Online Learning
- Optimal Mistake Bounds for Transductive Online Learning
- Procurement Auctions with Predictions: Improved Frugality for Facility Location
- Root Cause Analysis of Outliers with Missing Structural Knowledge
- Sample-Adaptivity Tradeoff in On-Demand Sampling
- The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets
- The Structural Complexity of Matrix-Vector Multiplication