Jérôme Malick
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Jérôme Malick has a total of 42 co-authors. Here are the top co-authors by number of shared publications:
- Franck Iutzeler
University of Grenoble Alpes, Grenoble, France
16 shared publications - Aris Daniilidis
Institut für Stochastik und Wirtschaftsmathematik, VADOR E105-04 TU Wien, Wien, Austria
6 shared publications - Yassine Laguel
Univ. Grenoble Alpes, CNRS, Grenoble INP, LJK, Grenoble, France
6 shared publications - Panayotis Mertikopoulos
Univ. Grenoble Alpes CNRS Inria Grenoble INP 38000 LIG Grenoble France
5 shared publications - Wim van Ackooij
EDF Lab Paris-Saclay, Palaiseau, France
5 shared publications - Hristo Sendov
Department of Statistical and Actuarial Sciences, Department of Mathematics, Western University, London, Canada
4 shared publications
Latest Publications
- Open Access
Knapsack with compactness: a semidefinite approach
The min-knapsack problem with compactness constraints extends the classical knapsack problem, in the case of ordered items, by introducing a restriction ensuring that they cannot be too far apart. This problem has applications in statistics, particularly in the detection of change-points in time series. In this paper, we propose a semidefinite programming approach for this problem, incorporating compactness in constraints or in objective. We study and compare the different relaxations, and argue that our method provides high-quality heuristics and tight bounds. In particular, the single hyperparameter of our penalized semidefinite models naturally balances the trade-off between compactness and accuracy of the computed solutions. Numerical experiments illustrate, on the hardest instances, the effectiveness and versatility of our approach compared to the existing mixed-integer programming formulation.
Open AccessKnapsack with compactness: a semidefinite approach
The min-knapsack problem with compactness constraints extends the classical knapsack problem, in the case of ordered items, by introducing a restriction ensuring that they cannot be too far apart. This problem has applications in statistics, particularly in the detection of change-points in time series. In this paper, we propose a semidefinite programming approach for this problem, incorporating compactness in constraints or in objective. We study and compare the different relaxations, and argue that our method provides high-quality heuristics and tight bounds. In particular, the single hyperparameter of our penalized semidefinite models naturally balances the trade-off between compactness and accuracy of the computed solutions. Numerical experiments illustrate, on the hardest instances, the effectiveness and versatility of our approach compared to the existing mixed-integer programming formulation.
- 9 July 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 34 (3) , 2440-2471
The Rate of Convergence of Bregman Proximal Methods: Local Geometry Versus Regularity Versus Sharpness
We examine the last-iterate convergence rate of Bregman proximal methods—from mirror descent to mirror-prox and its optimistic variants—as a function of the local geometry induced by the prox-mapping defining the method. For generality, we focus on local solutions of constrained, nonmonotone variational inequalities, and we show that the convergence rate of a given method depends sharply on its associated Legendre exponent, a notion that measures the growth rate of the underlying Bregman function (Euclidean, entropic, or other) near a solution. In particular, we show that boundary solutions exhibit a stark separation of regimes between methods with a zero and nonzero Legendre exponent: The former converge at a linear rate, while the latter converge, in general, sublinearly. This dichotomy becomes even more pronounced in linearly constrained problems where methods with entropic regularization achieve a linear convergence rate along sharp directions, compared to convergence in a finite number of steps under Euclidean regularization.
- 9 July 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 34 (3) , 2440-2471
The Rate of Convergence of Bregman Proximal Methods: Local Geometry Versus Regularity Versus Sharpness
We examine the last-iterate convergence rate of Bregman proximal methods—from mirror descent to mirror-prox and its optimistic variants—as a function of the local geometry induced by the prox-mapping defining the method. For generality, we focus on local solutions of constrained, nonmonotone variational inequalities, and we show that the convergence rate of a given method depends sharply on its associated Legendre exponent, a notion that measures the growth rate of the underlying Bregman function (Euclidean, entropic, or other) near a solution. In particular, we show that boundary solutions exhibit a stark separation of regimes between methods with a zero and nonzero Legendre exponent: The former converge at a linear rate, while the latter converge, in general, sublinearly. This dichotomy becomes even more pronounced in linearly constrained problems where methods with entropic regularization achieve a linear convergence rate along sharp directions, compared to convergence in a finite number of steps under Euclidean regularization.
- 27 April 2024
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 88 (3) , 819-847
Chance-constrained programs with convex underlying functions: a bilevel convex optimization perspective
- 27 April 2024
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 88 (3) , 819-847
Chance-constrained programs with convex underlying functions: a bilevel convex optimization perspective
- 23 August 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 33 (3) , 2222-2247
Harnessing Structure in Composite Nonsmooth Minimization
We consider the problem of minimizing the composition of a nonsmooth function with a smooth mapping in the case where the proximity operator of the nonsmooth function can be explicitly computed. We first show that this proximity operator can provide the exact smooth substructure of minimizers, not only of the nonsmooth function, but also of the full composite function. We then exploit this proximal identification by proposing an algorithm which combines proximal steps with sequential quadratic programming steps. We show that our method locally identifies the optimal smooth substructure and then converges quadratically. We illustrate its behavior on two problems: the minimization of a maximum of quadratic functions and the minimization of the maximal eigenvalue of a parametrized matrix.
- 23 August 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 33 (3) , 2222-2247
Harnessing Structure in Composite Nonsmooth Minimization
We consider the problem of minimizing the composition of a nonsmooth function with a smooth mapping in the case where the proximity operator of the nonsmooth function can be explicitly computed. We first show that this proximity operator can provide the exact smooth substructure of minimizers, not only of the nonsmooth function, but also of the full composite function. We then exploit this proximal identification by proposing an algorithm which combines proximal steps with sequential quadratic programming steps. We show that our method locally identifies the optimal smooth substructure and then converges quadratically. We illustrate its behavior on two problems: the minimization of a maximum of quadratic functions and the minimization of the maximal eigenvalue of a parametrized matrix.
- Open Access
The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness
We examine the last-iterate convergence rate of Bregman proximal methods - from mirror descent to mirror-prox and its optimistic variants - as a function of the local geometry induced by the prox-mapping defining the method. For generality, we focus on local solutions of constrained, non-monotone variational inequalities, and we show that the convergence rate of a given method depends sharply on its associated Legendre exponent, a notion that measures the growth rate of the underlying Bregman function (Euclidean, entropic, or other) near a solution. In particular, we show that boundary solutions exhibit a stark separation of regimes between methods with a zero and non-zero Legendre exponent: the former converge at a linear rate, while the latter converge, in general, sublinearly. This dichotomy becomes even more pronounced in linearly constrained problems where methods with entropic regularization achieve a linear convergence rate along sharp directions, compared to convergence in a finite number of steps under Euclidean regularization.
Open AccessThe rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness
We examine the last-iterate convergence rate of Bregman proximal methods - from mirror descent to mirror-prox and its optimistic variants - as a function of the local geometry induced by the prox-mapping defining the method. For generality, we focus on local solutions of constrained, non-monotone variational inequalities, and we show that the convergence rate of a given method depends sharply on its associated Legendre exponent, a notion that measures the growth rate of the underlying Bregman function (Euclidean, entropic, or other) near a solution. In particular, we show that boundary solutions exhibit a stark separation of regimes between methods with a zero and non-zero Legendre exponent: the former converge at a linear rate, while the latter converge, in general, sublinearly. This dichotomy becomes even more pronounced in linearly constrained problems where methods with entropic regularization achieve a linear convergence rate along sharp directions, compared to convergence in a finite number of steps under Euclidean regularization.
- 16 May 2023
- Published by Springer Nature in Machine Learning
- Vol. 113 (5) , 2955-3022
Federated learning with superquantile aggregation for heterogeneous data
- 16 May 2023
- Published by Springer Nature in Machine Learning
- Vol. 113 (5) , 2955-3022
Federated learning with superquantile aggregation for heterogeneous data
- Open Access
- 11 May 2023
- Published by EDP Sciences in ESAIM: Control, Optimisation and Calculus of Variations
- Vol. 29, 33
Regularization for Wasserstein distributionally robust optimization
Optimal transport has recently proved to be a useful tool in various machine learning applications needing comparisons of probability measures. Among these, applications of distributionally robust optimization naturally involve Wasserstein distances in their models of uncertainty, capturing data shifts or worst-case scenarios. Inspired by the success of the regularization of Wasserstein distances in optimal transport, we study in this paper the regularization of Wasserstein distributionally robust optimization. First, we derive a general strong duality result of regularized Wasserstein distributionally robust problems. Second, we refine this duality result in the case of entropic regularization and provide an approximation result when the regularization parameters vanish.
- 11 May 2023
- Published by EDP Sciences in ESAIM: Control, Optimisation and Calculus of Variations
- Vol. 29, 33
Open AccessRegularization for Wasserstein distributionally robust optimization
Optimal transport has recently proved to be a useful tool in various machine learning applications needing comparisons of probability measures. Among these, applications of distributionally robust optimization naturally involve Wasserstein distances in their models of uncertainty, capturing data shifts or worst-case scenarios. Inspired by the success of the regularization of Wasserstein distances in optimal transport, we study in this paper the regularization of Wasserstein distributionally robust optimization. First, we derive a general strong duality result of regularized Wasserstein distributionally robust problems. Second, we refine this duality result in the case of entropic regularization and provide an approximation result when the regularization parameters vanish.
- Open Access
Harnessing structure in composite nonsmooth minimization
We consider the problem of minimizing the composition of a nonsmooth function with a smooth mapping in the case where the proximity operator of the nonsmooth function can be explicitly computed. We first show that this proximity operator can provide the exact smooth substructure of minimizers, not only of the nonsmooth function, but also of the full composite function. We then exploit this proximal identification by proposing an algorithm which combines proximal steps with sequential quadratic programming steps. We show that our method locally identifies the optimal smooth substructure and then converges quadratically. We illustrate its behavior on two problems: the minimization of a maximum of quadratic functions and the minimization of the maximal eigenvalue of a parametrized matrix.
Open AccessHarnessing structure in composite nonsmooth minimization
We consider the problem of minimizing the composition of a nonsmooth function with a smooth mapping in the case where the proximity operator of the nonsmooth function can be explicitly computed. We first show that this proximity operator can provide the exact smooth substructure of minimizers, not only of the nonsmooth function, but also of the full composite function. We then exploit this proximal identification by proposing an algorithm which combines proximal steps with sequential quadratic programming steps. We show that our method locally identifies the optimal smooth substructure and then converges quadratically. We illustrate its behavior on two problems: the minimization of a maximum of quadratic functions and the minimization of the maximal eigenvalue of a parametrized matrix.
- Open Access
Push--Pull with Device Sampling
We consider decentralized optimization problems in which a number of agents collaborate to minimize the average of their local functions by exchanging over an underlying communication graph. Specifically, we place ourselves in an asynchronous model where only a random portion of nodes perform computation at each iteration, while the information exchange can be conducted between all the nodes and in an asymmetric fashion. For this setting, we propose an algorithm that combines gradient tracking with a network-level variance reduction (in contrast to variance reduction within each node). This enables each node to track the average of the gradients of the objective functions. Our theoretical analysis shows that the algorithm converges linearly, when the local objective functions are strongly convex, under mild connectivity conditions on the expected mixing matrices. In particular, our result does not require the mixing matrices to be doubly stochastic. In the experiments, we investigate a broadcast mechanism that transmits information from computing nodes to their neighbors, and confirm the linear convergence of our method on both synthetic and real-world datasets.
Open AccessPush--Pull with Device Sampling
We consider decentralized optimization problems in which a number of agents collaborate to minimize the average of their local functions by exchanging over an underlying communication graph. Specifically, we place ourselves in an asynchronous model where only a random portion of nodes perform computation at each iteration, while the information exchange can be conducted between all the nodes and in an asymmetric fashion. For this setting, we propose an algorithm that combines gradient tracking with a network-level variance reduction (in contrast to variance reduction within each node). This enables each node to track the average of the gradients of the objective functions. Our theoretical analysis shows that the algorithm converges linearly, when the local objective functions are strongly convex, under mild connectivity conditions on the expected mixing matrices. In particular, our result does not require the mixing matrices to be doubly stochastic. In the experiments, we investigate a broadcast mechanism that transmits information from computing nodes to their neighbors, and confirm the linear convergence of our method on both synthetic and real-world datasets.
- 28 February 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 68 (12) , 7179-7194
Push–Pull With Device Sampling
We consider decentralized optimization problems in which a number of agents collaborate to minimize the average of their local functions by exchanging over an underlying communication graph. Specifically, we place ourselves in an asynchronous model where only a random portion of nodes perform computation at each iteration, while the information exchange can be conducted between all the nodes and in an asymmetric fashion. For this setting, we propose an algorithm that combines gradient tracking with a network-level variance reduction (in contrast to variance reduction within each node). This enables the nodes to track the average of the gradients of the objective functions. Our theoretical analysis shows that the algorithm converges linearly, when the local objective functions are strongly convex, under mild connectivity conditions on the expected mixing matrices. In particular, our result does not require the mixing matrices to be doubly stochastic. In the experiments, we investigate a broadcast mechanism that transmits information from computing nodes to their neighbors, and confirm the linear convergence of our method on both synthetic and real-world datasets.
- 28 February 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 68 (12) , 7179-7194
Push–Pull With Device Sampling
We consider decentralized optimization problems in which a number of agents collaborate to minimize the average of their local functions by exchanging over an underlying communication graph. Specifically, we place ourselves in an asynchronous model where only a random portion of nodes perform computation at each iteration, while the information exchange can be conducted between all the nodes and in an asymmetric fashion. For this setting, we propose an algorithm that combines gradient tracking with a network-level variance reduction (in contrast to variance reduction within each node). This enables the nodes to track the average of the gradients of the objective functions. Our theoretical analysis shows that the algorithm converges linearly, when the local objective functions are strongly convex, under mild connectivity conditions on the expected mixing matrices. In particular, our result does not require the mixing matrices to be doubly stochastic. In the experiments, we investigate a broadcast mechanism that transmits information from computing nodes to their neighbors, and confirm the linear convergence of our method on both synthetic and real-world datasets.