## Samenvatting

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 features, in the setting where the feature vector is chosen uniformly while fixing the frequencies, and one of the features, say 0, is dominant in the sense that the number k = n^{θ}, θ ∈ (0, 1), 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 using no more than O(k) queries. However, so far, all efficient inference algorithms required at least Ω(k ln 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 prominent open question for the quantitative group testing problem.

Originele taal-2 | Engels |
---|---|

Titel | 35th Conference on Learning Theory, COLT 2022 |

Redacteuren | Po-Ling Loh, Maxim Raginsky |

Pagina's | 3395-3409 |

Aantal pagina's | 15 |

Status | Gepubliceerd - 2022 |

Evenement | 35th Conference on Learning Theory, COLT 2022 - London, Verenigd Koninkrijk Duur: 2 jul. 2022 → 5 jul. 2022 |

### Publicatie series

Naam | Proceedings of Machine Learning Research |
---|---|

Volume | 178 |

ISSN van elektronische versie | 2640-3498 |

### Congres

Congres | 35th Conference on Learning Theory, COLT 2022 |
---|---|

Land/Regio | Verenigd Koninkrijk |

Stad | London |

Periode | 2/07/22 → 5/07/22 |

### Bibliografische nota

Publisher Copyright:© 2022 M. Hahn-Klimroth & N. Müller.

### Financiering

Max Hahn-Klimroth is supported by DFG CO 646/5. Noela Müller has been supported by ERC-Grant 772606-PTRCSP. We thank Dominik Kaaser and Philipp Loick for fruitful discussions on the quantitative group testing problem. We furthermore thank an anonymous referee for his proposal of an elegant simplification of the starting phase of our algorithm.

Financiers | Financiernummer |
---|---|

International Advisory Board of ERC Advanced Grant Project THUNDERR | 772606-PTRCSP |

Deutsche Forschungsgemeinschaft | CO 646/5 |