FCFrançois Clément

François Clément

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


François Clément has a total of 24 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • An Optimization Perspective on the Construction of Low-Discrepancy Point Sets

    by François Clément

    La construction d'ensembles de points à faible discrépance via des approches d'optimisation: Les mesures de discrépance sont une famille de mesures quantifiant l'uniformité d'un ensemble de points: sont-ils bien répartis dans l'espace (discrépance faible) ou concentrés par endroits (discrépance élevée)? Parmi ces mesures, la discrépance à l'origine L∞ joue un rôle primordial: elle permet de quantifier l'erreur faite lors de l'approximation d'une intégrale par une somme finie composée d'évaluations de la fonction en un ensemble de points. Ce résultat mène à de très nombreuses applications dans des domaines variés allant de la vision en informatique à la finance, sans oublier tout ce qui concerne le plan d'expérience (design of experiments), où des points bien répartis sont essentiels. Les points à faible discrépance utilisés dans ces applications sont issus d'approches mathématiques en théorie des nombres, avec de nombreuses séquences ou ensembles de points connus depuis plusieurs décennies. Malgré cela, ce sujet reste surtout le domaine de mathématiciens, souvent plus intéressés par les propriétés asymptotiques de ces points que leur utilisations en pratique. Il en résulte que les ensembles à faible discrépance, bien que très bons théoriquement, sont parfois moins bien que des points aléatoires pour certaines applications, particulièrement lorsque la dimension augmente. D'un point de vue plus qualitatif, malgré certaines bornes asymptotiques, nous ne savons pas précisément quelle est la limite inférieure pour la discrépance d'un ensemble de points d'une taille fixée. Or, ce type de question a un impact immédiat sur la qualité des résultats lors d'applications. Dans cette thèse, nous abordons le problème de la construction d'ensembles à faible discrépance d'un point de vue informatique, tout en obtenant de nombreux résultats empiriques sur la qualité de ces ensembles. Plutôt que de construire mathématiquement ces séquences, nous utilisons un ensemble de méthodes issues de l'optimisation, ainsi que les séquences existantes, pour obtenir de nouveaux ensembles de points. Nous montrons qu'il est possible d'obtenir des ensembles de points de bien meilleure discrépance à l'origine L∞ que ceux existant déjà, dans des dimensions variées. Enfin, nous présentons également une approche basée sur la discrépance à l'origine L2, pour montrer que son utilisation de manière gloutonne permet la construction d'une séquence extrêmement régulière pour la discrépance L∞, ouvrant la voie vers de nombreuses approches novatrices.


  • Open Access

    Many critical points for discrete Riesz energy on $\mathbb{T}^2$

    by François Clément, Stefan Steinerberger

    It is widely believed that the energy functional $E_p:(\mathbb{S}^2)^n \rightarrow \mathbb{R}$ $$ E_p = \sum_{i,j=1 \atop i \neq j}^{n} \frac{1}{\|x_i-x_j\|^p}$$ has a number of critical points, $\nabla E(x) = 0$, that grows exponentially in $n$. Despite having been extensively tested and being physically well motivated, no rigorous result in this direction exists. We prove a version of this result on the two-dimensional flat torus $\mathbb{T}^2$ and show that there are infinitely many $n \in \mathbb{N}$ such that the number of critical points of $E_p: (\mathbb{T}^2)^n \rightarrow \mathbb{R}$ is at least $\exp(c \sqrt{n})$ provided $p \geq 5 \log{n}$. We also investigate the special cases $n=3,4,5$ which turn out to be surprisingly interesting.

  • Open Access

    Balanced Stick Breaking

    by François Clément, Stefan Steinerberger

    Consider an infinite sequence $(x_k)_{k=1}^{\infty}$ on the unit circle $\mathbb{S}^1$. We may interpret the first $n$ elements $(x_k)_{k=1}^{n}$ as places where the `circular stick' $\mathbb{S}^1$ is broken into a total of $n+1$ pieces. It is clear that they cannot all be the same length all the time. de Bruijn and Erdős (1949) show that the ratio of the largest to the smallest has to be arbitrarily close to 2 infinitely many times which is sharp. They also consider the problem of balancing the length of $r$ consecutive intervals and prove $$ \frac{\max \mbox{length of}~r~\mbox{consecutive intervals}}{\min \mbox{length of}~r~\mbox{consecutive intervals}} \geq 1 + \frac{1}{r}.$$ We prove that this ratio can be as small as $1 + c \log{r}/ r$. This is done by means of refined discrepancy estimates for the van der Corput sequence over very short intervals and proves a conjecture of Brethouwer.

  • Open Access

    Low-Discrepancy Set Post-Processing via Gradient Descent

    by François Clément, Linhang Huang, Woorim Lee, Cole Smidt, Braeden Sodt, Xuan Zhang

    The construction of low-discrepancy sets, used for uniform sampling and numerical integration, has recently seen great improvements based on optimization and machine learning techniques. However, these methods are computationally expensive, often requiring days of computation or access to GPU clusters. We show that simple gradient descent-based techniques allow for comparable results when starting with a reasonably uniform point set. Not only is this method much more efficient and accessible, but it can be applied as post-processing to any low-discrepancy set generation method for a variety of standard discrepancy measures.

  • Open Access

    Robust Online Sampling from Possibly Moving Target Distributions

    by François Clément, Stefan Steinerberger

    We suppose we are given a list of points $x_1, \dots, x_n \in \mathbb{R}$, a target probability measure $μ$ and are asked to add additional points $x_{n+1}, \dots, x_{n+m}$ so that $x_1, \dots, x_{n+m}$ is as close as possible to the distribution of $μ$; additionally, we want this to be true uniformly for all $m$. We propose a simple method that achieves this goal. It selects new points in regions where the existing set is lacking points and avoids regions that are already overly crowded. If we replace $μ$ by another measure $μ_2$ in the middle of the computation, the method dynamically adjusts and allows us to keep the original sampling points. $x_{n+1}$ can be computed in $\mathcal{O}(n)$ steps and we obtain state-of-the-art results. It appears to be an interesting dynamical system in its own right; we analyze a continuous mean-field version that reflects much of the same behavior.

  • Open Access

    Small gaps in the Ulam sequence

    by François Clément, Stefan Steinerberger

    The Ulam sequence, described by Stanisław Ulam in the 1960s, starts 1, 2 and then iteratively adds the smallest integer that can be uniquely written as the sum of two distinct earlier terms: this gives 1,2,3,4,6,8,11,⋯ Already in 1972 the great French poet Raymond Queneau wrote that it “gives an impression of great irregularity”. This irregularity appears to have a lot of structure and has inspired a great deal of work; nonetheless, very little is actually known. We improve the best upper bound on its growth and show that some small gaps have to exist: for some c>0 and all n∈ℕ,min 1≤k≤n a k+1 a k ≤1+clogn n.

  • Open Access

    Regular Structures in Kronecker Permutations

    by François Clément

    Kronecker sequences $(k α\mod 1)_{k=1}^{\infty}$ for some irrational $α> 0$ have played an important role in many areas of mathematics. It is possible to associate to each finite segment $(k α\mod 1)_{k=1}^{n}$ a permutation $π\in S_n$ associated with the canonical lifting to two dimensions. We show that these permutations induced by Kronecker sequences based on irrational $α$ are extremely regular for specific choices of $n$ and $α$. In particular, all quadratic irrationals have an infinite number of choices of $n$ that lead to permutations where no cycle has length more than 4.

  • Open Access

    On the optimization of discrepancy measures

    by François Clément, Nathan Kirk, Art B. Owen, T. Konstantin Rusch

    Points in the unit cube with low discrepancy can be constructed using algebra or, more recently, by direct computational optimization of a criterion. The usual $L_\infty$ star discrepancy is a poor criterion for this because it is computationally expensive and lacks differentiability. Its usual replacement, the $L_2$ star discrepancy, is smooth but exhibits other pathologies shown by J. Matoušek. In an attempt to address these problems, we introduce the \textit{average squared discrepancy} which averages over $2^d$ versions of the $L_2$ star discrepancy anchored in the different vertices of $[0,1]^d$. Not only can this criterion be computed in $O(dn^2)$ time, like the $L_2$ star discrepancy, but also we show that it is equivalent to a weighted symmetric $L_2$ criterion of Hickernell's by a constant factor. We compare this criterion with a wide range of traditional discrepancy measures, and show that only the average squared discrepancy avoids the problems raised by Matoušek. Furthermore, we present a comprehensive numerical study showing in particular that optimizing for the average squared discrepancy leads to strong performance for the $L_2$ star discrepancy, whereas the converse does not hold.


  • Open Access

    Monotone Paths on Acyclic 3-Regular Graphs

    by François Clément, Dan Guyer

    Motivated by trying to understand the behavior of the simplex method, Athanasiadis, De Loera and Zhang provided upper and lower bounds on the number of the monotone paths on 3-polytopes. For simple 3-polytopes with $2n$ vertices, they showed that the number of monotone paths is bounded above by $(1+\varphi)^n$, with $\varphi$ being the golden ratio. We improve the result and show that for a larger family of graphs the number is bounded above by $c \cdot 1.6779^n$ for some universal constant $c$. Meanwhile, the best known construction and conjectured extremizer is approximately $\varphi^n$.

  • Top Cited Papers
    Open Access

    Constructing optimal star discrepancy sets

    by François Clément, Carola Doerr, Kathrin Klamroth, Luís Paquete

    We provide in this paper a constructive proof of optimal L ∞ L_{\infty } star discrepancy values in dimension 2 for up to 21 points and up to 8 points in dimension 3. This extends work by White (Numer. Math. 27 (1976/77), no. 2, 157–164) for up to six points in dimension 2 and of Larcher and Pillichshammer (J. Comput. Appl. Math. 206 (2007), no. 2, 977–985) for two points in arbitrary dimensions. We show that these optimal sets have a far lower discrepancy than the previous references and, perhaps more importantly, present a very different structure.