在线稀疏线性回归最小最大遗憾首次下界及上界算法

发生了什么

据arXiv cs.LG论文《New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression》报道，研究关注在线稀疏线性回归（OSLR），其中任何算法在每个实例中仅被限制访问$d$个属性中的$b$个进行预测，并在预测后访问$b_0\geq 0$个额外属性。先前的工作侧重于在正则性假设下设计计算高效的算法，但未表征其信息论复杂度。本研究给出了OSLR最小最大遗憾的首次下界，并设计了在没有正则性假设下具有更好上界的算法。研究刻画了最小最大遗憾如何随问题依赖参数缩放，从而捕获OSLR的信息论复杂度。