pwc-archive/papers-with-abstracts huggingface dataset:
New Insight into Hybrid Stochastic Gradient Descent: Beyond With-Replacement Sampling and Convexity
Authors: Pan Zhou, Xiao-Tong Yuan, Jiashi Feng
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Open-Ended Question Answering

As an incremental-gradient algorithm, the hybrid stochastic gradient descent (HSGD)  enjoys  merits of both stochastic and full gradient methods for finite-sum minimization problem. However, the existing rate-of-convergence analysis for HSGD is made under with-replacement sampling (WRS) and is restricted to convex problems. It is not clear whether HSGD still carries these advantages under the common practice of without-replacement sampling (WoRS) for non-convex problems. In this paper, we affirmatively answer this open question by showing that under WoRS and for both convex and non-convex problems, it is still possible for HSGD (with constant step-size) to match full gradient descent in rate of convergence, while maintaining comparable sample-size-independent incremental first-order oracle  complexity to stochastic gradient descent. For a special class of finite-sum problems with linear prediction models, our convergence results can be further improved in some cases. Extensive numerical results confirm our theoretical affirmation and demonstrate the favorable efficiency of WoRS-based HSGD.
The Lingering of Gradients: How to Reuse Gradients Over Time
Authors: Zeyuan Allen-Zhu, David Simchi-Levi, Xinshang Wang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Management

Classically, the time complexity of a first-order method is estimated by its number of gradient computations. In this paper, we study a more refined complexity by taking into account the ``lingering'' of gradients: once a gradient is computed at $x_k$, the additional time to compute gradients at $x_{k+1},x_{k+2},\dots$ may be reduced.

We show how this improves the running time of gradient descent and SVRG. For instance, if the "additional time'' scales linearly with respect to the traveled distance, then the "convergence rate'' of gradient descent can be improved from $1/T$ to $\exp(-T^{1/3})$. On the empirical side, we solve a hypothetical revenue management problem on the Yahoo! Front Page Today Module application with 4.6m users to $10^{-6}$ error (or $10^{-12}$ dual error) using 6 passes of the dataset.
Global Gated Mixture of Second-order Pooling for Improving Deep Convolutional Neural Networks
Authors: Qilong Wang, Zilin Gao, Jiangtao Xie, WangMeng Zuo, Peihua Li
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

In most of existing deep convolutional neural networks (CNNs) for classification, global average (first-order) pooling (GAP) has become a standard module to summarize activations of the last convolution layer as final representation for prediction. Recent researches show integration of higher-order pooling (HOP) methods clearly improves performance of deep CNNs. However, both GAP and existing HOP methods assume unimodal distributions, which cannot fully capture statistics of convolutional activations, limiting representation ability of deep CNNs, especially for samples with complex contents. To overcome the above limitation, this paper proposes a global Gated Mixture of Second-order Pooling (GM-SOP) method to further improve representation ability of deep CNNs. To this end, we introduce a sparsity-constrained gating mechanism and propose a novel parametric SOP as component of mixture model. Given a bank of SOP candidates, our method can adaptively choose Top-K (K > 1) candidates for each input sample through the sparsity-constrained gating module, and performs weighted sum of outputs of K selected candidates as representation of the sample. The proposed GM-SOP can flexibly accommodate a large number of personalized SOP candidates in an efficient way, leading to richer representations. The deep networks with our GM-SOP can be end-to-end trained, having potential to characterize complex, multi-modal distributions. The proposed method is evaluated on two large scale image benchmarks (i.e., downsampled ImageNet-1K and Places365), and experimental results show our GM-SOP is superior to its counterparts and achieves very competitive performance. The source code will be available at http://www.peihuali.org/GM-SOP.
Revisiting Multi-Task Learning with ROCK: a Deep Residual Auxiliary Block for Visual Detection
Authors: Taylor Mordan, Nicolas Thome, Gilles Henaff, Matthieu Cord
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Depth Estimation, Depth Prediction, Multi-Task Learning, object-detection, Object Detection, Scene Classification, Surface Normal Estimation

Multi-Task Learning (MTL) is appealing for deep learning regularization. In this paper, we tackle a specific MTL context denoted as primary MTL, where the ultimate goal is to improve the performance of a given primary task by leveraging several other auxiliary tasks. Our main methodological contribution is to introduce ROCK, a new generic multi-modal fusion block for deep learning tailored to the primary MTL context. ROCK architecture is based on a residual connection, which makes forward prediction explicitly impacted by the intermediate auxiliary representations. The auxiliary predictor's architecture is also specifically designed to our primary MTL context, by incorporating intensive pooling operators for maximizing complementarity of intermediate representations. Extensive experiments on NYUv2 dataset (object detection with scene classification, depth prediction, and surface normal estimation as auxiliary tasks) validate the relevance of the approach and its superiority to flat MTL approaches. Our method outperforms state-of-the-art object detection models on NYUv2 dataset by a large margin, and is also able to handle large-scale heterogeneous inputs (real and synthetic images) with missing annotation modalities.
Joint Active Feature Acquisition and Classification with Variable-Size Set Encoding
Authors: Hajin Shim, Sung Ju Hwang, Eunho Yang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: General Classification

We consider the problem of active feature acquisition where the goal is to sequentially select the subset of features in order to achieve the maximum prediction performance in the most cost-effective way at test time. In this work, we formulate this active feature acquisition as a jointly learning problem of training both the classifier (environment) and the RL agent that decides either to `stop and predict' or `collect a new feature' at test time, in a cost-sensitive manner. We also introduce a novel encoding scheme to represent acquired subsets of features by proposing an order-invariant set encoding at the feature level, which also significantly reduces the search space for our agent. We evaluate our model on a carefully designed synthetic dataset for the active feature acquisition as well as several medical datasets. Our framework shows meaningful feature acquisition process for diagnosis that complies with human knowledge, and outperforms all baselines in terms of prediction performance as well as feature acquisition cost.
Multitask Boosting for Survival Analysis with Competing Risks
Authors: Alexis Bellot, Mihaela van der Schaar
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Survival Analysis

The co-occurrence of multiple diseases among the general population is an important problem as those patients have more risk of complications and represent a large share of health care expenditure. Learning to predict time-to-event probabilities for these patients is a challenging problem because the risks of events are correlated (there are competing risks) with often only few patients experiencing individual events of interest, and of those only a fraction are actually observed in the data. We introduce in this paper a survival model with the flexibility to leverage a common representation of related events that is designed to correct for the strong imbalance in observed outcomes. The procedure is sequential: outcome-specific survival distributions form the components of nonparametric multivariate estimators which we combine into an ensemble in such a way as to ensure accurate predictions on all outcome types simultaneously. Our algorithm is general and represents the first boosting-like method for time-to-event data with multiple outcomes. We demonstrate the performance of our algorithm on synthetic and real data.
Geometry Based Data Generation
Authors: Ofir Lindenbaum, Jay Stanley, Guy Wolf, Smita Krishnaswamy
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Clustering

We propose a new type of generative model for high-dimensional data that learns a manifold geometry of the data, rather than density, and can generate points evenly along this manifold. This is in contrast to existing generative models that represent data density, and are strongly affected by noise and other artifacts of data collection. We demonstrate how this approach corrects sampling biases and artifacts, thus improves several downstream data analysis tasks, such as clustering and classification. Finally, we demonstrate that this approach is especially useful in biology where, despite the advent of single-cell technologies, rare subpopulations and gene-interaction relationships are affected by biased sampling. We show that SUGAR can generate hypothetical populations, and it is able to reveal intrinsic patterns and mutual-information relationships between genes on a single-cell RNA sequencing dataset of hematopoiesis.
Designing by Training: Acceleration Neural Network for Fast High-Dimensional Convolution
Authors: Longquan Dai, Liang Tang, Yuan Xie, Jinhui Tang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Vocal Bursts Intensity Prediction

The high-dimensional convolution is widely used in various disciplines but has a serious performance problem due to its high computational complexity. Over the decades, people took a handmade approach to design fast algorithms for the Gaussian convolution. Recently, requirements for various non-Gaussian convolutions have emerged and are continuously getting higher. However, the handmade acceleration approach is no longer feasible for so many different convolutions since it is a time-consuming and painstaking job. Instead, we propose an Acceleration Network (AccNet) which turns the work of designing new fast algorithms to training the AccNet. This is done by: 1, interpreting splatting, blurring, slicing operations as convolutions; 2, turning these convolutions to $g$CP layers to build AccNet. After training,  the activation function $g$ together with AccNet weights automatically define the new splatting, blurring and slicing operations. Experiments demonstrate AccNet is able to design acceleration algorithms for a ton of convolutions including Gaussian/non-Gaussian convolutions and produce state-of-the-art results.
Stochastic Composite Mirror Descent: Optimal Bounds with High Probabilities
Authors: Yunwen Lei, Ke Tang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Generalization Bounds, Vocal Bursts Intensity Prediction

We study stochastic composite mirror descent, a class of scalable algorithms able to exploit the geometry and composite structure of a problem. We consider both convex and strongly convex objectives with non-smooth loss functions, for each of which we establish high-probability convergence rates optimal up to a logarithmic factor. We apply the derived computational error bounds to study the generalization performance of multi-pass stochastic gradient descent (SGD) in a non-parametric setting. Our high-probability generalization bounds enjoy a logarithmical dependency on the number of passes provided that the step size sequence is square-summable, which improves the existing bounds in expectation with a polynomial dependency and therefore gives a strong justification on the ability of multi-pass SGD to overcome overfitting. Our analysis removes boundedness assumptions on subgradients often imposed in the literature. Numerical results are reported to support our theoretical findings.
Multi-Class Learning: From Theory to Algorithm
Authors: Jian Li, Yong liu, Rong Yin, Hua Zhang, Lizhong Ding, Weiping Wang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Classification, General Classification, Multi-class Classification

In this paper, we study the generalization performance of multi-class classification and obtain a shaper data-dependent generalization error bound with fast convergence rate, substantially improving the state-of-art bounds in the existing data-dependent generalization analysis. The theoretical analysis motivates us to devise two effective multi-class kernel learning algorithms with statistical guarantees. Experimental results show that our proposed methods can significantly outperform the existing multi-class classification methods.
Multivariate Time Series Imputation with Generative Adversarial Networks
Authors: Yonghong Luo, Xiangrui Cai, Ying Zhang, Jun Xu, Yuan Xiaojie
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Image Generation, Imputation, Missing Values, Multivariate Time Series Imputation, Time Series, Time Series Analysis

Multivariate time series usually contain a large number of missing values, which hinders the application of advanced analysis methods on multivariate time series data. Conventional approaches to addressing the challenge of missing values, including mean/zero imputation, case deletion, and matrix factorization-based imputation, are all incapable of modeling the temporal dependencies and the nature of complex distribution in multivariate time series. In this paper, we treat the problem of missing value imputation as data generation.  Inspired by the success of Generative Adversarial Networks (GAN) in image generation, we propose to learn the overall distribution of a multivariate time series dataset with GAN, which is further used to generate the missing values for each sample. Different from the image data, the time series data are usually incomplete due to the nature of data recording process. A modified Gate Recurrent Unit is employed in GAN to model the temporal irregularity of the incomplete time series. Experiments on two multivariate time series datasets show that the proposed model outperformed the baselines in terms of accuracy of imputation. Experimental results also showed that a simple model on the imputed data can achieve state-of-the-art results on the prediction tasks, demonstrating the benefits of our model in downstream applications.
Learning Versatile Filters for Efficient Convolutional Neural Networks
Authors: Yunhe Wang, Chang Xu, Chunjing Xu, Chao Xu, DaCheng Tao
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

This paper introduces versatile filters to construct efficient convolutional neural network. Considering the demands of efficient deep learning techniques running on cost-effective hardware, a number of methods have been developed to learn compact neural networks. Most of these works aim to slim down filters in different ways, e.g., investigating small, sparse or binarized filters. In contrast, we treat filters from an additive perspective. A series of secondary filters can be derived from a primary filter. These secondary filters all inherit in the primary filter without occupying more storage, but once been unfolded in computation they could significantly enhance the capability of the filter by integrating information extracted from different receptive fields. Besides spatial versatile filters, we additionally investigate versatile filters from the channel perspective. The new techniques are general to upgrade filters in existing CNNs. Experimental results on benchmark datasets and neural networks demonstrate that CNNs constructed with our versatile filters are able to achieve comparable accuracy as that of original filters, but require less memory and FLOPs.
Video Prediction via Selective Sampling
Authors: Jingwei Xu, Bingbing Ni, Xiaokang Yang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Multiple-choice, Prediction, Video Prediction

Most adversarial learning based video prediction methods suffer from image blur, since the commonly used adversarial and regression loss pair work rather in a competitive way than collaboration, yielding compromised blur effect. 
  In the meantime, as often relying on a single-pass architecture, the predictor is inadequate to explicitly capture the forthcoming uncertainty.
  Our work involves two key insights:
  (1) Video prediction can be approached as a stochastic process: we sample a collection of proposals conforming to possible frame distribution at following time stamp, and one can select the final prediction from it.
  (2) De-coupling combined loss functions into dedicatedly designed sub-networks encourages them to work in a collaborative way.
  Combining above two insights we propose a two-stage network called VPSS (\textbf{V}ideo \textbf{P}rediction via \textbf{S}elective \textbf{S}ampling).  
  Specifically a \emph{Sampling} module produces a collection of high quality proposals, facilitated by a multiple choice adversarial learning scheme, yielding diverse frame proposal set. 
  Subsequently a \emph{Selection} module selects high possibility candidates from proposals and combines them to produce final prediction.  
  Extensive experiments on diverse challenging datasets 
  demonstrate the effectiveness of proposed video prediction approach, i.e., yielding more diverse proposals and accurate prediction results.
Learning to Exploit Stability for 3D Scene Parsing
Authors: Yilun Du, Zhijian Liu, Hector Basevi, Ales Leonardis, Bill Freeman, Josh Tenenbaum, Jiajun Wu
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Scene Parsing, Scene Understanding, Translation

Human scene understanding uses a variety of visual and non-visual cues to perform inference on object types, poses, and relations. Physics is a rich and universal cue which we exploit to enhance scene understanding. We integrate the physical cue of stability into the learning process using a REINFORCE approach coupled to a physics engine, and apply this to the problem of producing the 3D bounding boxes and poses of objects in a scene. We first show that applying physics supervision to an existing scene understanding model increases performance, produces more stable predictions, and allows training to an equivalent performance level with fewer annotated training examples. We then present a novel architecture for 3D scene parsing named Prim R-CNN, learning to predict bounding boxes as well as their 3D size, translation, and rotation. With physics supervision, Prim R-CNN outperforms existing scene understanding approaches on this problem. Finally, we show that applying physics supervision on unlabeled real images improves real domain transfer of models training on synthetic data.
Genetic-Gated Networks for Deep Reinforcement Learning
Authors: Simyung Chang, John Yang, Jaeseok Choi, Nojun Kwak
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We introduce the Genetic-Gated Networks (G2Ns), simple neural networks that combine a gate vector composed of binary genetic genes in the hidden layer(s) of networks. Our method can take both advantages of gradient-free optimization and gradient-based optimization methods, of which the former is effective for problems with multiple local minima, while the latter can quickly find local minima. In addition, multiple chromosomes can define different models, making it easy to construct multiple models and can be effectively applied to problems that require multiple models. We show that this G2N can be applied to typical reinforcement learning algorithms to achieve a large improvement in sample efficiency and performance.
Fighting Boredom in Recommender Systems with Linear Reinforcement Learning
Authors: Romain Warlop, Alessandro Lazaric, Jérémie Mary
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Recommendation Systems, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

A common assumption in recommender systems (RS) is the existence of a best fixed recommendation strategy. Such strategy may be simple and work at the item level (e.g., in multi-armed bandit it is assumed one best fixed arm/item exists) or implement more sophisticated RS (e.g., the objective of A/B testing is to find the
best fixed RS and execute it thereafter). We argue that this assumption is rarely verified in practice, as the recommendation process itself may impact the user’s
preferences. For instance, a user may get bored by a strategy, while she may gain interest again, if enough time passed since the last time that strategy was used. In
this case, a better approach consists in alternating different solutions at the right frequency to fully exploit their potential. In this paper, we first cast the problem as
a Markov decision process, where the rewards are a linear function of the recent history of actions, and we show that a policy considering the long-term influence
of the recommendations may outperform both fixed-action and contextual greedy policies. We then introduce an extension of the UCRL algorithm ( L IN UCRL ) to
effectively balance exploration and exploitation in an unknown environment, and we derive a regret bound that is independent of the number of states. Finally,
we empirically validate the model assumptions and the algorithm in a number of realistic scenarios.
Temporal Regularization for Markov Decision Process
Authors: Pierre Thodoroff, Audrey Durand, Joelle Pineau, Doina Precup
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Atari Games, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Several applications of Reinforcement Learning suffer from instability due to high
variance. This is especially prevalent in high dimensional domains. Regularization
is a commonly used technique in machine learning to reduce variance, at the cost
of introducing some bias. Most existing regularization techniques focus on spatial
(perceptual) regularization. Yet in reinforcement learning, due to the nature of the
Bellman equation, there is an opportunity to also exploit temporal regularization
based on smoothness in value estimates over trajectories. This paper explores a
class of methods for temporal regularization. We formally characterize the bias
induced by this technique using Markov chain concepts. We illustrate the various
characteristics of temporal regularization via a sequence of simple discrete and
continuous MDPs, and show that the technique provides improvement even in
high-dimensional Atari games.
Simple random search of static linear policies is competitive for reinforcement learning
Authors: Horia Mania, Aurelia Guy, Benjamin Recht
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: continuous-control, Continuous Control, MuJoCo, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Model-free reinforcement learning aims to offer off-the-shelf solutions for controlling dynamical systems without requiring models of the system dynamics.  We introduce a model-free random search algorithm for training static, linear policies for continuous control problems. Common evaluation methodology shows that our method matches state-of-the-art sample efficiency on the benchmark MuJoCo locomotion tasks.  Nonetheless, more rigorous evaluation reveals that the assessment of performance on these benchmarks is optimistic. We evaluate the performance of our method over hundreds of random seeds and many different hyperparameter configurations for each benchmark task. This extensive evaluation is possible because of the small computational footprint of our method. Our simulations highlight a high variability in performance in these benchmark tasks, indicating that commonly used estimations of sample efficiency do not adequately evaluate the performance of RL algorithms. Our results stress the need for new baselines, benchmarks and evaluation methodology for RL algorithms.