Source author record

Romain Cosson

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Machine Learning Computer Science and Game Theory math.OC math.PR math.ST Statistics Theory

Catalog footprint

Research overview

4works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

The value of random zero-sum games

We study the value of a two-player zero-sum game on a random matrix $M\in \mathbb{R}^{n\times m}$ , defined by $v(M) = \min_{x\inΔ_n}\max_{y\in Δ_m}x^T M y$ . In the setting where $n=m$ and $M$ has i.i.d. standard Gaussian entries, we prove that the standard deviation of $v(M)$ is of order $\frac{1}{n}$ . This confirms an experimental conjecture dating back to the 1980s. We also investigate the case where $M$ is a rectangular Gaussian matrix with $m = n+λ\sqrt{n}$ , showing that the expected value of the game is of order $\fracλ{n}$ , as well as the case where $M$ is a random orthogonal matrix. Our techniques are based on probabilistic arguments and convex geometry. We argue that the study of random games could shed new light on various problems in theoretical computer science.

preprint2022arXiv

Gradient Descent for Low-Rank 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 \emph{Low-Rank Gradient Descent} (LRGD) algorithm finds an $ε$ -approximate stationary point 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 complexities" of LRGD for strongly convex and non-convex objective functions are $\mathcal{O}(r \log(1/ε) + rp)$ and $\mathcal{O}(r/ε^2 + rp)$ , respectively. When $r \ll p$ , these complexities are smaller than the known complexities of $\mathcal{O}(p \log(1/ε))$ and $\mathcal{O}(p/ε^2)$ of {\gd} in the strongly convex and non-convex settings, respectively. Thus, LRGD significantly reduces the computational cost of gradient-based methods for sufficiently low-rank functions. In the course of our analysis, we also formally define and characterize the classes of exact and approximately low-rank functions.

preprint2022arXiv

Universal Online Learning with Bounded Loss: Reduction to Binary Classification

We study universal consistency of non-i.i.d. processes in the context of online learning. A stochastic process is said to admit universal consistency if there exists a learner that achieves vanishing average loss for any measurable response function on this process. When the loss function is unbounded, Blanchard et al. showed that the only processes admitting strong universal consistency are those taking a finite number of values almost surely. However, when the loss function is bounded, the class of processes admitting strong universal consistency is much richer and its characterization could be dependent on the response setting (Hanneke). In this paper, we show that this class of processes is independent from the response setting thereby closing an open question (Hanneke, Open Problem 3). Specifically, we show that the class of processes that admit universal online learning is the same for binary classification as for multiclass classification with countable number of classes. Consequently, any output setting with bounded loss can be reduced to binary classification. Our reduction is constructive and practical. Indeed, we show that the nearest neighbor algorithm is transported by our construction. For binary classification on a process admitting strong universal learning, we prove that nearest neighbor successfully learns at least all finite unions of intervals.

preprint2022arXiv

Universal Online Learning with Unbounded Losses: Memory Is All You Need

We resolve an open problem of Hanneke on the subject of universally consistent online learning with non-i.i.d. processes and unbounded losses. The notion of an optimistically universal learning rule was defined by Hanneke in an effort to study learning theory under minimal assumptions. A given learning rule is said to be optimistically universal if it achieves a low long-run average loss whenever the data generating process makes this goal achievable by some learning rule. Hanneke posed as an open problem whether, for every unbounded loss, the family of processes admitting universal learning are precisely those having a finite number of distinct values almost surely. In this paper, we completely resolve this problem, showing that this is indeed the case. As a consequence, this also offers a dramatically simpler formulation of an optimistically universal learning rule for any unbounded loss: namely, the simple memorization rule already suffices. Our proof relies on constructing random measurable partitions of the instance space and could be of independent interest for solving other open questions. We extend the results to the non-realizable setting thereby providing an optimistically universal Bayes consistent learning rule.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Romain Cosson

Research overview

Is this your work?

4 publications

The value of random zero-sum games

Gradient Descent for Low-Rank Functions

Universal Online Learning with Bounded Loss: Reduction to Binary Classification

Universal Online Learning with Unbounded Losses: Memory Is All You Need

See the researcher in context

Building this map preview