Romain Cosson
Romain Cosson has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Ali Jadbabaie
Massachusetts Institute of Technology, Cambridge, MA, USA
2 shared publications - Amirhossein Reisizadeh
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, USA
2 shared publications - Anuran Makur
Department of Computer Science and the Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA
2 shared publications - Devavrat Shah
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
2 shared publications - Laurent Massoulié
Inria Paris, ENS Paris, Paris, France
1 shared publication - Laurent Viennot
INRIA, DI ENS, Paris, France
1 shared publication
Latest Publications
- 9 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Collective algorithms for exploration and decision-making
Algorithmes collectifs pour l'exploration et la prise de décision: Cette thèse porte sur la prise de décision séquentielle, dite 'en ligne', c’est-à-dire sur la conception d’algorithmes capables de traiter des données révélées progressivement. Un problème central qui motive cette étude est l’exploration collective d’un arbre, dans lequel une équipe d’agents mobiles doit explorer un arbre inconnu en partant de sa racine, aussi rapidement que possible. À tout moment, les déplacements des agents doivent être décidés uniquement sur la base des informations déjà recueillies. Ce problème modélise une question fondamentale : l’exploration d’un labyrinthe est-elle parallélisable ? Cette thèse propose de nouvelles perspectives, de nouveaux algorithmes, ainsi que des garanties théoriques améliorées pour l’exploration collective des arbres. Nous mettons également en lumière des liens profonds avec des problèmes en ligne classiques, tels que la traversée de graphes, conduisant à de nouvelles questions et de nouveaux résultats pour ce problème également. Un thème récurrent dans la prise de décision en ligne est que les algorithmes aléatoires surpassent souvent les algorithmes déterministes. Nous proposons de réexaminer ce fait à travers le prisme des algorithmes collectifs, avec l’idée qu’une équipe d’agents simples (e.g., déterministes) peut collectivement obtenir de meilleures performances qu’un agent seul. Cette approche s’inscrit dans le cadre des algorithmes faiblement randomisés, qui utilisent seulement un nombre fini de bits aléatoires. Nous introduisons des algorithmes collectifs pour deux problèmes classiques : les systèmes de tâches métriques et le problème des k-serveurs. Cela offre une nouvelle perspective sur la complexité avec indices de ces problèmes, c’est-à-dire sur la manière dont la connaissance partielle de la donnée d’entrée peut améliorer les performances. La thèse aborde également d’autres aspects de la prise de décision en ligne, tels que l’analyse en moyenne, la complexité de communication, la complexité en espace, et la complexité computationnelle.
- 9 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Collective algorithms for exploration and decision-making
Algorithmes collectifs pour l'exploration et la prise de décision: Cette thèse porte sur la prise de décision séquentielle, dite 'en ligne', c’est-à-dire sur la conception d’algorithmes capables de traiter des données révélées progressivement. Un problème central qui motive cette étude est l’exploration collective d’un arbre, dans lequel une équipe d’agents mobiles doit explorer un arbre inconnu en partant de sa racine, aussi rapidement que possible. À tout moment, les déplacements des agents doivent être décidés uniquement sur la base des informations déjà recueillies. Ce problème modélise une question fondamentale : l’exploration d’un labyrinthe est-elle parallélisable ? Cette thèse propose de nouvelles perspectives, de nouveaux algorithmes, ainsi que des garanties théoriques améliorées pour l’exploration collective des arbres. Nous mettons également en lumière des liens profonds avec des problèmes en ligne classiques, tels que la traversée de graphes, conduisant à de nouvelles questions et de nouveaux résultats pour ce problème également. Un thème récurrent dans la prise de décision en ligne est que les algorithmes aléatoires surpassent souvent les algorithmes déterministes. Nous proposons de réexaminer ce fait à travers le prisme des algorithmes collectifs, avec l’idée qu’une équipe d’agents simples (e.g., déterministes) peut collectivement obtenir de meilleures performances qu’un agent seul. Cette approche s’inscrit dans le cadre des algorithmes faiblement randomisés, qui utilisent seulement un nombre fini de bits aléatoires. Nous introduisons des algorithmes collectifs pour deux problèmes classiques : les systèmes de tâches métriques et le problème des k-serveurs. Cela offre une nouvelle perspective sur la complexité avec indices de ces problèmes, c’est-à-dire sur la manière dont la connaissance partielle de la donnée d’entrée peut améliorer les performances. La thèse aborde également d’autres aspects de la prise de décision en ligne, tels que l’analyse en moyenne, la complexité de communication, la complexité en espace, et la complexité computationnelle.
- 13 December 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 34, 3309-3314
Gradient Descent with Low-Rank Objective Functions
Several recent empirical studies demonstrate that important machine learning tasks, e.g., training deep neural networks, exhibit low-rank structure, where the loss function varies significantly in only a few directions of the input space. In this paper, we leverage such low-rank structure to reduce the high computational cost of canonical gradient-based methods such as gradient descent (GD). Our proposed Low-Rank Gradient Descent (LRGD) algorithm finds an $\epsilon$ -minimizer of a p-dimensional function by first identifying $r\leq p$ significant directions, and then estimating the true p-dimensional gradient at every iteration by computing directional derivatives only along those $r$ directions. We establish that the “directional oracle complexity” of LRGD for strongly convex objective functions is $\mathrm{O}(r\log(1/\epsilon)+rp)$ . Therefore, when $r\ll p$ , LRGD provides significant improvement over the known complexity of $\mathcal{O}(p\log(1/\epsilon))$ of GD in the strongly convex setting. Furthermore, using real and synthetic data, we empirically find that LRGD provides significant gains over GD when the data has low-rank structure, and in the absence of such structure, LRGD does not degrade performance compared to GD.- 13 December 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 34, 3309-3314
Gradient Descent with Low-Rank Objective Functions
Several recent empirical studies demonstrate that important machine learning tasks, e.g., training deep neural networks, exhibit low-rank structure, where the loss function varies significantly in only a few directions of the input space. In this paper, we leverage such low-rank structure to reduce the high computational cost of canonical gradient-based methods such as gradient descent (GD). Our proposed Low-Rank Gradient Descent (LRGD) algorithm finds an $\epsilon$ -minimizer of a p-dimensional function by first identifying $r\leq p$ significant directions, and then estimating the true p-dimensional gradient at every iteration by computing directional derivatives only along those $r$ directions. We establish that the “directional oracle complexity” of LRGD for strongly convex objective functions is $\mathrm{O}(r\log(1/\epsilon)+rp)$ . Therefore, when $r\ll p$ , LRGD provides significant improvement over the known complexity of $\mathcal{O}(p\log(1/\epsilon))$ of GD in the strongly convex setting. Furthermore, using real and synthetic data, we empirically find that LRGD provides significant gains over GD when the data has low-rank structure, and in the absence of such structure, LRGD does not degrade performance compared to GD.- Open Access
- 13 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Open Journal of Control Systems
- Vol. 2, 380-395
Low-Rank Gradient Descent
Several recent empirical studies demonstrate that important machine learning tasks such as training deep neural networks, exhibit a low-rank structure, where most of the variation in the loss function occurs only in a few directions of the input space. In this paper, we leverage such low-rank structure to reduce the high computational cost of canonical gradient-based methods such as gradient descent (GD). Our proposed Low-Rank Gradient Descent (LRGD) algorithm finds an $\epsilon$ -approximate stationary point of a p-dimensional function by first identifying $r ≤ p$ significant directions, and then estimating the true p-dimensional gradient at every iteration by computing directional derivatives only along those r directions. We establish that the “directional oracle complexities” of LRGD for strongly convex and non-convex objective functions are $\mathcal{O}(r\ {\rm{log}}(1/\epsilon) + rp)$ and $\mathcal{O}(r/\epsilon^2 + rp)$ , respectively. Therefore, when $r\ll p$ , LRGD provides significant improvement over the known complexities of $\mathcal{O}(p\ \rm{log}(1/\epsilon)$ ) and $\mathcal{O}(p/\epsilon^2)$ of GD in the strongly convex and non-convex settings, respectively. Furthermore, we formally characterize the classes of exactly and approximately low-rank functions. Empirically, using real and synthetic data, LRGD provides significant gains over GD when the data has low-rank structure, and in the absence of such structure, LRGD does not degrade performance compared to GD. This suggests that LRGD could be used in practice in any setting in place of GD.
- 13 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Open Journal of Control Systems
- Vol. 2, 380-395
Open AccessLow-Rank Gradient Descent
Several recent empirical studies demonstrate that important machine learning tasks such as training deep neural networks, exhibit a low-rank structure, where most of the variation in the loss function occurs only in a few directions of the input space. In this paper, we leverage such low-rank structure to reduce the high computational cost of canonical gradient-based methods such as gradient descent (GD). Our proposed Low-Rank Gradient Descent (LRGD) algorithm finds an $\epsilon$ -approximate stationary point of a p-dimensional function by first identifying $r ≤ p$ significant directions, and then estimating the true p-dimensional gradient at every iteration by computing directional derivatives only along those r directions. We establish that the “directional oracle complexities” of LRGD for strongly convex and non-convex objective functions are $\mathcal{O}(r\ {\rm{log}}(1/\epsilon) + rp)$ and $\mathcal{O}(r/\epsilon^2 + rp)$ , respectively. Therefore, when $r\ll p$ , LRGD provides significant improvement over the known complexities of $\mathcal{O}(p\ \rm{log}(1/\epsilon)$ ) and $\mathcal{O}(p/\epsilon^2)$ of GD in the strongly convex and non-convex settings, respectively. Furthermore, we formally characterize the classes of exactly and approximately low-rank functions. Empirically, using real and synthetic data, LRGD provides significant gains over GD when the data has low-rank structure, and in the absence of such structure, LRGD does not degrade performance compared to GD. This suggests that LRGD could be used in practice in any setting in place of GD.
- Open Access
- 16 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 24-27
Brief Announcement: Efficient Collaborative Tree Exploration with Breadth-First Depth-Next
We consider the problem of collaborative tree exploration posed by Fraigniaud, Gasieniec, Kowalski, and Pelc [8] where a team of k agents is tasked to collectively go through all the edges of an unknown tree as fast as possible and return to the root. Denoting by n the total number of nodes and by D the tree depth, the O(n/log(k) + D) algorithm of [8] achieves the best competitive ratio known with respect to the optimal exploration algorithm that knows the tree in advance, which takes order max {2n/k, 2D} rounds. Brass, Cabrera-Mora, Gasparri, and Xiao [1] consider an alternative performance criterion, the additive overhead with respect to 2n/k, and obtain a 2n/k + O((D + k)k) runtime guarantee. In this announcement, we present 'Breadth-First Depth-Next' (BFDN), a novel and simple algorithm that performs collaborative tree exploration in time 2n/k + O(D2 log(k)), thus outperforming [1] for all values of (n, D) and being order-optimal for fixed k and trees with depth D = o(√n). The proof of our result crucially relies on the analysis of a simple two-player game with balls in urns that could be of independent interest. We extend the guarantees of BFDN to: scenarios with limited memory and communication, adversarial setups where robots can be blocked, and exploration of classes of non-tree graphs. Finally, we provide a recursive version of BFDN with a runtime of Oℓ(n/k1/ℓ + log(k)D1+1/ℓ) for parameter ℓ ≥ 1, thereby improving performance for trees with large depth. A complete version of the paper is available online [2].
- 16 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 24-27
Open AccessBrief Announcement: Efficient Collaborative Tree Exploration with Breadth-First Depth-Next
We consider the problem of collaborative tree exploration posed by Fraigniaud, Gasieniec, Kowalski, and Pelc [8] where a team of k agents is tasked to collectively go through all the edges of an unknown tree as fast as possible and return to the root. Denoting by n the total number of nodes and by D the tree depth, the O(n/log(k) + D) algorithm of [8] achieves the best competitive ratio known with respect to the optimal exploration algorithm that knows the tree in advance, which takes order max {2n/k, 2D} rounds. Brass, Cabrera-Mora, Gasparri, and Xiao [1] consider an alternative performance criterion, the additive overhead with respect to 2n/k, and obtain a 2n/k + O((D + k)k) runtime guarantee. In this announcement, we present 'Breadth-First Depth-Next' (BFDN), a novel and simple algorithm that performs collaborative tree exploration in time 2n/k + O(D2 log(k)), thus outperforming [1] for all values of (n, D) and being order-optimal for fixed k and trees with depth D = o(√n). The proof of our result crucially relies on the analysis of a simple two-player game with balls in urns that could be of independent interest. We extend the guarantees of BFDN to: scenarios with limited memory and communication, adversarial setups where robots can be blocked, and exploration of classes of non-tree graphs. Finally, we provide a recursive version of BFDN with a runtime of Oℓ(n/k1/ℓ + log(k)D1+1/ℓ) for parameter ℓ ≥ 1, thereby improving performance for trees with large depth. A complete version of the paper is available online [2].