File size: 69,372 Bytes
c692cd7 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 | 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
|