Concentration to Zero Bit-Error Probability for Regular LDPC Codes on the Binary Symmetric Channel: Proof by Loop Calculus. Marc Vuffray and Theodor Misiakiewicz. 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton, 2015).
Efficient reconstruction of transmission probabilities in a spreading process from partial observations. Andrey Y Lokhov and Theodor Misiakiewicz. Submitted.
High-dimensional model selection of Graphical Models. The goal of this project is to study model selection from i.i.d. samples in the high-dimensional regime (when the number of available samples is far lesser...). In particular, we are trying to understand the relation between incoherence condition (usual assumption in this setting), sparsistency and tresholding, and the consequences on learning a graphical model. For example, it was shown by Vuffray and al. that efficient algorithms for learning Ising models can be found without any assumption if the sparsistency condition is removed. An other application is the Gaussian models where we suggest an algorithm that achieves information-theoretic lower-bound without extra-dependencies on the parameters of the precision matrix.
D-Wave 2X as an efficient sampler. D-Wave 2X is a quantum computer produced by D-Wave Systems, operating a 1152-qubit chip and designed to solve optimization problems using quantum annealing. It was purchased by Los Alamos National Laboratory in 2016 (one of the three in the world). I was included in the first efforts of the laboratory to study the machine (2-days training on how to operate the machine and how to design performance measures). The aim of the project was to explore the possibility to use the imperfections of D-Wave (hardware noise, imperfect annealing) to efficiently sample from a Boltzmann distribution (difficult task in general, that has a lot of applications). The team consisted of M. Chertkov, A. Hagberg, A. Lokhov, S. Misra and M. Vuffray.
Designing performance criterions for general code ensembles and communication channels. The goal of this work is to propose general criterions for designing new efficient code ensembles over general communication channels. These criterions are based on graph-topology considerations and are tight with respect to the Bit-Error probability. We also propose a general method to approximate these criterions using the Bethe approximation and Loop series.
Non-convex optimization using noisy gradient descent. We are trying to give better complexity bounds.
Localization of saddle points for SDP problems and complexity bounds. This work studies SDPs in the case of large-scale systems when only an approximate solution is needed (using the rank-restricted non-convex surrogate k-SDP introduced by Burer and Monteiro). We use structural information on the saddle points in order to give an upper-bound on the complexity of the Trust-Region method in the case of Max-Cut, Z2 synchronization and Orthogonal-cut.
Fast algorithms for high-dimensional statistical estimation of Ising Models. The Ising Model corresponds to the simplest instance of a Graphical Model, namely a distribution of binary variables with pairwise interactions represented by a dependency graph. As such, it is often used as a first step to model complex interacting systems. We consider the problem of learning the underlying graph of an unknown Ising Model from i.i.d. samples, whose applications range from gene expression, protein interaction to image processing. In particular, we will focus on the high-dimensional regime, where the number of available data is much smaller than the number of variables. The best available estimator, the newly introduced Interaction Screening Estimator with a l1 regularization, is known to achieve the sample information-theoretic lower-bound. We investigate fast implementations of this convex estimator. We present numerical results as long as theoretical garantees for the composite gradient descent introduced by Nesterov for solving partially non smooth problems. We show that it attains a geometric convergence rate even in the high-dimensional setting where the Hessian is highly degenerate. We present also two other algorithms based on the Alternating Direction Method of Multipliers (ADMM) and the Generalized Approximate Message Passing (GAMP).
Efficient and robust learning of spreading processes on graphs. We investigate the problem of learning the parameters of a spreading process on a graph from data. In particular we are interested in methods that are efficient for large scale systems and that are robust with respect to the presence of noise and partial observations. The solution we propose is using the dynamic message-passing equations to approximate the marginal probabilities of the distribution.
Estimation du bruit de fond réductible par la méthode SS dans le canal de désintégration du boson de Higgs en 4 leptons (in French), Reductible noise estimation of the Higgs in 4 leptons decay channel using SS method. Graduate work under the supervision of Christophe Ochando, Leprince-Ringuet Laboratory, CNRS, Ecole Polytechnique and CMS collaboration, CERN. I participated in the analysis of the Data gathered during the year 2015 by the Compact Muon Solenoid (CMS) experiment at the Large Hadron Collider (LHC), CERN, Geneva. I studied the reductible noise (experimental noise) of the decay channel of the Higgs in 4 leptons. This work was included in the CMS collaboration report Measurement of the properties of a higgs boson in the four-lepton canal state at 13 tev (March 2016). The final results of the 2015 analysis can be found in Studies of higgs boson production in the four-lepton canal state at 13tev, March 2016.
Application of Graphical Models to Decoding and Machine Learning (in English). Undergraduate work under the supervision of Michael Chertkov at Center for Non-Linear Studies, Los Alamos National Laboratory, NM, USA. The aim of this internship was to understand the role of graphical models as a common underlying framework for statistical physics, computation and information theory. I investigated several tools that are widely used in different fields (message-passing algorithms, max-product, linear programming, expectation propagation). I present in this report three of the works I did during my stay. The first one presents a proof using loop calculus to show concentration to zero of the bit-error probability for regular LDPC codes on the Binary Symmetric Channel. The second one focus on a novel algorithm based on the Dynamic Message Passing equations, to efficiently reconstruct the transmission probabilities in a spreading process from partial observations. The third one introduces an original estimator to solve the inverse Ising problem using a convex objective, called Interaction Screening estimator. This work was later continued by Vuffray and al. (http://arxiv.org/pdf/1605.07252.pdf) in the high-dimensional case with a lasso regularization.
Ondes gravitationnelles en théorie de la gravité massive (in French), Gravitational waves in Massive Gravity Theories. Undergraduate work under the supervision of Daniele Steer. The first part presents the ADM formulation of General Relativity and the Dirac procedure to derive the constraints algebra of a classical Hamiltonian. The second part investigates the construction of coherent classical field theories for General Relativity with massive gravitons. The final part derives theoretical constraints that might be achieved on the mass of the graviton with the LIGO and VIRGO experiments. This is done by measuring the shift in the gravitational waves produced by a compact binary system (exactly the signal that was measured in October 2015, leading to the first experimental evidence of gravitational waves !!!).