lower bound
A theoretical limit that guarantees a minimum performance level or resource requirement for an algorithm in specific contexts, relevant for assessing efficiency.
- Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
- An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise
- Connecting Jensen–Shannon and Kullback–Leibler Divergences: A New Bound for Representation Learning
- Convergence of the Gradient Flow for Shallow ReLU Networks on Weakly Interacting Data
- Eluder dimension: localise it!
- High-Dimensional Calibration from Swap Regret
- High-Dimensional Calibration from Swap Regret
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
- Maximizing the Value of Predictions in Control: Accuracy Is Not Enough
- On the Universal Near Optimality of Hedge in Combinatorial Settings
- On the VC dimension of deep group convolutional neural networks
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
- Optimal Rates in Continual Linear Regression via Increasing Regularization
- Price of Parsimony: Complexity of Fourier Sparsity Testing
- Quantum speedup of non-linear Monte Carlo problems
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
- Replicable Online pricing
- Revisiting Agnostic Boosting
- Robust Contextual Pricing
- Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs
- The Adaptive Complexity of Minimizing Relative Fisher Information
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting
- Tight Lower Bounds and Improved Convergence in Performative Prediction
- True Impact of Cascade Length in Contextual Cascading Bandits