标签
该论文刻画了在线凸优化中仅能访问线性优化预言机（oracle）时的紧确遗憾界，给出了与维度无关的极小极大期望遗憾 Θ(GD·max{√T, T/(1+min{Q,BT})^{1/4}})，并同时证明了适用于任意随机化学习者的下界与匹配的算法上界。
本文证明了在高阶光滑非凸优化中寻找ε-稳定点的无维数尖锐一阶下界，解决了Hessian-Lipschitz和三阶光滑情况下的公开问题。