conftrace_

lower bound

173 papers

Explore in graph

Also known as

LB

Co-occurring keywords

sample complexity (1169) convex optimization (1321) learning theory (519) differential privacy (1016) statistical query (50) multi-armed bandit (1098) regret bound (1926) computational complexity (399) query complexity (183) oracle complexity (65)

Papers

Lower Bounds on the Bayesian Risk via Information Measures JMLR 2024
A Law of Robustness beyond Isoperimetry ICML 2023
Tight Data Access Bounds for Private Top-$k$ Selection ICML 2023
Lower Bounds and Accelerated Algorithms for Bilevel Optimization JMLR 2023
Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron COLT 2023
SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians COLT 2023
Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions ICML 2023
On The Computational Complexity of Self-Attention ALT 2023
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions NIPS 2023
On the Lower Bound of Minimizing Polyak-Łojasiewicz functions COLT 2023
A Lower Bound for Linear and Kernel Regression with Adaptive Covariates COLT 2023
Empirical Sufficiency Lower Bounds for Language Modeling with Locally-Bootstrapped Semantic Structures ACL 2023
Lower Bounds on Adaptive Sensing for Matrix Recovery NIPS 2023
SQ Lower Bounds for Learning Mixtures of Linear Classifiers NIPS 2023
How many samples are needed to leverage smoothness? NIPS 2023
On Lower Bounds for Maximin Share Guarantees IJCAI 2023
Curvature and complexity: Better lower bounds for geodesically convex optimization COLT 2023
Can semi-supervised learning use all the data effectively? A lower bound perspective NIPS 2023
Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond ICML 2023
Exponential Lower Bounds for Fictitious Play in Potential Games NIPS 2023
From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds AAAI 2023
On Coresets for Clustering in Small Dimensional Euclidean spaces ICML 2023
An Exact Algorithm for the Minimum Dominating Set Problem IJCAI 2023
The Price of Differential Privacy under Continual Observation ICML 2023
Fisher information lower bounds for sampling ALT 2023