RCRomain Cosson

Romain Cosson

*This is an algorithmically generated author record based on publicly available information.

Romain Cosson has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Collective algorithms for exploration and decision-making

    by Romain Cosson

    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.

  • Gradient Descent with Low-Rank Objective Functions

    by Romain Cosson, Ali Jadbabaie, Anuran Makur, Amirhossein Reisizadeh, Devavrat Shah

    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

    Low-Rank Gradient Descent

    by Romain Cosson, Ali Jadbabaie, Anuran Makur, Amirhossein Reisizadeh, Devavrat Shah

    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

    Brief Announcement: Efficient Collaborative Tree Exploration with Breadth-First Depth-Next

    by Romain Cosson, Laurent Massoulie, Laurent Viennot

    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].