2021/03/29 by Huang, Kevin, Zhang, Shuzhong
#65K15 #90C25 #90C33 #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2103.15270
In this paper, we propose a unifying framework incorporating several momentum-related search directions for solving strongly monotone variational inequalities. The specific combinations of the search directions in the framework are made to guarantee the optimal iteration complexity bound of O(κln(1/ε)) to reach an ε-solution, where κ is the condition number. This framework provides the flexibility for algorithm designers to train -- among different parameter combinations -- the one that best suits the structure of the problem class at hand. The proposed framework includes the following iterative points and directions as its constituents: the extra-gradient, the optimistic gradient descent ascent (OGDA) direction (aka "optimism"), the "heavy-ball" direction, and Nesterov's extrapolation points. As a result, all the afore-mentioned methods become the special cases under the general scheme of extra points. We also specialize this approach to strongly convex minimization, and show that a similar extra-point approach achieves the optimal iteration complexity bound of O(√κln(1/ε)) for this class of problems.