pwc-archive/papers-with-abstracts huggingface dataset:
Adaptive Single-Pass Stochastic Gradient Descent in Input Sparsity Time
Authors: Sepideh Mahabadi, David Woodruff, Samson Zhou
Date: 2021-01-01 00:00:00
Tasks: Second-order methods, Stochastic Optimization

We study sampling algorithms for variance reduction methods for stochastic optimization. Although stochastic gradient descent (SGD) is widely used for large scale machine learning, it sometimes experiences slow convergence rates due to the high variance from uniform sampling. In this paper, we introduce an algorithm that approximately samples a gradient from the optimal distribution for a common finite-sum form with $n$ terms, while just making a single pass over the data, using input sparsity time, and $\tO{Td}$ space. Our algorithm can be implemented in big data models such as the streaming and distributed models. Moreover, we show that our algorithm can be generalized to approximately sample Hessians and thus provides variance reduction for second-order methods as well. We demonstrate the efficiency of our algorithm on large-scale datasets.
Weights Having Stable Signs Are Important: Finding Primary Subnetworks and Kernels to Compress Binary Weight Networks
Authors: Zhaole Sun, Anbang Yao
Date: 2021-01-01 00:00:00
Tasks: Quantization

Binary Weight Networks (BWNs) have significantly lower computational and memory costs compared to their full-precision counterparts. To address the non-differentiable issue of BWNs, existing methods usually use the Straight-Through-Estimator (STE). In the optimization, they learn optimal binary weight outputs represented as a combination of scaling factors and weight signs to approximate 32-bit floating-point weight values, usually with a layer-wise quantization scheme. In this paper, we begin with an empirical study of training BWNs with STE under the settings of using common techniques and tricks. We show that in the context of using batch normalization after convolutional layers, adapting scaling factors with either hand-crafted or learnable methods brings marginal or no accuracy gain to final model, while the change of weight signs is crucial in the training of BWNs. Furthermore, we observe two astonishing training phenomena. Firstly, the training of BWNs demonstrates the process of seeking primary binary sub-networks whose weight signs are determined and fixed at the early training stage, which is akin to recent findings on the lottery ticket hypothesis for efficient learning of sparse neural networks. Secondly, we find binary kernels in the convolutional layers of final models tend to be centered on a limited number of fixed structural patterns, showing binary weight networks may has the potential to be further compressed, which breaks the common wisdom that representing each weight with a single bit puts the quantization to the extreme compression. To testify this hypothesis, we additionally propose a binary kernel quantization method, and we call resulting models Quantized Binary-Kernel Networks (QBNs). We hope these new experimental observations would shed new design insights to improve the training and broaden the usages of BWNs.
Triple-Search: Differentiable Joint-Search of Networks, Precision, and Accelerators
Authors: Yonggan Fu, Yongan Zhang, Haoran You, Yingyan Lin
Date: 2021-01-01 00:00:00

The record-breaking performance and prohibitive complexity of deep neural networks (DNNs) have ignited a substantial need for customized DNN accelerators which have the potential to boost DNN acceleration efficiency by orders-of-magnitude. While it has been recognized that maximizing DNNs' acceleration efficiency requires a joint design/search for three different yet highly coupled aspects, including the networks, adopted precision, and their accelerators, the challenges associated with such a joint search have not yet been fully discussed and addressed. First, to jointly search for a network and its precision via differentiable search, there exists a dilemma of whether to explode the memory consumption or achieve sub-optimal designs. Second, a generic and differentiable joint search of the networks and their accelerators is non-trivial due to (1) the discrete nature of the accelerator space and (2) the difficulty of obtaining operation-wise hardware cost penalties because some accelerator parameters are determined by the whole network. To this end, we propose a Triple-Search (TRIPS) framework to address the aforementioned challenges towards jointly searching for the network structure, precision, and accelerator in a differentiable manner, to efficiently and effectively explore the huge joint search space. Our TRIPS addresses the first challenge above via a heterogeneous sampling strategy to achieve unbiased search with constant memory consumption, and tackles the latter one using a novel co-search pipeline that integrates a generic differentiable accelerator search engine. Extensive experiments and ablation studies validate that both TRIPS generated networks and accelerators consistently outperform state-of-the-art (SOTA) designs (including co-search/exploration techniques, hardware-aware NAS methods, and DNN accelerators), in terms of search time, task accuracy, and accelerator efficiency. All codes will be released upon acceptance.
Flow Neural Network and Flow-Structured Data Representation
Authors: Xiangle Cheng, Yuchen He, Feifei Long, Shihan Xiao, FengLin Li
Date: 2021-01-01 00:00:00

Traffic flows are the most fundamental components in a communication networking system. An accurate understanding of these flows is crucial for many downstream network applications. However, the high nonlinearity, randomness and complicated self similarity (Leland et al., 1994) of these traffic thwart extensive traditional analytical and learning models, particularly in high time resolution. In this paper, we experimentally discover the spatio-temporal induction effect, a universally present property in flow-structured network traffic data. By exploiting the flowing invariance and variance, we propose FlowNN and induction operation to learn the representations of flow-structured data in communication networks. Results from regression tasks demonstrate several times better accuracy than the state-of-the-art baselines and extend the existing time resolution from second to millisecond, offering a good testament to the strength of our approach.
Analysis of Alignment Phenomenon in Simple Teacher-student Networks with Finite Width
Authors: Hanlin Zhu, Chengyang Ying, Song Zuo
Date: 2021-01-01 00:00:00

Recent theoretical analysis suggests that ultra-wide neural networks always converge to global minima near the initialization under first order methods. However, the convergence property of neural networks with finite width could be very different. The simplest experiment with two-layer teacher-student networks shows that the input weights of student neurons eventually align with one of the teacher neurons. This suggests a distinct convergence nature for ``not-too-wide'' neural networks that there might not be any local minima near the initialization. As the theoretical justification, we prove that under the most basic settings, all student neurons must align with the teacher neuron at any local minima. The methodology is extendable to more general cases, where the proof can be reduced to analyzing the properties of a special class of functions that we call {\em Angular Distance (AD) function}. Finally, we demonstrate that these properties can be easily verified numerically.
Individually Fair Rankings
Authors: Amanda Bower, Hamid Eftekhari, Mikhail Yurochkin, Yuekai Sun
Date: 2021-01-01 00:00:00
Proceeding: ICLR 2021 1
Tasks: Fairness, Learning-To-Rank

We develop an algorithm to train individually fair learning-to-rank (LTR) models. The proposed approach ensures items from minority groups appear alongside similar items from majority groups. This notion of fair ranking is based on the definition of individual fairness from supervised learning and is more nuanced than prior fair LTR approaches that simply ensure the ranking model provides underrepresented items with a basic level of exposure. The crux of our method is an optimal transport-based regularizer that enforces individual fairness and an efficient algorithm for optimizing the regularizer. We show that our approach leads to certifiably individually fair LTR models and demonstrate the efficacy of our method on ranking tasks subject to demographic biases.
Mobile Construction Benchmark
Authors: Wenyu Han, Chen Feng, Haoran Wu, Alexander Gao, Armand Jordana, Dongdong Liu, Lerrel Pinto, Ludovic Righetti
Date: 2021-01-01 00:00:00

We need intelligent robots to perform mobile construction, the process of moving in an environment and modifying its geometry according to a design plan. Without GPS or similar techniques, carefully engineered and learning-based methods face challenges to exactly achieve the plan due to the difficulty of accurately localizing the robot while strategically evolving the environment, because common tasks (manipulation/navigation) address at most one of the two coupled aspects. To seek a generic solution, we simplify mobile construction in 1/2/3D grid worlds to benchmark the performance of existing deep RL methods on this partially observable MDP. Our results show that the coupling makes this problem very challenging for model-free RL, and emphasize the need for novel task-specific solutions.
Interpretable Meta-Reinforcement Learning with Actor-Critic Method
Authors: Xingyuan Liang, Xu-Ying Liu
Date: 2021-01-01 00:00:00
Tasks: Meta Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Meta-reinforcement learning (meta-RL) algorithms have successfully trained agent systems to perform well on different tasks within only few updates. However, in gradient-based meta-RL algorithms, the Q-function at adaptation step is mainly estimated by the return of few trajectories, which can lead to high variance in Q-value and biased meta-gradient estimation, and the adaptation uses a large number of batched trajectories. To address these challenges, we propose a new meta-RL algorithm that can reduce the variance and bias of the meta-gradient estimation and perform few-shot task data sampling, which makes the meta-policy more interpretable. We reformulate the meta-RL objective, and introduce contextual Q-function as a meta-policy critic during task adaptation step and learn the Q-function under a soft actor-critic (SAC) framework. The experimental results on 2D navigation task and meta-RL benchmarks show that our approach can learn an more interpretable meta-policy to explore unknown environment and the performance are comparable to previous gradient-based algorithms.
Spectrally Similar Graph Pooling
Authors: Kyoung-Woon On, Eun-Sol Kim, Il-Jae Kwon, Sangwoong Yoon, Byoung-Tak Zhang
Date: 2021-01-01 00:00:00
Tasks: Image Retrieval, Retrieval

We consider the problem of learning compositional hierarchies of graphs. Even though structural characteristics of graphs can be learned by Graph Neural Networks (GNNs), it is difficult to find an overall compositional hierarchy using such flat operators.
In this paper, we propose a new graph pooling algorithm, Spectrally Similar Graph Pooling (SSGPool), to learn hierarchical representations of graphs. The main idea of the proposed SSGPool algorithm is to learn a coarsening matrix which maps nodes from an original graph to a smaller number of nodes in a coarsened graph. The coarsening matrix is trained to coarsen the nodes based on their feature vectors while keeping the spectral characteristics of the original graph in the coarsened one. Although existing graph pooling methods take either feature-based pooling or structure-preserving pooling, SSGPool considers two properties simultaneously in an end-to-end manner. Experiments on various graph benchmarks show the advantage of our method compared to strong baselines. To further investigate the effectiveness of our proposed method, we evaluate our approach on a real-world problem, image retrieval with visual scene graphs. Quantitative and qualitative analyses on the retrieval problem confirm that the proposed method efficiently captures the hierarchical semantic structure of scene graphs.
Using MMD GANs to correct physics models and improve Bayesian parameter estimation
Authors: Jonathan Doucette, Christian Kames, Alexander Rauscher
Date: 2021-01-01 00:00:00
Tasks: parameter estimation

Bayesian parameter estimation methods are robust techniques for quantifying properties of physical systems which cannot be observed directly. In estimating such parameters, one first requires a physics model of the phenomenon to be studied. Often, such a model follows a series of assumptions to make parameter inference feasible. When simplified models are used for inference, however, systematic differences between model predictions and observed data may propagate throughout the parameter estimation process, biasing inference results. In this work, we use generative adversarial networks (GANs) based on the maximum mean discrepancy (MMD) to learn small stochastic corrections to physics models in order to minimize inference bias. We further propose a hybrid training procedure utilizing both the MMD and the standard GAN objective functionals. We demonstrate the ability to learn stochastic model corrections and eliminate inference bias on a toy problem wherein the true data distribution is known. Subsequently, we apply these methods to a mildly ill-posed inference problem in magnetic resonance imaging (MRI), showing improvement over an established inference method. Finally, because 3D MRI images often contain millions of voxels which would each require parameter inference, we train a conditional variational autoencoder (CVAE) network on the corrected MRI physics model to perform fast inference and make this approach practical.
Continual Learning Without Knowing Task Identities: Rethinking Occam's Razor
Authors: Tiffany Tuor, Shiqiang Wang, Kin Leung
Date: 2021-01-01 00:00:00
Tasks: Continual Learning, Model Selection

Due to the catastrophic forgetting phenomenon of deep neural networks (DNNs), models trained in standard ways tend to forget what it has learned from previous tasks, especially when the new task is sufficiently different from the previous ones. To overcome this issue, various continual learning techniques have been developed in recent years, which, however, often suffer from a substantially increased model complexity and training time. In this paper, we illustrate that Occam's razor which suggests "entities should not be multiplied without necessity" carries to the development of efficient continual learning techniques. By proposing a relatively simple method based on Bayesian neural networks and model selection, we are able to significantly outperform various state-of-the-art techniques in terms of accuracy, model size, and running time. Moreover, unlike many existing works, our technique supports continual learning without task identity knowledge in training and inference phases, which is also known as task-free continual learning.
Unconditional Synthesis of Complex Scenes Using a Semantic Bottleneck
Authors: Samaneh Azadi, Michael Tschannen, Eric Tzeng, Sylvain Gelly, Trevor Darrell, Mario Lucic
Date: 2021-01-01 00:00:00
Tasks: Image Generation, Segmentation

Coupling the high-fidelity generation capabilities of label-conditional image synthesis methods with the flexibility of unconditional generative models, we propose a semantic bottleneck GAN model for unconditional synthesis of complex scenes. We assume pixel-wise segmentation labels are available during training and use them to learn the scene structure through an unconditional progressive segmentation generation network. During inference, our model first synthesizes a realistic segmentation layout from scratch, then synthesizes a realistic scene conditioned on that layout through a conditional segmentation-to-image synthesis network. When trained end-to-end, the resulting model outperforms state-of-the-art generative models in unsupervised image synthesis on two challenging domains in terms of the Frechet Inception Distance and perceptual evaluations. Moreover, we demonstrate that the end-to-end training significantly improves the segmentation-to-image synthesis sub-network, which results in superior performance over the state-of-the-art when conditioning on real segmentation layouts.
Near-Optimal Glimpse Sequences for Training Hard Attention Neural Networks
Authors: William Harvey, Michael Teng, Frank Wood
Date: 2021-01-01 00:00:00
Tasks: Experimental Design, General Classification, Hard Attention, image-classification, Image Classification

Hard visual attention is a promising approach to reduce the computational burden of modern computer vision methodologies. Hard attention mechanisms are typically non-differentiable. They can be trained with reinforcement learning but the high-variance training this entails hinders more widespread application. We show how hard attention for image classification can be framed as a Bayesian optimal experimental design (BOED) problem. From this perspective, the optimal locations to attend to are those which provide the greatest expected reduction in the entropy of the classification distribution. We introduce methodology from the BOED literature to approximate this optimal behaviour, and use it to generate `near-optimal' sequences of attention locations. We then show how to use such sequences to partially supervise, and therefore speed up, the training of a hard attention mechanism. Although generating these sequences is computationally expensive, they can be reused by any other networks later trained on the same task.
A Stochastic Gradient Langevin Dynamics Algorithm For Noise Intrinsic Federated Learning
Authors: Yan Shen, Jian Du, Chunwei Ma, Mingchen Gao, Benyu Zhang
Date: 2021-01-01 00:00:00
Tasks: Federated Learning

Non-i.i.d data distribution and Differential privacy(DP) protections are two open problems in Federated Learning(FL). We address these two problems by proposing the first noise intrinsic FL training algorithms. In our proposed algorithm, we incorporate a stochastic gradient Langevin dynamices(SGLD) oracle in local node's parameter update phase. Our introduced SGLD oracle would lower generalization errors in local node's parameter learning and provide local node DP protections. We theoretically analyze our algorithm by formulating a min-max objective functions and connects its upper bound with global loss function in FL. The convergence of our algorithm on non-convex function is also given as contraction and coupling rate of two random process defined by stochastic differential equations(SDE) We would provide DP analysis for our proposed training algorithm and provide more experiment results soon.
Hokey Pokey Causal Discovery: Using Deep Learning Model Errors to Learn Causal Structure
Authors: Emily Saldanha, Dustin Arendt, Svitlana Volkova
Date: 2021-01-01 00:00:00
Tasks: Causal Discovery

While machine learning excels at learning predictive models from observational data, learning the causal mechanisms behind the observed phenomena presents the significant challenge of distinguishing true causal relationships from confounding and other potential sources of spurious correlations. Many existing algorithms for the discovery of causal structure from observational data rely on evaluating the conditional independence relationships among features to account for the effects of confounding. However, the choice of independence tests for these algorithms often rely on assumptions regarding the data distributions and type of causal relationships. To avoid these assumptions, we develop a novel deep learning approach, dubbed the Hokey Pokey model, to indirectly explore the conditional dependencies among a set of variables by rapidly comparing predictive errors given different combinations of input variables. We then use the results of this comparison as a predictive signal for causal relationships among the variables. We conduct rigorous experiments to evaluate model robustness and generalizability using generated datasets with known underlying causal relationships and analyze the capacity of model error comparisons to provide a predictive signal for causal structure. Our model outperforms commonly used baseline models (PC and GES) and is capable of discovering causal relationships of different complexity (graph size, density and structure) in both binary and continuous data.
Fine-Tuning Offline Reinforcement Learning with Model-Based Policy Optimization
Authors: Adam Villaflor, John Dolan, Jeff Schneider
Date: 2021-01-01 00:00:00
Tasks: D4RL, MuJoCo, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

In offline reinforcement learning (RL), we attempt to learn a control policy from a fixed dataset of environment interactions. This setting has the potential benefit of allowing us to learn effective policies without needing to collect additional interactive data, which can be expensive or dangerous in real-world systems. However, traditional off-policy RL methods tend to perform poorly in this setting due to the distributional shift between the fixed data set and the learned policy. In particular, they tend to extrapolate optimistically and overestimate the action-values outside of the dataset distribution. Recently, two major avenues have been explored to address this issue. First, behavior-regularized methods that penalize actions that deviate from the demonstrated action distribution. Second, uncertainty-aware model-based (MB) methods that discourage state-actions where the dynamics are uncertain. In this work, we propose an algorithmic framework that consists of two stages. In the first stage, we train a policy using behavior-regularized model-free RL on the offline dataset. Then, we can optionally enter a second stage where we fine-tune the policy using our novel Model-Based Behavior-Regularized Policy Optimization (MB2PO) algorithm. We demonstrate that for certain tasks and dataset distributions our conservative model-based fine tuning can greatly increase performance and allow the agent to generalize and outperform the demonstrated behavior. We evaluate our method on a variety of the Gym-MuJoCo tasks in the D4RL benchmark and demonstrate that our method is competitive and in some cases superior to the state of the art for most of the evaluated tasks.
Learning to Generate Videos Using Neural Uncertainty Priors
Authors: Moitreya Chatterjee, Anoop Cherian, Narendra Ahuja
Date: 2021-01-01 00:00:00
Tasks: Diversity, Video Generation

Predicting the future frames of a video is a challenging task, in part due to the underlying stochastic real-world phenomena. Previous approaches attempt to tackle this issue by estimating a latent prior characterizing this stochasticity. Nonetheless, the cost function used in training such systems derives the training signal from the mean-squared error (MSE) between the generated frame and the ground truth, which can lead to sub-optimal training when the predictive uncertainty is high. To this end, we introduce Neural Uncertainty Priors (NUP), that produces a stochastic quantification of the uncertainty predicted by the latent prior, and use it to weigh the MSE loss. We propose a variational framework to derive the NUP in a principled manner using a hierarchical Bayesian deep graphical model. We further propose a sequence discriminator that ensures the generated frames are always realistically plausible, even when the uncertainty is consistently high. Our experiments show that NUP leads to more effective training than state-of-the-art models, especially when the training sets are small, while demonstrating better video generation quality and diversity.