OpenRaiser/Intern-Atlas huggingface dataset:
Pump and Dumps in the Bitcoin Era: Real Time Detection of Cryptocurrency Market Manipulations
Venue: arXiv cs.CY 2024
Year: 2024

In the last years, cryptocurrencies are increasingly popular. Even people who are not experts have started to invest in these securities and nowadays cryptocurrency exchanges process transactions for over 100 billion US dollars per month. However, many cryptocurrencies have low liquidity and therefore they are highly prone to market manipulation schemes. In this paper, we perform an in-depth analysis of pump and dump schemes organized by communities over the Internet. We observe how these communities are organized and how they carry out the fraud. Then, we report on two case studies related to pump and dump groups. Lastly, we introduce an approach to detect the fraud in real time that outperforms the current state of the art, so to help investors stay out of the market when a pump and dump scheme is in action.
Neural Bipartite Matching
Venue: arXiv cs.LG 2024
Year: 2024

Graph neural networks (GNNs) have found application for learning in the space of algorithms. However, the algorithms chosen by existing research (sorting, Breadth-First search, shortest path finding, etc.) usually align perfectly with a standard GNN architecture. This report describes how neural execution is applied to a complex algorithm, such as finding maximum bipartite matching by reducing it to a flow problem and using Ford-Fulkerson to find the maximum flow. This is achieved via neural execution based only on features generated from a single GNN. The evaluation shows strongly generalising results with the network achieving optimal matching almost 100% of the time.
When does MAML Work the Best? An Empirical Study on Model-Agnostic Meta-Learning in NLP Applications
Venue: arXiv cs.CL 2024
Year: 2024

Model-Agnostic Meta-Learning (MAML), a model-agnostic meta-learning method, is successfully employed in NLP applications including few-shot text classification and multi-domain low-resource language generation. Many impacting factors, including data quantity, similarity among tasks, and the balance between general language model and task-specific adaptation, can affect the performance of MAML in NLP, but few works have thoroughly studied them. In this paper, we conduct an empirical study to investigate these impacting factors and conclude when MAML works the best based on the experimental results.
Two variable logic with ultimately periodic counting
Venue: arXiv cs.LO 2024
Year: 2024

We consider the extension of two variable logic with quantifiers that state that the number of elements where a formula holds should belong to a given ultimately periodic set. We show that both satisfiability and finite satisfiability of the logic are decidable. We also show that the spectrum of any sentence is definable in Presburger arithmetic. In the process we present several refinements to the ``biregular graph method''. In this method, decidability issues concerning two-variable logics are reduced to questions about Presburger definability of integer vectors associated with partitioned graphs, where nodes in a partition satisfy certain constraints on their in- and out-degrees.
Tangles: a structural approach to artificial intelligence in the empirical sciences (Part I)
Venue: arXiv cs.AI 2024
Year: 2024

Traditional clustering identifies groups of objects that share certain qualities. Tangles do the converse: they identify groups of qualities that often occur together. They can thereby discover, relate, and structure types: of behaviour, political views, texts, or viruses. If desired, tangles can also be used as a new method for traditional clustering. They offer a precise, quantitative paradigm suited particularly to fuzzy clusters, since they do not require any assignment of objects to the clusters which these collectively form. This is the first of four parts of a book with the above title. The book explores applications outside mathematics of the notion and theory of tangles generalised from the graph tangles know from graph minor theory.
Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
Venue: arXiv cs.LG 2024
Year: 2024

Temporal-difference and Q-learning play a key role in deep reinforcement learning, where they are empowered by expressive nonlinear function approximators such as neural networks. At the core of their empirical successes is the learned feature representation, which embeds rich observations, e.g., images and texts, into the latent space that encodes semantic structures. Meanwhile, the evolution of such a feature representation is crucial to the convergence of temporal-difference and Q-learning. In particular, temporal-difference learning converges when the function approximator is linear in a feature representation, which is fixed throughout learning, and possibly diverges otherwise. We aim to answer the following questions: When the function approximator is a neural network, how does the associated feature representation evolve? If it converges, does it converge to the optimal one? We prove that, utilizing an overparameterized two-layer neural network, temporal-difference and Q-learning globally minimize the mean-squared projected Bellman error at a sublinear rate. Moreover, the associated feature representation converges to the optimal one, generalizing the previous analysis of Cai et al. (2019) in the neural tangent kernel regime, where the associated feature representation stabilizes at the initial one. The key to our analysis is a mean-field perspective, which connects the evolution of a finite-dimensional parameter to its limiting counterpart over an infinite-dimensional Wasserstein space. Our analysis generalizes to soft Q-learning, which is further connected to policy gradient.
Offline detection of change-points in the mean for stationary graph signals
Venue: arXiv cs.LG 2024
Year: 2024

This paper addresses the problem of segmenting a stream of graph signals: we aim to detect changes in the mean of a multivariate signal defined over the nodes of a known graph. We propose an offline method that relies on the concept of graph signal stationarity and allows the convenient translation of the problem from the original vertex domain to the spectral domain (Graph Fourier Transform), where it is much easier to solve. Although the obtained spectral representation is sparse in real applications, to the best of our knowledge this property has not been sufficiently exploited in the existing related literature. Our change-point detection method adopts a model selection approach that takes into account the sparsity of the spectral representation and determines automatically the number of change-points. Our detector comes with a proof of a non-asymptotic oracle inequality. Numerical experiments demonstrate the performance of the proposed method.
MgSvF: Multi-Grained Slow vs. Fast Framework for Few-Shot Class-Incremental Learning
Venue: arXiv cs.CV 2024
Year: 2024

As a challenging problem, few-shot class-incremental learning (FSCIL) continually learns a sequence of tasks, confronting the dilemma between slow forgetting of old knowledge and fast adaptation to new knowledge. In this paper, we concentrate on this "slow vs. fast" (SvF) dilemma to determine which knowledge components to be updated in a slow fashion or a fast fashion, and thereby balance old-knowledge preservation and new-knowledge adaptation. We propose a multi-grained SvF learning strategy to cope with the SvF dilemma from two different grains: intra-space (within the same feature space) and inter-space (between two different feature spaces). The proposed strategy designs a novel frequency-aware regularization to boost the intra-space SvF capability, and meanwhile develops a new feature space composition operation to enhance the inter-space SvF learning performance. With the multi-grained SvF learning strategy, our method outperforms the state-of-the-art approaches by a large margin.
Denotational Correctness of Forward-Mode Automatic Differentiation for Iteration and Recursion
Venue: arXiv cs.PL 2024
Year: 2024

We present semantic correctness proofs of forward-mode Automatic Differentiation (AD) for languages with sources of partiality such as partial operations, lazy conditionals on real parameters, iteration, and term and type recursion. We first define an AD macro on a standard call-by-value language with some primitive operations for smooth partial functions and constructs for real conditionals and iteration, as a unique structure preserving macro determined by its action on the primitive operations. We define a semantics for the language in terms of diffeological spaces, where the key idea is to make use of a suitable partiality monad. A semantic logical relations argument, constructed through a subsconing construction over diffeological spaces, yields a correctness proof of the defined AD macro. A key insight is that, to reason about differentiation at sum types, we work with relations which form sheaves. Next, we extend our language with term and type recursion. To model this in our semantics, we introduce a new notion of space, suitable for modeling both recursion and differentiation, by equipping a diffeological space with a compatible $ω$cpo-structure. We demonstrate that our whole development extends to this setting. By making use of a semantic, rather than syntactic, logical relations argument, we circumvent the usual technicalities of logical relations techniques for type recursion.
AQD: Towards Accurate Fully-Quantized Object Detection
Venue: arXiv cs.CV 2024
Year: 2024

Network quantization allows inference to be conducted using low-precision arithmetic for improved inference efficiency of deep neural networks on edge devices. However, designing aggressively low-bit (e.g., 2-bit) quantization schemes on complex tasks, such as object detection, still remains challenging in terms of severe performance degradation and unverifiable efficiency on common hardware. In this paper, we propose an Accurate Quantized object Detection solution, termed AQD, to fully get rid of floating-point computation. To this end, we target using fixed-point operations in all kinds of layers, including the convolutional layers, normalization layers, and skip connections, allowing the inference to be executed using integer-only arithmetic. To demonstrate the improved latency-vs-accuracy trade-off, we apply the proposed methods on RetinaNet and FCOS. In particular, experimental results on MS-COCO dataset show that our AQD achieves comparable or even better performance compared with the full-precision counterpart under extremely low-bit schemes, which is of great practical value. Source code and models are available at: https://github.com/ziplab/QTool
Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
Venue: arXiv cs.LG 2024
Year: 2024

The principle of optimism in the face of uncertainty is one of the most widely used and successful ideas in multi-armed bandits and reinforcement learning. However, existing optimistic algorithms (primarily UCB and its variants) often struggle to deal with general function classes and large context spaces. In this paper, we study general contextual bandits with an offline regression oracle and propose a simple, generic principle to design optimistic algorithms, dubbed "Upper Counterfactual Confidence Bounds" (UCCB). The key innovation of UCCB is building confidence bounds in policy space, rather than in action space as is done in UCB. We demonstrate that these algorithms are provably optimal and computationally efficient in handling general function classes and large context spaces. Furthermore, we illustrate that the UCCB principle can be seamlessly extended to infinite-action general contextual bandits, provide the first solutions to these settings when employing an offline regression oracle.
Parameter estimation for Gibbs distributions
Venue: arXiv cs.DS 2024
Year: 2024

We consider Gibbs distributions, which are families of probability distributions over a discrete space $Ω$ with probability mass function of the form $μ^Ω_β(ω) \propto e^{βH(ω)}$ for $β$ in an interval $[β_{\min}, β_{\max}]$ and $H( ω) \in \{0 \} \cup [1, n]$. The partition function is the normalization factor $Z(β)=\sum_{ω\inΩ}e^{βH(ω)}$. Two important parameters of these distributions are the log partition ratio $q = \log \tfrac{Z(β_{\max})}{Z(β_{\min})}$ and the counts $c_x = |H^{-1}(x)|$. These are correlated with system parameters in a number of physical applications and sampling algorithms. Our first main result is to estimate the counts $c_x$ using roughly $\tilde O( \frac{q}{\varepsilon^2})$ samples for general Gibbs distributions and $\tilde O( \frac{n^2}{\varepsilon^2} )$ samples for integer-valued distributions (ignoring some second-order terms and parameters), and we show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs, independent sets, and perfect matchings. As a key subroutine, we also develop algorithms to compute the partition function $Z$ using $\tilde O(\frac{q}{\varepsilon^2})$ samples for general Gibbs distributions and using $\tilde O(\frac{n^2}{\varepsilon^2})$ samples for integer-valued distributions.
Stochastic Optimization and Learning for Two-Stage Supplier Problems
Venue: arXiv cs.DS 2024
Year: 2024

The main focus of this paper is radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the form of a budget constraint. In addition to the standard (homogeneous) setting where all clients must be within a distance $R$ of the nearest facility, we provide results for the more general problem where the radius demands may be inhomogeneous (i.e., different for each client). We also explore a number of variants where additional constraints are imposed on the first-stage decisions, specifically matroid and multi-knapsack constraints, and provide results for these settings. We derive results for the most general distributional setting, where there is only black-box access to the underlying distribution. To accomplish this, we first develop algorithms for the polynomial scenarios setting; we then employ a novel scenario-discarding variant of the standard Sample Average Approximation (SAA) method, which crucially exploits properties of the restricted-case algorithms. We note that the scenario-discarding modification to the SAA method is necessary in order to optimize over the radius.
Deep-Lock: Secure Authorization for Deep Neural Networks
Venue: arXiv cs.LG 2024
Year: 2024

Trained Deep Neural Network (DNN) models are considered valuable Intellectual Properties (IP) in several business models. Prevention of IP theft and unauthorized usage of such DNN models has been raised as of significant concern by industry. In this paper, we address the problem of preventing unauthorized usage of DNN models by proposing a generic and lightweight key-based model-locking scheme, which ensures that a locked model functions correctly only upon applying the correct secret key. The proposed scheme, known as Deep-Lock, utilizes S-Boxes with good security properties to encrypt each parameter of a trained DNN model with secret keys generated from a master key via a key scheduling algorithm. The resulting dense network of encrypted weights is found robust against model fine-tuning attacks. Finally, Deep-Lock does not require any intervention in the structure and training of the DNN models, making it applicable for all existing software and hardware implementations of DNN.
FedCVT: Semi-supervised Vertical Federated Learning with Cross-view Training
Venue: arXiv cs.LG 2024
Year: 2024

Federated learning allows multiple parties to build machine learning models collaboratively without exposing data. In particular, vertical federated learning (VFL) enables participating parties to build a joint machine learning model based on distributed features of aligned samples. However, VFL requires all parties to share a sufficient amount of aligned samples. In reality, the set of aligned samples may be small, leaving the majority of the non-aligned data unused. In this article, we propose Federated Cross-view Training (FedCVT), a semi-supervised learning approach that improves the performance of the VFL model with limited aligned samples. More specifically, FedCVT estimates representations for missing features, predicts pseudo-labels for unlabeled samples to expand the training set, and trains three classifiers jointly based on different views of the expanded training set to improve the VFL model's performance. FedCVT does not require parties to share their original data and model parameters, thus preserving data privacy. We conduct experiments on NUS-WIDE, Vehicle, and CIFAR10 datasets. The experimental results demonstrate that FedCVT significantly outperforms vanilla VFL that only utilizes aligned samples. Finally, we perform ablation studies to investigate the contribution of each component of FedCVT to the performance of FedCVT. Code is available at https://github.com/yankang18/FedCVT
Algorithmic Persuasion with Evidence
Venue: arXiv cs.GT 2024
Year: 2024

In a game of persuasion with evidence, a sender has private information. By presenting evidence on the information, the sender wishes to persuade a receiver to take a single action (e.g., hire a job candidate, or convict a defendant). The sender's utility depends solely on whether or not the receiver takes the action. The receiver's utility depends on both the action and the sender's private information. We study three natural variations. First, we consider the problem of computing an equilibrium of the game without commitment power. Second, we consider a persuasion variant, where the sender commits to a signaling scheme and the receiver, after seeing the evidence, takes the action or not. Third, we study a delegation variant, where the receiver first commits to taking the action if being presented certain evidence, and the sender presents evidence to maximize the probability the action is taken. We study these variants through the computational lens, and give hardness results, optimal approximation algorithms, and polynomial-time algorithms for special cases. Among our results is an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm in algorithmic economics.
Author Mentions in Science News Reveal Widespread Disparities Across Name-inferred Ethnicities
Venue: arXiv cs.CY 2024
Year: 2024

Media outlets play a key role in spreading scientific knowledge to the general public and raising the profile of researchers among their peers. Yet, how journalists choose to present researchers in their stories is poorly understood. Using a comprehensive dataset of 223,587 news stories from 288 U.S. outlets reporting on 100,486 research papers across all areas of science, we investigate if the authors' ethnicities, as inferred from names, are associated with whether journalists explicitly mention them by name. By focusing on research papers news outlets chose to cover, our analysis reduces concerns that differences in name mentions are driven by differences in research quality or newsworthiness. We find substantial disparities in name mention rates across ethnically-distinctive names. Researchers with non-Anglo names, especially those with East Asian and African names, are significantly less likely to be mentioned in news stories covering their research, even when comparing stories from a particular news outlet reporting on publications in a particular scientific venue on a particular research topic. The disparities are not fully explained by authors' affiliation locations, suggesting that pragmatic factors such as difficulties in scheduling interviews play only a partial role. Furthermore, among U.S.-based authors, journalists more often use authors' institutions instead of names when referring to non-Anglo-named authors, suggesting that journalists' rhetorical choices are also key. Overall, this study finds evidence of ethnic disparities in how researchers are described in the media coverage of their research, likely affecting thousands of non-Anglo-named scholars in our data alone.
Approximate Multiplication of Sparse Matrices with Limited Space
Venue: arXiv cs.LG 2024
Year: 2024

Approximate matrix multiplication with limited space has received ever-increasing attention due to the emergence of large-scale applications. Recently, based on a popular matrix sketching algorithm -- frequent directions, previous work has introduced co-occuring directions (COD) to reduce the approximation error for this problem. Although it enjoys the space complexity of $O((m_x+m_y)\ell)$ for two input matrices $X\in\mathbb{R}^{m_x\times n}$ and $Y\in\mathbb{R}^{m_y\times n}$ where $\ell$ is the sketch size, its time complexity is $O\left(n(m_x+m_y+\ell)\ell\right)$, which is still very high for large input matrices. In this paper, we propose to reduce the time complexity by exploiting the sparsity of the input matrices. The key idea is to employ an approximate singular value decomposition (SVD) method which can utilize the sparsity, to reduce the number of QR decompositions required by COD. In this way, we develop sparse co-occuring directions, which reduces the time complexity to $\widetilde{O}\left((\nnz(X)+\nnz(Y))\ell+n\ell^2\right)$ in expectation while keeps the same space complexity as $O((m_x+m_y)\ell)$, where $\nnz(X)$ denotes the number of non-zero entries in $X$ and the $\widetilde{O}$ notation hides constant factors as well as polylogarithmic factors. Theoretical analysis reveals that the approximation error of our algorithm is almost the same as that of COD. Furthermore, we empirically verify the efficiency and effectiveness of our algorithm.
On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis
Venue: arXiv cs.LG 2024
Year: 2024

We study the approximation properties and optimization dynamics of recurrent neural networks (RNNs) when applied to learn input-output relationships in temporal data. We consider the simple but representative setting of using continuous-time linear RNNs to learn from data generated by linear relationships. Mathematically, the latter can be understood as a sequence of linear functionals. We prove a universal approximation theorem of such linear functionals, and characterize the approximation rate and its relation with memory. Moreover, we perform a fine-grained dynamical analysis of training linear RNNs, which further reveal the intricate interactions between memory and learning. A unifying theme uncovered is the non-trivial effect of memory, a notion that can be made precise in our framework, on approximation and optimization: when there is long term memory in the target, it takes a large number of neurons to approximate it. Moreover, the training process will suffer from slow downs. In particular, both of these effects become exponentially more pronounced with memory - a phenomenon we call the "curse of memory". These analyses represent a basic step towards a concrete mathematical understanding of new phenomenon that may arise in learning temporal relationships using recurrent architectures.