Making predictions in an unseen environment given data from multiple training environments is a challenging task. We approach this problem from an invariance perspective, focusing on binary classification to shed light on general nonlinear data generation mechanisms. We identify a unique form of invariance that exists solely in a binary setting that allows us to train models invariant over environments. We provide sufficient conditions for such invariance and show it is robust even when environmental conditions vary greatly. Our formulation admits a causal interpretation, allowing us to compare it with various frameworks. Finally, we propose a heuristic prediction method and conduct experiments using real and synthetic datasets.

Learning under distribution shifts is a challenging task. One principled approach is to exploit the invariance principle via the structural causal models. However, the invariance principle is violated when the response is intervened, making it a difficult setting. In a recent work, the invariant matching property has been developed to shed light on this scenario and shows promising performance. In this work, by formulating a high-dimensional problem with intrinsic sparsity, we generalize the invariant matching property for an important setting when only the target is intervened. We propose a more robust and computation-efficient algorithm by leveraging a variant of Lasso, improving upon the existing algorithms.

This work concerns controlling the false discovery rate (FDR) in networks under communication constraints. We present sample-and-forward, a flexible and communication-efficient version of the Benjamini-Hochberg (BH) procedure for multihop networks with general topologies. Our method evidences that the nodes in a network do not need to communicate p-values to each other to achieve a decent statistical power under the global FDR control constraint. Consider a network with a total of m p-values, our method consists of first sampling the (empirical) CDF of the p-values at each node and then forwarding O(log m) bits to its neighbors. Under the same assumptions as for the original BH procedure, our method has both the provable finite-sample FDR control as well as competitive empirical detection power, even with a few samples at each node. We provide an asymptotic analysis of power under a mixture model assumption on the p-values.

The Benjamini-Hochberg (BH) procedure is a celebrated method for multiple testing with false discovery rate (FDR) control. In this paper, we consider large-scale distributed networks where each node possesses a large number of p-values and the goal is to achieve the global BH performance in a communication-efficient manner. We propose that every node performs a local test with an adjusted test size according to the (estimated) global proportion of true null hypotheses. With suitable assumptions, our method is asymptotically equivalent to the global BH procedure. Motivated by this, we develop an algorithm for star networks where each node only needs to transmit an estimate of the (local) proportion of nulls and the (local) number of p-values to the center node; the center node then broadcasts a parameter (computed based on the global estimate and test size) to the local nodes. In the experiment section, we utilize existing estimators of the proportion of true nulls and consider various settings to evaluate the performance and robustness of our method.

Causal inference using the restricted structural causal model framework hinges largely on the asymmetry between cause and effect from the data generating mechanisms. For linear non-Gaussian noise models and nonlinear additive noise models, the asymmetry arises from non-Gaussianity or non-linearity, respectively. Despite the fact that this methodology can be adapted to stationary time series, inferring causal relationships from nonstationary time series remains a challenging task. In this work, we focus on slowly-varying nonstationary processes and propose to break the symmetry by exploiting the nonstationarity of the data. Our main theoretical result shows that the causal direction is identifiable in generic cases when cause and effect are connected via a time-varying filter. We propose a causal discovery procedure by leveraging powerful estimates of the bivariate evolutionary spectra. Both synthetic and real-world data simulations that involve high-order and non-smooth filters are provided to demonstrate the effectiveness of our proposed methodology.

The Additive Noise Models (ANMs) framework for causal discovery has gained much attention due to its strong theoretical guarantees, as well as superior empirical performances on a wide range of real-world data. For observational data, however, quantization (or discretization) is often an inevitable preprocessing step depending on measurement precision requirements. It is thus crucial to understand how sensitive the ANMs are with respect to quantization. In this work, we study the robustness of ANMs framework (via both uniform and Lloyd's quantizers), with a particular focus on its discrete variants. Instead of applying small perturbations on data, we adopt a more aggressive approach by empirically evaluating the methods over various discretization levels that are potentially much smaller than the support of the original data. Surprisingly, the discrete variants are outperformed by the original ANM method developed for continuous data, which inspired us to design a simple yet e ective discrete method that is relatively robust compared with existing discrete methods on various synthetic and real-world data.

A distributed version of the false discovery rate (FDR) control problem has been recently formulated and investigated by Ramdas, Chen, Wainwright, and Jordan [1]. However, their framework requires each agent to transmit real-valued p-value vectors, which makes it less applicable to real-world applications. In this work, we bring quantization into the framework by incorporating a discrete FDR control method, and provide sufficient conditions for the FDR control with respect to different ranges of the FDR level.

In this work, we propose a new inference procedure for understanding non-stationary processes, under the framework of evolutionary spectra developed by Priestley. Among various frameworks of modeling non-stationary processes, the distinguishing feature of the evolutionary spectra is its focus on the physical meaning of frequency. The classical estimate of the evolutionary spectral density is based on a double-window technique consisting of a short-Fourier transform and a smoothing. However, smoothing is known to suffer from the so-called bias leakage problem. By incorporating Thomson's multitaper method that was originally designed for stationary processes, we propose an improved estimate of the evolutionary spectral density, and analyze its bias/variance/resolution tradeoff. As an application of the new estimate, we further propose a non-parametric rank-based stationarity test, and provide various experimental studies.

We consider the problem of generating pseudorandom matrices based on the similarity of their spectra to Wigner's semicircular law. We introduce the notion of an r-independent pseudo-Wigner matrix ensemble and prove the closeness of the spectra of its matrices to the semicircular density in the Kolmogorov distance. We give an explicit construction of a family of N × N pseudo-Wigner ensembles using dual BCH codes and show that the Kolmogorov complexity of the obtained matrices is of the order of log(N) bits for a fixed designed Kolmogorov distance precision. We compare our construction with the quasi-random graphs introduced by Chung et al. and demonstrate that the pseudo-Wigner matrices pass stronger randomness tests than the adjacency matrices of these graphs (lifted by the mapping 0 → 1 and 1 → -1) do. Finally, we provide numerical simulations verifying our theoretical results.

We consider the problem of generating symmetric pseudo-random sign (±1) matrices based on the similarity of their spectra to Wigner's semicircular law. Using binary m-sequences (Golomb sequences) of lengths n = 2m- 1, we give a simple explicit construction of circulant n x n sign matrices and show that their spectra converge to the semicircular law when n grows. The Kolmogorov complexity of the proposed matrices equals to that of Golomb sequences and is at most 2log2(n) bits.

We consider the problem of generating symmetric pseudo-random sign (±1) matrices based on the similarity of their spectra to Wigner's semicircular law. We introduce r-independent pseudo-Wigner ensembles and prove closeness of their spectra to the semicircular density in Kolmogorov distance. We give an explicit construction of a family of N × N pseudo-Wigner ensembles using dual BCH codes and show that the Kolmogorov complexity of the obtained matrices is of the order of log (N) bits for a fixed Kolmogorov distance precision. Finally, we provide numerical simulations verifying our theoretical results.

We consider the problem of generating symmetric pseudo-random sign (±1) matrices based on the similarity of their spectra to Wigner's semicircular law. Using binary m-sequences (Golomb sequences) of lengths n = 2m- 1, we give a simple explicit construction of circulant n × n sign matrices and show that their spectra converge to the semicircular law when n grows. The Kolmogorov complexity of the proposed matrices equals to that of Golomb sequences and is at most 2log2(n) bits.

This paper reviews the relationship among several notions of capacity regions of a general discrete memoryless network under different code classes and performance criteria, such as average vs. maximal or block vs. bit error probabilities and deterministic vs. randomized codes. Applications of these meta-theorems include several structural results on capacity regions and a simple proof of the network equivalence theorem.

A hypothesis testing problem with communication constraints is studied, in which two nodes interactively communicate with each other in q rounds to perform a simple binary hypothesis testing on whether the observed random sequences at the nodes are generated independently or not. The optimal tradeoff between the communication rates in q rounds interaction and the testing performance measured by the type II error exponent such that the type I error probability asymptotically vanishes. An example is provided that shows that a two-way test outperforms the optimal one-way test and thus that interaction helps for hypothesis testing.

Optimal coding over the additive white Gaussian noise channel under the peak energy constraint is studied when there is noisy feedback over an orthogonal additive white Gaussian noise channel. As shown by Pinsker, under the peak energy constraint, the best error exponent for communicating an M-ary message, M ≥ 3, with noise-free feedback is strictly larger than the one without feedback. This paper extends Pinsker's result and shows that if the noise power in the feedback link is sufficiently small, the best error exponent for communicating an M-ary message can be strictly larger than the one without feedback. The proof involves two feedback coding schemes. One is motivated by a two-stage noisy feedback coding scheme of Burnashev and Yamamoto for binary symmetric channels, while the other is a linear noisy feedback coding scheme that extends Pinsker's noise-free feedback coding scheme. When the feedback noise power α is sufficiently small, the linear coding scheme outperforms the two-stage (nonlinear) coding scheme, and is asymptotically optimal as α tends to zero. By contrast, when α is relatively larger, the two-stage coding scheme performs better.

Optimal coding over the additive white Gaussian noise channel under the peak energy constraint is studied when there is noisy feedback over an orthogonal additive white Gaussian noise channel. Previously, Shepp, Wolf, Wyner, and Ziv, and Pinsker showed that under the peak energy constraint the best error exponent for transmission of two messages is achieved by antipodal signaling, regardless of the presence of feedback. This negative result might lead to an impression that under the peak energy constraint, even noise-free feedback does not improve the reliability of communication. Pinsker proved the contrary by showing that the best error exponent for sending M messages does not depend on M, and hence can be strictly larger than the best error exponent without feedback. This paper further extends this and shows that if the noise level in the feedback link is sufficiently small, then the best error exponent for transmission of three messages can be strictly larger than the one without feedback. This result is motivated by a series of recent papers of Burnashev and Yamamoto who considered a similar problem over binary symmetric channels.