An Optimal Algorithm for Strongly Convex Min-min Optimization
This work addresses optimization efficiency for researchers and practitioners in machine learning and related fields, offering an incremental improvement over state-of-the-art methods by reducing computational costs in specific scenarios.
The paper tackles the problem of smooth strongly convex min-min optimization by proposing a new algorithm that reduces computational complexity, requiring O(√κ_x log 1/ε) computations for ∇_x f(x,y) and O(√κ_y log 1/ε) for ∇_y f(x,y), compared to existing methods that need O(√max{κ_x, κ_y} log 1/ε) for both, leading to substantial performance gains when κ_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.