ACML 2022 Papers

An invertible function is bi-Lipschitz if both the function and its inverse have bounded Lipschitz constants. Most state-of-the-art Normalizing Flows are bi-Lipschitz by design or by training to limit numerical errors (among other things). In this paper, we discuss the expressivity of bi-Lipschitz Normalizing Flows and identify several target distributions that are difficult to approximate using such models. Then, we characterize the expressivity of bi-Lipschitz Normalizing Flows by giving several lower bounds on the Total Variation distance between these particularly unfavorable distributions and their best possible approximation. Finally, we show how to use the bounds to adjust the training parameters, and discuss potential remedies.

Attention mechanisms form a core component of several successful deep learning architectures, and are based on one key idea: “The output depends only on a small (but unknown) segment of the input.” In several practical applications like image captioning and language translation, this is mostly true. In trained models with an attention mechanism, the outputs of an intermediate module that encodes the segment of input responsible for the output is often used as a way to peek into the ‘reasoning’ of the network. We make such a notion more precise for a variant of the classification problem that we term selective dependence classification (SDC) when used with attention model architectures. Under such a setting, we demonstrate various error modes where an attention model can be accurate but fail to be interpretable, and show that such models do occur as a result of training. We illustrate various situations that can accentuate and mitigate this behaviour. Finally, we use our objective definition of interpretability for SDC tasks to evaluate a few attention model learning algorithms designed to encourage sparsity and demonstrate that these algorithms help improve interpretability.

Dog vs. hot dog and dog vs. wolf, which one tends to be a harder comparison task? While simple, this question can be meaningful for few-shot classification. Few-shot learning enables trained models to recognize unseen classes through just a few labelled samples. As such, trained few-shot models usually have to possess the ability to assess the similarity degree between the unlabelled and labelled samples. In each few-shot learning episode, a combination of the labelled support set and unlabelled query set are sampled from the training dataset for model-training. In the episodic settings of few-shot learning, most algorithms draw the data samples uniformly at random for training. However, this approach disregards concepts of difficulty of each training episode, which may make a difference. After all, it is usually easier to differentiate between a dog and a hot dog, versus the dog and a wolf. Therefore, in this paper, we delve into the concept of episodic difficulty, or difficulty of each training episode, discovering several insights and proposing strategies to utilize the difficulty. Firstly, defining episodic difficulty as a training loss, we find and study the correlation between episodic difficulty and visual similarity among data samples in each episode. Secondly, we assess the respective usefulness of easy and difficult episodes for the training process. Lastly, based on the assessment, we design a curriculum for few-shot learning to support training with incremental difficulty. We observe that such an approach can achieve faster convergence for few-shot algorithms, reducing the average training time by around 50%. It can also make meta-learning algorithms achieve an increase in final testing accuracy scores.

Adaptive gradient methods including Adam, AdaGrad, and their variants have been very successful for training deep learning models, such as neural networks. Meanwhile, given the need for distributed computing, distributed optimization algorithms are rapidly becoming a focal point. With the growth of computing power and the need for using machine learning models on mobile devices, the communication cost of distributed training algorithms needs careful consideration. In this paper, we introduce novel convergent decentralized adaptive gradient methods and rigorously incorporate adaptive gradient methods into decentralized training procedures. Specifically, we propose a general algorithmic framework that can convert existing adaptive gradient methods to their decentralized counterparts. In addition, we thoroughly analyze the convergence behavior of the proposed algorithmic framework and show that if a given adaptive gradient method converges, under some specific conditions, then its decentralized counterpart is also convergent. We illustrate the benefit of our generic decentralized framework on prototype methods, AMSGrad and AdaGrad.

In this paper, we study the problem of PAC learning halfspaces in the non-interactive local differential privacy model (NLDP). To breach the barrier of exponential sample complexity, previous results studied a relaxed setting where the server has access to some additional public but unlabeled data. We continue in this direction. Specifically, we consider the problem under the standard setting instead of the large margin setting studied before. Under different mild assumptions on the underlying data distribution, we propose two approaches that are based on the Massart noise model and self-supervised learning and show that it is possible to achieve sample complexities that are only linear in the dimension and polynomial in other terms for both private and public data, which significantly improve the previous results. Our methods could also be used for other private PAC learning problems.

We provide a robust convergence analysis of the Riemannian gradient descent algorithm for computing the leading eigenvector of a real symmetric matrix. Our result characterizes the convergence behavior of the algorithm under the noisy updates, where noises can be generated by a stochastic process or could be chosen adversarially. The noisy Riemannian gradient descent has a broad range of applications in machine learning and statistics, e.g., streaming principal component analysis or privacy-preserving spectral analysis. In particular, we demonstrate the usefulness of our convergence bound with a new eigengap-dependent sample complexity of the inexact Riemannian stochastic recursive gradient algorithm, which utilizes mini-batch gradients instead of full gradients in outer loops. Our robust convergence paradigm strictly improves the state-of-the-art sample complexity in terms of the gap dependence.

In this work, we consider the coalition formation games with an additional component, ‘noisy preferences’. Moreover, such noisy preferences are available only for a sample of coalitions. We propose a multiplicative noise model (equivalent to an additive noise model) and obtain the prediction probability, defined as the probability that the estimated PAC core-stable partition of the \emph{noisy} game is also PAC core-stable for the \emph{unknown noise-free} game. This prediction probability depends on the probability of a combinatorial construct called an ‘agreement event’. We explicitly obtain the agreement probability for $n$ agent noisy game with $l\geq 2$ support noise distribution. For a user-given satisfaction value on this probability, we identify the noise regimes for which an estimated partition is noise robust; that is, it is PAC core-stable in both the noisy and noise-free games. We obtain similar robustness results when the estimated partition is not PAC core-stable. These noise regimes correspond to the level sets of the agreement probability function and are non-convex sets. Moreover, an important fact is that the prediction probability can be high even if high noise values occur with a high probability. Further, for a class of top-responsive hedonic games, we obtain the bounds on the extra noisy samples required to get noise robustness with a user-given satisfaction value. We completely solve the noise robustness problem of a $2$ agent hedonic game. In particular, we obtain the prediction probability function for $l=2$ and $l=3$ noise support cases. For $l=2$, the prediction probability is convex in noise probability, but the noise robust regime is non-convex. Its minimum value, called the safety value, is 0.62; so, below 0.62, the noise robust regime is the entire probability simplex. However, for $l \geq 3$, the prediction probability is non-convex; so, the safety value is the global minima of a non-convex function and is computationally hard.

In recent years, semantic segmentation has shown very good performance in daytime scenes. But in nighttime scenes, semantic segmentation greatly reduces its accuracy. Due to the lack of large-scale nighttime semantic segmentation datasets, it is difficult to directly train segmentation models for nighttime scenes. Therefore, it becomes important to adapt the daytime scene segmentation model to the nighttime scene without directly using the nighttime scene segmentation dataset. In this paper, we propose a framework based on unsupervised learning and cross attention. The proposed method fuses supervised daytime scenes and unsupervised nighttime scenes, the supervision information in the daytime scene and the texture information specific to the nighttime scene are fully utilized, and the model is adapted to both the daytime scene and the nighttime scene. Consistency regulation is used to make segmentation model adapt to the complex and changeable night scene texture and illumination. In view of the coarse correspondence of static objects between day and night image pairs in the Dark Zurich dataset, cross attention is proposed to make the model pay more attention to the parts of the night scene which are similar to the daytime scene. Extensive experiments on Dark Zurich and Nighttime Driving datasets show that our method obtains better performance in nighttime semantic segmentation.

Missing data are ubiquitous in real world applications and, if not adequately handled, may lead to the loss of information and biased findings in downstream analysis. Particularly, high-dimensional incomplete data with a moderate sample size, such as analysis of multi-omics data, present daunting challenges. Imputation is arguably the most popular method for handling missing data, though existing imputation methods have a number of limitations. Single imputation methods such as matrix completion methods do not adequately account for imputation uncertainty and hence would yield improper statistical inference. In contrast, multiple imputation (MI) methods allow for proper inference but existing methods do not perform well in high-dimensional settings. Our work aims to address these significant methodological gaps, leveraging recent advances in neural network Gaussian process (NNGP) from a Bayesian viewpoint. We propose two NNGP-based MI methods, namely MI-NNGP, that can apply multiple imputations for missing values from a joint (posterior predictive) distribution. The MI-NNGP methods are shown to significantly outperform existing state-of-the-art methods on synthetic and real datasets, in terms of imputation error, statistical inference, robustness to missing rates, and computation costs, under three missing data mechanisms, MCAR, MAR, and MNAR.

Physiological signal classification is of great significance for health monitoring and medical diagnosis. Deep learning-based methods (e.g. RNN and CNN) have been used in this domain to obtain reliable predictions. However, the performance of existing methods is constrained by the long-term dependence and irregular vibration of the univariate physiological signal sequence. To overcome these limitations, this paper proposes a Multi-scale Progressive Gated Transformer (MPGT) model to learn multi-scale temporal representations for better physiological signal classification. The key novelties of MPGT are the proposed Multi-scale Temporal Feature extraction (MTF) and Progressive Gated Transformer (PGT). The former adopts coarse- and fine-grained feature extractors to project the input signal data into different temporal granularity embedding spaces and the latter integrates such multi-scale information for data representation. Classification task is then conducted on the learned representations. Experimental results on real-world datasets demonstrate the superiority of the proposed model.

Recent years have witnessed a great success of supervised deep learning, where predictive models were trained from a large amount of fully labeled data. However, in practice, labeling such big data can be very costly and may not even be possible for privacy reasons. Therefore, in this paper, we aim to learn an accurate classifier without any class labels. More specifically, we consider the case where multiple sets of unlabeled data and only their class priors, i.e., the proportions of each class, are available. Under this problem setup, we first derive an unbiased estimator of the classification risk that can be estimated from the given unlabeled sets and theoretically analyze the generalization error of the learned classifier. We then find that the classifier obtained as such tends to cause overfitting as its empirical risks go negative during training. To prevent overfitting, we further propose a partial risk regularization that maintains the partial risks with respect to unlabeled datasets and classes to certain levels. Experiments demonstrate that our method effectively mitigates overfitting and outperforms state-of-the-art methods for learning from multiple unlabeled sets.

Anomaly detection on time series is an important research topic in data mining, which has a wide range of applications in financial markets, biological data, information technology, manufacturing system, etc. However, the existing time series anomaly detection methods mainly capture temporal features from a single-scale viewpoint, which cannot detect multi-scale anomalies effectively. In this paper, we propose a novel approach of Multi-scale Anomaly Detection for Time Series (MAD-TS) with an attention-based recurrent autoencoder model to solve the above problem. The proposed method adopts a hierarchically connected recurrent encoder to extract the features of a time series from different levels. The multi-scale features are then fused by a hierarchical decoder with attention mechanism to reconstruct the original sequence at different scales. Based on the reconstruction errors at multiple scales, anomaly scores can be learned for different data points, which can be used to infer the anomaly status of the time series. Extensive experiments based on five open time series datasets show that the proposed MAD-TS method achieves significant performance improvement on anomaly detection compared to the state-of-the-arts.

Missing and corrupted labels can significantly ruin the learning process and, consequently, the classifier performance. Multi-label learning where each instance is tagged with variable number of labels is particularly affected. Although missing labels (false-negatives) is a well-studied problem in multi-label learning, it is considerably more challenging to have both false-negatives (missing labels) and false-positives (corrupted labels) simultaneously in multi-label datasets. In this paper, we propose Multi-Label Loss with Self Correction (MLLSC) which is a loss robust against coincident missing and corrupted labels. MLLSC computes the loss based on the true-positive (true-negative) or false-positive (false-negative) labels and deep neural network expertise. To distinguish between false-positive (false-negative) and true-positive (true-negative) labels, we use the output probability of the deep neural network during the learning process. Our method As MLLSC can be combined with different types of multi-label loss functions, we also address the label imbalance problem of multi-label datasets. Empirical evaluation on real-world vision datasets, i.e., MS-COCO, and MIR-FLICKR, shows that our method under medium (0.3) and high (0.6) corrupted and missing label probabilities outperform the state-of-the-art methods by, on average 23.97% and 9.31% mean average precision (mAP) points, respectively.

Long-tailed visual recognition tasks pose great challenges for neural networks on how to handle the imbalanced predictions between head (common) and tail (rare) classes, i.e., models tend to classify tail classes as head classes. While existing research focused on data resampling and loss function engineering, in this paper, we take a different perspective: the classification margins. We study the relationship between the margins and logits and empirically observe that the uncalibrated margins and logits are positively correlated. We propose a simple yet effective MARgin Calibration approach (MARC) to calibrate the margins to obtain better logits. We validate MARC through extensive experiments on common long-tailed benchmarks including CIFAR-LT, ImageNet-LT, Places-LT, and iNaturalist-LT. Experimental results demonstrate that our MARC achieves favorable results on these benchmarks. In addition, MARC is extremely easy to implement with just three lines of code. We hope this simple approach will motivate people to rethink the uncalibrated margins and logits in long-tailed visual recognition.

Reinforcement learning (RL) algorithms can be used to provide personalized services, which rely on users’ private and sensitive data. To protect the users’ privacy, privacy-preserving RL algorithms are in demand. In this paper, we study RL with linear function approximation and local differential privacy (LDP) guarantees. We propose a novel $(\varepsilon, \delta)$-LDP algorithm for learning a class of Markov decision processes (MDPs) dubbed linear mixture MDPs, and obtains an $\tilde{\mathcal{O}}( d^{5/4}H^{7/4}T^{3/4}\left(\log(1/\delta)\right)^{1/4}\sqrt{1/\varepsilon})$ regret, where $d$ is the dimension of feature mapping, $H$ is the length of the planning horizon, and $T$ is the number of interactions with the environment. We also prove a lower bound $\Omega(dH\sqrt{T}/\left(e^{\varepsilon}(e^{\varepsilon}-1)\right))$ for learning linear mixture MDPs under $\varepsilon$-LDP constraint. Experiments on synthetic datasets verify the effectiveness of our algorithm. To the best of our knowledge, this is the first provable privacy-preserving RL algorithm with linear function approximation.

Classical supervised learning generally trains one model from an i.i.d. data according to an unknown yet fixed distribution. In some real applications such as finance, however, multiple models may be trained by different companies and interacted in a dynamic environment, where the data distribution may take shift according to different models’ decisions. In this work, we study two models for simplicity, and formalize such scenario as a learning problem of two models over decision-dependent distributions. We develop the Repeated Risk Minimization (RRM) for two models, and present a sufficient condition to the existence of stable points for RRM, that is, an equilibrium notion. We further provide the theoretical analysis for the convergence of RRM to stable points based on data distribution and finite training sample, respectively. We also study more practical algorithms, such as gradient descent and stochastic gradient descent, to solve the RRM problem with convergence guarantees and we finally present some empirical studies to validate our theoretical analysis.

The inherent structure of the Convolutional Neural Networks (CNN) allows them to extract features that are highly correlated with the classes while performing image classification. However, it may happen that the extracted features are merely coincidental and may not be justifiable from a human perspective. For example, from a set of images of cows on grassland, CNN can erroneously extract grass as the feature of the class cow. There are two main limitations to this kind of learning: firstly, in many false-negative cases, correct features will not be used, and secondly, in false-positive cases the system will lack accountability. There is no implicit way to inform CNN to learn the features that are justifiable from a human perspective to resolve these issues. In this paper, we argue that if we provide domain knowledge to guide the learning process of CNN, it is possible to reliably learn the justifiable features. We propose a systematic yet simple mechanism to incorporate domain knowledge to guide the learning process of the CNNs to extract justifiable features. The flip side is that it needs additional input. However, we have shown that even with minimal additional input our method can effectively propagate the knowledge within a class during training. We demonstrate that justifiable features not only enhance accuracy but also demand less amount of data and training time. Moreover, we also show that the proposed method is more robust against perturbational changes in the input images.

In Multi-Agent Reinforcement Learning, communication is critical to encourage cooperation among agents. Communication in realistic wireless networks can be highly unreliable due to network conditions varying with agents’ mobility, and stochasticity in the transmission process. We propose a framework to learn practical communication strategies by addressing three fundamental questions: (1) \emph{When}: Agents learn the timing of communication based on not only message importance but also wireless channel conditions. (2) \emph{What}: Agents augment message contents with wireless network measurements to better select the game and communication actions. (3) \emph{How}: Agents use a novel neural message encoder to preserve all information from received messages, regardless of the number and order of messages. Simulating standard benchmarks under realistic wireless network settings, we show significant improvements in game performance, convergence speed and communication efficiency compared with state-of-the-art.

Efficiency is a critical issue in UAV tracking because of the limitations of computing resources, battery capacity, and maximum load of unmanned aerial vehicle (UAV). However, deep learning (DL)-based trackers hardly achieve real-time tracking on a single CPU despite their high tracking precision. To the contrary, discriminative correlation filters (DCF)-based trackers have high efficiency but their precision is barely satisfactory. Despite the precision is inferior, DCF-based trackers instead of DL-based ones are widely applied in UAV tracking to trade precision for efficiency. This paper aims to improve the efficiency of the DL-based tracker SiamFC++, in particular, for UAV tracking using the model compression technique, i.e., rank-based filter pruning, which has not been well explored before. Meanwhile, to combat the potential loss of precision caused by pruning we exploit disentangled representation learning to disentangle the output feature of the backbone into two parts: the identity-related features and the identity-unrelated features. Only the identity-related features are used for subsequent classification and regression tasks to improve the effectiveness of the feature representation. With the proposed disentangled representation in pruning, we achieved higher precisions when compressing the original model SiamFC++ with a global pruning ratio of 0.5. Extensive experiments on four public UAV benchmarks, i.e., UAV123@10fps, UAVDT, DTB70, and Vistrone2018, show that the proposed tracker DP-SiamFC++ strikes a remarkable balance between efficiency and precision, and achieves state-of-the-art performance in UAV tracking.