Publications

Discrete Factorial Representations as an Abstraction for Goal Conditioned RL
Riashat Islam
Hongyu Zang
Anirudh Goyal
Alex Lamb
Kenji Kawaguchi
Xin Li
Romain Laroche
Yoshua Bengio
Remi Tachet des Combes
2022-11-28
Conference on Neural Information Processing Systems (Accept)
openreview.net
openreview.net
Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution
Antonio Orvieto
Simon Lacoste-Julien
Nicolas Loizou
Recently, Loizou et al. (2021), proposed and analyzed stochastic gradient descent (SGD) with stochastic Polyak stepsize (SPS). The proposed … (see more)SPS comes with strong convergence guarantees and competitive performance; however, it has two main drawbacks when it is used in non-over-parameterized regimes: (i) It requires a priori knowledge of the optimal mini-batch losses, which are not available when the interpolation condition is not satisfied (e.g., regularized objectives), and (ii) it guarantees convergence only to a neighborhood of the solution. In this work, we study the dynamics and the convergence properties of SGD equipped with new variants of the stochastic Polyak stepsize and provide solutions to both drawbacks of the original SPS. We first show that a simple modification of the original SPS that uses lower bounds instead of the optimal function values can directly solve issue (i). On the other hand, solving issue (ii) turns out to be more challenging and leads us to valuable insights into the method's behavior. We show that if interpolation is not satisfied, the correlation between SPS and stochastic gradients introduces a bias, which effectively distorts the expectation of the gradient signal near minimizers, leading to non-convergence - even if the stepsize is scaled down during training. To fix this issue, we propose DecSPS, a novel modification of SPS, which guarantees convergence to the exact minimizer - without a priori knowledge of the problem parameters. For strongly-convex optimization problems, DecSPS is the first stochastic adaptive optimization method that converges to the exact solution without restrictive assumptions like bounded iterates/gradients.
2022-11-28
Conference on Neural Information Processing Systems (Accept)
doi.org
openreview.net
Equivariant Networks for Crystal Structures
Sékou-Oumar Kaba
Siamak Ravanbakhsh
Supervised learning with deep models has tremendous potential for applications in materials science. Recently, graph neural networks have be… (see more)en used in this context, drawing direct inspiration from models for molecules. However, materials are typically much more structured than molecules, which is a feature that these models do not leverage. In this work, we introduce a class of models that are equivariant with respect to crystalline symmetry groups. We do this by defining a generalization of the message passing operations that can be used with more general permutation groups, or that can alternatively be seen as defining an expressive convolution operation on the crystal graph. Empirically, these models achieve competitive results with state-of-the-art on property prediction tasks.
2022-11-28
Conference on Neural Information Processing Systems (Accept)
doi.org
openreview.net
Functional connectivity subtypes associate robustly with ASD diagnosis
Sebastian G. W. Urchs
Angela Tam
Pierre Orban
Clara A. Moreau
Yassine Benhajali
Hien Duy Nguyen
Alan C. Evans
Lune P Bellec
Our understanding of the changes in functional brain organization in autism is hampered by the extensive heterogeneity that characterizes th… (see more)is neurodevelopmental disorder. Data driven clustering offers a straightforward way to decompose autism heterogeneity into subtypes of connectivity and promises an unbiased framework to investigate behavioral symptoms and causative genetic factors. Yet, the robustness and generalizability of functional connectivity subtypes is unknown. Here, we show that a simple hierarchical cluster analysis can robustly relate a given individual and brain network to a connectivity subtype, but that continuous assignments are more robust than discrete ones. We also found that functional connectivity subtypes are moderately associated with the clinical diagnosis of autism, and these associations generalize to independent replication data. We explored systematically 18 different brain networks as we expected them to associate with different behavioral profiles as well as different key regions. Contrary to this prediction, autism functional connectivity subtypes converged on a common topography across different networks, consistent with a compression of the primary gradient of functional brain organization, as previously reported in the literature. Our results support the use of data driven clustering as a reliable data dimensionality reduction technique, where any given dimension only associates moderately with clinical manifestations.
2022-11-28
eLife (published)
doi.org
Gradient Descent Is Optimal Under Lower Restricted Secant Inequality And Upper Error Bound
Charles Guille-escuret
Baptiste Goujaud
Adam Ibrahim
Ioannis Mitliagkas
The study of first-order optimization is sensitive to the assumptions made on the objective functions. These assumptions induce complexity c… (see more)lasses which play a key role in worst-case analysis, including the fundamental concept of algorithm optimality. Recent work argues that strong convexity and smoothness, popular assumptions in literature, lead to a pathological definition of the condition number (Guille-Escuret et al., 2021). Motivated by this result, we focus on the class of functions satisfying a lower restricted secant inequality and an upper error bound. On top of being robust to the aforementioned pathological behavior and including some non-convex functions, this pair of conditions displays interesting geometrical properties. In particular, the necessary and sufficient conditions to interpolate a set of points and their gradients within the class can be separated into simple conditions on each sampled gradient. This allows the performance estimation problem (PEP, Drori and Teboulle (2012)) to be solved analytically, leading to a lower bound on the convergence rate that proves gradient descent to be exactly optimal on this class of functions among all first-order algorithms.
2022-11-28
Conference on Neural Information Processing Systems (Accept)
doi.org
openreview.net
High-Order Pooling for Graph Neural Networks with Tensor Decomposition
Chenqing Hua
Guillaume Rabusseau
Jian Tang
Graph Neural Networks (GNNs) are attracting growing attention due to their effectiveness and flexibility in modeling a variety of graph-stru… (see more)ctured data. Exiting GNN architectures usually adopt simple pooling operations (eg. sum, average, max) when aggregating messages from a local neighborhood for updating node representation or pooling node representations from the entire graph to compute the graph representation. Though simple and effective, these linear operations do not model high-order non-linear interactions among nodes. We propose the Tensorized Graph Neural Network (tGNN), a highly expressive GNN architecture relying on tensor decomposition to model high-order non-linear node interactions. tGNN leverages the symmetric CP decomposition to efficiently parameterize permutation-invariant multilinear maps for modeling node interactions. Theoretical and empirical analysis on both node and graph classification tasks show the superiority of tGNN over competitive baselines. In particular, tGNN achieves the most solid results on two OGB node classification datasets and one OGB graph classification dataset.
2022-11-28
Neural Information Processing Systems (Accept)
doi.org
openreview.net
Histology-informed automatic parcellation of white matter tracts in the rat spinal cord
Harris Nami
Christian S. Perone
Julien Cohen-Adad
The white matter is organized into “tracts” or “bundles,” which connect different parts of the central nervous system. Knowing where… (see more) these tracts are located in each individual is important for understanding the cause of potential sensorial, motor or cognitive deficits and for developing appropriate treatments. Traditionally, tracts are found using tracer injection, which is a difficult, slow and poorly scalable technique. However, axon populations from a given tract exhibit specific characteristics in terms of morphometrics and myelination. Hence, the delineation of tracts could, in principle, be done based on their morphometry. The objective of this study was to generate automatic parcellation of the rat spinal white matter tracts using the manifold information from scanning electron microscopy images of the entire spinal cord. The axon morphometrics (axon density, axon diameter, myelin thickness and g-ratio) were computed pixelwise following automatic axon segmentation using AxonSeg. The parcellation was based on an agglomerative clustering algorithm to group the tracts. Results show that axon morphometrics provide sufficient information to automatically identify some white matter tracts in the spinal cord, however, not all tracts were correctly identified. Future developments of microstructure quantitative MRI even bring hope for a personalized clustering of white matter tracts in each individual patient. The generated atlas and the associated code can be found at https://github.com/neuropoly/tract-clustering.
2022-11-28
Frontiers in Neuroanatomy (published)
doi.org
Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions
Courtney Paquette
Elliot Paquette
Ben Adlam
Jeffrey Pennington
Stochastic gradient descent (SGD) is a pillar of modern machine learning, serving as the go-to optimization algorithm for a diverse array of… (see more) problems. While the empirical success of SGD is often attributed to its computational efficiency and favorable generalization behavior, neither effect is well understood and disentangling them remains an open problem. Even in the simple setting of convex quadratic problems, worst-case analyses give an asymptotic convergence rate for SGD that is no better than full-batch gradient descent (GD), and the purported implicit regularization effects of SGD lack a precise explanation. In this work, we study the dynamics of multi-pass SGD on high-dimensional convex quadratics and establish an asymptotic equivalence to a stochastic differential equation, which we call homogenized stochastic gradient descent (HSGD), whose solutions we characterize explicitly in terms of a Volterra integral equation. These results yield precise formulas for the learning and risk trajectories, which reveal a mechanism of implicit conditioning that explains the efficiency of SGD relative to GD. We also prove that the noise from SGD negatively impacts generalization performance, ruling out the possibility of any type of implicit regularization in this context. Finally, we show how to adapt the HSGD formalism to include streaming SGD, which allows us to produce an exact prediction for the excess risk of multi-pass SGD relative to that of streaming SGD (bootstrap risk).
2022-11-28
Conference on Neural Information Processing Systems (Accept)
doi.org
openreview.net
Improving the accuracy of single-trial fMRI response estimates using GLMsingle
Jacob S Prince
Ian Charest
Jan W Kurzawski
John A Pyles
Michael J Tarr
Kendrick Kay
2022-11-28
eLife (published)
doi.org
Inductive Logical Query Answering in Knowledge Graphs
Mikhail Galkin
Zhaocheng Zhu
Hongyu Ren
Jian Tang
Formulating and answering logical queries is a standard communication interface for knowledge graphs (KGs). Alleviating the notorious incomp… (see more)leteness of real-world KGs, neural methods achieved impressive results in link prediction and complex query answering tasks by learning representations of entities, relations, and queries. Still, most existing query answering methods rely on transductive entity embeddings and cannot generalize to KGs containing new entities without retraining the entity embeddings. In this work, we study the inductive query answering task where inference is performed on a graph containing new entities with queries over both seen and unseen entities. To this end, we devise two mechanisms leveraging inductive node and relational structure representations powered by graph neural networks (GNNs). Experimentally, we show that inductive models are able to perform logical reasoning at inference time over unseen nodes generalizing to graphs up to 500% larger than training ones. Exploring the efficiency--effectiveness trade-off, we find the inductive relational structure representation method generally achieves higher performance, while the inductive node representation method is able to answer complex queries in the inference-only regime without any training on queries and scales to graphs of millions of nodes. Code is available at https://github.com/DeepGraphLearning/InductiveQE.
2022-11-28
Conference on Neural Information Processing Systems (Accept)
doi.org
openreview.net
Learning Robust Dynamics through Variational Sparse Gating
Arnav Kumar Jain
Shivakanth Sujit
Shruti Joshi
Vincent Michalski
Danijar Hafner
Samira Ebrahimi-Kahou
Learning world models from their sensory inputs enables agents to plan for actions by imagining their future outcomes. World models have pre… (see more)viously been shown to improve sample-efficiency in simulated environments with few objects, but have not yet been applied successfully to environments with many objects. In environments with many objects, often only a small number of them are moving or interacting at the same time. In this paper, we investigate integrating this inductive bias of sparse interactions into the latent dynamics of world models trained from pixels. First, we introduce Variational Sparse Gating (VSG), a latent dynamics model that updates its feature dimensions sparsely through stochastic binary gates. Moreover, we propose a simplified architecture Simple Variational Sparse Gating (SVSG) that removes the deterministic pathway of previous models, resulting in a fully stochastic transition function that leverages the VSG mechanism. We evaluate the two model architectures in the BringBackShapes (BBS) environment that features a large number of moving objects and partial observability, demonstrating clear improvements over prior models.
2022-11-28
Advances in Neural Information Processing Systems (Accept)
doi.org
openreview.net
Long Range Graph Benchmark
Vijay Prakash Dwivedi
Ladislav Rampasek
Mikhail Galkin
Ali Parviz
Guy Wolf
Anh Tuan Luu
Dominique Beaini
Graph Neural Networks (GNNs) that are based on the message passing (MP) paradigm generally exchange information between 1-hop neighbors to b… (see more)uild node representations at each layer. In principle, such networks are not able to capture long-range interactions (LRI) that may be desired or necessary for learning a given task on graphs. Recently, there has been an increasing interest in development of Transformer-based methods for graphs that can consider full node connectivity beyond the original sparse structure, thus enabling the modeling of LRI. However, MP-GNNs that simply rely on 1-hop message passing often fare better in several existing graph benchmarks when combined with positional feature representations, among other innovations, hence limiting the perceived utility and ranking of Transformer-like architectures. Here, we present the Long Range Graph Benchmark (LRGB) with 5 graph learning datasets: PascalVOC-SP, COCO-SP, PCQM-Contact, Peptides-func and Peptides-struct that arguably require LRI reasoning to achieve strong performance in a given task. We benchmark both baseline GNNs and Graph Transformer networks to verify that the models which capture long-range dependencies perform significantly better on these tasks. Therefore, these datasets are suitable for benchmarking and exploration of MP-GNNs and Graph Transformer architectures that are intended to capture LRI.
2022-11-28
Neural Information Processing Systems (Accept)
doi.org
openreview.net