In the context of finite sums minimization, variance reduction techniques are widely used to improve the performance of state-of-the-art stochastic gradient methods. Their practical impact is clear, as well as their theoretical properties. Stochastic proximal point algorithms have been studied as an alternative to stochastic gradient algorithms since they are more stable with respect to the choice of the step size. However, their variance-reduced versions are not as well studied as the gradient ones. In this work, we propose the first unified study of variance reduction techniques for stochastic proximal point algorithms. We introduce a generic stochastic proximal-based algorithm that can be specified to give the proximal version of SVRG, SAGA, and some of their variants. For this algorithm, in the smooth setting, we provide several convergence rates for the iterates and the objective function values, which are faster than those of the vanilla stochastic proximal point algorithm. More specifically, for convex functions, we prove a sublinear convergence rate of O(1/k). In addition, under the Polyak-Łojasiewicz (PL) condition, we obtain linear convergence rates. Finally, our numerical experiments demonstrate the advantages of the proximal variance reduction methods over their gradient counterparts in terms of the stability with respect to the choice of the step size in most cases, especially for difficult problems.
@article{traore-arXiv230809310T,author={{Traor{\'e}}, Cheik and {Apidopoulos}, Vassilis and {Salzo}, Saverio and {Villa}, Silvia},title={Variance reduction techniques for stochastic proximal point algorithms},type={article},journal={Journal of Optimization Theory and Applications},keywords={Mathematics - Optimization and Control, Computer Science - Machine Learning},year={2024},month=aug,eid={arXiv:2308.09310},pages={arXiv:2308.09310},doi={10.1007/s10957-024-02502-6},archiveprefix={arXiv},eprint={2308.09310},primaryclass={math.OC},google_scholar_id={IjCSPb-OGe4C}}
2023
COAP
Convergence of an Asynchronous Block-Coordinate Forward-Backward Algorithm for Convex Composite Optimization
Cheik Traoré
, Saverio
Salzo, and Silvia
Villa
Computational Optimization and Applications, May 2023
In this paper, we study the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block-coordinates are updated asynchronously and randomly according to an arbitrary probability distribution. We prove that the iterates generated by the algorithm form a stochastic quasi-Fejér sequence and thus converge almost surely to a minimizer of the objective function. Moreover, we prove a general sublinear rate of convergence in expectation for the function values and a linear rate of convergence in expectation under an error bound condition of Tseng type. Under the same condition strong convergence of the iterates is provided as well as their linear convergence rate.
@article{traore-s10589-023-00489-w,author={Traor\'{e}, Cheik and Salzo, Saverio and Villa, Silvia},title={Convergence of an Asynchronous Block-Coordinate Forward-Backward Algorithm for Convex Composite Optimization},type={article},year={2023},volume={86},number={1},url={https://doi.org/10.1007/s10589-023-00489-w},doi={10.1007/s10589-023-00489-w},journal={Computational Optimization and Applications},month=may,pages={303–344},numpages={42},keywords={Convergence rates, Convex optimization, 90C25, Randomized block-coordinate descent, Forward-backward algorithm, Stochastic quasi-Fej\'{e}r sequences, 65K05, Asynchronous algorithms, 90C06, Error bounds, 49M27},google_scholar_id={UeHWp8X0CEIC}}
2021
ORL
Sequential convergence of AdaGrad algorithm for smooth convex optimization
We prove that the iterates produced by, either the scalar step size variant, or the coordinatewise variant of AdaGrad algorithm, are convergent sequences when applied to convex objective functions with Lipschitz gradient. The key insight is to remark that such AdaGrad sequences satisfy a variable metric quasi-Fejér monotonicity property, which allows to prove convergence.
@article{traore-j.orl.2021.04.011.,title={Sequential convergence of AdaGrad algorithm for smooth convex optimization},type={article},author={Traor{\'e}, Cheik and Pauwels, Edouard},url={https://doi.org/10.1016/j.orl.2021.04.011},journal={Operations Research Letters},publisher={Elsevier},volume={49},number={4},pages={452-458},year={2021},month=jul,doi={10.1016/j.orl.2021.04.011},google_scholar_id={u5HHmVD_uO8C}}
