Near optimal efficient decoding from pooled data
Jul 2, 2022
Speakers
Max Hahn-Klimroth
Speaker · 0 followers
Noela Müller
Speaker · 0 followers
About
Consider n items, each of which is characterised by one of d+1 possible features in {0, ..., d}. We study the inference task of learning these types by queries on subsets, or pools, of the items that only reveal a form of coarsened information on the features - in our case, the sum of all the features in the pool. This is a realistic scenario in situations where one has memory or technical constraints in the data collection process, or where the data is subject to anonymisation. Related prominent problems are the quantitative group testing problem, of which it is a generalisation, as well as the compressed sensing problem, of which it is a special case. In the present article, we are interested in the minimum number of queries needed to efficiently infer the labels, if one of the features, say 0, is dominant in the sense that the number k of non-zero features among the items is much smaller than n. It is known that in this case, all features can be recovered in exponential time by using no more than O(k) queries. However, so far, all efficient inference algorithms required at least Ω(kln n) queries, and it was unknown whether this gap is artificial or of a fundamental nature. Here we show that indeed, the previous gap between the information-theoretic and computational bounds is not inherent to the problem by providing an efficient algorithm that succeeds with high probability and employs no more than O(k) measurements. This also solves a long standing open question for the quantitative group testing problem.Consider n items, each of which is characterised by one of d+1 possible features in {0, ..., d}. We study the inference task of learning these types by queries on subsets, or pools, of the items that only reveal a form of coarsened information on the features - in our case, the sum of all the features in the pool. This is a realistic scenario in situations where one has memory or technical constraints in the data collection process, or where the data is subject to anonymisation. Related prominen…
About COLT
The conference is held annually since 1988 and has become the leading conference on Learning theory by maintaining a highly selective process for submissions. It is committed in high-quality articles in all theoretical aspects of machine learning and related topics.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Bessel Smoothing and Multi-Distribution Property Estimation
Watch later
Ping Li, …
Toward Instance-Optimal State Certification With Incoherent Measurements
Watch later
Sitan Chen, …
Extrapolating the profile of a finite population
Watch later
Hierarchical Clustering: A 0.585 Revenue Approximation
Watch later
Noise-tolerant, Reliable Active Classification with Comparison Queries
Watch later
Daniel Kane, …