Fundamental limits of distributed multiclass classification from simple binary decisions Ioannis Papageorgiou ∗
Srinivas Nomula †
Sidharth Jaggi §
Ayalvadi Ganesh ‡
Parimal Parag ¶
July 22, 2026
arXiv:2607.19334v1 [stat.ML] 21 Jul 2026
Abstract We consider the problem of constructing a K-class classifier from the combination of O(log K) simple binary classifiers – this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the K class centers are independent Gaussian points in Rd and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results. Keywords. Multi-class classification, error-correcting output codes, distributed learning.
∗
School of Mathematics, University of Bristol. Email: [email protected]. Department of Electrical Communication Engineering, Indian Institute [email protected]. ‡ School of Mathematics, University of Bristol. Email: [email protected]. § School of Mathematics, University of Bristol. Email: [email protected]. ¶ Department of Electrical Communication Engineering, Indian Institute [email protected]. †
1
of
Science.
Email:
of
Science.
Email:
1
Introduction
Classification is one of the foundational tasks to which machine learning is applied, with uses ranging from image recognition to spam and fraud detection to medical diagnostics. The typical approach to building classifiers is to gather all the relevant data and use it to train a single complex and powerful classifier. In this paper, we study whether a large number of simple classifiers, each trained on a subset of the data, could cooperate to perform classification with an accuracy comparable to that of a single complex classifier that has access to all the data. There are multiple motivations for this work, including improved fault tolerance and data privacy. Two complementary perspectives form the starting point of this work: multiclass-to-binary reduction and constrained distributed inference. Many classical supervised learning methods were originally developed for binary classification, and a common approach to multiclass problems is therefore to decompose a K-class decision into a collection of binary decisions. Standard examples include one-versus-all schemes, which train one binary classifier per class, and oneversus-one schemes, which train a binary classifier for each pair of classes [15, 3]. Error-correcting output codes. More generally, error-correcting output codes (ECOC) provide a coding-theoretic framework for multiclass classification: each class is assigned a binary codeword, a collection of binary classifiers is evaluated, and the final prediction is obtained by decoding the resulting binary output vector to one of the class codewords [8, 2]. In classical ECOC methods, the code matrix specifies how the classes are grouped for each binary classifier. Later extensions allow more general coding schemes, including ternary codes in which some classes may be ignored for a given binary classifier, random dense and sparse code designs [2], and data-dependent variants that adapt the encoding to the classification problem [22, 9, 21]; see [10] for an implementation and summary of several important ECOC variants. Recent work has continued to revisit ECOC from modern perspectives, including scalable codebook design, deep ECOC architectures, and robustness-oriented output-code learning [13, 30, 6]. Our setting follows the same high-level principle, but it can be viewed as a random geometric analogue of ECOC. Rather than appropriately designing a binary decomposition (using any of the above methods), and training a separate binary classifier for each resulting binary partition, the binary tests we use are simple randomly chosen hyperplanes. This leads to a different set of questions. In particular, rather than asking how to design or learn an effective binary decomposition, we investigate the fundamental performance limits of a very simple and easilydistributed classification scheme, under noise and communication constraints. The key outcome of our analysis is that this random geometric construction is not merely a mathematically convenient variant of ECOC. The theory suggests that for Gaussian mixture models, random hyperplane codes can outperform commonly used ECOC decompositions like the random subsets [2], across a wide range of parameter regimes. Moreover, in this setting their performance often approaches that of optimally chosen hyperplanes, despite requiring no datadependent optimization of the binary tests. This indicates that random geometric measurements can provide a surprisingly effective coding mechanism for multiclass classification. The use of multiple binary tests introduces redundancy, so that classification can remain reliable even when some individual binary decisions are corrupted by noise. In this sense, the framework combines the simplicity of binary classification with the robustness of code-based decoding. Distributed learning. A second motivation comes from constrained and distributed inference. Modern classification systems often operate under practical limitations imposed by communication bandwidth, memory, energy consumption, latency, or privacy. In sensor net2
works, edge devices, and other distributed environments, it may be impractical to transmit full-precision measurements or feature vectors to a central processor. A natural alternative is to allow each local device to perform a simple binary decision and communicate only a highly compressed message to a central server. This perspective differs from the standard federated-learning paradigm, where distributed devices collaborate during training by communicating gradients or model updates to the central server [19, 17]. In our approach, rather than distributing the training algorithm, we distribute the decision process itself. The central server receives a collection of local binary responses and combines them to make a multiclass prediction. Beyond its practical motivation, this architecture provides a clean theoretical lens for studying classification from compressed information. The paper focuses on a deliberately simple random geometric model, in which class prototypes are drawn from a Gaussian distribution and binary responses are generated by random hyperplane tests. This abstraction is not intended to capture all aspects of modern datasets or learned classifiers. Instead, it isolates the basic phenomena of class separation, noise, compression, and decoding in a setting where a complete analysis is possible. The resulting theory gives fundamental limits for this stylized classification problem and provides a baseline for what one may expect in more realistic classification tasks involving richer data models and more flexible decision rules. Further connections and comments. Our framework also connects naturally to decentralized detection and distributed hypothesis testing [24, 25, 26, 1]. In those settings, multiple sensors observe data locally and transmit compressed messages to a central server, which decides among competing hypotheses. Our construction can be viewed as a multiclass classification analogue of that, where binary local decisions are combined by a decoder. In this perspective, different decoding rules correspond to different ways of combining local binary evidence, ranging from simple majority or distance-based rules to likelihood-based decisions. Finally, a related area is one-bit compressed sensing and quantized signal processing, where signals are observed only through severely quantized linear measurements [4, 16, 20]. However, rather than recovering an unknown signal from these measurements, the objective here is to study how such binary information can be used to distinguish among a finite collection of candidate classes. This shifts the focus from recovery to classification and leads naturally to questions about decoding, error probability, and the reliability of binary decision systems.
1.1
Outline of contributions
Motivated as above, in this work we investigate the fundamental performance limits of a K-class classifier that is constructed as a combination of N simple binary classifiers. We introduce a simple classification algorithm where the base classifiers associated to each agent are simple randomly generated hyperplanes. The first part of the paper is focused on a Gaussian noiseless setting, where the class centers are independent Gaussian points in Rd . We provide sharp theoretical analysis (upper and lower bounds) for the performance of a) the proposed random hyperplane scheme b) natural ECOC alternatives and c) information-theoretic optimal schemes. We conclude that the proposed scheme is of much higher practical interest than a standard random-subsets ECOC alternative [2], and actually show that in sufficiently high dimensions its performance is essentially similar to the information-theoretic limits. In the second part of the paper, noise is introduced, so that observations are obtained as one of the class centers corrupted by Gaussian noise. We derive explicit performance bounds for the random hyperplanes scheme across several decoding and dimensional regimes, and propose a computationally efficient decoder that performs nearly optimally in most regimes of practical interest. 3
The rest of this paper is organised as follows. Section 2 is focused on the noiseless setting, in which we describe the random hyperplanes algorithm and the random subsets baseline [2], and derive our main theoretical results for both schemes. Specifically, for random hyperplanes we prove matching upper and lower bounds showing that, in sufficiently high dimensions, N = 2 log2 K + log2 (1/δ), random hyperplanes are sufficient to assign distinct codewords to all K class centers with probability at least 1 − δ. Since any scheme using N binary tests can distinguish at most 2N classes, at least log2 K tests are necessary for any choice of hyperplanes. Thus, the proposed scheme is within a factor of two of the information-theoretic optimum, despite requiring no data-dependent optimization; something perhaps surprising having in mind the simplicity of the scheme. For the random subsets scheme, we also show that in sufficiently high-dimensions the same number of N = 2 log2 K + log2 (1/δ) hyperplanes is sufficient, but the dimensional requirement is much stronger in this case. In particular, random hyperplanes require a dimension only logarithmic in K, whereas random subsets require a dimension linear in K. This shows that the proposed scheme is substantially more dimension-efficient, something that is also verified in practice, in a number of simulation experiments. We then focus on the more realistic practical setting where observations are corrupted by Gaussian noise. In Section 3, as a tractable intermediate step towards understanding the performance of random hyperplane classifiers in the presence of noise, we first consider a simpler setting where hyperplanes are chosen to be orthogonal to each other. We derive explicit non-asymptotic bounds and exact finite-sample expressions for both Hamming and maximum likelihood (ML) decoding. Importantly, these results indicate that N = O(log K) hyperplanes are still sufficient, but now including a multiplicative constant that depends on the signal to noise ratio (SNR). In specific, we derive achievability conditions of the form, N≥
log((K − 1)/δ) , E(ρ)
sufficient to ensure an error probability smaller than δ, where ρ denotes the SNR and E(ρ) is the relevant decoder-dependent error exponent. In Section 4, the analysis is ultimately extended to random hyperplanes. We obtain an explicit finite-dimensional Chernoff bound for Hamming decoding, characterize its limiting probability of error, and establish high-dimensional regimes in which the random-hyperplane model approaches its orthogonal counterpart. Furthermore, due to the fact that exact ML decoding for random hyperplanes turns out to be particularly expensive, we also introduce a computationally efficient approximate ML decoder for this setting, which is motivated by the earlier orthogonal hyperplane analysis. We formally prove that this decoder is asymptotically optimal in sufficiently high dimensions, and provide extensive simulation results indicating that in practice it actually performs nearly as ML even in much lower dimensions. In fact, a dimension roughly at the same order as the number of hyperplanes seems to be enough. Finally, the experimental results lead to an important conclusion for general classification problems. As perhaps expected, Hamming decoding is found to perform substantially worse than the proposed reliability-aware decoder. This indicates that assigning equal weight to the binary decisions associated with each classifier/agent can be significantly suboptimal, and highlights the importance of exploiting heterogeneous classifier reliabilities. 4
2
Noiseless setting
Throughout this paper, the notation we use is that the number of classes is K, the dimensionality of the data is d (which is typically considered to be large), and there are N agents/binary classifiers who seek to cooperate to solve the classification problem. In this section, we first focus on a noiseless Gaussian setting, where the K class centers, x1 , ..., xK , are independent iid and identically distributed (i.i.d.) Gaussian points in Rd . In specific, x1 , . . . , xK ∼ N (0, Id ), where Id denotes the d-dimensional identity matrix. We first consider the fundamental task of separating the class centers themselves. In order to do so, we consider two algorithms, which we refer to as the random hyperplanes and random subsets algorithms.
2.1
Algorithms
Random hyperplanes algorithm. Each of the N agents picks a random hyperplane in Rd passing through the origin, as follows. Agent i picks a unit vector Wi uniformly at random from S d−1 , the unit sphere in Rd , independent of other agents. The vectors wi are the corresponding normal vectors that define the hyperplanes Hi = {x ∈ Rd : wi⊤ x = 0}. Now, with each class k, we associate an N -bit codeword Ck ∈ (±1)N , whose bits are given by, Ck,i := sign(wi⊤ xk ),
i = 1, . . . , N.
(1)
If the K codewords are all distinct, then the agents can collectively identify the classes perfectly. Question 1. For the random hyperplanes algorithm, how large should N be in order to guarantee that all K codewords are distinct with probability at least 1 − δ, where δ > 0 is a specified error tolerance? It is obvious by the pigeonhole principle that we need N ≥ log2 K. We show that we actually need at least 2 log2 K and that, if d is sufficiently large, then do not need much more. Random subsets algorithm. Each of the N agents randomly partitions the set of classes into two subsets of size approximately K/2 by Bernoulli sampling of the class labels. Denote − the subsets corresponding to agent i by A+ i and Ai , and let χi be the indicator that the subsets + − Ai and Ai are linearly separable, i.e., that they are separated by an affine hyperplane (one not necessarily passing through the origin). In this setting, only agents i that can linearly separate their subsets participate in discriminating between classes; otherwise, they assign the same symbol, −1, to all classes. So, we associate a codeword C̃k with class k as follows, ( +1, if χi = 1 and k ∈ A+ i , C̃k,i := (2) −1, otherwise. Again, the agents can collectively identify the classes only if all K codewords are distinct. Question 2. For the random subsets algorithm, how large should N be in order to guarantee that all K codewords are distinct with probability at least 1 − δ, where δ > 0 is a specified error tolerance? We now state the answers to these questions, providing necessary and sufficient conditions on the number of agents (and hence hyperplanes) required for each scheme. In the following, E refers to the error event that at least two distinct classes share the same codeword. 5
2.2
Theoretical results iid
Theorem 1. Let x1 , . . . , xK ∼ N (0, Id ), and w1 , . . . , wN be i.i.d. spherically symmetric random vectors defining N hyperplanes in Rd . Let δ ∈ (0, 1) and suppose d ≥ C log K for a suitable constant C > 0. Then, in order to ensure that the error probability satisfies Pr(E) ≤ δ, it is sufficient that the number of hyperplanes satisfies, q log(K 2 /δ) N ≥ 2 log2 K + log2 (1/δ) 1 + O . d Remarks. In the high-dimensional regime d ≫ log K, the correction term vanishes and the theorem says that 2 log2 K + log2 (1/δ) hyperplanes are sufficient to separate all the classes, with high probability. A more careful analysis shows that, in the intermediate regime where d is of the same order as log K, the required number of hyperplanes is still O(log K), with constants depending on the ratio between d and log K. In even lower dimensions, a logarithmic number of hyperplanes is not enough, and in particular, in the fixed-dimensional case (i.e., when d is a constant), a polynomial number of hyperplanes is needed; see proof below for more details. Theorem 2. Let x1 , . . . , xK and w1 , . . . , wN be as in Theorem 1. Then, in order to ensure that the error probability satisfies Pr(E) ≤ δ, it is necessary that, N ≥ 2 log2 K + log2 (1/δ) − C, where C is an absolute constant; e.g., one may take C = 4. Remark. In contrast to the upper bound on N in Theorem 1, this lower bound is dimensionindependent. iid
Theorem 3. Let x1 , . . . , xK ∼ N (0, Id ). Generate N random subset-pairs using i.i.d. Bern(1/2) labelings and retain only those that are separable by an affine hyperplane. a) High-dimensional regime. If d ≥ (1+ε) K−1 2 for some ε > 0, and if ρK is an exponentially small correction term, ε2 ρK = exp − (K − 1) , 4 + 2ε then in order to ensure that Pr(E) ≤ δ + O (ρK log K), it is sufficient that the total number of random labelings satisfies, N ≥ (2 log2 K + log2 (1/δ)) (1 + O (ρK )) . for some ε > 0, then exponentially many b) Low-dimensional regime. If d ≤ (1 − ε) K−1 2 trials (in K) are needed. So, the random subset scheme is infeasible in this case. Remark. Comparing Theorems 1 and 3, we see that the latter needs the data to be of much higher dimension, of order K rather than log K, in order to be classifiable using a small number of hyperplanes. However, if the condition on dimension is met, then both schemes need essentially the same number of hyperplanes, N = 2 log2 K + log2 (1/δ). iid
∗ Theorem 4. Let x1 , . . . , xK ∼ N (0, Id ), and let NK,d denote the minimum number of affine hyperplanes required to separate the K points. The following lower bounds hold:
6
1. Irrespective of the number of dimensions, ∗ NK,d ≥ ⌈log2 K⌉.
2. If d < 21 log2 K, then, ∗ NK,d ≥
1 dK 1/d . 2e
Remark. In the high-dimensional regime d ≫ log K, the number of random hyperplanes required ∗ , despite requiring no datais within a factor of two of the information-theoretic minimum NK,d dependent optimization. In the low dimension case where d is fixed, the number of random ∗ hyperplanes and the optimal NK,d both grow polynomially in K.
2.3
Proofs
Proof of Theorem 1. First, we revisit the concentration of pairwise angles among Gaussian class centers. For K i.i.d. Gaussian points in Rd , we show that these angles concentrate around π/2 with high probability, and quantifying this concentration in our setting allows us to control the collision probability of the random hyperplane code. Define x̂i := xi /∥xi ∥, so that x̂i , i = 1, . . . , K, are i.i.d. uniform on the sphere S d−1 . By standard sub-Gaussian concentration of inner products for uniform distributions on the sphere [28], we have for any t ∈ (0, 1) that, 2 Pr |⟨x̂i , x̂j ⟩| ≥ t ≤ 2 e−c d t , for some universal constant c > 0; one may take c = 1/4 in a standard version of this bound. By 2 applying a union bound over the K2 ≤ K2 pairs, we obtain with probability at least 1−δ/2 that, max |⟨x̂i , x̂j ⟩| ≤ t⋆ := i<j
q
c′ log(K 2 /δ) , d
for a universal constant c′ > 0. Writing θij for the pairwise angle between xi and xj , we get that with high probability, q ′ 2 /δ) . max | cos θij | ≤ t⋆ := c log(K d i<j
Since δ is fixed, if d ≥ C ′ log K for a sufficiently large constant C ′ > 0, as in the assumptions of the theorem, we get t⋆ ≤ 1, and therefore, with probability at least 1 − δ/2, |θij − π/2| ≤ arcsin(t⋆ ) ≤
log(K 2 /δ) π t⋆ ≤ C , 2 d
(3)
for all pairs i ̸= j, where C > 0 is a constant. We now turn to determining the relation between the number of hyperplanes and the error probability. Consider a single hyperplane w. For fixed xi , xj with angle θij and w uniform on the sphere, the probability that the hyperplane w does not separate the points is, θij . p = Pr sign(w⊤ xi ) = sign(w⊤ xj ) = 1 − π 7
As we have N independent hyperplanes, the probability that none of them separates a specific pair i ̸= j is pN , and taking a union bound over the pairs shows that, K N K2 N Pr(E) ≤ p ≤ p . (4) 2 2 From (3) we get that with probability at least 1 − δ/2, r 1 log(K 2 /δ) p≤ +C , 2 d
(5)
so, in order to ensure that Pr(E) ≤ δ, it suffices to choose N such that K 2 pN /2 ≤ δ/2, i.e., N ≥
log(K 2 /δ) 2 log K + log(1/δ) = . log(1/p) log(1/p)
(6)
Substituting for p from (5) and doing a Taylor expansion in the denominator yields the claim of the theorem. Remark. In the intermediate setting where d = Θ(log K), the extreme-angle asymptotics of [5], suggest that the minimum angle is strictly positive, and hence the worst-pair collision probability p is strictly smaller than one. Then, (6) suggests that N = O(log K) random hyperplanes suffice. In even lower dimension, when d is fixed, the results of [5] imply that the minimum angle scales as, θmin = Θp K −2/(d−1) , which means that a polynomial number of hyperplanes is required. Proof of Theorem 2. Define the codeword Ck corresponding to class k, and associated class center xk , as in (1). Fix the hyperplanes W = (w1 , . . . , wN ). Since the class centers xi are i.i.d. and independent of W , the codewords Ci are i.i.d. draws from some distribution PW on the finite set S = {±1}N . The probability of all codewords being distinct is maximised, and the error probability minimised, when PW is uniform on S. The error probability can be calculated in this case using a simple birthday problem argument. Thus, we have, Pr(E) ≥ 1 −
K−1 Y 2N − j j=0
2N
=1−
K−1 Y
1−
j=0
j . 2N
Using the inequality 1 − x ≤ e−x , we get, K−1 Y j=0
K−1 X j j K(K−1) 1 − N ≤ exp − = exp − , N +1 2 2 2N j=0
and so, . Pr(E) ≥ 1 − exp − K(K−1) 2N +1 Hence, to ensure Pr(E) ≤ δ, we need, 1 − exp − K(K−1) ≤ δ, 2N +1 or, 2N +1 ≥
K(K − 1) . − log(1 − δ) 8
Taking logarithms and using a Taylor expansion, we get, N ≥ 2 log2 K + log2 (1/δ) − C, as required, where C is an explicit constant (for which it is possible to show that C < 3.5). Next, we turn to the Random Subsets Algorithm. In order to analyse its performance, we will need the following result about linear separability of point sets. iid
Lemma 1. Let x1 , . . . , xK ∼ N (0, Id ), and let y1 , . . . , yK ∼ Bern(1/2) be independent random labels that partition the xi ’s into two random subsets. The probability that the subsets are linearly separable, or equivalently, that the labeling is realisable by an affine hyperplane in Rd is, p(d, K) =
1
d X K −1
2(K−1) j=0
j
h i = Pr Bin(K − 1, 12 ) ≤ d .
Proof. First consider the case where the hyperplanes w are homogeneous, i.e., passing through the origin. A labeling y is realizable iff there exists w ∈ Rd with, yi w ⊤ x i > 0
∀i = 1, . . . , K,
i.e., all the points yi xi lie in some open halfspace in Rd . As before, the directions ui = xi /∥xi ∥ are i.i.d. uniform on the sphere S d−1 . Multiplying by yi ∈ {±1} just flips signs, so yi ui has the same distribution as ui . Thus separability of the subsets reduces to the event that K i.i.d. uniform points {u1 , . . . , uK } on S d−1 all lie in some open hemisphere. By Wendel’s theorem [29], this probability is given by, −(K−1)
p(d, K) = 2
d−1 X K −1 . j j=0
Allowing affine hyperplanes corresponds to replacing d − 1 with d, by a lifting argument. Corollary 1. As K → ∞, the probability of separability, p(d, K), exhibits the following three regimes depending on how quickly the dimension d grows compared to K. 1. Low-dimensional regime If d ≤ (1 − ε) K−1 for some fixed ε > 0, then, by a lower-tail 2 Chernoff bound on the binomial distribution, 2 p(d, K) ≤ exp − ε4 (K − 1) . Thus, the probability that a random subset is linearly separable is exponentially small. 2. High-dimensional regime. If d ≥ (1 + ε) K−1 for some fixed ε > 0, then by Chernoff ’s 2 upper-tail bound for the binomial distribution, ε2 p(d, K) ≥ 1 − exp − (K − 1) . 4 + 2ε Hence p(d, K) → 1 exponentially fast, and almost every random subset is linearly separable. 9
We shall need the following lemma. Lemma 2. Let A and B be two events in the same probability space. Then, | Pr(B|A)−Pr(B)| ≤ 2 Pr(Ac ). Proof. Its proof follows from a straightforward calculation: | Pr(B|A) − Pr(B)| = | Pr(B|A) − Pr(B|A) Pr(A) − Pr(B|Ac ) Pr(Ac )| ≤ | Pr(B|A) Pr(Ac )| + | Pr(B|Ac ) Pr(Ac )| ≤ 2 Pr(Ac ). Proof of Theorem 3. First, consider the low-dimensional regime in which d ≤ (1 − ε) K−1 2 . Here, the probability that a random labeling is linearly separable is exponentially small. Thus, the expected number of random labellings required to get even one separable subset is, 2 1 ≥ exp ε4 (K − 1) , p(d, K) which grows exponentially in K. So, the random subset scheme is infeasible in this case. Henceforth, we consider the high-dimensional regime. Fix ε > 0 and suppose that d ≥ (1 + ε) K−1 2 . Let y1 , . . . , yK be i.i.d. Bern(1/2) random labels, and define A(y) to be the event that the subset partitioning induced by the labels y = (y1 , . . . , yK ) is linearly separable. Then, by Corollary 1, ε2 Pr(A(y)c ) ≤ ρK := exp − (K − 1) . 4 + 2ε Now fix a pair of indices i, j and define Bij to be the event that a random Bern(1/2) labelling y separates the points xi and xj , i.e., that yi ̸= yj . Clearly, Pr(Bij ) = 1/2. Hence, it follows from Lemma 2 that, 1 (7) 1 − Pr(Bij | A(y)) ≤ + 2ρK . 2 The Random Subsets Algorithm generates N independent labellings, each of which partitions the class centers into two subsets. Denote by NK the number of these labellings that yield linearly separable subsets; and are finally retained. It then follows from (7) that, that for a fixed pair of indices i ̸= j, the probability that it is not separated by any of the resulting NK hyperplanes is, p≤
1 + 2ρK 2
NK .
Taking a union bound over all pairs gives, NK K 1 Pr(E) ≤ + ρK , 2 2 and since
K 2
≤ K 2 , we obtain that in order to ensure that Pr(E) ≤ δ, it suffices if, NK ≥
2 log2 K + log2 (1/δ) 2 ln K + ln(1/δ) = . 1 1 − log2 (1 + 4ρK ) − ln 2 + 2ρK
10
(8)
Again by doing Taylor expansion in the denominator, we can rewrite the above sufficient condition as, NK ≥ (2 log2 K + log2 (1/δ)) (1 + O(ρK )) . (9) Next, each generated subset pair is rejected (if it is not linearly separable) with probability at most ρK . Hence, if we generate N = NK subset pairs, then by a union bound the probability that at least one of them is rejected is at most NK ρK . Combining this with (9), shows that if we take, N ≥ (2 log2 K + log2 (1/δ)) (1 + O(ρK )) , the total error probability is Pr(E) ≤ δ + O(ρK log K). Proof of Theorem 4. Since N hyperplanes create at most 2N distinct sign vectors, the elementary necessary condition 2N ≥ K gives the trivial lower bound, ∗ NK,d ≥ ⌈log2 K⌉,
which is valid in all dimensions. The proof for the lower-dimension case, d < 12 log2 K, uses the fact that the maximum number of regions determined by N affine hyperplanes in Rd is given by, R(N, d) =
d X N j=0
j
= 2N Pr Bin(N, 12 ) ≤ d ,
(10)
which follows from classical region-counting formulas [31, 18]. Now, a necessary condition to separate K points with N hyperplanes is that R(N, d) ≥ K. Suppose N < 2d. Then N < log2 K since d < 21 log2 K, and from (10) we observe that, R(N, d) ≤
N X N j=0
j
= 2N < K,
so by contradiction, fewer than2d hyperplanes do not suffice. Next, if N ≥ 2d, then Nj is increasing in j for j ∈ {0, . . . , d}. Hence, using standard binomial coefficient bounds, we obtain from (10) that, R(N, d) =
d X N j=0
j
eN d N ≤ (d + 1) < (d + 1) . d d
It follows that a necessary condition in order to ensure that R(N, d) ≥ K is, N≥
d 1/d 1 1 K ≥ dK 1/d , 1/d 2e (d + 1) e
where we have used the fact that 1/(d + 1)1/d is increasing in d, and is therefore minimised at d = 1.
11
2.4
Simulation results
In previous sections, we introduced the random hyperplanes and random subsets algorithms, described their behavior in different regimes, and derived asymptotic bounds for their performance. We now simulate the setup to validate how closely our asymptotic predictions match finite-system behavior, examine the dimensional requirements of each algorithm, and observe the existence of distinct regimes. We evaluate the performance of the algorithms across various regimes, comparing the number of hyperplanes required to achieve the same error probability, and discuss the trade-off between dimensional requirements and the number of hyperplanes. We perform the experiments as follows: We sample K classes from the standard Gaussian in Rd . For random hyperplanes, we sample the N hyperplane normals from the uniform distribution on the sphere. For random subsets, we partition the K points into two groups of size approximately K/2 by Bernoulli sampling the class labels. We try to find a hyperplane that perfectly separates these subsets, and retain this pair of subsets together with the corresponding hyperplane if this is possible. In each case, we use the hyperplanes to assign an N -length codeword to each of the K points as described in Section 2.1, and the experiment is marked as erroneous if any of the codewords are not unique. We estimate the probability of error as the empirical ratio of erroneous experiments to the total number of experiments. The results are obtained after 105 repetitions of each experiment. 2.4.1
Random hyperplanes
In Figure 1 (left), we illustrate the qualitative behavior of random hyperplanes in low-dimensional regimes. The number of classes in this case is K = 32, so with d = 2, 4, 6, 8, we have probably not effectively reached the high-dimensional region d ≫ log K. However, as perhaps expected, it is evident than d = 2 corresponds to a much slower decay compared to the other three cases. In all cases, it is evident that as the dimension increases, we need fewer hyperplanes to achieve the same probability of error. This is of course expected from our theory, since increasing the dimension means that we increase the minimum pairwise angle between two points, and therefore reduce the collision probability between any two codewords. 100
100
d = 16
Prob of error (Pe )
Prob of error (Pe )
d = 24
10−1 10−2 10−3
d=2 d=4
d = 32
10−1
Theory
10−2 10−3
d=6 d=8
10−4 0
200
400 600 800 Hyperplanes (N)
10−4
1,000
0
10
20 30 Hyperplanes (N)
40
Figure 1: Random hyperplanes error probability performance. Left: Low dimensions, Right: High dimensions
In Figure 1 (right), we illustrate the behavior of random hyperplanes in high dimensions. Since again K = 32, the presented experiments with d = 16, 24, 32 suggests that we have now probably reached the high-dimensional regime. When d ≫ log K, from our theory we expect all pairwise angles to concentrate on π/2, and therefore all pairwise collision probabilities to
12
converge to p = 1/2. In this case, our previous analysis in (4) shows that a simple upper bound on the probability of error is, N K 1 Pr(E) ≤ . (11) 2 2 As expected, Figure 1 verifies that as the dimension d increases, the empirical error curves closely match this theoretical bound, which is plotted as the red dashed line labeled ‘Theory’ in the figure. This precisely corresponds to the fact that as the dimension increases, the big-O correction term in Theorem 1 vanishes. 2.4.2
Random subsets
In Figure 2 (left), we illustrate the low-dimensional behavior of the random-subset policy. With K = 32 classes, we observe that for any d < 16, the probability of error essentially remains close to one irrespective of the number of hyperplanes. This verifies our theory since it is coherent with that fact that if d < (K − 1)/2 = 15.5, we expect the probability of random subset partitions being linearly separable to be exponentially small. For d = 16, it seems that we have effectively surpassed this threshold, so that the probability of error steadily decreases with N . In Figure 2 (right) we illustrate the high-dimensional behavior of the random subsets policy, by plotting the experimental results for d = 24, 28, which clearly fall in the high-dimensional regime d > (K − 1)/2. In sufficiently high dimensions, we expect the behavior of this scheme to be similar to random hyperplanes, since we expect essentially all randomly selected partitions to be linearly separable – and hence used. In particular, from (8) we again recover the same upper bound as in (11) for the probability of error. This is verified in Figure 2 (right), where the empirical error curves seem to be very close to the high-dimensional upper bound (11), signifying that again, the corresponding big-O correction term of Theorem 3 has vanished. 100 Prob of error (Pe )
Prob of error (Pe )
100 10−1 10−2 10−3
d=4
10−1 10−2 10−3
d = 24
d=8
d = 28
d = 12
10−4
d = 16
10−4 0
10
20 30 Hyperplanes (N)
40
Theory
0
10
20 30 Hyperplanes (N)
40
Figure 2: Random subsets error probability performance. Left: Low dimensions, Right: High dimensions
2.4.3
Policy comparison
In Figure 3, we compare the performance of the random hyperplane and random subset policies for K = 32 and K = 1024 classes, respectively. From Theorems 1 and 3, we expect the transition to the high-dimensional regime to occur at dimensions that scale as logarithmically with K for random hyperplanes and linearly with K for random subsets. Consequently, random hyperplanes begin exhibiting a faster reduction in the probability of error at significantly lower dimensions than random subsets. This fact is illustrated in both Figure 3, with the dimensional advantage of
13
random hyperplanes being substantially more pronounced in Figure 3(right), something expected since it corresponds to a much larger number of classes, K = 1024. 100 Prob of error (Pe )
Prob of error (Pe )
100 10−1 10−2
Hyperplanes d = 12 Hyperplanes d = 16 Hyperplanes d = 28 Subsets d = 12
10−3
Subsets d = 16
10−1 10−2
Hyperplanes d = 512 Hyperplanes d = 528 Hyperplanes d = 608 Subsets d = 512
10−3
Subsets d = 528
Subsets d = 28
10−4
d = 608
Theory
0
10
20 30 Hyperplanes (N)
10−4
40
Theory
0
10
20 30 Hyperplanes (N)
40
Figure 3: Policy comparison. Left: K = 32 classes, Right: K = 1024 classes
Summary. Overall, the experimental results validate the theoretical scaling laws derived in the previous sections and highlight the fundamental difference between the two constructions. Although both policies require a comparable number of hyperplanes in their respective highdimensional regimes, the random hyperplane policy attains the same reliability while requiring significantly fewer dimensions. As the number of classes increases, this dimensional advantage becomes increasingly pronounced, making the random hyperplane policy substantially more scalable than the random subset policy. For this reason, for the remaining of this paper where we focus on the full noisy-observation setting, we restrict our attention to the random hyperplanes scheme, and provide fundamental limits for its performance in the presence of noise.
3
Orthogonal hyperplanes with noise
As an intermediate step in understanding the fundamental limits of the random hyperplanes scheme in the presence of noise, we first consider a slightly simpler (in terms of analysis) scheme, where the hyperplanes are chosen orthogonal to each other. This simplification allows to get precise theoretical results, and at the same time gives a strong indication on what we expect to happen in sufficiently high dimensions in the original setting, where randomly chosen hyperplanes will tend to be orthogonal to each other; again, this is because of the concentration of random angles to π/2 in sufficiently high dimensions.
3.1
Model description
Let u1 , . . . , uN ∈ Rd be orthonormal, with N ≤ d. Let the K class centers be, iid
x1 , . . . , xK ∼ N (0, τ 2 Id ), and suppose the true class is a ∈ {1, . . . , K}. Define the noisy observation, y = xa + z,
z ∼ N (0, σ 2 Id ),
independently. For each class k, define its binary codeword, Ck = (Ck,1 , . . . , Ck,N ) ∈ {±1}N , 14
Ck,i := sign(u⊤ i xk ),
and define the observed binary vector, B = (B1 , . . . , BN ) ∈ {±1}N ,
Bi := sign(u⊤ i y).
For the true class a, let, |u⊤ i xa | pa,i := Pr(Bi ̸= Ca,i | xa , u1 , . . . , uN ) = Q σ
,
where Q(t) = Pr(Z ≥ t) for Z ∼ N (0, 1), and let ρ := τ /σ denote the signal to noise ratio (SNR). Communications formulation. This classification problem reduces very naturally to a communication problem. In particular, since the centers are sampled i.i.d., and the hyperplanes are orthogonal, we have K codewords C1 , ..., CK of length N that are sampled uniformly and independently from {±1}N . Since the hyperplanes are orthogonal, the transmitted codeword Ca is passed through a channel in which each of the N bits (coordinates) i is flipped independently with probability pa,i as defined above, which is geometry-dependent. Before considering the original geometry-dependent problem above, suppose we first simplify the analysis by removing the geometry and homogenizing the model. In particular, suppose we replace the coordinate-dependent flip probabilities pa,i by a single flip probability p, defined as the expected value of pa,i . With this simplification, the problem reduces to communication over a Binary Symmetry Channel (BSC), with crossover probability p.
3.2
Further reduction to BSC
Lemma 3. Let xa ∼ N (0, τ 2 Id ), z ∼ N (0, σ 2 Id ) independent of xa , ui ∈ S d−1 be a fixed unit vector, and ρ = τ /σ. Define, Ca,i = sign(u⊤ i xa ),
Bi = sign(u⊤ i (xa + z)).
The conditional probability that the i-th bit of the true codeword Ca is flipped is, ⊤ |ui xa | pa,i := Pr{Bi ̸= Ca,i | xa , ui } = Q , σ and its expected value is given by, p := Exa [pa,i ] =
1 1 arctan . π ρ
(12)
2 Proof. Condition on xa and ui . Since z ∼ N (0, σ 2 Id ), we have u⊤ i z ∼ N (0, σ ). The i-th bit is ⊤ ⊤ ⊤ flipped when the noise changes the sign of ui xa , i.e., sign(ui xa + ui z) ̸= sign(u⊤ i xa ). Therefore, ⊤ |ui xa | pa,i = Pr{Bi ̸= Ca,i | xa , ui } = Q . σ
Now averaging over xa gives, E[pa,i ] = EG [Q(ρ|G|)], where G ∼ N (0, 1). Finally, in order to compute this expectation, let W ∼ N (0, 1) be independent of G. Then by the definition of the Q-function, EG [Q(ρ|G|)] = Pr{W > ρ|G|}. 15
The vector (G, W ) is rotationally invariant in R2 , and the event {W > ρ|G|} is a cone with opening angle 2 arctan(1/ρ). Hence, 2 arctan(1/ρ) 1 1 = arctan . 2π π ρ
p = E[pa,i ] = Pr{W > ρ|G|} =
Using this appropriate crossover probability p, our setting is now reduced to a standard BSC(p). Standard analysis shows that Hamming decoding is maximum likelihood/optimal in this case, and similarly gives capacity and error exponents results, for example as below. Throughout this section, Pr(E) denotes the unconditional probability of error, where the probability is taken over the random class centers x1 , . . . , xK , the hyperplanes u1 , . . . , uN , the noise z, and the choice of the transmitted class a, i.e., Pr(E) := Pr(b a ̸= a). Capacity. A necessary and sufficient condition for reliable recovery asymptotically in the regime N ≤ d, N → ∞, under the BSC assumptions, is given by the channel coding theorem, log2 K < 1 − h2 (p), N
p=
1 1 arctan . π ρ
Theorem 5. Under the BSC assumptions, a sufficient condition to ensure that the probability of error satisfies Pr(E) ≤ δ is, log((K − 1)/δ) , N≥ EBSC (ρ) where, ρ = τ /σ, and EBSC (ρ) is given by,
1 p EBSC (ρ) := − log + p(1 − p) , 2
(13)
with p = π1 arctan ρ1 , as before in (12). Proof. The proof follows from Chernoff analysis applied to the homogenized BSC setting. It is omitted here since it can be seen as a special case of Theorem 6 that considers the more general setting with geometry-dependent bitflip probabilities pa,i , where we can set all pa,i = p.
3.3
Hamming decoding
Now, we return to our original geometry-dependent channel with independent bitflips with probability pa,i . As a first step, we consider a Hamming decoder, b a ∈ arg
min m∈{1,...,K}
dH (B, Cm ),
where dH (B, Cm ) denotes the Hamming distance between the binary vectors B, Cm . Performing a Chernoff-bound analysis to provide an achievability result for the sufficient number of hyperplanes, shows that our previous bound still works here, as expected. Theorem 6. In the orthogonal hyperplanes setting of Section 3.1, a sufficient condition to ensure that the probability of error satisfies Pr(E) ≤ δ is, N≥
log((K − 1)/δ) , EBSC (ρ)
where EBSC (ρ) is given by (13). 16
Proof. Fix a competitor b ̸= a, and define, Dab := {i : Ca,i ̸= Cb,i }. For i ∈ / Dab , the two codewords agree, so coordinate i contributes equally to dH (B, Ca ) and dH (B, Cb ); thus only coordinates in Dab matter. For i ∈ Dab , define, (ab)
Mi
:= 1{Bi ̸= Cb,i } − 1{Bi ̸= Ca,i },
and since for i ∈ Dab we have Ca,i ̸= Cb,i , we get, (ab)
Pr(Mi
= +1|xa , xb , ui ) = 1 − pa,i ,
(ab)
Pr(Mi
= −1|xa , xb , ui ) = pa,i .
Pairwise confusion occurs when, dH (B, Cb ) − dH (B, Ca ) =
X
(ab)
Mi
≤ 0.
i∈Dab N Let xK 1 and u1 denote the vector concatenations of x1 , ..., xK and u1 , ..., uN . Fix a global Chernoff parameter s ≥ 0. By Markov’s inequality, X X (ab) (ab) N N Pr M ≤ 0 xK ≤ E exp −s M . xK 1 , u1 1 , u1 i
i
i∈Dab
i∈Dab
⊤ Conditional on xa and uN 1 , the projected noises Wi := ui z, i = 1, . . . , N, are independent (ab) N (0, σ 2 ) random variables, since the hyperplanes are orthogonal, and hence the variables Mi are conditionally independent. Therefore, i X Y h (ab) (ab) N −sMi K N E exp −s Mi x K , u = E e x , u 1 1 1 1 , i∈Dab
i∈Dab
and for i ∈ Dab , h i (ab) N E e−sMi xK , u = (1 − pa,i )e−s + pa,i es . 1 1 Therefore, for any s ≥ 0, Y N Pr dH (B, Cb ) ≤ dH (B, Ca ) xK , u ≤ 1 1
(1 − pa,i )e−s + pa,i es ,
i∈Dab
and taking a union bound over b ̸= a, for every s ≥ 0, X Y N Pr E xK , u (1 − pa,i )e−s + pa,i es . 1 1 ≤ b̸=a i∈Dab iid
⊤ 2 Now fix xa and uN 1 , and average over one random competitor xb . Since ui xb ∼ N (0, τ ), the signs Cb,1 , . . . , Cb,N are independent fair signs. Therefore, conditional on Ca , 1{i ∈ Dab } ∼ Bernoulli(1/2), independently over i. Thus, N Y Y 1 1 −s s −s s N Exb + (1 − pa,i )e + pa,i e . (1 − pa,i )e + pa,i e xa , u1 = 2 2 i=1
i∈Dab
17
Using the notation, 1 1 (1 − x)e−s + xes , + 2 2 summing over the K − 1 competitors, and taking the infimum over s to tighten the bound yields, ms (x) :=
N Y Pr E xa , uN ≤ (K − 1) inf ms (pa,i ). 1 s≥0
(14)
i=1
Finally, average over the transmitted point xa . Since u1 , . . . , uN are orthonormal and xa ∼ iid 2 N (0, τ 2 Id ), we have u⊤ i xa ∼ N (0, τ ), and, pa,i = Q
|u⊤ i xa | σ
d
= Q(ρ|Zi |),
iid
where Z1 , . . . , ZN ∼ N (0, 1). We can now relax the bound by moving the infimum outside the expectation: " # "N # N Y Y Pr(E) ≤ (K − 1)E inf ms (pa,i ) ≤ (K − 1) inf E ms (pa,i ) = (K − 1) inf (ms (p))N , s≥0
s≥0
i=1
i=1
s≥0
where the last equality follows since the pa,i are i.i.d. with expectation E[pa,i ] = p as before, and ms (x) is linear in x. Optimizing over s ≥ 0, the minimum value of ms (p) is, ms (p) ≥
1 p + p(1 − p), 2
and substituting gives, Pr(E) ≤ (K − 1)
1 p + p(1 − p) 2
N
= (K − 1) e−N EBSC (ρ) ,
(15)
which gives the required error exponent and completes the proof after rearranging. Remark. Theorem 6 formally shows that the achievabilty condition under the BSC assumptions is still sufficient for the geometry-dependent case. Importantly, it shows that N = O(log K) hyperplanes are sufficient, with a multiplicative constant depending on the signal to noise ratio. A somewhat tighter constant can be obtained by exploiting the geometry. In specific, we can get a refinement by avoiding to move the expectation inside the infimum in (14), define, " # N Y 1 Eq,N (ρ) := − log E inf ms (pa,i ) , s≥0 N i=1
and use it in place of EBSC (ρ). However, this requires a much more expensive optimization, and in practice it was found to give very similar results with EBSC (ρ) in simulation experiments.
18
3.4
Capacity analysis
For a fixed realization of the geometry, the N coordinates form independent binary symmetric channels with crossover probabilities pa,1 , . . . , pa,N . If these realized reliabilities are known to the decoder, the total capacity over the N bits is, N X
(1 − h2 (pa,i )) .
i=1
Thus the geometry-aware capacity benchmark is, log2 K <
N X
(1 − h2 (pa,i )) .
i=1
Since the pa,i ’s are i.i.d. after averaging over the random geometry, by the law of large numbers, N
1 X (1 − h2 (pa,i )) −→ E [1 − h2 (pa,1 )] , N i=1
and the geometry-aware capacity benchmark reads, log2 K < Cgeom (ρ) + o(1), N where the geometry-aware capacity is, Cgeom (ρ) := 1 − E [h2 (Q(ρ|Z|))] ,
Z ∼ N (0, 1).
(16)
Comparison via Jensen’s inequality. Since the binary entropy function h2 is concave on [0, 1], Jensen’s inequality immediately gives, Cgeom (ρ) = 1 − E[h2 (Q(ρ|Z|))] ≥ 1 − h2 (E[Q(ρ|Z|)]) = 1 − h2 (p) = CBSC (ρ). Thus the geometry-aware capacity is always at least as large as the homogeneous BSC capacity. The improvement comes from exploiting the realized reliabilities of the individual bits rather than replacing them by their average crossover probability.
3.5
Maximum likelihood decoding
It is easy to see that Hamming decoding is not optimal in the geometry-aware setting. We now consider the optimal maximum likelihood decoder, which uses both the binary signs and the corresponding margins. For each class m and coordinate i, ⊤ |ui xm | pm,i := Q . σ Under hypothesis m, the observed bit Bi satisfies, Pr(Bi = Cm,i | m) = 1 − pm,i , 19
Pr(Bi ̸= Cm,i | m) = pm,i ,
and the likelihood of a candidate class m is, N Y
Pm (B) =
[(1 − pm,i )1{Bi = Cm,i } + pm,i 1{Bi ̸= Cm,i }] .
i=1
The geometry-aware maximum likelihood decoder is, m b ML ∈ arg
max m∈{1,...,K}
Pm (B).
Theorem 7. In the orthogonal hyperplanes setting of Section 3.1, a sufficient condition to ensure that the probability of error satisfies Pr(E) ≤ δ is, N≥
log((K − 1)/δ) , EML (ρ)
where, with Z ∼ N (0, 1), the corresponding ML error exponent is defined as, h i2 p p 1 EML (ρ) = − log 1 − Q(ρ|Z|) + Q(ρ|Z|) . EZ 2
(17)
Proof. The proof follows a Chernoff information analysis. Suppose the transmitted class is a. Fix a competitor b ̸= a. Let Pa and Pb denote the product distributions of the observed bit vector B under hypotheses a and b, respectively, given the geometry. The pairwise ML confusion N event is, {Pb (B) ≥ Pa (B)}. Conditional on xK 1 , u1 , for any s ∈ [0, 1], Markov’s inequality gives, Pb (B) s K N Pb (B) s K N K N ≥ 1 x1 , u1 ≤ E x1 , u1 . Pr Pb (B) ≥ Pa (B) x1 , u1 = Pr Pa (B) Pa (B) Since the bits B1 , . . . , BN are independent under each hypothesis (as before), E
Pb (B) Pa (B)
s
N xK 1 , u1
=
N Y X
Pa,i (β)
i=1 β∈{±1}
Pb,i (β) Pa,i (β)
s =
N Y X
Pa,i (β)1−s Pb,i (β)s .
i=1 β∈{±1}
Defining the coordinate Chernoff coefficient, X (ab) Zi (s) := Pa,i (β)1−s Pb,i (β)s , β∈{±1}
gives the conditional pairwise error bound, N Pr(Pb (B) ≥ Pa (B) | xK 1 , u1 ) ≤
N Y
(ab)
Zi
(s).
(18)
i=1
Now average over the random geometry xa , xb . Since xa and xb are i.i.d. Gaussian, as before, d
d
pb,i = Q(ρ|Zb |),
pa,i = Q(ρ|Za |), iid
where Za , Zb ∼ N (0, 1). Furthermore, the signs Ca,i and Cb,i are independent fair signs, independent of the magnitudes: Pr(Ca,i = Cb,i ) = Pr(Ca,i ̸= Cb,i ) = 1/2. If Ca,i = Cb,i , then, (ab)
Zi
s (s) = (1 − pa,i )1−s (1 − pb,i )s + p1−s a,i pb,i ,
20
and if Ca,i ̸= Cb,i , then, (ab)
Zi
s (s) = (1 − pa,i )1−s psb,i + p1−s a,i (1 − pb,i ) .
Therefore, denoting for simplicity of notation for the corresponding coordinate i, pa = pa,i , 1 1 (ab) s 1−s s s pb + p1−s E[Zi (s)] = E (1 − pa )1−s (1 − pb )s + p1−s a pb + E (1 − pa ) a (1 − pb ) . 2 2 Combining terms, 1 (ab) (1 − pb )s + psb . E[Zi (s)] = E (1 − pa )1−s + p1−s a 2 Since pa and pb are i.i.d. copies of a random variable q with distribution q ∼ Q(ρ|Z|), 1 (ab) E[Zi (s)] = Eq (1 − q)1−s + q 1−s Eq [(1 − q)s + q s ] . 2 Using the definition, Mρ (s) = Eq [(1 − q)s + q s ] , we obtain, 1 (s)] = Mρ (1 − s)Mρ (s) = Ψρ (s). 2 Since the coordinates are i.i.d., averaging over the random geometry and applying the union bound over the K − 1 competitors in (18) gives, (ab)
E[Zi
Pr(E) ≤ (K − 1) inf Ψρ (s)N . 0≤s≤1
(19)
It remains to identify the optimizer. The function Mρ (s) is log-convex as a function of s; this follows from a standard log-convexity argument for Chernoff coefficientsusing Hölder’s inequality. In particular, fix s0 , s1 ∈ [0, 1] and λ ∈ [0, 1], and consider s = (1 − λ)s0 + λs1 . Then, h i Mρ (s) = Eq [(1 − q)s + q s ] = Eq ((1 − q)s0 )1−λ ((1 − q)s1 )λ + (q s0 )1−λ (q s1 )λ . By Hölder’s inequality, Mρ (s) ≤ (Eq [(1 − q)s0 + q s0 ])1−λ (Eq [(1 − q)s1 + q s1 ])λ = Mρ (s0 )1−λ Mρ (s1 )λ , so Mρ (s) is log-convex, hence log Ψρ (s) is also log-convex, and therefore Ψρ (s) is convex in s. Since, Ψρ (s) = Ψρ (1 − s), it is also symmetric around s = 1/2. Therefore, as a convex and symmetric function, Ψρ (s) is minimized at its mid-point s = 1/2: i2 p 1 hp √ i2 1 hp E EZ 1−q+ q 1 − Q(ρ|Z|) + Q(ρ|Z|) = , Ψρ (s) ≥ Ψρ (1/2) = 2 2 where Z ∼ N (0, 1). Substituting in the above bound (19) and re-arranging gives the corresponding ML exponent and completes the proof. Remark. Theorem 7 gives an achievability condition of the same form as Theorem 6, showing that again N = O(log K) hyperplanes are sufficient. Comparing the corresponding multiplicative constants, Jensen’s inequality directly shows that EML (ρ) ≥ EBSC (ρ). In specific, since the √ √ function g(q) = 1 − q + q is concave on [0, 1], Jense’s gives, hp i p p √ EZ 1 − Q(ρ|Z|) + Q(ρ|Z|) = EZ [g(Q(ρ|Z|))] ≤ g(EZ [Q(ρ|Z|)]) = g(p) = 1 − p + p. Squaring both sides, multiplying by 1/2, and rearranging shows that EML (ρ) ≥ EBSC (ρ), which verifies that the ML Chernoff exponent always gives an improved bound. 21
3.6
Order-statistics error formulas
The Chernoff analysis gives clean exponential upper bounds and highlights the relevant error exponents. These bounds are especially useful for deriving achievability conditions of the form N ≳ log K/E(ρ). However, the union bound over competitors can be conservative, particularly at finite K and N . To obtain sharper approximations, we next exploit the order-statistic structure of the decoding rule: Conditional on the score of the true class, the scores of the K − 1 competing classes are independent, so the probability of error can be written as the probability that the maximum competitor score exceeds the true score. This leads to more precise finite-sample formulas, at the cost of less explicit expressions than the Chernoff exponents. 3.6.1
Hamming decoding
The Hamming decoder is, b a = arg min dH (B, Cm ). m
Proposition 1. In the orthogonal hyperplanes setting of Section 3.1, the probability of error of the Hamming decoder satisfies, PeHam =
N X N r=0
r
h i pr (1 − p)N −r 1 − (1 − FN (r))K−1 ,
(20)
where p = π1 arctan ρ1 , and FN (r) denotes the cumulative distribution function of the symmetric Binomial random variable, FN (r) = Pr Binomial N, 21 ≤ r . Proof. Let a denote the true class as before and define, Ra := dH (B, Ca ). Conditional on Ca and B, the wrong codewords Cb are i.i.d. and uniform on {±1}N , so that, dH (B, Cb ) ∼ Binomial (N, 1/2) . For any competitor b ̸= a, the probability that it does not beat the true class is given by 1 − FN (Ra ). Since the K − 1 wrong codewords are conditionally independent, the probability that no wrong class beats or ties the true class is, (1 − FN (Ra ))K−1 . Averaging over Ca and B, or equivalently over Ra , gives the exact Hamming error probability, h i Pr(E) = ERa 1 − (1 − FN (Ra ))K−1 . (21) It remains to compute the above expectation. Conditional on pa,1 , . . . , pa,N , the true distance is, Ra =
N X
Ei ,
Ei | pa,i ∼ Bernoulli(pa,i )
i=1
independently. Therefore its conditional probability-generating function is given by, E[tRa | pa,1 , . . . , pa,N ] =
N Y i=1
22
(1 − pa,i + pa,i t) .
Averaging over the i.i.d. pa,1 , . . . , pa,N gives the unconditional probability-generating function, "N # N Y Y Ra E[t ] = E (1 − pa,i + pa,i t) = E [1 − pa,i + pa,i t] . = (1 − p + pt)N , i=1
i=1
which is the probability-generating function of Binomial(N, p). Hence, unconditionally, we get, Ra ∼ Binomial(N, p), where, as before, p = π1 arctan ρ1 . Substituting appropriately the Binomial distribution in (21) completes the proof. Conclusion. Proposition 1 shows that, perhaps surprisingly, in this setting we are able to obtain an exact, finite-N closed-form expression for the Hamming probability of error. This formula is particularly useful for numerical evaluation, since it can be computed in just O(N ) operations. Nevertheless, since the finite-sum expression does not directly expose the scaling of the error probability with N , K, and ρ, the Chernoff bound derived above still remains useful: It isolates a simple exponential rate, gives an interpretable error exponent, and leads directly to achievability condition of the form N ≳ log K/E(ρ). 3.6.2
Maximum likelihood decoding
The log-likelihood score for class m is, Lm (B) =
N X
[1{Bi = Cm,i } log(1 − pm,i ) + 1{Bi ̸= Cm,i } log pm,i ] .
i=1
The ML decoder chooses, b aML = arg max Lm (B), m
and an ML error occurs if there exists b ̸= a such that Lb (B) ≥ La (B). Conditional on the trueclass score La and on the observed vector B, the wrong-class scores Lb (B), are i.i.d. Therefore, h i PeML = ELa ,B 1 − (1 − Pr (Lb (B) ≥ La | La , B))K−1 . For each wrong class b ̸= a, the competitor bits Cb,i are fair signs relative to the fixed observed vector B; and they are independent of the corresponding probabilities pb,i . Hence, the conditional distribution of the wrong-class score does not depend on the realized value of B, and, h i PeML = ELa 1 − (1 − Pr (Lb ≥ La | La ))K−1 . Now, it turns out that the distributions of La and Lb admit simple scalar-sum distributions, La =
N X
Si ,
Lb =
i=1
N X
Ti ,
i=1
where it remains to define the true-score and wrong score increments Si and Ti , respectively. Conditional on the true-class realized probability pa,i , the i-th true-score increment is, ( log pa,i , with probability pa,i , Si = log(1 − pa,i ), with probability 1 − pa,i , 23
iid
where, as before, pa,i = Q(ρ|Zi |), with Zi ∼ N (0, 1). So, S1 , . . . , SN are i.i.d. scalar increments. Similarly, the i-th wrong-score increment is given by, ( log qi , with probability 1/2, Ti = log(1 − qi ), with probability 1/2, iid
where qi = Q(ρ|Zi′ |), with Zi′ ∼ N (0, 1), independently of the true-class variables. Therefore T1 , . . . , TN are i.i.d. and independent of La . So, by defining the wrong-score tail function, ! N X GN (t) := Pr Ti ≥ t , i=1
the ML probability of error can be written as, PeML = ES1 ,...,SN 1 −
1 − GN
N X
!!K−1 . Si
(22)
i=1
Remark. The above expression can be evaluated by Monte Carlo (MC) over scalar i.i.d. sums, or by numerical convolution of the one-coordinate score distributions. The details of an appropriate Monte Carlo sampler are given in Appendix B; while this computation is more expensive than the direct Hamming formula, it is still much cheaper than simulating the full K-class experiment. The resulting MC estimate gives sharp finite-N predictions for the probability of error compared, but – unlike our previous Chernoff analysis – does not directly expose an exponential scaling law or lead to a simple closed-form achievability condition.
3.7
Simulation results
In this section, we run appropriate simulation experiments to empirically validate the main theoretical findings for the orthogonal hyperplanes setting. In specific, we inspect the empirical probability of error, together with the corresponding Chernoff upper bounds and order statistics expressions we derived, both for Hamming and ML decoding. In order to examine which values of the SNR parameter ρ seem practically relevant, in Table 1 we present a range of values for ρ together with their corresponding induced crossover probabilities p = π1 arctan(1/ρ), which play a key role in much of the above analysis. ρ
0.1
0.5
1
2
5
10
p
0.468
0.352
0.250
0.148
0.063
0.032
Table 1: Average crossover probability p = π1 arctan ρ1 for different values of ρ.
Here, we focus on the representative cases ρ = 1 and ρ = 2, which correspond to practically relevant intermediate crossover probabilities. Results for more extreme regimes, where p is closer either to 1/2 or to 0, can be found in Appendix C. These additional plots exhibit the same qualitative behavior as the cases reported here. The main effect of increasing ρ is to reduce the crossover probability and shift all error curves towards smaller values of N , so that the same 24
target error probability can be achieved using fewer hyperplanes. In all cases, the results are obtained from 104 repetitions of the experiment, using K = 32 class labels. The results presented in Figure 4 provide strong empirical validation of the theoretical predictions. First, the derived Chernoff expressions (15)-(19) give valid upper bounds on the probability of error for both Hamming and ML decoding, respectively. Although these bounds are somewhat loose at finite N , they correctly capture the exponential decay of the error probability and lead to clean achievability conditions of the form, N ≳ log K/E(ρ), where E(ρ) is the corresponding error exponent (Hamming or ML), that depends on the SNR. Second, ML decoding consistently and often substantially outperforms Hamming decoding. This highlights the importance of accounting for the unequal reliability of the individual binary decisions, and shows that treating all decisions equally, as in Hamming decoding or in a majorityvoting rule, can be significantly suboptimal in general classification problems.
Figure 4: Probability of error as a function of the number of orthogonal hyperplanes. Left: ρ = 1, Right: ρ = 2
Finally, the derived order-statistics expressions closely follow the empirical error curves, providing a more accurate finite-N characterization than the Chernoff bounds and further validating the theory. The small systematic discrepancy observed for the Hamming order-statistic curve is explained by the treatment of ties, since the analytical expression counts every tie with a competing class as an error, whereas the simulations use random tie-breaking. Consequently, the theoretical Hamming order-statistic curve is slightly conservative.
4
Random hyperplanes with noise
We now return to the original setting of practical interest, in which the hyperplanes are drawn randomly, and are no longer assumed to be orthogonal. The analysis of the orthogonal model provides a useful benchmark for this setting, since in sufficiently high dimensions i.i.d. random hyperplanes are approximately orthogonal; this high-dimensional regime is studied in detail in Section 4.4. Viewed as a communication channel, the critical difference from the orthogonal setting is that the coordinate bitflips are no longer independent.
25
4.1
Model description
The centers and test-point are generated exactly as before, with the true class a: iid
x1 , . . . , xK ∼ N (0, τ 2 Id ),
z ∼ N (0, σ 2 Id ),
y = xa + z.
The hyperplanes are now sampled independently as, iid
u1 , . . . , uN ∼ Unif(S d−1 ). The binary codeword of xk , and the observed binary vector are again denoted as, ⊤ ⊤ ⊤ Ck = sign(u⊤ x ), . . . , sign(u x ) , B = sign(u y), . . . , sign(u y) . 1 k N k 1 N In this setting, it is convenient to also define the following angles, α := ∠(xa , y),
4.2
θb := ∠(xa , xb ),
βb := ∠(xb , y).
(23)
Hamming decoder
First, we again consider the Hamming decoder, b a = arg min dH (B, Cm ). m
By appropriately applying a Chernoff analysis, we are again able to obtain an upper bound on the probability of error in this setting. Theorem 8. In the random hyperplanes setting of Section 4.1, the probability of error using a Hamming decoder satisfies, Pr(E) ≤ (K − 1)Bd,ρ (N ), (24) where, i h Bd,ρ (N ) := Exa ,z,xb e−N Eiid (θb ,α,βb ) ,
(25)
and, q − log 1 − θb + 1 θ2 − (βb − α)2 , b π π Eiid (θb , α, βb ) = 0,
βb ≥ α,
(26)
βb < α,
with the definition of the angles α, θb , βb as in (23). Proof. Fix a competitor b ̸= a, and as before define, (ab)
Mi
:= 1{Bi ̸= Cb,i } − 1{Bi ̸= Ca,i }. (ab)
(27)
Conditional on xa , xb , z, the random variables Mi are i.i.d. since the hyperplanes ui are i.i.d., and their corresponding conditional distribution is given in the following lemma.
26
(ab)
Lemma 4. Given xa , xb , z, the conditional law of Mi (ab)
a+ := Pr(Mi
∈ {−1, 0, +1} is,
= +1 | xa , xb , z) =
θb + β b − α , 2π
θb − β b + α , 2π θb (ab) a0 := Pr(Mi = 0 | xa , xb , z) = 1 − , π where the angles α, θb , βb are defined in (23). (ab)
a− := Pr(Mi
= −1 | xa , xb , z) =
(ab)
Proof. Since Mi ̸= 0 exactly when the hyperplane ui separates xa and xb , by rotational symmetry of the random hyperplane sampling we get, (ab)
Pr(Mi
̸= 0 | xa , xb , z) = a+ + a− =
θb , π
(28)
where for simplicity of notation we omit conditioning on xa , xb , z for rest of this proof. Now, by (ab) taking expectations in the definition of Mi in (27), we get, (ab)
E[Mi
⊤ ⊤ ⊤ ] = P(Bi ̸= Cb,i )−P(Bi ̸= Ca,i ) = P(sign(u⊤ i y) ̸= sign(ui xb ))−P(sign(ui y) ̸= sign(ui xa )),
and by rotational symmetry this gives, (ab)
E[Mi
]=
βb α (ab) (ab) − = Pr(Mi = +1) − Pr(Mi = −1) = a+ − a− π π
(29)
Solving the system of equations (28)-(29) for a+ , a− completes the proof of the lemma. Now, for any s ≥ 0, conditional on xa , xb , z, a Chernoff bound gives, ! " ! # N N X X (ab) (ab) Pr Mi ≤ 0 xa , xb , z ≤ E exp −s Mi xa , xb , z , i=1
i=1 (ab)
and since the random variables Mi
are conditionally independent, from Lemma 4, we get, ! N X N (ab) Pr (dH (B, Cb ) ≤ dH (B, Ca ) | xa , xb , z) = Pr Mi ≤ 0 xa , xb , z ≤ a+ e−s + a− es + a0 i=1
Optimizing over s, if βb ≥ α, the minimizer is, s⋆ =
a+ 1 θb + β b − α 1 log = log . 2 a− 2 θb − β b + α
If βb ≥ α, we get s⋆ ≥ 0, and substituting this value gives, q 1 θb inf a+ e−s + a− es + a0 = 1 − + θb2 − (βb − α)2 . s≥0 π π If βb < α, then s∗ < 0, and the infimum over s ≥ 0 is attained at s = 0, giving the trivial bound 1. So, with the definition of Eiid (θb , α, βb ) from (26), we get the pairwise error bound, Pr (dH (B, Cb ) ≤ dH (B, Ca ) | xa , xb , z) ≤ e−N Eiid (θb ,α,βb ) , 27
and taking a union bound over the competitors b ̸= a, gives the conditional probability of error bound, X Pr(E|xK , z) ≤ e−N Eiid (θb ,α,βb ) . (30) 1 b̸=a
Finally, averaging over the random centers xK 1 and the noise z, we get the required result by the tower property, since all competitors b ̸= a are identically distributed by symmetry. Remarks. Theorem 8 gives an upper to the probability of error of Hamming decoding. Unlike the orthogonal-hyperplane bound, Bd,ρ (N ) is not available in closed form, so the result does not immediately yield an explicit achievability condition of the form N ≳ log K/E(ρ). Nevertheless, the form of Bd,ρ (N ) allows to evaluate the bound efficiently by direct Monte Carlo, without requiring to simlulate the N hyperplanes. Moreover, by analysing the asymptotic behavior of Bd,ρ (N ), we are able to obtain a clean achievability condition in sufficiently high dimensions. 4.2.1
Numerical evaluation of the Hamming bound
First, it is noted that the expectation in (25) directly leads to a simple Monte Carlo estimate for Bd,ρ (N ), by obtaining T Gaussian samples of xa , xb , z in Rd : 1 Bbd,ρ (N ) = T (t)
T X
e−N Eiid (θ
(t) ,α(t) ,β (t) )
,
t=1
(t)
where xa , xb ∼ N (0, τ 2 Id ), z (t) ∼ N (0, σ 2 Id ), and the corresponding angles α(t) , β (t) , θ(t) are directly obtained from (23). Importantly, this simple estimate does not require to simulate N hyperplanes. Furthermore, it turns out that rotational invariance can be exploited to give an alternative lower-dimensional expression for Bd,ρ (N ), which therefore leads to a low-dimensional Monte Carlo sampler, that avoids d-dimensional sampling. This low-dimensional expression is given in the following proposition, proven in Appendix A. Proposition 2. For d > 2, an alternative expression for Bd,ρ (N ) is, h i Bd,ρ (N ) = ER,G,S,V1 ,V2 e−N Eiid (θ,α,β) , where the corresponding angles are given by, ! ρR + G α = arccos p , θ = arccos(V1 ), (ρR + G)2 + S 2
β = arccos(V1 cos α + V2 sin α),
and the expectation is over, R ∼ χd , G ∼ N (0, 1), S ∼ χd−1 , and (V1 , V2 ) with density, fd (v1 , v2 ) = 4.2.2
d−2 (1 − v12 − v22 )(d−4)/2 , 2π
v12 + v22 ≤ 1.
High-dimensional asymptotics: d → ∞, fixed N
In sufficiently high dimensions, we expect the random hyperplanes to behave as orthogonal hyperplanes due to the concentration of angles. This phenomenon is studied in its full generality in Section 4.4. In the following lemma, a much weaker – yet useful – statement is shown, namely, that as d → ∞ we recover the BSC achievability condition from Theorem 5. 28
Lemma 5. For fixed N > 0 and ρ > 0, as d → ∞, Bd,ρ (N ) → e−N EBSC (ρ) , and therefore a sufficient condition to ensure Pr(E) ≤ δ is, N≥
log((K − 1)/δ) . EBSC (ρ)
Proof. First, consider the angle α = ∠(xa , xa + z), so that, cos α =
x⊤ a (xa + z) , ∥xa ∥∥xa + z∥
where xa ∼ N (0, τ 2 Id ), z ∼ N (0, σ 2 Id ). By the law of large numbers, we easily get the concentration of Gaussian norms and inner products, ∥xa ∥2 P 2 →τ , d
x⊤ az P → 0. d
∥z∥2 P 2 →σ , d
Therefore,
ρ =p 1 + ρ2
τ
P
cos α → √
τ 2 + σ2
and since arccos is continuous, ρ
P
α → α∞ = arccos
p 1 + ρ2
!
1 = arctan . ρ
Similarly, since xb is independent of both xa and y = xa + z, its direction is asymptotically orthogonal to both, and the high-dimensional concentration of angles yields, P
θb = ∠(xa , xb ) →
π , 2
P
βb = ∠(xb , y) →
π . 2
Since ρ > 0, we have α∞ = arctan 1/ρ < π/2, and hence βb > α. Therefore, P
π
π
e−N Eiid (θb ,α,βb ) −→ e−N Eiid ( 2 ,α∞ , 2 ) , and since e−N Eiid (θb ,α,βb ) is uniformly bounded, we also get convergence in expectation, π
π
Bd,ρ (N ) = Exa ,xb ,z [e−N Eiid (θb ,α,βb ) ] → e−N Eiid ( 2 ,α∞ , 2 ) . Substituting in (26), and noting that p = απ∞ = π1 arctan ρ1 , completes the proof, since it finally yields, Eiid π2 , α∞ , π2 = EBSC (ρ).
29
4.2.3
Large-N asymptotics: N → ∞, fixed d
For fixed d, as N → ∞, Hamming distances converge to angular distances. In particular, N
1 X 1 P ∠(y, xm ) dH (B, Cm ) = 1{Bi ̸= Cm,i } → , N N π i=1
The convergence follows from the law of large numbers, since conditional on xm , y the indicator random variables are i.i.d. Bernoulli with p = ∠(y, xm )/π. Therefore, for any fixed realization of xK 1 , z, the Hamming decoder converges to angular nearest-neighbor decoding: b aHam → arg min ∠(y, xm ). m
Therefore, for any fixed d, the limiting probability of error is given by, Pe∞ = Pr min βb < α . b̸=a
In the following proposition, we derive an exact and numerically tractable expression for the limiting probability of error, which can be evaluated efficiently by low-dimensional Monte Carlo. Its proof follows an order statistics argument, and is given in Appendix A. Proposition 3. In the random hyperplanes setting of Section 4.1, for the probability of error of Hamming decoding, as N → ∞ we get, " K−1 # d − 1 d − 1 PeHam → Pe∞ = Pr min βb ≤ α = Eα 1 − I 1+cos α , , (31) 2 b̸=a 2 2 where Ix (a, b) denotes the regularized incomplete beta function, and, ρR + G cos α = p , (ρR + G)2 + S 2 with R ∼ χd , G ∼ N (0, 1), S ∼ χd−1 , mutually independent. Remark 1. For every finite d ≥ 2 and finite ρ < ∞, the limiting probability of error is strictly positive. Moreover, since Ix (a, b) is strictly increasing in x, the limiting probability of error is strictly decreasing with ρ. In particular, as ρ → ∞, Pe∞ → 0, and as ρ → 0, Pe∞ → 1 − 1/K. Remark 2. For any ρ > 0, Pe∞ → 0 as d → ∞, showing that in high dimensions the limiting probability of error vanishes. In fact, a more refined asymptotic analysis of the above expression (e.g., via Stirling’s approximation) suggests that the decay is exponential in d.
4.3
Maximum likelihood decoding
As before, Hamming decoding is not optimal in this setting, so we can again consider ML decoding to improve performance. Let, ⊤ u1 .. U = . ∈ RN ×d , B = sign(U y) ∈ {±1}N . u⊤ N
30
Under hypothesis m, z ∼ N (0, σ 2 Id ).
y = xm + z, so that, U y = U xm + U z, and finally,
U y ∼ N (U xm , σ 2 U U ⊤ ). Therefore, the likelihood of a candidate class m is, Gm ∼ N (U xm , σ 2 U U ⊤ ).
Pm (B) = Pr (sign(Gm ) = B) ,
In general, U U ⊤ ̸= IN , so the likelihood does not factor over coordinates as in the orthogonal hyperplanes setting. So computing the likelihood Pm (B) corresponds to computing an N dimensional correlated Gaussian orthant probability. The numerical evaluation of Gaussian orthant probabilities is a well-studied problem in the statistics literature, which becomes excessively hard as the dimension grows; see, e.g., [23]. Numerous approaches have been proposed, including numerical integration, importance-sampling, and sequential Monte Carlo methods [23, 11, 14, 12]. Although these methods can be effective in moderate dimensions (typically up to few tens, depending on the specific problem), in high dimensions the problem remains challenging. In our setting, ML decoding becomes already impractical for moderate values of N around N ≥ 50; see also the simulations section below. For this reason, we introduce the following approximate ML (‘pseudo-ML’) decoder, by assuming that bitflips are independent across coordinates. In the next section, we show that in sufficiently high dimensions, this decoder effectively achieves the same performance as the true ML decoder, while being computationally efficient. This observation is empirically validated in the simulations section, where we illustrate the practical utility of the pseudo-ML decoder. 4.3.1
Approximate pseudo-ML decoder
The pseudo-ML decoder assumes that bitflips are independent, as in the orthogonal hyperplanes setting. As before, for candidate m, we define the realized crossover probabilities, ⊤ |ui xm | pm,i = Q , σ for i = 1, ..., N . The pseudo-likelihood score of candidate m is defined exactly as in the orthogonal hyperplanes setting, by assuming that bitflips are independent across coordinates, Pem (B) =
N Y
[(1 − pm,i )1{Bi = Cm,i } + pm,i 1{Bi ̸= Cm,i }] ,
i=1
and the approximate pseudo-ML decoder is given by, m b pML = arg max Pem (B). m
This decoder is exactly ML in the orthogonal hyperplanes setting. For random hyperplanes, it is a valid reliability-aware mismatched decoder, but not the optimal one, since it uses the realized probabilities pm,i but ignores cross-bit correlations. In high dimensions, where random
31
hyperplanes are approximately orthogonal, we expect this decoder to actually perform similarly with the true ML decoder; this is studied in detail in the next section. It is noted that Chernoff analysis allows to obtain an upper bound to the probability of error of the pseudo-ML decoder; see Appendix A for more details. However, the resulting bound does not directly give a clean achievability condition for the required number of hyperplanes, and does not simplify enough to allow for an efficient Monte Carlo estimate.
4.4
Theoretical justification of the high-dimensional orthogonal limit
As described before, in sufficiently high dimensions we expect random hyperplanes to behave similarly with orthogonal hyperplanes, which provides the main motivation for the careful analysis of the orthogonal-hyperplanes setting in previous sections. We now provide strong theoretical justifications of this high-dimensional orthogonal limit. In terms of quantifying the modes of this convergence, we consider the following relevant regimes: a) Covariance-level convergence of the projected noise vector, and b) Full blocklikelihood convergence of the observed binary vector. In general, the first condition provides a practical rule of thumb for when to expect random hyperplanes to behave as approximately orthogonal, while the second gives a strong sufficient condition ensuring that the complete observation model has converged in a strict sense. These theoretical findings are also empirically validated in the following experimental section. 4.4.1
Covariance-level convergence
With notation as before, the exact sign likelihood under class m is, Pm (B) = Pr {sign(Gm ) = B} ,
Gm ∼ N (U xm , σ 2 U U ⊤ ).
The first sense in which random hyperplanes approximate the orthogonal model is through the projected-noise covariance, i.e., when, U U ⊤ ≈ IN . Since likelihood-based decoding depends on the full N -dimensional Gaussian covariance, this matrix approximation is naturally measured in operator norm. In the following, ∥ · ∥op denotes the spectral norm, or equivalently, the largest singular value of the matrix. ⊤ u1 iid Proposition 4. Let u1 , . . . , uN ∼ Unif(S d−1 ), U = ... ∈ RN ×d . If N/d → 0, then,
U U ⊤ − IN
op
= Op
u⊤ N r ! N P −→ 0. d
Proof.√The proof follows directly from standard random matrix theory. For example, by defining A := d U ⊤ ∈ Rd×N , its columns are √ independent, centered, isotropic sub-Gaussian random vectors in Rd , with norms ∥Ai ∥2 = d, almost surely. Also, under N/d → 0, we have N ≤ d eventually, and standard Gram-matrix concentration for such matrices gives, r ! 1 ⊤ N A A − IN = Op , d d op e.g., by Theorem 5.58 and Remark 5.59 of [27]. The required result follows directly. 32
Remark. Thus, d ≫ N is the natural covariance-level regime in which random hyperplanes behave approximately as orthogonal; this is also validated in the simulations section. This covariance convergence is, however, only a first-order notion of approximation. The stronger notion of convergence of the full block-likelihood of the N -bit vector is studied next. 4.4.2
Full block-likelihood convergence
A natural strong notion of convergence to the orthogonal limit is convergence of the full blocklikelihood in total variation. This is a natural notion of convergences since it ensures that every decoder has asymptotically the same probability of error probability under the two observation models (i.e., under orthogonal or random hyperplanes). In specific, for two probability distributions P and Pe on {±1}N , and any decoder rule m b : {±1}N → {1, . . . , K}, b ̸= m) ≤ dTV (P, Pe). Pr(m(B) b ̸= m) − Pr(m(B) P
Pe
In our setting, for any observed binary vector B ∈ {±1}N , define the likelihood of class m as, Pm (B) = Pr {sign(Gm ) = B} ,
Gm ∼ N (U xm , σ 2 U U ⊤ ),
(32)
and the corresponding pseudo-likelihood as, n o em ) = B , Pem (B) = Pr sign(G
e m ∼ N (U xm , σ 2 IN ). G
(33)
Proposition 5. Let Pm and Pem denote the likelihood and pseudo-likelihood of class m, as defined in (32)-(33), respectively. If N 2 /d → 0, then for every class m, N P e dTV (Pm , Pm ) = Op √ −→ 0. d Proof. By Pinsker’s inequality, it is sufficient to consider the relative entropy between Pm and Pem . Set Σ := U U ⊤ , µm := U xm . By the data-processing inequality for relative entropy, applied to the coordinatewise sign map, DKL (Pm ∥Pem ) ≤ DKL N (µm , σ 2 Σ) N (µm , σ 2 IN ) . Since the two Gaussian distributions have the same mean, 1 1 DKL N (µm , σ 2 Σ) N (µm , σ 2 IN ) = [tr(Σ) − N − log det Σ] = − log det Σ, 2 2 since every diagonal entry of Σ equals one, and therefore tr(Σ) = N . P
Let ∆ := Σ − IN . By Proposition 4, in this regime we have ∥∆∥op −→ 0, so we can apply a relevant Taylor expansion to the log-determinant term, log det Σ = log det(IN + ∆) = tr(∆) −
1 tr(∆2 ) + O ∥∆∥op ∥∆∥2F , 2
which follows by applying the Taylor expansion of log(1 + x) to the eigenvalues of ∆. Since tr(∆) = tr(Σ) − N = 0, and ∆ is symmetric, we obtain, 1 DKL N (µm , σ 2 Σ) N (µm , σ 2 IN ) = ∥∆∥2F + O ∥∆∥op ∥∆∥2F . 4 33
Moreover, by Proposition 4, we can bound the Frobenius norm as, 2 N 2 2 , ∥∆∥F ≤ N ∥∆∥op = Op d and since ∥∆∥op = op (1), the remainder is of smaller order, so, DKL (Pm ∥Pem ) ≤ DKL N (µm , σ 2 Σ) N (µm , σ 2 IN ) = Op
N2 d
.
By Pinsker’s inequality, we finally get, r dTV (Pm , Pem ) ≤
1 DKL (Pm ∥Pem ) = Op 2
N √ d
.
Corollary 2. Let PeML and PepML denote the error probabilities of the true-ML and pseudo-ML decoders, respectively. If N 2 /d → 0, then, N P pML ML 0 ≤ Pe − Pe = Op √ −→ 0. d Proof. The result follows immediately from the optimality of the true-ML decoder under Pm , the optimality of pseudo-ML decoder under Pem , and the fact that the error probability of any fixed decoder changes by at most the total-variation distance between the two observation laws. Conclusion. Hence, d ≫ N 2 provides a strong sufficient condition, ensuring convergence, in total variation, of the full N -bit likelihood to its orthogonal approximation. In this highdimensional regime, the proposed pseudo-ML decoder, that does not take into account correlations among the coordinate bitflips, is proven to be essentially optimal, while remaining computationally efficient. More generally, the detailed orthogonal-hyperplane analysis conducted in the previous section becomes asymptotically relevant in this high-dimensional regime, including the corresponding error exponents, achievability conditions and so on. In the following section, we conduct simulation experiments to validate the above theoretical findings. In practice, it turns out that the condition d ≫ N 2 appears to be conservative, in the sense that pseudo-ML decoding can perform nearly as well as true-ML at much lower dimensions. In fact, as a general rule of thumb, it appears that having a number of dimensions comparable to the number of hyperplanes seems to be enough for the two decoders to achieve similar error probabilities. These empirical findings are illustrated in detail in the next section.
4.5
Simulation results
In this section, we conduct simulation experiments to validate the preceding theoretical results, investigate the empirical performance of Hamming and pseudo-ML decoding, and obtain the practical high-dimensional regime in which pseudo-ML essentially performs as true-ML. All Hamming and pseudo-ML results are obtained from 104 repetitions of the experiment. For true-ML, in order to compute the high-dimensional Gaussian orthant probabilities we use the Geweke-Hajivassiliou-Keane (GHK) algorithm [11, 12, 14]; see also our relevant discussion in 34
Section 4.3. Since this computation quickly becomes excessively expensive, we evaluate the performance of true-ML up to N ≈ 30–40, using 103 repetitions of each experiment. In Figure 5, the experimental results are presented for a setting with K = 32 classes in three representative dimensional regimes: d = 5, d = 20, and d = 100, corresponding respectively to low, intermediate, and high dimensions. Overall, the results provide empirical validation of the theoretical predictions of the previous sections, and strongly support the use of the computationally efficient pseudo-ML decoder.
Figure 5: Probability of error as a function of the number of hyperplanes. Top Left: d = 5, Top Right: d = 20, Bottom: d = 100.
Figure 5 clearly illustrates that pseudo-ML can in practice perform nearly as well as trueML even in moderately low dimensions, despite being computationally much more efficient. In particular, the results suggest that pseudo-ML closely tracks the performance of true-ML even when the ambient dimension is only of the same order as the number of hyperplanes. Specifically, only in the very low-dimensional example d = 5 there seems to be an apparent gap between their corresponding error curves, and this happens only after N ≥ 15. In moderate and high dimensions where d = 20 and d = 100, pseudo-ML essentially achieves identical performance with true-ML all the way up to N = 30, where both decoders seem to converge to their limiting probability of error. Thus, the theoretical condition d ≫ N 2 , which guarantees convergence of the full-block likelihood in total variation, appears to be conservative in practice, and pseudo-ML decoding can perform essentially as true-ML at much lower dimensions. As predicted from Proposition 3, as N grows large, the probability of error of Hamming decoding converges to its derived limit in (31), which is also plotted in Figure 5. In addition, it is observed that this limiting error floor decreases rapidly with the ambient dimension, with the simulations exhibiting the exponential decay predicted by the theory. The high-dimensional 35
BSC limit of Hamming decoding is also empirically validated: For d = 100, we plot the BSC error bound from (15), which closely matches the corresponding Chernoff bound (24), therefore verifying the results of Lemma 5. The fact that across all tested regimes, Hamming decoding performs substantially worse than pseudo-ML, illustrates the importance of exploiting the heterogeneous coordinate reliabilities, and shows that treating all binary decisions with equal weight can be significantly suboptimal in general classification problems. In all the above, we have again focused on the representative case ρ = 2, corresponding to a practically relevant moderate-SNR regime. Additional experiments for smaller and larger SNR values can be found in Appendix C, with the corresponding plots essentially displaying the same qualitative behavior. As expected, the main effect of increasing ρ is that it shifts the error curves towards smaller values of N and it lowers the corresponding limiting error floor (for a certain value of d); while decreasing ρ has exactly the opposite effect.
5
Concluding remarks
We studied a distributed formulation of multiclass classification, motivated by settings in which a population of agents, each implementing a lightweight classifier trained on limited local data, cooperates to produce an accurate multiclass decision. To this end, we proposed a random hyperplanes classification scheme and derived explicit bounds for its performance in a variety of settings. In a noiseless Gaussian setting, we showed that, in sufficiently high dimensions, N = 2 log2 K random hyperplanes are required to separate the K class centers, which is within a factor of two of the information-theoretic minimum. Also, comparing with a natural ECOC alternative, we concluded that the dimensionality requirements of the proposed scheme are much lower, requiring a dimension that scales only logarithmically with K. In a more realistic setting where observations are corrupted by Gaussian noise, we again derived explicit performance bounds for the random hyperplanes classifier. It was shown that in sufficiently high dimensions, N = O(log K) hyperplanes are again sufficient, with a multiplicative constant that depends on the signal to noise ratio and the decoding mechanism. In specific, it was shown that Hamming decoding, which assigns equal weight to all binary decisions, can be significantly suboptimal compared to reliability-aware decoders. In this view, we proposed a computationally efficient approximate maximum likelihood algorithm, that is both theoretically justified and was found to perform nearly optimally in practice. Closing, we note a few possible directions for future work. First, it is natural to study an even more realistic version of the problem, where the class centers are not directly observed and need to be estimated from the data. Also, one can move beyond hyperplanes and consider more flexible base classifiers at the local agents. Finally, relaxing the Gaussian assumptions would help identify which aspects of the theory persist for more general data distributions. These extensions would greatly broaden the scope and practical applicability of the proposed framework.
36
References [1] R. Ahlswede and I. Csiszár. Hypothesis testing with communication constraints. IEEE transactions on information theory, 32(4):533–542, 2003. [2] E. L. Allwein, R. E. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of Machine Learning Research, 1:113–141, 2000. [3] M. Aly. Survey on multiclass classification methods. Neural Netw, 19(1-9):2, 2005. [4] P. T. Boufounos and R. G. Baraniuk. 1-bit compressive sensing. In 42nd Annual Conference on Information Sciences and Systems, pages 16–21, 2008. [5] T. T. Cai, J. Fan, and T. Jiang. Distributions of angles in random packing on spheres. Journal of Machine Learning Research, 14(136):1837–1864, 2013. [6] C.Y. Chou and H.H. Chen. Contrastive ECOC: Learning output codes for adversarial defense. In Proceedings of the 34th ACM International Conference on Information and Knowledge Management, pages 4685–4689, 2025. [7] P. Diaconis and D. Freedman. A dozen de Finetti-style results in search of a theory. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 23(S2):397–423, 1987. [8] T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286, 1994. [9] S. Escalera, O. Pujol, and P. Radeva. Subclass problem-dependent design for errorcorrecting output codes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(6):1041–1054, 2008. [10] S. Escalera, O. Pujol, and P. Radeva. Error-correcting output codes library. Journal of Machine Learning Research, 11:661–664, 2010. [11] A. Genz. Numerical computation of multivariate normal probabilities. Journal of Computational and Graphical Statistics, 1(2):141–149, 1992. [12] J. Geweke. Efficient simulation from the multivariate normal and student-t distributions subject to linear constraints and the evaluation of constraint probabilities. In Computing science and statistics: Proceedings of the 23rd symposium on the interface, volume 571, page 578, 1991. [13] S. Gupta and S. Amin. Scalable design of error-correcting output codes using discrete optimization with graph coloring. In Advances in Neural Information Processing Systems, volume 35, 2022. [14] V. Hajivassiliou, D. McFadden, and P. Ruud. Simulation of multivariate normal rectangle probabilities and their derivatives theoretical and computational results. Journal of Econometrics, 72(1-2):85–134, 1996. [15] T. Hastie and R. Tibshirani. Classification by pairwise coupling. In Advances in Neural Information Processing Systems, volume 10, 1997. 37
[16] L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Transactions on Information Theory, 59(4):2082–2102, 2013. [17] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1–2):1–210, 2021. [18] J. Matoušek. Lectures on Discrete Geometry, volume 212. Springer, 2002. [19] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communicationefficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282, 2017. [20] Y. Plan and R. Vershynin. One-bit compressed sensing by linear programming. Communications on Pure and Applied Mathematics, 66(8):1275–1297, 2013. [21] O. Pujol, S. Escalera, and P. Radeva. An incremental node embedding technique for error correcting output codes. Pattern Recognition, 41(2):713–725, 2008. [22] O. Pujol, P. Radeva, and J. Vitria. Discriminant ECOC: A heuristic method for application dependent design of error correcting output codes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(6):1007–1012, 2006. [23] J. Ridgway. Computation of Gaussian orthant probabilities in high dimension. Statistics and computing, 26(4):899–916, 2016. [24] R. R. Tenney and N. R. Sandell. Detection with distributed sensors. IEEE Transactions on Aerospace and Electronic Systems, AES-17(4):501–510, 1981. [25] J. N. Tsitsiklis. Decentralized detection by a large number of sensors. Mathematics of Control, Signals and Systems, 1(2):167–182, 1988. [26] P. K. Varshney. Distributed Detection and Data Fusion. Springer, 1997. [27] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices., 2012. [28] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. [29] J. G. Wendel. A problem in geometric probability. Mathematica Scandinavica, 11(1):109– 111, 1962. [30] A. Yu, S. Jing, N. Lyu, W. Wen, and Z. Yan. Error correction output codes for robust neural networks against weight-errors: A neural tangent kernel point of view. In Advances in Neural Information Processing Systems, 2024. [31] T. Zaslavsky. Facing Up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, volume 154. American Mathematical Society, 1975.
38
Appendix A
Theoretical results
A.1
Proof of Proposition 2
Because the Gaussian model is rotationally invariant, we may rotate coordinates so that e1 is aligned with the true center xa , i.e., e1 = xa /∥xa ∥. In these coordinates we may write, xa = τ Re1 , with R ∼ χd since xa ∼ N (0, τ 2 Id ), where χd denotes the chi distribution with d degrees of freedom. Now we can decompose the noise z into its component parallel to xa and its orthogonal component: z = σGe1 + σg⊥ , where G ∼ N (0, 1), and g⊥ ∼ N (0, Id−1 ) in the subspace orthogonal to e1 . If S := ∥g⊥ ∥, then, S ∼ χd−1 , and R, G, S are independent. With ρ = τ /σ, we have, y = xa + z = τ Re1 + σGe1 + σg⊥ = σ ((ρR + G)e1 + g⊥ ) . Therefore, cos α =
ρR + G x⊤ ay =p ∥xa ∥∥y∥ (ρR + G)2 + ∥g⊥ ∥2
Now, condition on α, or equivalently on the triple (R, G, S). Since xb is an independent isotropic Gaussian vector, its direction V := xb /∥xb ∥ is uniform on S d−1 and is independent of (R, G, S). After conditioning on α, we may place xa and y in the plane spanned by e1 , e2 , so that: y = cos α e1 + sin α e2 . ∥y∥ Therefore, for V ∼ Unif(S d−1 ), cos θ = V ⊤ e1 ,
cos β = V ⊤ (cos α e1 + sin α e2 ).
Therefore, we finally get, ii h h Bd,ρ (N ) = ER,G,S EV ∼Unif(S d−1 ) e−N Eiid (θ,α,β , where R ∼ χd , G ∼ N (0, 1), S ∼ χd−1 , V ∼ Unif(S d−1 ) are independent, and, ! ρR + G α = arccos p , θ = arccos(V ⊤ e1 ), β = arccos V ⊤ (cos α e1 + sin α e2 ) . (ρR + G)2 + S 2 The final expression follows by observing that only the first two components of V are needed. If we denote V1 := V ⊤ e1 , V2 := V ⊤ e2 , then, cos θ = V1 , cos β = V1 cos α + V2 sin α. For d = 2, V is uniform on the circle, and for d > 2, the joint density of the first two components (V1 , V2 ) is available in closed form, as, see, e.g. [7], fd (v1 , v2 ) =
d−2 (1 − v12 − v22 )(d−4)/2 , 2π 39
v12 + v22 ≤ 1.
A.2
Proof of Proposition 3
As described in the main text, the limiting probability of error is given by, ∞ Pe = Pr min βb ≤ α . b̸=a
It remains to evaluate this probability. For all competitors b ̸= a, define their corresponding directions Vb = xb /∥xb ∥, which are independent and uniform on the sphere S d−1 . Let V1 := V ⊤ e1 denote the first component of V , let Φ := ∠(V, e1 ) = arccos(V1 ) denote the angle between V and e1 , and let Fd (ϕ) denote its cumulative distribution function, Fd (ϕ) := Pr arccos V1 ≤ ϕ , V ∼ Unif(S d−1 ). Then, by rotational invariance we get, Pr(βb ≤ α | α) = Fd (α), and since the Vb ’s are conditionally independent given α, we get the order-statistics expression, h K−1 i Pr min βb ≤ α = Eα 1 − 1 − Fd (α) . (34) b̸=a
Now, it remains to obtain an expression for Fd . The first coordinate of a uniformly distributed point on S d−1 has density, fV1 (v) = √
Γ(d/2) (1 − v 2 )(d−3)/2 , π Γ((d − 1)/2)
−1 < v < 1,
1 see, for example, [7]. By defining, W := 1−V 2 , the change of variables formula gives the distribution of W , d−1 d−1 W ∼ Beta , . 2 2
Now,
1 − cos t . 2 Since the CDF of the Beta distribution is the regularized incomplete beta function, we get, d−1 d−1 , Fd (ϕ) = I 1−cos ϕ , 2 2 2 ∠(V, e1 ) ≤ t
⇐⇒
V1 ≥ cos t
⇐⇒
W ≤
and since, 1 − Ix (a, a) = I1−x (a, a), we finally get, d−1 d−1 1 − Fd (ϕ) = I 1+cos ϕ , . 2 2 2 Substituting with ϕ = α in (34) completes the proof, since the unconditional distribution of α is given as before in Proposition 2.
40
A.3
Chernoff bound for pseudo-ML decoder
For one hyperplane u, define, B(u) := sign(u⊤ y),
Cm (u) := sign(u⊤ xm ),
pm (u) := Q
|u⊤ xm | σ
.
The coordinate-wise pseudo-log-likelihood score for candidate m is, e lm (u) = 1{B(u) = Cm (u)} log(1 − pm (u)) + 1{B(u) ̸= Cm (u)} log pm (u). For a competitor b ̸= a, define the one-hyperplane score difference, ∆ab (u) := e lb (u) − e la (u). Conditional on xa , xb , z, the random variables ∆ab (u1 ), . . . , ∆ab (uN ) are i.i.d. since the hyperplanes ui are i.i.d. For any s ≥ 0, Chernoff’s bound gives the pairwise error bound, iN h . Pr Peb (B) ≥ Pea (B) xa , xb , z ≤ Eu es∆ab (u) xa , xb , z By defining the geometry-dependent pseudo-ML error exponent, i h EpML (xa , xb , z) := − inf log Eu es∆ab (u) xa , xb , z . s≥0
(35)
a union bound over the competitors yields, X −N E (xa ,x ,z) pML b Pr E xK e , 1 ,z ≤ b̸=a
and by symmetry, averaging over the random centers xN 1 and noise z, finally gives, h i Pr(E) ≤ (K − 1) Exa ,xb ,z e−N EpML (xa ,xb ,z) . Hence in this case the error exponent EpML (xa , xb , z) does not reduce to a closed-form function of the angles (θb , α, βb ), since ∆ab (u) also depends on the realized distances |u⊤ xa |, |u⊤ xb |. So, in order to numerically evaluate the bound, we need a nested MC procedure, which requires to first obtain outer MC samples of the geometry xa , xb , z, and then for each such realization sample enough hyperplanes to estimate EpML (xa , xb , z) from (35). This is not particularly helpful, since its computation cost becomes comparable with simulating the whole experiment.
A.4
Order-statistics error formulas for random hyperplanes
In order to tighten Chernoff analysis, it is possible to derive analogous order-statistics formulas for the random hyperplanes setting, avoiding the union bound over competitors. The analysis is similar with Section 3.6 for orthogonal hyperplanes, but unfortunately, the final expressions no longer simplify enough to be employed in an efficient Monte Carlo estimate. Indeed, computing the resulting estimates would require a computational cost comparable to simulating the whole experiment, meaning that the corresponding expressions are not particularly useful. Hamming decoder.
Denoting the conditional pairwise error probability, pHam := Pr dH (B, Cb ) ≤ dH (B, Ca ) xa , z, uN 1 ,
the exact Hamming error probability is given by, h K−1 i PeHam = Exa ,z,uN 1 − 1 − pHam , 1
but this final expectation does not simplify enough to give an efficient Monte Carlo estimate. 41
Approximate pseudo-ML decoder. Denoting the conditional pairwise error probability, ppML := Pr Peb (B) ≥ Pea (B) xa , z, uN , 1 the exact pseudo-ML error probability is, h K−1 i PepML = Exa ,z,uN 1 − 1 − ppML , 1
but again this does not lead to an efficient Monte Carlo estimate.
B
Monte Carlo sampler for Section 3.6.2
In the orthogonal hyperplane setting, the ML order-statistic expression in (22) can be estimated by Monte Carlo over the scalar score distributions of La and Lb . First, generate T independent (1) (T ) (t) true-score samples, La , . . . , La . For each sample La , draw, iid
Zi ∼ N (0, 1),
pi = Q(ρ|Zi |),
i = 1, . . . , N.
Conditional on pi , set, ( log pi , with probability pi , Si = log(1 − pi ), with probability 1 − pi , and compute, L(t) a =
N X
Si .
i=1 (1)
(M )
Independently, generate M wrong-class score samples Lb , . . . , Lb iid
Zi′ ∼ N (0, 1), Conditional on qi , set,
qi = Q(ρ|Zi′ |),
(m)
. For each sample Lb
, draw,
i = 1, . . . , N.
( log qi , with probability 1/2, Ti = log(1 − qi ), with probability 1/2,
and compute, (m) Lb =
N X
Ti .
i=1 (1)
(M )
After generating the M wrong-class score samples Lb , . . . , Lb , sort them. For each true-score (t) (t) sample La , estimate pt = Pr(Lb ≥ La ), by the empirical tail fraction, M
pbt =
1 X (ℓ) 1{Lb ≥ L(t) a }. M ℓ=1
The order-statistic Monte Carlo error estimate can then be computed as, 1 PbeML,orth = T
T X 1 − (1 − pbt )K−1 . t=1
42
C
Simulation results
C.1
Orthogonal hyperplanes with noise
Figure 6: Probability of error as a function of the number of orthogonal hyperplanes. Top Left: ρ = 0.5, Top Right: ρ = 5, Bottom: ρ = 10.
C.2
Random hyperplanes with noise
Figure 7: Probability of error as a function of the number of random hyperplanes. Left: ρ = 1, Right: ρ = 5.
43