mtybilly/Instruct2DS huggingface dataset:
Synthesizing Tasks for Block-based Programming
Authors: Umair Ahmed, Maria Christakis, Aleksandr Efremov, Nigel Fernandez, Ahana Ghosh, Abhik Roychoudhury, Adish Singla
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Block-based visual programming environments play a critical role in introducing computing concepts to K-12 students. One of the key pedagogical challenges in these environments is in designing new practice tasks for a student that match a desired level of difficulty and exercise specific programming concepts. In this paper, we formalize the problem of synthesizing visual programming tasks. In particular, given a reference visual task $\task^{in}$ and its solution code $\code^{in}$, we propose a novel methodology to automatically generate a set $\{(\task^{out}, \code^{out})\}$ of new tasks along with solution codes such that tasks $\task^{in}$ and $\task^{out}$ are conceptually similar but visually dissimilar.  Our methodology is based on the realization that the mapping from the space of visual tasks to their solution codes is highly discontinuous; hence, directly mutating reference task $\task^{in}$ to generate new tasks is futile. Our task synthesis algorithm operates by first mutating code $\code^{in}$  to obtain a set of codes $\{\code^{out}\}$. Then, the algorithm performs symbolic execution over a code $\code^{out}$ to obtain a visual task $\task^{out}$; this step uses the Monte Carlo Tree Search (MCTS) procedure to guide the search in the symbolic tree. We demonstrate the effectiveness of our algorithm through an extensive empirical evaluation and user study on reference tasks taken from the Hour of Code: Classic Maze challenge by Code.org and the Intro to Programming with Karel course by CodeHS.com.
Scalable Belief Propagation via Relaxed Scheduling
Authors: Vitalii Aksenov, Dan Alistarh, Janne H. Korhonen
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been considerable effort invested into developing efficient parallel variants of classic machine learning algorithms. However, despite the wealth of knowledge on parallelization, some classic machine learning algorithms often prove hard to parallelize efficiently while maintaining convergence.

In this paper, we focus on efficient parallel algorithms for the key machine learning task of inference on graphical models, in particular on the fundamental belief propagation algorithm. We address the challenge of efficiently parallelizing this classic paradigm by showing how to leverage scalable relaxed schedulers, which reduce parallelization overheads, in this context. We investigate the overheads of relaxation analytically, and present an extensive empirical study, showing that our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time, on a range of practical applications.
Firefly Neural Architecture Descent: a General Approach for Growing Neural Networks
Authors: Lemeng Wu, Bo Liu, Peter Stone, Qiang Liu
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: We propose firefly neural architecture descent, a general framework for progressively and dynamically growing neural networks to jointly optimize the networks' parameters and architectures. Our method works in a steepest descent fashion, which iteratively finds the best network within a functional neighborhood of the original network that includes a diverse set of candidate network structures. By using Taylor approximation, the optimal network structure in the neighborhood can be found with a greedy selection procedure. We show that firefly descent can flexibly grow networks both wider and deeper, and can be applied to learn accurate but resource-efficient neural architectures that avoid catastrophic forgetting in continual learning. Empirically, firefly descent achieves promising results on both neural architecture search and continual learning. In particular, on a challenging continual image classification task, it learns networks that are smaller in size but have higher average accuracy than those learned by the state-of-the-art methods.
Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
Authors: Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, Qiaomin Xie
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: We study risk-sensitive reinforcement learning in episodic Markov decision processes with unknown transition kernels, where the goal is to optimize the total reward under the risk measure of exponential utility. We propose two provably efficient model-free algorithms, Risk-Sensitive Value Iteration (RSVI) and Risk-Sensitive Q-learning (RSQ). These algorithms implement a form of risk-sensitive optimism in the face of uncertainty, which adapts to both risk-seeking and risk-averse modes of exploration. We prove that RSVI attains an \ensuremath{\tilde{O}\big(\lambda(|\beta| H^2) \cdot \sqrt{H^{3} S^{2}AT} \big)}$ regret, while RSQ attains an $\ensuremath{\tilde{O}\big(\lambda(|\beta| H^2) \cdot \sqrt{H^{4} SAT} \big)}$ regret, where $\lambda(u) = (e^{3u}-1)/u$ for $u>0$. In the above, $\beta$ is the risk parameter of the exponential utility function, $S$ the number of states, $A$ the number of actions,  $T$ the total number of timesteps, and $H$ the episode length. On the flip side, we establish a regret lower bound showing that the exponential dependence on $|\beta|$ and $H$ is unavoidable for any algorithm with an $\tilde{O}(\sqrt{T})$ regret (even when the risk objective is on the same scale as the original reward), thus certifying the near-optimality of the proposed algorithms. Our results demonstrate that incorporating risk awareness into reinforcement learning necessitates an exponential cost in $|\beta|$ and $H$,   which quantifies the fundamental tradeoff between risk sensitivity (related to aleatoric uncertainty) and sample efficiency (related to epistemic uncertainty). To the best of our knowledge, this is the first regret analysis of risk-sensitive reinforcement learning with the exponential utility.
Learning to Decode: Reinforcement Learning for Decoding of Sparse Graph-Based Channel Codes
Authors: Salman Habib, Allison Beemer, Joerg Kliewer
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: We show in this work that reinforcement learning can be successfully applied to decoding short to moderate length sparse graph-based channel codes. Specifically, we focus on low-density parity check (LDPC) codes, which for example have been standardized in the context of 5G cellular communication systems due to their excellent error correcting performance. These codes are typically decoded via belief propagation iterative decoding on the corresponding bipartite (Tanner) graph of the code via flooding, i.e., all check and variable nodes in the Tanner graph are updated at once. In contrast, in this paper we utilize a sequential update policy which selects the optimum check node (CN) scheduling in order to improve decoding performance. In particular, we model the CN update process as a multi-armed bandit process with dependent arms and employ a Q-learning scheme for optimizing the CN scheduling policy. In order to reduce the learning complexity, we propose a novel graph-induced CN clustering approach to partition the state space in such a way that dependencies between clusters are minimized. Our results show that compared to other decoding approaches from the literature, the proposed reinforcement learning scheme not only significantly improves the decoding performance, but also reduces the decoding complexity dramatically once
the scheduling policy is learned.
Faster DBSCAN via subsampled similarity queries
Authors: Heinrich Jiang, Jennifer Jang, Jakub Lacki
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: DBSCAN is a popular density-based clustering algorithm. It computes the $\epsilon$-neighborhood graph of a dataset and uses the connected components of the high-degree nodes to decide the clusters. However, the full neighborhood graph may be too costly to compute with a worst-case complexity of $O(n^2)$. In this paper, we propose a simple variant called SNG-DBSCAN, which clusters based on a subsampled $\epsilon$-neighborhood graph, only requires access to similarity queries for pairs of points and in particular avoids any complex data structures which need the embeddings of the data points themselves. The runtime of the procedure is $O(sn^2)$, where $s$ is the sampling rate. We show under some natural theoretical assumptions that $s \approx \log n/n$ is sufficient for statistical cluster recovery guarantees leading to an $O(n\log n)$ complexity. We provide an extensive experimental analysis showing that on large datasets, one can subsample as little as $0.1\%$ of the neighborhood graph, leading to as much as over 200x speedup and 250x reduction in RAM consumption compared to scikit-learn's implementation of DBSCAN, while still maintaining competitive clustering performance.
De-Anonymizing Text by Fingerprinting Language Generation
Authors: Zhen Sun, Roei Schuster, Vitaly Shmatikov
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Components of machine learning systems are not (yet) perceived as security hotspots.  Secure coding practices, such as ensuring that no execution paths depend on confidential inputs, have not yet been adopted by ML developers.  We initiate the study of code security of ML systems by investigating how nucleus sampling---a popular approach for generating text, used for applications such as auto-completion---unwittingly leaks texts typed by users. Our main result is that the series of nucleus sizes for many natural English word sequences is a unique fingerprint.  We then show how an attacker can infer typed text by measuring these fingerprints via a suitable side channel (e.g., cache access times), explain how this attack could help de-anonymize anonymous texts, and discuss defenses.
Multiparameter Persistence Image for Topological Machine Learning
Authors: Mathieu Carrière, Andrew Blumberg
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: In the last decade, there has been increasing interest in topological
data analysis, a new methodology for using geometric structures in
data for inference and learning. A central theme in the area is the
idea of persistence, which in its most basic form studies how measures
of shape change as a scale parameter varies. There are now a number of
frameworks that support statistics and machine learning in this
context. However, in many applications there are several different
parameters one might wish to vary: for example, scale and density.  In
contrast to the one-parameter setting, techniques for applying
statistics and machine learning in the setting of multiparameter
persistence are not well understood due to the lack of a concise
representation of the results.
We introduce a new descriptor for multiparameter persistence, which we
call the Multiparameter Persistence Image, that is suitable for
machine learning and statistical frameworks, is robust to
perturbations in the data, has finer resolution than existing
descriptors based on slicing, and can be efficiently computed on data
sets of realistic size.  Moreover, we demonstrate its efficacy by
comparing its performance to other multiparameter descriptors on
several classification tasks.
Matrix Inference and Estimation in Multi-Layer Models
Authors: Parthe Pandit, Mojtaba Sahraee Ardakan, Sundeep Rangan, Philip Schniter, Alyson K. Fletcher
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: We consider the problem of estimating the input and hidden variables of a stochastic multi-layer neural network from an observation of the output.  The hidden variables in each layer are represented as matrices with statistical interactions along both rows as well as columns. This problem applies to matrix imputation, signal recovery via deep generative prior models, multi-task and mixed regression, and learning certain classes of two-layer neural networks. We extend a recently-developed algorithm -- Multi-Layer Vector Approximate Message Passing (ML-VAMP), for this matrix-valued inference problem. It is shown that the performance of the proposed Multi-Layer Matrix VAMP (ML-Mat-VAMP) algorithm can be exactly predicted in a certain random large-system limit, where the dimensions $N\times d$ of the unknown quantities grow as $N\rightarrow\infty$ with $d$ fixed. In the two-layer neural-network learning problem, this scaling corresponds to the case where the number of input features, as well as training samples, grow to infinity but the number of hidden nodes stays fixed. The analysis enables a precise prediction of the parameter and test error of the learning.
MeshSDF: Differentiable Iso-Surface Extraction
Authors: Edoardo Remelli, Artem Lukoianov, Stephan Richter, Benoit Guillard, Timur Bagautdinov, Pierre Baque, Pascal Fua
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Geometric Deep Learning has recently made striking progress with the advent of continuous Deep Implicit Fields. They allow for detailed modeling of watertight surfaces of arbitrary topology while not relying on a 3D Euclidean grid, resulting in a learnable parameterization that is not limited in resolution. 
Unfortunately, these methods are often not suitable for applications that require an explicit mesh-based surface representation because converting an implicit field to such a representation relies on the Marching Cubes algorithm, which cannot be differentiated with respect to the underlying implicit field.
In this work, we remove this limitation and introduce a differentiable way to produce explicit surface mesh representations from Deep Signed Distance Functions. Our key insight is that by reasoning on how implicit field perturbations impact local surface geometry, one can ultimately differentiate the 3D location of surface samples with respect to the underlying deep implicit field. We exploit this to define MeshSDF, an end-to-end differentiable mesh representation which can vary its topology.
We use two different applications to validate our theoretical insight: Single-View Reconstruction via Differentiable Rendering and Physically-Driven Shape Optimization. In both cases our differentiable parameterization gives us an edge over state-of-the-art algorithms.
Variational Interaction Information Maximization for Cross-domain Disentanglement
Authors: HyeongJoo Hwang, Geon-Hyeong Kim, Seunghoon Hong, Kee-Eung Kim
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Cross-domain disentanglement is the problem of learning representations partitioned into domain-invariant and domain-specific representations, which is a key to successful domain transfer or measuring semantic distance between two domains. Grounded in information theory, we cast the simultaneous learning of domain-invariant and domain-specific representations as a joint objective of multiple information constraints, which does not require adversarial training or gradient reversal layers. We derive a tractable bound of the objective and propose a generative model named Interaction Information Auto-Encoder (IIAE). Our approach reveals insights on the desirable representation for cross-domain disentanglement and its connection to Variational Auto-Encoder (VAE). We demonstrate the validity of our model in the image-to-image translation and the cross-domain retrieval tasks. We further show that our model achieves the state-of-the-art performance in the zero-shot sketch based image retrieval task, even without external knowledge.
Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
Authors: Fei Feng, Ruosong Wang, Wotao Yin, Simon S Du, Lin Yang
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Motivated by the prevailing paradigm of using unsupervised learning for efficient exploration in reinforcement learning (RL) problems [tang2017exploration,bellemare2016unifying], we investigate when this paradigm is provably efficient. We study episodic Markov decision processes with rich observations generated from a small number of latent states. We present a general algorithmic framework that is built upon two components: an unsupervised learning algorithm and a no-regret tabular RL algorithm. Theoretically, we prove that as long as the unsupervised learning algorithm enjoys a polynomial sample complexity guarantee, we can find a near-optimal policy with sample complexity polynomial in the number of latent states, which is significantly smaller than the number of observations. Empirically, we instantiate our framework on a class of hard exploration problems to demonstrate the practicality of our theory.
Faithful Embeddings for Knowledge Base Queries
Authors: Haitian Sun, Andrew Arnold, Tania Bedrax Weiss, Fernando Pereira, William W. Cohen
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: The deductive closure of an ideal knowledge base (KB) contains exactly the logical queries that the KB can answer. However, in practice KBs are both incomplete and over-specified, failing to answer some queries that have real-world answers. \emph{Query embedding} (QE) techniques have been recently proposed where KB entities and KB queries are represented jointly in an embedding space, supporting relaxation and generalization in KB inference. However, experiments in this paper show that QE systems may disagree with deductive reasoning on answers that do not require generalization or relaxation.  We address this problem with a novel QE method that is more faithful to deductive reasoning, and show that this leads to better performance on complex queries to incomplete KBs. Finally we show that inserting this new QE module into a neural question-answering system leads to substantial improvements over the state-of-the-art.
Wasserstein Distances for Stereo Disparity Estimation
Authors: Divyansh Garg, Yan Wang, Bharath Hariharan, Mark Campbell, Kilian Q. Weinberger, Wei-Lun Chao
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Existing approaches to depth or disparity estimation output a distribution over a set of pre-defined discrete values. This leads to inaccurate results when the true depth or disparity does not match any of these values. The fact that this distribution is usually learned indirectly through a regression loss causes further problems in ambiguous regions around object boundaries. We address these issues using a new neural network architecture that is capable of outputting arbitrary depth values, and a new loss function that is derived from the Wasserstein distance between the true and the predicted distributions. We validate our approach on a variety of tasks, including stereo disparity and depth estimation, and the downstream 3D object detection. Our approach drastically reduces the error in ambiguous regions, especially around object boundaries that greatly affect the localization of objects in 3D, achieving the state-of-the-art in 3D object detection for autonomous driving.
Multi-agent Trajectory Prediction with Fuzzy Query Attention
Authors: Nitin Kamra, Hao Zhu, Dweep Kumarbhai Trivedi, Ming Zhang, Yan Liu
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Trajectory prediction for scenes with multiple agents and entities is a challenging problem in numerous domains such as traffic prediction, pedestrian tracking and path planning. We present a general architecture to address this challenge which models the crucial inductive biases of motion, namely, inertia, relative motion, intents and interactions. Specifically, we propose a relational model to flexibly model interactions between agents in diverse environments. Since it is well-known that human decision making is fuzzy by nature, at the core of our model lies a novel attention mechanism which models interactions by making continuous-valued (fuzzy) decisions and learning the corresponding responses. Our architecture demonstrates significant performance gains over existing state-of-the-art predictive models in diverse domains such as human crowd trajectories, US freeway traffic, NBA sports data and physics datasets. We also present ablations and augmentations to understand the decision-making process and the source of gains in our model.
Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping
Authors: Shashanka Ubaru, Sanjeeb Dash, Arya Mazumdar, Oktay Gunluk
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: In modern  multilabel classification problems, each data instance  belongs  to  a small number of classes among a large  set of  classes. In other words, these problems involve learning very sparse binary label  vectors. Moreover, in the large-scale problems, the labels typically have certain (unknown) hierarchy. In this paper we exploit the sparsity of label vectors and the hierarchical structure to embed them in low-dimensional space using label groupings. Consequently, we solve the classification problem in a much lower dimensional space and then obtain labels in the original space using an appropriately defined lifting. Our method builds on the work of (Ubaru & Mazumdar, 2017), where the idea of group testing was also explored for multilabel classification. We first present a novel data-dependent grouping approach, where we use a  group construction based on a low-rank Nonnegative Matrix Factorization (NMF) of the label matrix of training instances.
The construction also allows us, using recent results,  to develop a fast prediction algorithm that has a  \emph{logarithmic runtime in the number of labels}. We then present a hierarchical partitioning approach that exploits the label hierarchy in large-scale problems to divide the large label space into smaller sub-problems, which can then be solved independently via the grouping approach. Numerical results on many benchmark datasets illustrate that, compared to other popular methods, our proposed methods achieve comparable accuracy with significantly lower computational costs.
An Analysis of SVD for Deep Rotation Estimation
Authors: Jake Levinson, Carlos Esteves, Kefan Chen, Noah Snavely, Angjoo Kanazawa, Afshin Rostamizadeh, Ameesh Makadia
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Symmetric orthogonalization via SVD, and closely related procedures, are well-known techniques for projecting matrices onto O(n) or SO(n). These tools have long been used for applications in computer vision, for example optimal 3D alignment problems solved by orthogonal Procrustes, rotation averaging, or Essential matrix decomposition. Despite its utility in different settings, SVD orthogonalization as a procedure for producing rotation matrices is typically overlooked in deep learning models, where the preferences tend toward classic representations like unit quaternions, Euler angles, and axis-angle, or more recently-introduced methods. Despite the importance of 3D rotations in computer vision and robotics, a single universally effective representation is still missing. Here, we explore the viability of SVD orthogonalization for 3D rotations in neural networks. We present a theoretical analysis of SVD as used for projection onto the rotation group. Our extensive quantitative analysis shows simply replacing existing representations with the SVD orthogonalization procedure obtains state of the art performance in many deep learning applications covering both supervised and unsupervised training.
Can the Brain Do Backpropagation? --- Exact Implementation of Backpropagation in Predictive Coding Networks
Authors: Yuhang Song, Thomas Lukasiewicz, Zhenghua Xu, Rafal Bogacz
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Backpropagation (BP) has been the most successful algorithm used to train artificial neural networks. However, there are several gaps between BP and learning in biologically plausible neuronal networks of the brain (learning in the brain, or simply BL, for short), in particular, (1) it has been unclear to date, if BP can be implemented exactly via BL, (2) there is a lack of local plasticity in BP, i.e., weight updates require information that is not locally available, while BL utilizes only locally available information, and (3)~there is a lack of autonomy in BP, i.e., some external control over the neural network is required (e.g., switching between prediction and learning stages requires changes to dynamics and synaptic plasticity rules), while BL works fully autonomously. Bridging such gaps, i.e., understanding how BP can be approximated by BL, has been of major interest in both neuroscience and machine learning. Despite tremendous efforts, however, no previous model has bridged the gaps at a degree of demonstrating an equivalence to BP, instead, only approximations to BP have been shown. Here, we present for the first time a framework within BL that bridges the above crucial gaps. We propose a BL model that (1) produces \emph{exactly the same} updates of the neural weights as~BP, while (2)~employing local plasticity, i.e., all neurons perform only local computations, done simultaneously. We then modify it to an alternative BL model that (3) also works fully autonomously. Overall, our work provides important evidence for the debate on the long-disputed question whether the brain can perform~BP.
Manifold GPLVMs for discovering non-Euclidean latent structure in neural data
Authors: Kristopher Jensen, Ta-Chu Kao, Marco Tripodi, Guillaume Hennequin
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: A common problem in neuroscience is to elucidate the collective neural representations of behaviorally important variables such as head direction, spatial location, upcoming movements, or mental spatial transformations. Often, these latent variables are internal constructs not directly accessible to the experimenter. Here, we propose a new probabilistic latent variable model to simultaneously identify the latent state and the way each neuron contributes to its representation in an unsupervised way. In contrast to previous models which assume Euclidean latent spaces, we embrace the fact that latent states often belong to symmetric manifolds such as spheres, tori, or rotation groups of various dimensions. We therefore propose the manifold Gaussian process latent variable model (mGPLVM), where neural responses arise from (i) a shared latent variable living on a specific manifold, and (ii) a set of non-parametric tuning curves determining how each neuron contributes to the representation. Cross-validated comparisons of models with different topologies can be used to distinguish between candidate manifolds, and variational inference enables quantification of uncertainty. We demonstrate the validity of the approach on several synthetic datasets, as well as on calcium recordings from the ellipsoid body of Drosophila melanogaster and extracellular recordings from the mouse anterodorsal thalamic nucleus. These circuits are both known to encode head direction, and mGPLVM correctly recovers the ring topology expected from neural populations representing a single angular variable.
Distributed Distillation for On-Device Learning
Authors: Ilai Bistritz, Ariana Mann, Nicholas Bambos
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: On-device learning promises collaborative training of machine learning models across edge devices without the sharing of user data. In state-of-the-art on-device learning algorithms, devices communicate their model weights over a decentralized communication network. Transmitting model weights requires huge communication overhead and means only devices with identical model architectures can be included. To overcome these limitations, we introduce a distributed distillation algorithm where devices communicate and learn from soft-decision (softmax) outputs, which are inherently architecture-agnostic and scale only with the number of classes. The communicated soft-decisions are each model's outputs on a public, unlabeled reference dataset, which serves as a common vocabulary between devices. We prove that our algorithm converges with probability 1 to a stationary point where all devices in the communication network distill the entire network's knowledge on the reference data, regardless of their local connections. Our analysis assumes smooth loss functions, which can be non-convex. Simulations support our theoretical findings and show that even a naive implementation of our algorithm significantly reduces the communication overhead while achieving an overall comparable performance to state-of-the-art, depending on the regime. By requiring little communication overhead and allowing for cross-architecture training, we remove two main obstacles to scaling on-device learning.
COOT: Cooperative Hierarchical Transformer for Video-Text Representation Learning
Authors: Simon Ging, Mohammadreza Zolfaghari, Hamed Pirsiavash, Thomas Brox
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Many real-world video-text tasks involve different levels of granularity, such as frames and words, clip and sentences or videos and paragraphs, each with distinct semantics. In this paper, we propose a Cooperative hierarchical Transformer (COOT) to leverage this hierarchy information and model the interactions between different levels of granularity and different modalities. The method consists of three major components: an attention-aware feature aggregation layer, which leverages the local temporal context (intra-level, e.g., within a clip), a contextual transformer to learn the interactions between low-level and high-level semantics (inter-level, e.g. clip-video, sentence-paragraph), and a cross-modal cycle-consistency loss to connect video and text. The resulting method compares favorably to the state of the art on several benchmarks while having few parameters.
Passport-aware Normalization for Deep Model Protection
Authors: Jie Zhang, Dongdong Chen, Jing Liao, Weiming Zhang, Gang Hua, Nenghai Yu
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Despite tremendous success in many application scenarios, deep learning faces serious intellectual property (IP) infringement threats. Considering the cost of designing and training a good model, infringements will significantly infringe the interests of the original model owner. Recently, many impressive works have emerged for deep model IP protection. However, they either are vulnerable to ambiguity attacks, or require changes in the target network structure by replacing its original normalization layers and hence cause significant performance drops. To this end, we propose a new passport-aware normalization formulation, which is generally applicable to most existing normalization layers and only needs to add another passport-aware branch for IP protection. This new branch is jointly trained with the target model but discarded in the inference stage. Therefore it causes no structure change in the target model. Only when the model IP is suspected to be stolen by someone, the private passport-aware branch is added back for ownership verification. Through extensive experiments, we verify its effectiveness in both image and 3D point recognition models. It is demonstrated to be robust not only to common attack techniques like fine-tuning and model compression, but also to ambiguity attacks. By further combining it with trigger-set based methods, both black-box and white-box verification can be achieved for enhanced security of deep learning models deployed in real systems.
Sampling-Decomposable Generative Adversarial Recommender
Authors: Binbin Jin, Defu Lian, Zheng Liu, Qi Liu, Jianhui Ma, Xing Xie, Enhong Chen
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Recommendation techniques are important approaches for alleviating information overload. Being often trained on implicit user feedback, many recommenders suffer from the sparsity challenge due to the lack of explicitly negative samples. The GAN-style recommenders (i.e., IRGAN) addresses the challenge by learning a generator and a discriminator adversarially, such that the generator produces increasingly difficult samples for the discriminator to accelerate optimizing the discrimination objective. However, producing samples from the generator is very time-consuming, and our empirical study shows that the discriminator performs poor in top-k item recommendation. To this end, a theoretical analysis is made for the GAN-style algorithms, showing that the generator of limit capacity is diverged from the optimal generator. This may interpret the limitation of discriminator's performance. Based on these findings, we propose a Sampling-Decomposable Generative Adversarial Recommender (SD-GAR). In the framework, the divergence between some generator and the optimum is compensated by self-normalized importance sampling; the efficiency of sample generation is improved with a sampling-decomposable generator, such that each sample can be generated in O(1) with the Vose-Alias method. Interestingly, due to decomposability of sampling, the generator can be optimized with the closed-form solutions in an alternating manner, being different from policy gradient in the GAN-style algorithms. We extensively evaluate the proposed algorithm with five real-world recommendation datasets. The results show that SD-GAR outperforms IRGAN by 12.4% and the SOTA recommender by 10% on average. Moreover, discriminator training can be 20x faster on the dataset with more than 120K items.
Limits to Depth Efficiencies of Self-Attention
Authors: Yoav Levine, Noam Wies, Or Sharir, Hofit Bata, Amnon Shashua
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Self-attention architectures, which are rapidly pushing the frontier in natural language processing, demonstrate a surprising depth-inefficient behavior: Empirical signals indicate that increasing the internal representation (network width) is just as useful as increasing the number of self-attention layers (network depth). In this paper, we theoretically study the interplay between depth and width in self-attention. We shed light on the root of the above phenomenon, and establish two distinct parameter regimes of depth efficiency and inefficiency in self-attention. We invalidate the seemingly plausible hypothesis by which widening is as effective as deepening for self-attention, and show that in fact stacking self-attention layers is so effective that it quickly saturates a capacity of the network width. Specifically, we pinpoint a ``depth threshold" that is logarithmic in the network width: for networks of depth that is below the threshold, we establish a double-exponential depth-efficiency of the self-attention operation, while for depths over the threshold we show that depth-inefficiency kicks in. Our predictions accord with existing empirical ablations, and we further demonstrate the two depth-(in)efficiency regimes experimentally for common network depths of 6, 12, and 24. By identifying network width as a limiting factor, our analysis indicates that solutions for dramatically increasing the width can facilitate the next leap in self-attention expressivity.
Who Does What? A Novel Algorithm to Determine Function Localization
Authors: Ranit Aharonov-Barki, Isaac Meilijson, Eytan Ruppin
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  introduce  a  novel  algorithm,  termed  PPA  (Performance  Prediction  Algorithm),  that  quantitatively  measures  the  contributions  of elements  of a neural system to  the tasks it performs.  The algorithm identifies the  neurons or areas which participate in a cognitive or behavioral task, given  data about performance decrease in a small set of lesions.  It also allows  the  accurate  prediction  of performances  due  to  multi-element  lesions.  The effectiveness  of the  new  algorithm is  demonstrated  in  two  models  of recurrent neural  networks with  complex interactions among  the ele(cid:173) ments.  The algorithm is  scalable and applicable to  the  analysis of large  neural  networks.  Given  the  recent advances  in  reversible  inactivation  techniques,  it has  the  potential  to  significantly  contribute  to  the  under(cid:173) standing of the  organization of biological nervous systems, and to  shed  light on  the  long-lasting debate about local  versus distributed computa(cid:173) tion in the brain.
Overfitting in Neural Nets: Backpropagation, Conjugate Gradient, and Early Stopping
Authors: Rich Caruana, Steve Lawrence, C. Lee Giles
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The conventional wisdom is that backprop nets with excess hidden units  generalize  poorly.  We  show  that  nets  with  excess  capacity  generalize  well when  trained with backprop and early  stopping.  Experiments  sug(cid:173) gest two reasons for this:  1) Overfitting can vary significantly in different  regions of the model.  Excess capacity allows better fit to regions of high  non-linearity,  and  backprop often  avoids  overfitting  the  regions  of low  non-linearity.  2)  Regardless  of size,  nets  learn  task  subcomponents  in  similar sequence.  Big nets pass  through stages  similar to those learned  by  smaller nets.  Early  stopping can  stop training the large net  when  it  generalizes  comparably  to  a  smaller net.  We  also  show  that conjugate  gradient can yield worse generalization because it overfits regions of low  non-linearity when learning to fit regions of high non-linearity.
Learning Segmentation by Random Walks
Authors: Marina Meila, Jianbo Shi
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We present a new view of image segmentation by pairwise simi(cid:173) larities. We interpret the similarities as edge flows in a Markov  random walk and study the eigenvalues and eigenvectors of the  walk's transition matrix. This interpretation shows that spectral  methods for clustering and segmentation have a probabilistic foun(cid:173) dation. In particular, we prove that the Normalized Cut method  arises naturally from our framework. Finally, the framework pro(cid:173) vides a principled method for learning the similarity function as a  combination of features.
A PAC-Bayesian Margin Bound for Linear Classifiers: Why SVMs work
Authors: Ralf Herbrich, Thore Graepel
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present a  bound on the generalisation error of linear classifiers  in  terms  of  a  refined  margin  quantity  on  the  training  set.  The  result  is  obtained  in  a  PAC- Bayesian framework  and  is  based  on  geometrical  arguments  in  the space of linear  classifiers.  The  new  bound constitutes an exponential improvement of the so far tightest  margin bound by Shawe-Taylor et al.  [8]  and scales logarithmically  in  the inverse margin.  Even  in  the case  of less  training  examples  than input dimensions sufficiently large margins lead to non-trivial  bound values and - plexity  term.  Furthermore,  the  classical  margin  is  too  coarse  a  measure for  the  essential  quantity  that controls the generalisation  error:  the  volume  ratio  between  the  whole  hypothesis  space  and  the subset of consistent hypotheses.  The practical relevance of the  result  lies  in the fact  that the well-known support vector machine  is optimal w.r.t. the new bound only if the feature vectors are all of  the same length.  As a consequence we recommend to use SVMs on  normalised feature  vectors only - a  recommendation that is  well  supported  by our  numerical experiments on two  benchmark  data  sets. 
for maximum margins -
to a  vanishing com(cid:173)
Active Learning for Parameter Estimation in Bayesian Networks
Authors: Simon Tong, Daphne Koller
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Bayesian  networks  are  graphical  representations  of probability  distributions.  In  virtually  all  of the  work  on  learning  these  networks,  the  assumption  is  that  we  are  presented  with  a data  set consisting  of randomly  generated instances  from  the  underlying  distribution.  In  many  situations, however, we  also  have  the  option  of active  learning, where  we  have  the  possibility of guiding the  sampling process by  querying  for certain types  of samples.  This  paper addresses the problem of estimating the parameters of Bayesian networks in  an  active  learning  setting.  We  provide  a  theoretical  framework  for  this  problem,  and  an  algorithm  that chooses  which  active  learning  queries  to  generate  based  on  the  model  learned  so  far.  We present experimental results showing that our active learning algorithm can significantly  reduce the need for training data in  many situations.
A Tighter Bound for Graphical Models
Authors: Martijn A. R. Leisink, Hilbert J. Kappen
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  a  method to bound  the  partition function  of a  Boltz(cid:173) mann machine neural network with any odd order polynomial. This  is  a  direct  extension  of the mean field  bound,  which  is  first  order.  We  show  that  the  third  order  bound  is  strictly  better  than  mean  field.  Additionally  we  show  the  rough  outline  how  this  bound  is  applicable  to  sigmoid belief networks.  Numerical  experiments  in(cid:173) dicate  that  an error  reduction  of a  factor  two  is  easily  reached  in  the region  where  expansion based  approximations are  useful.
Occam's Razor
Authors: Carl Edward Rasmussen, Zoubin Ghahramani
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The Bayesian paradigm apparently only sometimes gives rise to Occam's  Razor;  at  other times  very  large models perform well.  We  give  simple  examples of both kinds of behaviour. The two views are reconciled when  measuring complexity of functions, rather than of the machinery used to  implement them.  We analyze the complexity of functions for some linear  in the parameter models that are  equivalent to  Gaussian Processes, and  always find Occam's Razor at work.
Exact Solutions to Time-Dependent MDPs
Authors: Justin A. Boyan, Michael L. Littman
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  describe an extension of the Markov decision process model in  which  a  continuous time  dimension  is  included in  the state space.  This  allows  for  the  representation  and  exact  solution  of  a  wide  range of problems in  which  transitions or rewards  vary over time.  We  examine  problems based on  route planning with  public trans(cid:173) portation and telescope observation scheduling.
An Information Maximization Approach to Overcomplete and Recurrent Representations
Authors: Oren Shriki, Haim Sompolinsky, Daniel D. Lee
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The principle of maximizing mutual  information is  applied to  learning  overcomplete and recurrent representations.  The underlying model con(cid:173) sists  of a network of input units driving a larger number of output units  with recurrent interactions.  In the limit of zero noise, the network is de(cid:173) terministic  and  the mutual information can be related  to  the  entropy  of  the output units.  Maximizing this entropy with respect to  both the feed(cid:173) forward connections as well as the recurrent interactions results in simple  learning rules for both sets of parameters.  The conventional independent  components (ICA) learning algorithm can be recovered as a special case  where  there  is  an  equal  number of output  units  and  no  recurrent  con(cid:173) nections.  The application of these new  learning rules is  illustrated on a  simple two-dimensional input example.
A Linear Programming Approach to Novelty Detection
Authors: Colin Campbell, Kristin P. Bennett
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Novelty detection involves modeling the normal behaviour of a sys(cid:173) tem hence  enabling detection of any divergence from normality.  It  has  potential applications in  many areas  such  as  detection  of ma(cid:173) chine  damage  or  highlighting  abnormal features  in  medical data.  One  approach  is  to  build  a  hypothesis  estimating  the  support  of  the normal data i.e. constructing a function which is positive in the  region  where  the  data is  located  and  negative elsewhere.  Recently  kernel  methods  have  been  proposed  for  estimating the  support  of  a  distribution  and  they  have  performed well  in  practice - training  involves solution of a  quadratic programming problem.  In this pa(cid:173) per we propose a simpler kernel method for  estimating the support  based  on  linear  programming.  The  method  is  easy  to  implement  and  can learn large  datasets rapidly.  We  demonstrate the method  on medical and fault detection datasets. 
1
Programmable Reinforcement Learning Agents
Authors: David Andre, Stuart J. Russell
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We present an expressive agent design language for reinforcement learn(cid:173) ing that allows the user to constrain the policies considered by the learn(cid:173) ing process.The language includes standard features  such as  parameter(cid:173) ized subroutines, temporary interrupts, aborts, and memory variables, but  also  allows  for  unspecified choices  in  the  agent program.  For learning  that which isn't specified, we present provably convergent learning algo(cid:173) rithms.  We  demonstrate by  example that agent programs written in the  language are concise as well as modular.  This facilitates state abstraction  and the transferability of learned skills.