arXiv：cs.AI· Shizhan Cai, Qixin Zhang, Siyuan Ma, Siyuan Liang, Yongcheng Jing, Dacheng Tao·· 17 小时前
ReSGD：基于可学习类别先验的多源双层数据选择方法
Probabilistic Multi-Source Data Selection via Learnable Categorical Priors: Variance Reduction and Guaranteed Derandomization
AI 导读
针对多源双层数据选择问题，研究者提出一种新的概率松弛方法，引入多个可学习类别先验来参数化仅在可行数据子集上支撑的概率分布，从而自然获得无损舍入方案。该方法给出有效的两点梯度估计器，可同时避免现有 0-1 松弛所需的逆 Hessian 计算和先验概率松弛中的无界分数项，并设计了可约简表示以减少梯度计算所需的下层重训练次数。
正文
Abstract:Bilevel data selection is a fundamental task with numerous applications in machine learning and statistics. A common strategy for tackling this problem is to relax the original bilevel combinatorial optimization into a continuous one. However, existing methods, including 0-1 relaxation and probabilistic relaxation, still suffer from several limitations, such as unstable gradient estimation and infeasible rounding. To address these issues, this paper proposes a new probabilistic relaxation for the multi-source bilevel data selection problem. Our key idea is to introduce multiple learnable categorical priors to parameterize a probability distribution supported only on feasible data subsets, thus naturally yielding a lossless rounding scheme. We further show that our proposed relaxation admits an effective two-point gradient estimator, which can simultaneously avoid the inverse-Hessian computation required by existing 0-1 relaxation and the unbounded score term appearing in prior probabilistic relaxation. Furthermore, we develop a reducible representation of this estimator, which substantially reduces the number of lower-level retrainings required for gradient computation. Built upon this reducible two-point estimator, we then design a novel stochastic gradient algorithm, termed ReSGD, for multi-source bilevel data selection problem, and establish a rigorous approximation guarantee for the subset returned by ReSGD under weak submodularity. Finally, extensive experiments are conducted to validate the effectiveness of our proposed ReSGD.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.14942 [cs.LG] |
| (or arXiv:2610.14942v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.14942 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Shizhan Cai [view email]
[v1]
Sat, 10 Oct 2026 14:14:34 UTC (214 KB)
来源：arXiv：cs.AI · arxiv.org