It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in finding solutions at low density. This phenomenon has been justified numerically by the existence of subdominant and dense connected regions of solutions, which are accessible by simple learning algorithms. In this paper, we establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons. We show that at low constraint density (equivalently for overparametrized perceptrons), there exists indeed a subdominant connected cluster of solutions with almost maximal diameter, and that an efficient multiscale majority algorithm can find solutions in such a cluster with high probability, settling in particular an open problem posed by Perkins-Xu in STOC'21. In addition, even close to the critical threshold, we show that there exist clusters of linear diameter for the symmetric perceptron, as well as for the asymmetric perceptron under additional assumptions.

ASSOC COMPUTING MACHINERY2022

Chargement

Predicting future myocardial infarction from angiographies with deep learning

Emmanuel Abbé, Farhang Aminfar, Nicolas Dayer, Stéphane Fournier, Pascal Frossard, David Meier, Olivier Muller, Omar Raita, Ortal Yona Senouf

In patients with stable Coronary Artery Disease (CAD), the identification of lesions which will be responsible of a myocardial infarction (MI) during follow-up remains a daily challenge. In this work, we propose to predict culprit stenosis by applying a deep learning framework on image stenosis obtained from patient data. Preliminary results on a data set of 746 lesions obtained from angiographies confirm that deep learning can indeed achieve significant predictive performance, and even outperforms the one achieved by a group of interventional cardiologists. To the best of our knowledge, this is the first work that leverages the power of deep learning to predict MI from coronary angiograms, and it opens new doors towards predicting MI using data-driven algorithms.

2021

Chargement

We derive generalization and excess risk bounds for neural networks using a family of complexity measures based on a multilevel relative entropy. The bounds are obtained by introducing the notion of generated hierarchical coverings of neural networks and by using the technique of chaining mutual information introduced by Asadi et al. '18. The resulting bounds are algorithm-dependent and multiscale: they exploit the multilevel structure of neural networks. This, in turn, leads to an empirical risk minimization problem with a multilevel entropic regularization. The minimization problem is resolved by introducing a multiscale extension of the celebrated Gibbs posterior distribution, proving that the derived distribution achieves the unique minimum. This leads to a new training procedure for neural networks with performance guarantees, which exploits the chain rule of relative entropy rather than the chain rule of derivatives (as in backpropagation), and which takes into account the interactions between different scales of the hypothesis sets of neural networks corresponding to different depths of the hidden layers. To obtain an efficient implementation of the latter, we further develop a multilevel Metropolis algorithm simulating the multiscale Gibbs distribution, with an experiment for a two-layer neural network on the MNIST data set.

MICROTOME PUBL2020

Chargement

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Chargement

Various embodiments are directed to Reed-Muller decoding systems and methods based on recursive projections and aggregations of cosets decoding, exploiting the self-similarity of RM codes, and extended with list-decoding procedures and with outer-code concatenations

2020

Chargement

This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw connections between such entropic matroids and secret-sharing matroids and show that entropic matroids are linear matroids when p=2,3 but not when p=9. Our results leave open the possibility for p-entropic matroids to be linear whenever p is prime, with particular cases proved here. Applications of entropic matroids to coding theory and cryptography are also discussed.

2019

Chargement

Reed-Muller codes polarize

Emmanuel Abbé, Min Ye

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix Gm = [1?] "' but using different subset of rows. RM codes select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in Gm; while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Ankan to show that the conditional mutual information polarizes, and this gives directly a capacity-achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this paper, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-to-down but from the lightest to the heaviest rows in Gm, the conditional mutual information again polarizes. We further demonstrate that it does so faster than for polar codes. This implies that Gm contains another code, different than the polar code and called here the twin-RM code, that is provably capacityachieving on any symmetric channel. This gives in particular a necessary condition for RM codes to achieve capacity on symmetric channels. It further gives a sufficient condition if the rows with largest conditional mutual information correspond to the heaviest rows, i.e., if the twin-RM code is the RM code. We demonstrate here that the two codes are at least similar and give further evidence that they are indeed the same.

IEEE COMPUTER SOC2019

Chargement

Subadditivity Beyond Trees and the Chi-Squared Mutual Information

Emmanuel Abbé

Evans et al. [1] proved the subadditivity of the mutual information in the broadcasting on tree model with binary vertex labels and symmetric edge channels. They raised the question of whether such subadditivity extends to loopy graphs in some appropriate way. We propose here such a generalization for general graphs and binary vertex labels. With enough channel symmetry, the generalization applies to arbitrary graphs, and with partial symmetry, it applies to series-parallel graphs. The results are obtained using the Chi-squared mutual information rather than the classical KL-mutual information (for which some of our bounds do not hold). Various properties of the Chi-squared mutual information are discussed.

IEEE2019

Chargement