Graph clustering is a central topic in unsupervised learning with a multitude of practical applications. In recent years, multi-view graph clustering has gained a lot of attention for its applicability to real-world instances where one often has access to multiple data sources. In this paper we formalize a new family of models, called multi-view stochastic block models that capture this setting. For this model, we first study efficient algorithms that naively work on the union of multiple graphs. Then, we introduce a new efficient algorithm that provably outperforms previous approaches by analyzing the structure of each graph separately. Finally, we complement our results with an information-theoretic lower bound studying the limits of what can be done in this model.

We consider estimation models of the form Y = X* + N, where X* is some m-dimensional structured signal we wish to recover, and N is symmetrically distributed noise that may be unbounded in all but a small α fraction of the entries. This setting captures problems such as (sparse) linear regression, (sparse) principal component analysis (PCA), and tensor PCA, even in the presence of oblivious outliers and heavy-tailed noise. We introduce a family of algorithms that under mild assumptions recover the signal X* in all estimation problems for which there exists a sum-of-squares algorithm that succeeds in recovering the signal X* when the noise N is Gaussian. This essentially shows that it is enough to design a sum-of-squares algorithm for an estimation problem with Gaussian additive noise in order to get the algorithm that works with the symmetric noise model. Our framework extends far beyond previous results on symmetric noise models and is even robust to an ε-fraction of adversarial perturbations. As concrete examples, we investigate two problems for which no efficient algorithms were known to work for heavy-tailed noise: tensor PCA and sparse PCA. For the former, our algorithm recovers the principal component in polynomial time when the signal-to-noise ratio is at least Õ(np/4/ α), that matches (up to logarithmic factors) current best known algorithmic guarantees for Gaussian noise. For the latter, our algorithm runs in quasipolynomial time and matches the state-of-the-art guarantees for quasipolynomial time algorithms in the case of Gaussian noise. Using a reduction from the planted clique problem, we provide evidence that the quasipolynomial time is likely to be necessary for sparse PCA with symmetric noise. In our proofs we use bounds on the covering numbers of sets of pseudo-expectations, which we obtain by certifying in sum-of-squares upper bounds on the Gaussian complexities of sets of solutions. This approach for bounding the covering numbers of sets of pseudo-expectations may be interesting in its own right and may find other application in future works. * This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 815464).

We give tight statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. In particular, suppose that all labels are corrupted with probability at most $\eta$. We show that for arbitrary $\eta \in [0,1/2]$ every SQ algorithm achieving misclassification error better than $\eta$ requires queries of superpolynomial accuracy or at least a superpolynomial number of queries. Further, this continues to hold even if the information-theoretically optimal error $\OPT$ is as small as $\exp\Paren{-\log^c(d)}$, where $d$ is the dimension and $0 < c < 1$ is an arbitrary absolute constant, and an overwhelming fraction of examples are noiseless. Our lower bound matches known polynomial time algorithms, which are also implementable in the SQ framework. Previously, such lower bounds only ruled out algorithms achieving error $\OPT + \e$ or error better than $\Omega(\eta)$ or, if $\eta$ is close to $1/2$, error $\eta - o_\eta(1)$, where the term $o_\eta(1)$ is constant in $d$ but going to 0 for $\eta$ approaching $1/2$. As a consequence, we also show that achieving misclassification error better than $1/2$ in the $(A,\alpha)$-Tsybakov model is SQ-hard for $A$ constant and $\alpha$ bounded away from 1.

We study the probability distribution of age of information (AoI) in arbitrary networks with memoryless service times. A source node generates packets following a Poisson process, and then the packets are forwarded across the network in such a way that newer updates preempt older ones. This model is equivalent to gossip networks that were recently studied by Yates, and for which he obtained a recursive formula allowing the computation for the average AoI. In this paper, we obtain a very simple characterization of the stationary distribution of AoI at every node in the network. This allows for the computation of the average of an arbitrary function of the age, such as the age-violation probabilities. Furthermore, we show how our simple characterization can yield substantial reductions in the computation time of average AoIs in some structured networks. Finally, we describe how it can yield faster and more accurate Monte Carlo simulations estimating the average AoI, or the average of an arbitrary function of the age.

Previous works on age of information and erasure channels have dealt with specific models and computed the average age or average peak age for certain settings. In this paper, given a source that produces a letter every$T_{s}$seconds and an erasure channel that can be used every$T_{c}$seconds, we ask what is the coding strategy that minimizes the time-average “age of information” that an observer of the channel output incurs. We first analyze the case where the source alphabet and the channel-input alphabet have the same size. We show that a trivial coding strategy is optimal and a closed form expression for the age can be derived. We then analyze the case where the alphabets have different sizes. We use a random coding argument to bound the average age and show that the average age achieved using random codes converges to the optimal average age of linear block codes as the source alphabet becomes large.

We develop an efficient algorithm for weak recovery in a robust version of the stochastic block model. The algorithm matches the statistical guarantees of the best known algorithms for the vanilla version of the stochastic block model. In this sense, our results show that there is no price of robustness in the stochastic block model. Our work is heavily inspired by recent work of Banks, Mohanty, and Raghavendra (SODA 2021) that provided an efficient algorithm for the corresponding distinguishing problem. Our algorithm and its analysis significantly depart from previous ones for robust recovery. A key challenge is the peculiar optimization landscape underlying our algorithm: The planted partition may be far from optimal in the sense that completely unrelated solutions could achieve the same objective value. This phenomenon is related to the push-out effect at the BBP phase transition for PCA. To the best of our knowledge, our algorithm is the first to achieve robust recovery in the presense of such a push-out effect in a non-asymptotic setting. Our algorithm is an instantiation of a framework based on convex optimization (related to but distinct from sum-of-squares), which may be useful for other robust matrix estimation problems. A by-product of our analysis is a general technique that boosts the probability of success (over the randomness of the input) of an arbitrary robust weak-recovery algorithm from constant (or slowly vanishing) probability to exponentially high probability.

We develop machinery to design efficiently computable and \emph{consistent} estimators, achieving estimation error approaching zero as the number of observations grows, when facing an oblivious adversary that may corrupt responses in all but an $\alpha$ fraction of the samples.As concrete examples, we investigate two problems: sparse regression and principal component analysis (PCA).For sparse regression, we achieve consistency for optimal sample size $n\gtrsim (k\log d)/\alpha^2$ and optimal error rate $O(\sqrt{(k\log d)/(n\cdot \alpha^2)})$where $n$ is the number of observations, $d$ is the number of dimensions and $k$ is the sparsity of the parameter vector, allowing the fraction of inliers to be inverse-polynomial in the number of samples.Prior to this work, no estimator was known to be consistent when the fraction of inliers $\alpha$ is $o(1/\log \log n)$, even for (non-spherical) Gaussian design matrices.Results holding under weak design assumptions and in the presence of such general noise have only been shown in dense setting (i.e., general linear regression) very recently by d'Orsi et al.~\cite{ICML-linear-regression}.In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix (usually used in matrix completion). Previous works could obtain non-trivial guarantees only under the assumptions that the measurement noise corresponding to the inliers is polynomially small in $n$ (e.g., Gaussian with variance $1/n^2$).To devise our estimators, we equip the Huber loss with non-smooth regularizers such as the $\ell_1$ norm or the nuclear norm, and extend d'Orsi et al.'s approach~\cite{ICML-linear-regression} in a novel way to analyze the loss function.Our machinery appears to be easily applicable to a wide range of estimation problems.We complement these algorithmic results with statistical lower bounds showing that the fraction of inliers that our PCA estimator can deal with is optimal up to a constant factor.

Given a source that produces a letter every Tsseconds and an erasure channel that can be used every Tcseconds, we ask what is the coding strategy that minimizes the time-average "age of information" that an observer of the channel output incurs. We will see that one has to distinguish the cases when the source and channel-input alphabets have equal or different size. In the first case, we show that a trivial coding strategy is optimal and a closed form expression for the age may be derived. In the second, we use random coding argument to bound the average age and show that the average age achieved using random codes converges to the optimal average age as the source alphabet becomes large.

It is known that if an Abelian group operation is used in an Arıkan-style construction, multilevel polarization occurs. An open problem in polarization theory is to determine the polarization levels of a given channel. In this paper, we discuss the polarization levels of a family of channels that we call automorphic-symmetric channels. We show that the polarization levels of an automorphic-symmetric channel are determined by characteristic subgroups. In particular, if the group that is used does not contain any non-trivial characteristic subgroup, we only have two-level polarization to almost perfect and almost useless channels.

Let W be a channel where the input alphabet is endowed with an Abelian group operation, and let (Wn)n≥0be Arıkan's channel-valued polarization process that is obtained from W using this operation. We prove that the process (Wn)n≥0converges almost surely to deterministic homomorphism channels in the noisiness/weak-* topology. This provides a simple proof of multilevel polarization for a large family of channels, containing among others, discrete memoryless channels (DMC), and channels with continuous output alphabets. This also shows that any continuous channel functional converges almost surely (even if it does not induce a submartingale or a supermartingale).

Consider a stream of status updates generated by a source, where each update is of one of two types: priority or ordinary; these updates are to be transmitted through a network to a monitor. We analyze a transmission policy that treats updates depending on their content: ordinary updates are served in a first-come first-served fashion, whereas the priority updates receive preferential treatment. An arriving priority update discards and replaces any currently-in-service priority update, and preempts (with eventual resume) any ordinary update. We model the arrival processes of the two kinds of updates as independent Poisson processes and the service times as two (possibly different rate) exponentials. We find the arrival and service rates under which the system is stable and give closed-form expressions for average peak age and a lower bound on the average age of the ordinary stream. We give numerical results on the average age of both streams and observe the effect of each stream on the age of the other.

The ordering of communication channels was first introduced by Shannon. In this paper, we aim to find characterizations of two orderings: input-degradedness and the Shannon ordering. A channel W is said to be input-degraded from another channel W' if W can be simulated from W' by randomization at the input. We provide a necessary and sufficient condition for a channel to be input-degraded from another one. We show that any decoder that is good for W is also good for W'. We provide two characterizations for input-degradedness, one of which is similar to the Blackwell-Sherman-Stein theorem. We show that W' contains W (in the Shannon ordering sense) if and only if W is the skew-composition of W' with a convex-product n channel. This fact is used to derive a characterization of the Shannon ordering that is similar to the Blackwell-Sherman-Stein theorem.

We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation, and an Arıkan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary cq multiple access channels. The encoder can be implemented inO(NlogN) operations, whereNis the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than 2(-N)βfor any β <; (1/2).

The ordering of communication channels was first introduced by Shannon. In this paper, we aim to find a characterization of the Shannon ordering. We show that W' contains W if and only if W is the skew-composition of W' with a convex-product channel. This fact is used to derive a characterization of the Shannon ordering that is similar to the Blackwell-Sherman-Stein theorem. Two channels are said to be Shannon-equivalent if each one is contained in the other. We investigate the topologies that can be constructed on the space of Shannon-equivalent channels. We introduce the strong topology and the BRM metric on this space. Finally, we study the continuity of a few channel parameters and operations under the strong topology.

A channel W is said to be input-degraded from another channel W' if W can be simulated from W' by randomization at the input. We provide a necessary and sufficient condition for a channel to be input-degraded from another one. We show that any decoder that is good for W' is also good for W. We provide two characterizations for input-degradedness, one of which is similar to the Blackwell-Sherman-Stein theorem. We say that two channels are input-equivalent if they are input-degraded from each other. We study the topologies that can be constructed on the space of input-equivalent channels, and we investigate their properties. Moreover, we study the continuity of several channel parameters and operations under these topologies.

Two channels are said to be equivalent if they are degraded from each other. The space of equivalent channels with input alphabet X and output alphabet Y can be naturally endowed with the quotient of the Euclidean topology by the equivalence relation. We show that this topology is compact, path-connected and metrizable. A topology on the space of equivalent channels with fixed input alphabet X and arbitrary but finite output alphabet is said to be natural if and only if it induces the quotient topology on the subspaces of equivalent channels sharing the same output alphabet. We show that every natural topology is σ-compact, separable and path-connected. On the other hand, if |X| ≥ 2, a Hausdorff natural topology is not Baire and it is not locally compact anywhere. This implies that no natural topology can be completely metrized if |X| ≥ 2. The finest natural topology, which we call the strong topology, is shown to be compactly generated, sequential and T4. On the other hand, the strong topology is not first-countable anywhere, hence it is not metrizable. We show that in the strong topology, a subspace is compact if and only if it is rank-bounded and strongly-closed. We provide a necessary and sufficient condition for a sequence of channels to converge in the strong topology. We introduce a metric distance on the space of equivalent channels which compares the noise levels between channels. The induced metric topology, which we call the noisiness topology, is shown to be natural. We also study topologies that are inherited from the space of meta-probability measures by identifying channels with their Blackwell measures. We show that the weak-* topology is exactly the same as the noisiness topology and hence it is natural. We prove that if |X| ≥ 2, the total variation topology is not natural nor Baire, hence it is not completely metrizable. Moreover, it is not locally compact anywhere. Finally, we show that the Borel σ-algebra is the same for all Hausdorff natural topologies.

We study the continuity of several channel parameters and operations under various topologies on the space of equivalent discrete memoryless channels (DMC). We show that mutual information, channel capacity, Bhattacharyya parameter, probability of error of a fixed code, and optimal probability of error for a given code rate and blocklength, are continuous under various DMC topologies. We also show that channel operations such as sums, products, interpolations, and Arikan-style transformations are continuous.

We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation and an Arikan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary classical-quantum multiple access channels (cq-MAC). The encoder can be implemented in O(N log N) operations, where N is the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than 2-Nβfor any β <; ½.

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (second) part provides a foundation of polarization theory based on the ergodic theory of binary operations which we developed in the first part. We show that a binary operation is polarizing if and only if it is uniformity preserving and its right-inverse is strongly ergodic. The rate of polarization of single user channels is studied. It is shown that the exponent of any polarizing operation cannot exceed 1/2, which is the exponent of quasi-group operations. We also study the polarization of multiple access channels (MAC). In particular, we show that a sequence of binary operations is MAC-polarizing if and only if each binary operation in the sequence is polarizing. It is shown that the exponent of any MAC-polarizing sequence cannot exceed 1/2, which is the exponent of sequences of quasi-group operations.

One problem with multiple access channel (MAC) polar codes that are based on MAC polarization is that they may not achieve the entire capacity region. The reason behind this problem is that MAC polarization sometimes induces a loss in the capacity region. This paper provides a single letter necessary and sufficient condition, which characterizes all the MACs that do not lose any part of their capacity region by polarization.

We consider a scenario where a monitor is interested in being up to date with respect to the status of some system which is not directly accessible to this monitor. However, we assume a source node has access to the status and can send status updates as packets to the monitor through a communication system. We also assume that the status updates are generated randomly as a Poisson process. The source node can manage the packet transmission to minimize the age of information at the destination node, which is defined as the time elapsed since the last successfully transmitted update was generated at the source. We use queuing theory to model the source-destination link and we assume that the time to successfully transmit a packet is a gamma distributed service time. We consider two packet management schemes: LCFS (Last Come First Served) with preemption and LCFS without preemption. We compute and analyze the average age and the average peak age of information under these assumptions. Moreover, we extend these results to the case where the service time is deterministic.

We study the performance of generalized polar (GP) codes when they are used for coding schemes involving erasure. GP codes are a family of codes which contains, among others, the standard polar codes of Arıkan and Reed-Muller codes. We derive a closed formula for the zero-undetected-error capacity I0GP(W) of GP codes for a given binary memoryless symmetric (BMS) channel W under the low complexity successive cancellation decoder with erasure. We show that for every R0GP(W), there exists a generalized polar code of blocklength N and of rate at least R where the undetected-error probability is zero and the erasure probability is less than 2-N1/2-ε. On the other hand, for any GP code of rate I0GP(W)-N1/2+εunless the erasure probability is close to 1.

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (first) part of this paper introduces the mathematical framework that we will use in the second part to characterize the polarizing operations. We define uniformity preserving, irreducible, ergodic, and strongly ergodic operations, and we study their properties. The concepts of a stable partition and the residue of a stable partition are introduced. We show that an ergodic operation is strongly ergodic if and only if all its stable partitions are their own residues. We also study the products of binary operations and the structure of their stable partitions. We show that the product of a sequence of binary operations is strongly ergodic if and only if all the operations in the sequence are strongly ergodic. In the second part of this paper, we provide a foundation of polarization theory based on the ergodic theory of binary operations that we develop in this part.

Polar codes are constructed for arbitrary channels by imposing an arbitrary quasi-group structure on the input alphabet. Just as with usual polar codes, the block error probability under successive cancellation decoding is o(2-N1/2ε), where N is the block length. Encoding and decoding for these codes can be implemented with a complexity of O(N\log N). It is shown that the same technique can be used to construct polar codes for arbitrary multiple access channels by using an appropriate Abelian group structure. Although the symmetric sum capacity is achieved by this coding scheme, some points in the symmetric capacity region may not be achieved. In the case where the channel is a combination of linear channels, we provide a necessary and sufficient condition characterizing the channels whose symmetric capacity region is preserved by the polarization process. We also provide a sufficient condition for having a maximal loss in the dominant face.

An open problem in polarization theory is to determine the binary operations that always lead to polarization when they are used in Arıkan style constructions. This paper solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. The characterization is given in terms of a new mathematical framework that we introduce. We show that a binary operation is polarizing if and only if its inverse is strongly ergodic.

An open problem in polarization theory is to determine the binary operations that always lead to polarization when they are used in Arıkan style constructions for multiple access channels (MAC). This paper solves this problem by providing a necessary and sufficient condition for a sequence of binary operations to be polarizing. We show that a sequence of binary operations is MAC-polarizing if and only if the inverse of each binary operation in the sequence is strongly ergodic. We extend the ergodic theory of binary operations and study the products of binary operations and the structure of their stable partitions. We show that the product of a sequence of binary operations is strongly ergodic if and only if all the operations in the sequence are strongly ergodic.

A problem of the polar code construction for multiple access channels (MACs) is that they do not always achieve the whole capacity region. This paper provides a single letter necessary and sufficient condition which characterizes all the MACs that do not lose any part of their capacity region by polarization.

A polarization phenomenon in a special sense is shown for an arbitrary discrete memoryless channel (DMC) by imposing a quasigroup structure on the input alphabet. The same technique is used to derive a polarization theorem for an arbitrary multiple access channel (MAC) by using an appropriate Abelian group structure. These results can be used to construct capacity-achieving polar codes for arbitrary DMCs with a block error probability of o(2-N1/2-ε), and an encoding/decoding complexity of O(N log N), where N is the block length.