Publications

Learning with Gradient Descent and Weakly Convex Losses

Dominic Richards

Michael G. Rabbat

We study the learning performance of gradient descent when the empirical risk is weakly convex, namely, the smallest negative eigenvalue of … (see more)the empirical risk's Hessian is bounded in magnitude. By showing that this eigenvalue can control the stability of gradient descent, generalisation error bounds are proven that hold under a wider range of step sizes compared to previous work. Out of sample guarantees are then achieved by decomposing the test error into generalisation, optimisation and approximation errors, each of which can be bounded and traded off with respect to algorithmic parameters, sample size and magnitude of this eigenvalue. In the case of a two layer neural network, we demonstrate that the empirical risk can satisfy a notion of local weak convexity, specifically, the Hessian's smallest eigenvalue during training can be controlled by the normalisation of the layers, i.e., network scaling. This allows test error guarantees to then be achieved when the population risk minimiser satisfies a complexity assumption. By trading off the network complexity and scaling, insights are gained into the implicit bias of neural network scaling, which are further supported by experimental findings.

2021-03-17

Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (published)

proceedings.mlr.press

Quantum Tensor Networks, Stochastic Processes, and Weighted Automata

Siddarth Srinivasan

Sandesh Adhikary

Jacob Miller

Guillaume Rabusseau

Byron Boots

Modeling joint probability distributions over sequences has been studied from many perspectives. The physics community developed matrix prod… (see more)uct states, a tensor-train decomposition for probabilistic modeling, motivated by the need to tractably model many-body systems. But similar models have also been studied in the stochastic processes and weighted automata literature, with little work on how these bodies of work relate to each other. We address this gap by showing how stationary or uniform versions of popular quantum tensor network models have equivalent representations in the stochastic processes and weighted automata literature, in the limit of infinitely long sequences. We demonstrate several equivalence results between models used in these three communities: (i) uniform variants of matrix product states, Born machines and locally purified states from the quantum tensor networks literature, (ii) predictive state representations, hidden Markov models, norm-observable operator models and hidden quantum Markov models from the stochastic process literature,and (iii) stochastic weighted automata, probabilistic automata and quadratic automata from the formal languages literature. Such connections may open the door for results and methods developed in one area to be applied in another.

2021-03-17

Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (published)

doi.org

proceedings.mlr.press

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence

We propose a stochastic variant of the classical Polyak step-size (Polyak, 1987) commonly used in the subgradient method. Although computing… (see more) the Polyak step-size requires knowledge of the optimal function values, this information is readily available for typical modern machine learning applications. Consequently, the proposed stochastic Polyak step-size (SPS) is an attractive choice for setting the learning rate for stochastic gradient descent (SGD). We provide theoretical convergence guarantees for SGD equipped with SPS in different settings, including strongly convex, convex and non-convex functions. Furthermore, our analysis results in novel convergence guarantees for SGD with a constant step-size. We show that SPS is particularly effective when training over-parameterized models capable of interpolating the training data. In this setting, we prove that SPS enables SGD to converge to the true solution at a fast rate without requiring the knowledge of any problem-dependent constants or additional computational overhead. We experimentally validate our theoretical results via extensive experiments on synthetic and real datasets. We demonstrate the strong performance of SGD with SPS compared to state-of-the-art optimization methods when training over-parameterized models.

2021-03-17

Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (published)

doi.org

proceedings.mlr.press

A Study of Condition Numbers for First-Order Optimization

Charles Guille-escuret

Baptiste Goujaud

Manuela Girotti

Ioannis Mitliagkas

The study of first-order optimization algorithms (FOA) typically starts with assumptions on the objective functions, most commonly smoothnes… (see more)s and strong convexity. These metrics are used to tune the hyperparameters of FOA. We introduce a class of perturbations quantified via a new norm, called *-norm. We show that adding a small perturbation to the objective function has an equivalently small impact on the behavior of any FOA, which suggests that it should have a minor impact on the tuning of the algorithm. However, we show that smoothness and strong convexity can be heavily impacted by arbitrarily small perturbations, leading to excessively conservative tunings and convergence issues. In view of these observations, we propose a notion of continuity of the metrics, which is essential for a robust tuning strategy. Since smoothness and strong convexity are not continuous, we propose a comprehensive study of existing alternative metrics which we prove to be continuous. We describe their mutual relations and provide their guaranteed convergence rates for the Gradient Descent algorithm accordingly tuned. Finally we discuss how our work impacts the theoretical understanding of FOA and their performances.

2021-03-17

Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (published)

doi.org

proceedings.mlr.press

Tensor Networks for Probabilistic Sequence Modeling

Jacob Miller

Guillaume Rabusseau

John Terilla

Tensor networks are a powerful modeling framework developed for computational many-body physics, which have only recently been applied withi… (see more)n machine learning. In this work we utilize a uniform matrix product state (u-MPS) model for probabilistic modeling of sequence data. We first show that u-MPS enable sequence-level parallelism, with length-n sequences able to be evaluated in depth O(log n). We then introduce a novel generative algorithm giving trained u-MPS the ability to efficiently sample from a wide variety of conditional distributions, each one defined by a regular expression. Special cases of this algorithm correspond to autoregressive and fill-in-the-blank sampling, but more complex regular expressions permit the generation of richly structured data in a manner that has no direct analogue in neural generative models. Experiments on sequence modeling with synthetic and real text data show u-MPS outperforming a variety of baselines and effectively generalizing their predictions in the presence of limited data.

2021-03-17

International Conference on Artificial Intelligence and Statistics (unknown)

doi.org

proceedings.mlr.press

A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrix

Thang Doan

Mehdi Bennani

Bogdan Mazoure

Guillaume Rabusseau

Pierre Alquier

Continual learning (CL) is a setting in which an agent has to learn from an incoming stream of data during its entire lifetime. Although maj… (see more)or advances have been made in the field, one recurring problem which remains unsolved is that of Catastrophic Forgetting (CF). While the issue has been extensively studied empirically, little attention has been paid from a theoretical angle. In this paper, we show that the impact of CF increases as two tasks increasingly align. We introduce a measure of task similarity called the NTK overlap matrix which is at the core of CF. We analyze common projected gradient algorithms and demonstrate how they mitigate forgetting. Then, we propose a variant of Orthogonal Gradient Descent (OGD) which leverages structure of the data through Principal Component Analysis (PCA). Experiments support our theoretical findings and show how our method can help reduce CF on classical CL datasets.

2021-03-17

Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (published)

doi.org

proceedings.mlr.press

[Strengthening the culture of public health surveillance and population health monitoring].

Arnaud Chiolero

David L Buckeridge

St'ephane Cullati

Public health surveillance is the systematic and ongoing collection, analysis and interpretation of data to produce information useful for d… (see more)ecision-making. With the development of data science, surveillance methods are evolving through access to big data. More data does not automatically mean more information. For example, the massive amounts of data on Covid-19 was not easily transformed in useful information for decision-making. Further, data scientists have often difficulties to make their analyses useful for decision-making. For the implementation of evidence-based and data-driven public health practice, the culture of public health surveillance and population health monitoring needs to be strengthened.

2021-03-16

Revue medicale suisse (published)

pubmed.ncbi.nlm.nih.gov

Price discounting as a hidden risk factor of energy drink consumption

Hiroshi Mamiya

Erica E. M. Moodie

Alexandra M. Schmidt

Yu Ma

David L. Buckeridge

Global consumption of caffeinated energy drinks (CED) has been increasing dramatically despite increasing evidence of their adverse health e… (see more)ffects. Temporary price discounting is a rarely investigated but potentially powerful food marketing tactic influencing purchasing of CED. Using grocery transaction records generated by food stores in Montreal, we investigated the association between price discounting and purchasing of CED across socio-economic status operationalized by education and income levels in store neighbourhood. The outcome, log-transformed weekly store-level sales of CED, was modelled as a function of store-level percent price discounting, store- and neighbourhood-level confounders, and an interaction term between discounting and each of tertile education and income in store neighbourhood. The model was separately fit to transactions from supermarkets, pharmacies, supercentres, and convenience stores. There were 18,743, 12,437, 3965, and 49,533 weeks of CED sales from supermarkets, pharmacies, supercentres, and convenience stores, respectively. Percent price discounting was positively associated with log sales of CED for all store types, and the interaction between education and discounting was prominent in supercentres: −0.039 [95% confidence interval (CI): −0.051, −0.028] and −0.039 [95% CI: −0.057, −0.021], for middle- and high-education neighbourhoods relative to low-education neighbourhoods, respectively. Relative to low-income areas, the associations of discounting and log CED sales in supercentres for neighbourhoods with middle- and high-income tertile were 0.022 [95% CI: 0.010, 0.033] and 0.015 (95% CI: −0.001, 0.031), respectively. Price discounting is an important driver of CED consumption and has a varying impact across community education and income.

2021-03-15

Canadian Journal of Public Health (published)

doi.org

Local Data Debiasing for Fairness Based on Generative Adversarial Training

Ulrich Matchi Aïvodji

François Bidet

Sébastien Gambs

Rosin Claude Ngueveu

Alain Tapp

The widespread use of automated decision processes in many areas of our society raises serious ethical issues with respect to the fairness o… (see more)f the process and the possible resulting discrimination. To solve this issue, we propose a novel adversarial training approach called GANSan for learning a sanitizer whose objective is to prevent the possibility of any discrimination (i.e., direct and indirect) based on a sensitive attribute by removing the attribute itself as well as the existing correlations with the remaining attributes. Our method GANSan is partially inspired by the powerful framework of generative adversarial networks (in particular Cycle-GANs), which offers a flexible way to learn a distribution empirically or to translate between two different distributions. In contrast to prior work, one of the strengths of our approach is that the sanitization is performed in the same space as the original data by only modifying the other attributes as little as possible, thus preserving the interpretability of the sanitized data. Consequently, once the sanitizer is trained, it can be applied to new data locally by an individual on their profile before releasing it. Finally, experiments on real datasets demonstrate the effectiveness of the approach as well as the achievable trade-off between fairness and utility.

2021-03-13

Algorithms (published)

doi.org

arxiv.org

Continuing professional education of Iranian healthcare professionals in shared decision-making: lessons learned

S. A. Rahimi

Charo Rodriguez

Jordie Croteau

Alireza Sadeghpour

Amir-Mohammad Navali

France Légaré

2021-03-11

BMC Health Services Research (published)

doi.org

Staying Ahead of the Epidemiologic Curve: Evaluation of the British Columbia Asthma Prediction System (BCAPS) During the Unprecedented 2018 Wildfire Season

Sarah B. Henderson

Kathryn T. Morrison

Kathleen E. McLean

Yue Ding

Jiayun Yao

Gavin Shaddick

David L Buckeridge

2021-03-11

Frontiers in Public Health (published)

doi.org

Pretraining Reward-Free Representations for Data-Efficient Reinforcement Learning

Max Schwarzer