Mr Theophile Thiery

Profile

My name is Theophile and I prefer he/him pronouns.

I am a Ph.D. Student in the Combinatorics group and I am very fortunate to have Dr. Justin Ward as my supervisor. I will submit my thesis in April 2023. I am looking for a postdoc position. Feel free to reach out to me.

Research Interests 

My research interests include theoretical computer science, in particular, the development and analysis of algorithms for combinatorial optimization problems that are motivated by theory, data analysis, and machine learning applications. Specifically, my research concerns the design of efficient algorithms with provable guarantees and uses combinatorial insights to meet modern challenges in ML and AI.

As such, two main branches stand out in my research. The first is related to classical combinatorial optimization, the goal of which is to study the computational complexity and the approximability of a given problem. The second is tailored to real-world applications in AI and ML and seeks to explain the success of certain heuristics in practice as well as devising fast and efficient algorithms.

In effect, the frontier between these two axes is imprecise and some of my research projects are hybrid. I enjoy theoretical problems with a twist coming from machine learning applications, whether it is motivated by the growth of modern datasets modeled in theory by "streaming, distributed, and online settings" or by artificial intelligence with the recent development of "learning augmented algorithm".

Bio

I hold a bachelor's degree in Mathematics from EPFL, and a Master's degree in Applied Mathematics from EPFL. From March 2018 until August 2018, I did a research internship at the Zuse Institute Berlin, whose goal was to develop and program an optimality certificate for mixed-integer problem solutions in SCIP.  Since November 2019, I am a postgraduate student (Ph.D.) in QMUL in the School of Mathematical Sciences. This fall, I will be a visiting Ph.D. student in the Combinatorial Optimization and Logistic Group at Bremen Universität. 

Teaching

I am/was a teaching assistant for the following courses:

Queen Mary University of London

• MTH5114 - Linear Programming and Games - 2020/21
• MTH5114 - Linear Programming and Games - 2021/22
• MTH6105 - Algorithmic Graph Theory - 2021/22
• MTH4100/MTH4200 - Calculus I - 2021/22

Ecole Polytechnique Fédérale de Lausanne

• Analysis I 
• Analysis II
• Advanced Linear Algebra
• Discrete Optimization

Research

Research Interests:

Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints — Joint Work with Chien-Chung Huang and Justin Ward — Accepted in APPROX'20 — Arxiv

In this project, we are interested in designing fast algorithms for Submodular Function Maximization. We work in the streaming setting where elements from the dataset arrive one by one in an adversarial order. We show that we can simulate the standard local search algorithms using few passes over the dataset and low memory footprint while preserving the quality of the solution. The family of constraints we consider generalizes both the intersection of p-arbitrary matroid constraints and p-uniform hypergraph matching. Our algorithm improves upon the state-of-the-art result by Chakrabarti and Kale [paper] and applies to non-monotone functions as well.

Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression —  Joint Work: with Justin Ward — Accepted in COLT'22 — Arxiv

Given a variable of interest, we would like to find the best linear predictor for it by choosing a subset of k relevant variables obeying a matroid constraint. This problem is a natural generalization of subset selection problems where it is necessary to spread observations amongst multiple different classes. We derive new and strengthened guarantees for this problem by improving the analysis of the Residual Random Greedy and by developing a novel distorted local search. Our algorithms have optimal asymptotic guarantees.
The central piece of our work is the introduction of a novel data-dependent parameter extending  Das and Kempe's definition [paper]. In the regression problem, this parameter is connected to the minimum k-sparse eigenvalue of the covariance matrix. We obtain similar results that Bayesian A-optimal Design and Column Subset Selection leading to new guarantees for these problems as well.

Improved Approximation Algorithm for Weighted k-Set Packing — Joint work with Justin Ward — Accepted in SODA'23

We consider a fundamental combinatorial optimization problem: Weighted k-Set Packing. We are given a collection of weighted sets, each with at most k elements, and must return a collection of pairwise disjoint sets with maximum total weight. For k = 3, this problem generalizes the classical 3-dimensional matching problem listed as one of Karp's original 21 NP-complete problems. We give an algorithm attaining an approximation factor of √3 = 1.732... for 3-set packing, and asymptotically approaching k/2. For k = 3, it improves upon the 1.9999998 approximation factor due to Neuwohner [paper]. At the heart of the proof is a new and extended analysis of Berman's algorithm for large exchanges.

Publications

• Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints — Joint Work with Chien-Chung Huang and Justin Ward — Accepted in APPROX'20 — Arxiv version
• Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression —  Joint Work: with Justin Ward — Accepted in COLT'22 — Arxiv version
• Improved Approximation Algorithm for Weighted k-Set Packing — Joint work with Justin Ward — Accepted in SODA'23