Minimizing finite sums of functions is a central problem in optimization, arising in numerous practical ap-
plications. Such problems are commonly addressed using first-order optimization methods. However, these
procedures cannot be used in settings where gradient information is unavailable. Finite-difference methods
provide an alternative by approximating gradients through function evaluations along a set of directions.
For finite-sum minimization problems, it was shown that incorporating variance-reduction techniques into
finite-difference methods can improve convergence rates. Additionally, recent studies showed that imposing
structure on the directions (e.g., orthogonality) enhances performance. However, the impact of structured
directions on variance-reduced finite-difference methods remains unexplored. In this work, we close this gap
by proposing a structured variance-reduced finite-difference algorithm for non-smooth finite-sum minimiza-
tion. We analyze the proposed method, establishing convergence rates for non-convex functions and those
satisfying the Polyak-Łojasiewicz condition. Our results show that our algorithm achieves state-of-the-art con-
vergence rates while incurring lower per-iteration costs. Finally, numerical experiments highlight the strong
practical performance of our method.
@article{rando2025structured,title={A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm},author={Rando, Marco and Traor{\'e}, Cheik and Molinari, Cesare and Rosasco, Lorenzo and Villa, Silvia},journal={arXiv preprint arXiv:2506.23758},year={2025},}
Peer-reviewed papers:
2024
JOTA
Variance reduction techniques for stochastic proximal point algorithms
Cheik Traoré
, Vassilis
Apidopoulos, Saverio
Salzo, and Silvia
Villa
Journal of Optimization Theory and Applications, Aug 2024
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},}
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},}
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},}
