Spaces:

ProCreations
/

repro-networked-information-aggregation-for-binary-classification

Running

App Files Files Community

repro-networked-information-aggregation-for-binary-classification / paper.txt

ProCreations

Publish validated ICML reproduction

c692cd7 verified 13 days ago

Raw

History Blame Contribute Delete

69.4 kB

	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 <sta- learning protocol where agents optimize logistic regression
	herij@uci.edu>.
	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