In this report, a method for achieving exact unlearning for Gibbs supervised learning algorithms is proposed using a variational formulation inspired by empirical risk minimization subject to relative entropy regularization (ERM-RER). Such a method consists of maximizing the expected empirical risk over the dataset to be unlearned subject to a regularization by relative entropy with respect to the original algorithm. The optimization variable is a probability measure on the models; and the solution is another Gibbs probability measure that represents a new Gibbs supervised learning algorithm. The method guarantees exact unlearning in the sense that the new Gibbs algorithm coincides in distribution with the algorithm that would have been obtained by retraining from scratch on the dataset to be retained. As a byproduct, a framework for reweighting data points in ERM-RER by strategically choosing both the reference measure and the regularization factor is obtained. In this framework, exact unlearning is the special case in which zero-weight is assigned to the contribution of the data points to be unlearned. More generally, depending on the choice of certain parameters, data points can be up-weighted or down-weighted in ERM-RER problems for particular purposes, e.g., controlling the generalization error of Gibbs algorithms. This paves the way to new constructive or adversarial views on classical reweighting data points in ERM-RER.

International audience

This work establishes that an optimal transport~(OT) problem regularized by a given $f$-divergence admits the same solution as another OT problem regularized by a different $g$-divergence, under an appropriate transformation of the cost function. This structural equivalence between OT problems regularized by distinct divergences, in the sense of sharing the same unique minimizer, is demonstrated within the framework of Polish spaces with bounded cost functions.

International audience

The dual formulation of empirical risk minimization with f-divergence regularization (ERM-fDR) is introduced. The solution of the dual optimization problem to the ERM-fDR is connected to the notion of normalization function introduced as an implicit function. This dual approach leverages the Legendre-Fenchel transform and the implicit function theorem to provide a nonlinear ODE expression to the normalization function. Furthermore, the nonlinear ODE expression and its properties provide a computationally efficient method to calculate the normalization function of the ERM-fDR solution under a mild condition.

This paper characterizes the trade-offs between information and energy transmission over an additive white Gaussian noise channel in the finite block-length regime with finite channel input symbols. These trade-offs are characterized in the form of inequalities involving the information transmission rate, energy transmission rate, decoding error probability (DEP) and energy outage probability (EOP) for a given finite block-length code. The first set of results identify a set of necessary conditions that a given code must satisfy for simultaneous information and energy transmission. Following this, a novel method for constructing a family of codes that can satisfy a target information rate, energy rate, DEP and EOP is proposed. Finally, achievability results identify the set of tuples of information rate, energy rate, DEP and EOP that can be simultaneously achieved by the constructed family of codes.

The effect of relative entropy asymmetry is analyzed in the context of empirical risk minimization (ERM) with relative entropy regularization (ERM-RER). Two regularizations are considered: (a) the relative entropy of the measure to be optimized with respect to a reference measure (Type-I ERM-RER); and (b) the relative entropy of the reference measure with respect to the measure to be optimized (Type-II ERM-RER). The main result is the characterization of the solution to the Type-II ERM-RER problem and its key properties. By comparing the well-understood Type-I ERM-RER with Type-II ERM-RER, the effects of entropy asymmetry are highlighted. The analysis shows that in both cases, regularization by relative entropy forces the support of the solution to collapse into the support of the reference measure, introducing a strong inductive bias that negates the evidence provided by the training data. Finally, it is shown that Type-II regularization is equivalent to Type-I regularization with an appropriate transformation of the empirical risk function.

In this paper, the worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. More specifically, the worst-case probability measure is a Gibbs probability measure and the unique solution to the maximization of the expected loss under a relative entropy constraint with respect to a reference probability measure. Fundamental generalization metrics, such as the sensitivity of the expected loss, the sensitivity of the empirical risk, and the generalization gap are shown to have closed-form expressions involving the worst-case data-generating probability measure. Existing results for the Gibbs algorithm, such as characterizing the generalization gap as a sum of mutual information and lautum information, up to a constant factor, are recovered. A novel parallel is established between the worst-case data-generating probability measure and the Gibbs algorithm. Specifically, the Gibbs probability measure is identified as a fundamental commonality of the model space and the data space for machine learning algorithms.

The solution to empirical risk minimization with$f-\mathbf{divergence}$regularization$(\mathbf{ERM}-f\mathbf{DR}$) is presented under mild conditions on$f$. Under such conditions, the optimal measure is shown to be unique. Examples of the solution for particular choices of the function$f$are presented. Previously known solutions to common regularization choices are obtained by lever-aging the flexibility of the family of$f-\mathbf{divergences}$, These include the unique solutions to empirical risk minimization with relative entropy regularization (Type-I and Type-II). The analysis of the solution unveils the following properties of$f-\mathbf{divergences}$when used in the ERM-f DR problem:$i$)$f-\mathbf{divergence}$regularization forces the support of the solution to coincide with the support of the reference measure, which introduces a strong inductive bias that dominates the evidence provided by the training data; and ii) any$f-\mathbf{divergence}$regularization is equivalent to a different$f-\mathbf{divergence}$regularization with an appropriate transformation of the empirical risk function.

This paper studies an instance of zero-sum games in which one player (the leader) commits to its opponent (the follower) to choose its actions by sampling a given probability measure (strategy). The actions of the leader are observed by the follower as the output of an arbitrary channel. In response to that, the follower chooses its action based on its current information, that is, the leader's commitment and the corresponding noisy observation of its action. Within this context, the equilibrium of the game with noisy action observability is shown to always exist and the necessary conditions for its uniqueness are identified. Interestingly, the noisy observations have important impact on the cardinality of the follower's set of best responses. Under particular conditions, such a set of best responses is proved to be a singleton almost surely. The proposed model captures any channel noise with a density with respect to the Lebesgue measure. As an example, the case in which the channel is described by a Gaussian probability measure is investigated.

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, 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 and under a specific condition, 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 established.

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.

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 this paper, 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.

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 σ-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 regularization parameters that achieve arbitrarily small empirical risk with arbitrarily high probability. Additionally, the sensitivity of the expected empirical risk to deviations from the solution of the ERM-RER problem is studied. Dataset-dependent and dataset-independent upper bounds on the absolute value of the sensitivity are presented. In a special case, it is shown that the expectation (with respect to the datasets) of the absolute value 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.

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.

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.

The water-filling algorithm is well known for providing optimal data rates in time varying wireless communication networks. In this paper, a perfectly coordinated water-filling game is considered, in which each user transmits only on the assigned carrier. Contrary to conventional algorithms, the main goal of the proposed algorithm (FEAT) is to achieve near optimal performance, while satisfying fairness constraints among different users. The key idea within FEAT is to minimize the ratio between the utilities of the best and the worst users. To achieve this goal, we devise an algorithm such that, at each iteration (channel assignment), a channel is assigned to a user, while ensuring that it does not lose much more than other users in the system. In this paper, we show that FEAT outperforms most of the existing related algorithms in many aspects, especially in interference-limited systems. Indeed, with FEAT, we can ensure a low complexity near-optimal, and fair solution. It is shown that the balance between being nearly globally optimal and good from an individual point of view seems hard to sustain with a significant number of users, hence adding robustness to the proposed algorithm.

In this paper, a real-valued function that approximates the cumulative distribution function (CDF) of a finite sum of real-valued independent and identically distributed random vectors is presented. The approximation error is upper bounded by an expression that is easy to calculate. As a byproduct, an upper bound and a lower bound on the CDF are obtained. Finally, in the case of lattice and absolutely continuous random variables, the proposed approximation is shown to be identical to the saddlepoint approximation of the CDF.

In this paper, the fundamental limits on the rates at which information and energy can be simultaneously transmitted over an additive white Gaussian noise channel are studied under the following assumptions: (a) the channel is memoryless; (b) the number of channel input symbols (constellation size) and block length are finite; and (c) the decoding error probability (DEP) and the energy outage probability (EOP) are bounded away from zero. In particular, it is shown that the limits on the maximum information and energy transmission rates; and the minimum DEP and EOP, are essentially set by the type induced by the code used to perform the transmission. That is, the empirical frequency with which each channel input symbol appears in the codewords. Using this observation, guidelines for optimal constellation design for simultaneous energy and information transmission are presented.

This paper introduces an upper-bound on the absolute difference between: (a) the cumulative distribution function (c.d. f.) of the sum of a finite number of independent and identically distributed (i.i.d) random variables; and (b) a saddlepoint approximation of such c.d.f. This upperbound is general and particularly precise in the regime of large deviations. This result is used to study the dependence testing (DT) bound on the minimum decoding error probability (DEP) in memoryless channels. Within this context, the main results include new lower and upper bounds on the DT bound. As a byproduct, an upper bound on the absolute difference between the exact value of the DT bound and its saddlepoint approximation is obtained. Numerical analysis of these bounds are presented for the case of the binary symmetric channel and the additive white Gaussian noise channel, in which the new bounds are observed to be tight.

Recent years have witnessed the proliferation of mobile computing and the Internet of Things (IoT), in which billions of mobile and IoT devices are connected to the Internet, generating zillions bytes of data at the network edge. However, it is challenging and infeasible to transfer and process zillions bytes of data using the current cloud-device architecture, due to bandwidth constraints of networks, potentially uncontrollable latency of cloud services, and privacy concerns while collecting data from IoT devices. To tackle these challenges, edge computing, an emerging computing paradigm, has received a tremendous amount of interest. By pushing data storage, computing, and controls closer to the network edge, edge computing has been widely recognized as a promising solution to meet the requirements of low latency, high scalability, and energy efficiency, as well as to mitigate the network traffic burdens. However, with the emergence of diverse IoT applications (e.g., smart city, industrial automation, and connected car), it becomes challenging for edge computing to deal with these heterogeneous IoT environments.

Given a code used to send a message to two receivers through a degraded discrete memoryless broadcast channel (DM-BC), the sender wishes to alter the codewords to achieve the following goals: (i) the original broadcast communication continues to take place, possibly at the expense of a tolerable increase of the decoding error probability; and (ii) an additional covert message can be transmitted to the stronger receiver such that the weaker receiver cannot detect the existence of this message. The main results are: (a) feasibility of covert communications is proven by using a random coding argument for general DM-BCs; and (b) necessary conditions for establishing covert communications are described and an impossibility (converse) result is presented for a particular class of DM-BCs. Together, these results characterize the asymptotic fundamental limits of covert communications for this particular class of DM-BCs within an arbitrarily small gap.

In this paper, the fundamental limits of simultaneous information and energy transmission in the two-user Gaussian interference channel with and without perfect channel-output feedback are approximated by two regions in each case, i.e., an achievable region and a converse region. When the energy transmission rate is normalized by the maximum energy rate, the approximation is within a constant gap. In the proof of achievability, the key idea is the use of power-splitting between two signal components: an information-carrying component and a no-information component. The construction of the former is based on random coding arguments, whereas the latter consists of a deterministic sequence known by all transmitters and receivers. The proof of the converse is obtained via cut-set bounds, genie-aided channel models, Fano's inequality, and some concentration inequalities considering that channel inputs might have a positive mean. Finally, the energy transmission enhancement due to feedback is quantified and it is shown that feedback can at most double the energy transmission rate at high signal-to-noise ratios.

In this paper, an analysis of an input distribution that achieves the secrecy capacity of a general degraded additive noise wiretap channel is presented. In particular, using convex optimization methods, an input distribution that achieves the secrecy capacity is characterized by conditions expressed in terms of integral equations. The new conditions are used to study the structure of the optimal input distribution for three different additive noise cases: vector Gaussian; scalar Cauchy; and scalar exponential.

In this paper, an achievable η-Nash equilibrium (η-NE) region for the two-user Gaussian interference channel with noisy channel-output feedback is presented for all η ≥ 1. This result is obtained in the scenario in which each transmitter-receiver pair chooses its own transmit-receive configuration in order to maximize its own individual information transmission rate. At an η-NE, any unilateral deviation by either of the pairs does not increase the corresponding individual rate by more than η bits per channel use.

In this paper, the benefits of channel-output feedback in the Gaussian interference channel (G-IC) are studied under the effect of additive Gaussian noise. Using a linear deterministic (LD) model, the signal to noise ratios (SNRs) in the feedback links beyond which feedback plays a significant role in terms of increasing the individual rates or the sum-rate are approximated. The relevance of this work lies in the fact that it identifies the feedback SNRs for which in any G-IC, one of the following statements is true: (a) feedback does not enlarge the capacity region; (b) feedback enlarges the capacity region and the sum-rate is greater than the largest sum-rate without feedback; and (c) feedback enlarges the capacity region but no significant improvement is observed in the sum-rate.

In this paper, the capacity region of the linear deterministic interference channel with noisy channel-output feedback (LD-IC-NF) is fully characterized. The proof of achievability is based on random coding arguments and rate splitting, block-Markov superposition coding, and backward decoding. The proof of the converse reuses some of the existing outer bounds and includes new ones obtained using genie-aided models. Following the insight gained from the analysis of the LD-IC-NF, an achievability region and a converse region for the two-user Gaussian interference channel with noisy channel-output feedback (G-IC-NF) are presented. Finally, the achievability region and the converse region are proven to approximate the capacity region of the G-IC-NF to within 4.4 bits.

In this paper, a new framework based on the notion of capacity sensitivity is introduced to study the capacity of continuous memoryless point-to-point channels. The capacity sensitivity reflects how the capacity changes with small perturbations in any of the parameters describing the channel, even when the capacity is not available in closed-form. This includes perturbations of the cost constraints on the input distribution as well as on the channel distribution. The framework is based on continuity of the capacity, which is shown for a class of perturbations in the cost constraint and the channel distribution. The continuity then forms the foundation for obtaining bounds on the capacity sensitivity. As an illustration, the capacity sensitivity bound is applied to obtain scaling laws when the support of additive α-stable noise is truncated.

In this paper, the η-Nash equilibrium (η-NE) region of the two-user linear deterministic interference channel (IC) with noisy channel-output feedback is characterized for all η > 0. The η-NE region, a subset of the capacity region, contains the set of all achievable information rate pairs that are stable in the sense of an η-NE. More specifically, given an η-NE coding scheme, there does not exist an alternative coding scheme for either transmitter-receiver pair that increases the individual rate by more than η bits per channel use. Existing results such as the η-NE region of the linear deterministic IC without feedback and with perfect output feedback are obtained as particular cases of the result presented in this paper.

In this paper, a generalization of the satisfaction equilibrium (SE) for games in satisfaction form (SF) is presented. This new solution concept is referred to as the generalized satisfaction equilibrium (GSE). In games in SF, players choose their actions to satisfy an individual constraint that depends on the actions of all the others. At a GSE, players that are unsatisfied are unable to unilaterally deviate to be satisfied. The concept of GSE generalizes the SE in the sense that it allows mixed-strategy equilibria in which there exist players who are unable to satisfy their individual constraints. The pure-strategy GSE problem is closely related to the constraint satisfaction problem and finding a pure-strategy GSE is proven to be NP-hard. The existence of at least one GSE in mixed strategies is proven for the class of games in which the constraints are defined by a lower limit on the expected utility. A dynamics referred to as the satisfaction response is shown to converge to a GSE in certain classes of games. Finally, Bayesian games in SF and the corresponding Bayesian GSE are introduced. These results provide a theoretical framework for studying service-level provisioning problems in communications networks as shown by several examples.

International audience

Device-to-device (D2D) communications can enhance spectrum and energy efficiency due to direct proximity communication and frequency reuse. However, such performance enhancement is limited by mutual interference and energy availability, especially when the deployment of D2D links is ultra-dense. In this paper, we present a distributed power control method for ultra-dense D2D communications underlying cellular communications. In this power control method, in addition to the remaining battery energy of the D2D transmitter, we consider the effects of both the interference caused by the generic D2D transmitter to others and the interference from all others caused to the generic D2D receiver. We formulate a mean-field game (MFG) theoretic framework with the interference mean-field approximation. We design the cost function combining both the performance of the D2D communication and cost for transmit power at the D2D transmitter. Within the MFG framework, we derive the related Hamilton-Jacobi-Bellman and Fokker-Planck-Kolmogorov equations. Then, a novel energy and interference aware power control policy is proposed, which is based on the Lax-Friedrichs scheme and the Lagrange relaxation. The numerical results are presented to demonstrate the spectrum and energy efficiency performances of our proposed approach.

In this paper, the fundamental limits of simultaneous information and energy transmission in the two-user Gaussian multiple access channel with feedback are fully characterized. A simple achievability scheme based on power-splitting and Ozarow's scheme is shown to be optimal. Finally, the maximum individual information rates and the information sum-capacity that are achievable given a minimum energy rate constraint of b energy-units per channel use at the input of the energy harvester are identified. An interesting conclusion is that for a fixed information transmission rate, feedback can at most double the energy transmission rate with respect to the case without feedback.

In this paper, an achievability region and a converse region for the two-user Gaussian interference channel with noisy channel-output feedback (G-IC-NOF) are presented. The achievability region is obtained using a random coding argument and three well-known techniques: rate splitting, superposition coding and backward decoding. The converse region is obtained using some of the existing perfect-output feedback outer-bounds as well as a set of new outer-bounds that are obtained by using genie-aided models of the original G-IC-NOF. Finally, it is shown that the achievability region and the converse region approximate the capacity region of the G-IC-NOF to within a constant gap in bits per channel use.

In this paper, the η-Nash equilibrium (η-NE) region of the two-user Gaussian interference channel (IC) with perfect output feedback is approximated to within 1 bit/s/Hz and η arbitrarily close to 1 bit/s/Hz. The relevance of the η-NE region is that it provides the set of rate pairs that are achievable and stable in the IC when both transmitter-receiver pairs autonomously tune their own transmit-receive configurations seeking an η-optimal individual transmission rate. Therefore, any rate tuple outside the η-NE region is not stable as there always exists one link able to increase by at least η bits/s/Hz its own transmission rate by updating its own transmit-receive configuration. The main insights that arise from this paper are as follows. First, the η-NE region achieved with feedback is larger than or equal to the η-NE region without feedback. More importantly, for each rate pair achievable at an η-NE without feedback, there exists at least one rate pair achievable at an η-NE with feedback that is weakly Pareto superior. Second, there always exists an η-NE transmit-receive configuration that achieves a rate pair that is at most 1 bit/s/Hz per user away from the outer bound of the capacity region.

In this paper, all the rate-pairs that are achievable at a Nash equilibrium (NE) in the two-user linear deterministic symmetric decentralized interference channel (LD-S-DIC) with noisy feedback are identified. More specifically, the Nash region (NR) of the LD-S-DIC with noisy feedback is fully characterized. The relevance of these rate-pairs is that once they are achieved by using NE transmit-receive configurations, none of the transmitter-receiver pairs can increase their individual rates by unilaterally changing their configurations. More importantly, it is shown that the NR of the LD-S-DIC with noisy feedback is larger than the NR of the LD-S-DIC without feedback only in certain cases. When interference is stronger than the desired signals, a larger NR is observed only if the signal to noise ratios (SNRs) of the feedback links are higher than the SNRs of the direct links. Conversely, when desired signals are stronger than interference, a larger NR is observed only if the SNRs of the feedback links are higher than both the signal to interference ratios (SIRs) and the interference to noise ratios (INRs) of the direct links. Previous results, namely the NE region of the two-user LD-S-DIC without feedback and with perfect output feedback are obtained as special cases of the results presented in this contribution.

In this paper, a wireless cooperative network is considered, in which multiple source-destination pairs communicate with each other via an energy harvesting relay. The focus of this paper is on the relay's strategies to distribute the harvested energy among the multiple users and their impact on the system performance. Specifically, a non-cooperative strategy that uses the energy harvested from the i-th source as the relay transmission power to the i-th destination is considered first, and asymptotic results show that its outage performance decays as log SNR/SNR. A faster decay rate, 1/SNR, can be achieved by two centralized strategies proposed next, of which a water filling based one can achieve optimal performance with respect to several criteria, at the price of high complexity. An auction based power allocation scheme is also proposed to achieve a better tradeoff between system performance and complexity. Simulation results are provided to confirm the accuracy of the developed analytical results.

In this paper, the problem of channel selection and power control is jointly analyzed in the context of multiple-channel clustered ad-hoc networks, i.e., decentralized networks in which radio devices are arranged into groups (clusters) and each cluster is managed by a central controller (CC). This problem is modeled by game in normal form in which the corresponding utility functions are designed for making some of the Nash equilibria (NE) to coincide with the solutions to a global network optimization problem. In order to ensure that the network operates in the equilibria that are globally optimal, a learning algorithm based on the paradigm of trial and error learning is proposed. These results are presented in the most general form and therefore, they can also be seen as a framework for designing both games and learning algorithms with which decentralized networks can operate at global optimal points using only their available local knowledge. The pertinence of the game design and the learning algorithm are highlighted using specific scenarios in decentralized clustered ad hoc networks. Numerical results confirm the relevance of using appropriate utility functions and trial and error learning for enhancing the performance of decentralized networks.

In this paper, the problem of distributed control of the heating, ventilation and air conditioning (HVAC) system in an energy-smart building is addressed. Using tools from game theory the interaction among several autonomous HVAC units is studied and simple learning dynamics based on trial-and-error learning are proposed to achieve equilibrium. In particular, it is shown that this algorithm reaches stochastically stable states that are equilibria and maximizers of the global welfare of the corresponding game. Simulation results demonstrate that dynamic distributed control for the HVAC system can significantly increase the energy efficiency of smart buildings.

In this paper, a decentralized iterative algorithm, namely the optimal dynamic learning (ODL) algorithm, is analysed. The ability of this algorithm of achieving a Pareto optimal working point exploiting only a minimal amount of information is shown. The algorithm performance is analysed in a clustered ad hoc network, where radio devices are assumed to operate above a minimal signal to interference plus noise ratio (SINR) threshold while minimizing the global power consumption. Sufficient analytical conditions for ODL to converge to the desired working point are provided, moreover through numerical simulations the ability of the algorithm to configure an interference limited network is shown. The performances of ODL and of a Nash equilibrium reaching algorithm are numerically compared, and their performance as a function of available resources is studied. The gain of ODL is shown to be larger when the amount of available radio resources is scarce.

In this paper, the impact of network-state knowledge is studied in the context of decentralized active non-colluding eavesdropping. The main contribution is a formal proof of a paradoxical effect that might appear when increasing the available knowledge at each of the network components. Using a broadcast channel similar to the time-division downlink of a single-cell cellular system, it is shown that providing more knowledge to both the transmitter and the receivers negatively affects their performance. Eavesdroppers become more conservative in their attacks, which makes them harmless in terms of information leakage, whereas the transmitter becomes more careful and less willing to transmit, which reduces the expected secrecy capacity of this channel. Finally, it is shown that this counter-intuitive effect vanishes in the high SNR regime, in which the system becomes resilient to active attacks.

Physical layer security can provide alternative means for securing the exchange of confidential messages in wireless applications. In this paper, the resilience of wireless multiuser networks to passive (interception of the broadcast channel) and active (interception of the broadcast channel and false feedback) eavesdroppers is investigated under Rayleigh fading conditions. Stochastic characterizations of the secrecy capacity (SC) are obtained in scenarios involving a base station and several destinations. The expected values and variances of the SC along with the probabilities of secrecy outages are evaluated in the following cases: (i) in the presence of passive eavesdroppers without any side information; (ii) in the presence of passive eavesdroppers with side information about the number of eavesdroppers; and (iii) in the presence of a single active eavesdropper with side information about the behavior of the eavesdropper. This investigation demonstrates that substantial secrecy rates are attainable on average in the presence of passive eavesdroppers as long as minimal side information is available. On the other hand, it is further found that active eavesdroppers can potentially compromise such networks unless statistical inference is employed to restrict their ability to attack. Interestingly, in the high signal to noise ratio regime, multiuser networks become insensitive to the activeness or passiveness of the attack.

In this paper, a decentralized and self-organizing mechanism for small cell networks (such as micro-, femto- and picocells) is proposed. In particular, an application to the case in which small cell networks aim to mitigate the interference caused to the macrocell network, while maximizing their own spectral efficiencies, is presented. The proposed mechanism is based on new notions of reinforcement learning (RL) through which small cells jointly estimate their time-average performance and optimize their probability distributions with which they judiciously choose their transmit configurations. Here, a minimum signal to interference plus noise ratio (SINR) is guaranteed at the macrocell user equipment (UE), while the small cells maximize their individual performances. The proposed RL procedure is fully distributed as every small cell base station requires only an observation of its instantaneous performance which can be obtained from its UE. Furthermore, it is shown that the proposed mechanism always converges to an epsilon Nash equilibrium when all small cells share the same interest. In addition, this mechanism is shown to possess better convergence properties and incur less overhead than existing techniques such as best response dynamics, fictitious play or classical RL. Finally, numerical results are given to validate the theoretical findings, highlighting the inherent tradeoffs facing small cells, namely exploration/exploitation, myopic/foresighted behavior and complete/incomplete information.

Security is becoming an increasingly important issue in wireless communications, to which physical layer approaches can contribute by providing addition resources for securing confidential messages. In this paper, the resilience of multi-user networks to passive and active eavesdropping is investigated. In particular, average secrecy capacities are evaluated in scenarios involving a base station and several terminals, some of which constitute passive or active eavesdroppers. Network resources (e.g. power) are allocated by the base station based on the available channel state information. The average secrecy capacity of such a network is evaluated in the following cases: (i) in the presence of passive eavesdroppers when no side information is available to the base station; (ii) in the presence of passive eavesdroppers with side information available; and (iii) in the presence of a single active eavesdropper with side information available. This investigation demonstrates that substantial secrecy rates are attainable in the presence of passive eavesdroppers as long as minimal side information, e.g. a statistical characterization of the number of potential eavesdroppers, is available to the base station. On the other hand, it is further found that active eavesdroppers can potentially compromise such networks unless statistical inference is employed to restrict their ability to attack.

In this paper, we study the strategic coexistence between macro and femto cell tiers from a game theoretic learning perspective. A novel regret-based learning algorithm is proposed whereby cognitive femtocells mitigate their interference toward the macrocell tier, on the downlink. The proposed algorithm is fully decentralized relying only on the signal-to-interference-plus-noise ratio (SINR) feedback to the corresponding femtocell base stations. Based on these local observations, femto base stations learn the probability distribution of their transmission strategies (power levels and frequency band) by minimizing their regrets for using certain strategies, while adhering to the cross-tier interference constraint. The decentralized regret based learning algorithm is shown to converge to an ϵ-coarse correlated equilibrium (ϵ-CCE) which is a generalization of the classical Nash Equilibrium (NE). Finally, numerical results are shown to corroborate our findings where, quite remarkably, our learning algorithm achieves the same performance as the classical regret matching, but with substantially much less overhead.

In this paper, we address the problem of global transmit power minimization in a self-configuring network where radio devices are subject to operate at a minimum signal to interference plus noise ratio (SINR) level. We model the network as a parallel Gaussian interference channel and we introduce a fully decentralized algorithm (based on trial and error) able to statistically achieve a configuration where the performance demands are met. Contrary to existing solutions, our algorithm requires only local information and can learn stable and efficient working points by using only one bit feedback. We model the network under two different game theoretical frameworks: normal form and satisfaction form. We show that the converging points correspond to equilibrium points, namely Nash and satisfaction equilibrium. Similarly, we provide sufficient conditions for the algorithm to converge in both formulations. Moreover, we provide analytical results to estimate the algorithm's performance, as a function of the network parameters. Finally, numerical results are provided to validate our theoretical conclusions.

In this article, we investigate the competitive interaction between electrical vehicles or hybrid oil-electricity vehicles in a Cournot market consisting of electricity transactions to or from an underlying electricity distribution network. We provide a mean field game formulation for this competition, and introduce the set of fundamental differential equations ruling the behavior of the vehicles at the feedback Nash equilibrium, referred here to as the mean field equilibrium. This framework allows for a consistent analysis of the evolution of the price of electricity as well as of the instantaneous electricity demand in the power grid. Simulations precisely quantify those parameters and suggest that significant reduction of the daily electricity peak demand can be achieved by appropriate electricity pricing.

In this paper, recent results in game theory and stochastic approximation are brought together to mitigate the problem of femto-to-macrocell cross-tier interference. The main result of this paper is an algorithm which reduces the impact of interference of femtocells over the existing macrocells. Such algorithm relies on the observations of the signal to interference plus noise ratio (SINR) of all active communications in both macro and femtocells when they are fed back to the corresponding base stations. Based on such observations, femto base stations learn the probability distributions over the feasible transmit configurations (frequency band and power levels) such that a minimum time-average SINR can be guaranteed in the macrocells, at the equilibrium. In this paper, we introduce the concept of logit equilibrium (LE) and present its interpretation in terms of the trade-off faced by femtocells when experimenting several actions to discover the network, and taking the action to maximize their instantaneous performance. Finally, numerical results are given to validate our theoretical findings.

This paper is concerned with the concept of equilibrium and quality of service (QoS) provisioning in self-configuring wireless networks with non-cooperative radio devices (RD). In contrast with the Nash equilibrium (NE), where RDs are interested in selfishly maximizing its QoS, we present a concept of equilibrium, named satisfaction equilibrium (SE), where RDs are interested only in guaranteing a minimum QoS. We provide the conditions for the existence and the uniqueness of the SE. Later, in order to provide an equilibrium selection framework for the SE, we introduce the concept of effort or cost of satisfaction, for instance, in terms of transmit power levels, constellation sizes, etc. Using the idea of effort, the set of efficient SE (ESE) is defined. At the ESE, transmitters satisfy their minimum QoS incurring in the lowest effort. We prove that contrary to the (generalized) NE, at least one ESE always exists whenever the network is able to simultaneously support the individual QoS requests. Finally, we provide a fully decentralized algorithm to allow self-configuring networks to converge to one of the SE relying only on local information.

In this contribution we present a decentralized power allocation algorithm for the uplink interleave division multiple access (IDMA) channel. Within the proposed optimal strategy for power allocation, each user aims at selfishly maximizing its own utility function. An iterative chip-by-chip (CBC) decoder at the receiver and a rational selfish behavior of all the users according to a classical game-theoretical framework are the underlying assumptions of this work. This approach leads to a channel inversion policy where the optimal power level is set locally at each terminal based on the knowledge of its own channel realization, the noise level at the receiver and the number of active users in the network.

We present two interference alignment techniques such that an opportunistic point-to-point multiple input multiple output (MIMO) link can reuse, without generating any additional interference, the same frequency band of a similar pre-existing primary link. In this scenario, we exploit the fact that under power constraints, although each radio maximizes independently its rate by water-filling on their channel transfer matrix singular values, frequently, not all of them are used. Therefore, by aligning the interference of the opportunistic radio it is possible to transmit at a significant rate while insuring zero-interference on the pre-existing link. We propose a linear pre-coder for a perfect interference alignment and a power allocation scheme which maximizes the individual data rate of the secondary link. Our numerical results show that significant data rates are achieved even for a reduced number of antennas.