The minimax optimal rate for minimizing the k-th derivative of a Hölder function from noisy zero-order queries is N^{-(β-1)/(β+k)}, achieved by a kernel-based projected stochastic gradient algorithm.
arXiv preprint arXiv:2002.11457 , year =
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
abstract
The goal of this short note is to provide simple proofs for the "folklore facts" on the sample complexity of learning a discrete probability distribution over a known domain of size $k$ to various distances $\varepsilon$, with error probability $\delta$.
representative citing papers
Defines bridge degree monotone for fermionic non-Gaussianity from Bell-sampling eigenvalues of Lambda, shows non-increase under Gaussian protocols for stronger no-go theorems, and gives polynomial-sample tests for Gaussianity and 2-designs.
Active context sampling algorithm for contextual linear bandits achieves instance-dependent guarantees improving over minimax rate by up to sqrt(d) and reduces samples needed in empirical tasks.
Defines empirical sensitivity and proves Ω(η + √(η d/n)) lower bound (tight up to logs) for any Gaussian mean estimator achieving optimal O(√(d/n)) ℓ₂ error.
Entropy equivalence testing distinguishes p=q from |H(p)−H(q)|≥ε with sample complexity far below closeness testing, enabling efficient closeness tests for low-degree Bayesian networks.
Binary-detector Gaussian boson sampling is proposed for sample-efficient graph classification, with an investigation into its connection to the Torontonian matrix function.
citing papers explorer
-
Gradient-free stochastic optimization of derivatives under strong convexity
The minimax optimal rate for minimizing the k-th derivative of a Hölder function from noisy zero-order queries is N^{-(β-1)/(β+k)}, achieved by a kernel-based projected stochastic gradient algorithm.
-
Fermionic non-Gaussianity via Bell sampling: monotones and efficient quantum algorithms
Defines bridge degree monotone for fermionic non-Gaussianity from Bell-sampling eigenvalues of Lambda, shows non-increase under Gaussian protocols for stronger no-go theorems, and gives polynomial-sample tests for Gaussianity and 2-designs.
-
Active Learning for Stochastic Contextual Linear Bandits
Active context sampling algorithm for contextual linear bandits achieves instance-dependent guarantees improving over minimax rate by up to sqrt(d) and reduces samples needed in empirical tasks.
-
Robust Statistical Estimators with Bounded Empirical Sensitivity
Defines empirical sensitivity and proves Ω(η + √(η d/n)) lower bound (tight up to logs) for any Gaussian mean estimator achieving optimal O(√(d/n)) ℓ₂ error.
-
Entropy Equivalence Testing
Entropy equivalence testing distinguishes p=q from |H(p)−H(q)|≥ε with sample complexity far below closeness testing, enabling efficient closeness tests for low-degree Bayesian networks.
-
Sample efficient graph classification using binary Gaussian boson sampling
Binary-detector Gaussian boson sampling is proposed for sample-efficient graph classification, with an investigation into its connection to the Torontonian matrix function.