论文标题
可分离的最小值和有限总和通过原始偶二的外部方法优化的较高速率
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods
论文作者
论文摘要
我们设计了多种基本优化问题类别的加速算法，并提高了利率。我们的算法都建立在与[CST21]最近提出的相对Lipschitzness分析原始双重外部方法有关的技术基础上。 （1）可分离的最小值优化。我们研究可分离的最小值优化问题$ \ min_x \ max_y f（x）-g（y） + h（x，y）$，其中$ f $和$ g $具有光滑且强的convexity参数$（l^x，μ^x）$，$（l^y，μ^y）$ h $和$ h $ convex -conconconconconcove（ λ^{xy}，λ^{yy}）$ - 块操作器norm Bounded Hessian。我们提供具有梯度查询复杂性$ \ tilde {o} \ left（\ sqrt {\ frac {\ frac {l^{x}} {μ^{x}}}} + \ sqrt { \ frac {λ^{xx}} {μ^{x}} + \ frac {λ^{xy}} {\ sqrt {\ sqrt {μ^{x}μ^{y}}}}}}}}}}}}}} + \ frac {yy}} =值得注意的是，对于双线性耦合（例如\ Quadratics）的凸 - 孔concave minimax问题，其中$λ^{xx} =λ^{yy} = 0 $，我们的费率与[zhz19]的下限相匹配。 （2）有限和优化。 We study finite sum optimization problems $\min_x \frac{1}{n}\sum_{i\in[n]} f_i(x)$, where each $f_i$ is $L_i$-smooth and the overall problem is $μ$-strongly convex.我们提供具有梯度查询复杂性$ \ tilde {o} \ left（n + \ sum_ {i \ in [n]} \ sqrt {\ frac {\ frac {l_i} {nμ} {nμ}} \ right）$的算法。值得注意的是，当平滑度界限$ \ {l_i \} _ {i \ in [n]} $是不均匀的时，我们的费率会在加速SVRG [LMH15，FGKS15]和Katyusha [alll17]中提高，最多可达$ \ \ sqrt。 （3）Minimax有限总和。我们将最小值和有限和优化的算法概括为以加速速率解决自然的有限总和优化问题，将两者封装在上述结果中，最高为对数因子。
We design accelerated algorithms with improved rates for several fundamental classes of optimization problems. Our algorithms all build upon techniques related to the analysis of primal-dual extragradient methods via relative Lipschitzness proposed recently by [CST21]. (1) Separable minimax optimization. We study separable minimax optimization problems $\min_x \max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(L^x, μ^x)$, $(L^y, μ^y)$, and $h$ is convex-concave with a $(Λ^{xx}, Λ^{xy}, Λ^{yy})$-blockwise operator norm bounded Hessian. We provide an algorithm with gradient query complexity $\tilde{O}\left(\sqrt{\frac{L^{x}}{μ^{x}}} + \sqrt{\frac{L^{y}}{μ^{y}}} + \frac{Λ^{xx}}{μ^{x}} + \frac{Λ^{xy}}{\sqrt{μ^{x}μ^{y}}} + \frac{Λ^{yy}}{μ^{y}}\right)$. Notably, for convex-concave minimax problems with bilinear coupling (e.g.\ quadratics), where $Λ^{xx} = Λ^{yy} = 0$, our rate matches a lower bound of [ZHZ19]. (2) Finite sum optimization. We study finite sum optimization problems $\min_x \frac{1}{n}\sum_{i\in[n]} f_i(x)$, where each $f_i$ is $L_i$-smooth and the overall problem is $μ$-strongly convex. We provide an algorithm with gradient query complexity $\tilde{O}\left(n + \sum_{i\in[n]} \sqrt{\frac{L_i}{nμ}} \right)$. Notably, when the smoothness bounds $\{L_i\}_{i\in[n]}$ are non-uniform, our rate improves upon accelerated SVRG [LMH15, FGKS15] and Katyusha [All17] by up to a $\sqrt{n}$ factor. (3) Minimax finite sums. We generalize our algorithms for minimax and finite sum optimization to solve a natural family of minimax finite sum optimization problems at an accelerated rate, encapsulating both above results up to a logarithmic factor.
