OpenRaiser/Intern-Atlas huggingface dataset:
Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size
Venue: arXiv cs.CG 2024
Year: 2024

Given a set of $n$ sites from $\mathbb{R}^d$, each having some positive weight factor, the Multiplicatively Weighted Voronoi Diagram is a subdivision of space that associates each cell to the site whose weighted Euclidean distance is minimal for all points in the cell. We give novel approximation algorithms that output a cube-based subdivision such that the weighted distance of a point with respect to the associated site is at most $(1+\varepsilon)$ times the minimum weighted distance, for any fixed parameter $\varepsilon \in (0,1)$. The diagram size is $O_d(n \log(1/\varepsilon)/\varepsilon^{d-1})$ and the construction time is within an $O_D(\log(n)/\varepsilon^{(d+5)/2})$-factor of the size bound. We also prove a matching lower bound for the size, showing that the proposed method is the first to achieve \emph{optimal size}, up to $Θ(1)^d$-factors. In particular, the obscure $\log(1/\varepsilon)$ factor is unavoidable. As a by-product, we obtain a factor $d^{O(d)}$ improvement in size for the unweighted case and $O(d \log(n) + d^2 \log(1/\varepsilon))$ point-location time in the subdivision, improving the known query bound by one $d$-factor. The key ingredients of our approximation algorithms are the study of convex regions that we call cores, an adaptive refinement algorithm to obtain optimal size, and a novel notion of \emph{bisector coresets}, which may be of independent interest. In particular, we show that coresets with $O_d(1/\varepsilon^{(d+3)/2})$ worst-case size can be computed in near-linear time.
Explicit non-special divisors of small degree, algebraic geometric hulls, and LCD codes from Kummer extensions
Venue: arXiv cs.IT 2024
Year: 2024

In this paper, we consider the hull of an algebraic geometry code, meaning the intersection of the code and its dual. We demonstrate how codes whose hulls are algebraic geometry codes may be defined using only rational places of Kummer extensions (and Hermitian function fields in particular). Our primary tool is explicitly constructing non-special divisors of degrees $g$ and $g-1$ on certain families of function fields with many rational places, accomplished by appealing to Weierstrass semigroups. We provide explicit algebraic geometry codes with hulls of specified dimensions, producing along the way linearly complementary dual algebraic geometric codes from the Hermitian function field (among others) using only rational places and an answer to an open question posed by Ballet and Le Brigand for particular function fields. These results complement earlier work by Mesnager, Tang, and Qi that use lower-genus function fields as well as instances using places of a higher degree from Hermitian function fields to construct linearly complementary dual (LCD) codes and that of Carlet, Mesnager, Tang, Qi, and Pellikaan to provide explicit algebraic geometry codes with the LCD property rather than obtaining codes via monomial equivalences.
Wasserstein Flow Meets Replicator Dynamics: A Mean-Field Analysis of Representation Learning in Actor-Critic
Venue: arXiv cs.LG 2024
Year: 2024

Actor-critic (AC) algorithms, empowered by neural networks, have had significant empirical success in recent years. However, most of the existing theoretical support for AC algorithms focuses on the case of linear function approximations, or linearized neural networks, where the feature representation is fixed throughout training. Such a limitation fails to capture the key aspect of representation learning in neural AC, which is pivotal in practical problems. In this work, we take a mean-field perspective on the evolution and convergence of feature-based neural AC. Specifically, we consider a version of AC where the actor and critic are represented by overparameterized two-layer neural networks and are updated with two-timescale learning rates. The critic is updated by temporal-difference (TD) learning with a larger stepsize while the actor is updated via proximal policy optimization (PPO) with a smaller stepsize. In the continuous-time and infinite-width limiting regime, when the timescales are properly separated, we prove that neural AC finds the globally optimal policy at a sublinear rate. Additionally, we prove that the feature representation induced by the critic network is allowed to evolve within a neighborhood of the initial one.
Res2NetFuse: A Novel Res2Net-based Fusion Method for Infrared and Visible Images
Venue: arXiv cs.CV 2024
Year: 2024

The fusion of visible light and infrared images has garnered significant attention in the field of imaging due to its pivotal role in various applications, including surveillance, remote sensing, and medical imaging. Therefore, this paper introduces a novel fusion framework using Res2Net architecture, capturing features across diverse receptive fields and scales for effective extraction of global and local features. Our methodology is structured into three fundamental components: the first part involves the Res2Net-based encoder, followed by the second part, which encompasses the fusion layer, and finally, the third part, which comprises the decoder. The encoder based on Res2Net is utilized for extracting multi-scale features from the input image. Simultaneously, with a single image as input, we introduce a pioneering training strategy tailored for a Res2Net-based encoder. We further enhance the fusion process with a novel strategy based on the attention model, ensuring precise reconstruction by the decoder for the fused image. Experimental results unequivocally showcase our method's unparalleled fusion performance, surpassing existing techniques, as evidenced by rigorous subjective and objective evaluations.
A Theoretical Understanding of Gradient Bias in Meta-Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

Gradient-based Meta-RL (GMRL) refers to methods that maintain two-level optimisation procedures wherein the outer-loop meta-learner guides the inner-loop gradient-based reinforcement learner to achieve fast adaptations. In this paper, we develop a unified framework that describes variations of GMRL algorithms and points out that existing stochastic meta-gradient estimators adopted by GMRL are actually \textbf{biased}. Such meta-gradient bias comes from two sources: 1) the compositional bias incurred by the two-level problem structure, which has an upper bound of $\mathcal{O}\big(Kα^{K}\hatσ_{\text{In}}|τ|^{-0.5}\big)$ \emph{w.r.t.} inner-loop update step $K$, learning rate $α$, estimate variance $\hatσ^{2}_{\text{In}}$ and sample size $|τ|$, and 2) the multi-step Hessian estimation bias $\hatΔ_{H}$ due to the use of autodiff, which has a polynomial impact $\mathcal{O}\big((K-1)(\hatΔ_{H})^{K-1}\big)$ on the meta-gradient bias. We study tabular MDPs empirically and offer quantitative evidence that testifies our theoretical findings on existing stochastic meta-gradient estimators. Furthermore, we conduct experiments on Iterated Prisoner's Dilemma and Atari games to show how other methods such as off-policy learning and low-bias estimator can help fix the gradient bias for GMRL algorithms in general.
Cross-Domain Deep Code Search with Meta Learning
Venue: arXiv cs.SE 2024
Year: 2024

Recently, pre-trained programming language models such as CodeBERT have demonstrated substantial gains in code search. Despite showing great performance, they rely on the availability of large amounts of parallel data to fine-tune the semantic mappings between queries and code. This restricts their practicality in domain-specific languages with relatively scarce and expensive data. In this paper, we propose CroCS, a novel approach for domain-specific code search. CroCS employs a transfer learning framework where an initial program representation model is pre-trained on a large corpus of common programming languages (such as Java and Python) and is further adapted to domain-specific languages such as SQL and Solidity. Unlike cross-language CodeBERT, which is directly fine-tuned in the target language, CroCS adapts a few-shot meta-learning algorithm called MAML to learn the good initialization of model parameters, which can be best reused in a domain-specific language. We evaluate the proposed approach on two domain-specific languages, namely, SQL and Solidity, with model transferred from two widely used languages (Python and Java). Experimental results show that CDCS significantly outperforms conventional pre-trained code models that are directly fine-tuned in domain-specific languages, and it is particularly effective for scarce data.
Automated Graph Machine Learning: Approaches, Libraries, Benchmarks and Directions
Venue: arXiv cs.LG 2024
Year: 2024

Graph machine learning has been extensively studied in both academic and industry. However, as the literature on graph learning booms with a vast number of emerging methods and techniques, it becomes increasingly difficult to manually design the optimal machine learning algorithm for different graph-related tasks. To tackle the challenge, automated graph machine learning, which aims at discovering the best hyper-parameter and neural architecture configuration for different graph tasks/data without manual design, is gaining an increasing number of attentions from the research community. In this paper, we extensively discuss automated graph machine learning approaches, covering hyper-parameter optimization (HPO) and neural architecture search (NAS) for graph machine learning. We briefly overview existing libraries designed for either graph machine learning or automated machine learning respectively, and further in depth introduce AutoGL, our dedicated and the world's first open-source library for automated graph machine learning. Also, we describe a tailored benchmark that supports unified, reproducible, and efficient evaluations. Last but not least, we share our insights on future research directions for automated graph machine learning. This paper is the first systematic and comprehensive discussion of approaches, libraries as well as directions for automated graph machine learning.
Beyond the Visible: A Survey on Cross-spectral Face Recognition
Venue: arXiv cs.CV 2024
Year: 2024

Cross-spectral face recognition (CFR) refers to recognizing individuals using face images stemming from different spectral bands, such as infrared versus visible. While CFR is inherently more challenging than classical face recognition due to significant variation in facial appearance caused by the modality gap, it is useful in many scenarios including night-vision biometrics and detecting presentation attacks. Recent advances in deep neural networks (DNNs) have resulted in significant improvement in the performance of CFR systems. Given these developments, the contributions of this survey are three-fold. First, we provide an overview of CFR, by formalizing the CFR problem and presenting related applications. Secondly, we discuss the appropriate spectral bands for face recognition and discuss recent CFR methods, placing emphasis on deep neural networks. In particular we describe techniques that have been proposed to extract and compare heterogeneous features emerging from different spectral bands. We also discuss the datasets that have been used for evaluating CFR methods. Finally, we discuss the challenges and future lines of research on this topic.
Language Model-Based Paired Variational Autoencoders for Robotic Language Learning
Venue: arXiv cs.NE 2024
Year: 2024

Human infants learn language while interacting with their environment in which their caregivers may describe the objects and actions they perform. Similar to human infants, artificial agents can learn language while interacting with their environment. In this work, first, we present a neural model that bidirectionally binds robot actions and their language descriptions in a simple object manipulation scenario. Building on our previous Paired Variational Autoencoders (PVAE) model, we demonstrate the superiority of the variational autoencoder over standard autoencoders by experimenting with cubes of different colours, and by enabling the production of alternative vocabularies. Additional experiments show that the model's channel-separated visual feature extraction module can cope with objects of different shapes. Next, we introduce PVAE-BERT, which equips the model with a pretrained large-scale language model, i.e., Bidirectional Encoder Representations from Transformers (BERT), enabling the model to go beyond comprehending only the predefined descriptions that the network has been trained on; the recognition of action descriptions generalises to unconstrained natural language as the model becomes capable of understanding unlimited variations of the same descriptions. Our experiments suggest that using a pretrained language model as the language encoder allows our approach to scale up for real-world scenarios with instructions from human users.
An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
Venue: arXiv cs.DS 2024
Year: 2024

\emph{$K$-best enumeration}, which asks to output $k$-best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, $k$-best enumeration tends to be intractable since, in many cases, finding one optimum solution is \NP-hard. To overcome this difficulty, we combine $k$-best enumeration with a concept of enumeration algorithms called \emph{approximation enumeration algorithms}. As a main result, we propose a $4$-approximation algorithm for minimal connected edge dominating sets which outputs $k$ minimal solutions with cardinality at most $4\cdot\OPT$, where $\OPT$ is the cardinality of a minimum solution which is \emph{not} outputted by the algorithm. Our proposed algorithm runs in $\order{nm^2Δ}$ delay, where $n$, $m$, $Δ$ are the number of vertices, the number of edges, and the maximum degree of an input graph.
Learning to Predict Gradients for Semi-Supervised Continual Learning
Venue: arXiv cs.LG 2024
Year: 2024

A key challenge for machine intelligence is to learn new visual concepts without forgetting the previously acquired knowledge. Continual learning is aimed towards addressing this challenge. However, there is a gap between existing supervised continual learning and human-like intelligence, where human is able to learn from both labeled and unlabeled data. How unlabeled data affects learning and catastrophic forgetting in the continual learning process remains unknown. To explore these issues, we formulate a new semi-supervised continual learning method, which can be generically applied to existing continual learning models. Specifically, a novel gradient learner learns from labeled data to predict gradients on unlabeled data. Hence, the unlabeled data could fit into the supervised continual learning method. Different from conventional semi-supervised settings, we do not hypothesize that the underlying classes, which are associated to the unlabeled data, are known to the learning process. In other words, the unlabeled data could be very distinct from the labeled data. We evaluate the proposed method on mainstream continual learning, adversarial continual learning, and semi-supervised learning tasks. The proposed method achieves state-of-the-art performance on classification accuracy and backward transfer in the continual learning setting while achieving desired performance on classification accuracy in the semi-supervised learning setting. This implies that the unlabeled images can enhance the generalizability of continual learning models on the predictive ability on unseen data and significantly alleviate catastrophic forgetting. The code is available at \url{https://github.com/luoyan407/grad_prediction.git}.
Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

Value-function (VF) approximation is a central problem in Reinforcement Learning (RL). Classical non-parametric VF estimation suffers from the curse of dimensionality. As a result, parsimonious parametric models have been adopted to approximate VFs in high-dimensional spaces, with most efforts being focused on linear and neural-network-based approaches. Differently, this paper puts forth a a parsimonious non-parametric approach, where we use stochastic low-rank algorithms to estimate the VF matrix in an online and model-free fashion. Furthermore, as VFs tend to be multi-dimensional, we propose replacing the classical VF matrix representation with a tensor (multi-way array) representation and, then, use the PARAFAC decomposition to design an online model-free tensor low-rank algorithm. Different versions of the algorithms are proposed, their complexity is analyzed, and their performance is assessed numerically using standardized RL environments.
Different Strokes in Randomised Strategies: Revisiting Kuhn's Theorem under Finite-Memory Assumptions
Venue: arXiv cs.GT 2024
Year: 2024

Two-player (antagonistic) games on (possibly stochastic) graphs are a prevalent model in theoretical computer science, notably as a framework for reactive synthesis. Optimal strategies may require randomisation when dealing with inherently probabilistic goals, balancing multiple objectives, or in contexts of partial information. There is no unique way to define randomised strategies. For instance, one can use so-called mixed strategies or behavioural ones. In the most general setting, these two classes do not share the same expressiveness. A seminal result in game theory -- Kuhn's theorem -- asserts their equivalence in games of perfect recall. This result crucially relies on the possibility for strategies to use infinite memory, i.e., unlimited knowledge of all past observations. However, computer systems are finite in practice. Hence it is pertinent to restrict our attention to finite-memory strategies, defined as automata with outputs. Randomisation can be implemented in these in different ways: the initialisation, outputs or transitions can be randomised or deterministic respectively. Depending on which aspects are randomised, the expressiveness of the corresponding class of finite-memory strategies differs. In this work, we study two-player concurrent stochastic games and provide a complete taxonomy of the classes of finite-memory strategies obtained by varying which of the three aforementioned components are randomised. Our taxonomy holds in games of perfect and imperfect information with perfect recall, and in games with more than two players. We also provide an adapted taxonomy for games with imperfect recall.
DecisionHoldem: Safe Depth-Limited Solving With Diverse Opponents for Imperfect-Information Games
Venue: arXiv cs.AI 2024
Year: 2024

An imperfect-information game is a type of game with asymmetric information. It is more common in life than perfect-information game. Artificial intelligence (AI) in imperfect-information games, such like poker, has made considerable progress and success in recent years. The great success of superhuman poker AI, such as Libratus and Deepstack, attracts researchers to pay attention to poker research. However, the lack of open-source code limits the development of Texas hold'em AI to some extent. This article introduces DecisionHoldem, a high-level AI for heads-up no-limit Texas hold'em with safe depth-limited subgame solving by considering possible ranges of opponent's private hands to reduce the exploitability of the strategy. Experimental results show that DecisionHoldem defeats the strongest openly available agent in heads-up no-limit Texas hold'em poker, namely Slumbot, and a high-level reproduction of Deepstack, viz, Openstack, by more than 730 mbb/h (one-thousandth big blind per round) and 700 mbb/h. Moreover, we release the source codes and tools of DecisionHoldem to promote AI development in imperfect-information games.
Learning Optimal Topology for Ad-hoc Robot Networks
Venue: arXiv cs.RO 2024
Year: 2024

In this paper, we synthesize a data-driven method to predict the optimal topology of an ad-hoc robot network. This problem is technically a multi-task classification problem. However, we divide it into a class of multi-class classification problems that can be more efficiently solved. For this purpose, we first compose an algorithm to create ground-truth optimal topologies associated with various configurations of a robot network. This algorithm incorporates a complex collection of optimality criteria that our learning model successfully manages to learn. This model is an stacked ensemble whose output is the topology prediction for a particular robot. Each stacked ensemble instance constitutes three low-level estimators whose outputs will be aggregated by a high-level boosting blender. Applying our model to a network of 10 robots displays over 80% accuracy in the prediction of optimal topologies corresponding to various configurations of the cited network.
Noisy Sorting Capacity
Venue: arXiv cs.IT 2024
Year: 2024

Sorting is the task of ordering $n$ elements using pairwise comparisons. It is well known that $m=Θ(n\log n)$ comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability $p$. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons $m$ to achieve a given desired error probability, we consider randomized algorithms with expected number of queries $\textsf{E}[M]$ and aim at characterizing the maximal sorting rate $\frac{n\log n}{\textsf{E}[M]}$ such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds -- one for fixed-length algorithms and one for variable-length algorithms -- are established by combining the insertion sort algorithm with the well-known Burnashev--Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of $p$, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.
Perpetual maintenance of machines with different urgency requirements
Venue: arXiv cs.DS 2024
Year: 2024

A garden $G$ is populated by $n\ge 1$ bamboos $b_1, b_2, ..., b_n$ with the respective daily growth rates $h_1 \ge h_2 \ge \dots \ge h_n$. It is assumed that the initial heights of bamboos are zero. The robotic gardener maintaining the garden regularly attends bamboos and trims them to height zero according to some schedule. The Bamboo Garden Trimming Problem (BGT) is to design a perpetual schedule of cuts to maintain the elevation of the bamboo garden as low as possible. The bamboo garden is a metaphor for a collection of machines which have to be serviced, with different frequencies, by a robot which can service only one machine at a time. The objective is to design a perpetual schedule of servicing which minimizes the maximum (weighted) waiting time for servicing. We consider two variants of BGT. In discrete BGT the robot trims only one bamboo at the end of each day. In continuous BGT the bamboos can be cut at any time, however, the robot needs time to move from one bamboo to the next. For discrete BGT, we show tighter approximation algorithms for the case when the growth rates are balanced and for the general case. The former algorithm settles one of the conjectures about the Pinwheel problem. The general approximation algorithm improves on the previous best approximation ratio. For continuous BGT, we propose approximation algorithms which achieve approximation ratios $O(\log \lceil h_1/h_n\rceil)$ and $O(\log n)$.