pwc-archive/papers-with-abstracts huggingface dataset:
Fast Adversarial Training with Adaptive Step Size
Authors: Zhichao Huang, Yanbo Fan, Chen Liu, Weizhong Zhang, Yong Zhang, Mathieu Salzmann, Sabine Süsstrunk, Jue Wang
Date: 2022-06-06 00:00:00

While adversarial training and its variants have shown to be the most effective algorithms to defend against adversarial attacks, their extremely slow training process makes it hard to scale to large datasets like ImageNet. The key idea of recent works to accelerate adversarial training is to substitute multi-step attacks (e.g., PGD) with single-step attacks (e.g., FGSM). However, these single-step methods suffer from catastrophic overfitting, where the accuracy against PGD attack suddenly drops to nearly 0% during training, destroying the robustness of the networks. In this work, we study the phenomenon from the perspective of training instances. We show that catastrophic overfitting is instance-dependent and fitting instances with larger gradient norm is more likely to cause catastrophic overfitting. Based on our findings, we propose a simple but effective method, Adversarial Training with Adaptive Step size (ATAS). ATAS learns an instancewise adaptive step size that is inversely proportional to its gradient norm. The theoretical analysis shows that ATAS converges faster than the commonly adopted non-adaptive counterparts. Empirically, ATAS consistently mitigates catastrophic overfitting and achieves higher robust accuracy on CIFAR10, CIFAR100 and ImageNet when evaluated on various adversarial budgets.
Interference Management for Over-the-Air Federated Learning in Multi-Cell Wireless Networks
Authors: Zhibin Wang, Yong Zhou, Yuanming Shi, Weihua Zhuang
Date: 2022-06-06 00:00:00
Tasks: Federated Learning, Management

Federated learning (FL) over resource-constrained wireless networks has recently attracted much attention. However, most existing studies consider one FL task in single-cell wireless networks and ignore the impact of downlink/uplink inter-cell interference on the learning performance. In this paper, we investigate FL over a multi-cell wireless network, where each cell performs a different FL task and over-the-air computation (AirComp) is adopted to enable fast uplink gradient aggregation. We conduct convergence analysis of AirComp-assisted FL systems, taking into account the inter-cell interference in both the downlink and uplink model/gradient transmissions, which reveals that the distorted model/gradient exchanges induce a gap to hinder the convergence of FL. We characterize the Pareto boundary of the error-induced gap region to quantify the learning performance trade-off among different FL tasks, based on which we formulate an optimization problem to minimize the sum of error-induced gaps in all cells. To tackle the coupling between the downlink and uplink transmissions as well as the coupling among multiple cells, we propose a cooperative multi-cell FL optimization framework to achieve efficient interference management for downlink and uplink transmission design. Results demonstrate that our proposed algorithm achieves much better average learning performance over multiple cells than non-cooperative baseline schemes.
Automated Circuit Sizing with Multi-objective Optimization based on Differential Evolution and Bayesian Inference
Authors: Catalin Visan, Octavian Pascu, Marius Stanescu, Elena-Diana Sandru, Cristian Diaconu, Andi Buzo, Georg Pelz, Horia Cucu
Date: 2022-06-06 00:00:00
Tasks: Bayesian Inference, Bayesian Optimization, Diversity, Evolutionary Algorithms, Gaussian Processes

With the ever increasing complexity of specifications, manual sizing for analog circuits recently became very challenging. Especially for innovative, large-scale circuits designs, with tens of design variables, operating conditions and conflicting objectives to be optimized, design engineers spend many weeks, running time-consuming simulations, in their attempt at finding the right configuration. Recent years brought machine learning and optimization techniques to the field of analog circuits design, with evolutionary algorithms and Bayesian models showing good results for circuit sizing. In this context, we introduce a design optimization method based on Generalized Differential Evolution 3 (GDE3) and Gaussian Processes (GPs). The proposed method is able to perform sizing for complex circuits with a large number of design variables and many conflicting objectives to be optimized. While state-of-the-art methods reduce multi-objective problems to single-objective optimization and potentially induce a prior bias, we search directly over the multi-objective space using Pareto dominance and ensure that diverse solutions are provided to the designers to choose from. To the best of our knowledge, the proposed method is the first to specifically address the diversity of the solutions, while also focusing on minimizing the number of simulations required to reach feasible configurations. We evaluate the introduced method on two voltage regulators showing different levels of complexity and we highlight that the proposed innovative candidate selection method and survival policy leads to obtaining feasible solutions, with a high degree of diversity, much faster than with GDE3 or Bayesian Optimization-based algorithms.
Restructuring Graph for Higher Homophily via Adaptive Spectral Clustering
Authors: Shouheng Li, Dongwoo Kim, Qing Wang
Date: 2022-06-06 00:00:00
Tasks: Clustering, Node Classification

While a growing body of literature has been studying new Graph Neural Networks (GNNs) that work on both homophilic and heterophilic graphs, little has been done on adapting classical GNNs to less-homophilic graphs. Although the ability to handle less-homophilic graphs is restricted, classical GNNs still stand out in several nice properties such as efficiency, simplicity, and explainability. In this work, we propose a novel graph restructuring method that can be integrated into any type of GNNs, including classical GNNs, to leverage the benefits of existing GNNs while alleviating their limitations. Our contribution is threefold: a) learning the weight of pseudo-eigenvectors for an adaptive spectral clustering that aligns well with known node labels, b) proposing a new density-aware homophilic metric that is robust to label imbalance, and c) reconstructing the adjacency matrix based on the result of adaptive spectral clustering to maximize the homophilic scores. The experimental results show that our graph restructuring method can significantly boost the performance of six classical GNNs by an average of 25% on less-homophilic graphs. The boosted performance is comparable to state-of-the-art methods.
Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions
Authors: Kaan Gokcesu, Hakan Gokcesu
Date: 2022-06-06 00:00:00
Tasks: global-optimization

In this work, we propose an efficient minimax optimal global optimization algorithm for multivariate Lipschitz continuous functions. To evaluate the performance of our approach, we utilize the average regret instead of the traditional simple regret, which, as we show, is not suitable for use in the multivariate non-convex optimization because of the inherent hardness of the problem itself. Since we study the average regret of the algorithm, our results directly imply a bound for the simple regret as well. Instead of constructing lower bounding proxy functions, our method utilizes a predetermined query creation rule, which makes it computationally superior to the Piyavskii-Shubert variants. We show that our algorithm achieves an average regret bound of $O(L\sqrt{n}T^{-\frac{1}{n}})$ for the optimization of an $n$-dimensional $L$-Lipschitz continuous objective in a time horizon $T$, which we show to be minimax optimal.
Markovian Interference in Experiments
Authors: Vivek F. Farias, Andrew A. Li, Tianyi Peng, Andrew Zheng
Date: 2022-06-06 00:00:00
Tasks: Off-policy evaluation, Reinforcement Learning (RL)

We consider experiments in dynamical systems where interventions on some experimental units impact other units through a limiting constraint (such as a limited inventory). Despite outsize practical importance, the best estimators for this `Markovian' interference problem are largely heuristic in nature, and their bias is not well understood. We formalize the problem of inference in such experiments as one of policy evaluation. Off-policy estimators, while unbiased, apparently incur a large penalty in variance relative to state-of-the-art heuristics. We introduce an on-policy estimator: the Differences-In-Q's (DQ) estimator. We show that the DQ estimator can in general have exponentially smaller variance than off-policy evaluation. At the same time, its bias is second order in the impact of the intervention. This yields a striking bias-variance tradeoff so that the DQ estimator effectively dominates state-of-the-art alternatives. From a theoretical perspective, we introduce three separate novel techniques that are of independent interest in the theory of Reinforcement Learning (RL). Our empirical evaluation includes a set of experiments on a city-scale ride-hailing simulator.
Bi-SimCut: A Simple Strategy for Boosting Neural Machine Translation
Authors: Pengzhi Gao, Zhongjun He, Hua Wu, Haifeng Wang
Date: 2022-06-06 00:00:00
Proceeding: NAACL 2022 7
Tasks: de-en, Machine Translation, NMT, Sentence, Translation

We introduce Bi-SimCut: a simple but effective training strategy to boost neural machine translation (NMT) performance. It consists of two procedures: bidirectional pretraining and unidirectional finetuning. Both procedures utilize SimCut, a simple regularization method that forces the consistency between the output distributions of the original and the cutoff sentence pairs. Without leveraging extra dataset via back-translation or integrating large-scale pretrained model, Bi-SimCut achieves strong translation performance across five translation benchmarks (data sizes range from 160K to 20.2M): BLEU scores of 31.16 for en -> de and 38.37 for de -> en on the IWSLT14 dataset, 30.78 for en -> de and 35.15 for de -> en on the WMT14 dataset, and 27.17 for zh -> en on the WMT17 dataset. SimCut is not a new method, but a version of Cutoff (Shen et al., 2020) simplified and adapted for NMT, and it could be considered as a perturbation-based method. Given the universality and simplicity of SimCut and Bi-SimCut, we believe they can serve as strong baselines for future NMT research.
Finite-Sample Maximum Likelihood Estimation of Location
Authors: Shivam Gupta, Jasper C. H. Lee, Eric Price, Paul Valiant
Date: 2022-06-06 00:00:00

We consider 1-dimensional location estimation, where we estimate a parameter $\lambda$ from $n$ samples $\lambda + \eta_i$, with each $\eta_i$ drawn i.i.d. from a known distribution $f$. For fixed $f$ the maximum-likelihood estimate (MLE) is well-known to be optimal in the limit as $n \to \infty$: it is asymptotically normal with variance matching the Cram\'er-Rao lower bound of $\frac{1}{n\mathcal{I}}$, where $\mathcal{I}$ is the Fisher information of $f$. However, this bound does not hold for finite $n$, or when $f$ varies with $n$. We show for arbitrary $f$ and $n$ that one can recover a similar theory based on the Fisher information of a smoothed version of $f$, where the smoothing radius decays with $n$.
Hashing Learning with Hyper-Class Representation
Authors: Shichao Zhang, Jiaye Li
Date: 2022-06-06 00:00:00
Tasks: Attribute

Existing unsupervised hash learning is a kind of attribute-centered calculation. It may not accurately preserve the similarity between data. This leads to low down the performance of hash function learning. In this paper, a hash algorithm is proposed with a hyper-class representation. It is a two-steps approach. The first step finds potential decision features and establish hyper-class. The second step constructs hash learning based on the hyper-class information in the first step, so that the hash codes of the data within the hyper-class are as similar as possible, as well as the hash codes of the data between the hyper-classes are as different as possible. To evaluate the efficiency, a series of experiments are conducted on four public datasets. The experimental results show that the proposed hash algorithm is more efficient than the compared algorithms, in terms of mean average precision (MAP), average precision (AP) and Hamming radius 2 (HAM2)
Asymptotic Instance-Optimal Algorithms for Interactive Decision Making
Authors: Kefan Dong, Tengyu Ma
Date: 2022-06-06 00:00:00
Tasks: Decision Making, Multi-Armed Bandits, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Past research on interactive decision making problems (bandits, reinforcement learning, etc.) mostly focuses on the minimax regret that measures the algorithm's performance on the hardest instance. However, an ideal algorithm should adapt to the complexity of a particular problem instance and incur smaller regrets on easy instances than worst-case instances. In this paper, we design the first asymptotic instance-optimal algorithm for general interactive decision making problems with finite number of decisions under mild conditions. On every instance $f$, our algorithm outperforms all consistent algorithms (those achieving non-trivial regrets on all instances), and has asymptotic regret $\mathcal{C}(f) \ln n$, where $\mathcal{C}(f)$ is an exact characterization of the complexity of $f$. The key step of the algorithm involves hypothesis testing with active data collection. It computes the most economical decisions with which the algorithm collects observations to test whether an estimated instance is indeed correct; thus, the complexity $\mathcal{C}(f)$ is the minimum cost to test the instance $f$ against other instances. Our results, instantiated on concrete problems, recover the classical gap-dependent bounds for multi-armed bandits [Lai and Robbins, 1985] and prior works on linear bandits [Lattimore and Szepesvari, 2017], and improve upon the previous best instance-dependent upper bound [Xu et al., 2021] for reinforcement learning.
Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling
Authors: Alexander Tyurin, Lukang Sun, Konstantin Burlachenko, Peter Richtárik
Date: 2022-06-05 00:00:00
Tasks: Federated Learning

We revisit the classical problem of finding an approximately stationary point of the average of $n$ smooth and possibly nonconvex functions. The optimal complexity of stochastic first-order methods in terms of the number of gradient evaluations of individual functions is $\mathcal{O}\left(n + n^{1/2}\varepsilon^{-1}\right)$, attained by the optimal SGD methods $\small\sf\color{green}{SPIDER}$(arXiv:1807.01695) and $\small\sf\color{green}{PAGE}$(arXiv:2008.10898), for example, where $\varepsilon$ is the error tolerance. However, i) the big-$\mathcal{O}$ notation hides crucial dependencies on the smoothness constants associated with the functions, and ii) the rates and theory in these methods assume simplistic sampling mechanisms that do not offer any flexibility. In this work we remedy the situation. First, we generalize the $\small\sf\color{green}{PAGE}$ algorithm so that it can provably work with virtually any (unbiased) sampling mechanism. This is particularly useful in federated learning, as it allows us to construct and better understand the impact of various combinations of client and data sampling strategies. Second, our analysis is sharper as we make explicit use of certain novel inequalities that capture the intricate interplay between the smoothness constants and the sampling procedure. Indeed, our analysis is better even for the simple sampling procedure analyzed in the $\small\sf\color{green}{PAGE}$ paper. However, this already improved bound can be further sharpened by a different sampling scheme which we propose. In summary, we provide the most general and most accurate analysis of optimal SGD in the smooth nonconvex regime. Finally, our theoretical findings are supposed with carefully designed experiments.
Information Threshold, Bayesian Inference and Decision-Making
Authors: Jacques Balayla
Date: 2022-06-05 00:00:00
Tasks: Bayesian Inference, Binary Classification, Classification, Decision Making, Persuasiveness

We define the information threshold as the point of maximum curvature in the prior vs. posterior Bayesian curve, both of which are described as a function of the true positive and negative rates of the classification system in question. The nature of the threshold is such that for sufficiently adequate binary classification systems, retrieving excess information beyond the threshold does not significantly alter the reliability of our classification assessment. We hereby introduce the "marital status thought experiment" to illustrate this idea and report a previously undefined mathematical relationship between the Bayesian prior and posterior, which may have significant philosophical and epistemological implications in decision theory. Where the prior probability is a scalar between 0 and 1 given by $\phi$ and the posterior is a scalar between 0 and 1 given by $\rho$, then at the information threshold, $\phi_e$: $\phi_e + \rho_e = 1$ Otherwise stated, given some degree of prior belief, we may assert its persuasiveness when sufficient quality evidence yields a posterior so that their combined sum equals 1. Retrieving further evidence beyond this point does not significantly improve the posterior probability, and may serve as a benchmark for confidence in decision-making.
Diffusion-GAN: Training GANs with Diffusion
Authors: Zhendong Wang, Huangjie Zheng, Pengcheng He, Weizhu Chen, Mingyuan Zhou
Date: 2022-06-05 00:00:00
Tasks: Image Generation

Generative adversarial networks (GANs) are challenging to train stably, and a promising remedy of injecting instance noise into the discriminator input has not been very effective in practice. In this paper, we propose Diffusion-GAN, a novel GAN framework that leverages a forward diffusion chain to generate Gaussian-mixture distributed instance noise. Diffusion-GAN consists of three components, including an adaptive diffusion process, a diffusion timestep-dependent discriminator, and a generator. Both the observed and generated data are diffused by the same adaptive diffusion process. At each diffusion timestep, there is a different noise-to-data ratio and the timestep-dependent discriminator learns to distinguish the diffused real data from the diffused generated data. The generator learns from the discriminator's feedback by backpropagating through the forward diffusion chain, whose length is adaptively adjusted to balance the noise and data levels. We theoretically show that the discriminator's timestep-dependent strategy gives consistent and helpful guidance to the generator, enabling it to match the true data distribution. We demonstrate the advantages of Diffusion-GAN over strong GAN baselines on various datasets, showing that it can produce more realistic images with higher stability and data efficiency than state-of-the-art GANs.
Enforcing Group Fairness in Algorithmic Decision Making: Utility Maximization Under Sufficiency
Authors: Joachim Baumann, Anikó Hannák, Christoph Heitz
Date: 2022-06-05 00:00:00
Tasks: Decision Making, Fairness

Binary decision making classifiers are not fair by default. Fairness requirements are an additional element to the decision making rationale, which is typically driven by maximizing some utility function. In that sense, algorithmic fairness can be formulated as a constrained optimization problem. This paper contributes to the discussion on how to implement fairness, focusing on the fairness concepts of positive predictive value (PPV) parity, false omission rate (FOR) parity, and sufficiency (which combines the former two). We show that group-specific threshold rules are optimal for PPV parity and FOR parity, similar to well-known results for other group fairness criteria. However, depending on the underlying population distributions and the utility function, we find that sometimes an upper-bound threshold rule for one group is optimal: utility maximization under PPV parity (or FOR parity) might thus lead to selecting the individuals with the smallest utility for one group, instead of selecting the most promising individuals. This result is counter-intuitive and in contrast to the analogous solutions for statistical parity and equality of opportunity. We also provide a solution for the optimal decision rules satisfying the fairness constraint sufficiency. We show that more complex decision rules are required and that this leads to within-group unfairness for all but one of the groups. We illustrate our findings based on simulated and real data.
Statistical Deep Learning for Spatial and Spatio-Temporal Data
Authors: Christopher K. Wikle, Andrew Zammit-Mangion
Date: 2022-06-05 00:00:00
Tasks: Deep Learning, Gaussian Processes

Deep neural network models have become ubiquitous in recent years, and have been applied to nearly all areas of science, engineering, and industry. These models are particularly useful for data that have strong dependencies in space (e.g., images) and time (e.g., sequences). Indeed, deep models have also been extensively used by the statistical community to model spatial and spatio-temporal data through, for example, the use of multi-level Bayesian hierarchical models and deep Gaussian processes. In this review, we first present an overview of traditional statistical and machine learning perspectives for modeling spatial and spatio-temporal data, and then focus on a variety of hybrid models that have recently been developed for latent process, data, and parameter specifications. These hybrid models integrate statistical modeling ideas with deep neural network models in order to take advantage of the strengths of each modeling paradigm. We conclude by giving an overview of computational technologies that have proven useful for these hybrid models, and with a brief discussion on future research directions.
Performance Comparison of Simple Transformer and Res-CNN-BiLSTM for Cyberbullying Classification
Authors: Raunak Joshi, Abhishek Gupta
Date: 2022-06-05 00:00:00
Tasks: text-classification, Text Classification

The task of text classification using Bidirectional based LSTM architectures is computationally expensive and time consuming to train. For this, transformers were discovered which effectively give good performance as compared to the traditional deep learning architectures. In this paper we present a performance based comparison between simple transformer based network and Res-CNN-BiLSTM based network for cyberbullying text classification problem. The results obtained show that transformer we trained with 0.65 million parameters has significantly being able to beat the performance of Res-CNN-BiLSTM with 48.82 million parameters for faster training speeds and more generalized metrics. The paper also compares the 1-dimensional character level embedding network and 100-dimensional glove embedding network with transformer.