pwc-archive/papers-with-abstracts huggingface dataset:
Learning Schatten--von Neumann Operators
Authors: Puoya Tabaghi, Maarten de Hoop, Ivan Dokmanić
Date: 2019-01-29 00:00:00
Tasks: Learning Theory

We study the learnability of a class of compact operators known as
Schatten--von Neumann operators. These operators between infinite-dimensional
function spaces play a central role in a variety of applications in learning
theory and inverse problems. We address the question of sample complexity of
learning Schatten-von Neumann operators and provide an upper bound on the
number of measurements required for the empirical risk minimizer to generalize
with arbitrary precision and probability, as a function of class parameter $p$.
Our results give generalization guarantees for regression of
infinite-dimensional signals from infinite-dimensional data. Next, we adapt the
representer theorem of Abernethy \emph{et al.} to show that empirical risk
minimization over an a priori infinite-dimensional, non-compact set, can be
converted to a convex finite dimensional optimization problem over a compact
set. In summary, the class of $p$-Schatten--von Neumann operators is probably
approximately correct (PAC)-learnable via a practical convex program for any $p
< \infty$.
On the negation of a Dempster-Shafer belief structure based on maximum uncertainty allocation
Authors: Xinyang Deng, Wen Jiang
Date: 2019-01-29 00:00:00
Tasks: Negation

Probability theory and Dempster-Shafer theory are two germane theories to
represent and handle uncertain information. Recent study suggested a
transformation to obtain the negation of a probability distribution based on
the maximum entropy. Correspondingly, determining the negation of a belief
structure, however, is still an open issue in Dempster-Shafer theory, which is
very important in theoretical research and practical applications. In this
paper, a negation transformation for belief structures is proposed based on
maximum uncertainty allocation, and several important properties satisfied by
the transformation have been studied. The proposed negation transformation is
more general and could totally compatible with existing transformation for
probability distributions.
Committee Selection with Attribute Level Preferences
Authors: Venkateswara Rao Kagita, Arun K Pujari, Vineet Padmanabhan, Vikas Kumar
Date: 2019-01-29 00:00:00
Tasks: Attribute

We consider the problem of committee selection from a fixed set of candidates where each candidate has multiple quantifiable attributes. To select the best possible committee, instead of voting for a candidate, a voter is allowed to approve the preferred attributes of a given candidate. Though attribute based preference is addressed in several contexts, committee selection problem with attribute approval of voters has not been attempted earlier. A committee formed on attribute preferences is more likely to be a better representative of the qualities desired by the voters and is less likely to be susceptible to collusion or manipulation. In this work, we provide a formal study of the different aspects of this problem and define properties of weak unanimity, strong unanimity, simple justified representations and compound justified representation, that are required to be satisfied by the selected committee. We show that none of the existing vote/approval aggregation rules satisfy these new properties for attribute aggregation. We describe a greedy approach for attribute aggregation that satisfies the first three properties, but not the fourth, i.e., compound justified representation, which we prove to be NP-complete. Furthermore, we prove that finding a committee with justified representation and the highest approval voting score is NP-complete.
A Framework for Deep Constrained Clustering -- Algorithms and Advances
Authors: Hongjing Zhang, Sugato Basu, Ian Davidson
Date: 2019-01-29 00:00:00
Tasks: Clustering, Constrained Clustering, Deep Learning

The area of constrained clustering has been extensively explored by researchers and used by practitioners. Constrained clustering formulations exist for popular algorithms such as k-means, mixture models, and spectral clustering but have several limitations. A fundamental strength of deep learning is its flexibility, and here we explore a deep learning framework for constrained clustering and in particular explore how it can extend the field of constrained clustering. We show that our framework can not only handle standard together/apart constraints (without the well documented negative effects reported earlier) generated from labeled side information but more complex constraints generated from new types of side information such as continuous values and high-level domain knowledge.
Conditioning by adaptive sampling for robust design
Authors: David H. Brookes, Hahnbeom Park, Jennifer Listgarten
Date: 2019-01-29 00:00:00
Tasks: Protein Design, Robust Design

We present a new method for design problems wherein the goal is to maximize or specify the value of one or more properties of interest. For example, in protein design, one may wish to find the protein sequence that maximizes fluorescence. We assume access to one or more, potentially black box, stochastic "oracle" predictive functions, each of which maps from input (e.g., protein sequences) design space to a distribution over a property of interest (e.g. protein fluorescence). At first glance, this problem can be framed as one of optimizing the oracle(s) with respect to the input. However, many state-of-the-art predictive models, such as neural networks, are known to suffer from pathologies, especially for data far from the training distribution. Thus we need to modulate the optimization of the oracle inputs with prior knowledge about what makes `realistic' inputs (e.g., proteins that stably fold). Herein, we propose a new method to solve this problem, Conditioning by Adaptive Sampling, which yields state-of-the-art results on a protein fluorescence problem, as compared to other recently published approaches. Formally, our method achieves its success by using model-based adaptive sampling to estimate the conditional distribution of the input sequences given the desired properties.
A Regulation Enforcement Solution for Multi-agent Reinforcement Learning
Authors: Fan-Yun Sun, Yen-Yu Chang, Yueh-Hua Wu, Shou-De Lin
Date: 2019-01-29 00:00:00
Tasks: AI Agent, Management, Multi-agent Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Human behaviors are regularized by a variety of norms or regulations, either to maintain orders or to enhance social welfare. If artificially intelligent (AI) agents make decisions on behalf of human beings, we would hope they can also follow established regulations while interacting with humans or other AI agents. However, it is possible that an AI agent can opt to disobey the regulations (being defective) for self-interests. In this paper, we aim to answer the following question: Consider a multi-agent decentralized environment. Agents make decisions in complete isolation of other agents. Each agent knows the state of its own MDP and its own actions but it does not know the states and the actions taken by other players. There is a set of regulations for all agents to follow. Although most agents are benign and will comply to regulations but not all agents are compliant at first, can we develop a framework such that it is in the self-interest of non-compliant agents to comply after all?. We first introduce the problem as Regulation Enforcement and formulate it using reinforcement learning and game theory under the scenario where agents make decisions in complete isolation of other agents. We then propose a solution based on the key idea that although we could not alter how defective agents choose to behave, we can, however, leverage the aggregated power of compliant agents to boycott the defective ones. We conducted simulated experiments on two scenarios: Replenishing Resource Management Dilemma and Diminishing Reward Shaping Enforcement, using deep multi-agent reinforcement learning algorithms. We further use empirical game-theoretic analysis to show that the method alters the resulting empirical payoff matrices in a way that promotes compliance (making mutual compliant a Nash Equilibrium).
Towards Fair Deep Clustering With Multi-State Protected Variables
Authors: Bokun Wang, Ian Davidson
Date: 2019-01-29 00:00:00
Tasks: Attribute, Clustering, Deep Clustering, Fairness

Fair clustering under the disparate impact doctrine requires that population
of each protected group should be approximately equal in every cluster.
Previous work investigated a difficult-to-scale pre-processing step for
$k$-center and $k$-median style algorithms for the special case of this problem
when the number of protected groups is two. In this work, we consider a more
general and practical setting where there can be many protected groups. To this
end, we propose Deep Fair Clustering, which learns a discriminative but fair
cluster assignment function. The experimental results on three public datasets
with different types of protected attribute show that our approach can steadily
improve the degree of fairness while only having minor loss in terms of
clustering quality.
Knowledge Refinement via Rule Selection
Authors: Phokion G. Kolaitis, Lucian Popa, Kun Qian
Date: 2019-01-29 00:00:00
Tasks: Entity Resolution

In several different applications, including data transformation and entity
resolution, rules are used to capture aspects of knowledge about the
application at hand. Often, a large set of such rules is generated
automatically or semi-automatically, and the challenge is to refine the
encapsulated knowledge by selecting a subset of rules based on the expected
operational behavior of the rules on available data. In this paper, we carry
out a systematic complexity-theoretic investigation of the following rule
selection problem: given a set of rules specified by Horn formulas, and a pair
of an input database and an output database, find a subset of the rules that
minimizes the total error, that is, the number of false positive and false
negative errors arising from the selected rules. We first establish
computational hardness results for the decision problems underlying this
minimization problem, as well as upper and lower bounds for its
approximability. We then investigate a bi-objective optimization version of the
rule selection problem in which both the total error and the size of the
selected rules are taken into account. We show that testing for membership in
the Pareto front of this bi-objective optimization problem is DP-complete.
Finally, we show that a similar DP-completeness result holds for a bi-level
optimization version of the rule selection problem, where one minimizes first
the total error and then the size.
Dense Depth Posterior (DDP) from Single Image and Sparse Range
Authors: Yanchao Yang, Alex Wong, Stefano Soatto
Date: 2019-01-28 00:00:00
Proceeding: CVPR 2019 6
Tasks: Depth Completion

We present a deep learning system to infer the posterior distribution of a
dense depth map associated with an image, by exploiting sparse range
measurements, for instance from a lidar. While the lidar may provide a depth
value for a small percentage of the pixels, we exploit regularities reflected
in the training set to complete the map so as to have a probability over depth
for each pixel in the image. We exploit a Conditional Prior Network, that
allows associating a probability to each depth value given an image, and
combine it with a likelihood term that uses the sparse measurements. Optionally
we can also exploit the availability of stereo during training, but in any case
only require a single image and a sparse point cloud at run-time. We test our
approach on both unsupervised and supervised depth completion using the KITTI
benchmark, and improve the state-of-the-art in both.
Lyapunov-based Safe Policy Optimization for Continuous Control
Authors: Yin-Lam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman, Mohammad Ghavamzadeh
Date: 2019-01-28 00:00:00
Tasks: continuous-control, Continuous Control, MuJoCo, Reinforcement Learning, Robot Navigation

We study continuous action reinforcement learning problems in which it is
crucial that the agent interacts with the environment only through safe
policies, i.e.,~policies that do not take the agent to undesirable situations.
We formulate these problems as constrained Markov decision processes (CMDPs)
and present safe policy optimization algorithms that are based on a Lyapunov
approach to solve them. Our algorithms can use any standard policy gradient
(PG) method, such as deep deterministic policy gradient (DDPG) or proximal
policy optimization (PPO), to train a neural network policy, while guaranteeing
near-constraint satisfaction for every policy update by projecting either the
policy parameter or the action onto the set of feasible solutions induced by
the state-dependent linearized Lyapunov constraints. Compared to the existing
constrained PG algorithms, ours are more data efficient as they are able to
utilize both on-policy and off-policy data. Moreover, our action-projection
algorithm often leads to less conservative policy updates and allows for
natural integration into an end-to-end PG training pipeline. We evaluate our
algorithms and compare them with the state-of-the-art baselines on several
simulated (MuJoCo) tasks, as well as a real-world indoor robot navigation
problem, demonstrating their effectiveness in terms of balancing performance
and constraint satisfaction. Videos of the experiments can be found in the
following link:
https://drive.google.com/file/d/1pzuzFqWIE710bE2U6DmS59AfRzqK2Kek/view?usp=sharing.
Heterogeneous Network Motifs
Authors: Ryan A. Rossi, Nesreen K. Ahmed, Aldo Carranza, David Arbour, Anup Rao, Sungchul Kim, Eunyee Koh
Date: 2019-01-28 00:00:00

Many real-world applications give rise to large heterogeneous networks where nodes and edges can be of any arbitrary type (e.g., user, web page, location). Special cases of such heterogeneous graphs include homogeneous graphs, bipartite, k-partite, signed, labeled graphs, among many others. In this work, we generalize the notion of network motifs to heterogeneous networks. In particular, small induced typed subgraphs called typed graphlets (heterogeneous network motifs) are introduced and shown to be the fundamental building blocks of complex heterogeneous networks. Typed graphlets are a powerful generalization of the notion of graphlet (network motif) to heterogeneous networks as they capture both the induced subgraph of interest and the types associated with the nodes in the induced subgraph. To address this problem, we propose a fast, parallel, and space-efficient framework for counting typed graphlets in large networks. We discover the existence of non-trivial combinatorial relationships between lower-order ($k-1$)-node typed graphlets and leverage them for deriving many of the $k$-node typed graphlets in $o(1)$ constant time. Thus, we avoid explicit enumeration of those typed graphlets. Notably, the time complexity matches the best untyped graphlet counting algorithm. The experiments demonstrate the effectiveness of the proposed framework in terms of runtime, space-efficiency, parallel speedup, and scalability as it is able to handle large-scale networks.
Cross-Domain Image Manipulation by Demonstration
Authors: Ben Usman, Nick Dufour, Kate Saenko, Chris Bregler
Date: 2019-01-28 00:00:00
Tasks: Attribute, Image Manipulation

In this work we propose a model that can manipulate individual visual
attributes of objects in a real scene using examples of how respective
attribute manipulations affect the output of a simulation. As an example, we
train our model to manipulate the expression of a human face using
nonphotorealistic 3D renders of a face with varied expression. Our model
manages to preserve all other visual attributes of a real face, such as head
orientation, even though this and other attributes are not labeled in either
real or synthetic domain. Since our model learns to manipulate a specific
property in isolation using only "synthetic demonstrations" of such
manipulations without explicitly provided labels, it can be applied to shape,
texture, lighting, and other properties that are difficult to measure or
represent as real-valued vectors. We measure the degree to which our model
preserves other attributes of a real image when a single specific attribute is
manipulated. We use digit datasets to analyze how discrepancy in attribute
distributions affects the performance of our model, and demonstrate results in
a far more difficult setting: learning to manipulate real human faces using
nonphotorealistic 3D renders.
Steerable Wavelet Scattering for 3D Atomic Systems with Application to Li-Si Energy Prediction
Authors: Xavier Brumwell, Paul Sinz, Kwang Jin Kim, Yue Qi, Matthew Hirn
Date: 2018-11-21 00:00:00
Tasks: BIG-bench Machine Learning, Formation Energy, regression

A general machine learning architecture is introduced that uses wavelet
scattering coefficients of an inputted three dimensional signal as features.
Solid harmonic wavelet scattering transforms of three dimensional signals were
previously introduced in a machine learning framework for the regression of
properties of small organic molecules. Here this approach is extended for
general steerable wavelets which are equivariant to translations and rotations,
resulting in a sparse model of the target function. The scattering coefficients
inherit from the wavelets invariance to translations and rotations. As an
illustration of this approach a linear regression model is learned for the
formation energy of amorphous lithium-silicon material states trained over a
database generated using plane-wave Density Functional Theory methods.
State-of-the-art results are produced as compared to other machine learning
approaches over similarly generated databases.
The OoO VLIW JIT Compiler for GPU Inference
Authors: Paras Jain, Xiangxi Mo, Ajay Jain, Alexey Tumanov, Joseph E. Gonzalez, Ion Stoica
Date: 2019-01-28 00:00:00
Tasks: GPU

Current trends in Machine Learning~(ML) inference on hardware accelerated
devices (e.g., GPUs, TPUs) point to alarmingly low utilization. As ML inference
is increasingly time-bounded by tight latency SLOs, increasing data parallelism
is not an option. The need for better efficiency motivates GPU multiplexing.
Furthermore, existing GPU programming abstractions force programmers to
micro-manage GPU resources in an early-binding, context-free fashion. We
propose a VLIW-inspired Out-of-Order (OoO) Just-in-Time (JIT) compiler that
coalesces and reorders execution kernels at runtime for throughput-optimal
device utilization while satisfying latency SLOs. We quantify the
inefficiencies of space-only and time-only multiplexing alternatives and
demonstrate an achievable 7.7x opportunity gap through spatial coalescing.
A Framework for Understanding Sources of Harm throughout the Machine Learning Life Cycle
Authors: Harini Suresh, John V. Guttag
Date: 2019-01-28 00:00:00
Tasks: BIG-bench Machine Learning

As machine learning (ML) increasingly affects people and society, awareness of its potential unwanted consequences has also grown. To anticipate, prevent, and mitigate undesirable downstream consequences, it is critical that we understand when and how harm might be introduced throughout the ML life cycle. In this paper, we provide a framework that identifies seven distinct potential sources of downstream harm in machine learning, spanning data collection, development, and deployment. In doing so, we aim to facilitate more productive and precise communication around these issues, as well as more direct, application-grounded ways to mitigate them.
Quasi-Newton Methods for Machine Learning: Forget the Past, Just Sample
Authors: Albert S. Berahas, Majid Jahani, Peter Richtárik, Martin Takáč
Date: 2019-01-28 00:00:00
Tasks: Benchmarking, BIG-bench Machine Learning, Binary Classification, Distributed Computing, General Classification

We present two sampled quasi-Newton methods (sampled LBFGS and sampled LSR1) for solving empirical risk minimization problems that arise in machine learning. Contrary to the classical variants of these methods that sequentially build Hessian or inverse Hessian approximations as the optimization progresses, our proposed methods sample points randomly around the current iterate at every iteration to produce these approximations. As a result, the approximations constructed make use of more reliable (recent and local) information, and do not depend on past iterate information that could be significantly stale. Our proposed algorithms are efficient in terms of accessed data points (epochs) and have enough concurrency to take advantage of parallel/distributed computing environments. We provide convergence guarantees for our proposed methods. Numerical tests on a toy classification problem as well as on popular benchmarking binary classification and neural network training tasks reveal that the methods outperform their classical variants.
Label Efficient Semi-Supervised Learning via Graph Filtering
Authors: Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, Zhichao Guan
Date: 2019-01-28 00:00:00
Proceeding: CVPR 2019 6
Tasks: General Classification, Graph Similarity

Graph-based methods have been demonstrated as one of the most effective approaches for semi-supervised learning, as they can exploit the connectivity patterns between labeled and unlabeled data samples to improve learning performance. However, existing graph-based methods either are limited in their ability to jointly model graph structures and data features, such as the classical label propagation methods, or require a considerable amount of labeled data for training and validation due to high model complexity, such as the recent neural-network-based methods. In this paper, we address label efficient semi-supervised learning from a graph filtering perspective. Specifically, we propose a graph filtering framework that injects graph similarity into data features by taking them as signals on the graph and applying a low-pass graph filter to extract useful data representations for classification, where label efficiency can be achieved by conveniently adjusting the strength of the graph filter. Interestingly, this framework unifies two seemingly very different methods -- label propagation and graph convolutional networks. Revisiting them under the graph filtering framework leads to new insights that improve their modeling capabilities and reduce model complexity. Experiments on various semi-supervised classification tasks on four citation networks and one knowledge graph and one semi-supervised regression task for zero-shot image recognition validate our findings and proposals.