Department of Mathematics of Data Science (SB/IC)

Laboratory

Related publications (34)

Binary Perceptron: Efficient Algorithms Can Find Solutions in a RareWell-Connected Cluster

Emmanuel Abbé

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

On Codes Decoding a Constant Fraction of Errors on the BSC

Jan Hazla

We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding on the BEC. We conclude that a linear code that is successful on the BEC can also decode over a range of binary memoryless symmetric (BMS) channels. In particular, applying the result of Kudekar, Kumar, Mondelli, Pfister, Sasoglu and Urbanke from STOC 2016, we prove that a Reed-Muller code of positive rate R decodes errors on the BSC (p) with high probability if p < 1/2 - root 2(-R)(1 - 2(-R)).

ASSOC COMPUTING MACHINERY2021

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

Bayesian Decision Making in Groups is Hard

Jan Hazla

We study the computations that Bayesian agents undertake when exchanging opinions over a network. The agents act repeatedly on their private information and take myopic actions that maximize their expected utility according to a fully rational posterior belief. We show that such computations are NP-hard for two natural utility functions: one with binary actions and another where agents reveal their posterior beliefs. In fact, we show that distinguishing between posteriors that are concentrated on different states of the world is NP-hard. Therefore, even approximating the Bayesian posterior beliefs is hard. We also describe a natural search algorithm to compute agents' actions, which we call elimination of impossible signals, and show that if the network is transitive, the algorithm can be modified to run in polynomial time.

INFORMS2021

We consider two problems regarding arithmetic progressions in symmetric sets in the finite field (product space) model. First, we show that a symmetric set S subset of Z(q)(n) containing vertical bar S vertical bar = mu . q(n) elements must contain at least delta(q, mu) . q(n) . 2(n) arithmetic progressions x, x+d, . . . , x+(q - 1).d such that the difference d is restricted to lie in {0, 1}(n). Second, we show that for prime p a symmetric set S subset of F-p(n) with vertical bar S vertical bar = mu . p(n) elements contains at least mu(C(p)) . p(2n) arithmetic progressions of length p. This establishes that the qualitative behavior of longer arithmetic progressions in symmetric sets is the same as for progressions of length three.

ELECTRONIC JOURNAL OF COMBINATORICS2020

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

The probability of intransitivity in dice and close elections

Jan Hazla

We study the phenomenon of intransitivity in models of dice and voting. First, we follow a recent thread of research for n-sided dice with pairwise ordering induced by the probability, relative to 1/2, that a throw from one die is higher than the other. We build on a recent result of Polymath showing that three dice with i.i.d. faces drawn from the uniform distribution on {1,…,n} and conditioned on the average of faces equal to (n+1)/2 are intransitive with asymptotic probability 1/4. We show that if dice faces are drawn from a non-uniform continuous mean zero distribution conditioned on the average of faces equal to 0, then three dice are transitive with high probability. We also extend our results to stationary Gaussian dice, whose faces, for example, can be the fractional Brownian increments with Hurst index H∈(0,1). Second, we pose an analogous model in the context of Condorcet voting. We consider n voters who rank k alternatives independently and uniformly at random. The winner between each two alternatives is decided by a majority vote based on the preferences. We show that in this model, if all pairwise elections are close to tied, then the asymptotic probability of obtaining any tournament on the k alternatives is equal to 2−k(k−1)/2, which markedly differs from known results in the model without conditioning. We also explore the Condorcet voting model where methods other than simple majority are used for pairwise elections. We investigate some natural definitions of “close to tied” for general functions and exhibit an example where the distribution over tournaments is not uniform under those definitions.

2020

System and method for decoding reed-muller codes

Emmanuel Abbé, Min Ye

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

Recursive Projection-Aggregation Decoding of Reed-Muller Codes

Emmanuel Abbé, Min Ye

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

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