Metraipolis › archive › dc_e65ca071dc5b

Optimal Lower Bounds for Networked Information Aggregation — arXiv:2608.15472

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.15472
License (as archived)
CC0-1.0
Archived
2026-10-18T18:03:31.455Z
SHA-256 of the archived text
d036f388b639ee9704865a0576992418d9fc14a079a5b07fb4c371e2f58d0b62
Stable URL of this page
https://metraipolis.com/documento/dc_e65ca071dc5b

How to cite

Optimal Lower Bounds for Networked Information Aggregation — arXiv:2608.15472 — arXiv (en), https://arxiv.org/abs/2608.15472 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e65ca071dc5b (Metraipolis archive dc_e65ca071dc5b, sha256 d036f388b639ee9704865a0576992418d9fc14a079a5b07fb4c371e2f58d0b62)
BibTeX
@misc{dce65ca071dc5b,
  title = {Optimal Lower Bounds for Networked Information Aggregation — arXiv:2608.15472},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.15472},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e65ca071dc5b; sha256 d036f388b639ee9704865a0576992418d9fc14a079a5b07fb4c371e2f58d0b62},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.15472. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The problem of networked information aggregation, studied in Kearns et al. (2026), involves a group of learners situated on the vertices of a directed acyclic graph $G$, each learning a linear predictor $\widehat Y$ for a fixed random variable $Y$ given access to a local feature, as well as the predictors learnt by its parents. Learning proceeds iteratively, with learners ordered according to a topological sort of $G$. The main quantity of interest is the error incurred by the current learner, constrained to this flow of information, with respect to the best linear predictor using all the features seen so far. When the studied error is the MSE, i.e., $\mathbb{E} (\widehat Y - Y)^2$, Kearns et al. (2026) show that the error is at most $O(1/\sqrt{D})$ along a path of length $D$. They also obtain a hard instance where the MSE is lower bounded by $\Omega(1/D)$, leaving the correct order open. In this work, we resolve this central open problem, and obtain a family of worst case problem instances with a MSE lower bound of $\Omega(1/\sqrt{D})$. By exploiting invariances in the structure of the learnt predictors, our analysis generalizes to all convex loss functions $\ell(\widehat Y, Y)$ satisfying regularity conditions which include strong convexity in a ball around the origin, and that the ideal predictor minimizing the population loss is positively correlated with the label. We show that networked information aggregation on a gaussian instance in our worst case family incurs an $\ell$-error lower bounded by $\Omega(1/\sqrt{D})$ with respect to this ideal predictor. We demonstrate that a variety of common losses satisfy these regularity conditions. In particular, the logistic loss satisfies them, and hence our analysis also closes the gap between the upper and lower bounds in Bateni et al. (2026).

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-18 in cs.AI).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2608.15472 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T16:29:14.021Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).