sample-complexity

Code for paper "Efficient Sparse Coding using Hierarchical Riemannian Pursuit," in IEEE Transactions on Signal Processing, Y. Xue, V. K. N. Lau and S. Cai, doi: 10.1109/TSP.2021.3093769.

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

Exact retained-qubit frontier for quantum complement sampling, with optimal decoders, converse bounds, source constructions, and dephasing analysis.

Copy and memory limits for quantum reference identification, with finite-query error bounds and sharp saturation of classical preprocessing before an unknown query arrives.

Copy-optimal loop-phase estimation and the coherent-run cost of learning weak quantum overlaps.

Copy complexity of reproducing labeled quantum trajectories, with unknown measurement probabilities and coherent processing.

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).

Optimal dimension-dependent sample cost of short-time Lindblad simulation, with a universal converse and an explicit collective rank-one processor.

Simulation study: copies needed by the six-copy Bell-difference-sampling stabilizer test under dephasing, depolarising and readout noise. Exact statistics, critical noise vs qubits (3-6), threshold ablation, Pauli-shadow baseline, 5 seeds.

Exact flat-rank quantum classification and rank-dependent limits on coherent learning and classical compilation.

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

Known-state quantum certification under noisy local readout: adaptive sample-complexity bounds, a sharp binary exponent, and fidelity noise thresholds.

Root-fidelity estimation under complete quantum resets, with adaptive converses and a loop-phase application.

This package was the result of master thesis that is seen at link https://tede2.uepg.br/jspui/handle/prefix/152 and in the article https://doi.org/10.5335/rbca.2015.3727.

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

Copy complexity of ordinary quantum reflection programming, with optimal bounds for one target and large batches.

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