首次给出贪心算法在线性回归主动学习中的风险近似比，揭示其性能关键因子。
The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression
- 提出贪心算法的风险近似比，基于最大初始杠杆率
- 近似比与最大初始杠杆率成线性关系，理论紧致
- 适用于关注主动学习理论分析的研究者
主动学习的核心问题是：应选择哪些数据进行观测？最优实验设计中的贪心算法是常用启发式方法，等价于线性回归场景下的近视贝叶斯主动学习——用单步最优选择替代长期规划。本文首次证明了该贪心算法风险的近似比，且该界在绝对常数意义下紧致。近似比与一个新识别的关键量——最大初始杠杆率（MILS）呈线性关系。最后，通过简单的数值模拟验证了结论。
原文摘要 · Abstract (English)
Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to myopic Bayesian active learning for linear regression, the common framework where long-term planning is replaced with the one-step optimal choice. In this work, we prove a first-of-its-kind approximation ratio for the greedy algorithm's risk that is tight up to an absolute constant. The approximation ratio is linear in the maximum initial leverage score (MILS), a newly identified quantity fundamental to the greedy algorithm's performance. Finally, we illustrate the results with simple numerical simulations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。