pwc-archive/papers-with-abstracts huggingface dataset:
Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity
Authors: Dan Garber
Date: 2019-12-03 00:00:00
Tasks: Retrieval

We consider convex optimization problems which are widely used as convex relaxations for low-rank matrix recovery problems. In particular, in several important problems, such as phase retrieval and robust PCA, the underlying assumption in many cases is that the optimal solution is rank-one. In this paper we consider a simple and natural sufficient condition on the objective so that the optimal solution to these relaxations is indeed unique and rank-one. Mainly, we show that under this condition, the standard Frank-Wolfe method with line-search (i.e., without any tuning of parameters whatsoever), which only requires a single rank-one SVD computation per iteration, finds an $\epsilon$-approximated solution in only $O(\log{1/\epsilon})$ iterations (as opposed to the previous best known bound of $O(1/\epsilon)$), despite the fact that the objective is not strongly convex. We consider several variants of the basic method with improved complexities, as well as an extension motivated by robust PCA, and finally, an extension to nonsmooth problems.
Adversarial Embedding: A robust and elusive Steganography and Watermarking technique
Authors: Salah Ghamizi, Maxime Cordy, Mike Papadakis, Yves Le Traon
Date: 2019-11-14 00:00:00
Tasks: Adversarial Attack, image-classification, Image Classification, Retrieval, Steganalysis

We propose adversarial embedding, a new steganography and watermarking technique that embeds secret information within images. The key idea of our method is to use deep neural networks for image classification and adversarial attacks to embed secret information within images. Thus, we use the attacks to embed an encoding of the message within images and the related deep neural network outputs to extract it. The key properties of adversarial attacks (invisible perturbations, nontransferability, resilience to tampering) offer guarantees regarding the confidentiality and the integrity of the hidden messages. We empirically evaluate adversarial embedding using more than 100 models and 1,000 messages. Our results confirm that our embedding passes unnoticed by both humans and steganalysis methods, while at the same time impedes illicit retrieval of the message (less than 13% recovery rate when the interceptor has some knowledge about our model), and is resilient to soft and (to some extent) aggressive image tampering (up to 100% recovery rate under jpeg compression). We further develop our method by proposing a new type of adversarial attack which improves the embedding density (amount of hidden information) of our method to up to 10 bits per pixel.
Experimental Evidence for Asymptotic Non-Optimality of Comb Adversary Strategy
Authors: Zachary Chase
Date: 2019-12-03 00:00:00

For the problem of prediction with expert advice in the adversarial setting with finite stopping time, we give strong computer evidence that the comb strategy for $k=5$ experts is not asymptotically optimal, thereby giving strong evidence against a conjecture of Gravin, Peres, and Sivan.
Unified Mechanism of Atrial Fibrillation in a Simple Model
Authors: Max Falkenberg, Andrew J. Ford, Anthony C. Li, Alberto Ciacci, Nicholas S. Peters, Kim Christensen
Date: 2018-10-29 00:00:00
Tasks: Rhythm

The mechanism of atrial fibrillation (AF) is poorly understood, resulting in disappointing success rates of ablative treatment. Different mechanisms defined largely by different atrial activation patterns have been proposed and, arguably, this dispute has slowed the progress of AF research. Recent clinical evidence suggests a unifying mechanism based on sustained re-entrant circuits in the complex atrial architecture. Here, we present a simple computational model showing spontaneous emergence of AF that strongly supports, and gives a theoretical explanation for, the clinically observed diversity of activation. We show that the difference in surface activation patterns is a direct consequence of the thickness of the discrete network of heart muscle cells through which electrical signals percolate to reach the imaged surface. The model naturally follows the clinical spectrum of AF spanning sinus rhythm, paroxysmal and persistent AF as the decoupling of myocardial cells results in the lattice approaching the percolation threshold. This allows the model to make additional predictions beyond the current clinical understanding, showing that for paroxysmal AF re-entrant circuits emerge near the endocardium, but in persistent AF they emerge deeper in the bulk of the atrial wall where endocardial ablation is less effective. If clinically confirmed, this may explain the lower success rate of ablation in long-lasting persistent AF.
Number detectors spontaneously emerge in a deep neural network designed for visual object recognition
Authors: Khaled Nasr, Pooja Viswanathan, Andreas Nieder
Date: 2019-05-08 00:00:00
Proceeding: journal 2019 5
Tasks: Object, Object Recognition

Humans and animals have a “number sense,” an innate capability to intuitively assess the number of visual
items in a set, its numerosity. This capability implies that mechanisms to extract numerosity indwell the
brain’s visual system, which is primarily concerned with visual object recognition. Here, we show that
network units tuned to abstract numerosity, and therefore reminiscent of real number neurons, spontaneously emerge in a biologically inspired deep neural network that was merely trained on visual object
recognition. These numerosity-tuned units underlay the network’s number discrimination performance that
showed all the characteristics of human and animal number discriminations as predicted by the WeberFechner law. These findings explain the spontaneous emergence of the number sense based on mechanisms inherent to the visual system.
Fantastic Generalization Measures and Where to Find Them
Authors: Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, Samy Bengio
Date: 2019-12-04 00:00:00
Proceeding: ICLR 2020 1
Tasks: valid

Generalization of deep networks has been of great interest in recent years, resulting in a number of theoretically and empirically motivated complexity measures. However, most papers proposing such measures study only a small set of models, leaving open the question of whether the conclusion drawn from those experiments would remain valid in other settings. We present the first large scale study of generalization in deep networks. We investigate more then 40 complexity measures taken from both theoretical bounds and empirical studies. We train over 10,000 convolutional networks by systematically varying commonly used hyperparameters. Hoping to uncover potentially causal relationships between each measure and generalization, we analyze carefully controlled experiments and show surprising failures of some measures as well as promising measures for further research.
Differentiation of Blackbox Combinatorial Solvers
Authors: Marin Vlastelica, Anselm Paulus, Vít Musil, Georg Martius, Michal Rolínek
Date: 2019-12-04 00:00:00
Proceeding: ICLR 2020 1
Tasks: Traveling Salesman Problem

Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence. One possible approach is to introduce combinatorial building blocks into neural networks. Such end-to-end architectures have the potential to tackle combinatorial problems on raw input data such as ensuring global consistency in multi-object tracking or route planning on maps in robotics. In this work, we present a method that implements an efficient backward pass through blackbox implementations of combinatorial solvers with linear objective functions. We provide both theoretical and experimental backing. In particular, we incorporate the Gurobi MIP solver, Blossom V algorithm, and Dijkstra's algorithm into architectures that extract suitable features from raw inputs for the traveling salesman problem, the min-cost perfect matching problem and the shortest path problem. The code is available at https://github.com/martius-lab/blackbox-backprop.
Copula-based anomaly scoring and localization for large-scale, high-dimensional continuous data
Authors: Gábor Horváth, Edith Kovács, Roland Molontay, Szabolcs Nováczki
Date: 2019-12-04 00:00:00
Tasks: Anomaly Detection, Missing Values

The anomaly detection method presented by this paper has a special feature: it does not only indicate whether an observation is anomalous or not but also tells what exactly makes an anomalous observation unusual. Hence, it provides support to localize the reason of the anomaly. The proposed approach is model-based; it relies on the multivariate probability distribution associated with the observations. Since the rare events are present in the tails of the probability distributions, we use copula functions, that are able to model the fat-tailed distributions well. The presented procedure scales well; it can cope with a large number of high-dimensional samples. Furthermore, our procedure can cope with missing values, too, which occur frequently in high-dimensional data sets. In the second part of the paper, we demonstrate the usability of the method through a case study, where we analyze a large data set consisting of the performance counters of a real mobile telecommunication network. Since such networks are complex systems, the signs of sub-optimal operation can remain hidden for a potentially long time. With the proposed procedure, many such hidden issues can be isolated and indicated to the network operator.
L3 Fusion: Fast Transformed Convolutions on CPUs
Authors: Rati Gelashvili, Nir Shavit, Aleksandar Zlateski
Date: 2019-12-04 00:00:00
Tasks: Benchmarking

Fast convolutions via transforms, either Winograd or FFT, had emerged as a preferred way of performing the computation of convolutional layers, as it greatly reduces the number of required operations. Recent work shows that, for many layer structures, a well--designed implementation of fast convolutions can greatly utilize modern CPUs, significantly reducing the compute time. However, the generous amount of shared L3 cache present on modern CPUs is often neglected, and the algorithms are optimized solely for the private L2 cache. In this paper we propose an efficient `L3 Fusion` algorithm that is specifically designed for CPUs with significant amount of shared L3 cache. Using the hierarchical roofline model, we show that in many cases, especially for layers with fewer channels, the `L3 fused` approach can greatly outperform standard 3 stage one provided by big vendors such as Intel. We validate our theoretical findings, by benchmarking our `L3 fused` implementation against publicly available state of the art.
Plug and Play Language Models: A Simple Approach to Controlled Text Generation
Authors: Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, Rosanne Liu
Date: 2019-12-04 00:00:00
Proceeding: ICLR 2020 1
Tasks: Attribute, Language Modelling, Text Generation

Large transformer-based language models (LMs) trained on huge text corpora have shown unparalleled generation capabilities. However, controlling attributes of the generated language (e.g. switching topic or sentiment) is difficult without modifying the model architecture or fine-tuning on attribute-specific data and entailing the significant cost of retraining. We propose a simple alternative: the Plug and Play Language Model (PPLM) for controllable language generation, which combines a pretrained LM with one or more simple attribute classifiers that guide text generation without any further training of the LM. In the canonical scenario we present, the attribute models are simple classifiers consisting of a user-specified bag of words or a single learned layer with 100,000 times fewer parameters than the LM. Sampling entails a forward and backward pass in which gradients from the attribute model push the LM's hidden activations and thus guide the generation. Model samples demonstrate control over a range of topics and sentiment styles, and extensive automated and human annotated evaluations show attribute alignment and fluency. PPLMs are flexible in that any combination of differentiable attribute models may be used to steer text generation, which will allow for diverse and creative applications beyond the examples given in this paper.
Regression with Uncertainty Quantification in Large Scale Complex Data
Authors: Nicholas Wilkins, Michael Johnson, Ifeoma Nwogu
Date: 2019-12-04 00:00:00
Tasks: Age Estimation, regression, Time Series, Time Series Analysis, Uncertainty Quantification

While several methods for predicting uncertainty on deep networks have been recently proposed, they do not readily translate to large and complex datasets. In this paper we utilize a simplified form of the Mixture Density Networks (MDNs) to produce a one-shot approach to quantify uncertainty in regression problems. We show that our uncertainty bounds are on-par or better than other reported existing methods. When applied to standard regression benchmark datasets, we show an improvement in predictive log-likelihood and root-mean-square-error when compared to existing state-of-the-art methods. We also demonstrate this method's efficacy on stochastic, highly volatile time-series data where stock prices are predicted for the next time interval. The resulting uncertainty graph summarizes significant anomalies in the stock price chart. Furthermore, we apply this method to the task of age estimation from the challenging IMDb-Wiki dataset of half a million face images. We successfully predict the uncertainties associated with the prediction and empirically analyze the underlying causes of the uncertainties. This uncertainty quantification can be used to pre-process low quality datasets and further enable learning.
Informative GANs via Structured Regularization of Optimal Transport
Authors: Pierre Bréchet, Tao Wu, Thomas Möllenhoff, Daniel Cremers
Date: 2019-12-04 00:00:00
Tasks: Representation Learning

We tackle the challenge of disentangled representation learning in generative adversarial networks (GANs) from the perspective of regularized optimal transport (OT). Specifically, a smoothed OT loss gives rise to an implicit transportation plan between the latent space and the data space. Based on this theoretical observation, we exploit a structured regularization on the transportation plan to encourage a prescribed latent subspace to be informative. This yields the formulation of a novel informative OT-based GAN. By convex duality, we obtain the equivalent view that this leads to perturbed ground costs favoring sparsity in the informative latent dimensions. Practically, we devise a stable training algorithm for the proposed informative GAN. Our experiments support the hypothesis that such regularizations effectively yield the discovery of disentangled and interpretable latent representations. Our work showcases potential power of a regularized OT framework in the context of generative modeling through its access to the transport plan. Further challenges are addressed in this line.
Visual Reaction: Learning to Play Catch with Your Drone
Authors: Kuo-Hao Zeng, Roozbeh Mottaghi, Luca Weihs, Ali Farhadi
Date: 2019-12-04 00:00:00
Proceeding: CVPR 2020 6

In this paper we address the problem of visual reaction: the task of interacting with dynamic environments where the changes in the environment are not necessarily caused by the agent itself. Visual reaction entails predicting the future changes in a visual environment and planning accordingly. We study the problem of visual reaction in the context of playing catch with a drone in visually rich synthetic environments. This is a challenging problem since the agent is required to learn (1) how objects with different physical properties and shapes move, (2) what sequence of actions should be taken according to the prediction, (3) how to adjust the actions based on the visual feedback from the dynamic environment (e.g., when objects bouncing off a wall), and (4) how to reason and act with an unexpected state change in a timely manner. We propose a new dataset for this task, which includes 30K throws of 20 types of objects in different directions with different forces. Our results show that our model that integrates a forecaster with a planner outperforms a set of strong baselines that are based on tracking as well as pure model-based and model-free RL baselines. The code and dataset are available at github.com/KuoHaoZeng/Visual_Reaction.
Extreme Learning Machine design for dealing with unrepresentative features
Authors: Nicolás Nieto, Francisco Ibarrola, Victoria Peterson, Hugo Rufiner, Ruben Spies
Date: 2019-12-04 00:00:00
Tasks: EEG, Electroencephalogram (EEG)

Extreme Learning Machines (ELMs) have become a popular tool in the field of Artificial Intelligence due to their very high training speed and generalization capabilities. Another advantage is that they have a single hyper-parameter that must be tuned up: the number of hidden nodes. Most traditional approaches dictate that this parameter should be chosen smaller than the number of available training samples in order to avoid over-fitting. In fact, it has been proved that choosing the number of hidden nodes equal to the number of training samples yields a perfect training classification with probability 1 (w.r.t. the random parameter initialization). In this article we argue that in spite of this, in some cases it may be beneficial to choose a much larger number of hidden nodes, depending on certain properties of the data. We explain why this happens and show some examples to illustrate how the model behaves. In addition, we present a pruning algorithm to cope with the additional computational burden associated to the enlarged ELM. Experimental results using electroencephalography (EEG) signals show an improvement in performance with respect to traditional ELM approaches, while diminishing the extra computing time associated to the use of large architectures.
Walking on the Edge: Fast, Low-Distortion Adversarial Examples
Authors: Hanwei Zhang, Yannis Avrithis, Teddy Furon, Laurent Amsaleg
Date: 2019-12-04 00:00:00

Adversarial examples of deep neural networks are receiving ever increasing attention because they help in understanding and reducing the sensitivity to their input. This is natural given the increasing applications of deep neural networks in our everyday lives. When white-box attacks are almost always successful, it is typically only the distortion of the perturbations that matters in their evaluation. In this work, we argue that speed is important as well, especially when considering that fast attacks are required by adversarial training. Given more time, iterative methods can always find better solutions. We investigate this speed-distortion trade-off in some depth and introduce a new attack called boundary projection (BP) that improves upon existing methods by a large margin. Our key idea is that the classification boundary is a manifold in the image space: we therefore quickly reach the boundary and then optimize distortion on this manifold.
A Probabilistic Approach to Satisfiability of Propositional Logic Formulae
Authors: Reazul Hasan Russel
Date: 2019-12-04 00:00:00

We propose a version of WalkSAT algorithm, named as BetaWalkSAT. This method uses probabilistic reasoning for biasing the starting state of the local search algorithm. Beta distribution is used to model the belief over boolean values of the literals. Our results suggest that, the proposed BetaWalkSAT algorithm can outperform other uninformed local search approaches for complex boolean satisfiability problems.
Dynamic Hilbert Maps: Real-Time Occupancy Predictions in Changing Environment
Authors: Vitor Guizilini, Ransalu Senanayake, Fabio Ramos
Date: 2019-12-04 00:00:00

This paper addresses the problem of learning instantaneous occupancy levels of dynamic environments and predicting future occupancy levels. Due to the complexity of most real-world environments, such as urban streets or crowded areas, the efficient and robust incorporation of temporal dependencies into otherwise static occupancy models remains a challenge. We propose a method to capture the spatial uncertainty of moving objects and incorporate this uncertainty information into a continuous occupancy map represented in a rich high-dimensional feature space. Experiments performed using LIDAR data verified the real-time performance of the algorithm.
An Exploration of Data Augmentation and Sampling Techniques for Domain-Agnostic Question Answering
Authors: Shayne Longpre, Yi Lu, Zhucheng Tu, Chris DuBois
Date: 2019-12-04 00:00:00
Proceeding: WS 2019 11
Tasks: Data Augmentation, Question Answering, Reading Comprehension, Translation

To produce a domain-agnostic question answering model for the Machine Reading Question Answering (MRQA) 2019 Shared Task, we investigate the relative benefits of large pre-trained language models, various data sampling strategies, as well as query and context paraphrases generated by back-translation. We find a simple negative sampling technique to be particularly effective, even though it is typically used for datasets that include unanswerable questions, such as SQuAD 2.0. When applied in conjunction with per-domain sampling, our XLNet (Yang et al., 2019)-based submission achieved the second best Exact Match and F1 in the MRQA leaderboard competition.
Landscape Complexity for the Empirical Risk of Generalized Linear Models
Authors: Antoine Maillard, Gérard Ben Arous, Giulio Biroli
Date: 2019-12-04 00:00:00

We present a method to obtain the average and the typical value of the number of critical points of the empirical risk landscape for generalized linear estimation problems and variants. This represents a substantial extension of previous applications of the Kac-Rice method since it allows to analyze the critical points of high dimensional non-Gaussian random functions. Under a technical hypothesis, we obtain a rigorous explicit variational formula for the annealed complexity, which is the logarithm of the average number of critical points at fixed value of the empirical risk. This result is simplified, and extended, using the non-rigorous Kac-Rice replicated method from theoretical physics. In this way we find an explicit variational formula for the quenched complexity, which is generally different from its annealed counterpart, and allows to obtain the number of critical points for typical instances up to exponential accuracy.
Simulating Evolution on Fitness Landscapes represented by Valued Constraint Satisfaction Problems
Authors: Alexandru Strimbu
Date: 2019-12-04 00:00:00

Recent theoretical research proposes that computational complexity can be seen as an ultimate constraint that allows for open-ended biological evolution on finite static fitness landscapes. Whereas on easy fitness landscapes, evolution will quickly converge to a local fitness peaks, on hard fitness landscapes this computational constraints prevents evolution from reaching any local fitness peak in polynomial time. Valued constraint satisfaction problems (VCSPs) can be used to represent both easy and hard fitness landscapes. Thus VCSPS can be seen as a natural way of linking the theory of evolution with notions of computer science to better understand the features that make landscapes hard. However, there are currently no simulators that study VCSP-structured fitness landscapes. This report describes the design and build of an evolution simulator for VCSP-structured fitness landscapes. The platform is used for simulating various instances of easy and hard fitness landscapes. In particular, we look at evolution under more realistic assumptions than fittest mutant strong-selection weak mutation dynamics on the winding semismooth fitness landscape. The results obtained match with the theoretical expectations, while also providing new information about the limits of evolution. The last part of the report introduces a mathematical model for smooth fitness landscapes and uses it to better understand why these landscapes are easy.