Search

We analytically derive from first physical principles the functional dependence of wireless channels on the RIS configuration for generic (i.e., potentially complex-scattering) RIS-parametrized radio environments. The wireless channel is a linear input-output relation that depends non-linearly on the RIS configuration because of two independent mechanisms: i) proximity-induced mutual coupling between close-by RIS elements; ii) reverberation-induced long-range coupling between all RIS elements. Mathematically, this "structural" non-linearity originates from the inversion of an "interaction" matrix that can be cast as the sum of an infinite Born series [for i)] or Born-like series [for ii)] whose $K$th term physically represents paths involving $K$ bounces between the RIS elements [for i)] or wireless entities [for ii)]. We identify the key physical parameters that determine whether these series can be truncated after the first and second term, respectively, as tacitly done in common cascaded models of RIS-parametrized wireless channels. Numerical results obtained with the physics-compliant PhysFad model and experimental results obtained with a RIS prototype in an anechoic (echo-free) chamber and rich-scattering reverberation chambers corroborate our analysis. Our findings raise doubts about the reliability of existing performance analysis and channel-estimation protocols for cases in which cascaded models poorly describe the physical reality., Comment: 30 pages, 5 figures, submitted to an IEEE Journal

Sparse stealth attack constructions that minimize the mutual information between the state variables and the observations are proposed. The attack construction is formulated as the design of a multivariate Gaussian distribution that aims to minimize the mutual information while limiting the Kullback-Leibler divergence between the distribution of the observations under attack and the distribution of the observations without attack. The sparsity constraint is incorporated as a support constraint of the attack distribution. Two heuristic greedy algorithms for the attack construction are proposed. The first algorithm assumes that the attack vector consists of independent entries, and therefore, requires no communication between different attacked locations. The second algorithm considers correlation between the attack vector entries which results in better attack performance at the expense of coordination between different locations. We numerically evaluate the performance of the proposed attack constructions on IEEE test systems and show that it is feasible to construct stealth attacks that generate significant disruption with a low number of compromised sensors., Comment: 10 pages, 6 figures, submited to IEEE Trans. Smart Grid

The effect of the relative entropy asymmetry is analyzed in the empirical risk minimization with relative entropy regularization (ERM-RER) problem. A novel regularization is introduced, coined Type-II regularization, that allows for solutions to the ERM-RER problem with a support that extends outside the support of the reference measure. The solution to the new ERM-RER Type-II problem is analytically characterized in terms of the Radon-Nikodym derivative of the reference measure with respect to the solution. The analysis of the solution unveils the following properties of relative entropy when it acts as a regularizer in the ERM-RER problem: i) relative entropy forces the support of the Type-II solution to collapse into the support of the reference measure, which introduces a strong inductive bias that dominates the evidence provided by the training data; ii) Type-II regularization is equivalent to classical relative entropy regularization with an appropriate transformation of the empirical risk function. Closed-form expressions of the expected empirical risk as a function of the regularization parameters are provided., To appear in the proceedings of the International Symposium on Information Theory 2023

This report considers different pricing models for a platform based rental system, such as Airbnb. A linear model is assumed for the demand response to price, and existence and uniqueness conditions for Nash equilibria are obtained. The Stackelberg equilibrium prices for the game are also obtained, and an iterative scheme is provided, which converges to the Nash equilibrium. Different cooperative pricing schemes are studied, and splitting of revenues based on the Shapley value is discussed. It is shown that a division of revenue based on the Shapley value gives a revenue to the platform proportional to its control of the market. The demand response function is modified to include user response to quality of service. It is shown that when the cost to provide quality of service is low, both renter and the platform will agree to maximize the quality of service. However, if this cost is high, they may not always be able to agree on what quality of service to provide.; Cet article examine différents modèles de tarification pour un système de location basé sur une plateforme, comme Airbnb. Un modèle linéaire est supposé pour la réponse de la demande au prix, et des conditions d’existence et d’unicité pour les équilibres de Nash sont obtenues. Les prix d’équilibre de Stackelberg pour le jeu sont également obtenus, et un schéma itératif est fourni, qui converge vers l’équilibre de Nash. Différents systèmes de tarification coopérative sont étudiés et la répartition des revenus basée sur la valeur de Shapley est discutée. Il est montré qu’une répartition des revenus basée sur la valeur de Shapley donne un revenu à la plateforme proportionnel à son contrôle du marché. La fonction de réponse à la demande est modifiée pour inclure la réponse de l’utilisateur à la qualité de service. Il est démontré que lorsque le coût de la qualité de service est faible, le locataire et la plateforme s’accordent pour maximiser la qualité de service. Cependant, si ce coût est élevé, ils ne peuvent pas toujours s’entendre sur la qualité de service à fournir.

The dependence on training data of the Gibbs algorithm (GA) is analytically characterized. By adopting the expected empirical risk as the performance metric, the sensitivity of the GA is obtained in closed form. In this case, sensitivity is the performance difference with respect to an arbitrary alternative algorithm. This description enables the development of explicit expressions involving the training errors and test errors of GAs trained with different datasets. Using these tools, dataset aggregation is studied and different figures of merit to evaluate the generalization capabilities of GAs are introduced. For particular sizes of such datasets and parameters of the GAs, a connection between Jeffrey's divergence, training and test errors is established., In Proc. IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan, Jun., 2023. arXiv admin note: text overlap with arXiv:2211.06617

International audience; This paper considers different pricing models for a platform based rental system, such as Airbnb. A linear model is assumed for the demand response to price, and existence and uniqueness conditions for Nash equilibria are obtained. The Stackelberg equilibrium prices for the game are also obtained, and an iterative scheme is provided, which converges to the Nash equilibrium. Different cooperative pricing schemes are studied, and splitting of revenues based on the Shapley value is discussed. It is shown that a division of revenue based on the Shapley value gives a revenue to the platform proportional to its control of the market. The demand response function is modified to include user response to quality of service. It is shown that when the cost to provide quality of service is low, both renter and the platform will agree to maximize the quality of service. However, if this cost is high, they may not always be able to agree on what quality of service to provide.

The effect of the relative entropy asymmetry is analyzed in the empirical risk minimization with relative entropy regularization (ERM-RER) problem. A novel regularization is introduced, coined Type-II regularization, that allows for solutions to the ERM-RER problem with a support that extends outside the support of the reference measure. The solution to the new ERM- RER Type-II problem is analytically characterized in terms of the Radon-Nikodym derivative of the reference measure with respect to the solution. The analysis of the solution unveils the following properties of relative entropy when it acts as a regularizer in the ERM-RER problem: (a) relative entropy forces the support of the Type-II solution to collapse into the support of the reference measure, which introduces a strong inductive bias that dominates the evidence provided by the training data; (b) Type-II regularization is equivalent to classical relative entropy regularization with an appropriate transformation of the empirical risk function. Closed-form expressions of the expected empirical risk as a function of the regularization parameters are provided.; L’effet de l’asymétrie de l’entropie relative est analysé dans leproblème de la minimisation du risque empirique avec régularisation par entropierelative (MRE-RER). Une nouvelle régularisation est introduite, appeléerégularisation de type-II, qui permet la recherche des solutions au problème dela MRE-RER avec un support qui s’étend en dehors du support de la mesurede référence. La solution au nouveau problème de la MRE-RER Type-II estcaractérisée analytiquement en termes de la dérivée de Radon-Nikodym de lamesure de référence par rapport à la solution. L’analyse de la solution dévoilecertaines propriétés de l’entropie relative lorsqu’elle agit comme régularisateurdu problème de la MRE-RER : (a) l’entropie relative force le support de lasolution de type-II à s’étaler sur tout le support de la mesure de référence, cequi introduit un fort biais inductif qui domine l’évidence fournie par les donnéesd’entraînement ; (b) La régularisation de type-II est équivalente à la régularisationd’entropie relative classique avec une transformation appropriée de lafonction du risque empirique. Enfin, une expression sous forme explicite de lavaleur espérée du risque empirique en fonction des paramètres de régularisationest présentée.

In this report, 2 × 2 zero-sum games are studied under the following assumptions: (1) One of the players (the leader) commits to choose its actions by sampling a given probability measure (strategy); (2) The leader announces its action, which is observed by its opponent (the follower) through a binary channel; and (3) the follower chooses its strategy based on the knowledge of the leader’s strategy and the noisy observation of the leader’s action. Under these conditions, the equilibrium is shown to always exist. Interestingly, even subject to noise, observing the actions of the leader is shown to be either beneficial or immaterial for the follower. More specifically, the payoff at the equilibrium of this game is upper bounded by the payoff at the Stackelberg equilibrium (SE) in pure strategies; and lower bounded by the payoff at the Nash equilibrium, which is equivalent to the SE in mixed strategies. Finally, necessary and sufficient conditions for observing the payoff at equilibrium to be equal to its lower bound are presented. Sufficient conditions for the payoff at equilibrium to be equal to its upper bound are also presented.; Dans ce rapport, les jeux à somme nulle 2 × 2 sont étudiés sous les hypothèses suivantes : (1) L’un des joueurs (le meneur) s’engage à choisir ses actions en échantillonnant une mesure de probabilité donnée (stratégie) ; (2) Le meneur annonce son action, qui est observée par son adversaire (le suiveur) à travers un canal binaire ; et (3) le suiveur choisit sa stratégie en fonction de la connaissance de la stratégie du meneur et de l’observation bruitée de l’action du meneur. Dans ces conditions, on montre que l’équilibre existe toujours. Fait intéressant, même sujette au bruit, l’observation des actions du leader s’avère soit bénéfique, soit immatérielle pour le suiveur. Plus précisément, la récompense à l’équilibre de ce jeu est majorée par la récompense à l’équilibre de Stackelberg (SE) en stratégies pures, et minorée par la récompense à l’équilibre de Nash, qui équivaut au SE en stratégies mixtes. Enfin, les conditions nécessaires et suffisantes pour observer que la récompense à l’équilibre est égale à sa borne inférieure sont présentées. Les conditions suffisantes pour observer que la récompense à l’équilibre est égale à sa borne supérieure sont aussi présentées.

This paper provides a complete characterization of the information-energy region of simultaneous information and energy transmission over an additive white Gaussian noise channel in the finite block-length regime with finite sets of channel input symbols. Given a set of channel input symbols, the converse characterizes the tuples of information rate, energy rate, decoding error probability (DEP) and energy outage probability (EOP) that cannot be achieved by any code built using the given set of channel inputs. A novel method for constructing a family of codes that respects the given information rate, energy rate, DEP and EOP requirements is proposed. The achievable region identifies the set of tuples of information rate, energy rate, DEP and EOP that can be achieved by the constructed family of codes. The proposed construction proves to be information rate, energy rate, and EOP optimal. The achieved DEP is, however, sub-optimal, owing to the choice of the decoding regions made during the construction.

International audience; This paper characterizes the trade-offs between the information and energy transmission rates, the decoding error probability, and the energy outage probability in simultaneous information and energy transmission over an additive white Gaussian noise channel. The results in this paper take into account the impact of energy harvester (EH) non-linearities on the harvested energy. The analysis is carried out in the finite block-length regime with finite constellations. Improved converse and achievability bounds that account for the EH non-linearities are presented.

In this paper, we consider a perfect coordinated water-filling game, where each user transmits solely on a given carrier. The main goal of the proposed algorithm (which we call FEAT) is to get close to the optimal, while keeping a decent level of fairness. The key idea within FEAT is to minimize the ratio between the best and the worst utilities of the users. This is done by ensuring that, at each iteration (channel assignment), a user is satisfied with this assignment as long as he does not loose much more than other users in the system. It has been shown that FEAT outperforms most related algorithms in many aspects, especially in interference-limited systems. Indeed, with FEAT we can ensure a near-optimal, fair and energy efficient solution with low computational complexity. In terms of robustness, it turns out that the balance between being nearly globally optimal and good from individual point of view seems hard to sustain with a significant number of users. Also notice that, in this regard, global optimality gets less affected than the individual one, which offers hope that such an accurate water-filling algorithm can be designed around competition in interference-limited systems., 27 PAGES, 14 FIGURES

In this report, sparse stealth attack constructions that minimize the mutual information between the state variables and the observations are proposed. The attack construction is formulated as the design of a multivariate Gaussian distribution aiming to minimize the mutual information while limiting the Kullback-Leibler divergence between the distribution of the observations under attack and the distribution of the observations without attack. The sparsity constraint is incorporated as a support constraint of the attack distribution. Two heuristic greedy algorithms for the attack construction are proposed. The first algorithm assumes that the attack vector consists of independent entries, and therefore, requires no communication between different attacked locations. The second algorithm considers correlations between the attack vector entries, which results in larger disruption and smaller probability of detection. A performance analysis of the proposed attack constructions on IEEE test systems is presented. Using a numerical example, it is shown that it is feasible to construct stealth attacks that generate significant disruption with a low number of compromised sensors.; Dans ce rapport, des constructions d’attaques furtives ciblant un sous-ensemble des capteurs qui minimisent l’information mutuelle entre les variables d’état et les observations sont proposées. La construction d’attaque est formulée comme la conception d’une distribution gaussienne multivariée visant à minimiser l’information mutuelle tout en limitant la divergence de Kullback-Leibler entre la distribution des observations sous attaque et la distribution des observations sans attaque. La contrainte pour modeliser le fait que l’attaque cible uniquement un sous-ensemble des capteurs est incorporée en tant que contrainte sur le support de la distribution de probabilité de l’attaque. Deux algorithmes heuristiques gloutons pour la construction d’attaques sont proposés. Le premier algorithme suppose que le vecteur d’attaque se compose d’entrées indépendantes et, par conséquent, ne nécessite aucune communication entre les différents emplacements attaqués. Le deuxième algorithme prend en compte les corrélations entre les entrées du vecteur d’attaque, ce qui entraîne une perturbation plus importante et une probabilité de détection plus faible. Une analyse des performances des constructions d’attaque proposées sur les systèmes de test IEEE est présentée. À l’aide d’un exemple numérique, il est démontré qu’il est possible de construire des attaques furtives qui génèrent des perturbations importantes avec un faible nombre de capteurs compromis.

International audience; This paper characterizes an achievable information-energy region of simultaneous information and energy transmission over an additive white Gaussian noise channel. This analysis is performed in the finite block-length regime with finite constellations. More specifically, a method for constructing a family of codes is proposed and the set of achievable tuples of information rate, energy rate, decoding error probability (DEP) and energy outage probability (EOP) is characterized. Using existing converse results, it is shown that the construction is information rate, energy rate, and EOP optimal. The achieved DEP is, however, sub-optimal.

An explicit expression for the sensitivity of the expected empirical risk (EER) induced by the Gibbs algorithm (GA) is presented in the context of supervised machine learning. The sensitivity is defined as the difference between the EER induced by the GA and the EER induced by an alternative probability measure on the models. When several datasets are available, the sensitivity plays a central role to determine whether or not a lower EER might be observed by aggregating several datasets. Necessary and sufficient conditions for decreasing the EER by dataset aggregation are presented. Such conditions, which are on the GA parameters and the referencemeasures assumed for each constituent dataset, boils down to the evaluation of the sign of the sum of some relative entropy terms. From this perspective, sensitivity appears as (a) an alternative metric to evaluate the generalization capabilities of the Gibbs algorithm; and (b) a theoretical ground to study the use of several datasets describing the same phenomenon, yet subject to different data acquisition systems, i.e., datasets with different statistical properties.; Une expression explicite de la sensibilité du risque empirique espéré (REE) induit par l’algorithme de Gibbs (AG) dans le problème de l’apprentissage automatique supervisé est présentée. La sensibilité est définie comme la différence entre l’REE induit par l’AG et l’REE induit par une mesure de probabilité alternative sur les modèles. Lorsque plusieurs ensembles de données sont disponibles, la sensibilité joue un rôle central pour déterminer si un REE plus petit peut-être observé comme résultat de l’agrégation de plusieurs ensembles de données. Les conditions nécessaires et suffisantes pour observer une diminution de l’EER due à l’agrégation des données sont présentées. De telles conditions,qui sont sur les paramètres de l’AG et les mesures de référence supposées pour chaque ensemble de données, se résument à l’évaluation du signe d’une somme de certains termes d’entropie relative. À la lumière de ces résultats, la sensibilité apparaît comme (a) une métrique alternative pour évaluer les capacités de généralisation de l’algorithme de Gibbs; et (b) un cadre théorique pour étudier l’impact de l’utilisation de plusieurs ensembles de données décrivant le même phénomène mais soumis à différents systèmes d’acquisition de données, ce qui implique par exemple, différentes propriétés statistiques pour chaque ensemble de données.

In this version minor edition is made to correct typos.; The empirical risk minimization (ERM) problem with relative entropy regularization (ERM-RER) is investigated under the assumption that the reference measure is a σ-finite measure, and not necessarily a probability measure. Under this assumption, which leads to a generalization of the ERM-RER problem allowing a larger degree of flexibility for incorporating prior knowledge, numerous relevant properties are stated. Among these properties, the solution to this problem, if it exists, is shown to be a unique probability measure, often mutually absolutely continuous with the reference measure. Such a solution exhibits a probably-approximately-correct guarantee for the ERM problem independently of whether the latter possesses a solution. For a fixed dataset, the empirical risk is shown to be a sub-Gaussian random variable when the models are sampled from the solution to the ERM-RER problem. The generalization capabilities of the solution to the ERMRER problem (the Gibbs algorithm) are studied via the sensitivity of the expected empirical risk to deviations from such a solution towards alternative probability measures. Finally, an interesting connection between sensitivity, generalization error, and lautum information is stablished.; Le problème de minimisation du risque empirique (ERM) avec régularisation d’entropie relative (ERM-RER) est étudié sous l’hypothèse que la mesure de référence est une mesure σ-finie, et pas nécessairement une mesure de probabilité. Sous cette hypothèse, qui conduit à une généralisation du problème ERM-RER permettant une plus grande flexibilité pour l’incorporation des connaissances antérieures, de nombreuses propriétés pertinentes sont énoncées. Parmi ces propriétés, la solution à ce problème, si elle existe, se révèle être une mesure de probabilité unique, souvent mutuellement absolument continue avec la mesure de référence. Une telle solution présente une garantie probablementapproximativement-correcte pour le problème ERM indépendamment du fait que ce dernier possède ou non une solution. Pour un ensemble de données fixe, le risque empirique s’avère être une variable aléatoire sous-gaussienne lorsque les modèles sont échantillonnés à partir de la solution au problème ERM-RER. Les capacités de généralisation de la solution au problème ERM-RER (l’algorithme de Gibbs) sont étudiées via la sensibilité de la valeur espérée du risque empirique aux déviations d’une telle solution vers des mesures de probabilité alternatives. Enfin, un lien intéressant entre la sensibilité, l’erreur de généralisation et l’information lautum est établi.

The optimality and sensitivity of the empirical risk minimization problem with relative entropy regularization (ERM-RER) are investigated for the case in which the reference is a sigma-finite measure instead of a probability measure. This generalization allows for a larger degree of flexibility in the incorporation of prior knowledge over the set of models. In this setting, the interplay of the regularization parameter, the reference measure, the risk function, and the empirical risk induced by the solution of the ERM-RER problem is characterized. This characterization yields necessary and sufficient conditions for the existence of a regularization parameter that achieves an arbitrarily small empirical risk with arbitrarily high probability. The sensitivity of the expected empirical risk to deviations from the solution of the ERM-RER problem is studied. The sensitivity is then used to provide upper and lower bounds on the expected empirical risk. Moreover, it is shown that the expectation of the sensitivity is upper bounded, up to a constant factor, by the square root of the lautum information between the models and the datasets., In Proc. IEEE International Symposium on Information Theory (ISIT), Aalto, Finland, Jul., 2022

International audience; Masks save lives. Therefore, whilst the culture of wearing masks is promoted, it is critical to understand the various aspects of how that culture is adopted. The main contribution of this paper is in the modeling of the mask game. Wearing a mask provides partial protection against epidemics at some cost of comfort. Players can be differentiated according to both their risk-state as well as their health-state (susceptible, infected and removed). We formulate the problem as a Bayesian game in which players know their own risk-state and ignore their own health state and the health and risk-states of their counterparts. Using ideas from evolutionary games, we reduce the problem to a one-shot equivalent game and describe the structure of the symmetric equilibria. We prove that the policies adopted by the players at such equilibria admit a threshold structure. More specifically, players wear masks only if their risk-state is equal to or bigger than a given threshold.

The empirical risk minimization (ERM) problem with relative entropy regularization (ERM-RER) is investigated under the assumption that the reference measure is a {\sigma}-finite measure, and not necessarily a probability measure. Under this assumption, which leads to a generalization of the ERM-RER problem allowing a larger degree of flexibility for incorporating prior knowledge, numerous relevant properties are stated. Among these properties, the solution to this problem, if it exists, is shown to be a unique probability measure, often mutually absolutely continuous with the reference measure. Such a solution exhibits a probably-approximately-correct guarantee for the ERM problem independently of whether the latter possesses a solution. For a fixed dataset, the empirical risk is shown to be a sub-Gaussian random variable when the models are sampled from the solution to the ERM-RER problem. The generalization capabilities of the solution to the ERM-RER problem (the Gibbs algorithm) are studied via the sensitivity of the expected empirical risk to deviations from such a solution towards alternative probability measures. Finally, an interesting connection between sensitivity, generalization error, and lautum information is stablished, Comment: Submitted to the the Transactions on Information Theory on June 12, 2023. Also available as: Research Report, INRIA, No. RR-9454, Centre Inria d'Universit\'e C\^ote d'Azur, Sophia Antipolis, France, Feb., 2022

In this chapter we review some of the basic attack constructions that exploit a stochastic description of the state variables. We pose the state estimation problem in a Bayesian setting and cast the bad data detection procedure as a Bayesian hypothesis testing problem. This revised detection framework provides the benchmark for the attack detection problem that limits the achievable attack disruption. Indeed, the trade-off between the impact of the attack, in terms of disruption to the state estimator, and the probability of attack detection is analytically characterized within this Bayesian attack setting. We then generalize the attack construction by considering information-theoretic measures that place fundamental limits to a broad class of detection, estimation, and learning techniques. Because the attack constructions proposed in this chapter rely on the attacker having access to the statistical structure of the random process describing the state variables, we conclude by studying the impact of imperfect statistics on the attack performance. Specifically, we study the attack performance as a function of the size of the training data set that is available to the attacker to estimate the second-order statistics of the state variables.

International audience; Information theoretic sparse attacks that minimize simultaneously the information obtained by the operator and the probability of detection are studied in a Bayesian state estimation setting. The attack construction is formulated as an optimization problem that aims to minimize the mutual information between the state variables and the observations while guaranteeing the stealth of the attack. Stealth is described in terms of the Kullback-Leibler (KL) divergence between the distributions of the observations under attack and without attack. To overcome the difficulty posed by the combinatorial nature of a sparse attack construction, the attack case in which only one sensor is compromised is analytically solved first. The insight generated in this case is then used to propose a greedy algorithm that constructs random sparse attacks. The performance of the proposed attack is evaluated in the IEEE 30 Bus Test Case.

Random attacks that jointly minimize the amount of information acquired by the operator about the state of the grid and the probability of attack detection are presented. The attacks minimize the information acquired by the operator by minimizing the mutual information between the observations and the state variables describing the grid. Simultaneously, the attacker aims to minimize the probability of attack detection by minimizing the Kullback-Leibler (KL) divergence between the distribution when the attack is present and the distribution under normal operation. The resulting cost function is the weighted sum of the mutual information and the KL divergence mentioned above. The tradeoff between the probability of attack detection and the reduction of mutual information is governed by the weighting parameter on the KL divergence term in the cost function. The probability of attack detection is evaluated as a function of the weighting parameter. A sufficient condition on the weighting parameter is given for achieving an arbitrarily small probability of attack detection. The attack performance is numerically assessed on the IEEE 30-Bus and 118-Bus test systems., Comment: IEEE Trans. Smart Grid