pwc-archive/papers-with-abstracts huggingface dataset:
A Ranking Approach to Fair Classification
Authors: Jakob Schoeffer, Niklas Kuehl, Isabel Valera
Date: 2021-02-08 00:00:00
Tasks: Classification, Decision Making, Fairness, General Classification

Algorithmic decision systems are increasingly used in areas such as hiring, school admission, or loan approval. Typically, these systems rely on labeled data for training a classification model. However, in many scenarios, ground-truth labels are unavailable, and instead we have only access to imperfect labels as the result of (potentially biased) human-made decisions. Despite being imperfect, historical decisions often contain some useful information on the unobserved true labels. In this paper, we focus on scenarios where only imperfect labels are available and propose a new fair ranking-based decision system based on monotonic relationships between legitimate features and the outcome. Our approach is both intuitive and easy to implement, and thus particularly suitable for adoption in real-world settings. More in detail, we introduce a distance-based decision criterion, which incorporates useful information from historical decisions and accounts for unwanted correlation between protected and legitimate features. Through extensive experiments on synthetic and real-world data, we show that our method is fair in the sense that a) it assigns the desirable outcome to the most qualified individuals, and b) it removes the effect of stereotypes in decision-making, thereby outperforming traditional classification algorithms. Additionally, we are able to show theoretically that our method is consistent with a prominent concept of individual fairness which states that "similar individuals should be treated similarly."
Rationally Inattentive Utility Maximization for Interpretable Deep Image Classification
Authors: Kunal Pattanayak, Vikram Krishnamurthy
Date: 2021-02-09 00:00:00
Tasks: Classification, Decision Making, General Classification, image-classification, Image Classification

Are deep convolutional neural networks (CNNs) for image classification explainable by utility maximization with information acquisition costs? We demonstrate that deep CNNs behave equivalently (in terms of necessary and sufficient conditions) to rationally inattentive utility maximizers, a generative model used extensively in economics for human decision making. Our claim is based by extensive experiments on 200 deep CNNs from 5 popular architectures. The parameters of our interpretable model are computed efficiently via convex feasibility algorithms. As an application, we show that our economics-based interpretable model can predict the classification performance of deep CNNs trained with arbitrary parameters with accuracy exceeding 94% . This eliminates the need to re-train the deep CNNs for image classification. The theoretical foundation of our approach lies in Bayesian revealed preference studied in micro-economics. All our results are on GitHub and completely reproducible.
WheaCha: A Method for Explaining the Predictions of Models of Code
Authors: Yu Wang, Ke Wang, Linzhang Wang
Date: 2021-02-09 00:00:00
Tasks: BIG-bench Machine Learning, Code Summarization, Feature Importance, Image Classification, Prediction, Source Code Summarization

Attribution methods have emerged as a popular approach to interpreting model predictions based on the relevance of input features. Although the feature importance ranking can provide insights of how models arrive at a prediction from a raw input, they do not give a clear-cut definition of the key features models use for the prediction. In this paper, we present a new method, called WheaCha, for explaining the predictions of code models. Although WheaCha employs the same mechanism of tracing model predictions back to the input features, it differs from all existing attribution methods in crucial ways. Specifically, WheaCha divides an input program into "wheat" (i.e., the defining features that are the reason for which models predict the label that they predict) and the rest "chaff" for any prediction of a learned code model. We realize WheaCha in a tool, HuoYan, and use it to explain four prominent code models: code2vec, seq-GNN, GGNN, and CodeBERT. Results show (1) HuoYan is efficient - taking on average under twenty seconds to compute the wheat for an input program in an end-to-end fashion (i.e., including model prediction time); (2) the wheat that all models use to predict input programs is made of simple syntactic or even lexical properties (i.e., identifier names); (3) Based on wheat, we present a novel approach to explaining the predictions of code models through the lens of training data.
MALI: A memory efficient and reverse accurate integrator for Neural ODEs
Authors: Juntang Zhuang, Nicha C. Dvornek, Sekhar Tatikonda, James S. Duncan
Date: 2021-02-09 00:00:00
Proceeding: ICLR 2021 1
Tasks: Image Generation, Time Series, Time Series Analysis

Neural ordinary differential equations (Neural ODEs) are a new family of deep-learning models with continuous depth. However, the numerical estimation of the gradient in the continuous case is not well solved: existing implementations of the adjoint method suffer from inaccuracy in reverse-time trajectory, while the naive method and the adaptive checkpoint adjoint method (ACA) have a memory cost that grows with integration time. In this project, based on the asynchronous leapfrog (ALF) solver, we propose the Memory-efficient ALF Integrator (MALI), which has a constant memory cost \textit{w.r.t} number of solver steps in integration similar to the adjoint method, and guarantees accuracy in reverse-time trajectory (hence accuracy in gradient estimation). We validate MALI in various tasks: on image recognition tasks, to our knowledge, MALI is the first to enable feasible training of a Neural ODE on ImageNet and outperform a well-tuned ResNet, while existing methods fail due to either heavy memory burden or inaccuracy; for time series modeling, MALI significantly outperforms the adjoint method; and for continuous generative models, MALI achieves new state-of-the-art performance. We provide a pypi package at \url{https://jzkay12.github.io/TorchDiffEqPack/}
Graph-Aided Online Multi-Kernel Learning
Authors: Pouya M Ghari, Yanning Shen
Date: 2021-02-09 00:00:00

Multi-kernel learning (MKL) has been widely used in function approximation tasks. The key problem of MKL is to combine kernels in a prescribed dictionary. Inclusion of irrelevant kernels in the dictionary can deteriorate accuracy of MKL, and increase the computational complexity. To improve the accuracy of function approximation and reduce the computational complexity, the present paper studies data-driven selection of kernels from the dictionary that provide satisfactory function approximations. Specifically, based on the similarities among kernels, the novel framework constructs and refines a graph to assist choosing a subset of kernels. In addition, random feature approximation is utilized to enable online implementation for sequentially obtained data. Theoretical analysis shows that our proposed algorithms enjoy tighter sub-linear regret bound compared with state-of-art graph-based online MKL alternatives. Experiments on a number of real datasets also showcase the advantages of our novel graph-aided framework.
Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
Authors: Haike Xu, Tengyu Ma, Simon S. Du
Date: 2021-02-09 00:00:00
Tasks: Multi-Armed Bandits

This paper presents a new model-free algorithm for episodic finite-horizon Markov Decision Processes (MDP), Adaptive Multi-step Bootstrap (AMB), which enjoys a stronger gap-dependent regret bound. The first innovation is to estimate the optimal $Q$-function by combining an optimistic bootstrap with an adaptive multi-step Monte Carlo rollout. The second innovation is to select the action with the largest confidence interval length among admissible actions that are not dominated by any other actions. We show when each state has a unique optimal action, AMB achieves a gap-dependent regret bound that only scales with the sum of the inverse of the sub-optimality gaps. In contrast, Simchowitz and Jamieson (2019) showed all upper-confidence-bound (UCB) algorithms suffer an additional $\Omega\left(\frac{S}{\Delta_{min}}\right)$ regret due to over-exploration where $\Delta_{min}$ is the minimum sub-optimality gap and $S$ is the number of states. We further show that for general MDPs, AMB suffers an additional $\frac{|Z_{mul}|}{\Delta_{min}}$ regret, where $Z_{mul}$ is the set of state-action pairs $(s,a)$'s satisfying $a$ is a non-unique optimal action for $s$. We complement our upper bound with a lower bound showing the dependency on $\frac{|Z_{mul}|}{\Delta_{min}}$ is unavoidable for any consistent algorithm. This lower bound also implies a separation between reinforcement learning and contextual bandits.
Inapproximability of a Pair of Forms Defining a Partial Boolean Function
Authors: David Stein, Bjoern Andres
Date: 2021-02-09 00:00:00

We consider the problem of jointly minimizing forms of two Boolean functions $f, g \colon \{0,1\}^J \to \{0,1\}$ such that $f + g \leq 1$ and so as to separate disjoint sets $A \cup B \subseteq \{0,1\}^J$ such that $f(A) = \{1\}$ and $g(B) = \{1\}$. We hypothesize that this problem is easier to solve or approximate than the well-understood problem of minimizing the form of one Boolean function $h: \{0,1\}^J \to \{0,1\}$ such that $h(A) = \{1\}$ and $h(B) = \{0\}$. For a large class of forms, including binary decision trees and ordered binary decision diagrams, we refute this hypothesis. For disjunctive normal forms, we show that the problem is at least as hard as MIN-SET-COVER. For all these forms, we establish that no $o(\ln (|A| + |B| -1))$-approximation algorithm exists unless P$=$NP.
Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Training
Authors: Lue Tao, Lei Feng, JinFeng Yi, Sheng-Jun Huang, Songcan Chen
Date: 2021-02-09 00:00:00
Proceeding: NeurIPS 2021 12

Delusive attacks aim to substantially deteriorate the test accuracy of the learning model by slightly perturbing the features of correctly labeled training examples. By formalizing this malicious attack as finding the worst-case training data within a specific $\infty$-Wasserstein ball, we show that minimizing adversarial risk on the perturbed data is equivalent to optimizing an upper bound of natural risk on the original data. This implies that adversarial training can serve as a principled defense against delusive attacks. Thus, the test accuracy decreased by delusive attacks can be largely recovered by adversarial training. To further understand the internal mechanism of the defense, we disclose that adversarial training can resist the delusive perturbations by preventing the learner from overly relying on non-robust features in a natural setting. Finally, we complement our theoretical findings with a set of experiments on popular benchmark datasets, which show that the defense withstands six different practical attacks. Both theoretical and empirical results vote for adversarial training when confronted with delusive adversaries.
Federated Learning with Local Differential Privacy: Trade-offs between Privacy, Utility, and Communication
Authors: Muah Kim, Onur Günlü, Rafael F. Schaefer
Date: 2021-02-09 00:00:00
Tasks: Federated Learning

Federated learning (FL) allows to train a massive amount of data privately due to its decentralized structure. Stochastic gradient descent (SGD) is commonly used for FL due to its good empirical performance, but sensitive user information can still be inferred from weight updates shared during FL iterations. We consider Gaussian mechanisms to preserve local differential privacy (LDP) of user data in the FL model with SGD. The trade-offs between user privacy, global utility, and transmission rate are proved by defining appropriate metrics for FL with LDP. Compared to existing results, the query sensitivity used in LDP is defined as a variable and a tighter privacy accounting method is applied. The proposed utility bound allows heterogeneous parameters over all users. Our bounds characterize how much utility decreases and transmission rate increases if a stronger privacy regime is targeted. Furthermore, given a target privacy level, our results guarantee a significantly larger utility and a smaller transmission rate as compared to existing privacy accounting methods.
Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
Authors: Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, Martin Jaggi
Date: 2021-02-09 00:00:00
Tasks: Deep Learning

Decentralized training of deep learning models is a key element for enabling data privacy and on-device learning over networks. In realistic learning scenarios, the presence of heterogeneity across different clients' local datasets poses an optimization challenge and may severely deteriorate the generalization performance. In this paper, we investigate and identify the limitation of several decentralized optimization algorithms for different degrees of data heterogeneity. We propose a novel momentum-based method to mitigate this decentralized training difficulty. We show in extensive empirical experiments on various CV/NLP datasets (CIFAR-10, ImageNet, and AG News) and several network topologies (Ring and Social Network) that our method is much more robust to the heterogeneity of clients' data than other existing methods, by a significant improvement in test performance ($1\% \!-\! 20\%$). Our code is publicly available.
$k$-Anonymity in Practice: How Generalisation and Suppression Affect Machine Learning Classifiers
Authors: Djordje Slijepčević, Maximilian Henzl, Lukas Daniel Klausner, Tobias Dam, Peter Kieseberg, Matthias Zeppelzauer
Date: 2021-02-09 00:00:00
Tasks: BIG-bench Machine Learning

The protection of private information is a crucial issue in data-driven research and business contexts. Typically, techniques like anonymisation or (selective) deletion are introduced in order to allow data sharing, e. g. in the case of collaborative research endeavours. For use with anonymisation techniques, the $k$-anonymity criterion is one of the most popular, with numerous scientific publications on different algorithms and metrics. Anonymisation techniques often require changing the data and thus necessarily affect the results of machine learning models trained on the underlying data. In this work, we conduct a systematic comparison and detailed investigation into the effects of different $k$-anonymisation algorithms on the results of machine learning models. We investigate a set of popular $k$-anonymisation algorithms with different classifiers and evaluate them on different real-world datasets. Our systematic evaluation shows that with an increasingly strong $k$-anonymity constraint, the classification performance generally degrades, but to varying degrees and strongly depending on the dataset and anonymisation method. Furthermore, Mondrian can be considered as the method with the most appealing properties for subsequent classification.
Fast discovery of multidimensional subsequences for robust trajectory classification
Authors: Tarlis Portela, Jonata Tyska, Vania Bogorny
Date: 2021-02-09 00:00:00
Tasks: Classification, General Classification

Trajectory classification tasks became more complex as large volumes of mobility data are being generated every day and enriched with new sources of information, such as social networks and IoT sensors. Fast classification algorithms are essential for discovering knowledge in trajectory data for real applications. In this work we propose a method for fast discovery of subtrajectories with the reduction of the search space and the optimization of the MASTERMovelets method, which has proven to be effective for discovering interpretable patterns in classification problems.
A Multi-Arm Bandit Approach To Subset Selection Under Constraints
Authors: Ayush Deva, Kumar Abhishek, Sujit Gujar
Date: 2021-02-09 00:00:00

We explore the class of problems where a central planner needs to select a subset of agents, each with different quality and cost. The planner wants to maximize its utility while ensuring that the average quality of the selected agents is above a certain threshold. When the agents' quality is known, we formulate our problem as an integer linear program (ILP) and propose a deterministic algorithm, namely \dpss\ that provides an exact solution to our ILP. We then consider the setting when the qualities of the agents are unknown. We model this as a Multi-Arm Bandit (MAB) problem and propose \newalgo\ to learn the qualities over multiple rounds. We show that after a certain number of rounds, $\tau$, \newalgo\ outputs a subset of agents that satisfy the average quality constraint with a high probability. Next, we provide bounds on $\tau$ and prove that after $\tau$ rounds, the algorithm incurs a regret of $O(\ln T)$, where $T$ is the total number of rounds. We further illustrate the efficacy of \newalgo\ through simulations. To overcome the computational limitations of \dpss, we propose a polynomial-time greedy algorithm, namely \greedy, that provides an approximate solution to our ILP. We also compare the performance of \dpss\ and \greedy\ through experiments.
Consensus Control for Decentralized Deep Learning
Authors: Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, Sebastian U. Stich
Date: 2021-02-09 00:00:00
Tasks: Deep Learning

Decentralized training of deep learning models enables on-device learning over networks, as well as efficient scaling to large compute clusters. Experiments in earlier works reveal that, even in a data-center setup, decentralized training often suffers from the degradation in the quality of the model: the training and test performance of models trained in a decentralized fashion is in general worse than that of models trained in a centralized fashion, and this performance drop is impacted by parameters such as network size, communication topology and data partitioning. We identify the changing consensus distance between devices as a key parameter to explain the gap between centralized and decentralized training. We show in theory that when the training consensus distance is lower than a critical quantity, decentralized training converges as fast as the centralized counterpart. We empirically validate that the relation between generalization performance and consensus distance is consistent with this theoretical observation. Our empirical insights allow the principled design of better decentralized training schemes that mitigate the performance drop. To this end, we provide practical training guidelines and exemplify its effectiveness on the data-center setup as the important first step.
Target Training Does Adversarial Training Without Adversarial Samples
Authors: Blerta Lindqvist
Date: 2021-02-09 00:00:00

Neural network classifiers are vulnerable to misclassification of adversarial samples, for which the current best defense trains classifiers with adversarial samples. However, adversarial samples are not optimal for steering attack convergence, based on the minimization at the core of adversarial attacks. The minimization perturbation term can be minimized towards $0$ by replacing adversarial samples in training with duplicated original samples, labeled differently only for training. Using only original samples, Target Training eliminates the need to generate adversarial samples for training against all attacks that minimize perturbation. In low-capacity classifiers and without using adversarial samples, Target Training exceeds both default CIFAR10 accuracy ($84.3$%) and current best defense accuracy (below $25$%) with $84.8$% against CW-L$_2$($\kappa=0$) attack, and $86.6$% against DeepFool. Using adversarial samples against attacks that do not minimize perturbation, Target Training exceeds current best defense ($69.1$%) with $76.4$% against CW-L$_2$($\kappa=40$) in CIFAR10.
Learning a powerful SVM using piece-wise linear loss functions
Authors: Pritam Anand
Date: 2021-02-09 00:00:00

In this paper, we have considered general k-piece-wise linear convex loss functions in SVM model for measuring the empirical risk. The resulting k-Piece-wise Linear loss Support Vector Machine (k-PL-SVM) model is an adaptive SVM model which can learn a suitable piece-wise linear loss function according to nature of the given training set. The k-PL-SVM models are general SVM models and existing popular SVM models, like C-SVM, LS-SVM and Pin-SVM models, are their particular cases. We have performed the extensive numerical experiments with k-PL-SVM models for k = 2 and 3 and shown that they are improvement over existing SVM models.
Measuring Progress in Deep Reinforcement Learning Sample Efficiency
Authors: Florian E. Dorner
Date: 2021-02-09 00:00:00
Tasks: Atari Games, continuous-control, Continuous Control, Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Sampled environment transitions are a critical input to deep reinforcement learning (DRL) algorithms. Current DRL benchmarks often allow for the cheap and easy generation of large amounts of samples such that perceived progress in DRL does not necessarily correspond to improved sample efficiency. As simulating real world processes is often prohibitively hard and collecting real world experience is costly, sample efficiency is an important indicator for economically relevant applications of DRL. We investigate progress in sample efficiency on Atari games and continuous control tasks by comparing the number of samples that a variety of algorithms need to reach a given performance level according to training curves in the corresponding publications. We find exponential progress in sample efficiency with estimated doubling times of around 10 to 18 months on Atari, 5 to 24 months on state-based continuous control and of around 4 to 9 months on pixel-based continuous control depending on the specific task and performance level.
On Theory-training Neural Networks to Infer the Solution of Highly Coupled Differential Equations
Authors: M. Torabi Rad, A. Viardin, M. Apel
Date: 2021-02-09 00:00:00

Deep neural networks are transforming fields ranging from computer vision to computational medicine, and we recently extended their application to the field of phase-change heat transfer by introducing theory-trained neural networks (TTNs) for a solidification problem \cite{TTN}. Here, we present general, in-depth, and empirical insights into theory-training networks for learning the solution of highly coupled differential equations. We analyze the deteriorating effects of the oscillating loss on the ability of a network to satisfy the equations at the training data points, measured by the final training loss, and on the accuracy of the inferred solution. We introduce a theory-training technique that, by leveraging regularization, eliminates those oscillations, decreases the final training loss, and improves the accuracy of the inferred solution, with no additional computational cost. Then, we present guidelines that allow a systematic search for the network that has the optimal training time and inference accuracy for a given set of equations; following these guidelines can reduce the number of tedious training iterations in that search. Finally, a comparison between theory-training and the rival, conventional method of solving differential equations using discretization attests to the advantages of theory-training not being necessarily limited to high-dimensional sets of equations. The comparison also reveals a limitation of the current theory-training framework that may limit its application in domains where extreme accuracies are necessary.