随机化线性最小化预言机方法在强凸集上的下界

针对随机化一阶线性最小化预言机（LMO）方法在强凸集上的优化问题，此前两项工作仅分别覆盖标准 Frank-Wolfe 算法和确定性方法，未给出无限制随机化方法的下界。该研究证明了 $\Omega(L\operatorname{diam}(S)^2/T^2)$ 的分布下界，填补了这一空白，并进一步表明相同误差阈值以至少 3/4 的概率成立，同时给出停时尾部界。