Selected Publications by Topic


For a more complete list, see my Google Scholar profile or my CV

Survey/Tutorial

Group Testing: An Information Theory Perspective
Matthew Aldridge, Oliver Johnson, and Jonathan Scarlett
Foundations and Trends in Communications and Information Theory, Volume 15, Issue 3-4, pp. 196-392, Dec. 2019.
[publisher] [arxiv]
An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation
Jonathan Scarlett and Volkan Cevher
Book chapter in Information-Theoretic Methods in Data Science (Rodrigues/Eldar), Cambridge University Press, 2021
[publisher] [arxiv]
Information-Theoretic Foundations of Mismatched Decoding
Jonathan Scarlett, Albert Guillén i Fàbregas, Anelia Somekh-Baruch, and Alfonso Martinez
Foundations and Trends in Communications and Information Theory, Volume 17, Issue 2-3, pp. 149-400, Aug. 2020.
[publisher] [arxiv]

Group Testing

Noisy Adaptive Group Testing via Noisy Binary Search
Bernard Teo and Jonathan Scarlett
In submission (Preprint)
[arxiv]
Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
Eric Price, Jonathan Scarlett, and Nelvin Tan
In submission (Preprint)
[arxiv]
Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms
Oliver Gebhard, Max Hahn-Klimroth, Olaf Parczyk, Manuel Penschuck, Maurice Rolvien, Jonathan Scarlett, and Nelvin Tan
In submission (Preprint)
[arxiv]
Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes
Wei Heng Bay, Eric Price, and Jonathan Scarlett
Accepted to Information and Inference: A Journal of the IMA, 2021
[arxiv]
Sublinear-Time Non-Adaptive Group Testing with O(k log n) Tests via Bit-Mixing Coding
Steffen Bondorf, Binbin Chen, Jonathan Scarlett, Haifeng Yu, and Yuda Zhao
IEEE Transactions on Information Theory, Volume 67, Issue 3, pp. 1559-1570, March 2021
[ieee] [arxiv]
On the All-Or-Nothing Behavior of Bernoulli Group Testing
Lan V. Truong, Matthew Aldridge, and Jonathan Scarlett
IEEE Journal on Selected Areas in Information Theory (Special Issue on Estimation and Inference), Volume 1, Issue 3, pp. 669-680, Nov. 2020
[ieee] [arxiv]
A Fast Binary Splitting Approach to Non-Adaptive Group Testing
Eric Price and Jonathan Scarlett
International Conference on Randomization and Computation (RANDOM), 2020
[drops] [arxiv]
Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
Jonathan Scarlett and Oliver Johnson
IEEE Transactions on Information Theory, Volume 66, Issue 6, pp. 3775-3797, June 2020
[ieee] [arxiv]
A MaxSAT-Based Framework for Group Testing
Bishwamittra Ghosh, Lorenzo Ciampiconi, Jonathan Scarlett, and Kuldeep S. Meel
AAAI Conference on Artificial Intelligence, 2020
[aaai] [github]
Noisy Adaptive Group Testing: Bounds and Algorithms
Jonathan Scarlett
IEEE Transactions on Information Theory, Volume 65, Issue 6, pp. 3646-3661, June 2019
[ieee] [arxiv]
Performance of Group Testing Algorithms with Near-Constant Tests-Per-Item
Oliver Johnson, Matthew Aldridge, and Jonathan Scarlett
IEEE Transactions on Information Theory, Volume 65, Issue 2, pp. 707-723, Feb. 2019
[ieee] [arxiv]
Near-Optimal Noisy Group Testing via Separate Decoding of Items
Jonathan Scarlett and Volkan Cevher
IEEE Journal on Selected Topics in Signal Processing (Special Issue on Information-Theoretic Methods in Data Acquisition, Analysis, and Processing), Volume 12, Issue 5, pp. 902-915, Oct. 2018
[ieee] [arxiv]
Phase Transitions in Group Testing
Jonathan Scarlett and Volkan Cevher
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016
[acm] [epfl]

Bayesian Optimization and Bandits

Gaussian Process Bandit Optimization with Few Batches
Zihan Li and Jonathan Scarlett
In submission (Preprint)
[arxiv]
Tight Regret Bounds for Noisy Optimization of a Brownian Motion
Zexin Wang, Vincent Y. F. Tan, and Jonathan Scarlett
In submission (Preprint)
[arxiv]
On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
Xu Cai and Jonathan Scarlett
International Conference on Machine Learning (ICML), 2021
[arxiv]
Lenient Regret and Good-Action Identification in Gaussian Process Bandits
Xu Cai, Selwyn Gomes, and Jonathan Scarlett
International Conference on Machine Learning (ICML), 2021
[arxiv]
Stochastic Linear Bandits Robust to Adversarial Attacks
Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett
International Conference on Artificial Intelligence and Statistics (AISTATS), 2021
[arxiv]
High-Dimensional Bayesian Optimization via Tree-Structured Graphical Models
Eric Han, Ishank Arora, and Jonathan Scarlett
AAAI Conference on Artificial Intelligence, 2021
[arxiv]
Corruption-Tolerant Gaussian Process Bandit Optimization
Ilija Bogunovic, Andreas Krause, and Jonathan Scarlett
International Conference on Artificial Intelligence and Statistics (AISTATS), 2020
[pmlr] [arxiv]
Adversarially Robust Optimization with Gaussian Processes
Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher
Conference on Neural Information Processing Systems (NeurIPS), 2018
[neurips] [arxiv]
Tight Regret Bounds for Bayesian Optimization in One Dimension
Jonathan Scarlett
International Conference on Machine Learning (ICML), 2018
[pmlr] [arxiv]
High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups
Paul Rolland, Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher
International Conference on Artificial Intelligence and Statistics (AISTATS), 2018
[pmlr] [arxiv]
Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher
Conference on Learning Theory (COLT), 2017
[pmlr] [arxiv]
Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
Ilija Bogunovic, Jonathan Scarlett, Andreas Krause, and Volkan Cevher
Conference on Neural Information Processing Systems (NeurIPS), 2016
[neurips] [arxiv]
Time-Varying Gaussian Process Bandit Optimization
Ilija Bogunovic, Jonathan Scarlett, and Volkan Cevher
International Conference on Artificial Intelligence and Statistics (AISTATS), 2016
[pmlr] [arxiv]

Sparsity and Compressive Sensing

Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors
Zhaoqiang Liu, Subhroshekhar Ghosh, and Jonathan Scarlett
Accepted to Conference on Neural Information Processing Systems (NeurIPS), 2021
[arxiv]
The Generalized Lasso with Nonlinear Observations and Generative Priors
Zhaoqiang Liu and Jonathan Scarlett
Conference on Neural Information Processing Systems (NeurIPS), 2020
[neurips] [arxiv]
Support Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limits
Lan V. Truong and Jonathan Scarlett
IEEE Transactions on Information Theory, Volume 66, Issue 12, pp. 7887-7910, December 2020
[ieee] [arxiv]
Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors
Zhaoqiang Liu, Selwyn Gomes, Avtansh Tiwari, and Jonathan Scarlett
International Conference on Machine Learning (ICML), 2020
[icml] [arxiv]
Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models
Zhaoqiang Liu and Jonathan Scarlett
IEEE Journal on Selected Areas in Information Theory (Special Issue on Deep Learning), Volume 1, Issue 1, pp. 292-303, May 2020
[ieee] [arxiv]
An Adaptive Sublinear-Time Block Sparse Fourier Transform
Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh
ACM Symposium on Theory of Computing (STOC), 2017
[acm] [arxiv]
Limits on Support Recovery with Probabilistic Models: An Information-Theoretic Framework
Jonathan Scarlett and Volkan Cevher
IEEE Transactions on Information Theory, Volume 63, Issue 1, pp. 593-620, Jan. 2017
[ieee] [arxiv]
Learning-Based Compressive Subsampling
Luca Baldassarre, Yen-Huan Li, Jonathan Scarlett, Baran Gözcü, Ilija Bogunovic, and Volkan Cevher
IEEE Journal on Selected Topics in Signal Processing (Special Issue on Structured Matrices in Signal and Data Processing), Volume 10, Issue 4, pp. 809-822, March 2016
[ieee] [arxiv]
Sparsistency of l1-Regularized M-estimators
Yen-Huan Li, Jonathan Scarlett, Pradeep Ravikumar, and Volkan Cevher
International Conference on Artificial Intelligence and Statistics (AISTATS), 2015
[pmlr] [arxiv]
Compressed Sensing with Prior Information: Information-Theoretic Limits and Practical Decoders
Jonathan Scarlett, Jamie Evans, and Subhrakanti Dey
IEEE Transactions on Signal Processing, Volume 61, Issue 2, pp. 427-439, Jan. 2013
[ieee]

Graphical Models

Learning Gaussian Graphical Models via Multiplicative Weights
Anamay Chaturvedi and Jonathan Scarlett
International Conference on Artificial Intelligence and Statistics (AISTATS), 2020
[pmlr] [arxiv]
Learning Erdős-Rényi Random Graphs via Edge Detecting Queries
Zihan Li, Matthias Fresacher, and Jonathan Scarlett
Conference on Neural Information Processing Systems (NeurIPS), 2019
[neurips] [arxiv]
Lower Bounds on Active Learning for Graphical Model Selection
Jonathan Scarlett and Volkan Cevher
International Conference on Artificial Intelligence and Statistics (AISTATS), 2017
[pmlr] [arxiv]
On the Difficulty of Selecting Ising Models with Approximate Recovery
Jonathan Scarlett and Volkan Cevher
IEEE Transactions on Signal and Information Processing over Networks (Special Issue on Inference and Learning over Networks), Volume 2, Issue 4, pp. 625-638, July 2016
[ieee] [arxiv]

Miscellaneous

Optimal Rates of Teaching and Learning Under Uncertainty
Yan Hao Ling and Jonathan Scarlett
Accepted to IEEE Transactions on Information Theory, 2021
[arxiv]
A Characteristic Function Approach to Deep Implicit Generative Modeling
Abdul Fatir Ansari, Jonathan Scarlett, and Harold Soh
Conference on Computer Vision and Pattern Recognition (CVPR), 2020
[ieee] [arxiv]
Phase Transitions in the Pooled Data Problem
Jonathan Scarlett and Volkan Cevher
Conference on Neural Information Processing Systems (NeurIPS), 2017
[neurips] [arxiv]
Robust Submodular Maximization: A Non-Uniform Partitioning Approach
Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher
International Conference on Machine Learning (ICML), 2017
[pmlr] [arxiv]

Mismatched Decoding in Information Theory

Mismatched Multi-Letter Successive Decoding for the Multiple-Access Channel
Jonathan Scarlett, Alfonso Martinez, and Albert Guillén i Fàbregas
IEEE Transactions on Information Theory, Volume 64, Issue 4, pp. 2253-2266, April 2018
[ieee] [arxiv]
The Dispersion of Nearest-Neighbor Decoding for Additive Non-Gaussian Channels
Jonathan Scarlett, Vincent Y. F. Tan, and Giuseppe Durisi
IEEE Transactions on Information Theory, Volume 63, Issue 1, pp. 81-92, Jan. 2017
[ieee] [arxiv]
Multiuser Random Coding Techniques for Mismatched Decoding
Jonathan Scarlett, Alfonso Martinez, and Albert Guillén i Fàbregas
IEEE Transactions on Information Theory, Volume 62, Issue 7, pp. 3950-3970, July 2016
[ieee] [arxiv]
A Counter-Example to the Mismatched Decoding Converse for Binary-Input Discrete Memoryless Channels
Jonathan Scarlett, Anelia Somekh-Baruch. Alfonso Martinez, and Albert Guillén i Fàbregas
IEEE Transactions on Information Theory, Volume 61, Issue 10, pp. 5387-5395, Oct. 2015
[ieee] [arxiv]
Mismatched Decoding: Error Exponents, Second-Order Rates and Saddlepoint Approximations
Jonathan Scarlett, Alfonso Martinez, and Albert Guillén i Fàbregas
IEEE Transactions on Information Theory, Volume 60, Issue 5, pp. 2647-2666, May 2014
[ieee] [arxiv]

Refined Asymptotics in Information Theory

Generalized Random Gilbert-Varshamov Codes
Anelia Somekh-Baruch, Jonathan Scarlett, and Albert Guillén i Fàbregas
IEEE Transactions on Information Theory, Volume 65, Issue 6, pp. 3452-3469, June 2019
[ieee] [arxiv]
Second-Order Asymptotics for the Gaussian MAC with Degraded Message Sets
Jonathan Scarlett and Vincent Y. F. Tan
IEEE Transactions on Information Theory, Volume 61, Issue 12, pp. 6700-6718, Dec. 2015
[ieee] [arxiv]
On the Dispersions of the Gel'fand-Pinsker Channel and Dirty Paper Coding
Jonathan Scarlett
IEEE Transactions on Information Theory, Volume 61, Issue 9, pp. 4569-4586, Sept. 2015
[ieee] [arxiv]
Second-Order Rate Region of Constant-Composition Codes for the Multiple-Access Channel
Jonathan Scarlett, Alfonso Martinez, and Albert Guillén i Fàbregas
IEEE Transactions on Information Theory, Volume 61, Issue 1, pp. 157-172, Jan. 2015
[ieee] [arxiv]
Expurgated Random-Coding Ensembles: Exponents, Refinements and Connections
Jonathan Scarlett, Li Peng, Neri Merhav, Alfonso Martinez, and Albert Guillén i Fàbregas
IEEE Transactions on Information Theory, Volume 60, Issue 8, pp. 4449-4462, Aug. 2014
[ieee] [arxiv]