Definable parametric optimization problems with possibly nonsmooth objectives, inequality constraints, and non-unique primal and dual solutions admit an adjoint state formula under a mere qualification condition. The adjoint construction yields a selection of a conservative field for the value function, providing a computable first-order object without requiring differentiation of the solution mapping. Through examples, we show that even in smooth problems, the formal adjoint construction fails without conservativity or definability, illustrating the relevance of these concepts to grasp theoretical aspects of the method. This work provides a tool which can be directly combined with existing primal-dual solvers for a wide range of parametric optimization problems.
@article{bolte2026adjointstatemethodparametric,title={The adjoint state method for parametric definable optimization without smoothness or uniqueness},author={Bolte, Jérôme and Pauwels, Edouard and Traoré, Cheik},year={2026},month=mar,eprint={2603.26503},archiveprefix={arXiv},journal={arXiv preprint arXiv:2603.26503},primaryclass={math.OC},note={(Authors in aphabetical order)}}
2025
arXiv
Bregman Stochastic Proximal Point Algorithm with Variance Reduction
Stochastic algorithms, especially stochastic gradient descent (SGD), have proven to be
the go-to methods in data science and machine learning. In recent years, the stochastic
proximal point algorithm (SPPA) emerged, and it was shown to be more robust than SGD
with respect to stepsize settings. However, SPPA still suffers from a decreased convergence
rate due to the need for vanishing stepsizes, which is resolved by using variance reduction
methods. In the deterministic setting, there are many problems that can be solved more
efficiently when viewing them in a non-Euclidean geometry using Bregman distances.
This paper combines these two worlds and proposes variance reduction techniques for
the Bregman stochastic proximal point algorithm (BSPPA). As special cases, we obtain
SAGA- and SVRG-like variance reduction techniques for BSPPA. Our theoretical and
numerical results demonstrate improved stability and convergence rates compared to the
vanilla BSPPA with constant and vanishing stepsizes, respectively. Our analysis, also,
allow to recover the same variance reduction techniques for Bregman SGD in a unified
way.
@article{traoré2025bsppa,title={Bregman Stochastic Proximal Point Algorithm with Variance Reduction},author={Traor{\'e}, Cheik and Ochs, Peter},year={2025},month=oct,eprint={2510.16655},archiveprefix={arXiv},primaryclass={math.OC},journal={arXiv preprint arXiv:2510.16655},}
arXiv
A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm
Marco
Rando,
Cheik Traoré
, Cesare
Molinari, Lorenzo
Rosasco, and Silvia
Villa
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},month=jun,}
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},}
