Publications

Cross-layer communication over fading channels with adaptive decision feedback

Borna Sayedana

Aditya Mahajan

E. Yeh

In this paper, cross-layer design of transmitting data packets over AWGN fading channel with adaptive decision feedback is considered. The t… (see more)ransmitter decides the number of packets to transmit and the threshold of the decision feedback based on the queue length and the channel state. The transmit power is chosen such that the probability of error is below a pre-specified threshold. We model the system as a Markov decision process and use ideas from lattice theory to establish qualitative properties of optimal transmission strategies. In particular, we show that: (i) if the channel state remains the same and the number of packets in the queue increase, then the optimal policy either transmits more packets or uses a smaller decision feedback threshold or both; and (ii) if the number of packets in the queue remain the same and the channel quality deteriorates, then the optimal policy either transmits fewer packets or uses a larger threshold for the decision feedback or both. We also show under rate constraints that if the channel gains for all channel states are above a threshold, then the “or” in the above characterization can be replaced by “and”. Finally, we present a numerical example showing that adaptive decision feedback significantly improves the power-delay trade-off as compared with the case of no feedback.

2020-01-01

WiOpt (published)

dblp.uni-trier.de

Differentiable Causal Discovery from Interventional Data

Philippe Brouillard

Sébastien Lachapelle

Alexandre Lacoste

Alexandre Drouin

Discovering causal relationships in data is a challenging task that involves solving a combinatorial problem for which the solution is not a… (see more)lways identifiable. A new line of work reformulates the combinatorial problem as a continuous constrained optimization one, enabling the use of different powerful optimization techniques. However, methods based on this idea do not yet make use of interventional data, which can significantly alleviate identifiability issues. In this work, we propose a neural network-based method for this task that can leverage interventional data. We illustrate the flexibility of the continuous-constrained framework by taking advantage of expressive neural architectures such as normalizing flows. We show that our approach compares favorably to the state of the art in a variety of settings, including perfect and imperfect interventions for which the targeted nodes may even be unknown.

A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms

Philip Amortila

Doina Precup

Prakash Panangaden

Marc Gendron-Bellemare

2020-01-01

AISTATS (published)

Divergent protein-coding genes and brain size in primates

Malesys Bourgeron Dumas

Guillaume Dumas

Simon Malesys

Thomas Bourgeron

17 The human brain differs from that of other primates, but the genetic basis of these differences 18 remains unclear. We investigated the e… (see more)volutionary pressures acting on almost all human 19 protein-coding genes ( N =11,667; 1:1 orthologs in primates) on the basis of their divergence 20 from those of early hominins, such as Neanderthals, and non-human primates. We confirm 21 that genes encoding brain-related proteins are among the most strongly conserved protein- 22 coding genes in the human genome. Combining our evolutionary pressure metrics for the 23 protein-coding genome with recent datasets, we found that this conservation applied to genes 24 functionally associated with the synapse and expressed in brain structures such as the 25 prefrontal cortex and the cerebellum. Conversely, several of the protein-coding genes that 26 diverge most in hominins relative to other primates are associated with brain-associated 27 diseases, such as micro/macrocephaly, dyslexia, and autism. We also showed that cerebellum 28 granule neurons express a set of divergent protein-coding genes that may have contributed to 29 the emergence of fine motor skills and social cognition in humans. This resource is available 30 from http://neanderthal.pasteur.fr and can be used to estimate evolutionary constraints acting 31 on a set of genes and to explore their relative contributions to human traits. 32

2020-01-01

(published)

Electric Vehicles Equilibrium Model that Considers Queue Delay and Mixed Traffic

Nurit Oliker

Miguel F. Anjos

Margarida Carvalho

Emma Frejinger

Bernard Gendron

This study develops an equilibrium model for electric vehicles (EVs) that considers both queue delays in charging stations and flow dependen… (see more)t travel times. This is a user equilibrium model that accounts for travel, charging and queuing time in the path choice modelling of EVs and the complementary traffic. Waiting and service times in charging stations are represented by an m/m/k queuing system. The model considers multiple vehicle and driver classes, expressing different battery capacity, initial charge state and range anxiety level. Feasible paths are found for multiple classes given their limited travel range. A numerical application exemplifies the limitations of EVs assignment and their impact on flow distribution.

2020-01-01

(published)

Expressiveness and Learning of Hidden Quantum Markov Models

Sandesh M. Adhikary

Siddarth Srinivasan

Geoff Gordon

Byron Boots

Extending classical probabilistic reasoning using the quantum mechanical view of probability has been of recent interest, particularly in th… (see more)e development of hidden quantum Markov models (HQMMs) to model stochastic processes. However, there has been little progress in characterizing the expressiveness of such models and learning them from data. We tackle these problems by showing that HQMMs are a special subclass of the general class of observable operator models (OOMs) that do not suffer from the \emph{negative probability problem} by design. We also provide a feasible retraction-based learning algorithm for HQMMs using constrained gradient descent on the Stiefel manifold of model parameters. We demonstrate that this approach is faster and scales to larger models than previous learning algorithms.

2020-01-01

AISTATS (published)

Fairness in Kidney Exchange Programs through Optimal Solutions Enumeration

Golnoosh Farnadi

Behrouz Babaki

Margarida Carvalho

Not all patients who need kidney transplant can find a donor with compatible characteristics. Kidney exchange programs (KEPs) seek to match … (see more)such incompatible patient-donor pairs together, usually with the objective of maximizing the total number of transplants. We propose a randomized policy for selecting an optimal solution in which patients’ equity of opportunity to receive a transplant is promoted. Our approach gives rise to the problem of enumerating all optimal solutions, which we tackle using a hybrid of constraint programming and linear programming. We empirically demonstrate the advantages of our proposed method over the common practice of using the first optimal solution obtained by a solver.

2020-01-01

(published)

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation

Si Yi Meng

Sharan Vaswani

Issam Hadj Laradji

Mark Schmidt

We consider stochastic second-order methods for minimizing smooth and strongly-convex functions under an interpolation condition satisfied b… (see more)y over-parameterized models. Under this condition, we show that the regularized subsampled Newton method (R-SSN) achieves global linear convergence with an adaptive step-size and a constant batch-size. By growing the batch size for both the subsampled gradient and Hessian, we show that R-SSN can converge at a quadratic rate in a local neighbourhood of the solution. We also show that R-SSN attains local linear convergence for the family of self-concordant functions. Furthermore, we analyze stochastic BFGS algorithms in the interpolation setting and prove their global linear convergence. We empirically evaluate stochastic L-BFGS and a "Hessian-free" implementation of R-SSN for binary classification on synthetic, linearly-separable datasets and real datasets under a kernel mapping. Our experimental results demonstrate the fast convergence of these methods, both in terms of the number of iterations and wall-clock time.

2020-01-01

AISTATS (published)

GAIT: A Geometric Approach to Information Theory

Jose Gallego-Posada

Ankit Vani

Max Schwarzer

We advocate the use of a notion of entropy that reflects the relative abundances of the symbols in an alphabet, as well as the similarities … (see more)between them. This concept was originally introduced in theoretical ecology to study the diversity of ecosystems. Based on this notion of entropy, we introduce geometry-aware counterparts for several concepts and theorems in information theory. Notably, our proposed divergence exhibits performance on par with state-of-the-art methods based on the Wasserstein distance, but enjoys a closed-form expression that can be computed efficiently. We demonstrate the versatility of our method via experiments on a broad range of domains: training generative models, computing image barycenters, approximating empirical measures and counting modes.

2020-01-01

AISTATS (published)

How to make your optimizer generalize better

Sharan Vaswani

Reza Babenzhad

Sait AI Lab

Montreal.

Jose Gallego

Aaron Mishkin

Nicolas Le Roux

We study the implicit regularization of optimization methods for linear models interpolating the training data in the under-parametrized and… (see more) over-parametrized regimes. For over-parameterized linear regression, where there are inﬁnitely many interpolating solutions, different optimization methods can converge to solutions with varying generalization performance. In this setting, we show that projections onto linear spans can be used to move between solutions. Furthermore, via a simple reparameterization, we can ensure that an arbitrary optimizer converges to the minimum (cid:96) 2 -norm solution with favourable generalization properties. For under-parameterized linear clas-siﬁcation, optimizers can converge to different decision boundaries separating the data. We prove that for any such classiﬁer, there exists a family of quadratic norms (cid:107)·(cid:107) P such that the classiﬁer’s direction is the same as that of the maximum P -margin solution. We argue that analyzing convergence to the standard maximum (cid:96) 2 -margin is arbitrary and show that minimizing the norm induced by the data can result in better generalization. We validate our theoretical results via experiments on synthetic and real datasets.

2020-01-01

(published)