The contribution of this paper includes two aspects. First, we study the lower bound complexity for the minimax optimization problem whose objective function is the average of $n$ individual smooth component functions. We consider Proximal Incremental First-order (PIFO) algorithms which have access to gradient and proximal oracle for each individual component. We develop a novel approach for constructing adversarial problems, which partitions the tridiagonal matrix of classical examples into $n$ groups. This construction is friendly to the analysis of incremental gradient and proximal oracle. With this approach, we demonstrate the lower bounds of first-order algorithms for finding an $\varepsilon$-suboptimal point and an $\varepsilon$-stationary point in different settings. Second, we also derive the lower bounds of minimization optimization with PIFO algorithms from our approach, which can cover the results in \citep{woodworth2016tight} and improve the results in \citep{zhou2019lower}.
翻译:本文的贡献包括两个方面。 首先, 我们研究微型最大优化问题的较低约束复杂性, 其客观功能是平均美元, 单个光滑元件功能。 我们考虑每个元件都可访问梯度和准角的精度一级算法( PIFO ) 。 我们开发了一种新颖的方法来构建对抗性问题, 将经典示例的三对角矩阵分割成 $美元 组 。 这个构造有利于分析递增梯度和准极分。 通过这个方法, 我们展示了在不同的环境下找到 $\ varepsilon 的次最佳点和 $\ varepsilon$ 固定点的第一等算法( PIFO 算法) 的较低界限。 其次, 我们还从我们的方法中得出了与 PIFO 算法的最小度优化的较低界限, 它可以覆盖 citep{woodworth2016tight}, 并改进 \ citep{x2019 lower} 的结果 。