QLQuoc-Tung Le

Quoc-Tung Le

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

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


Quoc-Tung Le has a total of 13 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Rapture of the Deep: Highs and lows of sparsity in a world of depths

    by Rémi Gribonval, Elisa Riccietti, Quoc-Tung Le, Léon Zheng

    Promoting sparsity in deep networks is a natural way to control their complexity, and it is a timely endeavor since practical neural model sizes have grown to unprecedented levels. The lessons from sparsity in linear inverse problems also bear the promise of many other benefits beyond such computational aspects, from statistical significance to explainability. Can these promises be fulfilled? Can we safely leverage the know-how of sparsity-promoting regularizers for inverse problems to harness sparsity in deeper contexts, linear or not? This article surveys the curses and blessings of deep sparsity. After a reminder on the main lessons from inverse problems, we tour a number of results that challenge their immediate deep extensions, from both a mathematical and a computational perspective. In particular, we highlight that ${\mathit{\ell}}^{1}$ regularization does not always lead to sparsity, and that optimization with a prescribed set of allowed nonzero coefficients can be NP-hard. We emphasize the role of rescaling invariances in these phenomena and the need to favor structured sparsity to keep sparse network training problems under control, ensure their stability, and actually enable efficient network implementations on GPUs. We finally outline the promises and challenges of a flexible family of Kronecker sparsity structures, which extend the classical butterfly structure and appear in many classical scientific computing applications and that have also recently emerged in deep learning.

  • Bilevel Gradient Methods and the Morse Parametric Qualification Condition

    by Jérôme Bolte, Quoc-Tung Le, Edouard Pauwels, Samuel Vaiter

    We introduce the Morse parametric qualification condition for bilevel programming. Generic semialgebraic functions are Morse parametric in a piecewise sense. Thus, bilevel programs with a Morse parametric lower level constitute a relevant intermediate class between strongly convex and fully generic lower levels. In this framework, we study bilevel gradient algorithms with two strategies: the single-step multistep strategy, which involves a sequence of steps on the lower-level problems followed by one step on the upper-level problem, and a differentiable programming strategy that optimizes a smooth approximation of the bilevel problem. Although the first is shown to be a biased gradient method on the problem with rich properties, the second, which is inspired by metalearning applications, is less stable but offers simplicity and ease of implementation. Funding: This research was supported by the Agence Nationale de la Recherche [Grants ANR-19-PI3A-0004 and ANR-23-CE23-0012-01]. J. Bolte, Q.-T. Le, and E. Pauwels thank the AI Interdisciplinary Institute [ANITI funding], the Agence Nationale de la Recherche [France 2030 Program Grant ANR-23-IACL-0002], the Chair TRIAL, and the Air Force Office of Scientific Research [Grant FA8655-22-1-7012]. J. Bolte, E. Pauwels, and S. Vaiter acknowledge support from the ANR MAD. J. Bolte and E. Pauwels acknowledge support from the Agence Nationale de la Recherche [Grant ANR-17-EURE-0010]. Q.-T. Le is supported by the Agence Nationale de la Recherche [Grant ANR-23-IACL-0006]. E. Pauwels acknowledges support from the IUF. S. Vaiter thanks the Agence Nationale de la Recherche [Grant ANR-23-PEIA-0004] and the Chair 3IA BOGL [Grant ANR-23-IACL-0001].

  • Butterfly Factorization with Error Guarantees

    by Quoc-Tung Le, Léon Zheng, Elisa Riccietti, Rémi Gribonval

    In this paper, we investigate the butterfly factorization problem, i.e., the problem of approximating a matrix by a product of sparse and structured factors. We propose a new formal mathematical description of such factors, that encompasses many different variations of butterfly factorization with different choices of the prescribed sparsity patterns. Among these choices we identify those that ensure that the factorization problem admits an optimum, thanks to a new property called “chainability”. For those supports we propose a new butterfly algorithm that yields an approximate solution to the butterfly factorization problem and that is supported by stronger theoretical guarantees than existing factorization methods. Specifically, we show that the ratio of the approximation error by the minimum value is bounded by a constant, independent of the target matrix. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://inria.hal.science/hal-04720713v1 . [Formula: see text]


  • Geometric and computational hardness of bilevel programming

    by Jérôme Bolte, Quốc-Tùng Lê, Edouard Pauwels, Samuel Vaiter


  • Open Access

    Towards Better Bounds for Finding Quasi-Identifiers

    by Ryan Hildebrant, Quoc-Tung Le, Duy-Hoang Ta, Hoa T. Vu

    We revisit the problem of finding small ε-separation keys introduced by Motwani and Xu (2008). In this problem, the input is a data set consisting of m-dimensional tuples {x1,x2,...,xn}. The goal is to find a small subset of coordinates that separates at least (1-ε)(n2) pairs of tuples. When n is large, they provided a fast algorithm that runs on Θ(m/ε) tuples sampled uniformly at random. We show that the sample size can be improved to Θ(m/√ε). Our algorithm also enjoys a faster running time. To obtain this result, we consider a decision problem that takes a subset of coordinates A ⊆ [m]. It rejects if A separates fewer than (1-ε)(n2) pairs of tuples, and accepts if A separates all (n2) pairs of tuples. The algorithm must be correct with probability at least 1-δ for all 2m choices of A. We show that for algorithms based on uniform sampling: - Θ (m/√ε) samples are sufficient and necessary so that δ ≤ e-m. - Ω(√log m/ε) samples are necessary so that δ is a constant. Closing the gap between the upper and lower bounds in this case is still an open question. The analysis is based on a constrained version of the balls-into-bins problem whose worst case can be determined using Karush Kuhn Tucker (KKT) conditions. We believe our analysis may be of independent interest. We also study a related problem that asks for the following sketching algorithm: with given parameters α,k and ε, the algorithm takes a subset of coordinates A of size at most k and returns an estimate of the number of unseparated pairs in A up to a (1±ε) factor if it is at least α (n2). We show that even for constant α and success probability, such a sketching algorithm must use Ømega(mk log ε-1) bits of space; on the other hand, uniform sampling yields a sketch of size Θ (mk/αε2) for this purpose.