The Convergence Analysis Of Stochastic Proximal Newton Method

The large-scale nonsmooth optimization problems often arise in machine learning and dataanalysis.In this paper,we consider the problem of minimizing the sum of two convex functions: one is the average of a large number of smooth component functions,and the other is a general convex function that admits a simple proximal mapping.The first-order algorithms for solving such problem can only converge linearly.In order to speed up the convergence,we can consider extending the Newton algorithm to solve such problems,such as the proximal Newton algorithm.Proximal Newton algorithm needs to calculate the Hessian of the objective functions when solving such problems.Therefore,when the number of components n is very large,it will lead to a large amount of calculations.In this paper,we propose a stochastic proximal Newton algorithm to solve large-scale composite convex optimization problems.The main idea of this algorithm is: first generate a set of samples using random sampling,then use the samples to construct the approximations of Hessian and gradient of the smooth part of the objective function,then combine the proximal Newton algorithm to generate the search direction,and finally complete the iterative process by line search.We first prove that the stochastic proximal Newton algorithm globally converges with high probability if the smooth part of the objective function is strongly convex.Furthermore,if the Hessian of the smooth part is Lipschitz continuous,the convergence rate of the stochastic proximate Newton algorithm only depends on the sample size.By choosing the sample sizes carefully,we propose two improved versions of the proposed algorithm,and prove that if the initial point satisfies certain conditions,both of these improved algorithms converge linearly to the optimal point with a high probability.If the sample sizes of the approximate Hessian are further increased,the algorithm converge R-superlinearly.