Optimization Algorithm And Complexity Analysis For Nonconvex Minimax Problems

The nonconvex minimax problem is an important research frontier and hot spot in the cross-fields of optimization,machine learning,signal processing,etc.in the recent years.Due to its own special structure,this type of problem is usually a nonconvex and non-smooth optimization problem,it's also a NP-hard problem.Many researches at this stage are aimed at the minimax problem in the nonconvex-concave case.There are two kinds of algorithms for solving nonconvex-concave minimax optimization problems,namely,the multi-loop algorithms and the single loop algorithms.In general,the iteration complexity of the multi loop algorithm is better than that of the single loop algorithm,but it has more parameters and is more complicated to implement.The best iteration complexity of the current first order multi-loop algorithms is O(?-2.5),there are few research on single loop algorithms.In this thesis,we propose a single-loop alternating gradient projection(AGP)algorithm,which can be used to solve the minimax problems in the two cases of nonconvexconcave and convex-nonconcave situations.AGP employs simple gradient projection steps for updating the x and y alternatively at each iteration.We show that it can find an ?stationary point of the objective function in O(?-4)iterations under nonconvex-concave setting,this is the best iteration complexity of the first order single loop algorithm for nonconvex-concave minimax problems.For the convex-nonconcave minimax problem,given the outer variable x,it is NP-hard to solve the inner subproblem,many existing multi-loop algorithms need to solve the approximate solution of(?)f(x,y)subproblem.Therefore,they cannot be directly used to solve the approximate solution of inner layer subproblem in the convex-nonconcave case.while we can still get the first order ?-stationary point of f(x,y)with the iteration complexity of O(?-4)by using AGP algorithm.To the best of our knowledge,this is the first algorithm with guaranteed complexity for solving convex-nonconcave minimax problems.In addition,the alternating gradient projection algorithm can also be used to solve block non-smooth minimax optimization problems,which are very common in distributed training.We propose alternating proximal gradient algorithm,and show that it can find an?-stationary point of the objective function in O(?-4)iterations under nonconvex-concave and convex-nonconcave setting.It is also the first algorithm with guaranteed complexity for solving this nonsmooth nonconvex-concave and convex-nonconcave minimax problems with block structure.This thesis is organized as follows.The first chapter is the introduction.It mainly introduces the background and significance of the nonconvex minimax problem,as well as the latest researches in optimization algorithms and complexity analysis for nonconvex minimax problems at home and abroad.In the second chapter,we propose a single-loop alternating gradient projection algorithm,it is proved that the iteration complexity of the algorithm is O(?-4)under nonconvexconcave setting,which is the best result among the existing first-order single loop algorithms.We show that it can find an ?-stationary point of the objective function in O(?-4 iterations under convex-nonconcave setting.To the best of our knowledge,this is the first time that a first order single loop algorithm is developed for solving convex-nonconcave minimax problems.In the third chapter,we propose alternating proximal gradient algorithm to solve nonsmooth minimax problems with block structure,we also analyze the iteration complexity of nonconvex-concave and convex-nonconcave minimax problems,the algorithm is currently the first one to solve nonsmooth nonconvex-concave and convex-nonconcave minimax problems with block structure in the first order algorithms,which is guaranteed by complexity.In the fourth chapter,the full text is summarized and the unresolved problems are prospected.