:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bousquet, Olivier, Kane, Daniel, Moran, Shay
Format:	Preprint
Published:	2019
Subjects:	Machine Learning Computational Complexity Information Theory Probability
Online Access:	https://arxiv.org/abs/1902.05876
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Learning from Equivalence Queries, Revisited
by: Braverman, Mark, et al.
Published: (2026)

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
by: Li, Cheuk Ting
Published: (2024)

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
by: Thornton, Mitchell A.
Published: (2026)

Optimal Estimation in Orthogonally Invariant Generalized Linear Models: Spectral Initialization and Approximate Message Passing
by: Zhang, Yihan, et al.
Published: (2026)

Privacy-aware Berrut Approximated Coded Computing for Federated Learning
by: Luaña, Xavier Martínez, et al.
Published: (2024)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
by: Saha, Barna, et al.
Published: (2024)

Detection of local geometry in random graphs: information-theoretic and computational limits
by: Bok, Jinho, et al.
Published: (2026)

Tensor cumulants for statistical inference on invariant distributions
by: Kunisky, Dmitriy, et al.
Published: (2024)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
by: Chen, Sitan, et al.
Published: (2026)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
by: Lou, Mengqi, et al.
Published: (2025)

Information-theoretic generalization bounds for learning from quantum data
by: Caro, Matthias, et al.
Published: (2023)

Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise
by: Dudeja, Rishabh, et al.
Published: (2024)

Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing
by: Zhang, Yihan, et al.
Published: (2023)

A Unified MDL-based Binning and Tensor Factorization Framework for PDF Estimation
by: Musab, Mustafa, et al.
Published: (2025)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
by: Li, Rupert, et al.
Published: (2025)

Optimal certification of constant-local Hamiltonians
by: Lee, Junseo, et al.
Published: (2025)

Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery
by: Kovačević, Filip, et al.
Published: (2025)

Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence
by: Pananjady, Ashwin, et al.
Published: (2024)

Optimal lower bounds for Quantum Learning via Information Theory
by: Hadiashar, Shima Bab, et al.
Published: (2023)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
by: Lowe, Angus, et al.
Published: (2022)

Taming Barren Plateaus in Arbitrary Parameterized Quantum Circuits without Sacrificing Expressibility
by: Chen, Zhenyu, et al.
Published: (2025)

Submodular Information Selection for Hypothesis Testing with Misclassification Penalties
by: Bhargav, Jayanth, et al.
Published: (2024)

Algorithmic causal structure emerging through compression
by: Wendong, Liang, et al.
Published: (2025)

The Agent Capability Problem: Predicting Solvability Through Information-Theoretic Bounds
by: Lutati, Shahar
Published: (2025)

Noisy Quantum Learning Theory
by: Cotler, Jordan, et al.
Published: (2025)

Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions
by: Tsui, Darin, et al.
Published: (2025)

Efficient Pauli channel estimation with logarithmic quantum memory
by: Chen, Sitan, et al.
Published: (2023)

Near-Optimal Clustering in Mixture of Markov Chains
by: Lee, Junghyun, et al.
Published: (2025)

On Universality of Non-Separable Approximate Message Passing Algorithms
by: Lovig, Max, et al.
Published: (2025)

A discrete Benamou-Brenier formulation of Optimal Transport on graphs
by: Morris, Kieran, et al.
Published: (2026)

The Exact Replica Threshold for Nonlinear Moments of Quantum States
by: Zeng, Shuai
Published: (2026)

Rigorous Implications of the Low-Degree Heuristic
by: Hsieh, Jun-Ting, et al.
Published: (2026)

On Statistical Estimation of Edge-Reinforced Random Walks
by: Qinghua, et al.
Published: (2025)

Variational Optimality of Föllmer Processes in Generative Diffusions
by: Chen, Yifan, et al.
Published: (2026)

Two-Sided Bounds for Entropic Optimal Transport via a Rate-Distortion Integral
by: Liu, Jingbo
Published: (2026)

A computational phase transition for learning-to-sample from Ising models
by: Risteski, Andrej, et al.
Published: (2026)

Sparsifying Suprema of Gaussian Processes
by: De, Anindya, et al.
Published: (2024)

Estimating stationary mass, frequency by frequency
by: Nakul, Milind, et al.
Published: (2025)

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)