We consider the problem of authenticated communication over a discrete arbitrarily varying channel where the legitimate parties are unaware of whether or not an adversary is present. When there is no adversary, the channel state always takes a default value $s_0$. When the adversary is present, they may choose the channel state sequence based on a non-causal noisy view of the transmitted codewords and the encoding and decoding scheme. We require that the decoder output the correct message with a high probability when there is no adversary, and either output the correct message or reject the transmission when the adversary is present. Further, we allow the transmitter to employ private randomness during encoding that is known neither to the receiver nor the adversary. Our first result proves a dichotomy property for the capacity for this problem -- the capacity either equals zero or it equals the non-adversarial capacity of the channel. Next, we give a sufficient condition for the capacity for this problem to be positive even when the non-adversarial channel to the receiver is stochastically degraded with respect to the channel to the adversary. Our proofs rely on a connection to a standalone authentication problem, where the goal is to accept or reject a candidate message that is already available to the decoder. Finally, we give examples and compare our sufficient condition with other related conditions known in the literature
相關內容
Despite significant advancements in existing models, generating text descriptions from structured data input, known as data-to-text generation, remains a challenging task. In this paper, we propose a novel approach that goes beyond traditional one-shot generation methods by introducing a multi-step process consisting of generation, verification, and correction stages. Our approach, VCP(Verification and Correction Prompting), begins with the model generating an initial output. We then proceed to verify the correctness of different aspects of the generated text. The observations from the verification step are converted into a specialized error-indication prompt, which instructs the model to regenerate the output while considering the identified errors. To enhance the model's correction ability, we have developed a carefully designed training procedure. This procedure enables the model to incorporate feedback from the error-indication prompt, resulting in improved output generation. Through experimental results, we demonstrate that our approach effectively reduces slot error rates while maintaining the overall quality of the generated text.
We study distributed estimation and learning problems in a networked environment in which agents exchange information to estimate unknown statistical properties of random variables from their privately observed samples. By exchanging information about their private observations, the agents can collectively estimate the unknown quantities, but they also face privacy risks. The goal of our aggregation schemes is to combine the observed data efficiently over time and across the network, while accommodating the privacy needs of the agents and without any coordination beyond their local neighborhoods. Our algorithms enable the participating agents to estimate a complete sufficient statistic from private signals that are acquired offline or online over time, and to preserve the privacy of their signals and network neighborhoods. This is achieved through linear aggregation schemes with adjusted randomization schemes that add noise to the exchanged estimates subject to differential privacy (DP) constraints. In every case, we demonstrate the efficiency of our algorithms by proving convergence to the estimators of a hypothetical, omniscient observer that has central access to all of the signals. We also provide convergence rate analysis and finite-time performance guarantees and show that the noise that minimizes the convergence time to the best estimates is the Laplace noise, with parameters corresponding to each agent's sensitivity to their signal and network characteristics. Finally, to supplement and validate our theoretical results, we run experiments on real-world data from the US Power Grid Network and electric consumption data from German Households to estimate the average power consumption of power stations and households under all privacy regimes.
In this letter, we investigate the mutual information rate (MIR) achieved by an independent identically distributed (IID) Gaussian input on the intensity-driven signal transduction channel. Specifically, the asymptotic expression of the continuous-time MIR is given. Next, aiming at low computational complexity, we also deduce an approximately numerical solution for this MIR. Moreover, the corresponding lower and upper bounds that can be used to find the capacity-achieving input distribution parameters are derived in closed-form. Finally, simulation results show the accuracy of our analysis.
The lower bound on the decoding error probability for the optimal code given a signal-to-noise ratio and a code rate are investigated in this letter for the reconfigurable intelligent surface (RIS) communication system over a Rician fading channel at the short blocklength regime, which is the key characteristic of ultra-reliable low-latency communications (URLLC) to meet the need for strict adherence to quality of service (QoS) requirements. Sphere packing technique is used to derive our main results. The Wald sequential t-test lemma and the Gaussian-Chebyshev quadrature are the main tools to obtain the closed-form expression for the lower bound. Numerical results are provided to validate our results and demonstrate the tightness of our results compared to the Polyanskiy-Poor-Verdu (PPV) bound.
Estimating the output size of a join query is a fundamental yet longstanding problem in database query processing. Traditional cardinality estimators used by database systems can routinely underestimate the true join size by orders of magnitude, which leads to significant system performance penalty. Recently, size upper bounds have been proposed that are based on information inequalities and incorporate sizes and max-degrees from input relations, yet they grossly overestimate the true join size. This paper puts forward a general class of size bounds that are based on information inequalities involving Lp-norms on the degree sequences of the join columns. They generalise prior efforts and can be asymptotically tighter than the known bounds. We give two types of lower and upper bounds: some hold for all entropic vectors, while others hold for all polymatroids. Whereas the former are asymptotically tight but possibly not computable, the latter are computable but not even asymptotically tight. In the case when all degree constraints are over a single variable then we call them "simple", and prove that the polymatroid and entropic bounds are equal, they are tight up to a query-dependent constant (which is stronger than asymptotically tight), are computable in exponential time in the size of the query, and that the worst case database instance that matches the bound has a simple structure called a "normal database".
We study a class of stochastic semilinear damped wave equations driven by additive Wiener noise. Owing to the damping term, under appropriate conditions on the nonlinearity, the solution admits a unique invariant distribution. We apply semi-discrete and fully-discrete methods in order to approximate this invariant distribution, using a spectral Galerkin method and an exponential Euler integrator for spatial and temporal discretization respectively. We prove that the considered numerical schemes also admit unique invariant distributions, and we prove error estimates between the approximate and exact invariant distributions, with identification of the orders of convergence. To the best of our knowledge this is the first result in the literature concerning numerical approximation of invariant distributions for stochastic damped wave equations.
We study the problem of certifying the robustness of Bayesian neural networks (BNNs) to adversarial input perturbations. Given a compact set of input points $T \subseteq \mathbb{R}^m$ and a set of output points $S \subseteq \mathbb{R}^n$, we define two notions of robustness for BNNs in an adversarial setting: probabilistic robustness and decision robustness. Probabilistic robustness is the probability that for all points in $T$ the output of a BNN sampled from the posterior is in $S$. On the other hand, decision robustness considers the optimal decision of a BNN and checks if for all points in $T$ the optimal decision of the BNN for a given loss function lies within the output set $S$. Although exact computation of these robustness properties is challenging due to the probabilistic and non-convex nature of BNNs, we present a unified computational framework for efficiently and formally bounding them. Our approach is based on weight interval sampling, integration, and bound propagation techniques, and can be applied to BNNs with a large number of parameters, and independently of the (approximate) inference method employed to train the BNN. We evaluate the effectiveness of our methods on various regression and classification tasks, including an industrial regression benchmark, MNIST, traffic sign recognition, and airborne collision avoidance, and demonstrate that our approach enables certification of robustness and uncertainty of BNN predictions.
This paper considers a variant of zero-sum matrix games where at each timestep the row player chooses row $i$, the column player chooses column $j$, and the row player receives a noisy reward with mean $A_{i,j}$. The objective of the row player is to accumulate as much reward as possible, even against an adversarial column player. If the row player uses the EXP3 strategy, an algorithm known for obtaining $\sqrt{T}$ regret against an arbitrary sequence of rewards, it is immediate that the row player also achieves $\sqrt{T}$ regret relative to the Nash equilibrium in this game setting. However, partly motivated by the fact that the EXP3 strategy is myopic to the structure of the game, O'Donoghue et al. (2021) proposed a UCB-style algorithm that leverages the game structure and demonstrated that this algorithm greatly outperforms EXP3 empirically. While they showed that this UCB-style algorithm achieved $\sqrt{T}$ regret, in this paper we ask if there exists an algorithm that provably achieves $\text{polylog}(T)$ regret against any adversary, analogous to results from stochastic bandits. We propose a novel algorithm that answers this question in the affirmative for the simple $2 \times 2$ setting, providing the first instance-dependent guarantees for games in the regret setting. Our algorithm overcomes two major hurdles: 1) obtaining logarithmic regret even though the Nash equilibrium is estimable only at a $1/\sqrt{T}$ rate, and 2) designing row-player strategies that guarantee that either the adversary provides information about the Nash equilibrium, or the row player incurs negative regret. Moreover, in the full information case we address the general $n \times m$ case where the first hurdle is still relevant. Finally, we show that EXP3 and the UCB-based algorithm necessarily cannot perform better than $\sqrt{T}$.
This paper is concerned with the optimal allocation of detection resources (sensors) to mitigate multi-stage attacks, in the presence of the defender's uncertainty in the attacker's intention. We model the attack planning problem using a Markov decision process and characterize the uncertainty in the attacker's intention using a finite set of reward functions -- each reward represents a type of the attacker. Based on this modeling framework, we employ the paradigm of the worst-case absolute regret minimization from robust game theory and develop mixed-integer linear program (MILP) formulations for solving the worst-case regret minimizing sensor allocation strategies for two classes of attack-defend interactions: one where the defender and attacker engage in a zero-sum game, and another where they engage in a non-zero-sum game. We demonstrate the effectiveness of our framework using a stochastic gridworld example.
While existing work in robust deep learning has focused on small pixel-level $\ell_p$ norm-based perturbations, this may not account for perturbations encountered in several real world settings. In many such cases although test data might not be available, broad specifications about the types of perturbations (such as an unknown degree of rotation) may be known. We consider a setup where robustness is expected over an unseen test domain that is not i.i.d. but deviates from the training domain. While this deviation may not be exactly known, its broad characterization is specified a priori, in terms of attributes. We propose an adversarial training approach which learns to generate new samples so as to maximize exposure of the classifier to the attributes-space, without having access to the data from the test domain. Our adversarial training solves a min-max optimization problem, with the inner maximization generating adversarial perturbations, and the outer minimization finding model parameters by optimizing the loss on adversarial perturbations generated from the inner maximization. We demonstrate the applicability of our approach on three types of naturally occurring perturbations -- object-related shifts, geometric transformations, and common image corruptions. Our approach enables deep neural networks to be robust against a wide range of naturally occurring perturbations. We demonstrate the usefulness of the proposed approach by showing the robustness gains of deep neural networks trained using our adversarial training on MNIST, CIFAR-10, and a new variant of the CLEVR dataset.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191