arXiv：cs.LG· Xiaxin Li, Arya Mazumdar·· 5 小时前AI 评分29
稀疏线性分类器混合模型的支持恢复：更少测量与亚线性解码
Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements
AI 导读
针对线性分类器混合模型的支持恢复问题，研究者提出自适应与非自适应方案，在减少测量次数的同时将解码复杂度从超二次降至与环境维度呈亚线性。自适应方案相比已有方法大幅减少测量量，非自适应方案也在改进测量上界的同时保持高效解码，整体在样本复杂度与解码时间之间取得更优权衡。
正文
Abstract:The support recovery problem in mixture of linear classifiers aims to identify the features relevant to the underlying decision rules when data is generated by a mixture of several linear decision rules. In particular, the goal is to recover the support (nonzero coordinates) of $l$ unknown $k$-sparse vectors from sign measurements. Each measurement is generated by selecting one of the $l$ vectors uniformly at random, and returning the sign of its inner product with a chosen measurement vector.
In this paper, we propose adaptive and non-adaptive schemes that significantly improve upon prior results by simultaneously reducing the number of measurements and achieving sublinear decoding time. In particular, our adaptive constructions substantially reduce measurements compared to existing approaches, while also lowering decoding complexity from super-quadratic to sublinear in the ambient dimension. We further provide a non-adaptive scheme that improves previous measurement bounds while maintaining efficient decoding.
Overall, our approach yields a more efficient trade-off between sample complexity and decoding time for support recovery in mixture models compared to previously known methods.
| Subjects: | Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Information Theory (cs.IT) |
| Cite as: | arXiv:2609.32176 [cs.LG] |
| (or arXiv:2609.32176v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2609.32176 arXiv-issued DOI via DataCite |
Submission history
From: Xiaxin Li [view email]
[v1]
Sat, 26 Sep 2026 02:55:10 UTC (63 KB)
[v2]
Fri, 2 Oct 2026 05:50:57 UTC (65 KB)
来源：arXiv：cs.LG · arxiv.org