OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Price Discrimination for Randomized Mechanisms
Venue: arXiv cs.GT 2023
Year: 2023

We study the power of price discrimination via an intermediary in bilateral trade, when there is a revenue-maximizing seller selling an item to a buyer with a private value drawn from a prior. Between the seller and the buyer, there is an intermediary that can segment the market by releasing information about the true values to the seller. This is termed signaling, and enables the seller to price discriminate. In this setting, Bergemann et al. showed the existence of a signaling scheme that simultaneously raises the optimal consumer surplus, guarantees the item always sells, and ensures the seller's revenue does not increase. Our work extends the positive result of Bergemann et al. to settings where the type space is larger, and where optimal auction is randomized, possibly over a menu that can be exponentially large. In particular, we consider two settings motivated by budgets: The first is when there is a publicly known budget constraint on the price the seller can charge and the second is the FedEx problem where the buyer has a private deadline or service level (equivalently, a private budget that is guaranteed to never bind). For both settings, we present a novel signaling scheme and its analysis via a continuous construction process that recreates the optimal consumer surplus guarantee of Bergemann et al. The settings we consider are special cases of the more general problem where the buyer has a private budget constraint in addition to a private value. We finally show that our positive results do not extend to this more general setting. Here, we show that any efficient signaling scheme necessarily transfers almost all the surplus to the seller instead of the buyer.
Reaching Agreement Among $k$ out of $n$ Processes
Venue: arXiv cs.DC 2023
Year: 2023

In agreement problems, each process has an input value and must choose a decision (output) value. Given $n\geq 2$ processes and $m \geq 2$ possible different input values, we want to design an agreement algorithm that enables as many processes as possible to decide on the (same) input value of one of the processes, in the presence of $t$ crash failures. Without communication, when each process simply decides on its input value, at least $\lceil (n-t)/m \rceil$ of the processes are guaranteed to always decide on the same value. Can we do better with communication? For some cases, for example when $m=2$, even in the presence of a single crash failure, the answer is negative in a deterministic asynchronous system where communication is either by using atomic read/write registers or by sending and receiving messages. The answer is positive in other cases.
Predictive Compliance Monitoring in Process-Aware Information Systems: State of the Art, Functionalities, Research Directions
Venue: arXiv cs.SE 2023
Year: 2023

Business process compliance is a key area of business process management and aims at ensuring that processes obey to compliance constraints such as regulatory constraints or business rules imposed on them. Process compliance can be checked during process design time based on verification of process models and at runtime based on monitoring the compliance states of running process instances. For existing compliance monitoring approaches it remains unclear whether and how compliance violations can be predicted, although predictions are crucial in order to prepare and take countermeasures in time. This work, hence, analyzes existing literature from compliance monitoring as well as predictive process monitoring and provides an updated framework of compliance monitoring functionalities. Moreover, it raises the vision of a comprehensive predictive compliance monitoring system that integrates existing predicate prediction approaches with the idea of employing PPM with different prediction goals such as next activity or remaining time for prediction and subsequent mapping of the prediction results onto the given set of compliance constraints (PCM). For each compliance monitoring functionality we elicit PCM system requirements and assess their coverage by existing approaches. Based on the assessment, open challenges and research directions realizing a comprehensive PCM system are elaborated.
Generation of non-stationary stochastic fields using Generative Adversarial Networks
Venue: arXiv cs.LG 2023
Year: 2023

In the context of generating geological facies conditioned on observed data, samples corresponding to all possible conditions are not generally available in the training set and hence the generation of these realizations depends primary on the generalization capability of the trained generative model. The problem becomes more complex when applied on non-stationary fields. In this work, we investigate the problem of using Generative Adversarial Networks (GANs) models to generate non-stationary geological channelized patterns and examine the models generalization capability at new spatial modes that were never seen in the given training set. The developed training method based on spatial-conditioning allowed for effective learning of the correlation between the spatial conditions (i.e. non-stationary maps) and the realizations implicitly without using additional loss terms or solving optimization problems for every new given data after training. In addition, our models can be trained on 2D and 3D samples. The results on real and artificial datasets show that we were able to generate geologically-plausible realizations beyond the training samples and with a strong correlation with the target maps.
BiAIT*: Symmetrical Bidirectional Optimal Path Planning with Adaptive Heuristic
Venue: arXiv cs.RO 2023
Year: 2023

Adaptively Informed Trees (AIT*) is an algorithm that uses the problem-specific heuristic to avoid unnecessary searches, which significantly improves its performance, especially when collision checking is expensive. However, the heuristic estimation in AIT* consumes lots of computational resources, and its asymmetric bidirectional searching strategy cannot fully exploit the potential of the bidirectional method. In this article, we propose an extension of AIT* called BiAIT*. Unlike AIT*, BiAIT* uses symmetrical bidirectional search for both the heuristic and space searching. The proposed method allows BiAIT* to find the initial solution faster than AIT*, and update the heuristic with less computation when a collision occurs. We evaluated the performance of BiAIT* through simulations and experiments, and the results show that BiAIT* can find the solution faster than state-of-the-art methods. We also analyze the reasons for the different performances between BiAIT* and AIT*. Furthermore, we discuss two simple but effective modifications to fully exploit the potential of the adaptively heuristic method.
Learning to Reorient Objects with Stable Placements Afforded by Extrinsic Supports
Venue: arXiv cs.RO 2023
Year: 2023

Reorienting objects by using supports is a practical yet challenging manipulation task. Owing to the intricate geometry of objects and the constrained feasible motions of the robot, multiple manipulation steps are required for object reorientation. In this work, we propose a pipeline for predicting various object placements from point clouds. This pipeline comprises three stages: a pose generation stage, followed by a pose refinement stage, and culminating in a placement classification stage. We also propose an algorithm to construct manipulation graphs based on point clouds. Feasible manipulation sequences are determined for the robot to transfer object placements. Both simulated and real-world experiments demonstrate that our approach is effective. The simulation results underscore our pipeline's capacity to generalize to novel objects in random start poses. Our predicted placements exhibit a 20% enhancement in accuracy compared to the state-of-the-art baseline. Furthermore, the robot finds feasible sequential steps in the manipulation graphs constructed by our algorithm to accomplish object reorientation manipulation.
Multi-scale Attention Flow for Probabilistic Time Series Forecasting
Venue: arXiv cs.LG 2023
Year: 2023

The probability prediction of multivariate time series is a notoriously challenging but practical task. On the one hand, the challenge is how to effectively capture the cross-series correlations between interacting time series, to achieve accurate distribution modeling. On the other hand, we should consider how to capture the contextual information within time series more accurately to model multivariate temporal dynamics of time series. In this work, we proposed a novel non-autoregressive deep learning model, called Multi-scale Attention Normalizing Flow(MANF), where we integrate multi-scale attention and relative position information and the multivariate data distribution is represented by the conditioned normalizing flow. Additionally, compared with autoregressive modeling methods, our model avoids the influence of cumulative error and does not increase the time complexity. Extensive experiments demonstrate that our model achieves state-of-the-art performance on many popular multivariate datasets.
Compositional Modeling with Stock and Flow Diagrams
Venue: arXiv cs.LO 2023
Year: 2023

Stock and flow diagrams are widely used in epidemiology to model the dynamics of populations. Although tools already exist for building these diagrams and simulating the systems they describe, we have created a new package called StockFlow, part of the AlgebraicJulia ecosystem, which uses ideas from category theory to overcome notable limitations of existing software. Compositionality is provided by the theory of decorated cospans: stock and flow diagrams can be composed to form larger ones in an intuitive way formalized by the operad of undirected wiring diagrams. Our approach also cleanly separates the syntax of stock and flow diagrams from the semantics they can be assigned. We consider semantics in ordinary differential equations, although others are possible. As an example, we explain code in StockFlow that implements a simplified version of a COVID-19 model used in Canada.
Dynamic Optimization Fabrics for Motion Generation
Venue: arXiv cs.RO 2023
Year: 2023

Optimization fabrics are a geometric approach to real-time local motion generation, where motions are designed by the composition of several differential equations that exhibit a desired motion behavior. We generalize this framework to dynamic scenarios and non-holonomic robots and prove that fundamental properties can be conserved. We show that convergence to desired trajectories and avoidance of moving obstacles can be guaranteed using simple construction rules of the components. Additionally, we present the first quantitative comparisons between optimization fabrics and model predictive control and show that optimization fabrics can generate similar trajectories with better scalability, and thus, much higher replanning frequency (up to 500 Hz with a 7 degrees of freedom robotic arm). Finally, we present empirical results on several robots, including a non-holonomic mobile manipulator with 10 degrees of freedom and avoidance of a moving human, supporting the theoretical findings.
Dynamic Recognition of Speakers for Consent Management by Contrastive Embedding Replay
Venue: arXiv cs.SD 2023
Year: 2023

Voice assistants overhear conversations and a consent management mechanism is required. Consent management can be implemented using speaker recognition. Users that do not give consent enrol their voice and all their further recordings are discarded. Building speaker recognition-based consent management is challenging as dynamic registration, removal, and re-registration of speakers must be efficiently handled. This work proposes a consent management system addressing the aforementioned challenges. A contrastive based training is applied to learn the underlying speaker equivariance inductive bias. The contrastive features for buckets of speakers are trained a few steps into each iteration and act as replay buffers. These features are progressively selected using a multi-strided random sampler for classification. Moreover, new methods for dynamic registration using a portion of old utterances, removal, and re-registration of speakers are proposed. The results verify memory efficiency and dynamic capabilities of the proposed methods and outperform the existing approach from the literature.
New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
Venue: arXiv cs.DS 2023
Year: 2023

We prove new lower bounds for statistical estimation tasks under the constraint of $(\varepsilon, δ)$-differential privacy. First, we provide tight lower bounds for private covariance estimation of Gaussian distributions. We show that estimating the covariance matrix in Frobenius norm requires $Ω(d^2)$ samples, and in spectral norm requires $Ω(d^{3/2})$ samples, both matching upper bounds up to logarithmic factors. The latter bound verifies the existence of a conjectured statistical gap between the private and the non-private sample complexities for spectral estimation of Gaussian covariances. We prove these bounds via our main technical contribution, a broad generalization of the fingerprinting method to exponential families. Additionally, using the private Assouad method of Acharya, Sun, and Zhang, we show a tight $Ω(d/(α^2 \varepsilon))$ lower bound for estimating the mean of a distribution with bounded covariance to $α$-error in $\ell_2$-distance. Prior known lower bounds for all these problems were either polynomially weaker or held under the stricter condition of $(\varepsilon, 0)$-differential privacy.
Cordial Miners: Fast and Efficient Consensus for Every Eventuality
Venue: arXiv cs.DC 2023
Year: 2023

Cordial Miners are a family of efficient Byzantine Atomic Broadcast protocols, with instances for asynchrony and eventual synchrony. They improve the latency of state-of-the-art DAG-based protocols by almost 2X and achieve optimal good-case complexity of O(n) by forgoing Reliable Broadcast as a building block. Rather, Cordial Miners use the blocklace -- a partially-ordered counterpart of the totally-ordered blockchain data structure -- to implement the three algorithmic components of consensus: Dissemination, equivocation-exclusion, and ordering.
PromptDA: Label-guided Data Augmentation for Prompt-based Few-shot Learners
Venue: arXiv cs.CL 2023
Year: 2023

Recent advances in large pre-trained language models (PLMs) lead to impressive gains in natural language understanding (NLU) tasks with task-specific fine-tuning. However, directly fine-tuning PLMs heavily relies on sufficient labeled training instances, which are usually hard to obtain. Prompt-based tuning on PLMs has shown to be powerful for various downstream few-shot tasks. Existing works studying prompt-based tuning for few-shot NLU tasks mainly focus on deriving proper label words with a verbalizer or generating prompt templates to elicit semantics from PLMs. In addition, conventional data augmentation strategies such as synonym substitution, though widely adopted in low-resource scenarios, only bring marginal improvements for prompt-based few-shot learning. Thus, an important research question arises: how to design effective data augmentation methods for prompt-based few-shot tuning? To this end, considering the label semantics are essential in prompt-based tuning, we propose a novel label-guided data augmentation framework PromptDA, which exploits the enriched label semantic information for data augmentation. Extensive experiment results on few-shot text classification tasks demonstrate the superior performance of the proposed framework by effectively leveraging label semantics and data augmentation for natural language understanding. Our code is available at https://github.com/canyuchen/PromptDA.
Accelerated Training of Physics-Informed Neural Networks (PINNs) using Meshless Discretizations
Venue: arXiv cs.LG 2023
Year: 2023

We present a new technique for the accelerated training of physics-informed neural networks (PINNs): discretely-trained PINNs (DT-PINNs). The repeated computation of partial derivative terms in the PINN loss functions via automatic differentiation during training is known to be computationally expensive, especially for higher-order derivatives. DT-PINNs are trained by replacing these exact spatial derivatives with high-order accurate numerical discretizations computed using meshless radial basis function-finite differences (RBF-FD) and applied via sparse-matrix vector multiplication. The use of RBF-FD allows for DT-PINNs to be trained even on point cloud samples placed on irregular domain geometries. Additionally, though traditional PINNs (vanilla-PINNs) are typically stored and trained in 32-bit floating-point (fp32) on the GPU, we show that for DT-PINNs, using fp64 on the GPU leads to significantly faster training times than fp32 vanilla-PINNs with comparable accuracy. We demonstrate the efficiency and accuracy of DT-PINNs via a series of experiments. First, we explore the effect of network depth on both numerical and automatic differentiation of a neural network with random weights and show that RBF-FD approximations of third-order accuracy and above are more efficient while being sufficiently accurate. We then compare the DT-PINNs to vanilla-PINNs on both linear and nonlinear Poisson equations and show that DT-PINNs achieve similar losses with 2-4x faster training times on a consumer GPU. Finally, we also demonstrate that similar results can be obtained for the PINN solution to the heat equation (a space-time problem) by discretizing the spatial derivatives using RBF-FD and using automatic differentiation for the temporal derivative. Our results show that fp64 DT-PINNs offer a superior cost-accuracy profile to fp32 vanilla-PINNs.
Neural Network Architecture Beyond Width and Depth
Venue: arXiv cs.LG 2023
Year: 2023

This paper proposes a new neural network architecture by introducing an additional dimension called height beyond width and depth. Neural network architectures with height, width, and depth as hyper-parameters are called three-dimensional architectures. It is shown that neural networks with three-dimensional architectures are significantly more expressive than the ones with two-dimensional architectures (those with only width and depth as hyper-parameters), e.g., standard fully connected networks. The new network architecture is constructed recursively via a nested structure, and hence we call a network with the new architecture nested network (NestNet). A NestNet of height $s$ is built with each hidden neuron activated by a NestNet of height $\le s-1$. When $s=1$, a NestNet degenerates to a standard network with a two-dimensional architecture. It is proved by construction that height-$s$ ReLU NestNets with $\mathcal{O}(n)$ parameters can approximate $1$-Lipschitz continuous functions on $[0,1]^d$ with an error $\mathcal{O}(n^{-(s+1)/d})$, while the optimal approximation error of standard ReLU networks with $\mathcal{O}(n)$ parameters is $\mathcal{O}(n^{-2/d})$. Furthermore, such a result is extended to generic continuous functions on $[0,1]^d$ with the approximation error characterized by the modulus of continuity. Finally, we use numerical experimentation to show the advantages of the super-approximation power of ReLU NestNets.
AIGenC: An AI generalisation model via creativity
Venue: arXiv cs.AI 2023
Year: 2023

Inspired by cognitive theories of creativity, this paper introduces a computational model (AIGenC) that lays down the necessary components to enable artificial agents to learn, use and generate transferable representations. Unlike machine representation learning, which relies exclusively on raw sensory data, biological representations incorporate relational and associative information that embeds rich and structured concept spaces. The AIGenC model poses a hierarchical graph architecture with various levels and types of representations procured by different components. The first component, Concept Processing, extracts objects and affordances from sensory input and encodes them into a concept space. The resulting representations are stored in a dual memory system and enriched with goal-directed and temporal information acquired through reinforcement learning, creating a higher-level of abstraction. Two additional components work in parallel to detect and recover relevant concepts and create new ones, respectively, in a process akin to cognitive Reflective Reasoning and Blending. The Reflective Reasoning unit detects and recovers from memory concepts relevant to the task by means of a matching process that calculates a similarity value between the current state and memory graph structures. Once the matching interaction ends, rewards and temporal information are added to the graph, building further abstractions. If the reflective reasoning processing fails to offer a suitable solution, a blending operation comes into place, creating new concepts by combining past information. We discuss the model's capability to yield better out-of-distribution generalisation in artificial agents, thus advancing toward Artificial General Intelligence.
FedAdapter: Efficient Federated Learning for Modern NLP
Venue: arXiv cs.LG 2023
Year: 2023

Transformer-based pre-trained models have revolutionized NLP for superior performance and generality. Fine-tuning pre-trained models for downstream tasks often requires private data, for which federated learning is the de-facto approach (i.e., FedNLP). However, our measurements show that FedNLP is prohibitively slow due to the large model sizes and the resultant high network/computation cost. Towards practical FedNLP, we identify as the key building blocks adapters, small bottleneck modules inserted at a variety of model layers. A key challenge is to properly configure the depth and width of adapters, to which the training speed and efficiency is highly sensitive. No silver-bullet configuration exists: the optimal choice varies across downstream NLP tasks, desired model accuracy, and mobile resources. To automate adapter configuration, we propose FedAdapter, a framework that enhances the existing FedNLP with two novel designs. First, FedAdapter progressively upgrades the adapter configuration throughout a training session; the principle is to quickly learn shallow knowledge by only training fewer and smaller adapters at the model's top layers, and incrementally learn deep knowledge by incorporating deeper and larger adapters. Second, FedAdapter continuously profiles future adapter configurations by allocating participant devices to trial groups. Extensive experiments show that FedAdapter can reduce FedNLP's model convergence delay to no more than several hours, which is up to 155.5$\times$ faster compared to vanilla FedNLP and 48$\times$ faster compared to strong baselines.
Bayesian Active Learning with Fully Bayesian Gaussian Processes
Venue: arXiv cs.LG 2023
Year: 2023

The bias-variance trade-off is a well-known problem in machine learning that only gets more pronounced the less available data there is. In active learning, where labeled data is scarce or difficult to obtain, neglecting this trade-off can cause inefficient and non-optimal querying, leading to unnecessary data labeling. In this paper, we focus on active learning with Gaussian Processes (GPs). For the GP, the bias-variance trade-off is made by optimization of the two hyperparameters: the length scale and noise-term. Considering that the optimal mode of the joint posterior of the hyperparameters is equivalent to the optimal bias-variance trade-off, we approximate this joint posterior and utilize it to design two new acquisition functions. The first one is a Bayesian variant of Query-by-Committee (B-QBC), and the second is an extension that explicitly minimizes the predictive variance through a Query by Mixture of Gaussian Processes (QB-MGP) formulation. Across six simulators, we empirically show that B-QBC, on average, achieves the best marginal likelihood, whereas QB-MGP achieves the best predictive performance. We show that incorporating the bias-variance trade-off in the acquisition functions mitigates unnecessary and expensive data labeling.