pwc-archive/papers-with-abstracts huggingface dataset:
On the Importance of Looking at the Manifold
Authors: Anonymous
Date: 2020-10-10 00:00:00
Tasks: Representation Learning

Data typically represented in regular domains, such as images, can have a higher level of relational information, either between data samples or even relations within samples.
With this perspective our data points can be enriched by explicitly accounting for this connectivity.
We analyze various approaches for unsupervised representation learning and investigate the importance of considering topological information.
We show that each of the representations learned by these models may have critical importance for further downstream tasks, and that accounting for the topological features can improve the modeling capabilities for certain problems.
Inter-layer Information Similarity Assessment of Deep Neural Networks Via Topological Similarity and Persistence Analysis of Data Neighbour Dynamics
Authors: Anonymous
Date: 2020-10-10 00:00:00

The quantitative analysis of information structure through a deep neural network (DNN) can unveil new insights into the theoretical performance of DNN architectures.  Two very promising avenues of research towards quantitative information structure analysis are: 1) layer similarity (LS) strategies focused on the inter-layer feature similarity, and 2) intrinsic dimensionality (ID) strategies focused on layer-wise data dimensionality using pairwise information.  Inspired by both LS and ID strategies for quantitative information structure analysis, we introduce two novel complimentary methods for inter-layer information similarity assessment premised on the interesting idea of studying a data sample's neighbourhood dynamics as it traverses through a DNN. More specifically, we introduce the concept of Nearest Neighbour Topological Similarity (NNTS) for quantifying the information topology similarity between layers of a DNN.  Furthermore, we introduce the concept of Nearest Neighbour Topological Persistence (NNTP) for quantifying the inter-layer persistence of data neighbourhood relationships throughout a DNN. The proposed strategies facilitates the efficient inter-layer information similarity assessment by leveraging only local topological information, and we demonstrate their efficacy in this study by performing analysis on a deep convolutional neural network architecture on image data to study the insights that can be gained with respect to the theoretical performance of a DNN.
Betti numbers of attention graphs is all you really need
Authors: Anonymous
Date: 2020-10-10 00:00:00
Tasks: All, Classification, text-classification, Text Classification

We apply methods of topological analysis to the attention graphs, calculated on the attention heads of the BERT model (Devlin et al. (2019)). Our research shows that the classifier built upon basic persistent topological features (namely, Betti numbers) of the trained neural network can achieve classification results on par with the conventional classification method. We show the relevance of such topological text representation on three text classification benchmarks. For the best of our knowledge, it is the first attempt to analyze the topology of an attention-based neural network, widely used for Natural Language Processing.
Multiple Hypothesis Testing with Persistent Homology
Authors: Mikael Vejdemo-Johansson, Sayan Mukherjee
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12

Multiple hypothesis testing requires a control procedure.
Simply increasing simulations or permutations to meet a Bonferroni-style threshold is prohibitively expensive.
In this paper we propose a null model based approach to testing for acyclicity, coupled with a Family-Wise Error Rate (FWER) control method that does not suffer from these computational costs.
Bifurcation Analysis using Zigzag Persistence
Authors: Sarah Tymochko, Elizabeth Munch, Firas Khasawneh
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: Time Series, Time Series Analysis

As bifurcations in a dynamical system are drastic behavioral changes, being able to detect when these bifurcations occur can be essential to understanding the system overall. While persistent homology has successfully been used in the field of dynamical systems, the most commonly used approaches have their limitations. Using zigzag persistence, we can simplify the methodology and capture topological changes through a collection of time series, rather that studying the topology of individual time series separately. Here we present Bifurcations using ZigZag (BuZZ), a method to detect Hopf bifurcations in dynamical systems.
Application of Topological Data Analysis to Delirium Detection
Authors: Mari Kajitani, Ken Kobayashi, Yuichi Ike, Takehiko Yamanashi, Yuhei Umeda, Yoshimasa Kadooka, Gen Shinozaki
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: EEG, Electroencephalogram (EEG), Topological Data Analysis

We propose a new scoring algorithm for detecting delirium from one-channel EEG, based on topological data analysis.  Numerical experiments demonstrated that our method achieved high predictive performance than the other existing methods.
Teaspoon: A comprehensive python package for topological signal processing
Authors: Audun D Myers, Melih Yesilli, Sarah Tymochko, Firas Khasawneh, Elizabeth Munch
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: Benchmarking, Topological Data Analysis

The emerging field of  topological signal processing brings methods from Topological Data Analysis (TDA) to create new tools for signal processing by incorporating aspects of shape. In this paper, we present an overview of the python package teaspoon, which brings together available software for computing persistent homology, the main workhorse of TDA, with modules that expand the functionality of teaspoon as a state-of-the-art topological signal processing tool. These modules include methods for incorporating tools from machine learning, complex networks,  information, and parameter selection along with a dynamical systems library to streamline the creation and benchmarking of new methods. All code is open source with up to date documentation, making the code easy to use, in particular for signal processing experts with limited experience in topological methods.
0-dimensional Homology Preserving Dimensionality Reduction with TopoMap
Authors: Harish Doraiswamy, Julien Tierny, Paulo J.S. Silva, Luis Gustavo Nonato, Cláudio Silva
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: Dimensionality Reduction

This note presents TopoMap, a novel dimensionality reduction technique which provides topological guarantees during the mapping process. In particular, TopoMap performs the mapping from a high-dimensional space to a visual space, while preserving the 0-dimensional persistence diagram of the Rips filtration of the high-dimensional data, ensuring that the filtrations generate the same connected components when applied to the original as well as projected data. The presented case studies show that the topological guarantee provided by TopoMap not only brings confidence to the visual analytic process but also can be used to assist in the assessment of other projection methods.
Multi-Parameter Persistent Homology is Practical (Extended Abstract)
Authors: Michael Kerber
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: Topological Data Analysis

Multi-parameter persistent homology is a branch of topological data analysis that is notorious for being more difficult than the standard (one-parameter) version, both in theory and for algorithmic problems. We report on three ongoing projects that demonstrates that multi-parameter method are applicable to large data sets. For instance, natural bi-filtrations generalizing Vietoris-Rips or alpha filtrations for hundred of thousands of points can be decomposed within seconds in their indecomposable parts.
$k$-simplex2vec: a simplicial extension of node2vec
Authors: Celia Hacker
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: BIG-bench Machine Learning

We present a novel method of associating Euclidean features to simplicial complexes, providing a way to use them as input to statistical and machine learning tools. This method extends the node2vec algorithm to simplices of higher dimensions, providing insight into the structure of a simplicial complex, or into the higher-order interactions in a graph.
On The Topological Expressive Power of Neural Networks
Authors: Giovanni Petri, António Leitão
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12

We propose a topological description of neural network expressive power. 
We adopt the topology of the space of decision boundaries realized by a neural architecture as a measure of its intrinsic expressive power. 
By sampling a large number of neural architectures with different sizes and design, we show how such measure of expressive power depends on the properties of the architectures, like depth, width and other related quantities.
Multi-parameter hierarchical clustering and beyond
Authors: Alexander Rolle
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: Clustering, Survey

We survey recent progress on multi-parameter hierarchical clustering, which has developed in several directions since it was introduced by Carlsson--M\'{e}moli in 2010. These lines of research show that tools originally developed in the setting of multi-parameter persistent homology can be applied more broadly, without linearizing via homology.
Topological Convolutional Neural Networks
Authors: Ephy Love, Benjamin Filippenko, Vasileios Maroulas, Gunnar E. Carlsson
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12

There is considerable interest in making convolutional neural networks (CNNs) that learn on less data, are better at generalizing, and are more easily interpreted. This work introduces the Topological CNN (TCNN), which encompasses several topologically defined convolutional methods. Manifolds with important relationships to the natural image space are used to parameterize image filters which are used as convolutional weights in a TCNN. These manifolds also parameterize slices in layers of a TCNN across which the weights are localized. We show evidence that TCNNs learn faster, on less data, with fewer learned parameters, and with greater generalizability and interpretability than conventional CNNs.
Comparing Distance Metrics on Vectorized Persistence Summaries
Authors: Brittany Fasy, Yu Qin, Brian Summa, Carola Wenk
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: Topological Data Analysis

The persistence diagram (PD) is an important tool in topological data analysis for encoding an abstract representation of the homology of a shape at different scales. Different vectorizations of PD summary are commonly used in machine learning applications, however distances between vectorized persistence summaries may differ greatly from the distances between the original PDs. Surprisingly, no research has been carried out in this area before. In this work we compare distances between PDs and between different commonly used vectorizations. Our results give new insights into comparing vectorized persistence summaries and can be used to design better feature-based learning models based on PDs.
Quantifying barley morphology using the Euler characteristic transform
Authors: Erik J Amezquita, Michelle Quigley, Tim Ophelders, Jacob Landis, Elizabeth Munch, Daniel Chitwood, Daniel Koenig
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12
Tasks: Topological Data Analysis

Shape is foundational to biology. Observing and documenting shape has fueled biological understanding, and from this perspective, it is also a type of data.  The vision of topological data analysis, that data is shape and shape is data, will be relevant as biology transitions into a data-driven era where meaningful interpretation of large data sets is a limiting factor. We focus first on quantifying the morphology of barley spikes and seeds using topological descriptors based on the Euler characteristic. We then successfully train a support vector machine to classify 28 different varieties of barley based solely on the shape of their grains.
Simplicial 2-Complex Convolutional Neural Networks
Authors: Eric Bunch, Qian You, Glenn Fung, Vikas Singh
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12

Recently, neural network architectures have been developed to accommodate when the data has the structure of a graph or, more generally, a hypergraph. While useful, graph structures can be potentially limiting. Hypergraph structures in general do not account for higher order relations between their hyperedges. Simplicial complexes offer a middle ground, with a rich theory to draw on. We develop a convolutional neural network layer on simplicial 2-complexes.
LUMAWIG: Un-bottling the bottleneck distance for zero dimensional persistence diagrams at scale
Authors: Paul Samuel Ignacio, Jay-Anne Bulauan, David Uminsky
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12

We present LUMÁWIG, a novel efficient algorithm to compute dimension zero bottleneck distance between two persistence diagrams of a specific kind which outperforms all other publicly available algorithm in runtime and accuracy.  We bypass the overwhelming matching problem in previous implementations of the bottleneck distance, and prove that the zero dimensional bottleneck distance can be recovered from a very small number of matching cases. LUMÁWIG also generally enjoys linear complexity as shown by empirical tests.  This allows us to scaleTDA to data sets of sizes encountered in machine learning and utilize persistence diagrams in a manner that goes beyond the simple use of the most persistent components.
Witness Autoencoder: Shaping the Latent Space with Witness Complexes
Authors: Simon Till Schönenberger, Anastasiia Varava, Vladislav Polianskii, Jen Jen Chung, Danica Kragic, Roland Siegwart
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12

We present a Witness Autoencoder (W-AE) – an autoencoder that captures geodesic distances of the data in the latent space. Our algorithm uses witness complexes to compute geodesic distance approximations on a mini-batch level, and leverages topological information from the entire dataset while performing batch-wise approximations. This way, our method allows to capture the global structure of the data even with a small batch size, which is beneficial for large-scale real-world data. We show that our method captures the structure of the manifold more accurately than the recently introduced topological autoencoder (TopoAE).
Topo Sampler: A Topology Constrained Noise Sampling for GANs
Authors: Adrish Dey, Sayantan Das
Date: 2020-10-10 00:00:00
Proceeding: NeurIPS Workshop TDA_and_Beyond 2020 12

This work studies disconnected manifold learning in generative models in the light of point-set topology and persistent homology. Under this formalism, the topological similarity of latent space in generative models with the underlying manifold of data distribution facilitates better generalization. To achieve this, we introduce a topology-constrained noise sampler, responsible for mapping the samples from Gaussian spheres to a latent embedding space, which in turn is constrained to be topologically similar to the manifold underlying the data distribution. We study the effectiveness of this method in GANs for learning disconnected manifolds. This is ongoing research, with the current report containing preliminary empirical experiments.
Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
Authors: Tanner Fiez, Lillian J Ratliff, Eric Mazumdar, Evan Faulkner, Adhyyan Narang
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12

We study gradient descent-ascent learning dynamics with timescale separation in unconstrained continuous action zero-sum games where the minimizing player faces a nonconvex optimization problem and the maximizing player optimizes a Polyak-Lojasiewicz (PL) or strongly-concave (SC) objective. In contrast to past work, we assess convergence in relation to game-theoretic equilibria instead of only notions of stationarity. In pursuit of this goal, we prove that the only locally stable points of the continuous-time limiting system correspond to strict local minmax equilibria in each class of games. For the class of nonconvex-PL zero-sum games, we exploit timescale separation to construct a potential function that when combined with the stability characterization and an asymptotic saddle avoidance result gives a global asymptotic almost-sure convergence guarantee to a set of the strict local minmax equilibrium. For the class of nonconvex-SC zero-sum games, we show the surprising property that the function of the game can be made a potential with timescale separation. Combining this insight with the stability characterization allows us to generalize methods for efficiently escaping saddle points from nonconvex optimization to this class of zero-sum games and obtain a global finite-time convergence guarantee for gradient descent-ascent with timescale separation to approximate local minmax equilibria.
Stochastic optimization under time drift: iterate averaging, step-decay schedules, and high probability guarantees
Authors: Joshua Cutler, Dmitriy Drusvyatskiy, Zaid Harchaoui
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Stochastic Optimization, valid

We consider the problem of minimizing a convex function that is evolving in time according to unknown and possibly stochastic dynamics. Such problems abound in the machine learning and signal processing literature, under the names of concept drift and stochastic tracking. We provide novel non-asymptotic convergence guarantees for stochastic algorithms with iterate averaging, focusing on bounds valid both in expectation and with high probability. Notably, we show that the tracking efficiency of the proximal stochastic gradient method depends only logarithmically on the initialization quality when equipped with a step-decay schedule.
Adaptive First-Order Methods Revisited: Convex Minimization without Lipschitz Requirements
Authors: Kimon Antonakopoulos, Panayotis Mertikopoulos
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12

We propose a new family of adaptive first-order methods for a class of convex minimization problems that may fail to be Lipschitz continuous or smooth in the standard sense. Specifically, motivated by a recent flurry of activity on non-Lipschitz (NoLips) optimization, we consider problems that are continuous or smooth relative to a reference Bregman function – as opposed to a global, ambient norm (Euclidean or otherwise). These conditions encompass a wide range ofproblems with singular objective, such as Fisher markets, Poisson tomography, D-design, and the like. In this setting, the application of existing order-optimal adaptive methods – like UnixGrad or AcceleGrad – is not possible, especially in the presence of randomness and uncertainty. The proposed method, adaptive mirror descent (AdaMir), aims to close this gap by concurrently achieving min-max optimal rates in problems that are relatively continuous or smooth, including stochastic ones.
Ultrahyperbolic Neural Networks
Authors: Marc T Law
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Node Classification

Riemannian space forms, such as the Euclidean space, sphere and hyperbolic space, are popular and powerful representation spaces in machine learning. For instance, hyperbolic geometry is appropriate to represent graphs without cycles and has been used to extend Graph Neural Networks. Recently, some pseudo-Riemannian space forms that generalize both hyperbolic and spherical geometries have been exploited to learn a specific type of nonparametric embedding called ultrahyperbolic. The lack of geodesic between every pair of ultrahyperbolic points makes the task of learning parametric models (e.g., neural networks) difficult. This paper introduces a method to learn parametric models in ultrahyperbolic space. We experimentally show the relevance of our approach in the tasks of graph and node classification.
Particle Dual Averaging: Optimization of Mean Field Neural Network with Global Convergence Rate Analysis
Authors: Atsushi Nitanda, Denny Wu, Taiji Suzuki
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12

We propose the particle dual averaging (PDA) method, which generalizes the dual averaging method in convex optimization to the optimization over probability distributions with quantitative runtime guarantee. The algorithm consists of an inner loop and outer loop: the inner loop utilizes the Langevin algorithm to approximately solve for a stationary distribution, which is then optimized in the outer loop. The method can be interpreted as an extension of the Langevin algorithm to naturally handle nonlinear functional on the probability space. An important application of the proposed method is the optimization of neural network in the mean field regime, which is theoretically attractive due to the presence of nonlinear feature learning, but quantitative convergence rate can be challenging to obtain. By adapting finite-dimensional convex optimization theory into the space of measures, we not only establish global convergence of PDA for two-layer mean field neural networks under more general settings and simpler analysis, but also provide quantitative polynomial runtime guarantee. Our theoretical results are supported by numerical simulations on neural networks with reasonable size.
Counterfactual Invariance to Spurious Correlations in Text Classification
Authors: Victor Veitch, Alexander D'Amour, Steve Yadlowsky, Jacob Eisenstein
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Causal Inference, Classification, counterfactual, text-classification, Text Classification

Informally, a 'spurious correlation' is the dependence of a model on some aspect of the input data that an analyst thinks shouldn't matter. In machine learning, these have a know-it-when-you-see-it character; e.g., changing the gender of a sentence's subject changes a sentiment predictor's output. To check for spurious correlations, we can 'stress test' models by perturbing irrelevant parts of input data and seeing if model predictions change. In this paper, we study stress testing using the tools of causal inference. We introduce counterfactual invariance as a formalization of the requirement that changing irrelevant parts of the input shouldn't change model predictions. We connect counterfactual invariance to out-of-domain model performance, and provide practical schemes for learning (approximately) counterfactual invariant predictors (without access to counterfactual examples). It turns out that both the means and implications of counterfactual invariance depend fundamentally on the true underlying causal structure of the data---in particular, whether the label causes the features or the features cause the label. Distinct causal structures require distinct regularization schemes to induce counterfactual invariance. Similarly, counterfactual invariance implies different domain shift guarantees depending on the underlying causal structure. This theory is supported by empirical results on text classification.