pwc-archive/papers-with-abstracts huggingface dataset:
Amortized Implicit Differentiation for Stochastic Bilevel Optimization
Authors: Michael Arbel, Julien Mairal
Date: 2021-11-29 00:00:00
Proceeding: ICLR 2022 4
Tasks: Bilevel Optimization

We study a class of algorithms for solving bilevel optimization problems in both stochastic and deterministic settings when the inner-level objective is strongly convex. Specifically, we consider algorithms based on inexact implicit differentiation and we exploit a warm-start strategy to amortize the estimation of the exact gradient. We then introduce a unified theoretical framework inspired by the study of singularly perturbed systems (Habets, 1974) to analyze such amortized algorithms. By using this framework, our analysis shows these algorithms to match the computational complexity of oracle methods that have access to an unbiased estimate of the gradient, thus outperforming many existing results for bilevel optimization. We illustrate these findings on synthetic experiments and demonstrate the efficiency of these algorithms on hyper-parameter optimization experiments involving several thousands of variables.
On the rate of convergence of a classifier based on a Transformer encoder
Authors: Iryna Gurevych, Michael Kohler, Gözde Gül Sahin
Date: 2021-11-29 00:00:00

Pattern recognition based on a high-dimensional predictor is considered. A classifier is defined which is based on a Transformer encoder. The rate of convergence of the misclassification probability of the classifier towards the optimal misclassification probability is analyzed. It is shown that this classifier is able to circumvent the curse of dimensionality provided the aposteriori probability satisfies a suitable hierarchical composition model. Furthermore, the difference between Transformer classifiers analyzed theoretically in this paper and Transformer classifiers used nowadays in practice are illustrated by considering classification problems in natural language processing.
A new Sinkhorn algorithm with Deletion and Insertion operations
Authors: Luc Brun, Benoit Gaüzère, Sébastien Bougleux, Florian Yger
Date: 2021-11-29 00:00:00

This technical report is devoted to the continuous estimation of an epsilon-assignment. Roughly speaking, an epsilon assignment between two sets V1 and V2 may be understood as a bijective mapping between a sub part of V1 and a sub part of V2 . The remaining elements of V1 (not included in this mapping) are mapped onto an epsilon pseudo element of V2 . We say that such elements are deleted. Conversely, the remaining elements of V2 correspond to the image of the epsilon pseudo element of V1. We say that these elements are inserted. As a result our method provides a result similar to the one of the Sinkhorn algorithm with the additional ability to reject some elements which are either inserted or deleted. It thus naturally handles sets V1 and V2 of different sizes and decides mappings/insertions/deletions in a unified way. Our algorithms are iterative and differentiable and may thus be easily inserted within a backpropagation based learning framework such as artificial neural networks.
BP-Net: Efficient Deep Learning for Continuous Arterial Blood Pressure Estimation using Photoplethysmogram
Authors: Rishi Vardhan K, Vedanth S, Poojah G, Abhishek K, Nitish Kumar M, Vineeth Vijayaraghavan
Date: 2021-11-29 00:00:00
Tasks: Blood pressure estimation, Feature Engineering, Raspberry Pi 4

Blood pressure (BP) is one of the most influential bio-markers for cardiovascular diseases and stroke; therefore, it needs to be regularly monitored to diagnose and prevent any advent of medical complications. Current cuffless approaches to continuous BP monitoring, though non-invasive and unobtrusive, involve explicit feature engineering surrounding fingertip Photoplethysmogram (PPG) signals. To circumvent this, we present an end-to-end deep learning solution, BP-Net, that uses PPG waveform to estimate Systolic BP (SBP), Mean Average Pressure (MAP), and Diastolic BP (DBP) through intermediate continuous Arterial BP (ABP) waveform. Under the terms of the British Hypertension Society (BHS) standard, BP-Net achieves Grade A for DBP and MAP estimation and Grade B for SBP estimation. BP-Net also satisfies Advancement of Medical Instrumentation (AAMI) criteria for DBP and MAP estimation and achieves Mean Absolute Error (MAE) of 5.16 mmHg and 2.89 mmHg for SBP and DBP, respectively. Further, we establish the ubiquitous potential of our approach by deploying BP-Net on a Raspberry Pi 4 device and achieve 4.25 ms inference time for our model to translate the PPG waveform to ABP waveform.
Robust On-Policy Sampling for Data-Efficient Policy Evaluation in Reinforcement Learning
Authors: Rujie Zhong, Duohan Zhang, Lukas Schäfer, Stefano V. Albrecht, Josiah P. Hanna
Date: 2021-11-29 00:00:00
Tasks: Offline RL, reinforcement-learning, Reinforcement Learning (RL)

Reinforcement learning (RL) algorithms are often categorized as either on-policy or off-policy depending on whether they use data from a target policy of interest or from a different behavior policy. In this paper, we study a subtle distinction between on-policy data and on-policy sampling in the context of the RL sub-problem of policy evaluation. We observe that on-policy sampling may fail to match the expected distribution of on-policy data after observing only a finite number of trajectories and this failure hinders data-efficient policy evaluation. Towards improved data-efficiency, we show how non-i.i.d., off-policy sampling can produce data that more closely matches the expected on-policy data distribution and consequently increases the accuracy of the Monte Carlo estimator for policy evaluation. We introduce a method called Robust On-Policy Sampling and demonstrate theoretically and empirically that it produces data that converges faster to the expected on-policy distribution compared to on-policy sampling. Empirically, we show that this faster convergence leads to lower mean squared error policy value estimates.
Spherical Matrix Factorization
Authors: Kai Liu
Date: 2021-11-29 00:00:00
Tasks: Dictionary Learning

Matrix Factorization plays an important role in machine learning such as Non-negative Matrix Factorization, Principal Component Analysis, Dictionary Learning, etc. However, most of the studies aim to minimize the loss by measuring the Euclidean distance, though in some fields, angle distance is known to be more important and critical for analysis. In this paper, we propose a method by adding constraints on factors to unify the Euclidean and angle distance. However, due to non-convexity of the objective and constraints, the optimized solution is not easy to obtain. In this paper we propose a general framework to systematically solve it with provable convergence guarantee with various constraints.
Understanding over-squashing and bottlenecks on graphs via curvature
Authors: Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein
Date: 2021-11-29 00:00:00
Proceeding: ICLR 2022 4
Tasks: Node Classification

Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of $k$-hop neighbors grows rapidly with $k$. We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing.
Conceptually Diverse Base Model Selection for Meta-Learners in Concept Drifting Data Streams
Authors: Helen McKay, Nathan Griffiths, Phillip Taylor
Date: 2021-11-29 00:00:00
Tasks: Clustering, Ensemble Pruning, Model Selection, Transfer Learning

Meta-learners and ensembles aim to combine a set of relevant yet diverse base models to improve predictive performance. However, determining an appropriate set of base models is challenging, especially in online environments where the underlying distribution of data can change over time. In this paper, we present a novel approach for estimating the conceptual similarity of base models, which is calculated using the Principal Angles (PAs) between their underlying subspaces. We propose two methods that use conceptual similarity as a metric to obtain a relevant yet diverse subset of base models: (i) parameterised threshold culling and (ii) parameterless conceptual clustering. We evaluate these methods against thresholding using common ensemble pruning metrics, namely predictive performance and Mutual Information (MI), in the context of online Transfer Learning (TL), using both synthetic and real-world data. Our results show that conceptual similarity thresholding has a reduced computational overhead, and yet yields comparable predictive performance to thresholding using predictive performance and MI. Furthermore, conceptual clustering achieves similar predictive performances without requiring parameterisation, and achieves this with lower computational overhead than thresholding using predictive performance and MI when the number of base models becomes large.
Naive Automated Machine Learning
Authors: Felix Mohr, Marcel Wever
Date: 2021-11-29 00:00:00
Tasks: AutoML, Bayesian Optimization, BIG-bench Machine Learning

An essential task of Automated Machine Learning (AutoML) is the problem of automatically finding the pipeline with the best generalization performance on a given dataset. This problem has been addressed with sophisticated black-box optimization techniques such as Bayesian Optimization, Grammar-Based Genetic Algorithms, and tree search algorithms. Most of the current approaches are motivated by the assumption that optimizing the components of a pipeline in isolation may yield sub-optimal results. We present Naive AutoML, an approach that does precisely this: It optimizes the different algorithms of a pre-defined pipeline scheme in isolation. The finally returned pipeline is obtained by just taking the best algorithm of each slot. The isolated optimization leads to substantially reduced search spaces, and, surprisingly, this approach yields comparable and sometimes even better performance than current state-of-the-art optimizers.
Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension
Authors: Yuling Jiao, Dingwei Li, Min Liu, Xiangliang Lu, Yuanyuan Yang
Date: 2021-11-29 00:00:00
Tasks: Decoder

In this paper, we consider recovering $n$ dimensional signals from $m$ binary measurements corrupted by noises and sign flips under the assumption that the target signals have low generative intrinsic dimension, i.e., the target signals can be approximately generated via an $L$-Lipschitz generator $G: \mathbb{R}^k\rightarrow\mathbb{R}^{n}, k\ll n$. Although the binary measurements model is highly nonlinear, we propose a least square decoder and prove that, up to a constant $c$, with high probability, the least square decoder achieves a sharp estimation error $\mathcal{O} (\sqrt{\frac{k\log (Ln)}{m}})$ as long as $m\geq \mathcal{O}( k\log (Ln))$. Extensive numerical simulations and comparisons with state-of-the-art methods demonstrated the least square decoder is robust to noise and sign flips, as indicated by our theory. By constructing a ReLU network with properly chosen depth and width, we verify the (approximately) deep generative prior, which is of independent interest.
TsFeX: Contact Tracing Model using Time Series Feature Extraction and Gradient Boosting
Authors: Valerio Antonini, Yingjie Niu, Manuela Nayantara Jeyaraj, Sonal Santosh Baberwal, Faithful Chiagoziem Onwuegbuche, Robert Foskin
Date: 2021-11-29 00:00:00
Tasks: Time Series, Time Series Analysis

With the outbreak of COVID-19 pandemic, a dire need to effectively identify the individuals who may have come in close-contact to others who have been infected with COVID-19 has risen. This process of identifying individuals, also termed as 'Contact tracing', has significant implications for the containment and control of the spread of this virus. However, manual tracing has proven to be ineffective calling for automated contact tracing approaches. As such, this research presents an automated machine learning system for identifying individuals who may have come in contact with others infected with COVID-19 using sensor data transmitted through handheld devices. This paper describes the different approaches followed in arriving at an optimal solution model that effectually predicts whether a person has been in close proximity to an infected individual using a gradient boosting algorithm and time series feature extraction.
Robust Federated Learning for execution time-based device model identification under label-flipping attack
Authors: Pedro Miguel Sánchez Sánchez, Alberto Huertas Celdrán, José Rafael Buendía Rubio, Gérôme Bovet, Gregorio Martínez Pérez
Date: 2021-11-29 00:00:00
Tasks: Federated Learning

The computing device deployment explosion experienced in recent years, motivated by the advances of technologies such as Internet-of-Things (IoT) and 5G, has led to a global scenario with increasing cybersecurity risks and threats. Among them, device spoofing and impersonation cyberattacks stand out due to their impact and, usually, low complexity required to be launched. To solve this issue, several solutions have emerged to identify device models and types based on the combination of behavioral fingerprinting and Machine/Deep Learning (ML/DL) techniques. However, these solutions are not appropriated for scenarios where data privacy and protection is a must, as they require data centralization for processing. In this context, newer approaches such as Federated Learning (FL) have not been fully explored yet, especially when malicious clients are present in the scenario setup. The present work analyzes and compares the device model identification performance of a centralized DL model with an FL one while using execution time-based events. For experimental purposes, a dataset containing execution-time features of 55 Raspberry Pis belonging to four different models has been collected and published. Using this dataset, the proposed solution achieved 0.9999 accuracy in both setups, centralized and federated, showing no performance decrease while preserving data privacy. Later, the impact of a label-flipping attack during the federated model training is evaluated, using several aggregation mechanisms as countermeasure. Zeno and coordinate-wise median aggregation show the best performance, although their performance greatly degrades when the percentage of fully malicious clients (all training samples poisoned) grows over 50%.
Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Model
Authors: Lies Hadjadj, Massih-Reza Amini, Sana Louhichi, Alexis Deschamps
Date: 2021-11-29 00:00:00

We investigate the generalization properties of a self-training algorithm with halfspaces. The approach learns a list of halfspaces iteratively from labeled and unlabeled training data, in which each iteration consists of two steps: exploration and pruning. In the exploration phase, the halfspace is found sequentially by maximizing the unsigned-margin among unlabeled examples and then assigning pseudo-labels to those that have a distance higher than the current threshold. The pseudo-labeled examples are then added to the training set, and a new classifier is learned. This process is repeated until no more unlabeled examples remain for pseudo-labeling. In the pruning phase, pseudo-labeled samples that have a distance to the last halfspace greater than the associated unsigned-margin are then discarded. We prove that the misclassification error of the resulting sequence of classifiers is bounded and show that the resulting semi-supervised approach never degrades performance compared to the classifier learned using only the initial labeled training set. Experiments carried out on a variety of benchmarks demonstrate the efficiency of the proposed approach compared to state-of-the-art methods.
Being Patient and Persistent: Optimizing An Early Stopping Strategy for Deep Learning in Profiled Attacks
Authors: Servio Paguada, Lejla Batina, Ileana Buhan, Igor Armendariz
Date: 2021-11-29 00:00:00
Tasks: Deep Learning

The absence of an algorithm that effectively monitors deep learning models used in side-channel attacks increases the difficulty of evaluation. If the attack is unsuccessful, the question is if we are dealing with a resistant implementation or a faulty model. We propose an early stopping algorithm that reliably recognizes the model's optimal state during training. The novelty of our solution is an efficient implementation of guessing entropy estimation. Additionally, we formalize two conditions, persistence and patience, for a deep learning model to be optimal. As a result, the model converges with fewer traces.
Online Fair Revenue Maximizing Cake Division with Non-Contiguous Pieces in Adversarial Bandits
Authors: Mohammad Ghodsi, Amirmahdi Mirfakhar
Date: 2021-11-29 00:00:00
Tasks: Fairness, Multi-Armed Bandits

The classic cake-cutting problem provides a model for addressing the fair and efficient allocation of a divisible, heterogeneous resource among agents with distinct preferences. Focusing on a standard formulation of cake cutting, in which each agent must receive a contiguous piece of the cake in an offline setting, this work instead focuses on online allocating non-contiguous pieces of cake among agents and establishes algorithmic results for fairness measures. In this regard, we made use of classic adversarial multi-armed bandits to achieve sub-linear Fairness and Revenue Regret at the same time. Adversarial bandits are powerful tools to model the adversarial reinforcement learning environments, that provide strong upper-bounds for regret of learning with just observing one action's reward in each step by applying smart trade-off between exploration and exploitation. This work studies the power of the famous EXP_3 algorithm that is based on exponential wight{-}importance updating probability distribution through time horizon.
Responding to Challenge Call of Machine Learning Model Development in Diagnosing Respiratory Disease Sounds
Authors: Negin Melek
Date: 2021-11-29 00:00:00
Tasks: BIG-bench Machine Learning, Classification, Environmental Sound Classification, Sound Classification

In this study, a machine learning model was developed for automatically detecting respiratory system sounds such as sneezing and coughing in disease diagnosis. The automatic model and approach development of breath sounds, which carry valuable information, results in early diagnosis and treatment. A successful machine learning model was developed in this study, which was a strong response to the challenge called the "Pfizer digital medicine challenge" on the "OSFHOME" open access platform. "Environmental sound classification" called ESC-50 and AudioSet sound files were used to prepare the dataset. In this dataset, which consisted of three parts, features that effectively showed coughing and sneezing sound analysis were extracted from training, testing and validating samples. Based on the Mel frequency cepstral coefficients (MFCC) feature extraction method, mathematical and statistical features were prepared. Three different classification techniques were considered to perform successful respiratory sound classification in the dataset containing more than 3800 different sounds. Support vector machine (SVM) with radial basis function (RBF) kernels, ensemble aggregation and decision tree classification methods were used as classification techniques. In an attempt to classify coughing and sneezing sounds from other sounds, SVM with RBF kernels was achieved with 83% success.
Physics-informed Evolutionary Strategy based Control for Mitigating Delayed Voltage Recovery
Authors: Yan Du, Qiuhua Huang, Renke Huang, Tianzhixi Yin, Jie Tan, Wenhao Yu, Xinya Li
Date: 2021-11-29 00:00:00

In this work we propose a novel data-driven, real-time power system voltage control method based on the physics-informed guided meta evolutionary strategy (ES). The main objective is to quickly provide an adaptive control strategy to mitigate the fault-induced delayed voltage recovery (FIDVR) problem. Reinforcement learning methods have been developed for the same or similar challenging control problems, but they suffer from training inefficiency and lack of robustness for "corner or unseen" scenarios. On the other hand, extensive physical knowledge has been developed in power systems but little has been leveraged in learning-based approaches. To address these challenges, we introduce the trainable action mask technique for flexibly embedding physical knowledge into RL models to rule out unnecessary or unfavorable actions, and achieve notable improvements in sample efficiency, control performance and robustness. Furthermore, our method leverages past learning experience to derive surrogate gradient to guide and accelerate the exploration process in training. Case studies on the IEEE 300-bus system and comparisons with other state-of-the-art benchmark methods demonstrate effectiveness and advantages of our method.
A Causal Approach for Unfair Edge Prioritization and Discrimination Removal
Authors: Pavan Ravishankar, Pranshu Malviya, Balaraman Ravindran
Date: 2021-11-29 00:00:00

In budget-constrained settings aimed at mitigating unfairness, like law enforcement, it is essential to prioritize the sources of unfairness before taking measures to mitigate them in the real world. Unlike previous works, which only serve as a caution against possible discrimination and de-bias data after data generation, this work provides a toolkit to mitigate unfairness during data generation, given by the Unfair Edge Prioritization algorithm, in addition to de-biasing data after generation, given by the Discrimination Removal algorithm. We assume that a non-parametric Markovian causal model representative of the data generation procedure is given. The edges emanating from the sensitive nodes in the causal graph, such as race, are assumed to be the sources of unfairness. We first quantify Edge Flow in any edge X -> Y, which is the belief of observing a specific value of Y due to the influence of a specific value of X along X -> Y. We then quantify Edge Unfairness by formulating a non-parametric model in terms of edge flows. We then prove that cumulative unfairness towards sensitive groups in a decision, like race in a bail decision, is non-existent when edge unfairness is absent. We prove this result for the non-trivial non-parametric model setting when the cumulative unfairness cannot be expressed in terms of edge unfairness. We then measure the Potential to mitigate the Cumulative Unfairness when edge unfairness is decreased. Based on these measurements, we propose the Unfair Edge Prioritization algorithm that can then be used by policymakers. We also propose the Discrimination Removal Procedure that de-biases a data distribution by eliminating optimization constraints that grow exponentially in the number of sensitive attributes and values taken by them. Extensive experiments validate the theorem and specifications used for quantifying the above measures.