lower bounds
In computational theory, these are limitations that describe the minimal performance or efficiency that any algorithm can achieve for a given problem. Establishing lower bounds helps researchers understand the inherent difficulty of problems in AI.
- A Novel General Framework for Sharp Lower Bounds in Succinct Stochastic Bandits
- Follow-the-Perturbed-Leader Nearly Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit Problems
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback
- Instance-Optimality for Private KL Distribution Estimation
- Isotropic Noise in Stochastic and Quantum Convex Optimization
- Learning from positive and unlabeled examples -Finite size sample bounds
- Learning-Augmented Online Bidding in Stochastic Settings
- Markov Persuasion Processes: Learning to Persuade From Scratch
- On Traceability in $\ell_p$ Stochastic Convex Optimization
- On the necessity of adaptive regularisation: Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls
- Optimal Mistake Bounds for Transductive Online Learning
- Optimal Mistake Bounds for Transductive Online Learning
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
- Pareto Optimal Risk-Agnostic Distributional Bandits with Heavy-Tail Rewards
- Purifying Approximate Differential Privacy with Randomized Post-processing
- Replicable Distribution Testing
- Replicable Online Learning
- Sample-Adaptivity Tradeoff in On-Demand Sampling
- The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets
- Tightening Regret Lower and Upper Bounds in Restless Rising Bandits
- Unifying Proportional Fairness in Centroid and Non-Centroid Clustering