General convergence analysis of stochastic first order methods for\n composite optimization

In this paper we consider stochastic composite convex optimization problems\nwith the objective function satisfying a stochastic bounded gradient condition,\nwith or without a quadratic functional growth property. These models include\nthe most well-known classes of objective functions analyzed in the literature:\nnon-smooth Lipschitz functions and composition of a (potentially) non-smooth\nfunction and a smooth function, with or without strong convexity. Based on the\nflexibility offered by our optimization model we consider several variants of\nstochastic first order methods, such as the stochastic proximal gradient and\nthe stochastic proximal point algorithms. Usually, the convergence theory for\nthese methods has been derived for simple stochastic optimization models\nsatisfying restrictive assumptions, the rates are in general sublinear and hold\nonly for specific decreasing stepsizes. Hence, we analyze the convergence rates\nof stochastic first order methods with constant or variable stepsize under\ngeneral assumptions covering a large class of objective functions. For constant\nstepsize we show that these methods can achieve linear convergence rate up to a\nconstant proportional to the stepsize and under some strong stochastic bounded\ngradient condition even pure linear convergence. Moreover, when a variable\nstepsize is chosen we derive sublinear convergence rates for these stochastic\nfirst order methods. Finally, the stochastic gradient mapping and the Moreau\nsmoothing mapping introduced in the present paper lead to simple and intuitive\nproofs.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC