OpenRaiser/Intern-Atlas huggingface dataset:
Can Stochastic Gradient Langevin Dynamics Provide Differential Privacy for Deep Learning?
Venue: arXiv cs.LG 2023
Year: 2023

Bayesian learning via Stochastic Gradient Langevin Dynamics (SGLD) has been suggested for differentially private learning. While previous research provides differential privacy bounds for SGLD at the initial steps of the algorithm or when close to convergence, the question of what differential privacy guarantees can be made in between remains unanswered. This interim region is of great importance, especially for Bayesian neural networks, as it is hard to guarantee convergence to the posterior. This paper shows that using SGLD might result in unbounded privacy loss for this interim region, even when sampling from the posterior is as differentially private as desired.
Convex-Concave Min-Max Stackelberg Games
Venue: arXiv cs.GT 2023
Year: 2023

Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent strategy sets; little is known about solving games with dependent strategy sets, which can be characterized as min-max Stackelberg games. We introduce two first-order methods that solve a large class of convex-concave min-max Stackelberg games, and show that our methods converge in polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald's maximin model, a variant of which is the main paradigm used in robust optimization, which means that our methods can likewise solve many convex robust optimization problems. We observe that the computation of competitive equilibria in Fisher markets also comprises a min-max Stackelberg game. Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.
Chaos as an interpretable benchmark for forecasting and data-driven modelling
Venue: arXiv cs.LG 2023
Year: 2023

The striking fractal geometry of strange attractors underscores the generative nature of chaos: like probability distributions, chaotic systems can be repeatedly measured to produce arbitrarily-detailed information about the underlying attractor. Chaotic systems thus pose a unique challenge to modern statistical learning techniques, while retaining quantifiable mathematical properties that make them controllable and interpretable as benchmarks. Here, we present a growing database currently comprising 131 known chaotic dynamical systems spanning fields such as astrophysics, climatology, and biochemistry. Each system is paired with precomputed multivariate and univariate time series. Our dataset has comparable scale to existing static time series databases; however, our systems can be re-integrated to produce additional datasets of arbitrary length and granularity. Our dataset is annotated with known mathematical properties of each system, and we perform feature analysis to broadly categorize the diverse dynamics present across the collection. Chaotic systems inherently challenge forecasting models, and across extensive benchmarks we correlate forecasting performance with the degree of chaos present. We also exploit the unique generative properties of our dataset in several proof-of-concept experiments: surrogate transfer learning to improve time series classification, importance sampling to accelerate model training, and benchmarking symbolic regression algorithms.
Subnetwork Constraints for Tighter Upper Bounds and Exact Solution of the Clique Partitioning Problem
Venue: arXiv cs.SI 2023
Year: 2023

We consider a variant of the clustering problem for a complete weighted graph. The aim is to partition the nodes into clusters maximizing the sum of the edge weights within the clusters. This problem is known as the clique partitioning problem, being NP-hard in the general case of having edge weights of different signs. We propose a new method of estimating an upper bound of the objective function that we combine with the classical branch-and-bound technique to find the exact solution. We evaluate our approach on a broad range of random graphs and real-world networks. The proposed approach provided tighter upper bounds and achieved significant convergence speed improvements compared to known alternative methods.
Popular matchings with weighted voters
Venue: arXiv cs.DS 2023
Year: 2023

In the Popular Matching problem, we are given a bipartite graph $G = (A \cup B, E)$ and for each vertex $v\in A\cup B$, strict preferences over the neighbors of $v$. Given two matchings $M$ and $M'$, matching $M$ is more popular than $M'$ if the number of vertices preferring $M$ to $M'$ is larger than the number of vertices preferring $M'$ to $M$. A matching $M$ is called popular if there is no matching $M'$ that is more popular than $M$. We consider a natural generalization of Popular Matching where every vertex has a weight. Then, we call a matching $M$ more popular than matching $M'$ if the weight of vertices preferring $M$ to $M'$ is larger than the weight of vertices preferring $M'$ to $M$. For this case, we show that it is NP-hard to find a popular matching. Our main result its a polynomial-time algorithm that delivers a popular matching or a proof for it non-existence in instances where all vertices on one side have weight $c > 3$ and all vertices on the other side have weight 1.
A Taxonomy and Archetypes of Business Analytics in Smart Manufacturing
Venue: arXiv cs.CY 2023
Year: 2023

Fueled by increasing data availability and the rise of technological advances for data processing and communication, business analytics is a key driver for smart manufacturing. However, due to the multitude of different local advances as well as its multidisciplinary complexity, both researchers and practitioners struggle to keep track of the progress and acquire new knowledge within the field, as there is a lack of a holistic conceptualization. To address this issue, we performed an extensive structured literature review, yielding 904 relevant hits, to develop a quadripartite taxonomy as well as to derive archetypes of business analytics in smart manufacturing. The taxonomy comprises the following meta-characteristics: application domain, orientation as the objective of the analysis, data origins, and analysis techniques. Collectively, they comprise eight dimensions with a total of 52 distinct characteristics. Using a cluster analysis, we found six archetypes that represent a synthesis of existing knowledge on planning, maintenance (reactive, offline, and online predictive), monitoring, and quality management. A temporal analysis highlights the push beyond predictive approaches and confirms that deep learning already dominates novel applications. Our results constitute an entry point to the field but can also serve as a reference work and a guide with which to assess the adequacy of one's own instruments.
StARformer: Transformer with State-Action-Reward Representations for Visual Reinforcement Learning
Venue: arXiv cs.LG 2023
Year: 2023

Reinforcement Learning (RL) can be considered as a sequence modeling task: given a sequence of past state-action-reward experiences, an agent predicts a sequence of next actions. In this work, we propose State-Action-Reward Transformer (StARformer) for visual RL, which explicitly models short-term state-action-reward representations (StAR-representations), essentially introducing a Markovian-like inductive bias to improve long-term modeling. Our approach first extracts StAR-representations by self-attending image state patches, action, and reward tokens within a short temporal window. These are then combined with pure image state representations -- extracted as convolutional features, to perform self-attention over the whole sequence. Our experiments show that StARformer outperforms the state-of-the-art Transformer-based method on image-based Atari and DeepMind Control Suite benchmarks, in both offline-RL and imitation learning settings. StARformer is also more compliant with longer sequences of inputs. Our code is available at https://github.com/elicassion/StARformer.
Efficiency in the Serverless Cloud Paradigm: A Survey on the Reusing and Approximation Aspects
Venue: arXiv cs.DC 2023
Year: 2023

Serverless computing along with Function-as-a-Service (FaaS) is forming a new computing paradigm that is anticipated to found the next generation of cloud systems. The popularity of this paradigm is due to offering a highly transparent infrastructure that enables user applications to scale in the granularity of their functions. Since these often small and single-purpose functions are managed on shared computing resources behind the scene, a great potential for computational reuse and approximate computing emerges that if unleashed, can remarkably improve the efficiency of serverless cloud systems -- both from the user's QoS and system's (energy consumption and incurred cost) perspectives. Accordingly, the goal of this survey study is to, first, unfold the internal mechanics of serverless computing and, second, explore the scope for efficiency within this paradigm via studying function reuse and approximation approaches and discussing the pros and cons of each one. Next, we outline potential future research directions within this paradigm that can either unlock new use cases or make the paradigm more efficient.
When saliency goes off on a tangent: Interpreting Deep Neural Networks with nonlinear saliency maps
Venue: arXiv cs.LG 2023
Year: 2023

A fundamental bottleneck in utilising complex machine learning systems for critical applications has been not knowing why they do and what they do, thus preventing the development of any crucial safety protocols. To date, no method exist that can provide full insight into the granularity of the neural network's decision process. In the past, saliency maps were an early attempt at resolving this problem through sensitivity calculations, whereby dimensions of a data point are selected based on how sensitive the output of the system is to them. However, the success of saliency maps has been at best limited, mainly due to the fact that they interpret the underlying learning system through a linear approximation. We present a novel class of methods for generating nonlinear saliency maps which fully account for the nonlinearity of the underlying learning system. While agreeing with linear saliency maps on simple problems where linear saliency maps are correct, they clearly identify more specific drivers of classification on complex examples where nonlinearities are more pronounced. This new class of methods significantly aids interpretability of deep neural networks and related machine learning systems. Crucially, they provide a starting point for their more broad use in serious applications, where 'why' is equally important as 'what'.
Newer is not always better: Rethinking transferability metrics, their peculiarities, stability and performance
Venue: arXiv cs.LG 2023
Year: 2023

Fine-tuning of large pre-trained image and language models on small customized datasets has become increasingly popular for improved prediction and efficient use of limited resources. Fine-tuning requires identification of best models to transfer-learn from and quantifying transferability prevents expensive re-training on all of the candidate models/tasks pairs. In this paper, we show that the statistical problems with covariance estimation drive the poor performance of H-score -- a common baseline for newer metrics -- and propose shrinkage-based estimator. This results in up to 80% absolute gain in H-score correlation performance, making it competitive with the state-of-the-art LogME measure. Our shrinkage-based H-score is $3\times$-10$\times$ faster to compute compared to LogME. Additionally, we look into a less common setting of target (as opposed to source) task selection. We demonstrate previously overlooked problems in such settings with different number of labels, class-imbalance ratios etc. for some recent metrics e.g., NCE, LEEP that resulted in them being misrepresented as leading measures. We propose a correction and recommend measuring correlation performance against relative accuracy in such settings. We support our findings with ~164,000 (fine-tuning trials) experiments on both vision models and graph neural networks.
Deconfounded Causal Collaborative Filtering
Venue: arXiv cs.IR 2023
Year: 2023

Recommender systems may be confounded by various types of confounding factors (also called confounders) that may lead to inaccurate recommendations and sacrificed recommendation performance. Current approaches to solving the problem usually design each specific model for each specific confounder. However, real-world systems may include a huge number of confounders and thus designing each specific model for each specific confounder could be unrealistic. More importantly, except for those ``explicit confounders'' that experts can manually identify and process such as item's position in the ranking list, there are also many ``latent confounders'' that are beyond the imagination of experts. For example, users' rating on a song may depend on their current mood or the current weather, and users' preference on ice creams may depend on the air temperature. Such latent confounders may be unobservable in the recorded training data. To solve the problem, we propose Deconfounded Causal Collaborative Filtering (DCCF). We first frame user behaviors with unobserved confounders into a causal graph, and then we design a front-door adjustment model carefully fused with machine learning to deconfound the influence of unobserved confounders. Experiments on real-world datasets show that our method is able to deconfound unobserved confounders to achieve better recommendation performance.
RocketQAv2: A Joint Training Method for Dense Passage Retrieval and Passage Re-ranking
Venue: arXiv cs.CL 2023
Year: 2023

In various natural language processing tasks, passage retrieval and passage re-ranking are two key procedures in finding and ranking relevant information. Since both the two procedures contribute to the final performance, it is important to jointly optimize them in order to achieve mutual improvement. In this paper, we propose a novel joint training approach for dense passage retrieval and passage re-ranking. A major contribution is that we introduce the dynamic listwise distillation, where we design a unified listwise training approach for both the retriever and the re-ranker. During the dynamic distillation, the retriever and the re-ranker can be adaptively improved according to each other's relevance information. We also propose a hybrid data augmentation strategy to construct diverse training instances for listwise training approach. Extensive experiments show the effectiveness of our approach on both MSMARCO and Natural Questions datasets. Our code is available at https://github.com/PaddlePaddle/RocketQA.
Composable Sparse Fine-Tuning for Cross-Lingual Transfer
Venue: arXiv cs.CL 2023
Year: 2023

Fine-tuning the entire set of parameters of a large pretrained model has become the mainstream approach for transfer learning. To increase its efficiency and prevent catastrophic forgetting and interference, techniques like adapters and sparse fine-tuning have been developed. Adapters are modular, as they can be combined to adapt a model towards different facets of knowledge (e.g., dedicated language and/or task adapters). Sparse fine-tuning is expressive, as it controls the behavior of all model components. In this work, we introduce a new fine-tuning method with both these desirable properties. In particular, we learn sparse, real-valued masks based on a simple variant of the Lottery Ticket Hypothesis. Task-specific masks are obtained from annotated data in a source language, and language-specific masks from masked language modeling in a target language. Both these masks can then be composed with the pretrained model. Unlike adapter-based fine-tuning, this method neither increases the number of parameters at inference time nor alters the original model architecture. Most importantly, it outperforms adapters in zero-shot cross-lingual transfer by a large margin in a series of multilingual benchmarks, including Universal Dependencies, MasakhaNER, and AmericasNLI. Based on an in-depth analysis, we additionally find that sparsity is crucial to prevent both 1) interference between the fine-tunings to be composed and 2) overfitting. We release the code and models at https://github.com/cambridgeltl/composable-sft.
Understanding and Improving Robustness of Vision Transformers through Patch-based Negative Augmentation
Venue: arXiv cs.LG 2023
Year: 2023

We investigate the robustness of vision transformers (ViTs) through the lens of their special patch-based architectural structure, i.e., they process an image as a sequence of image patches. We find that ViTs are surprisingly insensitive to patch-based transformations, even when the transformation largely destroys the original semantics and makes the image unrecognizable by humans. This indicates that ViTs heavily use features that survived such transformations but are generally not indicative of the semantic class to humans. Further investigations show that these features are useful but non-robust, as ViTs trained on them can achieve high in-distribution accuracy, but break down under distribution shifts. From this understanding, we ask: can training the model to rely less on these features improve ViT robustness and out-of-distribution performance? We use the images transformed with our patch-based operations as negatively augmented views and offer losses to regularize the training away from using non-robust features. This is a complementary view to existing research that mostly focuses on augmenting inputs with semantic-preserving transformations to enforce models' invariance. We show that patch-based negative augmentation consistently improves robustness of ViTs across a wide set of ImageNet based robustness benchmarks. Furthermore, we find our patch-based negative augmentation are complementary to traditional (positive) data augmentation, and together boost the performance further.
Label-Wise Graph Convolutional Network for Heterophilic Graphs
Venue: arXiv cs.LG 2023
Year: 2023

Graph Neural Networks (GNNs) have achieved remarkable performance in modeling graphs for various applications. However, most existing GNNs assume the graphs exhibit strong homophily in node labels, i.e., nodes with similar labels are connected in the graphs. They fail to generalize to heterophilic graphs where linked nodes may have dissimilar labels and attributes. Therefore, in this paper, we investigate a novel framework that performs well on graphs with either homophily or heterophily. More specifically, we propose a label-wise message passing mechanism to avoid the negative effects caused by aggregating dissimilar node representations and preserve the heterophilic contexts for representation learning. We further propose a bi-level optimization method to automatically select the model for graphs with homophily/heterophily. Theoretical analysis and extensive experiments demonstrate the effectiveness of our proposed framework for node classification on both homophilic and heterophilic graphs.
Information Operations in Turkey: Manufacturing Resilience with Free Twitter Accounts
Venue: arXiv cs.SI 2023
Year: 2023

Following the 2016 US elections Twitter launched their Information Operations (IO) hub where they archive account activity connected to state linked information operations. In June 2020, Twitter took down and released a set of accounts linked to Turkey's ruling political party (AKP). We investigate these accounts in the aftermath of the takedown to explore whether AKP-linked operations are ongoing and to understand the strategies they use to remain resilient to disruption. We collect live accounts that appear to be part of the same network, ~30% of which have been suspended by Twitter since our collection. We create a BERT-based classifier that shows similarity between these two networks, develop a taxonomy to categorize these accounts, find direct sequel accounts between the Turkish takedown and the live accounts, and find evidence that Turkish IO actors deliberately construct their network to withstand large-scale shutdown by utilizing explicit and implicit signals of coordination. We compare our findings from the Turkish operation to Russian and Chinese IO on Twitter and find that Turkey's IO utilizes a unique group structure to remain resilient. Our work highlights the fundamental imbalance between IO actors quickly and easily creating free accounts and the social media platforms spending significant resources on detection and removal, and contributes novel findings about Turkish IO on Twitter.
Machine Learning Featurizations for AI Hacking of Political Systems
Venue: arXiv cs.CY 2023
Year: 2023

What would the inputs be to a machine whose output is the destabilization of a robust democracy, or whose emanations could disrupt the political power of nations? In the recent essay "The Coming AI Hackers," Schneier (2021) proposed a future application of artificial intelligences to discover, manipulate, and exploit vulnerabilities of social, economic, and political systems at speeds far greater than humans' ability to recognize and respond to such threats. This work advances the concept by applying to it theory from machine learning, hypothesizing some possible "featurization" (input specification and transformation) frameworks for AI hacking. Focusing on the political domain, we develop graph and sequence data representations that would enable the application of a range of deep learning models to predict attributes and outcomes of political, particularly legislative, systems. We explore possible data models, datasets, predictive tasks, and actionable applications associated with each framework. We speculate about the likely practical impact and feasibility of such models, and conclude by discussing their ethical implications.
Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
Venue: arXiv cs.CC 2023
Year: 2023

In the general AntiFactor problem, a graph $G$ is given with a set $X_v\subseteq \mathbb{N}$ of forbidden degrees for every vertex $v$ and the task is to find a set $S$ of edges such that the degree of $v$ in $S$ is not in the set $X_v$. Standard techniques (dynamic programming + fast convolution) can be used to show that if $M$ is the largest forbidden degree, then the problem can be solved in time $(M+2)^k\cdot n^{O(1)}$ if a tree decomposition of width $k$ is given. However, significantly faster algorithms are possible if the sets $X_v$ are sparse: our main algorithmic result shows that if every vertex has at most $x$ forbidden degrees (we call this special case AntiFactor$_x$), then the problem can be solved in time $(x+1)^{O(k)}\cdot n^{O(1)}$. That is, the AntiFactor$_x$ is fixed-parameter tractable parameterized by treewidth $k$ and the maximum number $x$ of excluded degrees. Our algorithm uses the technique of representative sets, which can be generalized to the optimization version, but (as expected) not to the counting version of the problem. In fact, we show that #AntiFactor$_1$ is already #W[1]-hard parameterized by the width of the given decomposition. Moreover, we show that, unlike for the decision version, the standard dynamic programming algorithm is essentially optimal for the counting version. Formally, for a fixed nonempty set $X$, we denote by $X$-AntiFactor the special case where every vertex $v$ has the same set $X_v=X$ of forbidden degrees. We show the following lower bound for every fixed set $X$: if there is an $ε>0$ such that #$X$-AntiFactor can be solved in time $(\max X+2-ε)^k\cdot n^{O(1)}$ on a tree decomposition of width $k$, then the Counting Strong Exponential-Time Hypothesis (#SETH) fails.