论文标题
一种最佳算法，用于强凸出最小值优化
An Optimal Algorithm for Strongly Convex Min-min Optimization
论文作者
论文摘要
在本文中，我们研究了平稳的强烈凸出最小化问题$ \ min_ {x} \ min_y f（x，y）$。现有的最佳一阶方法需要$ \ MATHCAL {O}（\ sqrt {\ max \ {κ_x，κ_y\}} \ log 1/ε）$ \ nabla_x f（x，x，y）$ and $ \ nabla_y f（ynabla_y f {$ n $ and $ n $ and $ n $ and $κXy）的计算计算。可变块$ x $和$ y $。我们提出了一种新算法，该算法仅需要$ \ nabla_x f（x，y）$ and $ \ nabla_x f（x，y）$和$ \ mathcal {o}（O}（\ sqrt {\ sqrt {$ bog y $ bog y $ 1/〜1/ ^ bec）， f（x，y）$。在某些应用程序中，$κ_x\ggκ_y$，计算$ \ nabla_y f（x，y）$比计算$ \ nabla_x f（x，y）$便宜得多。在这种情况下，我们的算法大大优于现有的最新方法。
In this paper we study the smooth strongly convex minimization problem $\min_{x}\min_y f(x,y)$. The existing optimal first-order methods require $\mathcal{O}(\sqrt{\max\{κ_x,κ_y\}} \log 1/ε)$ of computations of both $\nabla_x f(x,y)$ and $\nabla_y f(x,y)$, where $κ_x$ and $κ_y$ are condition numbers with respect to variable blocks $x$ and $y$. We propose a new algorithm that only requires $\mathcal{O}(\sqrt{κ_x} \log 1/ε)$ of computations of $\nabla_x f(x,y)$ and $\mathcal{O}(\sqrt{κ_y} \log 1/ε)$ computations of $\nabla_y f(x,y)$. In some applications $κ_x \gg κ_y$, and computation of $\nabla_y f(x,y)$ is significantly cheaper than computation of $\nabla_x f(x,y)$. In this case, our algorithm substantially outperforms the existing state-of-the-art methods.
