论文标题
光滑且强烈凸优化的高阶甲骨文复杂性
High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
论文作者
论文摘要
在本说明中，我们考虑了通过调用$ k $ -th订单Oracle来优化高度光滑（Lipschitz $ k $ th订单衍生物）和强烈凸功能的复杂性，该订单返回了该功能的值和第一个$ k $衍射词，并在给定点的第一个$ k $衍射，以及维度不受限制的位置。扩展了Arjevani等人中引入的技术。 [2019]，我们证明，任何固定的$ k $最差的甲骨文复杂性，以优化函数到准确性$ε$的订单为$ \ left（\ frac {μ_k d^{k-1}}λ\ right）^{\ frac {2} {3k+1}}+\ log \ log \ log \ lod \ left（\ frac {1}ε\ right）$（在足够高的尺寸中，log log factor of log factor of $ε$ $ usus $ is $ iS $ ischit $ - $ usus $ iSchit $ ipschit os $ ulschit y lips $ - 到达最佳的距离，$λ$是强凸参数。
In this note, we consider the complexity of optimizing a highly smooth (Lipschitz $k$-th order derivative) and strongly convex function, via calls to a $k$-th order oracle which returns the value and first $k$ derivatives of the function at a given point, and where the dimension is unrestricted. Extending the techniques introduced in Arjevani et al. [2019], we prove that the worst-case oracle complexity for any fixed $k$ to optimize the function up to accuracy $ε$ is on the order of $\left(\frac{μ_k D^{k-1}}λ\right)^{\frac{2}{3k+1}}+\log\log\left(\frac{1}ε\right)$ (in sufficiently high dimension, and up to log factors independent of $ε$), where $μ_k$ is the Lipschitz constant of the $k$-th derivative, $D$ is the initial distance to the optimum, and $λ$ is the strong convexity parameter.
