pwc-archive/papers-with-abstracts huggingface dataset:
Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
Authors: Lifu Wang, Bo Shen, Ning Zhao
Date: 2019-10-14 00:00:00

In machine learning, asynchronous parallel stochastic gradient descent (APSGD) is broadly used to speed up the training process through multi-workers. Meanwhile, the time delay of stale gradients in asynchronous algorithms is generally proportional to the total number of workers, which brings additional deviation from the accurate gradient due to using delayed gradients. This may have a negative influence on the convergence of the algorithm. One may ask: How many workers can we use at most to achieve a good convergence and the linear speedup? In this paper, we consider the second-order convergence of asynchronous algorithms in non-convex optimization. We investigate the behaviors of APSGD with consistent read near strictly saddle points and provide a theoretical guarantee that if the total number of workers is bounded by $\widetilde{O}(K^{1/3}M^{-1/3})$ ($K$ is the total steps and $M$ is the mini-batch size), APSGD will converge to good stationary points ($||\nabla f(x)||\leq \epsilon, \nabla^2 f(x)\succeq -\sqrt{\epsilon}\bm{I}, \epsilon^2\leq O(\sqrt{\frac{1}{MK}}) $) and the linear speedup is achieved. Our works give the first theoretical guarantee on the second-order convergence for asynchronous algorithms. The technique we provide can be generalized to analyze other types of asynchronous algorithms to understand the behaviors of asynchronous algorithms in distributed asynchronous parallel training.
Optimization and Manipulation of Contextual Mutual Spaces for Multi-User Virtual and Augmented Reality Interaction
Authors: Mohammad Keshavarzi, Allen Y. Yang, Woojin Ko, Luisa Caldas
Date: 2019-10-14 00:00:00

Spatial computing experiences are physically constrained by the geometry and semantics of the local user environment. This limitation is elevated in remote multi-user interaction scenarios, where finding a common virtual ground physically accessible for all participants becomes challenging. Locating a common accessible virtual ground is difficult for the users themselves, particularly if they are not aware of the spatial properties of other participants. In this paper, we introduce a framework to generate an optimal mutual virtual space for a multi-user interaction setting where remote users' room spaces can have different layout and sizes. The framework further recommends movement of surrounding furniture objects that expand the size of the mutual space with minimal physical effort. Finally, we demonstrate the performance of our solution on real-world datasets and also a real HoloLens application. Results show the proposed algorithm can effectively discover optimal shareable space for multi-user virtual interaction and hence facilitate remote spatial computing communication in various collaborative workflows.
A unified framework of predicting binary interestingness of images based on discriminant correlation analysis and multiple kernel learning
Authors: Qiang Sun, Liting Wang, Maohui Li, Longtao Zhang, Yuxiang Yang
Date: 2019-10-14 00:00:00
Tasks: Content-Based Image Retrieval, Image Retrieval, Retrieval

In the modern content-based image retrieval systems, there is an increasingly interest in constructing a computationally effective model to predict the interestingness of images since the measure of image interestingness could improve the human-centered search satisfaction and the user experience in different applications. In this paper, we propose a unified framework to predict the binary interestingness of images based on discriminant correlation analysis (DCA) and multiple kernel learning (MKL) techniques. More specially, on the one hand, to reduce feature redundancy in describing the interestingness cues of images, the DCA or multi-set discriminant correlation analysis (MDCA) technique is adopted to fuse multiple feature sets of the same type for individual cues by taking into account the class structure among the samples involved to describe the three classical interestingness cues, unusualness,aesthetics as well as general preferences, with three sets of compact and representative features; on the other hand, to make good use of the heterogeneity from the three sets of high-level features for describing the interestingness cues, the SimpleMKL method is employed to enhance the generalization ability of the built model for the task of the binary interestingness classification. Experimental results on the publicly-released interestingness prediction data set have demonstrated the rationality and effectiveness of the proposed framework in the binary prediction of image interestingness where we have conducted several groups of comparative studies across different interestingness feature combinations, different interestingness cues, as well as different feature types for the three interestingness cues.
Pathological spectra of the Fisher information metric and its variants in deep neural networks
Authors: Ryo Karakida, Shotaro Akaho, Shun-ichi Amari
Date: 2019-10-14 00:00:00

The Fisher information matrix (FIM) plays an essential role in statistics and machine learning as a Riemannian metric tensor or a component of the Hessian matrix of loss functions. Focusing on the FIM and its variants in deep neural networks (DNNs), we reveal their characteristic scale dependence on the network width, depth and sample size when the network has random weights and is sufficiently wide. This study covers two widely-used FIMs for regression with linear output and for classification with softmax output. Both FIMs asymptotically show pathological eigenvalue spectra in the sense that a small number of eigenvalues become large outliers depending the width or sample size while the others are much smaller. It implies that the local shape of the parameter space or loss landscape is very sharp in a few specific directions while almost flat in the other directions. In particular, the softmax output disperses the outliers and makes a tail of the eigenvalue density spread from the bulk. We also show that pathological spectra appear in other variants of FIMs: one is the neural tangent kernel; another is a metric for the input signal and feature space that arises from feedforward signal propagation. Thus, we provide a unified perspective on the FIM and its variants that will lead to more quantitative understanding of learning in large-scale DNNs.
An Efficient Tensor Completion Method via New Latent Nuclear Norm
Authors: Jinshi Yu, Weijun Sun, Yuning Qiu, Shengli Xie
Date: 2019-10-14 00:00:00

In tensor completion, the latent nuclear norm is commonly used to induce low-rank structure, while substantially failing to capture the global information due to the utilization of unbalanced unfolding scheme. To overcome this drawback, a new latent nuclear norm equipped with a more balanced unfolding scheme is defined for low-rank regularizer. Moreover, the new latent nuclear norm together with the Frank-Wolfe (FW) algorithm is developed as an efficient completion method by utilizing the sparsity structure of observed tensor. Specifically, both FW linear subproblem and line search only need to access the observed entries, by which we can instead maintain the sparse tensors and a set of small basis matrices during iteration. Most operations are based on sparse tensors, and the closed-form solution of FW linear subproblem can be obtained from rank-one SVD. We theoretically analyze the space-complexity and time-complexity of the proposed method, and show that it is much more efficient over other norm-based completion methods for higher-order tensors. Extensive experimental results of visual-data inpainting demonstrate that the proposed method is able to achieve state-of-the-art performance at smaller costs of time and space, which is very meaningful for the memory-limited equipment in practical applications.
On the Reduction of Variance and Overestimation of Deep Q-Learning
Authors: Mohammed Sabry, Amr M. A. Khalifa
Date: 2019-10-14 00:00:00
Tasks: Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

The breakthrough of deep Q-Learning on different types of environments revolutionized the algorithmic design of Reinforcement Learning to introduce more stable and robust algorithms, to that end many extensions to deep Q-Learning algorithm have been proposed to reduce the variance of the target values and the overestimation phenomena. In this paper, we examine new methodology to solve these issues, we propose using Dropout techniques on deep Q-Learning algorithm as a way to reduce variance and overestimation. We also present experiments conducted on benchmark environments, demonstrating the effectiveness of our methodology in enhancing stability and reducing both variance and overestimation in model performance.
Preimplantation Blastomere Boundary Identification in HMC Microscopic Images of Early Stage Human Embryos
Authors: Shakiba Kheradmand, Parvaneh Saeedi, Jason Au, John Havelock
Date: 2019-10-14 00:00:00

We present a novel method for identification of the boundary of embryonic cells (blastomeres) in Hoffman Modulation Contrast (HMC) microscopic images that are taken between day one to day three. Identification of boundaries of blastomeres is a challenging task, especially in the cases containing four or more cells. This is because these cells are bundled up tightly inside an embryo's membrane and any 2D image projection of such 3D embryo includes cell overlaps, occlusions, and projection ambiguities. Moreover, human embryos include fragmentation, which does not conform to any specific patterns or shape. Here we developed a model-based iterative approach, in which blastomeres are modeled as ellipses that conform to the local image features, such as edges and normals. In an iterative process, each image feature contributes only to one candidate and is removed upon being associated to a model candidate. We have tested the proposed algorithm on an image dataset comprising of 468 human embryos obtained from different sources. An overall Precision, Sensitivity and Overall Quality (OQ) of 92%, 88% and 83% are achieved.
Cross-view kernel transfer
Authors: Riikka Huusari, Cécile Capponi, Paul Villoutreix, Hachem Kadri
Date: 2019-10-14 00:00:00
Tasks: Missing Values

We consider the kernel completion problem with the presence of multiple views in the data. In this context the data samples can be fully missing in some views, creating missing columns and rows to the kernel matrices that are calculated individually for each view. We propose to solve the problem of completing the kernel matrices with Cross-View Kernel Transfer (CVKT) procedure, in which the features of the other views are transformed to represent the view under consideration. The transformations are learned with kernel alignment to the known part of the kernel matrix, allowing for finding generalizable structures in the kernel matrix under completion. Its missing values can then be predicted with the data available in other views. We illustrate the benefits of our approach with simulated data, multivariate digits dataset and multi-view dataset on gesture classification, as well as with real biological datasets from studies of pattern formation in early \textit{Drosophila melanogaster} embryogenesis.
Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space
Authors: Quentin Mérigot, Alex Delalande, Frédéric Chazal
Date: 2019-10-14 00:00:00

This work studies an explicit embedding of the set of probability measures into a Hilbert space, defined using optimal transport maps from a reference probability density. This embedding linearizes to some extent the 2-Wasserstein space, and enables the direct use of generic supervised and unsupervised learning algorithms on measure data. Our main result is that the embedding is (bi-)H\"older continuous, when the reference density is uniform over a convex set, and can be equivalently phrased as a dimension-independent H\"older-stability results for optimal transport maps.
DISCERN: Diversity-based Selection of Centroids for k-Estimation and Rapid Non-stochastic Clustering
Authors: Ali Hassani, Amir Iranmanesh, Mahdi Eftekhari, Abbas Salemi
Date: 2019-10-14 00:00:00
Proceeding: IJMLC 2020 9
Tasks: Clustering, Diversity

One of the applications of center-based clustering algorithms such as K-Means is partitioning data points into K clusters. In some examples, the feature space relates to the underlying problem we are trying to solve, and sometimes we can obtain a suitable feature space. Nevertheless, while K-Means is one of the most efficient offline clustering algorithms, it is not equipped to estimate the number of clusters, which is useful in some practical cases. Other practical methods which do are simply too complex, as they require at least one run of K-Means for each possible K. In order to address this issue, we propose a K-Means initialization similar to K-Means++, which would be able to estimate K based on the feature space while finding suitable initial centroids for K-Means in a deterministic manner. Then we compare the proposed method, DISCERN, with a few of the most practical K estimation methods, while also comparing clustering results of K-Means when initialized randomly, using K-Means++ and using DISCERN. The results show improvement in both the estimation and final clustering performance.
Characterizing Deep Learning Training Workloads on Alibaba-PAI
Authors: Mengdi Wang, Chen Meng, Guoping Long, Chuan Wu, Jun Yang, Wei. Lin, Yangqing Jia
Date: 2019-10-14 00:00:00
Tasks: Deep Learning, GPU

Modern deep learning models have been exploited in various domains, including computer vision (CV), natural language processing (NLP), search and recommendation. In practical AI clusters, workloads training these models are run using software frameworks such as TensorFlow, Caffe, PyTorch and CNTK. One critical issue for efficiently operating practical AI clouds, is to characterize the computing and data transfer demands of these workloads, and more importantly, the training performance given the underlying software framework and hardware configurations. In this paper, we characterize deep learning training workloads from Platform of Artificial Intelligence (PAI) in Alibaba. We establish an analytical framework to investigate detailed execution time breakdown of various workloads using different training architectures, to identify performance bottleneck. Results show that weight/gradient communication during training takes almost 62% of the total execution time among all our workloads on average. The computation part, involving both GPU computing and memory access, are not the biggest bottleneck based on collective behavior of the workloads. We further evaluate attainable performance of the workloads on various potential software/hardware mappings, and explore implications on software architecture selection and hardware configurations. We identify that 60% of PS/Worker workloads can be potentially sped up when ported to the AllReduce architecture exploiting the high-speed NVLink for GPU interconnect, and on average 1.7X speedup can be achieved when Ethernet bandwidth is upgraded from 25 Gbps to 100 Gbps.
Emergent properties of the local geometry of neural loss landscapes
Authors: Stanislav Fort, Surya Ganguli
Date: 2019-10-14 00:00:00

The local geometry of high dimensional neural network loss landscapes can both challenge our cherished theoretical intuitions as well as dramatically impact the practical success of neural network training. Indeed recent works have observed 4 striking local properties of neural loss landscapes on classification tasks: (1) the landscape exhibits exactly $C$ directions of high positive curvature, where $C$ is the number of classes; (2) gradient directions are largely confined to this extremely low dimensional subspace of positive Hessian curvature, leaving the vast majority of directions in weight space unexplored; (3) gradient descent transiently explores intermediate regions of higher positive curvature before eventually finding flatter minima; (4) training can be successful even when confined to low dimensional {\it random} affine hyperplanes, as long as these hyperplanes intersect a Goldilocks zone of higher than average curvature. We develop a simple theoretical model of gradients and Hessians, justified by numerical experiments on architectures and datasets used in practice, that {\it simultaneously} accounts for all $4$ of these surprising and seemingly unrelated properties. Our unified model provides conceptual insights into the emergence of these properties and makes connections with diverse topics in neural networks, random matrix theory, and spin glasses, including the neural tangent kernel, BBP phase transitions, and Derrida's random energy model.
On the Expressivity of Neural Networks for Deep Reinforcement Learning
Authors: Kefan Dong, Yuping Luo, Tengyu Ma
Date: 2019-10-14 00:00:00
Proceeding: ICML 2020 1
Tasks: Deep Reinforcement Learning, MuJoCo, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We compare the model-free reinforcement learning with the model-based approaches through the lens of the expressive power of neural networks for policies, $Q$-functions, and dynamics. We show, theoretically and empirically, that even for one-dimensional continuous state space, there are many MDPs whose optimal $Q$-functions and policies are much more complex than the dynamics. We hypothesize many real-world MDPs also have a similar property. For these MDPs, model-based planning is a favorable algorithm, because the resulting policies can approximate the optimal policy significantly better than a neural network parameterization can, and model-free or model-based policy optimization rely on policy parameterization. Motivated by the theory, we apply a simple multi-step model-based bootstrapping planner (BOOTS) to bootstrap a weak $Q$-function into a stronger policy. Empirical results show that applying BOOTS on top of model-based or model-free policy optimization algorithms at the test time improves the performance on MuJoCo benchmark tasks.
Code Generation as a Dual Task of Code Summarization
Authors: Bolin Wei, Ge Li, Xin Xia, Zhiyi Fu, Zhi Jin
Date: 2019-10-14 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Code Generation, Code Summarization, Source Code Summarization

Code summarization (CS) and code generation (CG) are two crucial tasks in the field of automatic software development. Various neural network-based approaches are proposed to solve these two tasks separately. However, there exists a specific intuitive correlation between CS and CG, which have not been exploited in previous work. In this paper, we apply the relations between two tasks to improve the performance of both tasks. In other words, exploiting the duality between the two tasks, we propose a dual training framework to train the two tasks simultaneously. In this framework, we consider the dualities on probability and attention weights, and design corresponding regularization terms to constrain the duality. We evaluate our approach on two datasets collected from GitHub, and experimental results show that our dual framework can improve the performance of CS and CG tasks over baselines.
Variation-aware Binarized Memristive Networks
Authors: Corey Lammie, Olga Krestinskaya, Alex James, Mostafa Rahimi Azghadi
Date: 2019-10-14 00:00:00
Tasks: Quantization

The quantization of weights to binary states in Deep Neural Networks (DNNs) can replace resource-hungry multiply accumulate operations with simple accumulations. Such Binarized Neural Networks (BNNs) exhibit greatly reduced resource and power requirements. In addition, memristors have been shown as promising synaptic weight elements in DNNs. In this paper, we propose and simulate novel Binarized Memristive Convolutional Neural Network (BMCNN) architectures employing hybrid weight and parameter representations. We train the proposed architectures offline and then map the trained parameters to our binarized memristive devices for inference. To take into account the variations in memristive devices, and to study their effect on the performance, we introduce variations in $R_{ON}$ and $R_{OFF}$. Moreover, we introduce means to mitigate the adverse effect of memristive variations in our proposed networks. Finally, we benchmark our BMCNNs and variation-aware BMCNNs using the MNIST dataset.
Neural Collision Clearance Estimator for Batched Motion Planning
Authors: J. Chase Kew, Brian Ichter, Maryam Bandari, Tsang-Wei Edward Lee, Aleksandra Faust
Date: 2019-10-14 00:00:00
Tasks: Motion Planning

We present a neural network collision checking heuristic, ClearanceNet, and a planning algorithm, CN-RRT. ClearanceNet learns to predict separation distance (minimum distance between robot and workspace) with respect to a workspace. CN-RRT then efficiently computes a motion plan by leveraging three key features of ClearanceNet. First, CN-RRT explores the space by expanding multiple nodes at the same time, processing batches of thousands of collision checks. Second, CN-RRT adaptively relaxes its clearance requirements for more difficult problems. Third, to repair errors, CN-RRT shifts its nodes in the direction of ClearanceNet's gradient and repairs any residual errors with a traditional RRT, thus maintaining theoretical probabilistic completeness guarantees. In configuration spaces with up to 30 degrees of freedom, ClearanceNet achieves 845x speedup over traditional collision detection methods, while CN-RRT accelerates motion planning by up to 42% over a baseline and finds paths up to 36% more efficient. Experiments on an 11 degree of freedom robot in a cluttered environment confirm the method's feasibility on real robots.
Knowledge-guided Unsupervised Rhetorical Parsing for Text Summarization
Authors: Shengluan Hou, Ruqian Lu
Date: 2019-10-14 00:00:00
Tasks: Decoder, Knowledge Base Construction, Representation Learning, Text Summarization, Translation

Automatic text summarization (ATS) has recently achieved impressive performance thanks to recent advances in deep learning and the availability of large-scale corpora. To make the summarization results more faithful, this paper presents an unsupervised approach that combines rhetorical structure theory, deep neural model and domain knowledge concern for ATS. This architecture mainly contains three components: domain knowledge base construction based on representation learning, attentional encoder-decoder model for rhetorical parsing and subroutine-based model for text summarization. Domain knowledge can be effectively used for unsupervised rhetorical parsing thus rhetorical structure trees for each document can be derived. In the unsupervised rhetorical parsing module, the idea of translation was adopted to alleviate the problem of data scarcity. The subroutine-based summarization model purely depends on the derived rhetorical structure trees and can generate content-balanced results. To evaluate the summary results without golden standard, we proposed an unsupervised evaluation metric, whose hyper-parameters were tuned by supervised learning. Experimental results show that, on a large-scale Chinese dataset, our proposed approach can obtain comparable performances compared with existing methods.
Vertebrae Detection and Localization in CT with Two-Stage CNNs and Dense Annotations
Authors: James McCouat, Ben Glocker
Date: 2019-10-14 00:00:00

We propose a new, two-stage approach to the vertebrae centroid detection and localization problem. The first stage detects where the vertebrae appear in the scan using 3D samples, the second identifies the specific vertebrae within that region-of-interest using 2D slices. Our solution utilizes new techniques to improve the accuracy of the algorithm such as a revised approach to dense labelling from sparse centroid annotations and usage of large anisotropic kernels in the base level of a U-net architecture to maximize the receptive field. Our method improves the state-of-the-art's mean localization accuracy by 0.87mm on a publicly available spine CT benchmark.