Research On Algorithms And Convergence Of Proximal Incremental Aggregated Methods

In recent years,with the rise of big data,the problems of large-scale regularized empirical risk minimization have appeared in various fields.As a valid routine to han-dle these problems,the Proximal Incremental Aggregated Gradient method(PIAG)has received extensive attention from researchers.PIAG can be implemented by various man-ners,including cyclic orders,stochastic orders,and centralized master-slave distributed computing systems.Therefore PIAG has a wide application prospect.This paper system-atically constructs the research framework that PIAG will involve,including the Bregman distance,accelerated techniques,non-convex analysis,dual algorithms,primal-dual algo-rithms and monotone operator inclusion problems.We have studied several fundamental aspects to explore PIAG,proposed several novel incremental aggregated schemes,and ob-tained several improved theoretical results.The main content of the thesis can be divided into the following five aspects:First,we introduce the Proximal-Like Incremental Aggregated Gradient methods(PLIAG)with Bregman distance replacing Euclidean distance,and present its conver-gence theory.PLIAG is the generalization of PIAG,making PIAG more widely ap-plicable.In the convergence analysis of PLIAG,the linear convergence under quadratic growth and the sublinear convergence under general conditions are obtained.The sublin-ear convergence of such algorithms is presented for the first time,which is also the best result obtained so far.Secondly,we apply PIAG to a class of non-convex problems,expand the use range of PIAG method,and give the convergence analysis.We show that the iterates generated by PIAG have global convergence for non-convex problems.Convergence to a stable set of points and linear convergence under certain conditions are then proved.Thirdly,we extend the Double Incremental Aggregated Gradient methods(DIAG)to the minimization problems with regularization and obtains the PDIAG scheme.Through our improvement in the implementation of DIAG,the storage requirements are greatly reduced in the calculation.The linear convergence of PDIAG under strong convex condi-tions and the sublinear convergence under general conditions are also obtained.The for-mer restores the standard results in the Proximal Gradient method PG),the latter restoring the standard result of PG at a specific stepsize.Since DIAG is a special case of PDIAG,the sublinear convergence given in the thesis also provides a novel result for DIAG.Next,several new algorithms are proposed based on the dual problem,and the ap-plication range of PIAG is further extended.PIAG is employed in a class of separable strongly convex minimization problems.The dual representation and the primal represen-tation of the algorithms are obtained,respectively.The dual PIAG(D-PIAG)is combined with other fundamental work in this thesis to obtain the convergence of D-PIAG.At the same time,based on the research of the PDIAG in this thesis,dual PDIAG(D-PDIAG)is proposed.The corresponding convergence results are also given.Besides,if the proxim-ity operator corresponding to the regularization term is coupled with a linear operator,the closed-form of the proximity operator is usually unavailable,which makes the computa-tion complicated.We decouple the problem to the saddle point problem,and a variety of primal-dual PIAG schemes and corresponding convergence analysis are obtained.Finally,we abstract the PIAG algorithm in minimization problems and obtain the Forward-Backward Incremental Aggregated Splitting methods(F-BIAS)for solving a class of maximal monotone operator inclusion problems in the Hilbert spaces.Firstly,based on the classical convergence analysis of IAG,linear convergence in some special cases is obtained.The general case is explored and the convergence is also obtained.Then,based on the study of PDIAG,a Forward-Backward Double Incremental Aggre-gated Splitting scheme(F-BDIAS)is proposed,the convergence of which almost restores the standard results in the forward-backward splitting algorithm.