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

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization NIPS 2018
Stochastic Anytime Search for Bounding Marginal MAP IJCAI 2018
Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon COLT 2018
Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering ICML 2018
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials COLT 2018
Optimal Solution of the Generalized Dubins Interval Problem RSS 2018
Online Learning Without Prior Information COLT 2017
On the Complexity of Learning Neural Networks NIPS 2017
The Price of Selection in Differential Privacy COLT 2017
Inapproximability of VC Dimension and Littlestone’s Dimension COLT 2017
The Sample Complexity of Optimizing a Convex Function COLT 2017
The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime COLT 2017
Towards Lower Bounds on Number of Dimensions for Word Embeddings IJCNLP 2017
Dimension-Free Iteration Complexity of Finite Sum Optimization Problems NIPS 2016
On the Iteration Complexity of Oblivious First-Order Optimization Algorithms ICML 2016
A Guide to Learning Arithmetic Circuits COLT 2016
On Bayes Risk Lower Bounds JMLR 2016
Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables COLT 2016
Noisy Tensor Completion via the Sum-of-Squares Hierarchy COLT 2016
Variational Information Maximization for Feature Selection NIPS 2016
The Limits of Learning with Missing Data NIPS 2016
Algorithms and matching lower bounds for approximately-convex optimization NIPS 2016
Refined Lower Bounds for Adversarial Bandits NIPS 2016
Local Minimax Complexity of Stochastic Convex Optimization NIPS 2016
On Lower and Upper Bounds in Smooth and Strongly Convex Optimization JMLR 2016