pwc-archive/papers-with-abstracts huggingface dataset:
On Sparse High-Dimensional Graphical Model Learning For Dependent Time Series
Authors: Jitendra K. Tugnait
Date: 2021-11-15 00:00:00
Tasks: Time Series, Time Series Analysis, Vocal Bursts Intensity Prediction

We consider the problem of inferring the conditional independence graph (CIG) of a sparse, high-dimensional stationary multivariate Gaussian time series. A sparse-group lasso-based frequency-domain formulation of the problem based on frequency-domain sufficient statistic for the observed time series is presented. We investigate an alternating direction method of multipliers (ADMM) approach for optimization of the sparse-group lasso penalized log-likelihood. We provide sufficient conditions for convergence in the Frobenius norm of the inverse PSD estimators to the true value, jointly across all frequencies, where the number of frequencies are allowed to increase with sample size. This results also yields a rate of convergence. We also empirically investigate selection of the tuning parameters based on Bayesian information criterion, and illustrate our approach using numerical examples utilizing both synthetic and real data.
Choose Your Programming Copilot: A Comparison of the Program Synthesis Performance of GitHub Copilot and Genetic Programming
Authors: Dominik Sobania, Martin Briesch, Franz Rothlauf
Date: 2021-11-15 00:00:00
Tasks: Language Modeling, Language Modelling, Program Synthesis

GitHub Copilot, an extension for the Visual Studio Code development environment powered by the large-scale language model Codex, makes automatic program synthesis available for software developers. This model has been extensively studied in the field of deep learning, however, a comparison to genetic programming, which is also known for its performance in automatic program synthesis, has not yet been carried out. In this paper, we evaluate GitHub Copilot on standard program synthesis benchmark problems and compare the achieved results with those from the genetic programming literature. In addition, we discuss the performance of both approaches. We find that the performance of the two approaches on the benchmark problems is quite similar, however, in comparison to GitHub Copilot, the program synthesis approaches based on genetic programming are not yet mature enough to support programmers in practical software development. Genetic programming usually needs a huge amount of expensive hand-labeled training cases and takes too much time to generate solutions. Furthermore, source code generated by genetic programming approaches is often bloated and difficult to understand. For future work on program synthesis with genetic programming, we suggest researchers to focus on improving the execution time, readability, and usability.
Mitigating Divergence of Latent Factors via Dual Ascent for Low Latency Event Prediction Models
Authors: Alex Shtoff, Yair Koren
Date: 2021-11-15 00:00:00
Tasks: Collaborative Filtering

Real-world content recommendation marketplaces exhibit certain behaviors and are imposed by constraints that are not always apparent in common static offline data sets. One example that is common in ad marketplaces is swift ad turnover. New ads are introduced and old ads disappear at high rates every day. Another example is ad discontinuity, where existing ads may appear and disappear from the market for non negligible amounts of time due to a variety of reasons (e.g., depletion of budget, pausing by the advertiser, flagging by the system, and more). These behaviors sometimes cause the model's loss surface to change dramatically over short periods of time. To address these behaviors, fresh models are highly important, and to achieve this (and for several other reasons) incremental training on small chunks of past events is often employed. These behaviors and algorithmic optimizations occasionally cause model parameters to grow uncontrollably large, or \emph{diverge}. In this work present a systematic method to prevent model parameters from diverging by imposing a carefully chosen set of constraints on the model's latent vectors. We then devise a method inspired by primal-dual optimization algorithms to fulfill these constraints in a manner which both aligns well with incremental model training, and does not require any major modifications to the underlying model training algorithm. We analyze, demonstrate, and motivate our method on OFFSET, a collaborative filtering algorithm which drives Yahoo native advertising, which is one of VZM's largest and faster growing businesses, reaching a run-rate of many hundreds of millions USD per year. Finally, we conduct an online experiment which shows a substantial reduction in the number of diverging instances, and a significant improvement to both user experience and revenue.
Transfer Learning Capabilities of Untrained Neural Networks for MIMO CSI Recreation
Authors: Brenda Vilas Boas, Wolfgang Zirwas, Martin Haardt
Date: 2021-11-15 00:00:00
Tasks: Transfer Learning

Machine learning (ML) applications for wireless communications have gained momentum on the standardization discussions for 5G advanced and beyond. One of the biggest challenges for real world ML deployment is the need for labeled signals and big measurement campaigns. To overcome those problems, we propose the use of untrained neural networks (UNNs) for MIMO channel recreation/estimation and low overhead reporting. The UNNs learn the propagation environment by fitting a few channel measurements and we exploit their learned prior to provide higher channel estimation gains. Moreover, we present a UNN for simultaneous channel recreation for multiple users, or multiple user equipment (UE) positions, in which we have a trade-off between the estimated channel gain and the number of parameters. Our results show that transfer learning techniques are effective in accessing the learned prior on the environment structure as they provide higher channel gain for neighbouring users. Moreover, we indicate how the under-parameterization of UNNs can further enable low-overhead channel state information (CSI) reporting.
Machine Learning for CSI Recreation Based on Prior Knowledge
Authors: Brenda Vilas Boas, Wolfgang Zirwas, Martin Haardt
Date: 2021-11-15 00:00:00
Tasks: BIG-bench Machine Learning, Quantization

Knowledge of channel state information (CSI) is fundamental to many functionalities within the mobile wireless communications systems. With the advance of machine learning (ML) and digital maps, i.e., digital twins, we have a big opportunity to learn the propagation environment and design novel methods to derive and report CSI. In this work, we propose to combine untrained neural networks (UNNs) and conditional generative adversarial networks (cGANs) for MIMO channel recreation based on prior knowledge. The UNNs learn the prior-CSI for some locations which are used to build the input to a cGAN. Based on the prior-CSIs, their locations and the location of the desired channel, the cGAN is trained to output the channel expected at the desired location. This combined approach can be used for low overhead CSI reporting as, after training, we only need to report the desired location. Our results show that our method is successful in modelling the wireless channel and robust to location quantization errors in line of sight conditions.
Conditional Linear Regression for Heterogeneous Covariances
Authors: Brendan Juba, Leda Liang
Date: 2021-11-15 00:00:00
Tasks: regression

Often machine learning and statistical models will attempt to describe the majority of the data. However, there may be situations where only a fraction of the data can be fit well by a linear regression model. Here, we are interested in a case where such inliers can be identified by a Disjunctive Normal Form (DNF) formula. We give a polynomial time algorithm for the conditional linear regression task, which identifies a DNF condition together with the linear predictor on the corresponding portion of the data. In this work, we improve on previous algorithms by removing a requirement that the covariances of the data satisfying each of the terms of the condition have to all be very similar in spectral norm to the covariance of the overall condition.
Three-body renormalization group limit cycles based on unsupervised feature learning
Authors: Bastian Kaspschak, Ulf-G. Meißner
Date: 2021-11-15 00:00:00
Tasks: Dimensionality Reduction

Both the three-body system and the inverse square potential carry a special significance in the study of renormalization group limit cycles. In this work, we pursue an exploratory approach and address the question which two-body interactions lead to limit cycles in the three-body system at low energies, without imposing any restrictions upon the scattering length. For this, we train a boosted ensemble of variational autoencoders, that not only provide a severe dimensionality reduction, but also allow to generate further synthetic potentials, which is an important prerequisite in order to efficiently search for limit cycles in low-dimensional latent space. We do so by applying an elitist genetic algorithm to a population of synthetic potentials that minimizes a specially defined limit-cycle-loss. The resulting fittest individuals suggest that the inverse square potential is the only two-body potential that minimizes this limit cycle loss independent of the hyperangle.
A Teacher-Student Markov Decision Process-based Framework for Online Correctional Learning
Authors: Inês Lourenço, Rebecka Winqvist, Cristian R. Rojas, Bo Wahlberg
Date: 2021-11-15 00:00:00

A classical learning setting typically concerns an agent/student who collects data, or observations, from a system in order to estimate a certain property of interest. Correctional learning is a type of cooperative teacher-student framework where a teacher, who has partial knowledge about the system, has the ability to observe and alter (correct) the observations received by the student in order to improve the accuracy of its estimate. In this paper, we show how the variance of the estimate of the student can be reduced with the help of the teacher. We formulate the corresponding online problem - where the teacher has to decide, at each time instant, whether or not to change the observations due to a limited budget - as a Markov decision process, from which the optimal policy is derived using dynamic programming. We validate the framework in numerical experiments, and compare the optimal online policy with the one from the batch setting.
Spectral learning of multivariate extremes
Authors: Marco Avella Medina, Richard A. Davis, Gennady Samorodnitsky
Date: 2021-11-15 00:00:00
Tasks: Clustering

We propose a spectral clustering algorithm for analyzing the dependence structure of multivariate extremes. More specifically, we focus on the asymptotic dependence of multivariate extremes characterized by the angular or spectral measure in extreme value theory. Our work studies the theoretical performance of spectral clustering based on a random $k$-nearest neighbor graph constructed from an extremal sample, i.e., the angular part of random vectors for which the radius exceeds a large threshold. In particular, we derive the asymptotic distribution of extremes arising from a linear factor model and prove that, under certain conditions, spectral clustering can consistently identify the clusters of extremes arising in this model. Leveraging this result we propose a simple consistent estimation strategy for learning the angular measure. Our theoretical findings are complemented with numerical experiments illustrating the finite sample performance of our methods.
AutoGMap: Learning to Map Large-scale Sparse Graphs on Memristive Crossbars
Authors: Bo Lyu, Shengbo Wang, Shiping Wen, Kaibo Shi, Yin Yang, Lingfang Zeng, TingWen Huang
Date: 2021-11-15 00:00:00
Tasks: CPU, Decision Making, GPU, Knowledge Graphs, Reinforcement Learning (RL), Sequential Decision Making

The sparse representation of graphs has shown great potential for accelerating the computation of graph applications (e.g., Social Networks, Knowledge Graphs) on traditional computing architectures (CPU, GPU, or TPU). But the exploration of large-scale sparse graph computing on processing-in-memory (PIM) platforms (typically with memristive crossbars) is still in its infancy. To implement the computation or storage of large-scale or batch graphs on memristive crossbars, a natural assumption is that a large-scale crossbar is demanded, but with low utilization. Some recent works question this assumption, to avoid the waste of storage and computational resource, the fixed-size or progressively scheduled ''block partition'' schemes are proposed. However, these methods are coarse-grained or static, and are not effectively sparsity-aware. This work proposes the dynamic sparsity-aware mapping scheme generating method that models the problem with a sequential decision-making model, and optimizes it by reinforcement learning (RL) algorithm (REINFORCE). Our generating model (LSTM, combined with the dynamic-fill scheme) generates remarkable mapping performance on a small-scale graph/matrix data (complete mapping costs 43% area of the original matrix) and two large-scale matrix data (costing 22.5% area on qh882 and 17.1% area on qh1484). Our method may be extended to sparse graph computing on other PIM architectures, not limited to the memristive device-based platforms.
Reachability analysis of neural networks using mixed monotonicity
Authors: Pierre-Jean Meyer
Date: 2021-11-15 00:00:00

This paper presents a new reachability analysis approach to compute interval over-approximations of the output set of feedforward neural networks with input uncertainty. We adapt to neural networks an existing mixed-monotonicity method for the reachability analysis of dynamical systems and apply it to each partial network within the main network. This ensures that the intersection of the obtained results is the tightest interval over-approximation of the output of each layer that can be obtained using mixed-monotonicity on any partial network decomposition. Unlike other tools in the literature focusing on small classes of piecewise-affine or monotone activation functions, the main strength of our approach is its generality: it can handle neural networks with any Lipschitz-continuous activation function. In addition, the simplicity of our framework allows users to very easily add unimplemented activation functions, by simply providing the function, its derivative and the global argmin and argmax of the derivative. Our algorithm is compared to five other interval-based tools (Interval Bound Propagation, ReluVal, Neurify, VeriNet, CROWN) on both existing benchmarks and two sets of small and large randomly generated networks for four activation functions (ReLU, TanH, ELU, SiLU).
Contrastive Representation Learning with Trainable Augmentation Channel
Authors: Masanori Koyama, Kentaro Minami, Takeru Miyato, Yarin Gal
Date: 2021-11-15 00:00:00
Tasks: Representation Learning

In contrastive representation learning, data representation is trained so that it can classify the image instances even when the images are altered by augmentations. However, depending on the datasets, some augmentations can damage the information of the images beyond recognition, and such augmentations can result in collapsed representations. We present a partial solution to this problem by formalizing a stochastic encoding process in which there exist a tug-of-war between the data corruption introduced by the augmentations and the information preserved by the encoder. We show that, with the infoMax objective based on this framework, we can learn a data-dependent distribution of augmentations to avoid the collapse of the representation.
NeuralPDE: Modelling Dynamical Systems from Data
Authors: Andrzej Dulny, Andreas Hotho, Anna Krause
Date: 2021-11-15 00:00:00

Many physical processes such as weather phenomena or fluid mechanics are governed by partial differential equations (PDEs). Modelling such dynamical systems using Neural Networks is an active research field. However, current methods are still very limited, as they do not exploit the knowledge about the dynamical nature of the system, require extensive prior knowledge about the governing equations or are limited to linear or first-order equations. In this work we make the observation that the Method of Lines used to solve PDEs can be represented using convolutions which makes convolutional neural networks (CNNs) the natural choice to parametrize arbitrary PDE dynamics. We combine this parametrization with differentiable ODE solvers to form the NeuralPDE Model, which explicitly takes into account the fact that the data is governed by differential equations. We show in several experiments on toy and real-world data that our model consistently outperforms state-of-the-art models used to learn dynamical systems.
Versatile Inverse Reinforcement Learning via Cumulative Rewards
Authors: Niklas Freymuth, Philipp Becker, Gerhard Neumann
Date: 2021-11-15 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Inverse Reinforcement Learning infers a reward function from expert demonstrations, aiming to encode the behavior and intentions of the expert. Current approaches usually do this with generative and uni-modal models, meaning that they encode a single behavior. In the common setting, where there are various solutions to a problem and the experts show versatile behavior this severely limits the generalization capabilities of these methods. We propose a novel method for Inverse Reinforcement Learning that overcomes these problems by formulating the recovered reward as a sum of iteratively trained discriminators. We show on simulated tasks that our approach is able to recover general, high-quality reward functions and produces policies of the same quality as behavioral cloning approaches designed for versatile behavior.
Optimism and Delays in Episodic Reinforcement Learning
Authors: Benjamin Howson, Ciara Pike-Burke, Sarah Filippi
Date: 2021-11-15 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

There are many algorithms for regret minimisation in episodic reinforcement learning. This problem is well-understood from a theoretical perspective, providing that the sequences of states, actions and rewards associated with each episode are available to the algorithm updating the policy immediately after every interaction with the environment. However, feedback is almost always delayed in practice. In this paper, we study the impact of delayed feedback in episodic reinforcement learning from a theoretical perspective and propose two general-purpose approaches to handling the delays. The first involves updating as soon as new information becomes available, whereas the second waits before using newly observed information to update the policy. For the class of optimistic algorithms and either approach, we show that the regret increases by an additive term involving the number of states, actions, episode length, the expected delay and an algorithm-dependent constant. We empirically investigate the impact of various delay distributions on the regret of optimistic algorithms to validate our theoretical results.
Spectral Transform Forms Scalable Transformer
Authors: Bingxin Zhou, Xinliang Liu, Yuehua Liu, Yunying Huang, Pietro Liò, Yuguang Wang
Date: 2021-11-15 00:00:00
Tasks: Graph Learning, Philosophy

Many real-world relational systems, such as social networks and biological systems, contain dynamic interactions. When learning dynamic graph representation, it is essential to employ sequential temporal information and geometric structure. Mainstream work achieves topological embedding via message passing networks (e.g., GCN, GAT). The temporal evolution, on the other hand, is conventionally expressed via memory units (e.g., LSTM or GRU) that possess convenient information filtration in a gate mechanism. Though, such a design prevents large-scale input sequence due to the over-complicated encoding. This work learns from the philosophy of self-attention and proposes an efficient spectral-based neural unit that employs informative long-range temporal interaction. The developed spectral window unit (SWINIT) model predicts scalable dynamic graphs with assured efficiency. The architecture is assembled with a few simple effective computational blocks that constitute randomized SVD, MLP, and graph Framelet convolution. The SVD plus MLP module encodes the long-short-term feature evolution of the dynamic graph events. A fast framelet graph transform in the framelet convolution embeds the structural dynamics. Both strategies enhance the model's ability on scalable analysis. In particular, the iterative SVD approximation shrinks the computational complexity of attention to O(Nd\log(d)) for the dynamic graph with N edges and d edge features, and the multiscale transform of framelet convolution allows sufficient scalability in the network training. Our SWINIT achieves state-of-the-art performance on a variety of online continuous-time dynamic graph learning tasks, while compared to baseline methods, the number of its learnable parameters reduces by up to seven times.
DNN gradient lossless compression: Can GenNorm be the answer?
Authors: Zhong-Jing Chen, Eduin E. Hernandez, Yu-Chih Huang, Stefano Rini
Date: 2021-11-15 00:00:00
Tasks: Federated Learning

In this paper, the problem of optimal gradient lossless compression in Deep Neural Network (DNN) training is considered. Gradient compression is relevant in many distributed DNN training scenarios, including the recently popular federated learning (FL) scenario in which each remote users are connected to the parameter server (PS) through a noiseless but rate limited channel. In distributed DNN training, if the underlying gradient distribution is available, classical lossless compression approaches can be used to reduce the number of bits required for communicating the gradient entries. Mean field analysis has suggested that gradient updates can be considered as independent random variables, while Laplace approximation can be used to argue that gradient has a distribution approximating the normal (Norm) distribution in some regimes. In this paper we argue that, for some networks of practical interest, the gradient entries can be well modelled as having a generalized normal (GenNorm) distribution. We provide numerical evaluations to validate that the hypothesis GenNorm modelling provides a more accurate prediction of the DNN gradient tail distribution. Additionally, this modeling choice provides concrete improvement in terms of lossless compression of the gradients when applying classical fix-to-variable lossless coding algorithms, such as Huffman coding, to the quantized gradient updates. This latter results indeed provides an effective compression strategy with low memory and computational complexity that has great practical relevance in distributed DNN training scenarios.
Say What? Collaborative Pop Lyric Generation Using Multitask Transfer Learning
Authors: Naveen Ram, Tanay Gummadi, Rahul Bhethanabotla, Richard J. Savery, Gil Weinberg
Date: 2021-11-15 00:00:00
Tasks: Text Generation, Transfer Learning

Lyric generation is a popular sub-field of natural language generation that has seen growth in recent years. Pop lyrics are of unique interest due to the genre's unique style and content, in addition to the high level of collaboration that goes on behind the scenes in the professional pop songwriting process. In this paper, we present a collaborative line-level lyric generation system that utilizes transfer-learning via the T5 transformer model, which, till date, has not been used to generate pop lyrics. By working and communicating directly with professional songwriters, we develop a model that is able to learn lyrical and stylistic tasks like rhyming, matching line beat requirements, and ending lines with specific target words. Our approach compares favorably to existing methods for multiple datasets and yields positive results from our online studies and interviews with industry songwriters.