In this paper, we study the lower complexity bounds for finite-sum
optimization problems, where the objective is the average of $n$ individual
component functions. We consider Proximal Incremental First-order (PIFO)
algorithms which have access to the gradient and proximal oracles for each
component function. To incorporate loopless methods, we also allow PIFO
algorithms to obtain the full gradient infrequently. We develop a novel
approach to constructing the hard instances, which partitions the tridiagonal
matrix of classical examples into $n$ groups. This construction is friendly to
the analysis of PIFO algorithms. Based on this construction, we establish the
lower complexity bounds for finite-sum minimax optimization problems when the
objective is convex-concave or nonconvex-strongly-concave and the class of
component functions is $L$-average smooth. Most of these bounds are nearly
matched by existing upper bounds up to log factors. We can also derive similar
lower bounds for finite-sum minimization problems as previous work under both
smoothness and average smoothness assumptions. Our lower bounds imply that
proximal oracles for smooth functions are not much more powerful than gradient
oracles.

本文研究了有限和优化问题的下限复杂度界限，并基于分组的新方法构造了硬实例，从而建立了有限和最大最小优化问题的下限复杂度界限。

有限和优化问题的下限复杂度：结果与构造

Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results  and Construction

We propose an algorithm of generating hard instances for the Satisfying
Assignment Search Problem (in short, SAT). The algorithm transforms instances
of the integer factorization problem into SAT instances efficiently by using
the Chinese Remainder Theorem. For example, it is possible to construct SAT
instances with about 5,600 variables that is as hard as factorizing 100 bit
integers.

本文提出了一种使用中国剩余定理将整数因子分解问题转化为 SAT 问题的算法，能够生成与 100 位整数因子分解一样难度的约 5600 变量的 SAT 实例。