Memristor crossbars enable vector-matrix multiplication (VMM), and are promising for low-power applications. However, it can be difficult to write the memristor conductance values exactly. To improve the accuracy of VMM, we propose a scheme based on low-rank matrix approximation. Specifically, singular value decomposition (SVD) is first applied to obtain a low-rank approximation of the target matrix, which is then factored into a pair of smaller matrices. Subsequently, a two-step serial VMM is executed, where the stochastic write errors are mitigated through step-wise averaging. To evaluate the performance of the proposed scheme, we derive a general expression for the resulting computation error and provide an asymptotic analysis under a prescribed singular-value profile, which reveals how the error scales with matrix size and rank. Both analytical and numerical results confirm the superiority of the proposed scheme compared with the benchmark scheme.

Consider a point-to-point communication system in which the transmitter holds a binary message of length $m$ and transmits a corresponding codeword of length $n$. The receiver's goal is to recover a Boolean function of that message, where the function is unknown to the transmitter, but chosen from a known class $F$. We are interested in the asymptotic relationship of $m$ and $n$: given $n$, how large can $m$ be (asymptotically), such that the value of the Boolean function can be recovered reliably? This problem generalizes the identification-via-channels framework introduced by Ahlswede and Dueck. We formulate the notion of computation capacity, and derive achievability and converse results for selected classes of functions $F$, characterized by the Hamming weight of functions. Our obtained results are tight in the sense of the scaling behavior for all cases of $F$ considered in the paper.

Compute-Forward Multiple Access (CFMA) is a multiple access transmission scheme based on Compute-and-Forward (CF), which allows the receiver to first decode linear combinations of the transmitted signals and then solve for individual messages. This paper extends the CFMA scheme to a two-user Gaussian multiple-input multiple-output (MIMO) multiple access channel (MAC). We propose the CFMA Serial Coding Scheme (SCS) and the CFMA Parallel Coding Scheme (PCS) with nested lattice codes. We first derive the expression of the achievable rate pair for MIMO MAC with CFMA-SCS. We prove a general condition under which CFMA-SCS can achieve the sum capacity of the channel. Furthermore, this result is specialized to single-input multiple-output (SIMO) and 2-by-2 diagonal MIMO multiple access channels, for which more explicit sum capacity-achieving conditions on power and channel matrices are derived. We then study the achievable rate of CFMA-PCS by using an equivalent SIMO model, and analyze its sum capacity-achieving conditions. Numerical results are provided for the performance of CFMA-SCS and CFMA-PCS in different channel conditions. In general, CFMA-PCS has better sum capacity achievability, although with a higher computational complexity for encoding and decoding.

We develop a unified Data Processing Inequality PAC-Bayesian framework—abbreviated DPI-PAC-Bayesian—for deriving the generalization error bounds in the supervised learning setting. By embedding the Data Processing Inequality (DPI) into the change-of-measure technique, we obtain explicit bounds on the binary Kullback-Leibler generalization gap for both Rényi divergence and any f-divergence measured between a data-independent prior distribution and an algorithm-dependent posterior distribution. We present three bounds derived under our framework using Rényi, Hellinger p and Chi-Squared divergences. Additionally, our framework also demonstrates a close connection with other well-known bounds. When the prior distribution is chosen to be uniform, our bounds recover to the classical Occam's Razor bound and, crucially, eliminate the extraneous $\log (2\sqrt n )/n$ slack present in the PAC-Bayes bound, thereby achieving tighter bounds. The framework thus bridges data-processing and PAC-Bayesian perspectives, providing a flexible, information-theoretic tool to construct generalization guarantees.

A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch - Pirare based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that zero storage overhead is achievable for tree-shaped databases. In particular, we develop TreePIR, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no storage redundancy. This type of tree has been widely implemented in many real-world systems such as Amazon DynamoDB, Google's Certificate Transparency, and blockchains. Tree nodes along a root-to-leaf path forms the well-known Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel et al. S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving 3 ×lower total storage and 1.5-3 ×lower computation and communication costs. Most notably, TreePIR has 8-160× lower setup time and its polylog-complexity indexing algorithm is 19–160 ×faster than PBC for trees of 210_224leaves.

We study communication over a Gaussian multiple-access channel (MAC) with two types of transmitters: Digital transmitters hold a message from a discrete set that needs to be communicated to the receiver with vanishing error probability. Analog transmitters hold sequences of analog values. Some functions of these distributed values (but not the values themselves) need to be conveyed to the receiver, subject to a fidelity criterion such as mean squared error (MSE) or a certain maximum error with given confidence. For the case in which the computed function for the analog transmitters is a sum of values in$[-1,1]$, we derive inner and outer bounds for the tradeoff of digital and analog rates of communication under peak and average power constraints for digital transmitters and a peak power constraint for analog transmitters. We then extend the achievability result to a class of functions that includes all linear and some non-linear functions. This extended scheme works over fading channels as long as full channel state information is available at the transmitter. The practicality of our proposed communication scheme is shown in channel simulations that use a version of the scheme based on low density parity check (LDPC) coding. We evaluate the system performance for different block lengths and Gaussian as well as non-Gaussian noise distributions.

The generalization error of a learning algorithm refers to the discrepancy between the loss of a learning algorithm on training data and that on unseen testing data. Various information-theoretic bounds on the generalization error have been derived in the literature, where the mutual information between the training data and the hypothesis (the output of the learning algorithm) plays an important role. Focusing on the individual sample mutual information bound by Bu et al. [2], which itself is a tightened version of the first bound on the topic by Russo et al. [3] and Xu et al. [4], this paper investigates the tightness of these bounds, in terms of the dependence of their convergence rates on the sample size n. It has been recognized that these bounds are in general not tight, readily verified for the exemplary quadratic Gaussian mean estimation problem, where the individual sample mutual information bound scales asO(√1/n) while the true generalization error scales asO(1/n). The first contribution of this paper is to show that the same bound can in fact be asymptotically tight if an appropriate assumption is made. In particular, we show that the fast rate can be recovered when the assumption is made on the excess risk instead of the loss function, which was usually done in existing literature. A theoretical justification is given for this choice. The second contribution of the paper is a new set of generalization error bounds based on the (η,c)-central condition, a condition relatively easy to verify and has the property that the mutual information term directly determines the convergence rate of the bound. Several analytical and numerical examples are given to show the effectiveness of these bounds.

Compute-forward multiple access (CFMA) is a transmission strategy which allows the receiver in a multiple access channel (MAC) to first decode linear combinations of the transmitted signals and then solve for individual messages. Compared to existing MAC strategies such as joint decoding or successive interference cancellation (SIC), CFMA was shown to achieve the MAC capacity region for fixed channels under certain signal-to-noise (SNR) conditions without time-sharing using only single-user decoders. This paper studies the CFMA scheme for a two-user Gaussian fast fading MAC with channel state information only available at the receiver (CSIR). We investigate appropriate lattice decoding schemes to decode linear combinations with any integer coefficients in the fading MAC and derive the achievable rate pairs. We give a sufficient and necessary condition under which the proposed scheme can achieve the ergodic sum capacity. Furthermore, we investigate the impact of channel statistics on the capacity achievability of the CFMA scheme. In general, the sum capacity is achievable if the channel variance is small compared to the mean value of the channel strengths. Various numerical results are presented to illustrate the theoretical findings.

Semi-supervised learning (SSL) aims to train a machine learning (ML) model using both labeled and unlabeled data. While the unlabeled data have been used in various ways to improve the prediction accuracy, the reason why unlabeled data could help is not fully understood. One interesting and promising direction is to understand SSL from a causal perspective. In light of the independent causal mechanisms (ICM) principle, the unlabeled data can be helpful when the label causes the features but not vice versa. However, the causal relations between the features and labels can be complex in real world applications. In this article, we propose an SSL framework that works with general causal models in which the variables have flexible causal relations. More specifically, we explore the causal graph structures and design corresponding causal generative models which can be learned with the help of unlabeled data. The learned causal generative model can generate synthetic labeled data for training a more accurate predictive model. We verify the effectiveness of our proposed method by empirical studies on both simulated and real data.

We study communication over a Gaussian multiple-access channel (MAC) with two types of transmitters: Digital transmitters hold a message from a discrete set that needs to be communicated to the receiver. Analog transmitters hold sequences of analog values, and some function of these distributed values (but not the values themselves) need to be conveyed to the receiver. For the digital messages, it is required that they can be decoded error free at the receiver with high probability while the recovered analog function values have to satisfy a fidelity criterion such as an upper bound on mean squared error (MSE) or a certain maximum error with a given confidence. For the case in which the computed function for the analog transmitters is a sum of values in [-1, 1], we derive inner and outer bounds for the tradeoff of digital and analog rates of communication under peak and average power constraints for digital transmitters and a peak power constraint for analog transmitters. We then extend the achievability part of our result to a larger class of functions that includes all linear, but also some non-linear functions.

Compute-forward multiple access (CFMA) is a transmission strategy which allows the receiver in a multiple access channel (MAC) to first decode linear combinations of the transmitted signals and then solve for individual messages. Compared to existing MAC strategies such as joint decoding or successive interference cancellation (SIC), CFMA was shown to achieve the MAC capacity region for fixed channels under certain signal-to-noise (SNR) conditions without time-sharing using only single-user decoders. This paper studies the CFMA scheme for a two-user Gaussian fast fading MAC with channel state information only available at the receiver (CSIR). We develop appropriate lattice decoding schemes for the fading MAC and derive the achievable rate pairs for decoding linear combinations of codewords with any integer coefficients. We give a sufficient and necessary condition under which the proposed scheme can achieve the ergodic sum capacity. Furthermore, we investigate the impact of channel statistics on the capacity achievability of the CFMA scheme. In general, the sum capacity is achievable if the channel variance is small compared to the mean value of the channel strengths. Various numerical results are presented to illustrate the theoretical findings.

Recent advancements in unsupervised domain adaptation (UDA) and semi-supervised learning (SSL), particularly incorporating causality, have led to significant methodological improvements in these learning problems. However, a formal theory that explains the role of causality in the generalization performance of UDA/SSL is still lacking. In this paper, we consider the UDA/SSL scenarios where we access $m$ labelled source data and $n$ unlabelled target data as training instances under different causal settings with a parametric probabilistic model. We study the learning performance (e.g., excess risk) of prediction in the target domain from an information-theoretic perspective. Specifically, we distinguish two scenarios: the learning problem is called causal learning if the feature is the cause and the label is the effect, and is called anti-causal learning otherwise. We show that in causal learning, the excess risk depends on the size of the source sample at a rate of $O(\frac{1}{m})$ only if the labelling distribution between the source and target domains remains unchanged. In anti-causal learning, we show that the unlabelled data dominate the performance at a rate of typically $O(\frac{1}{n})$. These results bring out the relationship between the data sample size and the hardness of the learning problem with different causal mechanisms.

Transfer learning, or domain adaptation, is concerned with machine learning problems in which training and testing data come from possibly different probability distributions. In this work, we give an information-theoretic analysis of the generalization error and excess risk of transfer learning algorithms. Our results suggest, perhaps as expected, that the Kullback-Leibler (KL) divergence$D(\mu \|\mu ')$plays an important role in the characterizations where$\mu $and$\mu '$denote the distribution of the training data and the testing data, respectively. Specifically, we provide generalization error and excess risk upper bounds for learning algorithms where data from both distributions are available in the training phase. Recognizing that the bounds could be sub-optimal in general, we provide improved excess risk upper bounds for a certain class of algorithms, including the empirical risk minimization (ERM) algorithm, by making stronger assumptions through the central condition. To demonstrate the usefulness of the bounds, we further extend the analysis to the Gibbs algorithm and the noisy stochastic gradient descent method. We then generalize the mutual information bound with other divergences such as$\phi $-divergence and Wasserstein distance, which may lead to tighter bounds and can handle the case when$\mu $is not absolutely continuous with respect to$\mu '$. Several numerical results are provided to demonstrate our theoretical findings. Lastly, to address the problem that the bounds are often not directly applicable in practice due to the absence of the distributional knowledge of the data, we develop an algorithm (called InfoBoost) that dynamically adjusts the importance weights for both source and target data based on certain information measures. The empirical results show the effectiveness of the proposed algorithm.

Hardware-limited task-based quantization is a new design paradigm for data acquisition systems equipped with scalar analog-to-digital converters using a small number of bits. By taking into account the system task, task-based quantizers can efficiently recover the desired parameters from the low-bit quantized observation. Current design and analysis frameworks for hardware-limited task-based quantization are only applicable to inputs with bounded support and uniform quantizers with non-subtractive dithering. In this paper, we propose a new framework based on generalized Bussgang decomposition that enables the design and analysis of hardware-limited task-based quantizers equipped with non-uniform scalar quantizers or have inputs with unbounded support. We consider the scenario in which the task is linear. Under this scenario, we derive new pre-quantization and post-quantization mappings for task-based quantizers with mean squared error (MSE) that closely matches the theoretical MSE.

We study the effectiveness of stochastic side information in deterministic online learning scenarios. We propose a forecaster to predict a deterministic sequence where its performance is evaluated against an expert class. We assume that certain stochastic side information is available to the forecaster but not the experts. We define the minimax expected regret for evaluating the forecaster’s performance, for which we obtain both upper and lower bounds. Consequently, our results characterize the improvement in the regret due to the stochastic side information. Compared with the classical online learning problem with regret scales with $O(\sqrt n )$, the regret can be negative when the stochastic side information is more powerful than the experts. To illustrate, we apply the proposed bounds to two concrete examples of different types of side information.

This paper examines the maximum code rate achievable by a data-driven communication system over some unknown discrete memoryless channel in the finite blocklength regime. A class of channel codes, called learning-based channel codes, is first introduced. Learning-based channel codes include a learning algorithm to transform the training data into a pair of encoding and decoding functions that satisfy some statistical reliability constraint. Data-dependent achievability and converse bounds in the non-asymptotic regime are established for this class of channel codes. It is shown analytically that the asymptotic expansion of the bounds for the maximum achievable code rate of the learning-based channel codes are tight for sufficiently large training data.

Compute-forward multiple access (CFMA) is a multiple access transmission scheme based on Compute-and-Forward (CF) which allows the receiver to first decode linear combinations of the transmitted signals and then solve for individual messages. This paper extends the CFMA scheme to a two-user Gaussian multiple-input multiple-output (MIMO) multiple access channel (MAC). We first derive the expression of the achievable rate pair for MIMO MAC with CFMA. We prove a general condition under which CFMA can achieve the sum capacity of the channel. Furthermore, this result is specialized to SIMO and 2-by-2 diagonal MIMO multiple access channels, for which more explicit sum capacity-achieving conditions on power and channel matrices are derived. Numerical results are also provided for the performance of CFMA on general MIMO multiple access channels.

Transfer learning is a machine learning paradigm where knowledge from one problem is utilized to solve a new but related problem. While conceivable that knowledge from one task could help solve a related task, if not executed properly, transfer learning algorithms can impair the learning performance instead of improving it – commonly known as negative transfer. In this paper, we use a parametric statistical model to study transfer learning from a Bayesian perspective. Specifically, we study three variants of transfer learning problems, instantaneous, online, and time-variant transfer learning. We define an appropriate objective function for each problem and provide either exact expressions or upper bounds on the learning performance using information-theoretic quantities, which allow simple and explicit characterizations when the sample size becomes large. Furthermore, examples show that the derived bounds are accurate even for small sample sizes. The obtained bounds give valuable insights into the effect of prior knowledge on transfer learning, at least with respect to our Bayesian formulation of the transfer learning problem. In particular, we formally characterize the conditions under which negative transfer occurs. Lastly, we devise several (online) transfer learning algorithms that are amenable to practical implementations, some of which do not require the parametric assumption. We demonstrate the effectiveness of our algorithms with real data sets, focusing primarily on when the source and target data have strong similarities.

This paper studies a linear physical-layer network coding multiple access (LPNC-MA) scheme that is capable of achieving any rate-tuples in the MAC capacity region without receiver-iterations or time-sharing. We propose to utilize q-ary irregular repeat accumulate (IRA) codes over finite integer field-s/rings and q-PAM as the underlying coded-modulation. The receiver sequentially computes M network coded (NC) message sequences, where the previously computed message sequence is used as side information in computing subsequent ones. All users’ messages are then recovered by solving the computed M NC messages via the inverse of the NC coefficient matrix. A joint nested code construction and EXIT chart based code optimization method is developed, yielding near-capacity performance (within 1.1 dB the capacity limit for three users). For fading MAC, we propose a pragmatic method for identifying the network coding coefficient matrix that maximizes the mutual information. Numerical results demonstrate that the frame error rate (FER) of LPNC-MA is within a fraction of dB the outage probability of fading MAC capacity. For a relatively large number of users, it is shown that LPNC-MA remarkably outperforms NOMA-SIC and IDMA in the high spectral efficiency regime, while avoiding the big-loop receiver iteration.

Lagrange coded computation (LCC) is essential to solving problems about matrix polynomials in a coded distributed fashion; nevertheless, it can only solve the problems that are representable as matrix polynomials. In this paper, we propose AICC, an AI-aided learning approach that is inspired by LCC but also uses deep neural networks (DNNs). It is appropriate for coded computation of more general functions. Numerical simulations demonstrate the suitability of the proposed approach for the coded computation of different matrix functions that are often utilized in digital signal processing.

A recent line of works, initiated by [1] and [2], has shown that the generalization error of a learning algorithm can be upper bounded by information measures. In most of the relevant works, the convergence rate of the expected generalization error is in the form of $O(\sqrt {\lambda I/n} )$ where λ is an assumption-dependent coefficient and I is some information-theoretic quantities such as the mutual information between the data sample and the learned hypothesis. However, such a learning rate is typically considered to be "slow", compared to a "fast rate" of O(1 /n) in many learning scenarios. In this work, we first show that the square root does not necessarily imply a slow rate, and a fast rate result can still be obtained using this bound by evaluating λ under an appropriate assumption. Furthermore, we identify the key conditions needed for the fast rate generalization error, which we call the ( η, c)-central condition. Under this condition, we give information-theoretic bounds on the generalization error and excess risk, with a convergence rate of O (1 /n) for specific learning algorithms such as empirical risk minimization. Finally, analytical examples are given to show the effectiveness of the bounds.

The polar receiver architecture is a receiver design that captures the envelope and phase information of the signal rather than its in-phase and quadrature components. Several studies have demonstrated the robustness of polar receivers to phase noise and other nonlinearities. Yet, the information-theoretic limits of polar receivers with finite-precision quantizers have not been investigated in the literature. The main contribution of this work is to identify the optimal signaling strategy for the additive white Gaussian noise (AWGN) channel with polar quantization at the output. More precisely, we show that the capacity-achieving modulation scheme has an amplitude phase shift keying (APSK) structure. Using this result, the capacity of the AWGN channel with polar quantization at the output is established by numerically optimizing the probability mass function of the amplitude. The capacity of the polar-quantized AWGN channel with$b_{1}$-bit phase quantizer and optimized single-bit magnitude quantizer is also presented. Our numerical findings suggest the existence of signal-to-noise ratio (SNR) thresholds, above which the number of amplitude levels of the optimal APSK scheme and their respective probabilities change abruptly. Moreover, the manner in which the capacity-achieving input evolves with increasing SNR depends on the number of phase quantization bits.

The use of 1-bit analog-to-digital converters (ADCs) is seen as a promising approach to significantly reduce the power consumption and hardware cost of multiple-input multiple-output (MIMO) receivers. However, the nonlinear distortion due to 1-bit quantization fundamentally changes the optimal communication strategy and also imposes a capacity penalty to the system. In this paper, the capacity of a Gaussian MIMO channel in which the antenna outputs are processed by an analog linear combiner and then quantized by a set of zero threshold ADCs is studied. A new capacity upper bound for the zero threshold case is established that is tighter than the bounds available in the literature. In addition, we propose an achievability scheme which configures the analog combiner to create parallel Gaussian channels with phase quantization at the output. Under this class of analog combiners, an algorithm is presented that identifies the analog combiner and input distribution that maximize the achievable rate. Numerical results are provided showing that the rate of the achievability scheme is tight in the low signal-to-noise ratio (SNR) regime. Finally, a new 1-bit MIMO receiver architecture which employs analog temporal and spatial processing is proposed. The proposed receiver attains the capacity in the high SNR regime.

Several information-theoretic studies on channels with output quantization have identified the capacity-achieving input distributions for different fading channels with 1-bit in-phase and quadrature (I/Q) output quantization. However, an exact characterization of the capacity-achieving input distribution for channels with multi-bit phase quantization has not been provided. In this paper, we consider four different channel models with multi-bit phase quantization at the output and identify the optimal input distribution for each channel model. We first consider a complex Gaussian channel with$b$-bit phase-quantized output and prove that the capacity-achieving distribution is a rotated$2^{b}$-phase shift keying (PSK). The analysis is then extended to multiple fading scenarios. We show that the optimality of rotated$2^{b}$-PSK continues to hold under noncoherent fast fading Rician channels with$b$-bit phase quantization when line-of-sight (LoS) is present. When channel state information (CSI) is available at the receiver, we identify$\frac {2\pi }{2^{b}}$-symmetry and constant amplitude as the necessary and sufficient conditions for the ergodic capacity-achieving input distribution; which a$2^{b}$-PSK satisfies. Finally, an optimum power control scheme is presented which achieves ergodic capacity when CSI is also available at the transmitter.

This paper establishes the capacity of additive white Gaussian noise (AWGN) channels with phase-quantized output. We show that a rotated$2^{b}$-phase shift keying scheme is the capacity-achieving input distribution for a complex AWGN channel with b-bit phase quantization. The result is then used to establish the expression for the channel capacity as a function of average power constraint$P$and quantization bits$b$. The outage performance of phase-quantized system is also investigated for the case of Rayleigh fading when the channel state information (CSI) is only known at the receiver. Our findings suggest the existence of a threshold in the rate$R$, above which the outage exponent of the outage probability changes abruptly. In fact, this threshold effect in the outage exponent causes$2^{b}$-PSK to have suboptimal outage performance at high SNR.

Transfer learning is a machine learning paradigm where the knowledge from one task is utilized to resolve the problem in a related task. On the one hand, it is conceivable that knowledge from one task could be useful for solving a related problem. On the other hand, it is also recognized that if not executed properly, transfer learning algorithms could in fact impair the learning performance instead of improving it - commonly known as negative transfer. In this paper, we study the online transfer learning problems where the source samples are given in an off-line way while the target samples arrive sequentially. We define the expected regret of the online transfer learning problem, and provide upper bounds on the regret using information-theoretic quantities. We also obtain exact expressions for the bounds when the sample size becomes large. Examples show that the derived bounds are accurate even for small sample sizes. Furthermore, the obtained bounds give valuable insight on the effect of prior knowledge for transfer learning in our formulation. In particular, we formally characterize the conditions under which negative transfer occurs.

We analyze the symbol error probability (SEP) of$M$-ary pulse amplitude modulation ($M$-PAM) receivers equipped with optimal low-resolution quantizers. We first show that the optimum detector can be reduced to a simple decision rule. Using this simplification, an exact SEP expression for quantized$M$-PAM receivers is obtained when Nakagami-$m$fading channel is considered. The derived expression enables the optimization of the quantizer and/or constellation under the minimum SEP criterion. Our analysis of optimal quantization for equidistant$M$-PAM receiver reveals the existence of error floor which decays at a double exponential rate with increasing quantization bits,$b$. Moreover, by also allowing the transmitter to optimize the constellation based on the statistics of the fading channel, we prove that the error floor can be eliminated but at a lower decay exponent than the unquantized case. Characterization of this decay exponent is provided in this paper. We also expose the outage performance limitations of SEP-optimal uniform quantizers. To be more precise, its decay exponent does not improve with$b$. Lastly, we demonstrate that the decay exponent of a quantized receiver can be complemented by receive antenna diversity techniques.

Transfer learning, or domain adaptation, is concerned with machine learning problems in which training and testing data come from possibly different distributions (denoted as μ and μ', respectively). In this work, we give an informationtheoretic analysis on the generalization error and the excess risk of transfer learning algorithms, following a line of work initiated by Russo and Zhou. Our results suggest, perhaps as expected, that the Kullback-Leibler (KL) divergence D(μ||μ') plays an important role in characterizing the generalization error in the settings of domain adaptation. Specifically, we provide generalization error upper bounds for general transfer learning algorithms, and extend the results to a specific empirical risk minimization (ERM) algorithm where data from both distributions are available in the training phase. We further apply the method to iterative, noisy gradient descent algorithms, and obtain upper bounds which can be easily calculated, only using parameters from the learning algorithms. A few illustrative examples are provided to demonstrate the usefulness of the results. In particular, our bound is tighter in specific classification problems than the bound derived using Rademacher complexity.

Semi-supervised learning algorithms attempt to take advantage of relatively inexpensive unlabeled data to improve learning performance. In this work, we consider statistical models where the data distributions can be characterized by continuous parameters. We show that under certain conditions on the distribution, unlabeled data is equally useful as labeled date in terms of learning rate. Specifically, let $n, m$ be the number of labeled and unlabeled data, respectively. It is shown that the learning rate of semi-supervised learning scales as $O(1/n)$ if $m\sim n$, and scales as $O(1/n^{1+\gamma})$ if $m\sim n^{1+\gamma}$ for some $\gamma>0$, whereas the learning rate of supervised learning scales as $O(1/n)$. (Note: this version contains an error in the proof of Lemma~2. A corrected version is available on arXiv)

We present a practical strategy that aims to attain rate points on the dominant face of the multiple access channel capacity using a standard low complexity decoder. This technique is built upon recent theoretical developments of Zhu and Gastpar on compute-forward multiple access which achieves the capacity of the multiple access channel using a sequential decoder. We illustrate this strategy with off-the-shelf LDPC codes. In the first stage of decoding, the receiver first recovers a linear combination of the transmitted codewords using the sum-product algorithm (SPA). In the second stage, by using the recovered sum-of-codewords as side information, the receiver recovers one of the two codewords using a modified SPA, ultimately recovering both codewords. The main benefit of recovering the sum-of-codewords instead of the codeword itself is that it allows to attain points on the dominant face of the multiple access channel capacity without the need of rate-splitting or time sharing while maintaining a low complexity in the order of a standard point-to-point decoder. This property is also shown to be crucial for some applications, e.g., interference channels. For all the simulations with single-layer binary codes, our proposed practical strategy is shown to be within 1.7 dB of the theoretical limits, without explicit optimization on the off-the-self LDPC codes.

Computation codes in network information theory are designed for scenarios where the decoder is not interested in recovering the information sources themselves, but only a function thereof. Körner and Marton showed for distributed source coding (DSC) that such function decoding can be achieved more efficiently than decoding the full information sources. Compute-forward has shown that function decoding, in combination with network coding ideas, is a useful building block for end-to-end communication over a network. In both cases, good computation codes are the key component in the coding schemes. Could these same codes simultaneously also enable full message decoding over a sufficiently strong multiple-access channel (MAC)? This work establishes a partial negative answer and converse result. Specifically, for any code that is known to be a good computation code for some MAC, we characterize a class of MACs for which that code cannot enable full message decoding (and vice versa). Finally, an analogous duality result is established for a related DSC problem.

Inspired by the compute-and-forward scheme from Nazer and Gastpar, a novel multiple-access scheme introduced by Zhu and Gastpar makes use of nested lattice codes and sequential decoding of linear combinations of codewords to recover the individual messages. This strategy, coined compute-forward multiple access (CFMA), provably achieves points on the dominant face of the multiple-access capacity region while circumventing the need of time sharing or rate splitting. For a two-user multiple-access channel (MAC), we propose a practical procedure to design suitable codes from off-the-shelf LDPC codes and present a sequential belief propagation decoder with complexity comparable with that of point-to-point decoders. We demonstrate the potential of our strategy by comparing several numerical evaluations with theoretical limits.

Lattice codes used under the compute-and-forward paradigm suggest an alternative strategy for the standard Gaussian multiple-access channel (MAC): the receiver successively decodes the integer linear combinations of the messages until it can invert and recover all messages. In this paper, a multiple-access technique called compute-forward multiple access (CFMA) is proposed and analyzed. For the two-user MAC, it is shown that without time-sharing, the entire capacity region can be attained using CFMA with a single-user decoder as soon as the signal-to-noise ratios are above √1+ 2. A partial analysis is given for more than two users. Finally, the strategy is extended to the so-called dirty MAC, where two interfering signals are known non-causally to the two transmitters in a distributed fashion. Our scheme extends the previously known results and gives new achievable rate regions.

The usefulness of lattice codes is investigated for two-user Gaussian interference channels (IC). A coding scheme based on the compute-and-forward technique is shown to achieve the capacity region of the Gaussian IC under strong interference. The proposed scheme uses single-user decoders whereas the conventional scheme uses multi-user decoders for simultaneous decoding. The same scheme is applicable to the Gaussian Z-interference channel. A lattice-based coding scheme is also devised for the state-dependent Gaussian IC with the state sequence non-causally known to transmitters. The proposed scheme establishes new achievable rate regions, which can be considerably larger than the best known results, especially when the interfering state sequence has very large power.

The classical modulo-lattice construction of Erez et al. has been successfully applied to several coding problems under Gaussian noise, including coding for computation over multiple-access channels (MAC). For the latter problem, an alternative construction can be developed by extending a recently proposed nested linear code to Gaussian case. In this note, it is shown that using the nested linear code with judiciously chosen input distributions, the original compute-and-forward result is recovered and larger computation rates are achievable. In particular we show that the Gaussian input distribution is not optimal in general for the computation problem over Gaussian MAC. Among other results, new achievable rates for the Gaussian two-way relay channel (TWRC) are given.

A new achievable rate region is given for the Gaussian cognitive many-to-one interference channel. The proposed novel coding scheme is based on the compute-and-forward approach with lattice codes. Using the idea of decoding sums of codewords, our scheme improves considerably upon the conventional coding schemes which treat interference as noise or decode messages simultaneously. Our strategy also extends directly to the usual many-to-one interference channels without cognitive messages. Comparing to the usual compute-and-forward scheme where a fixed lattice is used for the code construction, the novel scheme employs scaled lattices and also encompasses key ingredients of the existing schemes for the cognitive interference channel. With this new component, our scheme achieves a larger rate region in general. For some symmetric channel settings, new constant gap or capacity results are established, which are independent of the number of users in the system.

Lattice codes are applied to the two-user Gaussian multiple access channel (MAC) combined with a modified compute-and-forward transmitting scheme. It is shown that non-corner points on the boundary of the capacity region can be achieved by decoding two integer sums of the codewords, which can be viewed as a generalization of the well-known successive cancellation decoding. A similar idea is then applied to the so-called dirty MAC where two interfering signals are known non-causally to the two transmitters in a distributed fashion. Our scheme recovers previously known results and gives new achievable rate regions. The proposed scheme can be extended to the case with more than two users.

In this work we consider the cognitive many-to-one interference network. We first extend existing coding schemes from the two-user case to this network scenario. Then we present a novel coding scheme using compute-and-forward and show it can enlarge the achievable rate region considerably for a wide range of parameters. Numerical evaluations are given to compare the performance of different schemes. Specializing the results to symmetric settings, for a range of parameters, our achievable rate region is shown to be within a constant gap from capacity, regardless of the number of cognitive users.