{"id":"arxiv/2603.21492","url":"https://arxiv.org/abs/2603.21492","tags":["cs.LG","math.OC"],"score":0,"title":"Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection","domain":"cs.LG","source":"arxiv","authors":["Qixin Zhang","Wei Huang","Yan Sun","Yao Shu","Yi Yu","Dacheng Tao"],"reviews":0,"subject":"cs.LG","summary":"Identifying the most representative subset for a close-to-submodular objective while satisfying the predefined partition constraint is a fundamental task with numerous applications in machine learning. However, the existing distorted local-search methods are often hindered by their prohibitive query complexities and the rigid requirement for prior knowledge of difficult-to-obtain structural parameters. To overcome these limitations, we introduce a novel algorithm titled Multinoulli-SCG, which not only is parameter-free, but also can achieve the same approximation guarantees as the distorted…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-23","reactions":{}}