Paper deep dive
Optimal Lower Bounds for Networked Information Aggregation
Ambar Pal
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/22/2026, 2:22:11 AM
Summary
This paper resolves an open problem regarding the optimal lower bounds for networked information aggregation in directed acyclic graphs. It proves that the Mean Squared Error (MSE) lower bound is \(\Omega(1/\sqrt{D})\), matching the known upper bound, thereby closing the gap left by Kearns et al. (2026). The analysis generalizes to other convex loss functions, including logistic loss, showing similar lower bounds and closing gaps for Bateni et al. (2026).
Entities (7)
Relation Signals (4)
This work → resolvesopenproblemfor → Networked Information Aggregation
confidence 95% · 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}).
This work → closesgapfor → Bateni et al. (2026)
confidence 90% · our analysis also closes the gap between the upper and lower bounds in Bateni et al. (2026).
Kearns et al. (2026) → establishedupperboundfor → Networked Information Aggregation
confidence 90% · Kearns et al. (2026) show that the error is at most O(1/\sqrt{D}) along a path of length D.
Logistic Loss → satisfiesregularityconditionsof → General Convex Loss Analysis
confidence 85% · In particular, the logistic loss satisfies them, and hence our analysis also closes the gap...
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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).
Tags
Links
- Source: https://arxiv.org/abs/2608.15472v1
- Canonical: https://arxiv.org/abs/2608.15472v1
Trouble viewing inline? Open PDF directly →
Full Text
68,691 characters extracted from source content.
Expand or collapse full text
Optimal Lower Bounds for Networked Information Aggregation Ambar Pal Note: This work is not related to AP’s position at Amazon. Email: ambarpal@amazon.com Affiliation: Amazon Responsible AI August 16, 2026 Abstract 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 Y 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., (Y^−Y)2 ( Y-Y)^2, Kearns et al. 2026 show that the error is at most O(1/D)O(1/ D) along a path of length D. They also obtain a hard instance where the MSE is lower bounded by Ω(1/D) (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 Ω(1/D) (1/ D). By exploiting invariances in the structure of the learnt predictors, our analysis generalizes to all loss functions ℓ(Y^,Y) ( 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 ℓ -error lower bounded by Ω(1/D) (1/ 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. Contents 1 Problem Setup 2 Main Results 2.1 Least Squares Regression 2.2 Logistic Regression 2.3 General Convex Loss 3 Overall proof technique 4 Least Squares Regression 4.1 Vertex Transformations 4.2 Coefficient invariants 4.3 Cumulative-sum lower bound 4.4 Controlling the cumulative sum 5 Regression with a Convex Loss 5.1 MSE 5.2 Logistic Loss 5.3 Huber and other Losses A Omitted Proofs for Section A.1 Proof of Lemma A.2 Proof of Lemma A.3 Proof of Lemma A.4 Proof of Lemma A.5 Proof of Theorem A.6 Proof of Lemma B Omitted Proofs for Section B.1 Proof of Lemma B.2 Proof of Lemma References 1 Problem Setup We have a group of learners V each of which try to learn a predictor Y^i Y_i for a random variable Y, that obtains a low population loss ℓ(Y^i,Y) ( Y_i,Y). These learners are arranged in the form of a directed acyclic graph G=(,ℰ)G=(V,E), where an edge (i,j)∈ℰ(i,j) exists whenever learner j has access to the predictor learnt by learner i. Each learner has knowledge of a local set of features, i.e., random variables iX_i that may be predictive of Y. Additionally, each learner i has access to the predictors Y^j Y_j learnt by its parents in G. Learning proceeds iteratively following along vertices ordered by a topological sort of G. At each iteration, the current learner j obtains a linear predictor Y^j Y_j by solving the optimization problem minY^ℓ(Y^,Y) _ Y \ ( Y,Y) over Y Y constrained to be linear in the features accessible to learner j, i.e., j∪Y^i:(i,j)∈ℰX_j∪\ Y_i (i,j) \. For the purposes of our analysis, it will be sufficient to assume that both these sets are singletons, i.e., j=XjX_j=\X_j\ for all learners j, and each j has at most one parent par(j)par(j) in G. For ℓ(Y^,Y)=(Y^−Y)2 ( Y,Y)=( Y-Y)^2, the above becomes the so-called networked information aggregation setup studied by Kearns et al. 2026. In this work, we will analyze a generalization of the worst case instance for this problem studied by Kearns et al. 2026, and show that the error decays along the path at a rate inversely proportional to the square root of the length of the path. Further, we will see that the same lower bound applies to logistic regression, studied in Bateni et al. 2026. 2 Main Results Worst Case Instance Family. Let Z1,…,ZkZ_1,…,Z_k be random variables such that Zi=0,Zi2=1 Z_i=0, Z_i^2=1 for i∈1,2,…,ki∈\1,2,…,k\, and ZiZj=0 Z_iZ_j=0 whenever i≠ji≠ j for i,j∈1,2,…,ki,j∈\1,2,…,k\. Let the learners be =1,2,…,k⋅(k−1)V=\1,2,…,k·(k-1)\, and the edges ℰE be given by 1⟶2⋯⟶k⟶k+1⟶k+2⟶⋯⟶2k⟶⋯⟶k⋅(k−1).1 2·s k k+1 k+2 ·s 2k ·s k·(k-1). We define the pass p to be the group of learners (p−1)⋅k+1,(p−1)⋅k+2,…,(p−1)⋅k+k.\(p-1)· k+1,(p-1)· k+2,…,(p-1)· k+k\. For each vertex i, we let the local feature set be a singleton, given by the random variable XiX_i. For the first vertex on pass p, we let X(p−1)⋅k+1=Z1X_(p-1)· k+1=Z_1, and for each 2≤i≤k2≤ i≤ k, we let X(p−1)⋅k+i=Zi−Zi−1X_(p-1)· k+i=Z_i-Z_i-1. Note that the set of all features viewed in each pass is the same. Finally, we define the label Y=ZkY=Z_k. Recall that each learner solves an optimization program to minimize the population loss L with respect to the features it has access to. We define Errℓ(i)=ℓ(Y^i,Y)Err (i)= ( Y_i,Y), and our results provide bounds on the error at the end of each pass p, defined as Errpℓ=ℓ(Y^p⋅k,Y)Err _p= ( Y_p· k,Y) for p∈1,2,…,k−1p∈\1,2,…,k-1\. Our results can be divided according to the loss used. 2.1 Least Squares Regression Setting the loss to be the mean squared error, i.e., ℓMSE(Y^,Y)=(Y^−Y)2 _ MSE( Y,Y)=( Y-Y)^2 recovers the setup studied in Kearns et al. 2026. Each learner i solves the optimization problem minα,β∈ℝ[(αXi+βY^i−1−Y)2] _α,β [ (α X_i+β Y_i-1-Y )^2 ] (1) to obtain the predictor Y^i=αiXi+βiY^i−1 Y_i= _iX_i+ _i Y_i-1, with the convention Y^0=0 Y_0=0. Note that the ideal linear predictor at the end of each pass, given access to all the features seen so far, obtains zero error, as Y^⋆=X1+X2+…+Xk=Y Y =X_1+X_2+…+X_k=Y obtains ℓMSE(Y^⋆,Y)=0 _ MSE( Y ,Y)=0. Our main result is Theorem 2.1 (Simplified MSE lower bound). For every instance in the worst case family, and every 1≤p≤k−11≤ p≤ k-1, ErrpMSE≥136p.Err MSE_p≥ 136 p. For a fixed k, along with the matching upper bound of O(1p)O( 1 p) in Kearns et al. 2026, this settles the correct order of dependence on depth for learning with the MSE loss in the networked information aggregation model. Theorem 2.1 contains simplified constants for clarity, the full result is in Theorem 4.6. 2.2 Logistic Regression Setting ℓ to be the logistic loss, ℓlogistic(Y^,Y)=−σ(Y)logσ(Y^)−(1−σ(Y))⋅log(1−σ(Y^)) _ logistic( Y,Y)=-σ(Y) σ( Y)-(1-σ(Y))· (1-σ( Y)), where σ(y)=11+exp(−y)σ(y)= 11+ (-y) recovers the setup studied in Bateni et al. 2026. Note that we require a slight transformation of the random variables in Bateni et al. 2026 to keep our exposition consistent: our Y is a real-valued random variable, which is transformed into their binary label probability using σ(Y)σ(Y), and similarly our real-valued Y Y is viewed as the logit learnt by each learner in their setup to produce the probability σ(Y^)σ( Y) of predicting the label 11 in their setup. Similar to (1), each learner i now solves the optimization problem minα,β∈ℝ[ℓlogistic(αXi+βY^i−1,Y)]. _α,β [ _ logistic (α X_i+β Y_i-1,Y ) ]. Note that the ideal linear predictor at the end of each pass is still Y^⋆=∑iXi=Y Y = _iX_i=Y, but it no longer achieves zero error, as ℓlogistic(Y,Y)=ℓlogistic(Zk,Zk) _ logistic(Y,Y)= _ logistic(Z_k,Z_k) is non-negative in general. We hence show Theorem 2.2 (Simplified Logistic error lower bound). For the instance in the worst case family where Z1,Z2,…,Zk∼i.i.d.(0,1)Z_1,Z_2,…,Z_k i.i.d. N(0,1), for every 1≤p≤k−11≤ p≤ k-1, Errplogistic≥1104p+Errlogistic,⋆,Err logistic_p≥ 110^4 p+Err logistic, , where Errlogistic,⋆=ℓlogistic(Zk,Zk)Err logistic, = _ logistic(Z_k,Z_k). For a fixed k, along with the matching upper bound of O(1p)O( 1 p) in Bateni et al. 2026, this settles the correct order of dependence on depth for learning with the logistic loss in the networked information aggregation model. Theorem 2.2 contains simplified constants, and is in fact proved in Section 5.2 as an application of our more general result Theorem 2.3. 2.3 General Convex Loss Finally, we generalize our lower bound arguments to a differentiable loss ℓ . Subject to a few regularity conditions including strong convexity in a ball around the origin and differentiability, we show that, Theorem 2.3 (Simplified general error lower bound). For the gaussian instance in the worst case family where Z1,Z2,…,Zk∼i.i.d.(0,1)Z_1,Z_2,…,Z_k i.i.d. N(0,1), for any convex loss ℓ satisfying (Regular-I) and (Regular-I), for every 1≤p≤k−11≤ p≤ k-1, we have, Errpℓ≥μ72p+Errℓ,⋆,Err _p≥ μ72 p+Err , , where Errℓ,⋆=ℓ(Zk,Zk)Err , = (Z_k,Z_k), and μ is the strong convexity parameter in (Regular-I). 3 Overall proof technique We now describe the high level proof technique, and then derive each result in the subsequent sections. Note that the learnt predictor is a linear combination of the latent variables, Z1,Z2,…,ZkZ_1,Z_2,…,Z_k, which we will denote by ∑iaiZi _ia_iZ_i in the following, for coefficients =(a1,…,ak)∈ℝk a=(a_1,…,a_k) ^k. Further, we will denote the coefficients at the last vertex of pass p as (p) a^(p). The first four steps apply to learning with ℓMSE _ MSE, and the rest extend the arguments to other losses. 1. In each pass p, we divide the vertices into three types: Type I is the starting vertex k⋅(p−1)+1k·(p-1)+1, Type I consists of the intermediate vertices, k⋅(p−1)+ik·(p-1)+i for 2≤i≤k−12≤ i≤ k-1, and Type I is the final vertex k⋅pk· p. We then compute a closed form expression for the coefficients at each vertex as a transformation of the coefficients of its predecessor, in Lemma 4.1. Specifically, each vertex type corresponds to one such transformation T: T1T_1 sets a1a_1 to zero and rescales, TiT_i, for 2≤i≤k−12≤ i≤ k-1 averages two adjacent coefficients in a and rescales, and TkT_k averages the last two coefficients in a, rescales, and adds (0,…,0,−12,12)(0,…,0,- 12, 12). 2. Lemma 4.2 then derives the coefficient invariants at the end of every pass. In particular, ∑jaj=0,ak=1−ErrpMSE,ak−ak−1=1,ak−1=−ErrpMSE. _ja_j=0, a_k=1-Err MSE_p, a_k-a_k-1=1, a_k-1=-Err MSE_p. It also identifies that only the last p+1p+1 coefficients are non-zero (in (p) a^(p)) at the end of pass p, and that all of these are negative except the last coefficient ak(p)a^(p)_k. 3. The zero-sum invariant, along with the fact that ErrpMSE=∑i=k−pk−1ai2+(1−ak)2Err MSE_p= _i=k-p^k-1a_i^2+(1-a_k)^2 at the last vertex of pass p, is enough to recover the lower bound in Kearns et al. 2026. To see this, apply Cauchy–Schwarz to ak−p+⋯+ak−1+(ak−1)=−1,a_k-p+·s+a_k-1+(a_k-1)=-1, to obtain ErrpMSE≥1p+1Err MSE_p≥ 1p+1. Lemma 4.3 generalizes the above idea, applying Cauchy–Schwarz to the last N+1N+1 coefficients instead, ak−N+⋯+ak−1+(ak−1)=ck−N−1, where ci=∑j=ikaj,a_k-N+·s+a_k-1+(a_k-1)=c_k-N-1, where c_i= _j=i^ka_j, and obtains ErrpMSE≥(1−ck−N)2N+1.Err MSE_p≥ (1-c_k-N)^2N+1. Now, it is enough to show that ck−Nc_k-N is low enough (say 1−ck−N≥1/31-c_k-N≥ 1/3), for some N≲pN p. 4. To control ck−Nc_k-N, Lemma 4.4 obtains the recurrence relationship relating (p) a^(p) to all the previous (i),i<p a^(i),i<p. This recurrence involves complicated non-linear terms in the coefficients through the normalization factors. However, a technical manipulation allows us to bypass analysis of the normalization terms by bounding the ratio of the partial sum of these coefficients to (1−ErrpMSE)(1-Err MSE_p). Lemma 4.4 contains this argument, allowing us to obtain ck−N≲exp(−N2p),c_k-N (- N^2p ), completing our argument. The above argument can be neatly extended to more general losses satisfying some regularity conditions, including strong convexity, by utilizing a conditioning argument for regression under misspecified losses developed in Li and Duan 1989. This extension is presented in Section 5. 4 Least Squares Regression In this section, we analyze learning on any problem instance in our worst case family, with the MSE loss ℓMSE=(Y^−Y)2 _ MSE=( Y-Y)^2, and provide details for steps (1-4) outlined in Section 3. 4.1 Vertex Transformations Every prediction is a linear combination of the latent variables Z1,…,ZkZ_1,…,Z_k. In the following, suppose that the prediction output by the parent of a vertex is Y^=∑j=1kajZj,=(a1,…,ak). Y= _j=1^ka_jZ_j, a=(a_1,…,a_k). Then, Lemma 4.1 provides the prediction output of each vertex in terms of a. Lemma 4.1 (Vertex Transformations). Define the linear operators A1,A2,…,AkA_1,A_2,…,A_k, where A1=(0,a2,…,ak)A_1 a=(0,a_2,…,a_k) set the first coefficient to zero, and Ai=(a1,…,12(ai−1+ai),12(ai−1+ai),ai+1,…,ak)A_i a= (a_1,…, 12(a_i-1+a_i), 12(a_i-1+a_i),a_i+1,…,a_k ) for 2≤i≤k2≤ i≤ k replace ai−1a_i-1 and aia_i by their average and leave the other coordinates unchanged. With the convention that 00=0 00=0, the transformation at the i-th vertex in pass p is as follows. (i) At the Type-I learner k(p−1)+1k(p-1)+1, assigned Xk(p−1)+1=Z1X_k(p-1)+1=Z_1, T1()=s1()A1,s1()=ak∑j=2kaj2.T_1( a)=s_1( a)A_1 a, s_1( a)= a_k _j=2^ka_j^2. (i) At a Type-I learner k(p−1)+ik(p-1)+i, assigned Xk(p−1)+i=Zi−Zi−1X_k(p-1)+i=Z_i-Z_i-1 for 2≤i≤k−12≤ i≤ k-1, Ti()=si()Ai,si()=ak∥Ai∥22.T_i( a)=s_i( a)A_i a, s_i( a)= a_k A_i a _2^2. (i) At the Type-I learner kpkp, assigned Xkp=Zk−Zk−1X_kp=Z_k-Z_k-1, Tk()=sk()Ak+,sk()=ak−1+ak2∑j=1k−2aj2+(ak−1+ak)2=(0,…,0,−12,12).T_k( a)=s_k( a)A_k a+ b, s_k( a)= a_k-1+a_k2 _j=1^k-2a_j^2+(a_k-1+a_k)^2 b=(0,…,0,- 12, 12). Note 1. Observe that each vertex map TiT_i is invariant to positive scaling, i.e., for every t>0t>0, Ti(t)=Ti()T_i(t a)=T_i( a). Consequently, when we compose the maps in one pass, we ignore all intermediate positive normalizations until the final Type-I update. 4.2 Coefficient invariants Recall from Section 3 that (p)=(a1(p),…,ak(p)) a^(p)=(a_1^(p),…,a_k^(p)) is defined to be the coefficient vector at the end of pass p. Lemma 4.2 then obtains a few important properties of coefficient vectors that the learners output. Lemma 4.2 (Coefficient invariants). For the coefficient vector a returned by any vertex, the last coordinate is related to the MSE error as ak=1−ErrMSE,a_k=1-Err MSE, (2) the coefficients sum to zero, ∑j=1kaj=0, _j=1^ka_j=0, (3) and the squared norm is given by ∑j=1kaj2=ak. _j=1^ka_j^2=a_k. (4) For the coefficient vector i a^i returned by vertex k≤i≤k(k−1)k≤ i≤ k(k-1), we have that 12≤aki<1 12≤ a^i_k<1. Further, for 1≤p≤k−11≤ p≤ k-1, for the coefficient vector (p)=pk a^(p)= a^pk returned by the last vertex of pass p, the last two coordinates are related as ak(p)−ak−1(p)=1,a_k^(p)-a_k-1^(p)=1, (5) hence ak−1(p)=−ErrpMSE.a_k-1^(p)=-Err MSE_p. (6) Finally, the signs of the coefficient vector after each pass are given by aj(p)=0(j<k−p),aj(p)<0(k−p≤j<k),ak(p)≥12.a_j^(p)=0 (j<k-p), a_j^(p)<0 (k-p≤ j<k), a_k^(p)≥ 12. (7) 4.3 Cumulative-sum lower bound Fix a pass 1≤p≤k−11≤ p≤ k-1 and define ci(p)=∑j=ikaj(p),1≤i≤k.c_i^(p)= _j=i^ka_j^(p), 1≤ i≤ k. Lemma 4.3 (Cumulative-sum bound). For every integer 0≤N≤k−10≤ N≤ k-1, ErrpMSE≥(1−ck−N(p))2N+1.Err MSE_p≥ (1-c_k-N^(p))^2N+1. (8) Taking N=pN=p, equations (3) and (7) give ck−p(p)=0c_k-p^(p)=0, and therefore ErrpMSE≥1p+1,Err MSE_p≥ 1p+1, (9) showing the error lower bound of Kearns et al. 2026 is valid for any instance in our worst case family. Our improvement over (9) comes from showing that ck−N(p)c_k-N^(p) is small even for N≲pN p. 4.4 Controlling the cumulative sum In this section, we upper bound ck−N(p)c^(p)_k-N. In principle, one could directly try to iterate the recurrence a(p)=Tk∘Tk−1∘…∘T1(a(p−1))a^(p)=T_k T_k-1 … T_1(a^(p-1)) to obtain a(p)a^(p), and calculate the cumulative sum from the resultant vector. This direct approach does not seem to work, as keeping track of the normalization factors accumulating at each pass is difficult. In the following, we instead tightly utilize the invariances we have developed in Lemma 4.2 to circumvent tracking the normalization factors, and solve a more manageable recurrence. For ease of exposition, we change coordinates to count from the right edge of the vector (p) a^(p). We ignore the only positive entry ak(p)a_k^(p), since it is determined by the remaining entries through the zero-sum invariant. Define wi(p)=−ak−i(p),1≤i≤k−1.w_i^(p)=-a_k-i^(p), 1≤ i≤ k-1. (10) From the coefficient invariances (2), (3), (6), and (7), we get wi(p)≥0w_i^(p)≥ 0 for all 1≤i≤k−11≤ i≤ k-1, w1(p)=ErrpMSE,∑i=1k−1wi(p)=ck(p)=1−ErrpMSE,∑i=N+1k−1wi(p)=ck−N(p).w_1^(p)=Err MSE_p, _i=1^k-1w_i^(p)=c_k^(p)=1-Err MSE_p, _i=N+1^k-1w_i^(p)=c^(p)_k-N. (11) Proof Strategy. We pause here to comment on the proof strategy, as it involves an important manipulation. We will show that ck−N(p)/ck(p)≤γp(N)c^(p)_k-N/c^(p)_k≤ _p(N) for some small γp(N) _p(N), which will then imply via (11) that ck−N(p)≤γp(N)(1−ErrpMSE)<γp(N)c^(p)_k-N≤ _p(N)(1-Err_p MSE)< _p(N). This manipulation incurs a slack of ErrpMSEErr_p MSE due to the second inequality, but, as we will see, allows us to go around reasoning about the scaling altogether, due to the ratio ck−N(p)/ck(p)c^(p)_k-N/c^(p)_k. Lemma 4.4 (One-pass recurrence). There are positive normalization factors ηp _p, and a linear transformation :ℝk−1→ℝk−1T:R^k-1 ^k-1 such that for 1≤p≤k−21≤ p≤ k-2, (p+1)=ηp(p)+Errp+1MSE1,(1)=121, w^(p+1)= _pT w^(p)+Err MSE_p+1 e_1, w^(1)= 12 e_1, (12) where (w)i=0,i=1,∑t=0k−i2−(t+1)wi−1+t,2≤i≤k−1..(Tw)_i= cases0,&i=1,\\ _t=0^k-i2^-(t+1)w_i-1+t,&2≤ i≤ k-1. cases. (13) Consequently (letting an empty product equal 11), (p+1)=∑s=1p+1ErrsMSE(∏r=spηr)p+1−s1. w^(p+1)= _s=1^p+1Err MSE_s ( _r=s^p _r )T^p+1-s e_1. (14) Lemma 4.4 thus shows that the vector (p+1) w^(p+1) is a weighted sum of the p+1p+1 vectors n1T^n e_1 for 0≤n≤p0≤ n≤ p. This is useful for our purposes, as the cumulative sums of (p+1) w^(p+1) is then equal to a weighted sum of the cumulative sums of n1T^n e_1. The following lemma lets us use this structure, by calculating the cumulative sums of n1T^n e_1. Lemma 4.5 (Cumulative sums). For 0≤p≤k−20≤ p≤ k-2 and 0≤N≤k−10≤ N≤ k-1, define the cumulative sum (p,N)=∑i=N+1k−1(p1)i. c(p,N)= _i=N+1^k-1 (T^p e_1 )_i. (15) Then, we have (p,N)=(2p−Np)2−(2p−N),0≤N≤p,0,p<N≤k−1. c(p,N)= cases 2p-Np2^-(2p-N),&0≤ N≤ p,\\[8.00003pt] 0,&p<N≤ k-1. cases (16) Consequently, for 1≤N≤p≤k−21≤ N≤ p≤ k-2, (p,N)(p,0)=∏j=0N−12(p−j)2p−j≤exp(−N(N−1)4p). c(p,N) c(p,0)= _j=0^N-1 2(p-j)2p-j≤ (- N(N-1)4p ). (17) The proof of Lemma 4.5 is done cleanly using the theory of generating functions, and is deferred to Appendix A.6. We now have the machinery needed to prove our main Theorem 2.1. Proof of Theorem 2.1. Note that for p≤3p≤ 3, we have 1p+1≥136p 1p+1≥ 136 p, so (9) is sufficient to show the result. For p≥4p≥ 4, we have ck−N(p) c_k-N^(p) =(11)∑i=N+1k−1wi(p) eq:edge-facts= _i=N+1^k-1w_i^(p) =(14)∑i=N+1k−1∑s=1pErrsMSE(∏r=sp−1ηr)(p−s1)i eq:positive-mixture= _i=N+1^k-1 _s=1^pErr MSE_s ( _r=s^p-1 _r ) (T^p-s e_1 )_i =(15)∑s=1pErrsMSE(∏r=sp−1ηr)⏟>0(p−s,N) eq:partial-sum-definition= _s=1^p Err MSE_s ( _r=s^p-1 _r )_>0 c(p-s,N) ≤(17)exp(−N(N−1)4(p−1))∑s=1pErrsMSE(∏r=sp−1ηr)(p−s,0) eq:tail-ratio≤ (- N(N-1)4(p-1) ) _s=1^pErr MSE_s ( _r=s^p-1 _r ) c(p-s,0) (18) =exp(−N(N−1)4(p−1))∑i=1k−1(∑s=1pErrsMSE(∏r=sp−1ηr)p−s1)i = (- N(N-1)4(p-1) ) _i=1^k-1 ( _s=1^pErr MSE_s ( _r=s^p-1 _r )T^p-s e_1 )_i =(11)exp(−N(N−1)4(p−1))(1−ErrpMSE) eq:edge-facts= (- N(N-1)4(p-1) )(1-Err MSE_p) ≤exp(−N(N−1)4(p−1)), ≤ (- N(N-1)4(p-1) ), (19) where (18) follows from (17) when 1≤N≤p−s≤p−11≤ N≤ p-s≤ p-1, and (p−s,N)=0 c(p-s,N)=0 when N>p−sN>p-s. Let N=⌈2p⌉N= 2 p . Then N≥2p≥2N≥ 2 p≥ 2 and N−1≥2p−1≥pN-1≥ 2 p-1≥ p, implying N(N−1)≥2p≥2(p−1)N(N-1)≥ 2p≥ 2(p-1). Equation (19) now yields ck−N(p)≤e−1/2<23.c_k-N^(p)≤ e^-1/2< 23. Now applying Lemma 4.3, we have ErrpMSE≥(1−ck−N(p))2N+1≥(1/3)24p=136p.Err MSE_p≥ (1-c_k-N^(p))^2N+1≥ (1/3)^24 p= 136 p. Finally, for p=1p=1, we have ErrpMSE=1/2Err_p MSE=1/2, which satisfies the above. ∎ Improving constants. The constant 1/361/36 is loose in the above: Theorem 4.6 performs improved book-keeping to show a tighter lower bound. Theorem 4.6. For every 2≤p≤k−12≤ p≤ k-1 and t>0t>0 such that ⌈tp−1+1⌉≤k−1 t p-1+1 ≤ k-1, ErrpMSE≥(1−e−t2/4)2tp−1+3.Err MSE_p≥ (1-e^-t^2/4)^2t p-1+3. (20) Using t=3t=3 in Theorem 4.6, gives approximately ErrpMSE≥13.75pErr MSE_p≥ 13.75 p when p and k are large enough. 5 Regression with a Convex Loss In this section, we analyze learning with a general loss ℓ(Y^,Y) ( Y,Y) that is convex in the first argument, subject to a few regularity conditions, which are satisfied by several common losses. Unlike Section 4, we will specialize to the gaussian instance in our worst case family, assuming Z1,…,Zk∼i.i.d.(0,1)Z_1,…,Z_k i.i.d. N(0,1). Recall that Xk(p−1)+j=Zj−Zj−1X_k(p-1)+j=Z_j-Z_j-1 for 1≤j≤k,1≤p≤k−11≤ j≤ k,1≤ p≤ k-1, and the predictor output by learner i is Y^i=αiXi+βiY^i−1 Y_i= _iX_i+ _i Y_i-1, where (αi,βi)( _i, _i) is the solution to minα,β∈ℝℓ(αXi+βY^i−1,Zk), _α,β (α X_i+β Y_i-1,Z_k ), (21) with Y^0=0,Z0=0 Y_0=0,Z_0=0. Note that for all i, both XiX_i and Y^i−1 Y_i-1 are linear combinations of Z1,…,Zk\Z_1,…,Z_k\. Defining L()=ℓ(∑jajZj,Zk)L( a)= ( _ja_jZ_j,Z_k), our first regularity condition requires that the population loss be differentiable, strongly convex on a radius 22 neighborhood around the origin, and minimized at the true label: L is differentiable, μ-strongly convex on :‖2≤2, and minimized at kL is differentiable, μ-strongly convex on \ a \| a\|_2≤ 2\, and minimized at e_k (Regular-I) Further, the second regularity condition we impose on ℓ is that the predictor minimizing the population loss be positively correlated with the label, i.e., for a random variable E∼(0,γ0(1−γ0))E N(0, _0(1- _0)) independent of ZkZ_k, and scalar 12≤γ0≤1 12≤ _0≤ 1, we have minγ∈ℝℓ(γ(E+γ0Zk),Zk) is attained at γ∈(0,2] _γ (γ(E+ _0Z_k),Z_k) is attained at γ∈(0,2] (Regular-I) Using (Regular-I) and (Regular-I), we give an inductive argument showing that learning with ℓ incurs a Ω(1/p) (1/ p) error relative to the best linear predictor, matching the dependence that we saw for learning with MSE MSE in Section 4. In particular, we will prove the following: Lemma 5.1. Y^i Y_i is a positive scaled multiple of Y^i,MSE Y_i, MSE for all i≥0i≥ 0, where Y^i,MSE Y_i, MSE and Y^i Y_i are the predictors output by the learner i when learning with MSE MSE (1), and ℓ (21), respectively. Proof. The base case is verified trivially as Y^0=Y^0,MSE=0 Y_0= Y_0, MSE=0. Assume that the inductive hypothesis is true for i−1i-1, i.e., Y^i−1=γi−1Y^i−1,MSE Y_i-1= _i-1 Y_i-1, MSE for some γi−1>0 _i-1>0. Decompose Zk=Y^i,MSE+E1Z_k= Y_i, MSE+E_1, where E1E_1 is a random variable independent of (Xi,Y^i−1)(X_i, Y_i-1). It can be seen that E1E_1 is not zero. The key observation needed now comes from Li and Duan 1989: their conditioning argument can be replicated by expanding (21) as follows, ℓ(αXi+βY^i−1,Zk)=(ℓ(αXi+βY^i−1,Zk)|Y^i,MSE,E1)≥(ℓ((αXi+βY^i−1|Y^i,MSE,E1),Zk)) (α X_i+β Y_i-1,Z_k )= ( (α X_i+β Y_i-1,Z_k )| Y_i, MSE,E_1 )≥ ( ( (α X_i+β Y_i-1| Y_i, MSE,E_1 ),Z_k) ) where the inequality is due to Jensen’s inequality applied to the convex function ℓ(⋅,z) (·,z) for any fixed z. Further, E1⟂(Xi,Y^i−1)E_1 (X_i, Y_i-1) implies E1⟂Y^i,MSEE_1 Y_i, MSE, as Y^i,MSE Y_i, MSE is a linear combination of XiX_i and Y^i−1,MSE=(1/γi−1)Y^i−1 Y_i-1, MSE=(1/ _i-1) Y_i-1. Hence, (αXi+βY^i−1|Y^i,MSE,E1)=(αXi+βY^i−1|Y^i,MSE). (α X_i+β Y_i-1| Y_i, MSE,E_1)= (α X_i+β Y_i-1| Y_i, MSE). Now, αXi+βY^i−1α X_i+β Y_i-1 and Y^i,MSE Y_i, MSE are both linear combinations of Z1,…,Zk\Z_1,…,Z_k\, i.e., they are zero-mean, jointly gaussian random variables. Hence for some γ∈ℝγ , we have (αXi+βY^i−1|Y^i,MSE)=γY^i,MSE. (α X_i+β Y_i-1| Y_i, MSE)=γ Y_i, MSE. We have thus shown that the objective of (21), at every feasible predictor is lower bounded by the objective at a predictor of the form γY^i,MSEγ Y_i, MSE. Further, this predictor is feasible for (21), as Y^i−1=γi−1Y^i−1,MSE Y_i-1= _i-1 Y_i-1, MSE with γi−1≠0 _i-1≠ 0. This shows that there always exists a minimizer of (21) of the form γY^i,MSEγ Y_i, MSE, for some γ∈ℝγ . The optimization problem (21) now reduces to minγ∈ℝℓ(γY^i,MSE,Zk). _γ (γ Y_i, MSE,Z_k). For completing the argument, we need to show that this minimizer γ⋆γ exists, is positive, and unique, implying that it is indeed output by learner i. We handle i≥ki≥ k and 1≤i≤k−11≤ i≤ k-1 separately. For all i≥ki≥ k, by Lemma 4.2, we have Y^i,MSE=E2+akiZk Y_i, MSE=E_2+a^i_kZ_k, for some 12≤aki≤1 12≤ a^i_k≤ 1, and E2E_2 a gaussian independent of ZkZ_k with Var(E2)=aki(1−aki) Var(E_2)=a^i_k(1-a^i_k). Then, (Regular-I) implies that γ⋆Y^i,MSEγ Y_i, MSE is a minimizer of (21) for γ⋆∈(0,2]γ ∈(0,2]. Further, the coefficients of Y^i,MSE Y_i, MSE satisfy ‖i‖22=aki<1\| a^i\|_2^2=a^i_k<1 (Lemma 4.2) implying that γ⋆Y^i,MSEγ Y_i, MSE lies in the region where (Regular-I) guarantees that the population loss is strongly convex. Along with the convexity of ℓ , this ensures that γ⋆Y^i,MSEγ Y_i, MSE is the unique minimizer. For 1≤i≤k−11≤ i≤ k-1, Y^i,MSE=0 Y_i, MSE=0, implying that the zero predictor is a minimizer for (21). Now ℓ is convex, and (Regular-I) guarantees strong convexity near 0, implying that the zero predictor is the unique minimizer. ∎ Let the predictor11 1 Recall that we refer to the coefficients a instead of the predictor Y^=∑jajZj Y= _ja_jZ_j when non-ambiguous from context. at the end of pass p be MSE a MSE when learning on the gaussian instance with ℓMSE _ MSE, and ℓ a when learning with a loss ℓ . From Lemma 5.1, we have that ℓ=γMSE a =γ a MSE, and obtain ‖ℓ−k‖22 \| a - e_k\|_2^2 =‖γMSE−k‖22 =\|γ a MSE- e_k\|_2^2 =γ2‖MSE‖22−2γakMSE+1 =γ^2\| a MSE\|_2^2-2γ a MSE_k+1 =γ2akMSE−2γakMSE+akMSE−akMSE+1 =γ^2a MSE_k-2γ a MSE_k+a MSE_k-a MSE_k+1 =(1−γ)2akMSE+(1−akMSE) =(1-γ)^2a MSE_k+(1-a MSE_k) (22) ≥ErrpMSE, MSE_p, where we have invoked Lemma 4.2 on multiple steps, and define ErrpMSEErr MSE_p as the error obtained by the predictor MSE a MSE. Now using Theorem 2.1, we have shown the following result. Theorem 5.2 (MSE when learning with a regular loss). For learning with a loss ℓ satisfying (Regular-I) and (Regular-I), for the gaussian instance in the worst case family where Z1,Z2,…,Zk∼i.i.d.(0,1)Z_1,Z_2,…,Z_k i.i.d. N(0,1), for every 1≤p≤k−11≤ p≤ k-1, we have, (Y^(p)−Y)2≥136p, ( Y_(p)-Y)^2≥ 136 p, where Y^(p) Y_(p) denotes the predictor learnt by the last vertex on pass p. To obtain a bound on ErrℓErr instead, we use (Regular-I) on (22) to get ‖ℓ−k‖22≤akMSE+(1−akMSE)≤1\| a - e_k\|^2_2≤ a MSE_k+(1-a MSE_k)≤ 1. Along with ‖k‖2≤1\| e_k\|_2≤ 1, this shows ‖ℓ‖2≤2\| a \|_2≤ 2. Thus, when ℓ satisfies both (Regular-I) and (Regular-I), we have Errpℓ−Errℓ,⋆=L(ℓ)−L(k)≥(ℓ−k)⊤∇L(k)+μ2∥ℓ−k∥2≥μ72p. _p-Err , =L( a )-L( e_k)≥( a - e_k) ∇ L( e_k)+ μ2\| a - e_k\|^2≥ μ72 p. We have hence proved Theorem 2.3, and can apply it to several losses to obtain a Ω(1p) ( 1 p) error lower bound as corollaries. For the following discussion, fix a scalar γ0∈[1/2,1] _0∈[1/2,1], and let E∼(0,γ0(1−γ0))E N(0, _0(1- _0)) be independent of ZkZ_k. Further, denote the vector =(Z1,Z2,…,Zk) Z=(Z_1,Z_2,…,Z_k). 5.1 MSE For LMSE()=(∑jajZj−Zk)2L_ MSE( a)= ( _ja_jZ_j-Z_k)^2, we have LMSE()=(⊤(−k))2=(−k)⊤⊤(−k)=‖−k‖22,L_ MSE( a)= ( Z ( a- e_k))^2= ( a- e_k) Z Z ( a- e_k)=\| a- e_k\|_2^2, which is differentiable, strongly convex with μ=2μ=2, and minimized at k e_k. Thus (Regular-I) is verified. Further, (γ(E+γ0Zk)−Zk)2=γ2γ0(1−γ0)+(γγ0−1)2=γ2γ0−2γγ0+1=(γ−1)2γ0+(1−γ0), (γ(E+ _0Z_k)-Z_k)^2=γ^2 _0(1- _0)+(γ _0-1)^2=γ^2 _0-2γ _0+1=(γ-1)^2 _0+(1- _0), which has a unique minimizer at γ=1γ=1. Thus, (Regular-I) is verified, and we recover the Ω(136p) ( 136 p) lower bound in Theorem 2.1, as expected. 5.2 Logistic Loss Recall that Llogistic()=ℓlogistic(⊤,Zk)L_ logistic( a)= _ logistic( a Z,Z_k), where ℓlogistic(y^,y)=−σ(y)logσ(y^)−(1−σ(y))log(1−σ(y^)) _ logistic( y,y)=-σ(y) σ( y)-(1-σ(y)) (1-σ( y)) with σ(t)=(1+exp(−t))−1σ(t)=(1+ (-t))^-1. Taking derivatives, we get ∂y^ℓlogistic(y^,y)=σ(y^)−σ(y), and∂2∂y^2ℓlogistic(y^,y)=σ(y^)(1−σ(y^))>0 for finite y^. ∂ y _logistic( y,y)=σ( y)-σ(y), and ∂^2∂ y^2 _logistic( y,y)=σ( y)(1-σ( y))>0 for finite y. Thus, L is differentiable and convex everywhere, and strongly convex in any bounded domain, e.g., :‖2≤2\ a \| a\|_2≤ 2\. Further, ∇L()=((σ(⊤)−σ(Zk)))=0∇ L( a)= ((σ( a Z)-σ(Z_k)) Z )=0 when =k a= e_k, implying that L has a unique minimizer at k e_k. We still need to explicitly obtain the strong convexity parameter μ. We have [∇2L()]u,v=σ′(⊤)ZuZv [∇^2L( a) ]_u,v= σ ( a Z)Z_uZ_v, i.e., ∇2L()=σ′(⊤)⊤.∇^2L( a)= σ ( a Z) Z Z . By rotational symmetry of the gaussian Z, we can replace Z by RR Z for any rotation matrix R. Specifically, take R such that R⊤=‖21R a=\| a\|_2 e_1. This gives ∇2L()=Rσ′(Z1‖2)⊤R⊤∇^2L( a)=R σ (Z_1\| a\|_2) Z Z R . As a result, we have [R⊤∇2L()R]u,v=0,u≠vσ′(Z1∥2)Z12,u=v=1σ′(Z1∥2),u=v≠1. [R ∇^2L( a)R ]_u,v= cases0, &u≠ v\\ σ (Z_1\| a\|_2)Z_1^2, &u=v=1\\ σ (Z_1\| a\|_2), &u=v≠ 1 cases. Thus, ∇2L()≽μIk∇^2L( a) μ I_k, where the strong convexity parameter μ=inf‖2≤2minσ′(Z1‖2)Z12,σ′(Z1‖2)μ= _\| a\|_2≤ 2 \ σ (Z_1\| a\|_2)Z_1^2, σ (Z_1\| a\|_2)\. Lemma B.1 completes this argument and gives μ≥0.048μ≥ 0.048. Thus, (Regular-I) is verified. Define F(γ)=ℓlogistic(γ(E+γ0Zk),Zk)F(γ)= _ logistic(γ(E+ _0Z_k),Z_k), and note that F is strongly convex in [0,2][0,2]. Further Lemma B.2, shows that F′(0)<0F (0)<0 and F′(1)≥0F (1)≥ 0, showing that the unique minimizer γ∗γ lies in (0,1](0,1], verifying (Regular-I). Subsequently, applying Theorem 2.3 proves Theorem 2.2. 5.3 Huber and other Losses For any fixed δ>0δ>0, define the Huber loss (Huber 1964) as L()=ℓhuber,δ(⊤−Zk)=ℓhuber,δ((−k)⊤)L( a)= _ huber,δ( a Z-Z_k)= _ huber,δ(( a- e_k) Z), where ℓhuber,δ(t)=12t2,|t|≤δ,δ|t|−δ22,|t|>δ. _ huber,δ(t)= cases 12t^2,&|t|≤δ,\\ δ|t|- δ^22,&|t|>δ cases. As earlier, it is clear that L is differentiable, strongly convex in :‖2≤2\ a \| a\|_2≤ 2\, and the minimizer is obtained at =k a= e_k. We need to obtain the strong convexity parameter μ. We have ∇L()=((|(−k)⊤|≤δ)⊤(−k)+(|(−k)⊤|>δ)δsgn(⊤(−k))).∇ L( a)= ( 1 (|( a- e_k) Z|≤δ ) Z Z ( a- e_k)+ 1 (|( a- e_k) Z|>δ )δ sgn( Z ( a- e_k)) Z ). Again, due to the rotational symmetry of the gaussian Z, we replace Z by RR Z for a rotation matrix such that R⊤(−k)=‖−k‖21R ( a- e_k)=\| a- e_k\|_2 e_1. This gives ∇2L()=(‖−k‖2|Z1|≤δ)R⊤R⊤∇^2L( a)= 1 (\| a- e_k\|_2|Z_1|≤δ )R Z Z R . When =k a= e_k, we have ∇2L()=I∇^2L( a)=I. Otherwise, the expression simplifies to [R⊤∇2L()R]u,v=0,u≠v(|Z1|≤δ‖−k‖2)Z12,u=v=1ℙ(|Z1|≤δ‖−k‖2),u=v≠1. [R ∇^2L( a)R ]_u,v= cases0,&u≠ v\\ 1 (|Z_1|≤ δ\| a- e_k\|_2 )Z_1^2,&u=v=1\\ (|Z_1|≤ δ\| a- e_k\|_2 ),&u=v≠ 1 cases. As with ‖−k‖2≤3\| a- e_k\|_2≤ 3, we get that the strong convexity parameter μ≥min(|Z1|≤δ/3)Z12,ℙ(|Z1|≤δ/3)>0μ≥ \ 1(|Z_1|≤δ/3)Z_1^2, (|Z_1|≤δ/3)\>0. This completes verification of (Regular-I). Further, defining H(γ)=ℓhuber,δ(γ(E+γ0Zk)−Zk)H(γ)= _ huber,δ(γ(E+ _0Z_k)-Z_k), we note that similar to the MSE, γ(E+γ0Zk)−Zk∼(0,(γ−1)2γ0+(1−γ0))γ(E+ _0Z_k)-Z_k N(0,(γ-1)^2 _0+(1- _0)), hence, H(γ)=ℓhuber,δ((γ−1)2γ0+(1−γ0)Z1)H(γ)= _ huber,δ( (γ-1)^2 _0+(1- _0)Z_1), which decreases as the variance of the random variable inside ℓhuber,δ _ huber,δ decreases. Hence, the unique minimizer is γ=1γ=1, verifying (Regular-I). Very similar analyses can be performed for other losses, like ℓ(y^,y)=ρ(y^−y) ( y,y)=ρ( y-y), or ℓ(y^,y)=−yy^+ρ(y^) ( y,y)=-y y+ρ( y) for a suitably normalized, strongly convex ρ. Finally, we note that the constant 22 in the regularity conditions can be generalized to c≥1c≥ 1 to show the same result, with minor modifications in the proofs. Acknowledgements and Disclosure of AI Usage We thank Aaron Roth and Michael Kearns for helpful discussions. Additionally, GPT 5.6 was used to discover the reference (Li and Duan 1989), shorten lengthy algebra in the generating function proof of Lemma 4.5, discover the elementary proof of Lemma B.1 by bounding the cosh function, and discover other losses that our argument applies to in Section 5.3. Appendix A Omitted Proofs for Section 4 A.1 Proof of Lemma 4.1 See 4.1 Proof. The objective in (1) is the squared Euclidean norm of the residual coefficient vector. We consider each vertex type separately. At a Type-I learner, the objective is [(αZ1+β∑j=1kajZj−Zk)2] [ (α Z_1+β _j=1^ka_jZ_j-Z_k )^2 ] =(α+βa1)2+∑j=2k−1(βaj)2+(βak−1)2. =(α+β a_1)^2+ _j=2^k-1(β a_j)^2+(β a_k-1)^2. (23) For every fixed β, we may set α=−βa1α=-β a_1, which makes the first term zero. The remaining objective is β2∑j=2kaj2−2βak+1.β^2 _j=2^ka_j^2-2β a_k+1. It is minimized at β=ak∑j=2kaj2=s1().β= a_k _j=2^ka_j^2=s_1( a). The new coefficient vector is therefore β(0,a2,…,ak)=s1()A1,β(0,a_2,…,a_k)=s_1( a)A_1 a, which proves (i). At a Type-I learner in position i, assigned Xk(p−1)+i=Zi−Zi−1X_k(p-1)+i=Z_i-Z_i-1, the objective is [(α(Zi−Zi−1)+β∑j=1kajZj−Zk)2] [ (α(Z_i-Z_i-1)+β _j=1^ka_jZ_j-Z_k )^2 ] =∑j∉i−1,i,k(βaj)2+(−α+βai−1)2+(α+βai)2+(βak−1)2. = _j∉\i-1,i,k\(β a_j)^2+(-α+β a_i-1)^2+(α+β a_i)^2+(β a_k-1)^2. (24) For fixed β, the terms containing α are minimized at α=β2(ai−1−ai).α= β2(a_i-1-a_i). At this value of α, both affected predictor coefficients equal β2(ai−1+ai). β2(a_i-1+a_i). Thus the new coefficient vector before optimizing over β is βAiβ A_i a, and the objective becomes β2∥Ai∥22−2βak+1.β^2 A_i a _2^2-2β a_k+1. It is minimized at β=ak∥Ai∥22=si(),β= a_k A_i a _2^2=s_i( a), which proves (i). At a Type-I learner, the objective is [(α(Zk−Zk−1)+β∑j=1kajZj−Zk)2] [ (α(Z_k-Z_k-1)+β _j=1^ka_jZ_j-Z_k )^2 ] =∑j=1k−2(βaj)2+(−α+βak−1)2+(α+βak−1)2. = _j=1^k-2(β a_j)^2+(-α+β a_k-1)^2+(α+β a_k-1)^2. (25) For fixed β, the terms containing α are minimized at α=1+β(ak−1−ak)2.α= 1+β(a_k-1-a_k)2. Substituting this value gives β2(∑j=1k−2aj2+12(ak−1+ak)2)−β(ak−1+ak)+12.β^2 ( _j=1^k-2a_j^2+ 12(a_k-1+a_k)^2 )-β(a_k-1+a_k)+ 12. The minimizing value of β is β=ak−1+ak2∑j=1k−2aj2+(ak−1+ak)2=sk().β= a_k-1+a_k2 _j=1^k-2a_j^2+(a_k-1+a_k)^2=s_k( a). At this value, the first k−2k-2 predictor coefficients are βajβ a_j, while the last two are β2(ak−1+ak)−12,β2(ak−1+ak)+12. β2(a_k-1+a_k)- 12, β2(a_k-1+a_k)+ 12. Hence the new coefficient vector is βAk+(0,…,0,−12,12)=sk()Ak+,β A_k a+(0,…,0,- 12, 12)=s_k( a)A_k a+ b, which proves (i). ∎ A.2 Proof of Lemma 4.2 See 4.2 Proof. Fix a learner i whose returned predictor has coefficient vector =(a1,…,ak) a=(a_1,…,a_k), and write Y=Zk,Y^=Y^i=∑j=1kajZj,Err=Err(i)=[(Y−Y^)2].Y=Z_k, Y= Y_i= _j=1^ka_jZ_j, =Err(i)= [(Y- Y)^2]. By the least-squares program (1), Y Y is the orthogonal projection of Y onto the feasible linear space i=spanXi,Y^i−1.S_i=span\X_i, Y_i-1\. Thus the residual Y−Y^Y- Y is orthogonal to every element of iS_i. In particular, because Y^∈i Y _i, [(Y−Y^)Y^]=0. [(Y- Y) Y]=0. (26) As [ZrZs]=r=s [Z_rZ_s]=1\r=s\, we have [YY^]=ak [Y Y]=a_k and [Y^2]=∑j=1kaj2 [ Y^2]= _j=1^ka_j^2. Substituting these two identities into (26) gives ak=∑j=1kaj2a_k= _j=1^ka_j^2, proving (4). Finally, [Y2]=[Zk2]=1 [Y^2]= [Z_k^2]=1, so expanding the squared error and using (4) yields Err=[Y2]−2[YY^]+[Y^2]=1−2ak+∑j=1kaj2=1−ak.Err= [Y^2]-2 [Y Y]+ [ Y^2]=1-2a_k+ _j=1^ka_j^2=1-a_k. This proves (2). Note that this error is non-increasing along the path as every vertex may retain its incoming predictor by setting the coefficient of its newly assigned feature to zero. At the first Type-I learner, the error is 1/21/2 by (27), hence every learner from that point onward has 0≤Err≤1/20 ≤ 1/2. We will further obtain Err≠0Err≠ 0 shortly due to the zero-sum condition. Along with (2), this gives 1/2≤ak<11/2≤ a_k<1. It remains to prove (3), (5), (6), and (7). For 1≤p≤k−11≤ p≤ k-1 and 1≤i≤k1≤ i≤ k, let (p,i) a^(p,i) be the vector returned by learner k(p−1)+ik(p-1)+i. Set (0)= a^(0)= 0. Then (p,0)=(p−1),(p,i)=Ti((p,i−1)),(p,k)=(p). a^(p,0)= a^(p-1), a^(p,i)=T_i( a^(p,i-1)), a^(p,k)= a^(p). The final update in every pass has the form (p,k)=sk((p,k−1))Ak(p,k−1)+. a^(p,k)=s_k( a^(p,k-1))A_k a^(p,k-1)+ b. The last two coordinates of Ak(p,k−1)A_k a^(p,k-1) are equal, while those of b are −1/2-1/2 and 1/21/2. Their difference is therefore 11, proving (5). Combining this identity with (2) gives (6). We first prove (3). During the first pass, Ti()=T_i( 0)= 0 for i<ki<k, and the Type-I vertex outputs (1)=(0,…,0,−12,12),Err1=12. a^(1)=(0,…,0,- 12, 12), _1= 12. (27) Thus (3) holds throughout the first pass. At its end, only the last two coordinates can be nonzero. In each later pass, the left-to-right Type-I updates can extend the support by at most one coordinate to the left, while the Type-I and Type-I maps do not extend it further. Hence, before every Type-I update in the regime p≤k−1p≤ k-1, the first coordinate is zero, so the Type-I output is a scalar multiple of the same zero-sum vector. Every Type-I averaging operator preserves the coordinate sum, as does scalar multiplication. Finally, AkA_k preserves the coordinate sum, and the entries of b sum to zero. Induction over the passes proves (3) at every vertex. We now prove (7) by induction over the passes. Equation (27) is the base case. For the induction step, fix 2≤p≤k−12≤ p≤ k-1, and assume that (7) holds at the end of pass p−1p-1. Since a1(p−1)=0a_1^(p-1)=0, the Type-I map at the start of pass p is the identity: by (4), its scale is ak(p−1)∑j=2k(aj(p−1))2=1 a_k^(p-1) _j=2^k(a_j^(p-1))^2=1. Hence (p,1)=(p−1) a^(p,1)= a^(p-1). Every Type-I scale is positive: its numerator satisfies ak>0a_k>0 by (2) and error monotonicity, and its denominator is positive. Therefore, scaling does not change support or signs. Before the Type-I updates, the induction hypothesis gives zero coordinates for j≤k−pj≤ k-p and negative coordinates for k−p+1≤j≤k−1k-p+1≤ j≤ k-1. The updates through i=k−pi=k-p average pairs of zeros. The update at i=k−p+1i=k-p+1 averages the pair (ak−p,ak−p+1)(a_k-p,a_k-p+1), making both entries negative, and every subsequent update averages two negative entries. Consequently, just before the Type-I update, aj(p,k−1)=0(j<k−p),aj(p,k−1)<0(k−p≤j≤k−1).a_j^(p,k-1)=0 (j<k-p), a_j^(p,k-1)<0 (k-p≤ j≤ k-1). Equation (3) and the preceding sign pattern give ak−1(p,k−1)+ak(p,k−1)=−∑j=1k−2aj(p,k−1)>0.a_k-1^(p,k-1)+a_k^(p,k-1)=- _j=1^k-2a_j^(p,k-1)>0. This is the numerator of the Type-I scale, whose denominator is positive. Thus the Type-I scale is positive as well. For j≤k−2j≤ k-2, the Type-I map only multiplies aj(p,k−1)a_j^(p,k-1) by its positive scale, so the support and signs above persist. It remains to check j=k−1j=k-1. Equation (6) gives ak−1(p)=−Errpa_k-1^(p)=-Err_p, where Errp>0Err_p>0 because the zero-sum condition rules out zero error. Finally, error monotonicity and Err1=1/2Err_1=1/2 give ak(p)=1−Errp≥12.a_k^(p)=1-Err_p≥ 12. This completes the induction and proves (7). ∎ A.3 Proof of Lemma 4.3 See 4.3 Proof. Recall that using [ZiZj]=i=j [Z_iZ_j]=1\i=j\, we have Errp=∑j<k(aj(p))2+(ak(p)−1)2.Err_p= _j<k(a_j^(p))^2+(a_k^(p)-1)^2. The last N+1N+1 residual coefficients sum to ∑j=k−Nk−1(−aj(p))+(1−ak(p))=1−ck−N(p). _j=k-N^k-1(-a_j^(p))+(1-a_k^(p))=1-c_k-N^(p). Cauchy–Schwarz on these N+1N+1 terms gives (1−ck−N(p))2≤(N+1)(∑j=k−Nk−1(aj(p))2+(1−ak(p))2)≤(N+1)Errp.(1-c_k-N^(p))^2≤(N+1) ( _j=k-N^k-1(a_j^(p))^2+(1-a_k^(p))^2 )≤(N+1)Err_p. ∎ A.4 Proof of Lemma 4.4 See 4.4 Proof. Let (p+1,i) a^(p+1,i) be the coefficient vector after the i-th learner in pass p+1p+1, for 0≤i≤k−10≤ i≤ k-1. Thus (p+1,0)=(p) a^(p+1,0)= a^(p), and (p+1,k−1) a^(p+1,k-1) is the vector returned by learner pk+k−1pk+k-1, the last Type-I learner. For 1≤i≤k−11≤ i≤ k-1, Lemma 4.1 gives (p+1,i)=Ti((p+1,i−1))=si((p+1,i−1))Ai(p+1,i−1). a^(p+1,i)=T_i ( a^(p+1,i-1) )=s_i ( a^(p+1,i-1) )A_i a^(p+1,i-1). As shown in the proof of (7), a1(p)=0a_1^(p)=0 and the Type-I scale is 11. Hence (p+1,1)=(p) a^(p+1,1)= a^(p). Then, by Note 1, we may ignore the positive scales introduced by the Type-I vertices when determining the vector entering the Type-I vertex. More precisely, define ~(p+1,k−1):=Ak−1⋯A2(p). a^(p+1,k-1):=A_k-1·s A_2 a^(p). Then (p+1,k−1) a^(p+1,k-1) is a positive scalar multiple of ~(p+1,k−1) a^(p+1,k-1). Since TkT_k is scale invariant, the final update may be computed from ~(p+1,k−1) a^(p+1,k-1). The operators A2,…,Ak−1A_2,…,A_k-1 successively replace the pairs (a1,a2),…,(ak−2,ak−1)(a_1,a_2),…,(a_k-2,a_k-1) by their averages. Define m0=0,mj=12(mj−1+aj+1(p)),1≤j≤k−2.m_0=0, m_j= 12 (m_j-1+a_j+1^(p) ), 1≤ j≤ k-2. At learner pk+2pk+2, assigned Xpk+2=Z2−Z1X_pk+2=Z_2-Z_1, the first two entries are replaced by m1=a2(p)/2m_1=a_2^(p)/2. At the next learner, the second and third entries are replaced by m2=(m1+a3(p))/2m_2=(m_1+a_3^(p))/2, and so on. It follows inductively that, after all Type-I learners, the vector entering the final learner (ignoring the scale) is ~(p+1,k−1)=(m1,…,mk−2,mk−2,ak(p)). a^(p+1,k-1)=(m_1,…,m_k-2,m_k-2,a_k^(p)). The running-average recurrence has the explicit form mj=∑r=2j+12−(j−r+2)ar(p).m_j= _r=2^j+12^-(j-r+2)a_r^(p). (28) The Type-I map applies AkA_k, multiplies by a positive scale, which we denote by ηp _p, and then adds =(0,…,0,−12,12) b=(0,…,0,- 12, 12). Since w omits coordinate k, the additive term b affects only w1w_1 among the profile coordinates. By Lemma 4.2, specifically (6), w1(p+1)=−ak−1(p+1)=Errp+1.w_1^(p+1)=-a_k-1^(p+1)=Err_p+1. For 2≤i≤k−12≤ i≤ k-1, set j=k−ij=k-i, substitute r=k−(i−1+t)r=k-(i-1+t), and use (10) with a1(p)=0a_1^(p)=0. Equation (28) then gives wi(p+1)=−ηpmk−i=ηp∑t=0k−i2−(t+1)wi−1+t(p)=ηp((p))i.w_i^(p+1)=- _pm_k-i= _p _t=0^k-i2^-(t+1)w_i-1+t^(p)= _p(T w^(p))_i. We have thus proved (12), which, on iteration, gives (14). ∎ A.5 Proof of Theorem 4.6 See 4.6 Proof. Retaining the exact dependence on N in (19) (which was derived for p≥4p≥ 4, but holds for p=2,3p=2,3 as well), Lemma 4.3 gives, for every integer 1≤N≤k−11≤ N≤ k-1, Errp≥(1−exp−N(N−1)/(4(p−1)))2N+1.Err_p≥ (1- \-N(N-1)/(4(p-1))\ )^2N+1. (29) Take N=⌈tp−1+1⌉N= t p-1+1 in (29). Then N(N−1)≥t2(p−1),N+1≤tp−1+3,N(N-1)≥ t^2(p-1), N+1≤ t p-1+3, which proves (20). ∎ A.6 Proof of Lemma 4.5 See 4.5 Proof of Lemma 4.5. We will obtain a generating function V(x,y)V(x,y) containing the coefficients (p1)i(T^p e_1)_i, and then obtain the cumulative sum (p,N) c(p,N) from V(x,y)V(x,y). For the rest of this proof, x,yx,y are free variables, unrelated to their usage elsewhere in the manuscript. Functional equation for V. For 1≤i,j≤k−11≤ i,j≤ k-1, define vi,j=(i−11)j,v_i,j= (T^i-1 e_1 )_j, and note the boundary conditions v1,1=1v_1,1=1, v1,j=0v_1,j=0 for j≥2j≥ 2, and vi,1=0v_i,1=0 for i≥2i≥ 2. For i,j≥ki,j≥ k, we define vi,j=0v_i,j=0. Now, for i,j≥2i,j≥ 2, the definition of T gives vi,j=∑t≥02−(t+1)vi−1,j−1+t,v_i,j= _t≥ 02^-(t+1)v_i-1,j-1+t, which can be rewritten as the recurrence vi,j=12vi−1,j−1+12vi,j+1.v_i,j= 12v_i-1,j-1+ 12v_i,j+1. (30) Now, we arrange the coefficients vi,jv_i,j on a formal power series by defining V(x,y)=∑i,j≥1vi,jxiyj.V(x,y)= _i,j≥ 1v_i,jx^iy^j. Further, let V2(x)=∑i≥1vi,2xiV_2(x)= _i≥ 1v_i,2x^i be the formal power series obtained from the second column of the coefficient matrix. Now using the recurrence (30), we get ∑i,j≥2vi,jxiyj=12∑i,j≥2vi−1,j−1xiyj+12∑i,j≥2vi,j+1xiyj, _i,j≥ 2v_i,jx^iy^j= 12 _i,j≥ 2v_i-1,j-1x^iy^j+ 12 _i,j≥ 2v_i,j+1x^iy^j, which obtains V(x,y)−xy=xy2V(x,y)+12y(V(x,y)−xy−y2V2(x))V(x,y)-xy= xy2V(x,y)+ 12y (V(x,y)-xy-y^2V_2(x) ) using the boundary conditions. Equivalently, (2y−xy2−1)V(x,y)=2xy2−xy−y2V2(x). (2y-xy^2-1 )V(x,y)=2xy^2-xy-y^2V_2(x). (31) Solving for V. We will now apply the so-called kernel method to solve (31) for V(x,y)V(x,y). Let P(x,y)=2y−xy2−1,Q(x,y)=2xy2−xy−y2V2(x),P(x,y)=2y-xy^2-1, Q(x,y)=2xy^2-xy-y^2V_2(x), so that (31) is P(x,y)V(x,y)=Q(x,y)P(x,y)V(x,y)=Q(x,y). Letting U(x)=1−1−xxandU~(x)=1+1−x,U(x)= 1- 1-xx U(x)= 1+ 1-xx, be the roots of P(x,y)P(x,y) viewed as a polynomial in y, we have P(x,y)=−x(y−U(x))(y−U~(x))andQ(x,y)=y((2x−V2(x))y−x).P(x,y)=-x(y-U(x))(y- U(x)) Q(x,y)=y ((2x-V_2(x))y-x ). Note that U(x)U(x) is the only formal power series among the roots, the other root U~(x) U(x) contains the term 1/x1/x. It is tempting to substitute y=U(x)y=U(x) in (31) to obtain V2(x)V_2(x), and eventually V(x,y)V(x,y). However, we must be cautious, as [x0]U(x)≠0[x^0]U(x)≠ 0, and the composition of power series might not be well defined. Fortunately, we observe from the recurrence (30) that vi,j=0v_i,j=0 for j≥i+1j≥ i+1. Hence, the coefficient of xax^a in V(x,y)V(x,y), denoted [xa]V(x,y)[x^a]V(x,y), is a polynomial in y for all a≥0a≥ 0, and substituting a formal power series for y yields a valid formal power series V(x,U(x))V(x,U(x)). Since P(x,U(x))=0P(x,U(x))=0, (31) shows that Q(x,U(x))=0Q(x,U(x))=0. We thus have (2x−V2(x))U(x)=x(2x-V_2(x))U(x)=x, which in turn shows Q(x,y)=xU(x)y(y−U(x)).Q(x,y)= xU(x)y(y-U(x)). Consequently, recalling V(x,y)=Q(x,y)/P(x,y)V(x,y)=Q(x,y)/P(x,y), we have V(x,y)=(x/U(x))y(y−U(x))−x(y−U(x))(y−U~(x))=yU(x)U~(x)−yU(x)=xy1−xyU(x)=xy1−y(1−1−x), V(x,y)= (x/U(x))y(y-U(x))-x(y-U(x))(y- U(x))= yU(x) U(x)-yU(x)= xy1-xyU(x)= xy1-y(1- 1-x), where the last equality uses U(x)U~(x)=1/xU(x) U(x)=1/x. Extracting the partial sum. To obtain (p,N) c(p,N), we see that [xp+1yN](1−y)−1V(x,y)=∑j=1Nvp+1,j=(p,0)−(p,N),[x^p+1y^N](1-y)^-1V(x,y)= _j=1^Nv_p+1,j= c(p,0)- c(p,N), from which the required partial sum is obtained as (p,N) c(p,N) =[xp+1yN](1−y)−1(V(x,1)−V(x,y)). =[x^p+1y^N](1-y)^-1(V(x,1)-V(x,y)). Letting u(x)=1−1−xu(x)=1- 1-x, we have V(x,1)−V(x,y)1−y=x(1−u(x))(1−yu(x))=x1−u(x)∑r≥0yru(x)r, V(x,1)-V(x,y)1-y= x(1-u(x))(1-yu(x))= x1-u(x) _r≥ 0y^ru(x)^r, which implies (p,N)=[xp]u(x)N1−u(x). c(p,N)=[x^p] u(x)^N1-u(x). (32) We would ideally like to apply the Lagrange inversion formula to solve (32) using the implicit form u(x)=x⋅(2−u(x))−1.u(x)=x·(2-u(x))^-1. (33) However, direct application leads to a cumbersome calculation involving sums of binomial coefficients. It is easier to apply a variant instead (see (Flajolet and Sedgewick 2009, Appendix A.6, A.13)). To do this, we differentiate (33) to get u′(x)=12(1−u(x))u (x)= 12(1-u(x)), which then gives dxu(x)N+1=(N+1)u(x)Nu′(x)=N+12u(x)N1−u(x). ddxu(x)^N+1=(N+1)u(x)^Nu (x)= N+12 u(x)^N1-u(x). Let H be any formal power series H(x)H(x). Then we have [xp]H′(x)=(p+1)[xp+1]H(x)[x^p]H (x)=(p+1)[x^p+1]H(x). Therefore, we have [xp]u(x)N1−u(x)=2N+1[xp]dxu(x)N+1=2(p+1)N+1[xp+1]u(x)N+1. [x^p] u(x)^N1-u(x)= 2N+1[x^p] ddxu(x)^N+1= 2(p+1)N+1[x^p+1]u(x)^N+1. Now recall the Lagrange inversion formula which gives [xa]H(u)=1a[ua−1](H′(u)ϕ(u)a)[x^a]H(u)= 1a[u^a-1](H (u)φ(u)^a) for a formal power series u(x)u(x) satisfying the functional form u=xϕ(u)u=xφ(u), [x0]u=0[x^0]u=0, any formal power series H, and ϕ(0)≠0φ(0)≠ 0. Applying this with ϕ(u)=(2−u)−1φ(u)=(2-u)^-1, and H(u)=uN+1H(u)=u^N+1, we have [xp+1]u(x)N+1=N+1p+1[up−N](2−u)−(p+1).[x^p+1]u(x)^N+1= N+1p+1[u^p-N](2-u)^-(p+1). Hence, for 0≤N≤p0≤ N≤ p, we use the generalized binomial coefficients to get [xp]u(x)N1−u(x)=2[up−N](2−u)−(p+1)=2(−(p+1)p−N)(−1)p−N2−(p+1)−(p−N)=2N−2p(2p−Np). [x^p] u(x)^N1-u(x)=2[u^p-N](2-u)^-(p+1)=2 -(p+1)p-N(-1)^p-N2^-(p+1)-(p-N)=2^N-2p 2p-Np. Further, [x0]u(x)=0[x^0]u(x)=0, implies that the coefficient [xp]u(x)N1−u(x)=0[x^p] u(x)^N1-u(x)=0 for all p<Np<N. Finally, (p,N)(p,0)=2N(2p−Np)(2p)=∏j=0N−1(1−j2p−j)≤exp(−∑j=0N−1j2p)=exp(−N(N−1)4p), c(p,N) c(p,0)=2^N 2p-Np 2pp= _j=0^N-1 (1- j2p-j )≤ (- _j=0^N-1 j2p )= (- N(N-1)4p ), for all 1≤N≤p1≤ N≤ p, where we have used 1−x≤e−x1-x≤ e^-x and 2p−j≤2p2p-j≤ 2p for the inequality. ∎ Appendix B Omitted Proofs for Section 5 B.1 Proof of Lemma B.1 Lemma B.1. Let G∼(0,1)G N(0,1). For every 0≤r≤20≤ r≤ 2, min[σ′(rG)],[G2σ′(rG)]≥1123>0.048. \ [σ (rG)], [G^2σ (rG)] \≥ 112 3>0.048. Proof. Let S∼Unif−1,1S \-1,1\ be a Rademacher random variable. Since [S]=0 [S]=0 and S∈[−1,1]S∈[-1,1], Hoeffding’s lemma gives, for every u∈ℝu , eu+e−u2=[euS]≤exp(u2(1−(−1))28)=eu2/2. e^u+e^-u2= [e^uS]≤ ( u^2(1-(-1))^28 )=e^u^2/2. (34) From the definition σ(t)=(1+e−t)−1σ(t)=(1+e^-t)^-1, applying (34) with u=t/2u=t/2 gives σ′(t)=e−t(1+e−t)2=1(et/2+e−t/2)2=14(et/2+e−t/22)−2≥14(et2/8)−2=14e−t2/4.σ (t)= e^-t(1+e^-t)^2= 1(e^t/2+e^-t/2)^2= 14 ( e^t/2+e^-t/22 )^-2≥ 14 (e^t^2/8 )^-2= 14e^-t^2/4. Consequently, for every r≥0r≥ 0, σ′(rG)≥14e−r2G2/4.σ (rG)≥ 14e^-r^2G^2/4. (35) For a≥0a≥ 0, first write each expectation against the standard Gaussian density: [e−aG2] [e^-aG^2] =12π∫ℝe−(1+2a)x2/2dx, = 1 2π _Re^-(1+2a)x^2/2\,dx, [G2e−aG2] [G^2e^-aG^2] =12π∫ℝx2e−(1+2a)x2/2dx. = 1 2π _Rx^2e^-(1+2a)x^2/2\,dx. Under the change of variables z=1+2axz= 1+2a\,x, we have dx=(1+2a)−1/2dzdx=(1+2a)^-1/2\,dz and x2=(1+2a)−1z2x^2=(1+2a)^-1z^2. Hence [e−aG2] [e^-aG^2] =(1+2a)−1/212π∫ℝe−z2/2dz=(1+2a)−1/2, =(1+2a)^-1/2 1 2π _Re^-z^2/2\,dz=(1+2a)^-1/2, [G2e−aG2] [G^2e^-aG^2] =(1+2a)−3/212π∫ℝz2e−z2/2dz=(1+2a)−3/2, =(1+2a)^-3/2 1 2π _Rz^2e^-z^2/2\,dz=(1+2a)^-3/2, where the last equalities use that the standard Gaussian density integrates to one and [G2]=1 [G^2]=1, respectively. Taking a=r2/4a=r^2/4 in these identities and using (35) gives [σ′(rG)] [σ (rG)] ≥14(1+r22)−1/2, ≥ 14 (1+ r^22 )^-1/2, [G2σ′(rG)] [G^2σ (rG)] ≥14(1+r22)−3/2. ≥ 14 (1+ r^22 )^-3/2. Since 1+r2/2≥11+r^2/2≥ 1 and r≤2r≤ 2, both expectations are at least 14(1+r22)−3/2≥14(3)−3/2=1123. 14 (1+ r^22 )^-3/2≥ 14(3)^-3/2= 112 3. ∎ B.2 Proof of Lemma B.2 Lemma B.2. Fix γ0∈[1/2,1] _0∈[1/2,1]. Let Z∼(0,1)Z N(0,1) and E∼(0,γ0(1−γ0))E N(0, _0(1- _0)) be independent, and define F(γ)=ℓlogistic(γ(E+γ0Z),Z).F(γ)= _ logistic (γ(E+ _0Z),Z ). Then F′(0)<0F (0)<0 and F′(1)≥0F (1)≥ 0. Proof. Let X=E+γ0ZX=E+ _0Z. Since E and Z are independent, mean zero gaussian random variables, we have that X is a mean zero gaussian with variance Var(X)=Var(E)+γ02Var(Z)=γ0(1−γ0)+γ02=γ0. Var(X)= Var(E)+ _0^2 Var(Z)= _0(1- _0)+ _0^2= _0. Further, Cov(X,Z)=γ0 Cov(X,Z)= _0, and F′(γ)=[(σ(γX)−σ(Z))X]=γ0γ[σ′(γX)]−[σ′(Z)],F (γ)= [ (σ(γ X)-σ(Z) )X ]= _0 \γ [σ (γ X)]- [σ (Z)] \, where the last equality follows by applying Stein’s identity in the form [f(E1)E2]=Cov(E1,E2)f′(E1) [f(E_1)E_2]= Cov(E_1,E_2) f (E_1) for centered jointly gaussian random variables (E1,E2)(E_1,E_2). Let G∼(0,1)G N(0,1). At γ=0γ=0, F′(0)=−γ0[σ′(G)]<0,F (0)=- _0 [σ (G)]<0, because γ0>0 _0>0 and σ′(G)>0σ (G)>0 almost surely. At γ=1γ=1, we get F′(1)=γ0[σ′(γ0G)]−[σ′(G)].F (1)= _0 \ [σ ( _0G)]- [σ (G)] \. Fix any g∈ℝg . Since γ0≤1 _0≤ 1, we have |γ0g|≤|g|| _0g|≤|g|. Moreover, σ′(t)=(et/2+e−t/2)−2σ (t)=(e^t/2+e^-t/2)^-2, i.e., σ′(t)=σ′(|t|)σ (t)=σ (|t|) and σ′σ decreases on [0,∞)[0,∞). Hence σ′(γ0g)=σ′(|γ0g|)≥σ′(|g|)=σ′(g).σ ( _0g)=σ (| _0g|)≥σ (|g|)=σ (g). Taking expectations and using γ0>0 _0>0 shows that F′(1)≥0F (1)≥ 0. ∎ References Bateni et al. (2026) Mohammadhossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, and Shayan Taherijam. Networked information aggregation for binary classification. In Forty-third International Conference on Machine Learning, 2026. Flajolet and Sedgewick (2009) P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. URL https://doi.org/10.1017/CBO9780511801655. Huber (1964) P. J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73–101, 1964. URL https://doi.org/10.1214/aoms/1177703732. Kearns et al. (2026) M. Kearns, A. Roth, and E. Ryu. Networked information aggregation via machine learning. In Proceedings of the Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), 2026. Li and Duan (1989) K.-C. Li and N. Duan. Regression analysis under link violation. The Annals of Statistics, 17(3):1009–1052, 1989. URL https://doi.org/10.1214/aos/1176347254.