Networked Information Aggregation for Binary Classification MohammadHossein Bateni 1 Zahra Hadizadeh 2 MohammadTaghi Hajiaghayi 3 Mahdi JafariRaviz 3 Shayan Taherijam 2 Abstract with partial and heterogeneous information aggregate their observations to form an accurate global belief? This line of We study networked binary classification on a inquiry has a rich literature in economics and network sci- directed acyclic graph (DAG) where each agent arXiv:2605.01082v1 [cs.LG] 1 May 2026 ence, commencing with the seminal work of DeGroot (De- observes only a subset of the feature columns of a groot, 1974). The DeGroot model conceptualizes learning shared dataset. Agents act sequentially along the as an iterative process of weighted averaging, where agents DAG: each receives prediction columns from its update their scalar beliefs based on the beliefs of their neigh- parents (if any), augments its local features with bors. This heuristic approach was subsequently refined by these columns, fits a logistic predictor by mini- Bayesian models of observational learning and information mizing binary cross-entropy (BCE), and forwards cascades, where rational agents infer private signals from its prediction column to its outgoing neighbors. the actions of their predecessors to reach a consensus or We ask whether this sequential distributed train- truth. For example, Banerjee (Banerjee, 1992) studies herd- ing procedure achieves information aggregation, ing behavior in sequential decision-making; Bikhchandani meaning that some agent attains small excess loss et al. (Bikhchandani et al., 1992) formalize informational compared to the best logistic predictor trained cascades as a mechanism for fads and fashions; Gale and with access to all feature columns. Kariv (Gale & Kariv, 2003) analyze Bayesian learning dy- This question was studied for linear regres- namics over social networks; and Golub and Jackson (Golub sion under squared loss by Kearns, Roth, and & Jackson, 2010) study conditions under which naive aver- Ryu (Kearns et al., 2026). Extending their guar- aging aggregates information. antees to classification is nontrivial because their analysis relies on quadratic structure that does not While classical social learning focuses on the aggregation directly transfer to BCE with a logistic link. We of scalar estimates for a single state variable, modern ap- analyze the resulting sequential logit-passing pro- plications increasingly demand networked machine learn- tocol and√ prove: (i) an excess loss upper bound ing, where agents collaboratively learn high-dimensional of O(M/ D) on depth-D paths under the condi- hypothesis functions. In this setting, aggregation entails tion that every M contiguous subsequence of M reconstructing a complex predictive relationship—such as agents collectively observe all features, and (ii) a a classifier mapping a high-dimensional feature vector to close lower bound showing instances with excess a label—dispersed across a network. Recently, Kearns et loss of at least Ω(k/D) where k is the dimension al. (Kearns et al., 2026) introduced a formal framework of the feature space. Together, these results iden- for this problem, embedding learning agents in a Directed tify network depth as a fundamental bottleneck Acyclic Graph (DAG). In their protocol, agents observe a for information aggregation in networked logistic local subset of features and the predictions of their parents, regression. training a model to minimize a local loss function. For linear regression under squared error, they demonstrated that such a process allows agents to achieve excess loss competitive with a global learner having access to all features, with the 1. Introduction network depth acting as the critical resource for aggregation. The study of social learning in networks addresses a fun- damental question in distributed learning: How do agents 1.1. Our Contributions 1 Google Research, New York City, NY, USA 2 University of In this work, we focus on the classification variant of the California, Irvine, CA, USA 3 University of Maryland, College model of (Kearns et al., 2026). We analyze a sequential Park, MD, USA. Correspondence to: Shayan Taherijam . models using local features and incoming logits from their Preprint. May 5, 2026. parents in a DAG. Our main contributions are as follows. 1 Networked Information Aggregation for Binary Classification Upper Bounds. We analyze information aggregation in a gression require genuinely different tools once the target network of logistic regression agents. We show that if a is probabilistic classification. We list three representative path of length D satisfies a coverage condition—namely, pairs. First, in sketching/subspace-embedding methods, every contiguous block of M agents collectively observes least-squares regression admits sharp oblivious sketching all features. In particular, we prove √ that the excess loss of guarantees (Clarkson & Woodruff, 2013), whereas logistic the final agent scales as O(M/ D) (Theorem 3.8). objectives require non-L2 progress measures and different proof techniques (Munteanu et al., 2021). Second, in second- At a high level, our proof extends the analysis of (Kearns order / curvature-aware acceleration via sketching, iterative et al., 2026) from squared loss to logistic loss. The squared- Hessian sketch methods are cleanly analyzed for constrained loss argument relies on an exact variance decomposition, least squares (Pilanci & Wainwright, 2016), while Newton- which does not carry over to Binary Cross-Entropy (BCE). sketch extensions for regularized ERM objectives (including Instead, we certify progress via a KL/Bregman-type char- logistic regression) require controlling curvature that de- acterization of loss differences (Lemma 3.3) together with pends on current predictions (Pilanci & Wainwright, 2017). a Pinsker-style link from KL progress to prediction error Third, in distribution-free predictive inference, split confor- (Lemma 3.4). A key technical input is an orthogonality mal prediction yields regression intervals (Lei et al., 2018), condition for BCE residuals (Lemma 3.1). Finally, a stabil- whereas classification requires set-valued prediction regions ity (pigeonhole) argument identifies a segment of the path and different uncertainty objects (Angelopoulos & Bates, where improvement saturates; this forces small residuals and 2021). Taken together, these examples support the mes- yields a bound on the deviation from the global optimum. sage most relevant to our paper: moving from regression to Lower Bounds and Hard Instances We complement the classification typically replaces Euclidean residual decom- upper bound by exhibiting a hard instance for the sequential positions with KL/Bregman-flavored notions of progress, logit-passing protocol. On this instance, early features are which becomes unavoidable when the information flowing uninformative about the label in isolation and only become through the network is itself a low-bandwidth probabilistic useful after sufficiently many passes through the feature prediction. cycle. We prove that the excess loss is lower-bounded by Ω(k/D) where k is the dimension of the feature space, 1.3. Related Work showing that network depth is not merely sufficient but necessary in the framework. The most directly related body of work comes from Vertical Federated Learning (VFL), where different parties hold dis- joint feature columns for the same aligned examples and col- 1.2. From Regression to Classification laborate to train a joint predictor. The standard VFL setting Extending theoretical guarantees of networked aggregation is inherently interactive: the survey of (Yang et al., 2019) from linear regression to binary classification is non-trivial. formalizes the feature-partitioned regime and highlights that The analysis in (Kearns et al., 2026) relies fundamentally on most practical protocols rely on repeated message exchanges the geometry of squared loss—in particular, orthogonality (e.g., gradients, activations, or protected sufficient statistics) of residuals and a Pythagorean variance decomposition— to optimize a shared objective. This view is reflected in which translate loss reduction directly into parameter-space deployed platforms such as FATE (Liu et al., 2021), which convergence. In contrast, binary classification via logistic re- operationalize multi-round VFL pipelines and make explicit gression and Binary Cross-Entropy (BCE) does not admit a the practical tension between accuracy, privacy protection, comparable bias–variance decomposition. The non-linearity and communication cost. A particularly relevant algorith- of the sigmoid link introduces genuine geometric complica- mic family is vertical gradient-boosted tree training: Se- tions; in particular, linear aggregation in probability space cureBoost (Cheng et al., 2021) and later high-performance is not equivalent to linear aggregation in feature space, mo- variants such as SecureBoost+ (Fan et al., 2024) show that tivating the architectural choice of passing logits rather than strong predictors can be trained over vertically split fea- probabilities. tures, but only by repeatedly coordinating split decisions through exchanging split-related information. From the Despite these challenges, classification remains the primary perspective of our setting, these works provide concrete modality for distributed applications ranging from medical evidence that feature partitioning alone already induces diagnosis (Vepakomma et al., 2018) to decentralized fraud a strong communication bottleneck; our work asks what detection. Establishing guarantees for information aggrega- can be guaranteed when the interaction budget is pushed tion under BCE is therefore a central theoretical goal. much closer to its limit. A complementary architectural line More broadly, this regression-to-classification gap is not is split learning (Vepakomma et al., 2018), which avoids unique to our networked setting: across several areas, tech- sharing raw features by cutting a neural network across par- niques and guarantees that are clean for squared-loss re- ties and communicating intermediate activations/gradients. 2 Networked Information Aggregation for Binary Classification While the mechanism is different from VFL-by-gradients or 2.3. Sequential Learning Protocol VFL-by-trees, it again emphasizes the same friction point The agents learn models in a sequential manner. Unlike lin- that is central to our paper: learning can succeed under ear regression settings where agents minimize squared error, information-flow constraints, but the protocol must care- here each agent Ai aims to train a model fi to minimize the fully manage what is transmitted and how many rounds are local Binary Cross Entropy (BCE) loss. available. Finally, recent surveys (Wu et al., 2025; Khan et al., 2025) synthesize these lines and stress that communi- Each agent Ai observes its local features xSi and the set cation (both message size and number of rounds) remains of outputs from its parents. To preserve the information a dominant practical limitation in VFL, alongside privacy geometry of the exponential family, agents communicate leakage and the statistical dependence patterns induced by their logits (the input to the sigmoid function) rather than feature/label partitioning; this framing closely matches the their final probabilities. Let zj be the logit output by parent communication-centric viewpoint taken in our analysis. Aj , such that the parent’s prediction is p̂j = σ(zj ). The model pi for agent Ai is a logistic function of its local 2. Preliminaries features and the parents’ logits: In this section, we formally define the notation, the logistic X regression framework, and the distributed learning setup. pi (x) = σ(zi (x)) where zi (x) = wiT xSi + vij zj (x). j∈Pa(Ai ) (3) 2.1. Binary Classification and Logistic Regression Here, wi (weights for local features) and vij (weights We consider a binary classification problem. Let D be a for incoming logits) are learnable parameters. Agent Ai distribution over feature-label pairs (x, y), where x ∈ Rd is chooses these parameters to minimize the expected BCE a vector of features and y ∈ {0, 1} is the binary target label. loss E[L(pi )]. We model the conditional probability P (y = 1|x) using the The final output of the system is the prediction of the sink logistic function σ(z) = 1+e1−z . A hypothesis is parameter- agent (or the last agent in the topological sort). ized by a vector θ ∈ Rd , yielding the predictor: We use the notation L(p), L(θ), and L(z) interchangeably. p(θ) T (x) = σ(θ x). (1) Here, θ denotes the weight vector. We define z(x) = θT x and p(x) = σ(z(x)). The quality of a predictor is measured by the expected Bi- nary Cross Entropy (BCE) loss: 3. Upper Bounds (θ) (θ) L(θ) = −E(x,y)∼D [y log p (x)+(1−y) log(1−p(x))]. This section analyzes information aggregation within a net- (2) work of logistic regression agents. We demonstrate that se- The global Maximum Likelihood Estimator (MLE), denoted quentially minimizing Binary Cross Entropy (BCE) allows by p∗ , corresponds to the parameters θ∗ that minimize this the network to approximate the global predictor derived loss over the full feature space. from all features, assuming sufficient network depth and feature coverage. 2.2. Distributed Learning Setup We first establish that the residuals of the BCE loss optimizer We consider a distributed learning setting with a set of N are orthogonal to the input. A similar result was previously agents, A = {A1 , . . . , AN }. The agents are organized derived by (Kearns et al., 2026) for the linear regression in a Directed Acyclic Graph (DAG), G = (A, E), where with MSE loss. an edge (Aj , Ai ) ∈ E indicates that agent Ai receives information from agent Aj . We sometimes also write Aj → Lemma 3.1 (Orthogonality of Residuals). Let p∗ be the Ai to denote this relationship. We denote the set of parents optimal logistic predictor on a feature space X . The residual of agent Ai as Pa(Ai ) = {Aj | (Aj , Ai ) ∈ E}. The agents error (p∗ (x) − y) is orthogonal to the feature vector x in learn in an order consistent with a topological sort of the expectation: DAG, with ties in the topological ordering broken arbitrarily. E [x(p∗ (x) − y)] = 0. Let [d] = {1, 2, . . . , d} be the set of indices for d total features. Each agent Ai ∈ A is associated with a specific Proof. Given p(θ) (x) = σ(θT x), the gradient of the logistic subset of these features, Si ⊆ [d]. For any agent Ai , its output is ∇θ p(θ) (x) = p(θ) (x)(1 −p(θ) (x))x. Applying the local view of the features is xSi , which is the sub-vector of chain rule to L(θ) yields: x corresponding to the features indexed by Si . The agent h i also receives its parents’ logits. ∇θ L(θ) = −E (y(1 − p(θ) (x)) − (1 − y)p(θ) (x))x 3 Networked Information Aggregation for Binary Classification h i h i = E (p(θ) (x) − y)x . + E (p∗ (x) − y) (θ − θ∗ )T x . (4) The optimal parameters θ∗ satisfy the condition ∇θ L(θ∗ ) = The second term is zero due to the orthogonality condition 0. Thus: derived in Lemma 3.1. For the first term, we expand the E [x(p∗ (x) − y)] = 0. definition of D(p∗ ∥q) with z = θT x and z ∗ = (θ∗ )T x: h  ∗  This orthogonality allows us to decompose the error of any D(p∗ ∥q) = E p∗ (x) (z ∗ − z) − log 1 + ez suboptimal model. We express the error of a suboptimal i model in terms of the optimal predictor using the expected + log (1 + ez ) Kullback-Leibler divergence of the Bernoulli distribution, h  T   ∗ T  defined as follows. = E log 1 + eθ x − log 1 + e(θ ) x i Definition 3.2. Let p and q be two predictors on feature − p∗ (x) (θ − θ∗ )T x . space X . Then D(p∥q) is defined as: D(p∥q) = E [DKL (Bernoulli(p(x))∥Bernoulli(q(x)))] , This matches the first term in Equation (4), completing the proof. where DKL (p′ ∥q ′ ) is the Kullback-Leibler divergence be- tween distributions p′ and q ′ , given by: To bound the parameter error using the KL divergence, we use the following inequality. This is a specific case X p′ (x) of Pinsker’s inequality (Pinsker, 1964), included here for DKL (p′ ∥q ′ ) = p′ (x) log . x q ′ (x) completeness. Lemma 3.4. For the expected KL divergence D(p∥q), the Expanding this definition, D(p∥q) becomes: following inequality holds: D(p∥q) ≥ 2E (p(x) − q(x))2 .   1 − p(x)   p(x) D(p∥q) = E p(x) log + (1 − p(x)) log . q(x) 1 − q(x) We refer to Appendix A for the proof. We define the point- Lemma 3.3 (Decomposing Loss). Let p∗ be the optimal wise loss function as: logistic predictor on a feature set S, and let q be any logistic predictor on S. The loss decomposes as: l(z, y) = log(1 + ez ) − yz. (5) L(q) = L(p∗ ) + D(p∗ ∥q). We can thus write L(p) = E[l(z(x), y)]. Lemma 3.5. Let g(x) = σ(zg (x)) be any logistic predictor. Proof. Using the identity log σ(z) = z − log(1 + ez ), we Let S be a feature subspace and p(x) = σ(zp (x)) be the write the loss with z = θT x as: predictor that minimizes L(p) over S. Then: L(θ) = −E [yz − log(1 + ez )] L(p) ≤ L(g) + |E[(p − y)zg ]|. h T i = E log(1 + eθ x ) − y(θT x) . Proof. Let ϕ(z) = log(1+ez ). The derivatives are ϕ′ (z) = σ(z) and ϕ′′ (z) = σ(z)(1 − σ(z)). Since σ(z) ∈ (0, 1), Let θ∗ be the corresponding parameters of p∗ . Expanding we have ϕ′′ (z) ≥ 0, implying ϕ is convex. Convexity the difference L(θ) − L(θ∗ ): implies that for any u, v ∈ R, ϕ(v) ≥ ϕ(u) + ϕ′ (u)(v − u). h T Rearranging implies the following: L(θ) − L(θ∗ ) = E log(1 + eθ x ) ∗ T ϕ(u) ≤ ϕ(v) + σ(u)(u − v). (6) − log(1 + e(θ ) x ) i We define the relationship between the losses l(u, y) and − y((θ − θ∗ )T x) . l(v, y). Substituting l(z, y) = ϕ(z) − yz, we aim to show the following inequality: Adding and subtracting p∗ (x)(θ − θ∗ )T x inside the expec- tation yields: l(u, y) ≤ l(v, y) + (σ(u) − y)(u − v). (7) h T ∗ T  Expanding terms confirms this holds given the convexity of L(θ) − L(θ∗ ) =E log(1 + eθ x ) − log 1 + e(θ ) x ϕ in Equation (6): i − p∗ (x) (θ − θ∗ )T x ϕ(u) − yu ≤ ϕ(v) − yv + σ(u)(u − v) − yu + yv 4 Networked Information Aggregation for Binary Classification ⇐⇒ ϕ(u) ≤ ϕ(v) + σ(u)(u − v). = |E[xl (pk − pj )]|. Applying the Cauchy-Schwarz inequality: Now, for a point x, let u = zp (x) and v = zg (x). Applying q q Equation (7): |E[xl (pk − pj )]| ≤ E[x2l ] E[(pk − pj )2 ] l(zp , y) ≤ l(zg , y) + (σ(zp ) − y)(zp − zg ). = ∥xl ∥2 ∥pk − pj ∥2 . Taking the expectation over x: Given ∥xl ∥2 ≤ BX , we bound ∥pk − pj ∥2 using the loss difference ε. Applying Lemma 3.4, we get for any s ∈ L(p) ≤ L(g) + E[(p − y)(zp − zg )] {1, . . . , k − 1}: = L(g) + E[(p − y)zp ] − E[(p − y)zg ].  1 E (ps − ps+1 )2 ≤ D(ps+1 ∥ps ).  From Lemma 3.1 (Orthogonality), we know that for any 2 feature xl in the support of p, E[xl (p − y)] = 0. Since zp By the triangle inequality and Cauchy-Schwarz: is a linear combination of such features, E[(p − y)zp ] = 0. k−1 r Substituting this yields: X D(ps+1 ∥ps ) ∥pj − pk ∥2 ≤ 2 L(p) ≤ L(g) − E[(p − y)zg ] ≤ L(g) + |E[(p − y)zg ]|. s=j s Pk−1 k s=1 D(ps+1 ∥ps ) We consider a path of agents A1 , . . . , AD . Each agent i ≤ 2 receives the logit zi−1 from its predecessor and trains a r logistic predictor model using locally observed features xSi , kε ≤ . zi−1 , and possibly some other predecessors’ logits. Since 2 one option for the agent Ai is to pass the logits zi−1 through, Combining these bounds with the constraint on αl : we have that L(pi−1 ) ≥ L(pi ). We also get that Lemma 3.3 holds for pi−1 and pi , since pi−1 is in the stricter subspace d r X kε of pi . |E[(pk − y)zg ]| ≤ |αl | · |E[xl (pk − y)]| ≤ Bg BX . 2 p l=1 We use the notation ∥f (x)∥2 = E [f (x)2 ] for any func- tion f . Lemma 3.6 (Residual Bound via Path Coverage). Let We now give the below definition. A1 , . . . , Ak be a path of agents where every feature xl Definition 3.7 (M -Coverage Condition, Kearns et al. is observed at least once. Let g(x) = σ(zg (x)) where (2026)). A path satisfies the M -coverage condition if every Pd zg (x) = l=1 αl xl be any logistic predictor over the whole contiguous subsequence of M agents collectively observes Pd space. Assume the coefficients of zg satisfy l=1 |αl | ≤ Bg , all d features x1 , . . . , xd . and the features satisfy E[x2l ] ≤ BX 2 , for some Bg and BX . We are finally ready to prove Theorem 3.8. Combining Let ε ≥ L(p1 ) − L(pk ). Then: Lemma 3.5 and Lemmap3.6, we obtain the relationship r kε L(pk ) ≤ L(g) + Bg BX kε/2 for a path of length k. Ex- |E[(pk − y)zg ]| ≤ Bg BX . tending this analysis over the full path satisfying the M - 2 coverage condition leads to our main convergence result. Proof. Let zg (x) = Pd Theorem 3.8 (Global Convergence Rate). Consider a DAG l=1 αl xl . We bound the error term: G containing a path of length D of agents A1 , . . . , AD satisfying the M -coverage condition. Let p∗ be the global " d # X |E[(pk − y)zg ]| = E αl xl (pk − y) optimal logistic predictor over all d features. Assume: l=1 d X 1. Bounded second moments: E[x2l ] ≤ BX 2 for all l ∈ ≤ |αl | |E[xl (pk − y)]|. {1, . . . , d}. l=1 2. Bounded coefficients: for the optimal logits z ∗ (x) = Consider a feature xl . Due to each feature being observed, P l αl xl where ∥α∥1 ≤ Bp . ∗ this feature appears in the index set of some agent Aj in the path. By orthogonality, E[xl (pj − y)] = 0. We decompose Then the excess risk of the final agent pD is bounded by: the expectation using the triangle inequality:   M M |E[xl (pk − y)]| ≤ |E[xl (pk − pj )]| + |E[xl (pj − y)]| L(pD ) − L(p∗ ) ≤ Bp∗ BX √ = O √ . D D 5 Networked Information Aggregation for Binary Classification Proof. We partition the path into K = ⌊D/M ⌋ disjoint Network and Assignment. Consider a path of agents blocks of length M . By the Pigeonhole Principle, since A1 , . . . , AD . The agents observe features one-at-a-time in a the total loss reduction is bounded by the loss of the first repeating cyclic order. Agent Ai observes the single feature agent L(p1 ), there exists at least one stable block k ∗ where xℓ where ℓ = ((i−1) (mod k))+1. The network structure the reduction is at most the total reduction divided by K. is a simple path where Pa(Ai ) = {Ai−1 }. Suppose this block k ∗ is on indices s, s + 1, . . . , t. We define a pass p as p-th disjoint block of k t X L(p1 ) 2M L(p1 ) agents. Specifically, the p-th pass consists of the agents (L(pi−1 ) − L(pi )) ≤ ≤ := ε. A(p−1)k+1 , . . . , Apk . i=s+1 K D Applying Lemma 3.5 and Lemma 4.2. Information Capacity and Variance p3.6, we get that over this path L(pt ) ≤ L(p∗ ) + Bp∗ BX M ε/2. Next, note that We analyze the capacity of the final agent in pass p to re- L(p1 ) ≤ log 2 since using θ1 = 0 achieves a loss of log 2, construct the target Zk by identifying which features can be and because the first agent optimizes within its domain then effectively decoded from the scalar stream. L(p1 ) ≤ log 2 < 1. Combined with the non-increasing losses, we get: The following lemma characterizes the restricted informa- tion available to agents. This result follows the methods of M Lemma 5.5 in (Kearns et al., 2026), which establishes an L(pD ) − L(p∗ ) ≤ Bp∗ BX √ . D analogous result. We provide the proof for completeness. Lemma 4.1 (Recursive Information Relevance). For any 4. Lower Bound Analysis pass p with p ≤ k, define the feature subset Ip = In this section, we construct a theoretical lower bound for {xk , xk−1 , . . . , xk−p+1 }. The optimal logistic predictor for the convergence rate of the distributed learning protocol. We σ(Zk ) at the end of pass p depends solely on the features in demonstrate the existence of a specific data distribution and Ip . network configuration where the excess loss decays at a rate of Ω(k/D), where D is the depth of the network and k is the dimension of the feature space. This result confirms that Proof. We proceed by induction on the pass index p. the sequential nature of the protocol makes network depth a Base Case (p = 1): The first pass ends at agent Ak , who fundamental bottleneck for information aggregation. observes the local feature xk = Zk − Zk−1 . Preceding agents A1 , . . . , Ak−1 observe features x1 , . . . , xk−1 , all of 4.1. Problem Construction which are independent of the target Zk and thus the label We define a hard instance that exploits the information bot- y. Because each agent Ai (for i < k) minimizes its local tleneck inherent in sequential logit aggregation. BCE loss using only information independent of the label, each sequentially transmits a logit of 0 to its successor. Data Distribution. Let k ≥ 2 be the dimension of the Consequently, Ak receives a logit of 0 from Ak−1 and must feature space. Consider a sequence of independent latent rely exclusively on its local observation xk to predict y. This variables Z1 , Z2 , . . . , Zk ∼ N (0, 1). We define the observ- establishes the effective information set I1 = {xk }. able features x1 , . . . , xk ∈ R as follows: Inductive Step: Assume at the end of pass p, the optimal predictor z (p) is a function only of the features in Ip = x1 = Z1 (8) {xk , xk−1 , . . . , xk−p+1 }. In pass p + 1, the initial sequence xi = Zi − Zi−1 , for 2 ≤ i ≤ k (9) of agents observe features x1 , . . . , xk−p−1 . Because these features are independent of the current information set Ip , Pi Zi can be recovered By construction, the latent variable they are also independent of the incoming logit z (p) and by the prefix sum of features: j=1 xj = Zi . We define the label y. Consequently, these agents cannot improve the binary target label y ∈ {0, 1} based on the final latent the prediction; they sequentially forward the logit z (p) to variable Zk via the logistic model: one another without modification. This process continues  k  until an agent observes xk−p = Zk−p − Zk−p−1 . This new feature is correlated with the latent variable Zk−p currently X P (y = 1|x) = σ(Zk ) = σ  xj  (10) j=1 acting as noise in z (p) , allowing the agent to partially cancel that noise and improve the estimate of Zk . Subsequent Thus, the optimal global logit predictor is z ∗ (x) = Zk , agents in the pass observe only features in Ip . Thus, the which requires access to all k features to cancel the interme- relevant information set expands by exactly one feature: diate noise terms. Ip+1 = Ip ∪ {xk−p }. 6 Networked Information Aggregation for Binary Classification Given this restriction, any logit z (p) generated at the end of Proof. We first analyze the loss conditioned on Zk . Assum- pass p is a linear function of the features in Ip . We analyze ing y|Zk ∼ Bernoulli(σ(Zk )), we expand the conditional this linear predictor in the following lemma. loss as: Lemma 4.2. Let z (p) be a linear predictor based on Ip . L(z|Zk ) = Ey|Zk [−yz + log(1 + ez )] Then z (p) is given by = −σ(Zk )z + log(1 + ez ). (11)   (p) 1 z = c Zk + √ ξ , Define g(z) = L(z|Zk ). Differentiating with respect to z p yields g ′ (z) = −σ(Zk ) + σ(z). The second derivative is g ′′ (z) = σ(z)(1 − σ(z)). Since σ(z) ∈ (0, 1), g ′′ (z) > 0, where c ∈ R is a constant and ξ ∼ N (0, Vp ) is independent implying g is strictly convex. of Zk . For a fixed c, minimizing the variance Vp yields Vp = 1. The total loss for zv is L(zv ) = EZk [Eξv [g(cZk + ξv )]]. To compare zu and zv , let δ ∼ N (0, u − v) be independent Pp−1 of ξv . We can model the higher variance noise as ξu = ξv +δ. Proof. Define z (p) = j=0 cj xk−j with coefficients Applying Jensen’s inequality to the strictly convex function c0 , . . . , cp−1 . We rewrite this expression in terms of the g: variables Zk , . . . , Zk−p : Eδ [g(cZk + ξv + δ)] > g(Eδ [cZk + ξv + δ]) p−1 = g(cZk + ξv ). X (p) z = c0 Zk + (cj − cj−1 )Zk−j − cp−1 Zk−p . j=1 Taking the expectation over Zk and ξv on both sides yields Let c = c0 and αj = cj − cj−1 . Substituting these terms L(zu ) > L(zv ). yields: We next demonstrate that for the optimal predictor in the   p−1 X p−1 X form of Lemma 4.2, the scaling factor c is strictly within the z (p) = cZk + αj Zk−j −  αj + c Zk−p . interval (0, 1). j=1 j=1 Lemma 4.4. Let zc = c(Zk + ξ), where ξ ∼ N (0, v) with v > 0, and ξ is independent of Zk . The optimal scaling Define the residual η = z (p) − cZk . Since Pp−1Zi are factor c minimizing L(zc ) satisfies c ∈ (0, 1). i.i.d. N (0, 1), the variance of η is Var(η) = j=1 αj2 + 2 √ Proof. Define S = Zk + ξ. Note that S ∼ N (0, 1 + v). We P p−1 p j=1 αj + c . Define ξ = c η. It follows that p expand the loss L(zc ): ξ ∼ N (0, Vp ), where Vp = c2 Var(η). This establishes L(zc ) = E −σ(Zk ) · cS + log(1 + ecS ) .   the form of the predictor. Next, we fix c and minimize Vp , which is equivalent to Let g(c) = L(zc ). Differentiating with respect to c: Pp−1 minimizing Var(η). Let S = αj . The variance Pp−1j=12 2 g ′ (c) = E[−Sσ(Zk ) + Sσ(cS)] can be written as Var(η) = j=1 αj + (S + c) . For P 2 a fixed sum S, the term αj is minimized when all αj are = E[−Zk σ(Zk )] + E[Sσ(cS)]. 2 S equal, yielding Var(η) = p−1 + (S + c)2 . Differentiating The second derivative is g ′′ (c) = E[S 2 σ ′ (cS)]. Since the with respect to S and setting the result to zero, we find the sigmoid derivative is strictly positive, g ′′ (c) > 0, implying minimum occurs at S = −c(p − 1)/p. Substituting this that g is strictly convex. value back, the minimum variance is c2 /p. Consequently, Vp = Var(η) cp2 = 1. Evaluating the gradient at c = 0:   1 g ′ (0) = −E[(Zk + ξ)σ(Zk )] + E S · Next, we analyze the properties of the noise term ξ in the lin- 2 ear predictor defined in Lemma 4.2 and examine its impact = −E[Zk σ(Zk )]. on the BCE loss. Lemma 4.3. Let zv = cZk + ξv , where ξv ∼ N (0, v) is We observe that E[Zk σ(Zk )] = Cov(Zk , σ(Zk )) > 0. independent of Zk . For a fixed c, if u > v, then: Therefore, g ′ (0) < 0, which implies the minimizer of g must lie to the right of 0. L(zv ) < L(zu ), Next, consider the gradient at c = 1: where L(z) denotes the BCE loss. g ′ (1) = −E[Zk σ(Zk )] + E[Sσ(S)]. 7 Networked Information Aggregation for Binary Classification Define the function h(u) = EX [Xσ(X)] √ where X ∼ address this, we restrict our analysis to a bounded region N (0, u2 ). We observe that g ′ (1) = h( 1 + v) − h(1). where the sigmoid function has non-vanishing derivative. If h(u) is increasing for u > 0, then g ′ (1) > 0, meaning Define the event BR where both Zk and ξ are bounded by the minimizer must be less than 1. R: BR := {|Zk | < R, |ξ| < R}. Using the reparameterization X = uX ′ where X ′ ∼ N (0, 1), we write h(u) = u · EX ′ [X ′ σ(uX ′ )]. The deriva- By selecting a sufficiently large R, BR captures a constant tive is: fraction of the probability mass. On this set, the arguments to the sigmoid function are bounded. By the Mean Value h′ (u) = EX ′ [X ′ σ(uX ′ )] + EX ′ [u(X ′ )2 σ ′ (uX ′ )]. Theorem, there exists η between Zk and zD such that For u > 0, the first term is positive as it equals p∗ − pD = σ(Zk ) − σ(zD ) = σ ′ (η)(Zk − zD ) 1 ′ ′ u Cov(uX , σ(uX )). The second term is non-negative Since |η| < 2R on BR , σ ′ (η) ≥ Cuniv > 0 for some con- since the term inside the expectation is non-negative. Thus, stant Cuniv dependent only on R. h′ (u) > 0 for u > 0. This concludes that the optimal c lies 2 in the interval (0, 1). Restricting the expectation to BR and defining C1 = 2Cuniv , we have: 2E (p∗ − pD )2 1BR ≥ C1 E (Zk − zD )2 1BR .     4.3. Connection to Excess Loss Finally, we connect the variance of the logit estimator to the Substituting the estimator form from Equation (12), we BCE loss to establish a lower bound on the excess loss. expand the quadratic term: Theorem 4.5 (Lower Bound on Convergence). Let k denote " 2 # the dimension of the feature space. Consider the feature c E (1 − c)Zk − √ ξ 1BR distribution and network construction defined in Section 4.1. p For the agent at the end of the pass p (where p ≤ k − 1), 2c(1 − c) let p∗ denote the optimal global logistic predictor and pD = (1 − c)2 E[Zk2 1BR ] − √ E[Zk ξ1BR ] p (where D = kp) the predictor of the final agent. The excess loss is lower bounded by: c2 + E[ξ 2 1BR ].     p ∗ 1 k L(pD ) − L(p ) = Ω =Ω . p D Since Zk and ξ are independent and centered, and the re- gion BR is symmetric about the origin for both variables, Proof. We begin by relating the excess loss to the ex- E[Zk ξ1BR ] = 0. pected squared difference in the probability space. Invoking Since Zk and ξ follow the same distribution on BR , we Lemma 3.3 and Lemma 3.4, the loss difference satisfies: define C2 = E[Zk2 1BR ] = E[ξ 2 1BR ]. This yields: L(pD ) − L(p∗ ) = E[D(p∗ ||pD )] ≥ 2E (p∗ − pD )2 .   c2   L(pD ) − L(p∗ ) ≥ C1 C2 (1 − c)2 + . p The agent AD operates at the end of pass p. Let zD be the 2 logit of this agent such that pD = σ(zD ). By Lemma 4.1, The quadratic function (1 − c)2 + cp is minimized at c = AD relies only on the information in Ip . Consequently, by p p+1 . Substituting this value: Lemma 4.2, zD takes the form:   C1 C2 1  1  L(pD ) − L(p∗ ) ≥ =Ω . zD = c Zk + √ ξ , (12) p+1 p p Recalling that p = D/k, we conclude: for some constant c, where ξ ∼ N (0, Vp ). Since zD mini-   mizes the BCE loss (Lemma 4.3), Vp must be minimized. ∗ k L(pD ) − L(p ) = Ω . Lemma 4.2 states this minimum occurs at Vp = 1. Further- D more, Lemma 4.4 implies c ∈ (0, 1). Impact Statement To establish a lower bound, we relate the squared error in probabilities (p∗ − pD )2 to the squared error in logits (Zk − This paper presents work whose goal is to advance the field zD )2 using Mean Value Theorem. However, the sigmoid of Machine Learning. There are many potential societal derivative vanishes for large inputs, which could dampen consequences of our work, none of which we feel must be the probability difference even if the logit error is large. To specifically highlighted here. 8 Networked Information Aggregation for Binary Classification References Proceedings of the 2026 Annual ACM-SIAM Sympo- sium on Discrete Algorithms (SODA), pp. 4799–4845. Angelopoulos, A. N. and Bates, S. A gentle introduc- SIAM, 2026. doi: 10.1137/1.9781611978971.173. tion to conformal prediction and distribution-free uncer- URL https://epubs.siam.org/doi/abs/10. tainty quantification. CoRR, abs/2107.07511, 2021. URL 1137/1.9781611978971.173. https://arxiv.org/abs/2107.07511. Khan, A., ten Thij, M., and Wilbik, A. Vertical federated Banerjee, A. V. A simple model of herd behavior. The learning: A structured literature review. Knowledge and Quarterly Journal of Economics, 107(3):797–817, 1992. Information Systems, pp. 1–39, 2025. Bikhchandani, S., Hirshleifer, D., and Welch, I. A theory Lei, J., G’Sell, M., Rinaldo, A., Tibshirani, R. J., and of fads, fashion, custom, and cultural change as informa- Wasserman, L. Distribution-free predictive inference for tional cascades. Journal of Political Economy, 100(5): regression. Journal of the American Statistical Associa- 992–1027, 1992. tion, 113(523):1094–1111, 2018. Cheng, K., Fan, T., Jin, Y., Liu, Y., Chen, T., Papadopoulos, Liu, Y., Fan, T., Chen, T., Xu, Q., and Yang, Q. FATE: D., and Yang, Q. Secureboost: A lossless federated an industrial grade platform for collaborative learning learning framework. IEEE Intelligent Systems, 36(6): with data protection. J. Mach. Learn. Res., 22:226:1– 87–98, 2021. ISSN 1541-1672. doi: 10.1109/MIS.2021. 226:6, 2021. URL https://jmlr.org/papers/ 3082561. Publisher Copyright: © 2001-2011 IEEE. v22/20-815.html. Clarkson, K. L. and Woodruff, D. P. Low rank ap- Munteanu, C., Omlor, L., and Woodruff, D. P. Oblivi- proximation and regression in input sparsity time. In ous sketching for logistic regression. In Proceedings of Proceedings of the Forty-Fifth Annual ACM Sympo- the 38th International Conference on Machine Learning sium on Theory of Computing, STOC ’13, pp. 81–90, (ICML), volume 139 of Proceedings of Machine Learning New York, NY, USA, 2013. Association for Comput- Research, pp. 7816–7825. PMLR, 2021. ing Machinery. ISBN 9781450320290. doi: 10.1145/ 2488608.2488620. URL https://doi.org/10. Pilanci, M. and Wainwright, M. J. Iterative hessian sketch: 1145/2488608.2488620. Fast and accurate solution approximation for constrained least-squares. Journal of Machine Learning Research, 17 Degroot, M. H. Reaching a consensus. Jour- (1):1842–1879, 2016. nal of the American Statistical Association, 69 (345):118–121, 1974. doi: 10.1080/01621459.1974. Pilanci, M. and Wainwright, M. J. Newton sketch: A near 10480137. URL https://doi.org/10.1080/ linear-time optimization algorithm with linear-quadratic 01621459.1974.10480137. convergence. SIAM Journal on Optimization, 27(1):205– Fan, T., Chen, W., Ma, G., Kang, Y., Fan, L., and Yang, Q. 245, 2017. Secureboost+: Large scale and high-performance vertical Pinsker, M. S. Information and Information Stability of federated gradient boosting decision tree, 2024. URL Random Variables and Processes. Holden-Day, San Fran- https://arxiv.org/abs/2110.10927. cisco, 1964. Translated and edited by Amiel Feinstein. Gale, D. and Kariv, S. Bayesian learning in so- Vepakomma, P., Gupta, O., Swedish, T., and Raskar, R. Split cial networks. Games and Economic Behavior, learning for health: Distributed deep learning without 45(2):329–346, 2003. ISSN 0899-8256. doi: sharing raw patient data. CoRR, abs/1812.00564, 2018. https://doi.org/10.1016/S0899-8256(03)00144-1. URL http://arxiv.org/abs/1812.00564. URL https://www.sciencedirect.com/ science/article/pii/S0899825603001441. Wu, Z., Qin, Z., Hou, J., Zhao, H., Li, Q., He, B., and Fan, Special Issue in Honor of Robert W. Rosenthal. L. Vertical federated learning in practice: The good, the bad, and the ugly, 2025. URL https://arxiv.org/ Golub, B. and Jackson, M. O. Naı̈ve learning in social abs/2502.08160. networks and the wisdom of crowds. American Economic Journal: Microeconomics, 2(1):112–49, Yang, Q., Liu, Y., Chen, T., and Tong, Y. Federated February 2010. doi: 10.1257/mic.2.1.112. URL machine learning: Concept and applications. CoRR, https://www.aeaweb.org/articles?id=10. abs/1902.04885, 2019. URL http://arxiv.org/ 1257/mic.2.1.112. abs/1902.04885. Kearns, M., Roth, A., and Ryu, E. Networked in- formation aggregation via machine learning. In 9 Networked Information Aggregation for Binary Classification A. Omitted Proofs Lemma 3.4. For the expected KL divergence D(p∥q), the following inequality holds: D(p∥q) ≥ 2E (p(x) − q(x))2 .   Proof. We verify the inequality pointwise for any x ∈ X . We aim to show: p(x) 1 − p(x) p(x) log + (1 − p(x)) log ≥ 2(p(x) − q(x))2 . (13) q(x) 1 − q(x) Define the function f (p) = p log pq + (1 − p) log 1−p 2 ′ 1−q − 2(p − q) . The first derivative with respect to p is: f (p) = p 1−p ′′ 1 1 1 log q − log 1−q − 4(p − q). The second derivative is f (p) = p + 1−p − 4 = p(1−p) − 4. For p ∈ [0, 1], the term p(1 − p) has a maximum value of 0.25. Consequently, p(1−p) 1 ≥ 4, which implies f ′′ (p) ≥ 0. Since f is convex and satisfies ′ f (q) = 0, the point p = q is a global minimum. Observing that f (q) = 0, we conclude that f (p) ≥ 0 for all p. Taking the expectation of both sides in (13) yields the result:   p(x) 1 − p(x) D(p∥q) = E p(x) log + (1 − p(x)) log ≥ 2E[(p(x) − q(x))2 ]. q(x) 1 − q(x) 10