Publications

2024

1. Conference

   Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression

   Lucas Clarté, Adrien Vandenbroucque, Guillaume Dalle, and 3 more authors

   In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, 2024

   Abs DOI Bib PDF Code

   

   We investigate popular resampling methods for estimating the uncertainty of statistical models, such as subsampling, bootstrap and the jackknife, and their performance in high-dimensional supervised regression tasks. We provide a tight asymptotic description of the biases and variances estimated by these methods in the context of generalized linear models, such as ridge and logistic regression, taking the limit where the number of samples n and dimension d of the covariates grow at a comparable rate: α=n/d fixed. Our findings are three-fold: i) resampling methods are fraught with problems in high dimensions and exhibit the double-descent-like behavior typical of these situations; ii) only when αis large enough do they provide consistent and reliable error estimations (we give convergence rates); iii) in the over-parametrized regime α<1 relevant to modern machine learning practice, their predictions are not consistent, even with optimal regularization.

   @inproceedings{pmlr-v244-clarte24a,
     title = {Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression},
     author = {Clart\'e, Lucas and Vandenbroucque, Adrien and Dalle, Guillaume and Loureiro, Bruno and Krzakala, Florent and Zdeborov\'a, Lenka},
     booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence},
     pages = {787--819},
     year = {2024},
     editor = {Kiyavash, Negar and Mooij, Joris M.},
     volume = {244},
     series = {Proceedings of Machine Learning Research},
     publisher = {PMLR},
     doi = {10.5555/3702676.3702714},
     url = {https://proceedings.mlr.press/v244/clarte24a.html},
   }

2. Journal

   Lower Bounds on the Bayesian Risk via Information Measures

   Amedeo Roberto Esposito, Adrien Vandenbroucque, and Michael Gastpar

   Journal of Machine Learning Research, 2024

   Abs DOI Bib

   

   This paper focuses on parameter estimation and introduces a new method for lower bounding the Bayesian risk. The method allows for the use of virtually any information measure, including Rényi’s α, φ-Divergences, and Sibson’s α-Mutual Information. The approach considers divergences as functionals of measures and exploits the duality between spaces of measures and spaces of functions. In particular, we show that one can lower bound the risk with any information measure by upper bounding its dual via Markov’s inequality. We are thus able to provide estimator-independent impossibility results thanks to the Data-Processing Inequalities that divergences satisfy. The results are then applied to settings of interest involving both discrete and continuous parameters, including the “Hide-and-Seek” problem, and compared to the state-of-the-art techniques. An important observation is that the behaviour of the lower bound in the number of samples is influenced by the choice of the information measure. We leverage this by introducing a new divergence inspired by the “Hockey-Stick” Divergence, which is demonstrated empirically to provide the largest lower-bound across all considered settings. If the observations are subject to privatisation, stronger impossibility results can be obtained via Strong Data-Processing Inequalities. The paper also discusses some generalisations and alternative directions.

   @article{JMLR:v25:23-0361,
     author = {Esposito, Amedeo Roberto and Vandenbroucque, Adrien and Gastpar, Michael},
     title = {Lower Bounds on the Bayesian Risk via Information Measures},
     journal = {Journal of Machine Learning Research},
     year = {2024},
     volume = {25},
     number = {340},
     pages = {1--45},
     url = {http://jmlr.org/papers/v25/23-0361.html},
     doi = {10.5555/3722577.3722917},
   }

2023

1. Patent

   Methods and systems for optimization problem transformation for facilitated resolution

   Adrien Vandenbroucque and Ewan Munro

   2023

   Abs Bib HTML

   Methods and system for transformation of an optimization problems to facilitate its resolution are provided. According to at least one aspect of the present embodiments, a method includes casting the optimization problem into a quadratic unconstrained binary model and transforming the optimization problem into an optimization problem in the same model but with reduced connectivity. Transforming the optimization problem into the optimization problem with reduced connectivity includes partitioning decision variables in the quadratic unconstrained binary model into two or more groups, each of the two or more groups comprising at least one decision variable node and introducing a register variable node between adjacent pairs of the at least one decision variable node in the two or more groups to hold partial values of a sum in a linear constraint to form the optimization problem with reduced connectivity.

   @patent{vandenbroucque2023patent,
     title = {Methods and systems for optimization problem transformation for facilitated resolution},
     author = {Vandenbroucque, Adrien and Munro, Ewan},
     year = {2023},
     number = {WO2023140794A3},
     url = {https://patents.google.com/patent/WO2023140794A3/en},
   }

2022

1. Conference

   On Sibson’s α-Mutual Information

   Amedeo Roberto Esposito, Adrien Vandenbroucque, and Michael Gastpar

   In 2022 IEEE International Symposium on Information Theory (ISIT), 2022

   Abs DOI Bib HTML

   

   We explore a family of information measures that stems from Rényi’s α-Divergences with α < 0. In particular, we extend the definition of Sibson’s α-Mutual Information to negative values of α and show several properties of these objects. Moreover, we highlight how this family of information measures is related to functional inequalities that can be employed in a variety of fields, including lower-bounds on the Risk in Bayesian Estimation Procedures.

   @inproceedings{9834428,
     author = {Esposito, Amedeo Roberto and Vandenbroucque, Adrien and Gastpar, Michael},
     booktitle = {2022 IEEE International Symposium on Information Theory (ISIT)},
     title = {On Sibson’s α-Mutual Information},
     year = {2022},
     volume = {},
     number = {},
     pages = {2904-2909},
     keywords = {Atmospheric measurements;Estimation;Particle measurements;Bayes methods;Information theory;Rényi-Divergence;Sibson’s Mutual Information;Information Measures;Bayesian Risk;Estimation},
     doi = {10.1109/ISIT50566.2022.9834428},
     url = {https://ieeexplore.ieee.org/document/9834428},
   }

2. Preprint

   The Houdayer Algorithm: Overview, Extensions, and Applications

   Adrien Vandenbroucque, Ezequiel Ignacio Rodríguez Chiacchio, and Ewan Munro

   2022

   Abs Bib HTML

   

   The study of spin systems with disorder and frustration is known to be a computationally hard task. Standard heuristics developed for optimizing and sampling from general Ising Hamiltonians tend to produce correlated solutions due to their locality, resulting in a suboptimal exploration of the search space. To mitigate these effects, cluster Monte-Carlo methods are often employed as they provide ways to perform non-local transformations on the system. In this work, we investigate the Houdayer algorithm, a cluster Monte-Carlo method with small numerical overhead which improves the exploration of configurations by preserving the energy of the system. We propose a generalization capable of reaching exponentially many configurations at the same energy, while offering a high level of adaptability to ensure that no biased choice is made. We discuss its applicability in various contexts, including Markov chain Monte-Carlo sampling and as part of a genetic algorithm. The performance of our generalization in these settings is illustrated by sampling for the Ising model across different graph connectivities and by solving instances of well-known binary optimization problems. We expect our results to be of theoretical and practical relevance in the study of spin glasses but also more broadly in discrete optimization, where a multitude of problems follow the structure of Ising spin systems.

   @misc{vandenbroucque2022houdayeralgorithmoverviewextensions,
     title = {The Houdayer Algorithm: Overview, Extensions, and Applications},
     author = {Vandenbroucque, Adrien and Chiacchio, Ezequiel Ignacio Rodríguez and Munro, Ewan},
     year = {2022},
     eprint = {2211.11556},
     archiveprefix = {arXiv},
     primaryclass = {cond-mat.dis-nn},
     url = {https://arxiv.org/abs/2211.11556},
   }

3. Conference

   Lower-bounds on the Bayesian Risk in Estimation Procedures via f–Divergences

   Adrien Vandenbroucque, Amedeo Roberto Esposito, and Michael Gastpar

   In 2022 IEEE International Symposium on Information Theory (ISIT), 2022

   Abs DOI Bib HTML Code

   

   We consider the problem of parameter estimation in a Bayesian setting and propose a general lower-bound that includes part of the family of f-Divergences. The results are then applied to specific settings of interest and compared to other notable results in the literature. In particular, we show that the known bounds using Mutual Information can be improved by using, for example, Maximal Leakage, Hellinger divergence, or generalizations of the Hockey-Stick divergence.

   @inproceedings{9834708,
     author = {Vandenbroucque, Adrien and Esposito, Amedeo Roberto and Gastpar, Michael},
     booktitle = {2022 IEEE International Symposium on Information Theory (ISIT)},
     title = {Lower-bounds on the Bayesian Risk in Estimation Procedures via f–Divergences},
     year = {2022},
     volume = {},
     number = {},
     pages = {1106-1111},
     url = {https://ieeexplore.ieee.org/document/9834708},
     keywords = {Parameter estimation;Atmospheric measurements;Estimation;Particle measurements;Bayes methods;Mutual information;Bayesian Risk;Parameter Estimation;Information Measures;f−Divergences;Mutual Information;Hockey-Stick Divergence},
     doi = {10.1109/ISIT50566.2022.9834708},
   }

2021

1. Master’s Thesis

   A Dive into Cluster Monte-Carlo Algorithms: A Quantum-Inspired Approach

   Adrien Vandenbroucque

   École Polytechnique Fédérale de Lausanne, 2021

   Abs Bib PDF

   Many discrete optimization problems can be mapped onto Ising spin-glass models, which gives a general framework to solve them. However, it is well-known that such systems can be hard to study, especially when frustration is present, with most results coming from numerical simulations. It has been shown that cluster Monte-Carlo algorithms are particularly efficient for simulating ferromagnetic Ising models, but results on more generic statistical mechanical models are not conclusive. Here we compare multiple of these algorithms and dive deeper into the analysis of the Houdayer algorithm, leading to an improved version which can yield better convergence to equilibrium. We also argue that this proposed method can be used to improve the sampling of optimal solutions when many of them exist, and this can be further tweaked to allow for better sampling of feasible solutions in constrained problems. We illustrate the various benefits of using our extended cluster move through experiments involving multiple graph topologies, in particular we look at a discrete optimization problem arising from industry.

   @mastersthesis{vandenbroucque2021thesis,
     author = {Vandenbroucque, Adrien},
     title = {A Dive into Cluster Monte-Carlo Algorithms: A Quantum-Inspired Approach},
     school = {École Polytechnique Fédérale de Lausanne},
     year = {2021},
     url = {adrienvdb.com/assets/master_thesis_adrien_vandenbroucque.pdf},
   }

2019

1. Semester Project

   On Quantum Algorithms for Solving Linear Systems of Equations

   Adrien Vandenbroucque

   2019

   Bib PDF Code

   @techreport{vandenbroucque2019semesterproject,
     author = {Vandenbroucque, Adrien},
     title = {On Quantum Algorithms for Solving Linear Systems of Equations},
     institution = {École Polytechnique Fédérale de Lausanne},
     year = {2019},
     url = {adrienvdb.com/assets/pdf/master_semester_project.pdf},
   }