sample-complexity

We analyze algorithms to learn Gaussian Bayesian networks with known structure up to a bounded error in total variation distance.

OSRL (Optimal Representation Learning in Multi-Task Bandits) comprises an algorithm that addresses the problem of sample complexity with fixed confidence in Multi-Task Bandit problems. Published at the Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI23)

Paper and verification code: a single-copy lower bound for rank-one nonlinear overlap estimation

Python implementation of algorithms for Best Policy Identification in Markov Decision Processes

Reproduction code for the paper 'Structure, Not Size: The Sample and Parameter Complexity of State Tracking in Selective State-Space Models' (selective PD-SSM / diagonal SSM / GRU state-tracking, MLX).

Sharp robustness criteria and optimal certification costs for quantum operations from finite pure-state training sets.

An MLP hits a real sample-complexity wall learning sparse parities, with a Fourier-basis progress measure that sees it coming before the loss does

Learning hidden Pauli measurements from quantum examples with noisy labels: optimal sample bounds, quantum-memory advantage, and conditional hardness under quantum decision-LPN.

Copy-complexity separation between quantum conditional-state synthesis and arbitrary classical descriptions, with stabilizer proofs, finite verification, and a Watrous-based learning route.

Python utilities to compute a lower bound of the expected sample complexity to identify the best arm in a bandit model

Optimal outcome counts, polynomial rigidity, and statistical costs of universal entanglement detection using fixed collective quantum measurements.