OpenRaiser/Intern-Atlas huggingface dataset:
A Unified Linear Speedup Analysis of Federated Averaging and Nesterov FedAvg
Venue: arXiv cs.LG 2023
Year: 2023

Federated learning (FL) learns a model jointly from a set of participating devices without sharing each other's privately held data. The characteristics of non-i.i.d. data across the network, low device participation, high communication costs, and the mandate that data remain private bring challenges in understanding the convergence of FL algorithms, particularly regarding how convergence scales with the number of participating devices. In this paper, we focus on Federated Averaging (FedAvg), one of the most popular and effective FL algorithms in use today, as well as its Nesterov accelerated variant, and conduct a systematic study of how their convergence scale with the number of participating devices under non-i.i.d. data and partial participation in convex settings. We provide a unified analysis that establishes convergence guarantees for FedAvg under strongly convex, convex, and overparameterized strongly convex problems. We show that FedAvg enjoys linear speedup in each case, although with different convergence rates and communication efficiencies. For strongly convex and convex problems, we also characterize the corresponding convergence rates for the Nesterov accelerated FedAvg algorithm, which are the first linear speedup guarantees for momentum variants of FedAvg in convex settings. Empirical studies of the algorithms in various settings have supported our theoretical results.
Optimal Learning for Structured Bandits
Venue: arXiv cs.LG 2023
Year: 2023

We study structured multi-armed bandits, which is the problem of online decision-making under uncertainty in the presence of structural information. In this problem, the decision-maker needs to discover the best course of action despite observing only uncertain rewards over time. The decision-maker is aware of certain convex structural information regarding the reward distributions; that is, the decision-maker knows the reward distributions of the arms belong to a convex compact set. In the presence such structural information, they then would like to minimize their regret by exploiting this information, where the regret is its performance difference against a benchmark policy that knows the best action ahead of time. In the absence of structural information, the classical upper confidence bound (UCB) and Thomson sampling algorithms are well known to suffer minimal regret. As recently pointed out, neither algorithms are, however, capable of exploiting structural information that is commonly available in practice. We propose a novel learning algorithm that we call "DUSA" whose regret matches the information-theoretic regret lower bound up to a constant factor and can handle a wide range of structural information. Our algorithm DUSA solves a dual counterpart of the regret lower bound at the empirical reward distribution and follows its suggested play. We show that this idea leads to the first computationally viable learning policy with asymptotic minimal regret for various structural information, including well-known structured bandits such as linear, Lipschitz, and convex bandits, and novel structured bandits that have not been studied in the literature due to the lack of a unified and flexible framework.
Compressed sensing-based SARS-CoV-2 pool testing
Venue: arXiv cs.IT 2023
Year: 2023

We propose a compressed sensing-based testing approach with a practical measurement design and a tuning-free and noise-robust algorithm for detecting infected persons. Compressed sensing results can be used to provably detect a small number of infected persons among a possibly large number of people. There are several advantages of this method compared to classical group testing. Firstly, it is non-adaptive and thus possibly faster to perform than adaptive methods which is crucial in exponentially growing pandemic phases. Secondly, due to nonnegativity of measurements and an appropriate noise model, the compressed sensing problem can be solved with the non-negative least absolute deviation regression (NNLAD) algorithm. This convex tuning-free program requires the same number of tests as current state of the art group testing methods. Empirically it performs significantly better than theoretically guaranteed, and thus the high-throughput, reducing the number of tests to a fraction compared to other methods. Further, numerical evidence suggests that our method can correct sparsely occurring errors.
OccamNet: A Fast Neural Model for Symbolic Regression at Scale
Venue: arXiv cs.LG 2023
Year: 2023

Neural networks' expressiveness comes at the cost of complex, black-box models that often extrapolate poorly beyond the domain of the training dataset, conflicting with the goal of finding compact analytic expressions to describe scientific data. We introduce OccamNet, a neural network model that finds interpretable, compact, and sparse symbolic fits to data, à la Occam's razor. Our model defines a probability distribution over functions with efficient sampling and function evaluation. We train by sampling functions and biasing the probability mass toward better fitting solutions, backpropagating using cross-entropy matching in a reinforcement-learning loss. OccamNet can identify symbolic fits for a variety of problems, including analytic and non-analytic functions, implicit functions, and simple image classification, and can outperform state-of-the-art symbolic regression methods on real-world regression datasets. Our method requires a minimal memory footprint, fits complicated functions in minutes on a single CPU, and scales on a GPU.
ResNet After All? Neural ODEs and Their Numerical Solution
Venue: arXiv cs.LG 2023
Year: 2023

A key appeal of the recently proposed Neural Ordinary Differential Equation (ODE) framework is that it seems to provide a continuous-time extension of discrete residual neural networks. As we show herein, though, trained Neural ODE models actually depend on the specific numerical method used during training. If the trained model is supposed to be a flow generated from an ODE, it should be possible to choose another numerical solver with equal or smaller numerical error without loss of performance. We observe that if training relies on a solver with overly coarse discretization, then testing with another solver of equal or smaller numerical error results in a sharp drop in accuracy. In such cases, the combination of vector field and numerical method cannot be interpreted as a flow generated from an ODE, which arguably poses a fatal breakdown of the Neural ODE concept. We observe, however, that there exists a critical step size beyond which the training yields a valid ODE vector field. We propose a method that monitors the behavior of the ODE solver during training to adapt its step size, aiming to ensure a valid ODE without unnecessarily increasing computational cost. We verify this adaptation algorithm on a common bench mark dataset as well as a synthetic dataset.
On the Nature and Types of Anomalies: A Review of Deviations in Data
Venue: arXiv cs.DB 2023
Year: 2023

Anomalies are occurrences in a dataset that are in some way unusual and do not fit the general patterns. The concept of the anomaly is typically ill-defined and perceived as vague and domain-dependent. Moreover, despite some 250 years of publications on the topic, no comprehensive and concrete overviews of the different types of anomalies have hitherto been published. By means of an extensive literature review this study therefore offers the first theoretically principled and domain-independent typology of data anomalies and presents a full overview of anomaly types and subtypes. To concretely define the concept of the anomaly and its different manifestations, the typology employs five dimensions: data type, cardinality of relationship, anomaly level, data structure, and data distribution. These fundamental and data-centric dimensions naturally yield 3 broad groups, 9 basic types, and 63 subtypes of anomalies. The typology facilitates the evaluation of the functional capabilities of anomaly detection algorithms, contributes to explainable data science, and provides insights into relevant topics such as local versus global anomalies.
Revisiting Robust Model Fitting Using Truncated Loss
Venue: arXiv cs.CV 2023
Year: 2023

Robust fitting is a fundamental problem in low-level vision, which is typically achieved by maximum consensus (MC) estimators to identify inliers first or by M-estimators directly. While these two methods are discriminately preferred in different applications, truncated loss based M-estimators are similar to MC as they can also identify inliers. This work revisits a formulation that achieves simultaneous inlier identification and model estimation (SIME) using truncated loss. It has a generalized form adapts to both linear and nonlinear residual models. We show that as SIME takes fitting residual into account in finding inliers, its lowest achievable residual in model fitting is lower than that of MC robust fitting. Then, an alternating minimization (AM) algorithm is employed to solve the SIME formulation. Meanwhile, a semidefinite relaxation (SDR) embedded AM algorithm is developed in order to ease the high nonconvexity of the SIME formulation. Furthermore, the new algorithms are applied to various 2D/3D registration problems. Experimental results show that the new algorithms significantly outperform RANSAC and deterministic approximate MC methods at high outlier ratios. Besides, in rotation and Euclidean registration problems, the new algorithms also compare favorably with state-of-the-art registration methods, especially in high noise and outliers. Code is available at \textit{https://github.com/FWen/mcme.git}.
Aligning AI With Shared Human Values
Venue: arXiv cs.CY 2023
Year: 2023

We show how to assess a language model's knowledge of basic concepts of morality. We introduce the ETHICS dataset, a new benchmark that spans concepts in justice, well-being, duties, virtues, and commonsense morality. Models predict widespread moral judgments about diverse text scenarios. This requires connecting physical and social world knowledge to value judgements, a capability that may enable us to steer chatbot outputs or eventually regularize open-ended reinforcement learning agents. With the ETHICS dataset, we find that current language models have a promising but incomplete ability to predict basic human ethical judgements. Our work shows that progress can be made on machine ethics today, and it provides a steppingstone toward AI that is aligned with human values.
NCS4CVR: Neuron-Connection Sharing for Multi-Task Learning in Video Conversion Rate Prediction
Venue: arXiv cs.IR 2023
Year: 2023

Click-through rate (CTR) and post-click conversion rate (CVR) predictions are two fundamental modules in industrial ranking systems such as recommender systems, advertising, and search engines. Since CVR involves much fewer samples than CTR (known as the CVR data sparsity problem), most of the existing works try to leverage CTR&CVR multi-task learning to improve CVR performance. However, typical coarse-grained sub-network/layer sharing methods may introduce conflicts and lead to performance degradation, since not every neuron or neuron connection in one layer should be shared between CVR and CTR tasks. This is because users may have different fine-grained content feature preferences between deep consumption and click behavior, represented by CVR and CTR, respectively. To address this sharing&conflict problem, we propose a novel multi-task CVR modeling scheme with neuron-connection level sharing named NCS4CVR, which can automatically and flexibly learn which neuron weights are shared or not shared without artificial experience. Compared with previous layer-level sharing methods, this is the first time that a fine-grained CTR&CVR sharing method at the neuron connection level is proposed, which is a research paradigm shift in the sharing level. Both offline and online experiments demonstrate that our method outperforms both the single-task model and the layer-level sharing model. Our proposed method has now been successfully deployed in an industry video recommender system serving major traffic.
Reactive Bisimulation Semantics for a Process Algebra with Time-Outs
Venue: arXiv cs.LO 2023
Year: 2023

This paper introduces the counterpart of strong bisimilarity for labelled transition systems extended with time-out transitions. It supports this concept through a modal characterisation, congruence results for a standard process algebra with recursion, and a complete axiomatisation.
A Background-Agnostic Framework with Adversarial Training for Abnormal Event Detection in Video
Venue: arXiv cs.CV 2023
Year: 2023

Abnormal event detection in video is a complex computer vision problem that has attracted significant attention in recent years. The complexity of the task arises from the commonly-adopted definition of an abnormal event, that is, a rarely occurring event that typically depends on the surrounding context. Following the standard formulation of abnormal event detection as outlier detection, we propose a background-agnostic framework that learns from training videos containing only normal events. Our framework is composed of an object detector, a set of appearance and motion auto-encoders, and a set of classifiers. Since our framework only looks at object detections, it can be applied to different scenes, provided that normal events are defined identically across scenes and that the single main factor of variation is the background. To overcome the lack of abnormal data during training, we propose an adversarial learning strategy for the auto-encoders. We create a scene-agnostic set of out-of-domain pseudo-abnormal examples, which are correctly reconstructed by the auto-encoders before applying gradient ascent on the pseudo-abnormal examples. We further utilize the pseudo-abnormal examples to serve as abnormal examples when training appearance-based and motion-based binary classifiers to discriminate between normal and abnormal latent features and reconstructions. We compare our framework with the state-of-the-art methods on four benchmark data sets, using various evaluation metrics. Compared to existing methods, the empirical results indicate that our approach achieves favorable performance on all data sets. In addition, we provide region-based and track-based annotations for two large-scale abnormal event detection data sets from the literature, namely ShanghaiTech and Subway.
A Framework for Generating Diverse Haskell-IO Exercise Tasks
Venue: arXiv cs.SE 2023
Year: 2023

We present the design of a framework to automatically generate a large range of different exercise tasks on Haskell-I/O programming. Automatic task generation is useful in many different ways. Manual task creating is a time consuming process, so automating it saves valuable time for the educator. Together with an automated assessment system automatic task generation allows students to practice with as many exercise tasks as needed. Additionally, each student can be given a slightly different version of a task, reducing issues regarding plagiarism that arise naturally in an e-learning environment. Our task generation is centered around a specification language for I/O behavior that we developed in an earlier work. The task generation framework, an EDSL in Haskell, provides powerful primitives for the creation of various artifacts, including program code, from specifications. We will not go into detail on the technical realization of these primitives. This article instead showcases how such artifacts and the framework as a whole can be used to build exercise tasks templates that can then be (randomly) instantiated.
Solving the single-track train scheduling problem via Deep Reinforcement Learning
Venue: arXiv cs.AI 2023
Year: 2023

Every day, railways experience disturbances and disruptions, both on the network and the fleet side, that affect the stability of rail traffic. Induced delays propagate through the network, which leads to a mismatch in demand and offer for goods and passengers, and, in turn, to a loss in service quality. In these cases, it is the duty of human traffic controllers, the so-called dispatchers, to do their best to minimize the impact on traffic. However, dispatchers inevitably have a limited depth of perception of the knock-on effect of their decisions, particularly how they affect areas of the network that are outside their direct control. In recent years, much work in Decision Science has been devoted to developing methods to solve the problem automatically and support the dispatchers in this challenging task. This paper investigates Machine Learning-based methods for tackling this problem, proposing two different Deep Q-Learning methods(Decentralized and Centralized). Numerical results show the superiority of these techniques with respect to the classical linear Q-Learning based on matrices. Moreover, the Centralized approach is compared with a MILP formulation showing interesting results. The experiments are inspired by data provided by a U.S. Class 1 railroad.
PANE: scalable and effective attributed network embedding
Venue: arXiv cs.SI 2023
Year: 2023

Given a graph G where each node is associated with a set of attributes, attributed network embedding (ANE) maps each node v in G to a compact vector Xv, which can be used in downstream machine learning tasks. Ideally, Xv should capture node v's affinity to each attribute, which considers not only v's own attribute associations, but also those of its connected nodes along edges in G. It is challenging to obtain high-utility embeddings that enable accurate predictions; scaling effective ANE computation to massive graphs pushes the difficulty of the problem to a whole new level. Existing solutions largely fail on such graphs, leading to prohibitive costs, low-quality embeddings, or both. This paper proposes PANE, an effective and scalable approach to ANE computation for massive graphs that achieves state-of-the-art result quality on multiple benchmark datasets. PANE obtains high scalability and effectiveness through 3 main algorithmic designs. First, it formulates the learning objective based on a novel random walk model for attributed networks. Second, PANE includes a highly efficient solver for the above optimization problem, whose key module is a carefully designed initialization of the embeddings, which drastically reduces the number of iterations required to converge. Finally, PANE utilizes multi-core CPUs through non-trivial parallelization of the above solver, which achieves scalability while retaining the high quality of the resulting embeddings. The performance of PANE depends upon the number of attributes in the input network. To handle large networks with numerous attributes, we further extend PANE to PANE++. Extensive experiments, comparing 10 existing approaches on 8 real datasets, demonstrate that PANE and PANE++ consistently outperform all existing methods in terms of result quality, while being orders of magnitude faster.
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
Venue: arXiv cs.DS 2023
Year: 2023

We prove that any two-pass graph streaming algorithm for the $s$-$t$ reachability problem in $n$-vertex directed graphs requires near-quadratic space of $n^{2-o(1)}$ bits. As a corollary, we also obtain near-quadratic space lower bounds for several other fundamental problems including maximum bipartite matching and (approximate) shortest path in undirected graphs. Our results collectively imply that a wide range of graph problems admit essentially no non-trivial streaming algorithm even when two passes over the input is allowed. Prior to our work, such impossibility results were only known for single-pass streaming algorithms, and the best two-pass lower bounds only ruled out $o(n^{7/6})$ space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.
A GPU Parallel Algorithm for Computing Morse-Smale Complexes
Venue: arXiv cs.GR 2023
Year: 2023

The Morse-Smale complex is a well studied topological structure that represents the gradient flow behavior between critical points of a scalar function. It supports multi-scale topological analysis and visualization of feature-rich scientific data. Several parallel algorithms have been proposed towards the fast computation of the 3D Morse-Smale complex. Its computation continues to pose significant algorithmic challenges. In particular, the non-trivial structure of the connections between the saddle critical points are not amenable to parallel computation. This paper describes a fine grained parallel algorithm for computing the Morse-Smale complex and a GPU implementation gMSC. The algorithm first determines the saddle-saddle reachability via a transformation into a sequence of vector operations, and next computes the paths between saddles by transforming it into a sequence of matrix operations. Computational experiments show that the method achieves up to 8.6x speedup over pyms3d and 6x speedup over TTK, the current shared memory implementations. The paper also presents a comprehensive experimental analysis of different steps of the algorithm and reports on their contribution towards runtime performance. Finally, it introduces a CPU based data parallel algorithm for simplifying the Morse-Smale complex via iterative critical point pair cancellation.
Disjunctive Delimited Control
Venue: arXiv cs.PL 2023
Year: 2023

Delimited control is a powerful mechanism for programming language extension which has been recently proposed for Prolog (and implemented in SWI-Prolog). By manipulating the control flow of a program from inside the language, it enables the implementation of powerful features, such as tabling, without modifying the internals of the Prolog engine. However, its current formulation is inadequate: it does not capture Prolog's unique non-deterministic nature which allows multiple ways to satisfy a goal. This paper fully embraces Prolog's non-determinism with a novel interface for disjunctive delimited control, which gives the programmer not only control over the sequential (conjunctive) control flow, but also over the non-deterministic control flow. We provide a meta-interpreter that conservatively extends Prolog with delimited control and show that it enables a range of typical Prolog features and extensions, now at the library level: findall, cut, branch-and-bound optimisation, probabilistic programming, . . . This paper is under consideration for publication in Theory and Practice of Logic Programming (TPLP).
Computing the Rate-Distortion Function of Gray-Wyner System
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, the rate-distortion theory of the Gray-Wyner lossy source coding system is investigated. For the case of jointly Gaussian distributed sources, we establish an expression for the rate-distortion function under the constraint of quadratic distortion. Using the proposed rate-distortion function, any corner point on the rate-distortion region can be conveniently calculated. We take Wyner's common information as an example and provide a general and simple method to solve this problem. Through the analysis of the rate-distortion function, the rate on each layer and covariance matrix of auxiliary random variables and the sources are also presented in this paper.