pwc-archive/papers-with-abstracts huggingface dataset:
A Mean Field Analysis Of Deep ResNet And Beyond: Towards Provably Optimization Via Overparameterization From Depth
Authors: Yiping Lu, Chao Ma, Yulong Lu, Jianfeng Lu, Lexing Ying
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Training deep neural networks with stochastic gradient descent (SGD) can often achieve zero training loss on real-world tasks although the optimization landscape is known to be highly non-convex. To understand the success of SGD for training deep neural networks, this work presents a mean-field analysis of deep residual networks, based on a line of works which interpret the continuum limit of the deep residual network as an ordinary differential equation as the the network capacity tends to infinity. Specifically, we propose a \textbf{new continuum limit} of deep residual networks, which enjoys a good landscape in the sense that \textbf{every local minimizer is global}. 
This characterization enables us to derive the first global convergence result for multilayer neural networks in the mean-field regime. Furthermore, our proof does not rely on the convexity of the loss landscape, but instead, an assumption on the global minimizer should achieve zero loss which can be achieved when the model shares a universal approximation property. Key to our result is the observation that a deep residual network resembles a shallow network ensemble~\cite{veit2016residual}, \emph{i.e.} a two-layer network. We bound the difference between the shallow network and our ResNet model via the adjoint sensitivity method, which enables us to transfer previous mean-field analysis of two-layer networks to deep networks. Furthermore, we propose several novel training schemes based on our new continuous model, among which one new training procedure introduces the operation of switching the order of the residual blocks and results in strong empirical performance on benchmark datasets.
Fast and Consistent Learning of Hidden Markov Models by Incorporating Non-Consecutive Correlations
Authors: Robert Mattila, Cristian Rojas, Eric Moulines, Vikram Krishnamurthy, Bo Wahlberg
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Time Series, Time Series Analysis, Triplet

Can the parameters of a hidden Markov model (HMM) be estimated from a single sweep through the observations -- and additionally, without being trapped at a local optimum in the likelihood surface? That is the premise of recent method of moments algorithms devised for HMMs. In these, correlations between consecutive pair- or triplet-wise observations are empirically estimated and used to compute estimates of the HMM parameters. Albeit computationally very attractive, the main drawback is that by restricting to only low-order correlations in the data, information is being neglected which results in a loss of accuracy (compared to standard maximum likelihood schemes). In this paper, we propose extending these methods (both pair- and triplet-based) by also including non-consecutive correlations in a way which does not significantly increase the computational cost (which scales linearly with the number of additional lags included). We prove strong consistency of the new methods, and demonstrate an improved performance in numerical simulations on both synthetic and real-world financial time-series datasets.
Implicit Euler Skip Connections: Enhancing Adversarial Robustness via Numerical Stability
Authors: Mingjie Li, Lingshen He, Zhouchen Lin
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Adversarial Attack, Adversarial Robustness

Deep neural networks have achieved great success in various areas. However, recent works have found that neural networks are vulnerable to adversarial attacks, which leads to a hot topic nowadays. Although many approaches have been proposed to enhance the robustness of neural networks, few of them explored robust architectures for neural networks. On this account, we try to address such an issue from the perspective of dynamic system in this work. By viewing ResNet as an explicit Euler discretization of an ordinary differential equation (ODE), for the first time, we find that the adversarial robustness of ResNet is connected to the numerical stability of the corresponding dynamic system. Namely, more stable numerical schemes may correspond to more robust deep networks. Furthermore, inspired by the implicit Euler method for solving numerical ODE problems, we propose Implicit Euler skip connections (IE-Skips) by modifying the original skip connection in ResNet or its variants. Then we theoretically prove its advantages under the adversarial attack. Experimental results show that our ResNet with IE-Skips can largely improve the robustness and the generalization ability under adversarial attacks when compared with the vanilla ResNet of the same parameter size.
Margin-aware Adversarial Domain Adaptation with Optimal Transport
Authors: Sofien Dhouib, Ievgen Redko, Carole Lartizien
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Domain Adaptation, Unsupervised Domain Adaptation

In this paper, we propose a new theoretical analysis of unsupervised domain adaptation that relates notions of large margin separation, adversarial learning and optimal transport. This analysis generalizes previous work on the subject by providing a bound on the target margin violation rate, thus reflecting a better control of the quality of separation between classes in the target domain than bounding the misclassification rate. The bound also highlights the benefit of a large margin separation on the source domain for adaptation and introduces an optimal transport (OT) based distance between domains that has the virtue of being task-dependent, contrary to other approaches. From the obtained theoretical results, we derive a novel algorithmic solution for domain adaptation that introduces a novel shallow OT-based adversarial approach and outperforms other OT-based DA baselines on several simulated and real-world classification tasks.
Mix-n-Match : Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning
Authors: Jize Zhang, Bhavya Kailkhura, T. Yong-Jin Han
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

This paper studies the problem of post-hoc calibration of machine learning classifiers. We introduce the following desiderata for uncertainty calibration: (a) accuracy-preserving, (b) data-efficient, and (c) high expressive power. We show that none of the existing methods satisfy all three requirements, and demonstrate how Mix-n-Match calibration strategies (i.e., ensemble and composition) can help achieve remarkably better data-efficiency and expressive power while provably preserving classification accuracy of the original classifier. We also show that existing calibration error estimators (e.g., histogram-based ECE) are unreliable especially in small-data regime. Therefore, we propose an alternative data-efficient kernel density-based estimator for a reliable evaluation of the calibration performance and prove its asymptotically unbiasedness and consistency.
Optimal Sequential Maximization: One Interview is Enough!
Authors: Moein Falahatgar, Alon Orlitsky, Venkatadheeraj Pichapati
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Maximum selection under probabilistic queries
\emph{(probabilistic maximization)} is a fundamental algorithmic problem
arising in numerous theoretical and practical contexts. 
We derive the first query-optimal sequential algorithm for
probabilistic-maximization.
Departing from previous assumptions,
the algorithm and performance guarantees
apply even for infinitely many items, hence in particular do
not require a-priori knowledge of the number of items.
The algorithm has linear query complexity,
and is optimal also in the streaming setting.

To derive these results we consider a probabilistic setting where several candidates
for a position are asked multiple questions with the goal of
finding who has the highest probability of answering interview
questions correctly. Previous work minimized the total number
of questions asked by alternating back and forth between the
best performing candidates,
in a sense, inviting them to multiple interviews.  We
show that the same order-wise selection accuracy can be achieved by
querying the candidates sequentially, never returning to a previously
queried candidate. Hence one interview is enough!
Robust Multi-Agent Decision-Making with Heavy-Tailed Payoffs
Authors: Abhimanyu Dubey, Alex `Sandy' Pentland
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Decision Making

We study the heavy-tailed stochastic bandit problem in the cooperative multiagent setting, where a group of agents interact with a common bandit problem, while communicating on a network with delays. Existing algorithms for the stochastic bandit in this setting utilize confidence intervals arising from an averaging-based communication protocol known as~\textit{running consensus}, that does not lend itself to robust estimation for heavy-tailed settings. We propose \textsc{MP-UCB}, a decentralized multi-agent algorithm for the cooperative stochastic bandit that incorporates robust estimation with a message-passing protocol. We prove optimal regret bounds for \textsc{MP-UCB} for several problem settings, and also demonstrate its superiority to existing methods. Furthermore, we establish the first lower bounds for the cooperative bandit problem, in addition to providing efficient algorithms for robust bandit estimation of location.
A Game Theoretic Perspective on Model-Based Reinforcement Learning
Authors: Aravind Rajeswaran, Igor Mordatch, Vikash Kumar
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: continuous-control, Continuous Control, Model-based Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We illustrate how game theory is a good framework to understand model-based reinforcement learning (MBRL). We point out that a large class of MBRL algorithms can be viewed as a game between two players: (1) a policy player, which attempts to maximize rewards under the learned model; (2) a model player, which attempts to fit the real-world data collected by the policy player. Their goals need not be aligned, and are often conflicting. We show that stable algorithms for MBRL can be derived by considering a Stackelberg game between the two players. This formulation gives rise to two natural schools of MBRL algorithms based on which player is chosen as the leader in the Stackelberg game, and together encapsulate many existing MBRL algorithms. Through experiments on a suite of continuous control tasks, we validate that algorithms based on our framework lead to stable and sample efficient learning.
Analyzing the effect of neural network architecture on training performance
Authors: Karthik Abinav Sankararaman, Soham De, Zheng Xu, W. Ronny Huang, Tom Goldstein
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In this paper we study how neural network architecture affects the speed of training. We introduce a simple concept called gradient confusion to help formally analyze this.  When confusion is high, stochastic gradients produced by different data samples may be negatively correlated, slowing down convergence. But when gradient confusion is low, data samples interact harmoniously, and training proceeds quickly. Through novel theoretical and experimental results, we show how the neural net architecture affects gradient confusion, and thus the efficiency of training. We show that for popular initialization techniques used in deep learning, increasing the width of neural networks leads to lower gradient confusion, and thus easier model training. On the other hand, increasing the depth of neural networks has the opposite effect. Finally, we observe that the combination of batch normalization and skip connections reduces gradient confusion, which helps reduce the training burden of very deep networks.
Evolutionary Topology Search for Tensor Network Decomposition
Authors: Chao Li, Zhun Sun
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Evolutionary Algorithms

Tensor network (TN) decomposition is a promising framework to represent extremely high-dimensional problems with few parameters. However, it is challenging to search the (near-)optimal topological structure for TN decomposition, since the number of possible solutions exponentially grows with increasing the order of tensor. In this paper, we claim that this issue can be practically tackled by evolutionary algorithms in an efficient manner. We encode the complex topological structures into binary string, and develop a simple yet efficient genetic-based algorithm (GA) to search the optimal topology on Hamming space. The experimental results by both synthetic and real-world data demonstrate that our method can efficiently discovers the groundtruth topology or even better structures with few number of generations, and significantly boost the representational power of TN decomposition compared with well-known tensor-train (TT) or tensor-ring (TR) models.
Fast computation of Nash Equilibria in Imperfect Information Games
Authors: Remi Munos, Julien Perolat, Jean-Baptiste Lespiau, Mark Rowland, Bart De Vylder, Marc Lanctot, Finbarr Timbers, Daniel Hennes, Shayegan Omidshafiei, Audrunas Gruslys, Mohammad Gheshlaghi Azar, Edward Lockhart, Karl Tuyls
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Form

We introduce and analyze a class of algorithms, called Mirror Ascent against an Improved Opponent (MAIO), for computing Nash equilibria in two-player zero-sum games, both in normal form and in sequential imperfect information form. These algorithms update the policy of each player with a mirror-descent step to minimize the loss of playing against an improved opponent. We establish a convergence result to the set of Nash equilibria where the speed of convergence depends on the amount of improvement of the opponent policies. In addition, if the improved opponent is a best response, then an exponential convergence rate is achieved.
How to Solve Fair k-Center in Massive Data Models
Authors: Ashish Chiplunkar, Sagar Kale, Sivaramakrishnan Natarajan Ramamoorthy
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Data Summarization, Decision Making, Fairness

Fueled by massive data, important decision making is being automated with the help of algorithms, therefore, fairness in algorithms has become an especially important research topic. In this work, we design new streaming and distributed algorithms for the fair k-center problem that models fair data summarization. The streaming and distributed models of computation have an attractive feature of being able to handle massive data sets that do not fit into main memory. Our main contributions are: (a) the first distributed algorithm; which has provably constant approximation ratio and is extremely parallelizable, and (b) a two-pass streaming algorithm with a provable approximation guarantee matching the best known algorithm (which is not a streaming algorithm). Our algorithms have the advantages of being easy to implement in practice, being fast with linear running times, having very small working memory and communication, and outperforming existing algorithms on several real and synthetic data sets. To complement our distributed algorithm, we also give a hardness result for natural distributed algorithms, which holds for even the special case of k-center.
NetGAN without GAN: From Random Walks to Low-Rank Approximations
Authors: Luca Rendsburg, Holger Heidrich, Ulrike Von Luxburg
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Inductive Bias

A graph generative model takes a graph as input and is supposed to generate new graphs that ``look like'' the input graph. While most classical models focus on few, hand-selected graph statistics and are too simplistic to reproduce real-world graphs, NetGAN recently emerged as an attractive alternative: by training a GAN to learn the random walk distribution of the input graph, the algorithm is able to reproduce a large number of important network patterns simultaneously, without explicitly specifying any of them. In this paper, we investigate the implicit bias of NetGAN. We find that the root of its generalization properties does not lie in the GAN architecture, but in an inconspicuous low-rank approximation of the logits random walk transition matrix. Step by step we can strip NetGAN of all unnecessary parts, including the GAN, and obtain a highly simplified reformulation that achieves comparable generalization results, but is orders of magnitudes faster and easier to adapt. Being much simpler on the conceptual side, we reveal the implicit inductive bias of the algorithm  --- an important step towards increasing the interpretability, transparency and acceptance of machine learning systems.
Test-Time Training for Generalization under Distribution Shifts
Authors: Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, University of California Moritz Hardt
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: image-classification, Image Classification, Self-Supervised Learning

We introduce a general approach, called test-time training, for improving the performance of predictive models when training and test data come from different distributions. Test-time training turns a single unlabeled test instance into a self-supervised learning problem, on which we update the model parameters before making a prediction. We show that this simple idea leads to surprising improvements on diverse image classification benchmarks aimed at evaluating robustness to distribution shifts. Theoretical investigations on a convex model reveal helpful intuitions for when we can expect our approach to help.
Time-Consistent Self-Supervision for Semi-Supervised Learning
Authors: Tianyi Zhou, Shengjie Wang, Jeff Bilmes
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Semi-supervised learning (SSL) leverages unlabeled data when training a model with insufficient labeled data. A common strategy for SSL is to enforce the consistency of model outputs between similar samples, e.g., neighbors or data augmentations of the same sample. However, model outputs can vary dramatically on unlabeled data over different training stages, e.g., when using large learning rates. This can introduce harmful noises and inconsistent objectives over time that may lead to concept drift and catastrophic forgetting. In this paper, we study the dynamics of neural net outputs in SSL and show that selecting and using first the unlabeled samples with more consistent outputs over the course of training (i.e., "time-consistency") can improve the final test accuracy and save computation. Under the time-consistent data selection, we design an SSL objective composed of two self-supervised losses, i.e., a consistency loss between a sample and its augmentation, and a contrastive loss encouraging different samples to have different outputs. Our approach achieves SOTA on several SSL benchmarks with much fewer computations.
A Geometric Approach to Archetypal Analysis via Sparse Projections
Authors: Vinayak Abrol, Pulkit Sharma
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Data Visualization

Archetypal analysis (AA) aims to extract patterns using self-expressive decomposition of data as convex combinations of extremal points (on the convex hull) of the data. This work presents a computationally efficient greedy AA (GAA) algorithm. GAA leverages the underlying geometry and sparseness property of AA, is scalable to larger datasets, and has significantly faster convergence to existing methods. To achieve this, archetypes are learned via sparse projection of data in linearly transformed space. GAA employs an iterative subset selection approach to identify archetypes based on the sparsity of convex representations. The work further presents the use of GAA algorithm for extended AA models such as robust and kernel AA. Experimental results show that GAA is significantly faster while performing comparable to existing methods for tasks such as classification, data visualization/categorization.
Double Trouble in Double Descent: Bias and Variance(s) in the Lazy Regime
Authors: Stéphane d'Ascoli, Maria Refinetti, Giulio Biroli, Florent Krzakala
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Deep neural networks can achieve remarkable generalization performances while interpolating the training data. Rather than the U-curve emblematic of the bias-variance trade-off, their test error often follows a ``double descent"---a mark of the beneficial role of overparametrization. In this work, we develop a quantitative theory for this phenomenon in the so-called lazy learning regime of neural networks, by considering the problem of learning a high-dimensional function with random features regression. We obtain a precise asymptotic expression for the bias-variance decomposition of the test error, and show that the bias displays a phase transition at the interpolation threshold, beyond it which it remains constant. We disentangle the variances stemming from the sampling of the dataset, from the additive noise corrupting the labels, and from the initialization of the weights. We demonstrate that the latter two contributions are the crux of the double descent: they lead to the overfitting peak at the interpolation threshold and to the decay of the test error upon overparametrization. We quantify how they are suppressed by ensembling the outputs of $K$ independently initialized estimators. For $K\rightarrow \infty$, the test error is monotonously decreasing and remains constant beyond the interpolation threshold. We further compare the effects of overparametrizing, ensembling and regularizing. Finally, we present numerical experiments on classic deep learning setups to show that our results hold qualitatively in realistic lazy learning scenarios.
From Local SGD to Local Fixed Point Methods for Federated Learning
Authors: Grigory Malinovsky, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, Peter Richtarik
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Federated Learning

Most algorithms for solving optimization problems or finding saddle points of convex-concave functions are fixed point algorithms. In this work we consider the generic problem of finding a fixed point of an average of operators, or an approximation thereof, in a distributed setting. Our work is motivated by the needs of federated learning. In this context, each local operator models the computations done locally on a mobile device. We investigate two strategies to achieve such a consensus: one  based on a fixed number of  local steps, and the other based on randomized  computations. In both cases, the goal is to limit communication of the locally-computed variables, which is often the bottleneck in distributed frameworks. We perform convergence analysis of both methods and conduct a number of experiments highlighting the benefits of our approach.
Multidimensional Shape Constraints
Authors: Maya Gupta, Erez Louidor, Oleksandr Mangylov, Nobu Morioka, Tamann Narayan, Sen Zhao
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Additive models

We propose new multi-input shape constraints across four intuitive categories:  complements, diminishers, dominance, and unimodality constraints. We show these shape constraints can be checked and even enforced when training machine-learned models for linear models, generalized additive models, and the nonlinear function class of multi-layer lattice models. Toy examples and real-world experiments illustrate how the different shape constraints can be used to increase interpretability and better regularize machine-learned models.