pwc-archive/papers-with-abstracts huggingface dataset:
Learning particle swarming models from data with Gaussian processes
Authors: Jinchao Feng, Charles Kulick, Yunxiang Ren, Sui Tang
Date: 2021-06-04 00:00:00
Tasks: Friction, Gaussian Processes, Uncertainty Quantification

Interacting particle or agent systems that display a rich variety of swarming behaviours are ubiquitous in science and engineering. A fundamental and challenging goal is to understand the link between individual interaction rules and swarming. In this paper, we study the data-driven discovery of a second-order particle swarming model that describes the evolution of $N$ particles in $\mathbb{R}^d$ under radial interactions. We propose a learning approach that models the latent radial interaction function as Gaussian processes, which can simultaneously fulfill two inference goals: one is the nonparametric inference of {the} interaction function with pointwise uncertainty quantification, and the other one is the inference of unknown scalar parameters in the non-collective friction forces of the system. We formulate the learning problem as a statistical inverse problem and provide a detailed analysis of recoverability conditions, establishing that a coercivity condition is sufficient for recoverability. Given data collected from $M$ i.i.d trajectories with independent Gaussian observational noise, we provide a finite-sample analysis, showing that our posterior mean estimator converges in a Reproducing kernel Hilbert space norm, at an optimal rate in $M$ equal to the one in the classical 1-dimensional Kernel Ridge regression. As a byproduct, we show we can obtain a parametric learning rate in $M$ for the posterior marginal variance using $L^{\infty}$ norm, and the rate could also involve $N$ and $L$ (the number of observation time instances for each trajectory), depending on the condition number of the inverse problem. Numerical results on systems that exhibit different swarming behaviors demonstrate efficient learning of our approach from scarce noisy trajectory data.
Revisiting Hilbert-Schmidt Information Bottleneck for Adversarial Robustness
Authors: Zifeng Wang, Tong Jian, Aria Masoomi, Stratis Ioannidis, Jennifer Dy
Date: 2021-06-04 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Adversarial Robustness

We investigate the HSIC (Hilbert-Schmidt independence criterion) bottleneck as a regularizer for learning an adversarially robust deep neural network classifier. In addition to the usual cross-entropy loss, we add regularization terms for every intermediate layer to ensure that the latent representations retain useful information for output prediction while reducing redundant information. We show that the HSIC bottleneck enhances robustness to adversarial attacks both theoretically and experimentally. In particular, we prove that the HSIC bottleneck regularizer reduces the sensitivity of the classifier to adversarial examples. Our experiments on multiple benchmark datasets and architectures demonstrate that incorporating an HSIC bottleneck regularizer attains competitive natural accuracy and improves adversarial robustness, both with and without adversarial examples during training. Our code and adversarially robust models are publicly available.
BO-DBA: Query-Efficient Decision-Based Adversarial Attacks via Bayesian Optimization
Authors: Zhuosheng Zhang, Shucheng Yu
Date: 2021-06-04 00:00:00
Tasks: Bayesian Optimization

Decision-based attacks (DBA), wherein attackers perturb inputs to spoof learning algorithms by observing solely the output labels, are a type of severe adversarial attacks against Deep Neural Networks (DNNs) requiring minimal knowledge of attackers. State-of-the-art DBA attacks relying on zeroth-order gradient estimation require an excessive number of queries. Recently, Bayesian optimization (BO) has shown promising in reducing the number of queries in score-based attacks (SBA), in which attackers need to observe real-valued probability scores as outputs. However, extending BO to the setting of DBA is nontrivial because in DBA only output labels instead of real-valued scores, as needed by BO, are available to attackers. In this paper, we close this gap by proposing an efficient DBA attack, namely BO-DBA. Different from existing approaches, BO-DBA generates adversarial examples by searching so-called \emph{directions of perturbations}. It then formulates the problem as a BO problem that minimizes the real-valued distortion of perturbations. With the optimized perturbation generation process, BO-DBA converges much faster than the state-of-the-art DBA techniques. Experimental results on pre-trained ImageNet classifiers show that BO-DBA converges within 200 queries while the state-of-the-art DBA techniques need over 15,000 queries to achieve the same level of perturbation distortion. BO-DBA also shows similar attack success rates even as compared to BO-based SBA attacks but with less distortion.
An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
Authors: Blake Woodworth, Nathan Srebro
Date: 2021-06-04 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Stochastic Optimization

We present and analyze an algorithm for optimizing smooth and convex or strongly convex objectives using minibatch stochastic gradient estimates. The algorithm is optimal with respect to its dependence on both the minibatch size and minimum expected loss simultaneously. This improves over the optimal method of Lan (2012), which is insensitive to the minimum expected loss; over the optimistic acceleration of Cotter et al. (2011), which has suboptimal dependence on the minibatch size; and over the algorithm of Liu and Belkin (2018), which is limited to least squares problems and is also similarly suboptimal with respect to the minibatch size. Applied to interpolation learning, the improvement over Cotter et al. and Liu and Belkin translates to a linear, rather than square-root, parallelization speedup.
Point Cloud Failure Criterion for Composites using k-Nearest Neighbor Classification
Authors: Subramaniam Rajan, Bilal Khaled, Loukham Shyamsunder
Date: 2021-06-04 00:00:00

Numerous theories of failure have been postulated and implemented in various commercial programs for composite materials. Even the best theories have had limited success in predicting damage and failure in validation exercises. In view of this background, many researchers have started exploring the use of multiscale modeling to improve the fidelity of the modeling and simulation of various structural and materials systems. In this paper, a multi-scale modeling scheme is used to illustrate how a combination of virtual and laboratory testing programs can be used to generate a point cloud of failure surface data that can then be queried during finite element analysis at the continuum scale to ascertain if the onset of failure has occurred. The k-nearest neighbor (k-NN) classification concept is used to obtain the answer to the query. A linear, elastic, static finite element example using a unidirectional composite shows that the framework can be generated and used effectively and efficiently with the possibility to extend the approach for all types of composite architectures and behaviors.
Learning Curves for SGD on Structured Features
Authors: Blake Bordelon, Cengiz Pehlevan
Date: 2021-06-04 00:00:00
Proceeding: ICLR 2022 4
Tasks: BIG-bench Machine Learning, Feature Correlation, Learning Theory

The generalization performance of a machine learning algorithm such as a neural network depends in a non-trivial way on the structure of the data distribution. To analyze the influence of data structure on test loss dynamics, we study an exactly solveable model of stochastic gradient descent (SGD) on mean square loss which predicts test loss when training on features with arbitrary covariance structure. We solve the theory exactly for both Gaussian features and arbitrary features and we show that the simpler Gaussian model accurately predicts test loss of nonlinear random-feature models and deep neural networks trained with SGD on real datasets such as MNIST and CIFAR-10. We show that the optimal batch size at a fixed compute budget is typically small and depends on the feature correlation structure, demonstrating the computational benefits of SGD with small batch sizes. Lastly, we extend our theory to the more usual setting of stochastic gradient descent on a fixed subsampled training set, showing that both training and test error can be accurately predicted in our framework on real data.
Understanding and Improving Fairness-Accuracy Trade-offs in Multi-Task Learning
Authors: Yuyan Wang, Xuezhi Wang, Alex Beutel, Flavien Prost, Jilin Chen, Ed H. Chi
Date: 2021-06-04 00:00:00
Tasks: Fairness, Multi-Task Learning

As multi-task models gain popularity in a wider range of machine learning applications, it is becoming increasingly important for practitioners to understand the fairness implications associated with those models. Most existing fairness literature focuses on learning a single task more fairly, while how ML fairness interacts with multiple tasks in the joint learning setting is largely under-explored. In this paper, we are concerned with how group fairness (e.g., equal opportunity, equalized odds) as an ML fairness concept plays out in the multi-task scenario. In multi-task learning, several tasks are learned jointly to exploit task correlations for a more efficient inductive transfer. This presents a multi-dimensional Pareto frontier on (1) the trade-off between group fairness and accuracy with respect to each task, as well as (2) the trade-offs across multiple tasks. We aim to provide a deeper understanding on how group fairness interacts with accuracy in multi-task learning, and we show that traditional approaches that mainly focus on optimizing the Pareto frontier of multi-task accuracy might not perform well on fairness goals. We propose a new set of metrics to better capture the multi-dimensional Pareto frontier of fairness-accuracy trade-offs uniquely presented in a multi-task learning setting. We further propose a Multi-Task-Aware Fairness (MTA-F) approach to improve fairness in multi-task learning. Experiments on several real-world datasets demonstrate the effectiveness of our proposed approach.
A Discrete Variational Derivation of Accelerated Methods in Optimization
Authors: Cédric M. Campos, Alejandro Mahillo, David Martín de Diego
Date: 2021-06-04 00:00:00

Many of the new developments in machine learning are connected with gradient-based optimization methods. Recently, these methods have been studied using a variational perspective. This has opened up the possibility of introducing variational and symplectic methods using geometric integration. In particular, in this paper, we introduce variational integrators which allow us to derive different methods for optimization. Using both, Hamilton's and Lagrange-d'Alembert's principle, we derive two families of respective optimization methods in one-to-one correspondence that generalize Polyak's heavy ball and the well known Nesterov accelerated gradient method, the second of which mimics the behavior of the first reducing the oscillations of classical momentum methods. However, since the systems considered are explicitly time-dependent, the preservation of symplecticity of autonomous systems occurs here solely on the fibers. Several experiments exemplify the result.
Enterprise-Scale Search: Accelerating Inference for Sparse Extreme Multi-Label Ranking Trees
Authors: Philip A. Etter, Kai Zhong, Hsiang-Fu Yu, Lexing Ying, Inderjit Dhillon
Date: 2021-06-04 00:00:00
Tasks: Recommendation Systems

Tree-based models underpin many modern semantic search engines and recommender systems due to their sub-linear inference times. In industrial applications, these models operate at extreme scales, where every bit of performance is critical. Memory constraints at extreme scales also require that models be sparse, hence tree-based models are often back-ended by sparse matrix algebra routines. However, there are currently no sparse matrix techniques specifically designed for the sparsity structure one encounters in tree-based models for extreme multi-label ranking/classification (XMR/XMC) problems. To address this issue, we present the masked sparse chunk multiplication (MSCM) technique, a sparse matrix technique specifically tailored to XMR trees. MSCM is easy to implement, embarrassingly parallelizable, and offers a significant performance boost to any existing tree inference pipeline at no cost. We perform a comprehensive study of MSCM applied to several different sparse inference schemes and benchmark our methods on a general purpose extreme multi-label ranking framework. We observe that MSCM gives consistently dramatic speedups across both the online and batch inference settings, single- and multi-threaded settings, and on many different tree models and datasets. To demonstrate its utility in industrial applications, we apply MSCM to an enterprise-scale semantic product search problem with 100 million products and achieve sub-millisecond latency of 0.88 ms per query on a single thread -- an 8x reduction in latency over vanilla inference techniques. The MSCM technique requires absolutely no sacrifices to model accuracy as it gives exactly the same results as standard sparse matrix techniques. Therefore, we believe that MSCM will enable users of XMR trees to save a substantial amount of compute resources in their inference pipelines at very little cost.
Meta-Learning with Fewer Tasks through Task Interpolation
Authors: Huaxiu Yao, Linjun Zhang, Chelsea Finn
Date: 2021-06-04 00:00:00
Proceeding: ICLR 2022 4
Tasks: image-classification, Image Classification, Medical Image Classification, Meta-Learning, Pose Prediction, Property Prediction

Meta-learning enables algorithms to quickly learn a newly encountered task with just a few labeled examples by transferring previously learned knowledge. However, the bottleneck of current meta-learning algorithms is the requirement of a large number of meta-training tasks, which may not be accessible in real-world scenarios. To address the challenge that available tasks may not densely sample the space of tasks, we propose to augment the task set through interpolation. By meta-learning with task interpolation (MLTI), our approach effectively generates additional tasks by randomly sampling a pair of tasks and interpolating the corresponding features and labels. Under both gradient-based and metric-based meta-learning settings, our theoretical analysis shows MLTI corresponds to a data-adaptive meta-regularization and further improves the generalization. Empirically, in our experiments on eight datasets from diverse domains including image recognition, pose prediction, molecule property prediction, and medical image classification, we find that the proposed general MLTI framework is compatible with representative meta-learning algorithms and consistently outperforms other state-of-the-art strategies.
Generic E-Variables for Exact Sequential k-Sample Tests that allow for Optional Stopping
Authors: Rosanne Turner, Alexander Ly, Peter Grünwald
Date: 2021-06-04 00:00:00

We develop E-variables for testing whether two or more data streams come from the same source or not, and more generally, whether the difference between the sources is larger than some minimal effect size. These E-variables lead to exact, nonasymptotic tests that remain safe, i.e. keep their type-I error guarantees, under flexible sampling scenarios such as optional stopping and continuation. In special cases our E-variables also have an optimal 'growth' property under the alternative. While the construction is generic, we illustrate it through the special case of k x 2 contingency tables, where we also allow for the incorporation of different restrictions on a composite alternative. Comparison to p-value analysis in simulations and a real-world example show that E-variables, through their flexibility, often allow for early stopping of data collection, thereby retaining similar power as classical methods, while also retaining the option of extending or combining data afterwards.
SpikePropamine: Differentiable Plasticity in Spiking Neural Networks
Authors: Samuel Schmidgall, Julia Ashkanazy, Wallace Lawson, Joe Hays
Date: 2021-06-04 00:00:00

The adaptive changes in synaptic efficacy that occur between spiking neurons have been demonstrated to play a critical role in learning for biological neural networks. Despite this source of inspiration, many learning focused applications using Spiking Neural Networks (SNNs) retain static synaptic connections, preventing additional learning after the initial training period. Here, we introduce a framework for simultaneously learning the underlying fixed-weights and the rules governing the dynamics of synaptic plasticity and neuromodulated synaptic plasticity in SNNs through gradient descent. We further demonstrate the capabilities of this framework on a series of challenging benchmarks, learning the parameters of several plasticity rules including BCM, Oja's, and their respective set of neuromodulatory variants. The experimental results display that SNNs augmented with differentiable plasticity are sufficient for solving a set of challenging temporal learning tasks that a traditional SNN fails to solve, even in the presence of significant noise. These networks are also shown to be capable of producing locomotion on a high-dimensional robotic learning task, where near-minimal degradation in performance is observed in the presence of novel conditions not seen during the initial training period.
Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over $SO(3)$
Authors: Allen Liu, Ankur Moitra
Date: 2021-06-04 00:00:00
Tasks: Electron Tomography, Tensor Decomposition

In this work we study orbit recovery over $SO(3)$, where the goal is to recover a function on the sphere from noisy, randomly rotated copies of it. We assume that the function is a linear combination of low-degree spherical harmonics. This is a natural abstraction for the problem of recovering the three-dimensional structure of a molecule through cryo-electron tomography. For provably learning the parameters of a generative model, the method of moments is the standard workhorse of theoretical machine learning. It turns out that there is a natural incarnation of the method of moments for orbit recovery based on invariant theory. Bandeira et al. [BBSK+18] used invariant theory to give tight bounds on the sample complexity in terms of the noise level. However many of the key challenges remain: Can we prove bounds on the sample complexity that are polynomial in $n$, the dimension of the signal? The bounds in [BBSK+18] hide constants that have an unspecified dependence on $n$ and only hold in the limit as $\sigma^2 \rightarrow \infty$ where $\sigma^2$ is the variance of the noise. Moreover can we give efficient algorithms? We revisit these challenges from the perspective of smoothed analysis, where we assume that the coefficients of the signal, in the basis of spherical harmonics, are subject to small random perturbations. Our main result is a quasi-polynomial time algorithm for orbit recovery over $SO(3)$ in this model. Our approach is based on frequency marching, which sequentially solves linear systems to find higher degree coefficients. Our main technical contribution is to show that these linear systems have unique solutions, are well-conditioned, and that the error can be made to compound over at most a logarithmic number of rounds. We believe that our work takes an important first step towards uncovering the algorithmic implications of invariant theory.
A novel multi-scale loss function for classification problems in machine learning
Authors: Leonid Berlyand, Robert Creese, Pierre-Emmanuel Jabin
Date: 2021-06-04 00:00:00
Tasks: BIG-bench Machine Learning

We introduce two-scale loss functions for use in various gradient descent algorithms applied to classification problems via deep neural networks. This new method is generic in the sense that it can be applied to a wide range of machine learning architectures, from deep neural networks to support vector machines for example. These two-scale loss functions allow to focus the training onto objects in the training set which are not well classified. This leads to an increase in several measures of performance for appropriately-defined two-scale loss functions with respect to the more classical cross-entropy when tested on traditional deep neural networks on the MNIST, CIFAR10, and CIFAR100 data-sets.
Counterfactual Explanations Can Be Manipulated
Authors: Dylan Slack, Sophie Hilgard, Himabindu Lakkaraju, Sameer Singh
Date: 2021-06-04 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: counterfactual, Counterfactual Explanation, Crime Prediction

Counterfactual explanations are emerging as an attractive option for providing recourse to individuals adversely impacted by algorithmic decisions. As they are deployed in critical applications (e.g. law enforcement, financial lending), it becomes important to ensure that we clearly understand the vulnerabilities of these methods and find ways to address them. However, there is little understanding of the vulnerabilities and shortcomings of counterfactual explanations. In this work, we introduce the first framework that describes the vulnerabilities of counterfactual explanations and shows how they can be manipulated. More specifically, we show counterfactual explanations may converge to drastically different counterfactuals under a small perturbation indicating they are not robust. Leveraging this insight, we introduce a novel objective to train seemingly fair models where counterfactual explanations find much lower cost recourse under a slight perturbation. We describe how these models can unfairly provide low-cost recourse for specific subgroups in the data while appearing fair to auditors. We perform experiments on loan and violent crime prediction data sets where certain subgroups achieve up to 20x lower cost recourse under the perturbation. These results raise concerns regarding the dependability of current counterfactual explanation techniques, which we hope will inspire investigations in robust counterfactual explanations.
A Simple Recipe for Multilingual Grammatical Error Correction
Authors: Sascha Rothe, Jonathan Mallinson, Eric Malmi, Sebastian Krause, Aliaksei Severyn
Date: 2021-06-07 00:00:00
Proceeding: ACL 2021 5
Tasks: Grammatical Error Correction

This paper presents a simple recipe to train state-of-the-art multilingual Grammatical Error Correction (GEC) models. We achieve this by first proposing a language-agnostic method to generate a large number of synthetic examples. The second ingredient is to use large-scale multilingual language models (up to 11B parameters). Once fine-tuned on language-specific supervised sets we surpass the previous state-of-the-art results on GEC benchmarks in four languages: English, Czech, German and Russian. Having established a new set of baselines for GEC, we make our results easily reproducible and accessible by releasing a cLang-8 dataset. It is produced by using our best model, which we call gT5, to clean the targets of a widely used yet noisy lang-8 dataset. cLang-8 greatly simplifies typical GEC training pipelines composed of multiple fine-tuning stages -- we demonstrate that performing a single fine-tuning step on cLang-8 with the off-the-shelf language models yields further accuracy improvements over an already top-performing gT5 model for English.