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

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.

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.

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.

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.

Compressive covariance estimation has arisen as a class of techniques whose aim is to obtain second-order statistics of stochastic processes from compressive measurements. Recently, these methods have been used in various image processing and communications applications, including denoising, spectrum sensing, and compression. Notice that estimating the covariance matrix from compressive samples leads to ill-posed minimizations with severe performance loss at high compression rates. In this regard, a regularization term is typically aggregated to the cost function to consider prior information about a particular property of the covariance matrix. Hence, this paper proposes an algorithm based on the projected gradient method to recover low-rank or Toeplitz approximations of the covariance matrix from compressive measurements. The proposed algorithm divides the compressive measurements into data subsets projected onto different subspaces and accurately estimates the covariance matrix by solving a single optimization problem assuming that each data subset contains an approximation of the signal statistics. Furthermore, gradient filtering is included at every iteration of the proposed algorithm to minimize the estimation error. The error induced by the proposed splitting approach is analytically derived along with the convergence guarantees of the proposed method. The proposed algorithm estimates the covariance matrix of hyperspectral images from synthetic and real compressive samples. Extensive simulations show that the proposed algorithm can effectively recover the covariance matrix of hyperspectral images from compressive measurements with high compression ratios ( 8-15% approx) in noisy scenarios. Moreover, simulations and theoretical results show that the filtering step reduces the recovery error up to twice the number of eigenvectors. Finally, an optical implementation is proposed, and real measurements are used to validate the theoretical findings.

Compressive covariance sampling (CCS) theory aims to recover the covariance matrix (CM) of a signal, instead of the signal itself, from a reduced set of random linear projections. Although several theoretical works demonstrate the CCS theory’s advantages in compressive spectral imaging tasks, a real optical implementation has no been proposed. Therefore, this paper proposes a compressive spectral sensing protocol for the dual-dispersive coded aperture spectral snapshot imager (DD-CASSI) to directly estimate the covariance matrix of the signal. Specifically, we propose a coded aperture design that allows recasting the vector sensing problem into matrix form, which enables to exploit the covariance matrix structure such as positive-semidefiniteness, low-rank, or Toeplitz. Additionally, a low-rank approximation of the image is reconstructed using a Principal Components Analysis (PCA) based method. In order to test the precision of the reconstruction, some spectral signatures of the image are captured with a spectrometer and compared with those obtained in the reconstruction using the covariance matrix. Results show the reconstructed spectrum is accurate with a spectral angle mapper (SAM) of less than 14°. RGB image composites of the spectral image also provide evidence of a correct color reconstruction.

The learning data requirements are analyzed for the construction of stealth attacks in state estimation. In particular, the training data set is used to compute a sample covariance matrix that results in a random matrix with a Wishart distribution. The ergodic attack performance is defined as the average attack performance obtained by taking the expectation with respect to the distribution of the training data set. The impact of the training data size on the ergodic attack performance is characterized by proposing an upper bound for the performance. Simulations on the IEEE 30-Bus test system show that the proposed bound is tight in practical settings.

Smart meters enable improvements in electricity distribution system efficiency at some cost in customer privacy. Users with home batteries can mitigate this privacy loss by applying charging policies that mask their underlying energy use. A battery charging policy is proposed and shown to provide universal privacy guarantees subject to a constraint on energy cost. The guarantee bounds our strategy's maximal information leakage from the user to the utility provider under general stochastic models of user energy consumption. The policy construction adapts coding strategies for non-probabilistic permuting channels to this privacy problem.

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

Attack detection problems in the smart grid are posed as statistical learning problems for different attack scenarios in which the measurements are observed in batch or online settings. In this approach, machine learning algorithms are used to classify measurements as being either secure or attacked. An attack detection framework is provided to exploit any available prior knowledge about the system and surmount constraints arising from the sparse structure of the problem in the proposed approach. Well-known batch and online learning algorithms (supervised and semisupervised) are employed with decision- and feature-level fusion to model the attack detection problem. The relationships between statistical and geometric properties of attack vectors employed in the attack scenarios and learning algorithms are analyzed to detect unobservable attacks using statistical learning methods. The proposed algorithms are examined on various IEEE test systems. Experimental analyses show that machine learning algorithms can detect attacks with performances higher than attack detection algorithms that employ state vector estimation methods in the proposed attack detection framework.

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.

The secrecy rate of Wyner wiretap channels is analyzed for general classes of sources, sensing schemes, and channel distributions. Using the replica method, heuristic closed form expressions are obtained for the asymptotic secrecy rate as a function of the statistics of the system model. This result is then applied in practically oriented scenarios, leading to expressions that expose the existing trade-offs between system parameters and security requirements, including the region in which perfect secrecy is feasible. As a particular example of the broad class of sources that are considered in the main contribution, source distributions giving rise to sparse signals are studied. In that setting, the secrecy rate linked to the disclosure of information about the support of the signals is investigated.

New methods that exploit sparse structures arising in smart grid networks are proposed for the state estimation problem when data injection attacks are present. First, construction strategies for unobservable sparse data injection attacks on power grids are proposed for an attacker with access to all network information and nodes. Specifically, novel formulations for the optimization problem that provide a flexible design of the trade-off between performance and false alarm are proposed. In addition, the centralized case is extended to a distributed framework for both the estimation and attack problems. Different distributed scenarios are proposed depending on assumptions that lead to the spreading of the resources, network nodes and players. Consequently, for each of the presented frameworks a corresponding optimization problem is introduced jointly with an algorithm to solve it. The validity of the presented procedures in real settings is studied through extensive simulations in the IEEE test systems.

The effect of prior knowledge when linear analog codes are used as joint source-channel codes for sources modeled as multivariate Gaussian processes is analyzed. We use information theoretic tools to evaluate the achievable performance gain obtained by exploiting prior knowledge. In order to assess the validity of linear codes in practical scenarios, where exact source statistics are not known, we study the effect of having partial knowledge of the statistics. We model the mismatch of the statistics as an additive perturbation matrix between the real covariance matrix and the postulated covariance matrix in the recovery process. In this setting, we obtain closed form expressions for a deterministic perturbation matrix and using random matrix theory tools we characterize the performance loss for i.i.d. random matrices.

In this paper, we provide an information-theoretic analysis of a Gaussian multiple-input multiple-output multiple access channel (MIMO MAC) with imperfect channel knowledge at the receiver. In particular, we derive inner and outer bounds for the MIMO MAC rate region when the inputs are Gaussian. We then apply these bounds to a Gaussian interference network with receiver cooperation, in which a central processor with incomplete channel state information must jointly decode all the received signals. Then, in the case where the channel knowledge at the receiver is obtained through training signals, we derive the structure of the optimum training signals for all users under a definite and semidefinite rank constraint. Numerical results show that the bounds we derive can be quite tight, confirming the asymptotic analysis conducted for the finite case. Finally, we also investigate the low-SNR and high-SNR regimes, specifically analyzing the minimum required energy per information bit and the wideband slope region in the first case, and the high-SNR slope in the second.

We present inner and outer bounds of the rate region for the multiple-input-multiple-output mutiple access channel with imperfect channel estimates. We then employ them to compare different channel estimation techniques. We show that the benefit of using traditional compressed sensing recovery techniques, specifically orthogonal matching pursuit, for multipath wireless channels is dominant for high signal to noise ratio regimes, but does not provide a good performance for low signal to noise ratio regime.

The distortion increase in minimum mean-square error (MMSE) estimation of multivariate Gaussian sources is analyzed for the situation in which the statistics are mismatched, i.e., the covariance matrix is not perfectly known during the estimation process. First a deterministic mismatch model with an additive perturbation matrix is considered, for which we provide closed form expressions for the distortion excess caused by the mismatch. The mismatch study is then generalized by using random matrix theory tools which allow an asymptotic result for a broad class of perturbation matrices to be proved.

The Burrows-Wheeler Transform (BWT) [1] is a block sorting algorithm which has been proven to be useful in compressing text data [2]. More recently, schemes based on the BWT have been proposed for lossless data compression using LDPC [3]-[5] and Fountain [6] codes, as well as for joint source-channel coding of sources with memory [7],[8]. In this paper we propose a source-controlled Turbo coding scheme for the transmission of sources with memory over AWGN channels also based on the Burrows-Wheeler Transform. Our approach combines the BWT with a Turbo code and employs different energy allocation techniques for the encoded symbols before their transmission. Simulation results show that the performance of the designed scheme is close (within 1.5 dB) to the theoretical Shannon limit.

Recent developments in compressed sensing have shown that if a signal can be compressed in some basis, then it can be reconstructed in such basis from a certain number of random projections. Distributed compressed sensing, where several correlated signals are compressed in a distributed manner, has also been proposed in the literature. By allowing additional distortion, successful recovery in distributed compressed sensing can be achieved even if the projections are corrupted by noise. We extend this result by showing that in addition to sparsity, it is possible to exploit prior knowledge existing in the correlation between the signals of interest to significantly improve reconstruction performance. This is done in a fashion resembling distributed coding of digital sources.

Recent developments in compressed sensing have shown that if a signal has a low Kolmogorov complexity, then it can be reconstructed from a certain number of random projections. We study the distributed coding of correlated Gaussian sources. Both intra- and inter-correlation models are considered in the source models. Decoding schemes in which it is possible to exploit the existing correlation between the signals of interest to significantly improve reconstruction performance are presented. This is done in a fashion resembling distributed coding of digital sources.

Recent developments in compressed sensing have shown that if a signal can be compressed in some basis, then it can be reconstructed in such basis from a certain number of random projections. Distributed compressed sensing, where several correlated signals are compressed in a distributed manner, has also been proposed in the literature. By allowing additional distortion, successful recovery in distributed compressed sensing can be achieved even if the projections are corrupted by noise. We extend this result by showing that in addition to sparsity, it is possible to exploit prior knowledge existing in the correlation between the signals of interest to significantly improve reconstruction performance. This is done in a fashion resembling distributed coding of digital sources.

It has been recently shown that if a, signal can be compressed in some basis, then it can be reconstructed in such basis from, a certain number of random, projections. By allowing additional distortion, this holds even if the projections are corrupted by noise. We extend this result by showing that it is possible to exploit prior knowledge (e.g., if the signal is a realization of a stochastic process,) to significantly improve reconstruction performance. This is done in a fashion resembling standard joint source-channel coding of digital sources. Moreover, the exploitation of such knowledge allows for reconstruction in bases where the signal is not sparse