We simulate behaviour of independent reinforcement learning algorithms playing the Crawford and Sobel (1982) game of strategic information transmission. We show that a sender and a receiver training together converge to strategies approximating the ex-ante optimal equilibrium of the game. Communication occurs to the largest extent predicted by Nash equilibrium. The conclusion is robust to alternative specifications of the learning hyperparameters and of the game. We discuss implications for theories of equilibrium selection in information transmission games, for work on emerging communication among algorithms in computer science, and for the economics of collusions in markets populated by artificially intelligent agents.
Hybrid quantum-classical algorithms appear to be the most promising approach for near-term quantum applications. An important bottleneck is the classical optimization loop, where the multiple local minima and the emergence of barren plateaux make these approaches less appealing. To improve the optimization the Quantum Natural Gradient (QNG) method [Quantum 4, 269 (2020)] was introduced - a method that uses information about the local geometry of the quantum state-space. While the QNG-based optimization is promising, in each step it requires more quantum resources, since to compute the QNG one requires $O(m^2)$ quantum state preparations, where $m$ is the number of parameters in the parameterized circuit. In this work we propose two methods that reduce the resources/state preparations required for QNG, while keeping the advantages and performance of the QNG-based optimization. Specifically, we first introduce the Random Natural Gradient (RNG) that uses random measurements and the classical Fisher information matrix (as opposed to the quantum Fisher information used in QNG). The essential quantum resources reduce to linear $O(m)$ and thus offer a quadratic "speed-up", while in our numerical simulations it matches QNG in terms of accuracy. We give some theoretical arguments for RNG and then benchmark the method with the QNG on both classical and quantum problems. Secondly, inspired by stochastic-coordinate methods, we propose a novel approximation to the QNG which we call Stochastic-Coordinate Quantum Natural Gradient that optimizes only a small (randomly sampled) fraction of the total parameters at each iteration. This method also performs equally well in our benchmarks, while it uses fewer resources than the QNG.
Profile-guided optimizations rely on profile data for directing compilers to generate optimized code. To achieve the maximum performance boost, profile data needs to be collected on the same version of the binary that is being optimized. In practice however, there is typically a gap between the profile collection and the release, which makes a portion of the profile invalid for optimizations. This phenomenon is known as profile staleness, and it is a serious practical problem for data-center workloads both for compilers and binary optimizers. In this paper we thoroughly study the staleness problem and propose the first practical solution for utilizing profiles collected on binaries built from several revisions behind the release. Our algorithm is developed and implemented in a mainstream open-source post-link optimizer, BOLT. An extensive evaluation on a variety of standalone benchmarks and production services indicates that the new method recovers up to $0.8$ of the maximum BOLT benefit, even when most of the input profile data is stale and would have been discarded by the optimizer otherwise.
We give complete presentations for the dagger-compact props of affine Lagrangian and coisotropic relations over an arbitrary field. This provides a unified family of graphical languages for both affinely constrained classical mechanical systems, as well as odd-prime-dimensional stabiliser quantum circuits. To this end, we present affine Lagrangian relations by a particular class of undirected coloured graphs. In order to reason about composite systems, we introduce a powerful scalable notation where the vertices of these graphs are themselves coloured by graphs. In the setting of stabiliser quantum mechanics, this scalable notation gives an extremely concise description of graph states, which can be composed via ``phased spider fusion.'' Likewise, in the classical mechanical setting of electrical circuits, we show that impedance matrices for reciprocal networks are presented in essentially the same way.
Publicly-verifiable quantum money has been a central focus in quantum cryptography. To date, no constructions for this primitive exist based on standard assumptions. In this study, we propose an alternative notion which we refer to as $\textit{quantum cheques}$ (QCs). A quantum cheque can be verified using a public-key but only by a single user. Specifically, the payer signs the quantum cheque for a particular recipient using their ID, and the recipient can validate it without the assistance of the bank, ensuring that the payer cannot assign the same cheque to another user with a different ID. Unlike quantum money, QCs only necessitate quantum communication when a cheque is issued by the bank, meaning all payments and deposits are entirely classical! We demonstrate how to construct QCs based on the well-studied learning-with-errors (LWE) assumption. In the process, we build two novel primitives which are of independent interest. Firstly, we construct $\textit{signatures with publicly-verifiable deletion}$ under LWE. This primitive enables the signing of a message $m$ such that the recipient can produce a classical string that publicly proves the inability to reproduce a signature of $m$. We then demonstrate how this primitive can be used to construct $\textit{2-message signature tokens}$. This primitive enables the production of a token that can be used to sign a single bit and then self-destructs. Finally, we show that 2-message signature tokens can be used to construct QCs.
This study explores a new mathematical operator, symbolized as $\cupplus$, for information aggregation, aimed at enhancing traditional methods by directly amalgamating probability distributions. This operator facilitates the combination of probability densities, contributing a nuanced approach to probabilistic analysis. We apply this operator to a personalized incentive scenario, illustrating its potential in a practical context. The paper's primary contribution lies in introducing this operator and elucidating its elegant mathematical properties. This exploratory work marks a step forward in the field of information fusion and probabilistic reasoning.
Differential privacy has emerged as an significant cornerstone in the realm of scientific hypothesis testing utilizing confidential data. In reporting scientific discoveries, Bayesian tests are widely adopted since they effectively circumnavigate the key criticisms of P-values, namely, lack of interpretability and inability to quantify evidence in support of the competing hypotheses. We present a novel differentially private Bayesian hypotheses testing framework that arise naturally under a principled data generative mechanism, inherently maintaining the interpretability of the resulting inferences. Furthermore, by focusing on differentially private Bayes factors based on widely used test statistics, we circumvent the need to model the complete data generative mechanism and ensure substantial computational benefits. We also provide a set of sufficient conditions to establish results on Bayes factor consistency under the proposed framework. The utility of the devised technology is showcased via several numerical experiments.
Interactive Natural Language Processing (iNLP) has emerged as a novel paradigm within the field of NLP, aimed at addressing limitations in existing frameworks while aligning with the ultimate goals of artificial intelligence. This paradigm considers language models as agents capable of observing, acting, and receiving feedback iteratively from external entities. Specifically, language models in this context can: (1) interact with humans for better understanding and addressing user needs, personalizing responses, aligning with human values, and improving the overall user experience; (2) interact with knowledge bases for enriching language representations with factual knowledge, enhancing the contextual relevance of responses, and dynamically leveraging external information to generate more accurate and informed responses; (3) interact with models and tools for effectively decomposing and addressing complex tasks, leveraging specialized expertise for specific subtasks, and fostering the simulation of social behaviors; and (4) interact with environments for learning grounded representations of language, and effectively tackling embodied tasks such as reasoning, planning, and decision-making in response to environmental observations. This paper offers a comprehensive survey of iNLP, starting by proposing a unified definition and framework of the concept. We then provide a systematic classification of iNLP, dissecting its various components, including interactive objects, interaction interfaces, and interaction methods. We proceed to delve into the evaluation methodologies used in the field, explore its diverse applications, scrutinize its ethical and safety issues, and discuss prospective research directions. This survey serves as an entry point for researchers who are interested in this rapidly evolving area and offers a broad view of the current landscape and future trajectory of iNLP.
Disentangled Representation Learning (DRL) aims to learn a model capable of identifying and disentangling the underlying factors hidden in the observable data in representation form. The process of separating underlying factors of variation into variables with semantic meaning benefits in learning explainable representations of data, which imitates the meaningful understanding process of humans when observing an object or relation. As a general learning strategy, DRL has demonstrated its power in improving the model explainability, controlability, robustness, as well as generalization capacity in a wide range of scenarios such as computer vision, natural language processing, data mining etc. In this article, we comprehensively review DRL from various aspects including motivations, definitions, methodologies, evaluations, applications and model designs. We discuss works on DRL based on two well-recognized definitions, i.e., Intuitive Definition and Group Theory Definition. We further categorize the methodologies for DRL into four groups, i.e., Traditional Statistical Approaches, Variational Auto-encoder Based Approaches, Generative Adversarial Networks Based Approaches, Hierarchical Approaches and Other Approaches. We also analyze principles to design different DRL models that may benefit different tasks in practical applications. Finally, we point out challenges in DRL as well as potential research directions deserving future investigations. We believe this work may provide insights for promoting the DRL research in the community.
Adversarial attack is a technique for deceiving Machine Learning (ML) models, which provides a way to evaluate the adversarial robustness. In practice, attack algorithms are artificially selected and tuned by human experts to break a ML system. However, manual selection of attackers tends to be sub-optimal, leading to a mistakenly assessment of model security. In this paper, a new procedure called Composite Adversarial Attack (CAA) is proposed for automatically searching the best combination of attack algorithms and their hyper-parameters from a candidate pool of \textbf{32 base attackers}. We design a search space where attack policy is represented as an attacking sequence, i.e., the output of the previous attacker is used as the initialization input for successors. Multi-objective NSGA-II genetic algorithm is adopted for finding the strongest attack policy with minimum complexity. The experimental result shows CAA beats 10 top attackers on 11 diverse defenses with less elapsed time (\textbf{6 $\times$ faster than AutoAttack}), and achieves the new state-of-the-art on $l_{\infty}$, $l_{2}$ and unrestricted adversarial attacks.
The dominant sequence transduction models are based on complex recurrent or convolutional neural networks in an encoder-decoder configuration. The best performing models also connect the encoder and decoder through an attention mechanism. We propose a new simple network architecture, the Transformer, based solely on attention mechanisms, dispensing with recurrence and convolutions entirely. Experiments on two machine translation tasks show these models to be superior in quality while being more parallelizable and requiring significantly less time to train. Our model achieves 28.4 BLEU on the WMT 2014 English-to-German translation task, improving over the existing best results, including ensembles by over 2 BLEU. On the WMT 2014 English-to-French translation task, our model establishes a new single-model state-of-the-art BLEU score of 41.8 after training for 3.5 days on eight GPUs, a small fraction of the training costs of the best models from the literature. We show that the Transformer generalizes well to other tasks by applying it successfully to English constituency parsing both with large and limited training data.