pwc-archive/papers-with-abstracts huggingface dataset:
p-Norm Flow Diffusion for Local Graph Clustering
Authors: Kimon Fountoulakis, Di Wang, Shenghao Yang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Clustering, Community Detection, Graph Clustering

Local graph clustering and the closely related seed set expansion problem are primitives on graphs that are central to a wide range of analytic and learning tasks such as local clustering, community detection, nodes ranking and feature inference. Prior work on local graph clustering mostly falls into two categories with numerical and combinatorial roots respectively. 
In this work, we draw inspiration from both fields and propose a family of convex optimization formulations based on the idea of diffusion with $p$-norm network flow for $p\in (1,\infty)$. 

In the context of local clustering, we characterize the optimal solutions for these optimization problems and show their usefulness in finding low conductance cuts around input seed set. In particular, we achieve quadratic approximation of conductance in the case of $p=2$ similar to the Cheeger-type bounds of spectral methods, constant factor approximation when $p\rightarrow\infty$ similar to max-flow based methods, and a smooth transition for general $p$ values in between. Thus, our optimization formulation can be viewed as bridging the numerical and combinatorial approaches, and we can achieve the best of both worlds in terms of speed and noise robustness. 

We show that the proposed problem can be solved in strongly local running time for $p\ge 2$ and conduct empirical evaluations on both synthetic and real-world graphs to illustrate our approach compares favorably with existing methods.
PoKED: A Semi-Supervised System for Word Sense Disambiguation
Authors: Feng Wei
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Language Modeling, Language Modelling, Position, Sentence, Word Sense Disambiguation

Word Sense Disambiguation (WSD) is an open problem in Natural Language Processing, which is challenging and useful in both supervised and unsupervised settings where all the words in any given text need to be disambiguated without sufficient labeled data. Typically, Most WSD systems use the sentence or a small window of words around the target word as the context for disambiguation, as their computational complexity scales exponentially with the size of the context. In this paper, we propose a semi-supervised neural system, Position-wise Orthogonal Knowledge-Enhanced Disambiguator (PoKED), which allows attention-driven, long-range dependency modeling for word sense disambiguation tasks. The proposed PoKED incorporates position-wise encoding into an orthogonal framework and applies a knowledge-based attentive neural model to solve the WSD problem. Our proposed unsupervised language model is trained over unlabelled corpus, and then the pre-trained language model is capable of abstracting the surrounding context of polyseme instances in labeled corpus into context embeddings. We further utilize the semantic relations in the WordNet, by extracting semantic level inter-word connections from each document-sentence pair in the WSD dataset, and allows us to control the amount of the extraction results by setting a hyperparameter. Our experimental results from standard benchmarks show that our proposed system, PoKED, can achieve competitive performance compared with state-of-the-art knowledge-based WSD systems.
Robust Pricing in Dynamic Mechanism Design
Authors: Yuan Deng, Sébastien Lahaie, Vahab Mirrokni
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Motivated by the repeated sale of online ads via auctions, optimal pricing in repeated auctions has attracted a large body of research. While dynamic mechanisms offer powerful techniques to improve on both revenue and efficiency by optimizing auctions across different items, their reliance on exact distributional information of buyers' valuations (present and future) limits their use in practice. In this paper, we propose robust dynamic mechanism design. We develop a new framework to design dynamic mechanisms that are robust to both estimation errors in value distributions and strategic behavior. We apply the framework in learning environments, leading to the first policy that achieves provably low regret against the optimal dynamic mechanism in contextual auctions, where the dynamic benchmark has full and accurate distributional information.
Task Understanding from Confusing Multi-task Data
Authors: Xin Su, Yizhou Jiang, Shangqi Guo, Feng Chen
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Multi-Task Learning

Beyond machine learning's success in the specific tasks, research for learning multiple tasks simultaneously is referred to as multi-task learning. However, existing multi-task learning needs manual definition of tasks and manual task annotation. A crucial problem for advanced intelligence is how to understand the human task concept using basic input-output pairs. Without task definition, samples from multiple tasks are mixed together and result in a confusing mapping challenge. We propose Confusing Supervised Learning (CSL) that takes these confusing samples and extracts task concepts by differentiating between these samples. We theoretically proved the feasibility of the CSL framework and designed an iterative algorithm to distinguish between tasks. The experiments demonstrate that our CSL methods could achieve a human-like task understanding without task labeling in multi-function regression problems and multi-task recognition problems.
Towards Accurate Post-training Network Quantization via Bit-Split and Stitching
Authors: Peisong Wang, Qiang Chen, Xiangyu He, Jian Cheng
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: CPU, GPU, image-classification, Image Classification, Instance Segmentation, object-detection, Object Detection, Quantization, Semantic Segmentation

Network quantization is essential for deploying deep models to IoT devices due to the high efficiency, no matter on special hardware like TPU or general hardware like CPU and GPU. Most existing quantization approaches rely on retraining to retain accuracy, which is referred to as quantization-aware training. However, this quantization scheme assumes the access to the training data, which is not always the case. Moreover, retraining is a tedious and time-consuming procedure, which hinders the application of quantization to a wider range of tasks. Post-training quantization, on the other hand, does not have these problems. However, it has only been shown effective for 8-bit quantization due to the simple optimization strategy. In this paper, we propose a Bit-Split and Stitching framework for lower-bit post-training quantization with minimal accuracy degradation. The proposed framework are validated on a variety of computer vision tasks, including image classification, object detection, instance segmentation, with various network architectures.
Transparency Promotion with Model-Agnostic Linear Competitors
Authors:  Hassan Rafique, Tong Wang, Qihang Lin, Arshia Singhani
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Decision Making, model, Multi-class Classification

We propose a novel type of hybrid model for multi-class classification, which utilizes competing linear models to collaborate with an existing black-box model, promoting transparency in the decision-making process. Our proposed hybrid model, Model-Agnostic Linear Competitors (MALC), brings together the interpretable power of linear models and the good predictive performance of the state-of-the-art black-box models. We formulate the training of a MALC model as a convex optimization problem, which optimizes the predictive accuracy and transparency (defined as the percentage of data captured by the linear models) in the objective function. Experiments show that MALC offers more model flexibility for users to balance transparency and accuracy, in contrast to the currently available choice of either a pure black-box model or a pure interpretable model. The human evaluation also shows that more users are likely to choose MALC for this model flexibility when comparing with interpretable models and black-box models.
Understanding Contrastive Representation Learning through Geometry on the Hypersphere
Authors: Tongzhou Wang, Phillip Isola
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Contrastive Learning, Depth Estimation, Depth Prediction, image-classification, Image Classification, Representation Learning

Contrastive representation learning has been outstandingly successful in practice. In this work, we identify two key properties related to the contrastive loss: (1) alignment (closeness) of features from positive pairs, and (2) uniformity of the induced distribution of the (normalized) features on the hypersphere. We prove that, asymptotically, the contrastive loss indeed optimizes these properties, and analyze their positive effects on downstream tasks. Empirically, we introduce an optimizable metric to quantify each property. Extensive experiments on standard image classification and depth prediction datasets confirm the strong agreement between both metrics and downstream task performance. Remarkably, directly optimizing for these two metrics leads to representations with comparable or better performance at downstream tasks than contrastive learning.
Universal Asymptotic Optimality of Polyak Momentum
Authors: Damien Scieur, Fabian Pedregosa
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We consider the average-case runtime analysis of algorithms for minimizing quadratic objectives.
In this setting, and contrary to the more classical worst-case analysis,
non-asymptotic convergence rates and optimal algorithms depend on the full spectrum of the Hessian through its expected spectral distribution. 
Under mild assumptions, we show that these optimal methods converge asymptotically towards Polyak momentum \emph{independently} of the expected spectral density. This makes Polyak momentum universally (i.e., independent of the spectral distribution) asymptotically average-case optimal.
Upper bounds for Model-Free Row-Sparse Principal Component Analysis
Authors: Guanyi Wang, Santanu Dey
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Dimensionality Reduction

Sparse principal component analysis (PCA) is a widely-used dimensionality reduction tool in statistics and machine learning. Most methods mentioned in literature are either heuristics for good primal feasible solutions under statistical assumptions or ADMM-type algorithms with stationary/critical points convergence property for the regularized reformulation of sparse PCA. However, none of these methods can efficiently verify the quality of the solutions via comparing current objective values with their dual bounds, especially in model-free case. We propose a new framework that finds out upper (dual) bounds for the sparse PCA within polynomial time via solving a convex integer program (IP). We show that, in the worst-case, the dual bounds provided by the convex IP is within an affine function of the global optimal value. Moreover, in contrast to the semi-definition relaxation, this framework is much easier to scale on large cases. Numerical results on both artificial and real cases are reported to demonstrate the advantages of our method.
ACFlow: Flow Models for Arbitrary Conditional Likelihoods
Authors: Yang Li, Shoaib Akbar, Junier Oliva
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Imputation

Understanding the dependencies among features of a dataset is at the core of most unsupervised learning tasks. However, a majority of generative modeling approaches are focused solely on the joint distribution $p(x)$ and utilize models where it is intractable to obtain the conditional distribution of some arbitrary subset of features $x_u$ given the rest of the observed covariates $x_o$: $p(x_u \mid x_o)$. Traditional conditional approaches provide a model for a \emph{fixed} set of covariates conditioned on another \emph{fixed} set of observed covariates. Instead, in this work we develop a model that is capable of yielding \emph{all} conditional distributions $p(x_u \mid x_o)$ (for arbitrary $x_u$) via tractable conditional likelihoods. We propose a novel extension of (change of variables based) flow generative models, arbitrary conditioning flow models (ACFlow). ACFlow can be conditioned on arbitrary subsets of observed covariates, which was previously infeasible. We further extend ACFlow to model the joint distributions $p(x)$ and arbitrary marginal distributions $p(x_u)$. We also apply ACFlow to the imputation of features, and develop a unified platform for both multiple and single imputation by introducing an auxiliary objective that provides a principled single ``best guess'' for flow models. Extensive empirical evaluations show that our model achieves state-of-the-art performance in modeling arbitrary conditional likelihoods in addition to both single and multiple imputation in synthetic and real-world datasets.
A Nearly-Linear Time Algorithm for Exact Community Recovery in Stochastic Block Model
Authors: Peng Wang, Zirui Zhou, Anthony Man-Cho So
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Stochastic Block Model

Learning community structures in graphs that are randomly generated by stochastic block models (SBMs) has received much attention lately. In this paper, we focus on the problem of exactly recovering the communities in a binary symmetric SBM, where a graph of $n$ vertices is partitioned into two equal-sized communities and the vertices are connected with probability $p = \alpha\log(n)/n$ within communities and $q = \beta\log(n)/n$ across communities for some $\alpha>\beta>0$. We propose a two-stage iterative algorithm for solving this problem, which employs the power method with a random starting point in the first-stage and turns to a generalized power method that can identify the communities in a finite number of iterations in the second-stage. It is shown that for any fixed $\alpha$ and $\beta$ such that $\sqrt{\alpha} - \sqrt{\beta} > \sqrt{2}$, which is known to be the information-theoretical limit for exact recovery, the proposed algorithm exactly identifies the underlying communities in $\tilde{O}(n)$ running time with probability tending to one as $n\rightarrow\infty$. As far as we know, this is the first algorithm with nearly-linear running time that achieves exact recovery at the information-theoretical limit. We also present numerical results of the proposed algorithm to support and complement our theoretical development.
Breaking the Curse of Many Agents: Provable Mean Embedding $Q$-Iteration for Mean-Field Reinforcement Learning
Authors: Lingxiao Wang, Zhuoran Yang, Zhaoran Wang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Multi-agent Reinforcement Learning, reinforcement-learning, Reinforcement Learning (RL)

Multi-agent reinforcement learning (MARL) achieves significant empirical successes. However, MARL suffers from the curse of many agents. In this paper, we exploit the symmetry of agents in MARL. In the most generic form, we study a mean-field MARL problem. Such a mean-field MARL is defined on mean-field states, which are distributions that are supported on continuous space. Based on the mean embedding of the distributions, we propose MF-FQI algorithm, which solves the mean-field MARL and establishes a non-asymptotic analysis for MF-FQI algorithm. We highlight that MF-FQI algorithm enjoys a ``blessing of many agents'' property in the sense that a larger number of observed agents improves the performance of MF-FQI algorithm.
Composing Molecules with Multiple Property Constraints
Authors: Wengong Jin, Regina Barzilay, Tommi Jaakkola
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Diversity, Drug Design, Drug Discovery

Drug discovery aims to find novel compounds with specified chemical property profiles. In terms of generative modeling, the goal is to learn to sample molecules in the intersection of multiple property constraints. This task becomes increasingly challenging when there are many property constraints. We propose to offset this complexity by composing molecules from a vocabulary of substructures that we call molecular rationales. These rationales are identified from molecules as substructures that are likely responsible for each property of interest. We then learn to expand rationales into a full molecule using graph generative models. Our final generative model composes molecules as mixtures of multiple rationale completions, and this mixture is fine-tuned to preserve the properties of interest. We evaluate our model on various drug design tasks and demonstrate significant improvements over state-of-the-art baselines in terms of accuracy, diversity, and novelty of generated compounds.
Computational and Statistical Tradeoffs in Inferring Combinatorial Structures of Ising Model
Authors: Ying Jin, Zhaoran Wang, Junwei Lu
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: valid

We study the computational and statistical tradeoffs in inferring combinatorial structures of high dimensional simple zero-field ferromagnetic Ising model. Under the framework of oracle computational model where an algorithm interacts with an oracle that discourses a randomized version of truth, we characterize the computational lower bounds of learning combinatorial structures in polynomial time, under which no algorithms within polynomial-time can distinguish between graphs with and without certain structures. This hardness of learning with limited computational budget is shown to be characterized by a novel quantity called vertex overlap ratio. Such quantity is universally valid for many specific graph structures including cliques and nearest neighbors. On the other side, we attain the optimal rates for testing these structures against empty graph by proposing the quadratic testing statistics to match the lower bounds. We also investigate the relationship between computational bounds and information-theoretic bounds for such problems, and found gaps between the two boundaries in inferring some particular structures, especially for those with dense edges.
Conditional Augmentation for Generative Modeling
Authors: Heewoo Jun, Rewon Child, Mark Chen, John Schulman, Aditya Ramesh, Alec Radford, Ilya Sutskever
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Data Augmentation, Self-Supervised Learning

We present conditional augmentation (CondAugment), a simple and powerful method of regularizing generative models. Core to our approach is applying augmentation functions to data and then conditioning the generative model on the specific function used. Unlike typical data augmentation, CondAugment allows usage of functions which modify the target density, enabling aggressive augmentations more commonly seen in supervised and self-supervised learning. We demonstrate this is a more effective regularizer than standard methods, and use it to train a 150M parameter autoregressive model on CIFAR-10 to 2.56 bits per dim (relative to the state-of-the-art 2.80). Samples from this model attain FID 12.75 and IS 8.40, outperforming the majority of GANs. We further demonstrate the technique is broadly applicable across model architectures, objectives, and problem domains.
Converging to Team-Maxmin Equilibria in Zero-Sum Multiplayer Games
Authors: Youzhi Zhang, Bo An
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Efficiently computing equilibria for multiplayer games is still an open challenge in computational game theory. This paper focuses on computing Team-Maxmin Equilibria (TMEs), which is an important solution concept for zero-sum multiplayer
games where players in a team having the same utility function play against an adversary independently. Existing algorithms are inefficient to compute TMEs in large games, especially when the strategy space is too large to be represented due to limited memory. In two-player games, the Incremental Strategy Generation (ISG) algorithm is an efficient approach to avoid enumerating all pure strategies. However, the study of ISG for computing TMEs is completely unexplored. To fill this gap, we first study the properties of ISG for multiplayer games, showing that ISG converges to a Nash equilibrium (NE) but may not converge to a TME. Second, we design an ISG variant for TMEs (ISGT) by exploiting that a TME is an NE maximizing the team’s utility and show that ISGT converges to a TME and the impossibility of relaxing conditions in ISGT. Third, to further improve the scalability, we design an ISGT variant (CISGT) by using the strategy space for computing an equilibrium that is close to TME but is easier to be computed as the initial strategy space of ISGT. Finally, extensive experimental results show that CISGT is orders of magnitude faster than ISGT and the state-of-the-art algorithm to compute TMEs in large games.
Generalization via Derandomization
Authors: Jeffrey Negrea, Daniel Roy, Gintare Karolina Dziugaite
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We propose to study the generalization error of a learned predictor h^ in terms of that of a surrogate (potentially randomized) classifier that is coupled to h^ and designed to trade empirical risk for control of generalization error. In the case where h^ interpolates the data, it is interesting to consider theoretical surrogate classifiers that are partially derandomized or rerandomized, e.g., fit to the training data but with modified label noise. We show that replacing h^ by its conditional distribution with respect to an arbitrary sigma-field is a viable method to derandomize. We give an example, inspired by the work of Nagarajan and Kolter (2019), where the learned classifier h^ interpolates the training data with high probability, has small risk, and, yet, does not belong to a nonrandom class with a tight uniform bound on two-sided generalization error. At the same time, we bound the risk of h^ in terms of a surrogate that is constructed by conditioning and shown to belong to a nonrandom class with uniformly small generalization error.
Goodness-of-Fit Tests for Inhomogeneous Random Graphs
Authors: Soham Dan, Bhaswar B. Bhattacharya
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Two-sample testing

Hypothesis testing of random networks is an emerging area of modern research, especially in the high-dimensional regime, where the  number of samples is smaller or comparable to the size of the graph.  In this paper we consider the goodness-of-fit testing problem for large inhomogeneous random (IER) graphs, where given a (known) reference symmetric matrix $Q \in [0, 1]^{n \times n}$ and $m$ independent samples from an IER graph given by an unknown  symmetric matrix $P \in [0, 1]^{n \times n}$, the goal is to test the hypothesis $P=Q$ versus $||P-Q|| \geq \varepsilon$, where $||\cdot||$ is some specified norm on symmetric matrices. Building on recent related work on two-sample testing for IER graphs, we derive the optimal minimax sample complexities for the goodness-of-fit problem in various natural norms, such as the Frobenius norm and the operator norm. We also propose practical implementations of natural test statistics, using their asymptotic distributions and through the parametric bootstrap. We compare the performances of the different tests in simulations, and show that the proposed  tests outperform the baseline tests across various natural random graphs models.