The Rényi Information Dimension (RID) is a fundamental measure for quantifying the compressibility of random variables with singularities in their distributions, extending beyond classical notions of sparsity. At a high level, RID represents the average number of bits required to encode i.i.d. samples of a random variable with high precision. For stochastic processes, two main extensions of RID exist: the information dimension rate (IDR) and the block information dimension (BID). A more recent approach to characterizing the compressibility of stochastic processes is through ϵ-achievable compression rates, which treat a random process as the limit of finite-dimensional random vectors and leverage tools from compressed sensing. However, the interplay between BID, IDR, and ϵ-achievable compression rates remains poorly understood. Furthermore, explicit values of IDR and BID are known only for a limited class of processes, such as i.i.d. sequences (i.e., discrete-time white noise) and moving-average (MA) processes. This paper investigates the IDR and BID of discrete-time Auto-Regressive Moving-Average (ARMA) processes and their relationship with ϵ-achievable compression rates when the excitation noise follows a discrete-continuous distribution. Specifically, we show that the RID and ϵ-achievable compression rates of such ARMA processes are equal to those of their excitation noise. In other words, despite the fact that ARMA process samples are not sparse, their compressibility matches that of their sparse excitation noise. To establish this result, we demonstrate that the singular components of the sample distribution are supported on affine sets, with relative dimensions that concentrate around the BID. Leveraging a known result on typical affinely singular sources, we further prove that in this setting, the RID coincides with ϵ-achievable compression rates. The findings of this paper provide new insights into the compressibility of locally correlated data with finite- or infinite-memory, which are commonly modeled using ARMA processes.

Learn-to-Defer is a paradigm that enables learning algorithms to work not in isolation but as a team with human experts. In this paradigm, we permit the system to defer a subset of its tasks to the expert. Although there are currently systems that follow this paradigm and are designed to optimize the accuracy of the final human-AI team, the general methodology for developing such systems under a set of constraints (e.g., algorithmic fairness, expert intervention budget, defer of anomaly, etc.) remains largely unexplored. In this paper, using a d-dimensional generalization to the fundamental lemma of Neyman and Pearson (d-GNP), we obtain the Bayes optimal solution for learn-to-defer systems under various constraints. Furthermore, we design a generalizable algorithm to estimate that solution and apply this algorithm to the COMPAS, Hatespeech, and ACSIncome datasets. Our algorithm shows improvements in terms of constraint violation over a set of learn-to-defer baselines and can control multiple constraint violations at once. The use of d-GNP is beyond learn-to-defer applications and can potentially obtain a solution to decision-making problems with a set of controlled expected performance measures.

One of the goals of learning algorithms is to complement and reduce the burden on human decision makers. The expert deferral setting wherein an algorithm can either predict on its own or defer the decision to a downstream expert helps accomplish this goal. A fundamental aspect of this setting is the need to learn complementary predictors that improve on the human’s weaknesses rather than learning predictors optimized for average error. In this work, we provide the first theoretical analysis of the benefit of learning complementary predictors in expert deferral. To enable efficiently learning such predictors, we consider a family of consistent surrogate loss functions for expert deferral and analyze their theoretical properties. Finally, we design active learning schemes that require minimal amount of data of human expert predictions in order to learn accurate deferral systems.

Kernel mean embedding is a useful tool to compare probability measures. Despite its usefulness, kernel mean embedding considers infinite-dimensional features, which are challenging to handle in the context of differentially private data generation. A recent work, DP-MERF (Harder et al., 2021), proposes to approximate the kernel mean embedding of data distribution using finite-dimensional random features, which yields an analytically tractable sensitivity of approximate kernel mean embedding. However, the required number of random features in DP-MERF is excessively high, often ten thousand to a hundred thousand, which worsens the sensitivity of the approximate kernel mean embedding. To improve the sensitivity, we propose to replace random features with Hermite polynomial features. Unlike the random features, the Hermite polynomial features are ordered, where the features at the low orders contain more information on the distribution than those at the high orders. Hence, a relatively low order of Hermite polynomial features can more accurately approximate the mean embedding of the data distribution compared to a significantly higher number of random features. As a result, the Hermite polynomial features help us to improve the privacy-accuracy trade-off compared to DP-MERF, as demonstrated on several heterogeneous tabular datasets, as well as several image benchmark datasets.

The notion of compressibility of a random measure is a rather general concept which find applications in many contexts from data compression, to signal quantization, and parameter estimation. While compressibility for discrete and continuous measures is generally well understood, the case of discrete-continuous measures is quite subtle. In this paper, we focus on a class of multi-dimensional random measures that have singularities on affine lower-dimensional subsets. We refer to this class of random variables asaffinely singular. Affinely singular random vectors naturally arises when considering linear transformation of component-wise independent discrete-continuous random variables. To measure the compressibility of such distributions, we introduce the new notion of dimensional-rate bias (DRB) which is closely related to the entropy and differential entropy in discrete and continuous cases, respectively. Similar to entropy and differential entropy, DRB is useful in evaluating the mutual information between distributions of the aforementioned type. Besides the DRB, we also evaluate the the RID of these distributions. We further provide an upper-bound for the RID of multi-dimensional random measures that are obtained by Lipschitz functions of component-wise independent discrete-continuous random variables (X). The upper-bound is shown to be achievable when the Lipschitz function is$A \mathrm {X}$, where$A$satisfies${\mathrm{ SPARK}}({A_{m\times n}}) = m+1$(e.g., Vandermonde matrices). When considering discrete-domain moving-average processes with non-Gaussian excitation noise, the above results allow us to evaluate the block-average RID and DRB, as well as to determine a relationship between these parameters and other existing compressibility measures.

The Renyi's information dimension (RID) of an n-dimensional random vector (RV) is the average dimension of the vector when accounting for non-zero probability measures over lower-dimensional subsets. From an information-theoretical perspective, the RID can be interpreted as a measure of compressibility of a probability distribution. While the RID for continuous and discrete measures is well understood, the case of a discrete-continuous measures presents a number of interesting subtleties. In this paper, we investigate the RID for a class of multi-dimensional discrete-continuous random measures with singularities on affine lower dimensional subsets. This class of RVs, which we term affinely singular, arises from linear transformation of orthogonally singular RVs, that include RVs with singularities on affine subsets parallel to principal axes. We obtain the RID of affinely singular RVs and derive an upper bound for the RID of Lipschitz functions of orthogonally singular RVs. As an application of our results, we consider the example of a moving-average stochastic process with discrete-continuous excitation noise and obtain the RID for samples of this process. We also provide insight about the relationship between the block-average information dimension of the truncated samples, the minimum achievable compression rate, and other measures of compressibility for this process.