Timezone: »
In this paper, we study the {\em pooled data} problem of identifying the labels associated with a large collection of items, based on a sequence of pooled tests revealing the counts of each label within the pool. In the noiseless setting, we identify an exact asymptotic threshold on the required number of tests with optimal decoding, and prove a {\em phase transition} between complete success and complete failure. In addition, we present a novel {\em noisy} variation of the problem, and provide an information-theoretic framework for characterizing the required number of tests for general random noise models. Our results reveal that noise can make the problem considerably more difficult, with strict increases in the scaling laws even at low noise levels. Finally, we demonstrate similar behavior in an {\em approximate recovery} setting, where a given number of errors is allowed in the decoded labels.
Author Information
Jonathan Scarlett (EPFL)
Volkan Cevher (EPFL)
More from the Same Authors
-
2020 Poster: On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems »
Panayotis Mertikopoulos · Nadav Hallak · Ali Kavis · Volkan Cevher -
2020 Poster: Robust Reinforcement Learning via Adversarial training with Langevin Dynamics »
Parameswaran Kamalaruban · Yu-Ting Huang · Ya-Ping Hsieh · Paul Rolland · Cheng Shi · Volkan Cevher -
2019 Poster: An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints »
Mehmet Fatih Sahin · Armin eftekhari · Ahmet Alacaoglu · Fabian Latorre · Volkan Cevher -
2019 Poster: Stochastic Frank-Wolfe for Composite Convex Minimization »
Francesco Locatello · Alp Yurtsever · Olivier Fercoq · Volkan Cevher -
2019 Poster: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2019 Poster: Fast and Provable ADMM for Learning with Generative Priors »
Fabian Latorre · Armin eftekhari · Volkan Cevher -
2019 Spotlight: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2019 Spotlight: Fast and Provable ADMM for Learning with Generative Priors »
Fabian Latorre · Armin eftekhari · Volkan Cevher -
2018 Poster: Online Adaptive Methods, Universality and Acceleration »
Kfir Y. Levy · Alp Yurtsever · Volkan Cevher -
2018 Poster: Mirrored Langevin Dynamics »
Ya-Ping Hsieh · Ali Kavis · Paul Rolland · Volkan Cevher -
2018 Spotlight: Mirrored Langevin Dynamics »
Ya-Ping Hsieh · Ali Kavis · Paul Rolland · Volkan Cevher -
2018 Poster: Adversarially Robust Optimization with Gaussian Processes »
Ilija Bogunovic · Jonathan Scarlett · Stefanie Jegelka · Volkan Cevher -
2018 Spotlight: Adversarially Robust Optimization with Gaussian Processes »
Ilija Bogunovic · Jonathan Scarlett · Stefanie Jegelka · Volkan Cevher -
2017 Poster: Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach »
Slobodan Mitrovic · Ilija Bogunovic · Ashkan Norouzi-Fard · Jakub M Tarnawski · Volkan Cevher -
2017 Poster: Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data »
Joel A Tropp · Alp Yurtsever · Madeleine Udell · Volkan Cevher -
2017 Poster: Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization »
Ahmet Alacaoglu · Quoc Tran Dinh · Olivier Fercoq · Volkan Cevher -
2016 Poster: An Efficient Streaming Algorithm for the Submodular Cover Problem »
Ashkan Norouzi-Fard · Abbas Bazzi · Ilija Bogunovic · Marwa El Halabi · Ya-Ping Hsieh · Volkan Cevher -
2016 Poster: Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation »
Ilija Bogunovic · Jonathan Scarlett · Andreas Krause · Volkan Cevher -
2016 Poster: Stochastic Three-Composite Convex Minimization »
Alp Yurtsever · Bang Cong Vu · Volkan Cevher -
2015 Poster: Preconditioned Spectral Descent for Deep Learning »
David Carlson · Edo Collins · Ya-Ping Hsieh · Lawrence Carin · Volkan Cevher -
2015 Poster: A Universal Primal-Dual Convex Optimization Framework »
Alp Yurtsever · Quoc Tran Dinh · Volkan Cevher -
2014 Workshop: Discrete Optimization in Machine Learning »
Jeffrey A Bilmes · Andreas Krause · Stefanie Jegelka · S Thomas McCormick · Sebastian Nowozin · Yaron Singer · Dhruv Batra · Volkan Cevher -
2014 Poster: Constrained convex minimization via model-based excessive gap »
Quoc Tran-Dinh · Volkan Cevher -
2014 Poster: Time--Data Tradeoffs by Aggressive Smoothing »
John J Bruer · Joel A Tropp · Volkan Cevher · Stephen Becker -
2013 Poster: High-Dimensional Gaussian Process Bandits »
Josip Djolonga · Andreas Krause · Volkan Cevher -
2012 Poster: Active Learning of Multi-Index Function Models »
Hemant Tyagi · Volkan Cevher -
2009 Workshop: Manifolds, sparsity, and structured models: When can low-dimensional geometry really help? »
Richard Baraniuk · Volkan Cevher · Mark A Davenport · Piotr Indyk · Bruno Olshausen · Michael B Wakin -
2009 Poster: Learning with Compressible Priors »
Volkan Cevher -
2008 Poster: Sparse Signal Recovery Using Markov Random Fields »
Volkan Cevher · Marco F Duarte · Chinmay Hegde · Richard Baraniuk -
2008 Spotlight: Sparse Signal Recovery Using Markov Random Fields »
Volkan Cevher · Marco F Duarte · Chinmay Hegde · Richard Baraniuk