Self-training is a classical approach in semi-supervised learning which is successfully applied to a variety of machine learning problems. Self-training algorithms generate pseudo-labels for the unlabeled examples and progressively refine these pseudo-labels which hopefully coincides with the actual labels. This work provides theoretical insights into self-training algorithms with a focus on linear classifiers. First, we provide a sample complexity analysis for Gaussian mixture models with two components. This is established by sharp non-asymptotic characterization of the self-training iterations which captures the evolution of the model accuracy in terms of a fixed-point iteration. Our analysis reveals the provable benefits of rejecting samples with low confidence and demonstrates how self-training iterations can gracefully improve the model accuracy. Secondly, we study a generalized GMM where the component means follow a distribution. We demonstrate that ridge regularization and class margin (i.e. separation between the component means) is crucial for the success and lack of regularization may prevent self-training from identifying the core features in the data.

We consider a novel multi-armed bandit setup in which the reward distribution of each arm depends on a single discrete Markov process. This setup involves correlation among arms, as well as correlation among each time instant when one of the arms is pulled. For this problem we show that the cumulative regret has to grow linearly with the number of instances where the outcome of the previous arm pull cannot be determined uniquely. We propose an algorithm relying on the empirical transition matrix and analyze its performance. The algorithm is shown to minimize the contribution of regret for the time instances where the outcome of the previous arm pull can be identified uniquely. This implies that the algorithm performs order-wise optimally. We experimentally show that our algorithm can perform better than the correlated-UCB algorithm introduced by Gupta et. al. in 2018 and the classical UCB algorithm.

We address the problem of repairing a failed node of a distributed storage system (DSS) in a secure way. We require the information leakage to the helper nodes and the information gained by the repaired node except for its lost content are both zero. We consider the Reed-Solomon code construction of Tamo et al., 2017 which achieves the cut-set bound. For this DSS setup, we propose a secure node repair algorithm and show that it performs near to optimal in terms of the bandwidth when the rate of RS code is low.

We consider the problem of representing a finite energy signal with a finite number of samples. When the signal is interpolated via sinc function from the samples, there will be a certain reconstruction error since only a finite number of samples are used. Without making any additional assumptions, we derive a lower bound for this error. This error bound depends on the number of samples but nothing else, and is thus represented as a universal curve of error versus number of samples. Furthermore, the existence of a function that achieves the bound shows that this is the tightest such bound possible.

It is known that polar codes can be efficiently constructed for binary-input channels. At the same time, existing algorithms for general input alphabets are less practical because of high complexity. We address the construction problem for the general case, and analyze an algorithm that is based on successive reduction of the output alphabet size of the subchannels in each recursion step. For this procedure, we estimate the approximation error as O(μ-1/(q-1)), where q is the input alphabet size and μ is the “quantization parameter,” i.e., the maximum size of the subchannel output alphabet allowed by the algorithm. The complexity of the code construction scales as O(N μ2log μ), where N is the length of the code. We also show that if the polarizing operation relies on modulo-q addition, it is possible to merge subsets of output symbols without any loss in subchannel capacity. Performing this procedure before each approximation step results in a further speed-up of the code construction, and the resulting codes have smaller gap to capacity. We also show that a similar acceleration can be attained for polar codes over finite field alphabets. Experimentation shows that the suggested construction algorithms can be used to construct long polar codes for alphabets of size q = 16 and more with acceptable loss of the code rate for a variety of polarizing transforms.

The wiretap channel model of Wyner is one of the first communication models with both reliability and security constraints. Capacity-achieving schemes for various models of the wiretap channel have received considerable attention in recent literature. In this paper, we show that capacity of the general (not necessarily degraded or symmetric) wiretap channel under a “strong secrecy constraint” can be achieved using a transmission scheme based on polar codes. We also extend our construction to the case of broadcast channels with confidential messages defined by Csiszár and Körner, achieving the entire capacity region of this communication model.