Paper deep dive
Dynamics of Learning under User Choice: Overspecialization and Peer-Model Probing
Adhyyan Narang, Sarah Dean, Lillian J Ratliff, Maryam Fazel
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 7/20/2026, 8:19:58 AM
Summary
This paper investigates the dynamics of machine learning in multi-platform markets where users select platforms based on both model quality and inherent preferences. It identifies an 'overspecialization trap' where standard algorithms (MSGD) converge to models with poor global performance despite good local performance, due to feedback loops that restrict data observation. The authors propose a 'peer-model probing' mechanism inspired by knowledge distillation, allowing learners to query peer models for synthetic labels to learn about unobserved users. Theoretical analysis proves that this approach converges to stationary points with bounded full-population risk under specific conditions, and empirical results on MovieLens, Census, and Amazon Sentiment datasets validate these findings.
Entities (12)
Relation Signals (11)
Sarah Dean → authored → Dynamics of Learning under User Choice: Overspecialization and Peer-Model Probing
confidence 95% · Adhyyan Narang† Sarah Dean‡ Lillian J. Ratliff† Maryam Fazel†
Maryam Fazel → authored → Dynamics of Learning under User Choice: Overspecialization and Peer-Model Probing
confidence 95% · Adhyyan Narang† Sarah Dean‡ Lillian J. Ratliff† Maryam Fazel†
Lillian J. Ratliff → authored → Dynamics of Learning under User Choice: Overspecialization and Peer-Model Probing
confidence 95% · Adhyyan Narang† Sarah Dean‡ Lillian J. Ratliff† Maryam Fazel†
Adhyyan Narang → authored → Dynamics of Learning under User Choice: Overspecialization and Peer-Model Probing
confidence 95% · Adhyyan Narang† Sarah Dean‡ Lillian J. Ratliff† Maryam Fazel†
Peer-Model Probing → mitigates → Overspecialization Trap
confidence 95% · We propose an algorithm that allows learners to 'probe' the predictions of peer models... Our analysis characterizes when probing succeeds: this procedure converges almost surely to a stationary point with bounded full-population risk
MSGD → suffersfrom → Overspecialization Trap
confidence 95% · We find that there exist instances where learners who use existing algorithms almost surely converge to models with arbitrarily poor global performance... This happens through a feedback-induced mechanism, which we call the overspecialization trap
MovieLens → usedin → Empirical Validation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In many economically relevant contexts where machine learning is deployed, multiple platforms obtain data from the same pool of users, each of whom selects the platform that best serves them. Prior work in this setting focuses exclusively on the "local" losses of learners on the distribution of data that they observe. We find that there exist instances where learners who use existing algorithms almost surely converge to models with arbitrarily poor global performance, even when models with low full-population loss exist. This happens through a feedback-induced mechanism, which we call the overspecialization trap: as learners optimize for users who already prefer them, they become less attractive to users outside this base, which further restricts the data they observe. Inspired by the recent use of knowledge distillation in modern ML, we propose an algorithm that allows learners to "probe" the predictions of peer models, enabling them to learn about users who do not select them. Our analysis characterizes when probing succeeds: this procedure converges almost surely to a stationary point with bounded full-population risk when probing sources are sufficiently informative, e.g., a known market leader or a majority of peers with good global performance. We verify our findings with semi-synthetic experiments on the MovieLens, Census, and Amazon Sentiment datasets.
Tags
Links
- Source: https://arxiv.org/abs/2602.23565v2
- Canonical: https://arxiv.org/abs/2602.23565v2
Trouble viewing inline? Open PDF directly →
Full Text
166,472 characters extracted from source content.
Expand or collapse full text
Dynamics of Learning under User Choice: Overspecialization and Peer-Model Probing Adhyyan Narang† Sarah Dean‡ Lillian J. Ratliff† Maryam Fazel† Electrical and Computer Engineering, University of Washington† Computer Science, Cornell University ‡ Correspondence: adhyyan@uw.edu Abstract In many economically relevant contexts where machine learning is deployed, multiple platforms obtain data from the same pool of users, each of whom selects the platform that best serves them. Prior work in this setting focuses exclusively on the “local” losses of learners on the distribution of data that they observe. We find that there exist instances where learners who use existing algorithms almost surely converge to models with arbitrarily poor global performance, even when models with low full-population loss exist. This happens through a feedback-induced mechanism, which we call the overspecialization trap: as learners optimize for users who already prefer them, they become less attractive to users outside this base, which further restricts the data they observe. Inspired by the recent use of knowledge distillation in modern ML, we propose an algorithm that allows learners to "probe" the predictions of peer models, enabling them to learn about users who do not select them. Our analysis characterizes when probing succeeds: this procedure converges almost surely to a stationary point with bounded full-population risk when probing sources are sufficiently informative, e.g., a known market leader or a majority of peers with good global performance. We verify our findings with semi-synthetic experiments on the MovieLens, Census, and Amazon Sentiment datasets.111Code for this paper is available at: https://github.com/AdhyyanNarang/overspecialization-probing. 1 Introduction Traditional supervised learning theory typically assumes a single learner observing data drawn from a fixed distribution. However, this assumption is increasingly violated in modern machine learning markets, such as recommendation platforms and large language model (LLM) services. In these ecosystems, multiple learners operate on the same pool of users, and data is not assigned randomly. Instead, users choose which platform to engage with based on how well that platform serves their specific needs or preferences. Consequently, the data distribution observed by a learner is a function of the learner’s own performance and the choices available in the market. This setting is increasingly garnering interest in the machine learning community Dean et al. [2024]; Su and Dean [2024]; Ginart et al. [2021]; Bose et al. [2023]; Shekhtman and Dean [2024]. This coupling between model performance and user selection creates a feedback loop. As a learner optimizes for its current user base, it becomes increasingly specialized to that subpopulation. While this minimizes "local" loss on observed users, it often degrades performance on the unobserved population, a phenomenon we term overspecialization. Once a learner is overspecialized, it gets caught in an informational trap: it cannot learn to serve new users because it never observes them, and it never observes them because it cannot serve them. At a societal level, this dynamic fuels the formation of algorithmic echo chambers Cinus et al. [2022]; Beardow [2021]; Jiang et al. [2021]; Interian et al. [2022], where platforms fragment the population rather than learning a robust, globally capable model. Independently, another trend has become relevant in modern machine learning systems that has implications for the overspecialization problem: techniques such as knowledge distillation and training on synthetic data are becoming ubiquitous, particularly in the training of Large Language Models Hinton et al. [2015]; Werner [2025]. While these methods are typically employed to improve reasoning capabilities or computational efficiency (through compression of data), they introduce a structural change to the learning dynamic. Models are no longer limited to learning from organic user data, but can also "probe" other models to acquire synthetic labels. This enables learners to observe signals outside their siloed data distributions. In this work, we study whether the use of probing mechanisms in these machine learning markets can mitigate overspecialization. Our Contributions. We model a market where users select learners based on a combination of inherent preferences and predictive loss. We analyze the resulting dynamics through a game-theoretic lens to understand the impact of peer probing. Our main findings are as follows: 1. The Failure of Standard Learning: We first analyze standard Multi-learner Streaming Gradient Descent (MSGD) in the absence of probing [Su and Dean, 2024]. We prove that due to the user selection mechanism, MSGD can converge to "bad" stationary points. In these equilibria, learners become overspecialized, achieving low loss on their niche but arbitrarily poor performance on the global population. 2. Convergence of Peer Probing: We propose a new algorithm, MSGD with Probing (MSGD-P), where learners mix gradient updates from organic users with updates from pseudo-labeled queries sent to peer models. We prove that this multi-agent dynamic converges to a stationary point of a modified potential function (Theorem˜3). To our knowledge, we are the first to observe and study the multi-agent dynamics that arise from synthetic data training. 3. Restoring Global Competence: We show that probing effectively mitigates overspecialization. By characterizing the stationary points of MSGD-P, we derive bounds on the full-population loss under appropriate informational conditions (e.g., probing a known market leader vs. aggregating diverse peers). 4. Empirical Validation: We validate our findings on the MovieLens, US Census and Amazon Sentiment datasets. We observe that while standard learning leaves some models trapped with poor accuracy, introducing peer probing closes this performance gap. Figure 1: Illustration of our online multi-learner problem setting. The borders of users represent their highest ranked learner π(z)π(z). For further details, see Section˜3. 2 Related Work Our work sits at the intersection of three lines of research. We study a multi-learner setting where users select among competing platforms based on a combination of inherent preferences and predictive quality: a model richer than pure loss-minimization or uniform-random selection. Motivated by modern distillation practices, we analyze peer-model probing as a mechanism to mitigate overspecialization. Performative Prediction. Our setting is an instance of performative prediction [Perdomo et al., 2020; Hardt et al., 2016; Miller et al., 2021], where deploying a model influences the data a learner subsequently observes. Multi-learner extensions [Piliouras and Yu, 2023; Narang et al., 2023; Li et al., 2022; Wang et al., 2023; Zhu et al., 2023; Góis et al., 2025; Wang et al., 2025] provide general tools for endogenous distribution shift. We specialize to user-choice, where shift arises from selection rather than manipulation, enabling precise characterization of overspecialization and peer-model probing. Learning under User Agency. Prior work on user agency focuses on single-learner settings where users opt out or selectively provide data Hashimoto et al. [2018]; Zhang et al. [2019]; James et al. [2023]; Ben-Porat and Tennenholtz [2017]; Cherapanamjeri et al. [2023]; Harris et al. [2023]; Raab et al. [2024]; these analyses do not capture the inter-learner feedback dynamics that arise in our multi-learner setting. In the multi-learner setting, Ginart et al. [2021] characterize the existence of performance gaps due to competition via batch retraining; we prove that streaming dynamics converge to overspecialized equilibria (Theorem 2) and propose probing as a mitigation. Most closely related, Dean et al. [2024] and Su and Dean [2024] study gradient-based dynamics in choice-driven settings; we extend their framework to analyze full-population risk and introduce peer probing. See Appendix A for detailed comparisons with Ginart et al. [2021], Kwon et al. [2022], Bose et al. [2023], and Su and Dean [2024]. Knowledge Distillation. Our probing mechanism draws on knowledge distillation [Hinton et al., 2015] and self-training [Scudder, 1965; Yarowsky, 1995]; unlike Deep Mutual Learning [Zhang et al., 2018] and codistillation [Anil et al., 2018], which assume shared data, our setting couples distillation with user-driven selection, yielding novel multi-agent dynamics. This also distinguishes our setting from domain generalization methods, which train a centralized model from labeled source domains, and selective-label/sample-selection work, which typically studies a single learner under an exogenous censoring rule; here each learner’s observed distribution is endogenously determined by user choices among competing models. 3 Problem Setting We now formalize the machine learning market described above. 3.1 Users and Learners Consider a market with m service providers (learners) serving a population of users distributed according to P over =×Z=X×Y, where ⊆ℝdX ^d denotes covariates and Y denotes labels (⊆ℝY for regression, ⊆1,…,CY \1,…,C\ for classification). We write XP_X for the marginal distribution over covariates and Y∣X(⋅∣x)P_Y X(· x) for the conditional label distribution. When densities exist, we denote them by pXp_X and pY∣Xp_Y X. Each learner i∈[m]:=1,…,mi∈[m]:=\1,…,m\ maintains a model with parameters θi _i, and we write Θ=(θ1,…,θm) =( _1,…, _m) for the joint parameter vector. The loss ℓ(x,y;θ) (x,y;θ) measures the cost incurred by a model with parameters θ on a user with features x and label y. For regression, we consider linear predictors hθ(x)=x⊤θh_θ(x)=x θ with squared loss ℓSQ(x,y;θ)=(y−x⊤θ)2. _SQ(x,y;θ)=(y-x θ)^2. For classification with C classes, we use cross-entropy loss ℓCE(x,y;θ)=−∑c=1Cycloghθ(x)c, _CE(x,y;θ)=- _c=1^Cy_c h_θ(x)_c, where hθ(x)c=ex⊤θc/∑j=1Cex⊤θjh_θ(x)_c=e^x _c/ _j=1^Ce^x _j is the softmax output. Our framework can handle nonlinear relationships as well, as long as a suitable nonlinear feature transformation is known i.e if hθ(x)=ϕ(x)⊤θh_θ(x)=φ(x) θ. Assumption 1. The distribution P has continuous density pZ(z)=pX(x)pY|X(y|x)p_Z(z)=p_X(x)p_Y|X(y|x) with pXp_X supported on x:‖x‖≤R\x:\|x\|≤ R\ for some R>0R>0. For regression, pY|Xp_Y|X is supported on [−Ymax,Ymax][-Y_ ,Y_ ]. Under this assumption, both loss functions satisfy standard regularity conditions (see Appendix B). Lemma 1. Under Assumption 1, for all z∈z , the loss ℓ(z,⋅) (z,·) is non-negative, convex, differentiable, locally Lipschitz, and βℓ _ -smooth. 3.2 User Preferences and Platform Choice A central feature of our framework is that users have inherent preferences over platforms that exist independently of current model quality. These preferences capture factors such as brand loyalty, familiarity, network effects, or historical habits. We encode them via a function π:→[m]π:Z→[m], where π(z)π(z) denotes the platform that user z intrinsically prefers. This function is exogenous and fixed throughout learning: it represents pre-existing affinities that platforms cannot directly influence through model updates. The preference function π induces a partition of the user space. Let Si=z∈:π(z)=iS_i=\z :π(z)=i\ denote users who prefer platform i, with i=|SiP_i=P|_S_i the corresponding conditional distribution and αi=Prz∼[π(z)=i] _i= _z [π(z)=i] the fraction of users preferring platform i. Users do not only follow their inherent preferences; they also consider predictive quality. We model this tradeoff as follows: Definition 1 (User Selection Rule). Given models Θ , user z selects platform M(z;Θ)=π(z)with probability τ,argmini∈[m]ℓ(z;θi)with probability 1−τ.M(z; )= casesπ(z)&with probability τ,\\ _i∈[m] (z; _i)&with probability 1-τ. cases The parameter τ∈[0,1]τ∈[0,1] governs how strongly inherent preferences influence user behavior. When τ=1τ=1, users ignore model quality entirely and follow their intrinsic preferences. When τ=0τ=0, users select the platform minimizing their loss. For intermediate values, users often default to familiar platforms but sometimes shop based on quality. This model generalizes the setting of Su and Dean [2024], who assume users either minimize loss or choose uniformly at random. We make this choice because user preferences in practice are neither purely quality-driven nor purely random: the π(z)π(z) function captures persistent individual affinities that create systematic heterogeneity in platform selection. Model quality also induces a partition of users. Let Zi(Θ)=z:i=argminj∈[m]ℓ(z;θj)Z_i( )=\z:i= _j∈[m] (z; _j)\ denote users for whom platform i achieves minimal loss, with i(Θ)=|Zi(Θ)D_i( )=P|_Z_i( ) the conditional distribution and ai(Θ)=Prz∼[z∈Zi(Θ)]a_i( )= _z [z∈ Z_i( )] the population fraction. Under Definition 1, learner i observes users from the mixture i(Θ)=ταii+(1−τ)ai(Θ)i(Θ),O_i( )=τ _iP_i+(1-τ)a_i( )D_i( ), where i(Θ)O_i( ) is a sub-probability measure with total mass wi(Θ)=ταi+(1−τ)ai(Θ)w_i( )=τ _i+(1-τ)a_i( ). 3.3 Dynamics and Learning Objective We consider an online setting where learners interact with users over T timesteps, illustrated in Figure 1. At each step t: 1. A user zt∼z^t arrives and selects platform M(zt;Θt)M(z^t; ^t). 2. The selected learner observes ztz^t, incurs loss ℓ(zt;θM(zt;Θt)t) (z^t; _M(z^t; ^t)^t), and updates its parameters. We denote an instance of this market as =(,ℓ,π,τ)G=(P, ,π,τ). Learning Objective. Each learner’s goal is to minimize the full-population risk ℛ(θ)=z∼[ℓ(z;θ)].R(θ)=E_z [ (z;θ)]. We write θ⋆=argminθℛ(θ)θ = _θR(θ) for the population-optimal model and ϵ=ℛ(θ⋆)ε=R(θ ) for the Bayes risk. This objective differs from prior work [Su and Dean, 2024; Dean et al., 2024], which focuses on the “local” loss over each learner’s observed distribution i(Θ)O_i( ). We focus on full-population risk because the signature of overspecialization is precisely the gap between local and global performance: a learner may achieve low loss on i(Θ)O_i( ) while performing poorly on users outside its observed base. Understanding when this gap emerges and how to prevent it is the central question of this paper. 4 The Failure of Standard Learning Dynamics We now analyze Multi-learner Streaming Gradient Descent (MSGD), the standard algorithm for this setting introduced by Su and Dean [2024]. First, we reproduce the result from Su and Dean [2024] that MSGD converges to stationary points (Theorem 1); however, we use a different proof technique that we believe is more insightful, which we describe below. Despite convergence, we show that these equilibria can exhibit severe overspecialization: learners achieve low loss on observed users while performing arbitrarily poorly on the full population (Theorem 2). 4.1 Algorithm and Assumptions Algorithm 1 presents MSGD, studied in prior work by Su and Dean [2024]. When a user arrives and selects learner i, that learner performs a stochastic gradient update on the observed loss, and other learners remain unchanged. Algorithm 1 Multi-learner Streaming Gradient Descent (MSGD) [Su and Dean, 2024] 1:Loss function ℓ(⋅,⋅)≥0 (·,·)≥ 0; initial models Θ0=(θ10,…,θm0) ^0=(θ^0_1,…,θ^0_m); learning rate ηtt≥1\η^t\_t≥ 1 2:for t=0,1,2,…,Tt=0,1,2,…,T do 3: Sample user zt∼z^t 4: User selects learner i=M(zt;Θt)i=M(z^t; ^t) 5: θit+1←θit−ηt∇θℓ(zt;θit)θ^t+1_i←θ^t_i-η^t _θ (z^t;θ^t_i) 6:end for 7:return ΘT ^T In order to study the convergence behavior of the algorithm, we make the following standard assumptions on learning rates and loss geometry, which are the same as in Su and Dean [2024]. Assumption 2. The learning rates satisfy ∑t=1∞ηt=∞ _t=1^∞η^t=∞ and ∑t=1∞(ηt)2<∞ _t=1^∞(η^t)^2<∞. Assumption 3. For any θ≠θ′θ≠θ , there exists d0>0d_0>0 such that for all d<d0d<d_0, the set z:|ℓ(z;θ)−ℓ(z;θ′)|<d\z:| (z;θ)- (z;θ )|<d\ has Lebesgue measure at most d. Assumption 3, from Su and Dean [2024], rules out pathological cases where a large mass of users is nearly indifferent between two learners. Intuitively, it ensures that small parameter perturbations move only a small mass of users across loss-induced decision boundaries, so the partition-dependent potential f can be differentiated without boundary terms. Assumption 4 below is the standard boundedness condition used in stochastic-approximation analyses. 4.2 Convergence to Stationary Points In MSGD, each learner i optimizes its expected loss over observed users. Define the potential function f(Θ)f( ) as the sum of the expected losses of all learners on the distributions that they observe. f(Θ)=∑i=1mi(Θ)[ℓ(z;θi)],f( )= _i=1^mE_O_i( )[ (z; _i)], (1) where we recall that i(Θ)=ταii+(1−τ)ai(Θ)i(Θ),O_i( )=τ _iP_i+(1-τ)a_i( )D_i( ), and wi(Θ)=ταi+(1−τ)ai(Θ)w_i( )=τ _i+(1-τ)a_i( ). Note that this is the sum of the “local" losses of each of the learners on their observed distribution, unlike the global risk ℛ(⋅)R(·) that was introduced above. In order to show convergence, we make the same boundedness assumptions as in Su and Dean [2024]. Assumption 4. The parameter sequence Θtt≥0\ ^t\_t≥ 0 is almost surely bounded: supt≥0‖Θt‖<∞ _t≥ 0\| ^t\|<∞. Moreover, the set Θ:∇f(Θ)=0\ :∇ f( )=0\ is compact. Our approach uses stochastic approximation [Borkar, 2008] and differs from that of Su and Dean [2024]. The key insight is that f serves as a Lyapunov function: despite each learner optimizing over a different, endogenously-determined user distribution, the aggregate of local losses forms a coherent potential. This is surprising because multi-agent gradient dynamics often cycle or diverge [Mazumdar et al., 2020]; the Lyapunov structure explains why convergence occurs here. Concretely, we show that the MSGD iterates track the ODE Θ˙=−∇f(Θ) =-∇ f( ). The following lemma, proved using standard stochastic approximation arguments, establishes this connection. Lemma 2. Let Assumptions 1–4 hold. Then the iterates Θt\ ^t\ of Algorithm 1 converge to a compact connected internally chain transitive invariant set of the ODE Θ˙=−∇f(Θ) =-∇ f( ). See Appendix B.1 for definitions of the dynamical-systems terms used in Lemma 2. The lemma shows that the discrete stochastic dynamics behave, in the limit, like the continuous gradient flow on f. Since f decreases along trajectories of this ODE i.e dtf(Θ(t))=−‖∇f‖2≤0 ddtf( (t))=-\|∇ f\|^2≤ 0, the only invariant sets are stationary points. This yields our main convergence result. Theorem 1. Let Assumptions 1–4 hold. Then the iterates Θt\ ^t\ of Algorithm 1 converge to the set of stationary points Θ:∇f(Θ)=0\ :∇ f( )=0\ almost surely. Hence, the stochastic approximation framework reveals that MSGD implicitly minimizes a single global objective f, providing a clean explanation for why convergence occurs despite the multi-agent structure. The same potential argument extends to mini-batch updates, matching the implementation used in the experiments. If a batch ℬtB^t is sampled i.i.d. and learner i updates using the average gradient over the selected subset Sit=z∈ℬt:M(z;Θt)=iS_i^t=\z ^t:M(z; ^t)=i\, then conditional on Sit≠∅S_i^t≠ this average is an unbiased gradient over i(Θt)/wi(Θt)O_i( ^t)/w_i( ^t). Since wi(Θ)≥ταi>0w_i( )≥τ _i>0 for τ>0τ>0, the batch dynamics track the same potential with a bounded state-dependent rescaling of the step size. 4.3 The Overspecialization Trap While Theorem 1 guarantees convergence, the stationary points may be highly undesirable. A learner cannot improve on users it never observes, and it never observes users it cannot serve well. This feedback loop is the overspecialization trap. The following theorem shows that this trap can be severe: MSGD can converge to equilibria where some learners have arbitrarily poor global performance, even when models with low full-population loss exist. Theorem 2. Let Assumptions 1–4 hold. For any τ≥12τ≥ 12 and any choice of ϵ,Γε, with 0<ϵ<Γ0<ε< , there exists an instance G such that: 1. There exists θ⋆θ with ℛ(θ⋆)≤ϵR(θ )≤ε. 2. The MSGD iterates converge to a unique stationary point Θ¯ where ℛ(θ¯i)≥ΓR( θ_i)≥ for some learner i∈[m]i∈[m]. The key mechanism is as follows. When τ≥12τ≥ 12, inherent preferences dominate at equilibrium: the loss-induced partition collapses to the ranking partition, so that Zi(Θ)=SiZ_i( )=S_i for all i. Each learner optimizes exclusively for users who intrinsically prefer it, arriving at θ¯i=argminθz∼i[ℓ(z;θ)]. θ_i= _θE_z _i[ (z;θ)]. This specialization occurs regardless of whether a better global model exists. In the constructed instance (detailed in Appendix C), learner 1 achieves zero loss on its observed population 1P_1 while its full-population loss exceeds Γ . The learner has perfectly fit its niche while becoming arbitrarily poor globally. This dynamic formalizes the echo chamber phenomenon that platforms become increasingly specialized to their existing audience, unable to learn models that serve the broader population. The condition τ≥12τ≥ 12 delineates the regime where inherent preferences dominate user behavior. A key contribution of the analysis is showing that in this regime the equilibrium is unique and obtainable in closed form, which enables us to exactly characterize the risk. However, when τ<12τ< 12 and quality-based selection dominates, there may be multiple equilibria. Now, the limit point becomes initialization-dependent, which presents a technical obstacle to characterizing the limiting risk in closed form; however, experiments in Section 6 demonstrate similar phenomena across different values of τ. 5 Mitigating Overspecialization through Peer Probing The standard MSGD dynamics from Su and Dean [2024] fail to converge to models that perform well on the full population because they are “blocked” from observing users outside the ones who choose them, and are limited to learning from a restricted portion of the feature space. However, in many practical settings, learners can probe the predictions of other learners. For example, a platform could create an account on a competitor’s service to observe their recommendations. This concept has gained particular prominence in the context of Large Language Models (LLMs) through knowledge distillation Hinton et al. [2015], where one model learns from another model’s outputs. Recent work has extensively explored this area Werner [2025]; Xu et al. [2024]; Yang et al. [2024]; Li et al. [2024]; Tan et al. [2023]; Anonymous [2023]. The release of the DeepSeek LLM Werner [2025] has brought knowledge distillation to the forefront of both policy discussions and mainstream media attention Werner [2025]. Despite this growing practical importance, the theoretical implications of these multi-agent learning interactions—where models train on each other’s outputs—remain largely unexplored. This section asks the question: under what circumstances can probing the predictions of others help overcome the overspecialization trap? 5.1 Algorithm We propose MSGD with Probing (MSGD-P), shown in Algorithm 2. The algorithm has two phases. In the offline phase, each probing learner j∈Uj∈ U collects a dataset j D_j of pseudo-labeled examples by querying peer models on sampled covariates. In the online phase, learners interleave standard MSGD updates (on organic users) with gradient steps on their probing datasets. More concretely, for each probing learner i∈Ui∈ U, we sample covariates (x~i1,…,x~in)∼Xn( x^1_i,…, x^n_i) _X^n. Given a query covariate x, the learner selects a subset of peers Ti(x)⊆[m]T_i(x) [m] to consult, and forms a pseudo-label via median aggregation yagg,i(x,Θ)=medianhθj(x):j∈Ti(x).y_agg,i(x, )=median\h_ _j(x):j∈ T_i(x)\. We then define y~iq:=yagg,i(x~iq,Θ0) y^q_i:=y_agg,i( x^q_i, ^0) and the pseudo-labeled examples z~iq:=(x~iq,y~iq) z^q_i:=( x^q_i, y^q_i), and collect the probing dataset i:=z~iqq=1n D_i:=\ z^q_i\_q=1^n. The choice of Ti(x)T_i(x) determines which peers are consulted; we discuss this in Section 5.3. For a probing learner i∈Ui∈ U, the update can be interpreted as a stochastic gradient step on the following instantaneous loss: Lit(θi)=ταiz∼i[ℓ(z;θi)]+(1−τ)ai(Θt)z∼i(Θt)[ℓ(z;θi)]+pn∑q=1nℓ(z~iq;θi)+λp2‖θi‖2.L_i^t( _i)=τ _iE_z _i[ (z; _i)]+(1-τ)a_i( ^t)E_z _i( ^t)[ (z; _i)]+ pn _q=1^n ( z^q_i; _i)+ λ p2\| _i\|^2. (2) The first two terms capture organic learning from users who select learner i (via inherent preference iP_i or quality-based choice iD_i), while the third term captures learning from probing data. The parameter p>0p>0 controls the relative weight of probing gradients: larger p emphasizes pseudo-labels, smaller p prioritizes organic data. Algorithm 2 Multi-learner Streaming Gradient Descent with Probing (MSGD-P) 1:loss function ℓ(⋅,⋅)≥0 (·,·)≥ 0; Initial models Θ0=(θ10,…,θm0) ^0=(θ^0_1,…,θ^0_m); Learning rate ηtt=1T+1\η^t\_t=1^T+1, probing weight p>0p>0, set of probing learners U⊆[m]U [m], regularization weight λ≥0λ≥ 0 2:// Offline probing data collection 3:for j∈U:j∈ U: do 4: Sample covariates (x~j1,…,x~jn)∼Xn( x^1_j,…, x^n_j) _X^n. 5: Collect pseudo-labels and store dataset j=(x~j1,yagg,i(x~j1,Θ0))…(x~jn,yagg,i(x~jn,Θ0)) D_j=\ ( x^1_j,y_agg,i( x^1_j, ^0) )… ( x^n_j,y_agg,i( x^n_j, ^0) )\ 6:end for 7:// Online updates 8:for t=0,1,2,…,Tt=0,1,2,…,T do 9: Sample data point zt∼z^t 10: User selects model i=M(zt;Θt)i=M(z^t; ^t) 11: θit+1←θit−ηt∇ℓ(zt,θit)θ^t+1_i←θ^t_i-η^t∇ (z^t,θ^t_i) 12: for j∈U:j∈ U: do 13: Sample z~jt z^t_j uniformly from j D_j 14: θjt+1←θjt−ηtp(∇ℓ(z~jt,θjt)+λθjt)θ^t+1_j←θ^t_j-η^tp (∇ ( z^t_j,θ^t_j)+λθ^t_j ) 15: end for 16:end for 17:return ΘT ^T We assume that probing learners can sample covariates from the full distribution XP_X, but do not have access to true labels. This asymmetry is natural in practice: covariates are often publicly available or easy to generate, while labels require costly human annotation or reveal private user behavior. For example, a streaming service knows the metadata of all movies (genre, cast, runtime) and general user demographics, but not which movies a non-subscriber would rate highly. In the LLM setting, covariates are simply text prompts, which can be generated synthetically or scraped from public sources (e.g., Reddit, StackOverflow), whereas ground-truth responses require expensive human evaluation. We focus on offline probing, where pseudo-labels are collected once at initialization from a fixed snapshot of peer models. This design choice mirrors practical knowledge distillation workflows: in settings like DeepSeek distilling from Claude or GPT-4, teachers are queried to create a fixed dataset, and student training then proceeds independently [Werner, 2025]. Offline probing also ensures reproducibility by capturing a specific model version’s behavior, avoiding inconsistencies from querying peers at different stages of adaptation. We discuss extensions to online probing in Section 7. 5.2 Convergence With probing, each learner i∈Ui∈ U now optimizes a blend of two objectives: the loss on observed users (as in standard MSGD) and the loss on probing data. This leads to a modified potential function: f~(Θ)=f(Θ)+p∑i∈U(1n∑q=1nℓ(z~iq,θi)+λ2‖θi‖2), f( )=f( )+p _i∈ U ( 1n _q=1^n ( z^q_i, _i)+ λ2\| _i\|^2 ), (3) where the second term captures the probing loss (with regularization) weighted by p. The same stochastic approximation analysis from Section 4 extends to this setting: f~ f serves as a Lyapunov function for the modified dynamics, yielding the following convergence guarantee. Theorem 3. Let Assumptions 1-3, ˜4 (as applied to f~ f), and ˜5 hold. Then, the iterates Θt\ ^t\ of Algorithm˜2 converge to the set of stationary points Θ:∇f~(Θ)=0\ :∇ f( )=0\ almost surely. Crucially, the stationary points of f~ f differ from those of f: probing changes where learners converge, not whether they converge. The probing term pulls learners toward models that perform well on the probed distribution, potentially escaping the overspecialization trap. However, this benefit depends on the quality of the pseudo-labels—a question we address next. 5.3 When Does Probing Help? Note that the convergence guarantee above holds for any choice of Ti(x)T_i(x). However, in order for the probing data to be helpful, the pseudo-labels must be a good proxy for the ground-truth labels. Assumption 5 (Accurate Probing). We say that the “accurate probing” condition holds for probing learner i∈[m]i∈[m] if there exists B≥0B≥ 0 such that (x,y)∼[(yagg,i(x,Θ−i)−y)2]≤B. *E_(x,y) [ (y_agg,i(x, _-i)-y )^2 ]≤ B. This assumption is stated for a single probing learner i. Different learners may satisfy it via different scenarios (or not at all); performance guarantees in Section 5.4 apply to any learner for whom the assumption holds. Below, we identify scenarios under which Assumption 5 holds. These scenarios differ along two axes: what learner i must know about the market, and what must be true about peer models at initialization. Table 1 summarizes these scenarios; the second and third columns display the knowledge-vs-peer-requirement tradeoff. Scenario What i knows Peer requirement Ti(x)T_i(x) B Majority-good Nothing >50%>50\% in Br(θ∗)B_r(θ ) [m][m] R2r2+2ϵR^2r^2+2ε Market-leader Identity of j∗j ℛ(θj∗0)≤ξR(θ^0_j )≤ξ j∗\j \ ξ Partial knowledge Subset G >50%>50\% of G in Br(θ∗)B_r(θ ) G R2r2+2ϵR^2r^2+2ε Preference-aware π(x)π(x) Nothing π(x)\π(x)\ ϵε Table 1: Probing scenarios with corresponding rules and accuracy bounds. The preference-aware scenario is notable: it requires no assumption on peer quality, only knowledge of user preferences. Definition 2 (Globally good peers). We say learner i can achieve accurate probing via globally good peers if the following instance properties and knowledge conditions hold: (i) Majority-good. More than half of the learners satisfy θj0∈Br(θ∗) _j^0∈ B_r(θ ) for a given proximity parameter r>0r>0. (i) Market-leader. There exists a single learner j∗∈[m]j ∈[m] such that x∼[ℓ(x,θj∗0)]≤ξ, *E_x [ (x,θ^0_j )]≤ξ, and the identity of j∗j is known to learner i. (i) Partial knowledge. There exists a subset G⊆[m]∖iG [m] \i\ such that more than half of the learners in G satisfy θj0∈Br(θ∗) _j^0∈ B_r(θ ) for a given r>0r>0, and learner i has knowledge of the subset G. Above, the parameter r>0r>0 in the majority-good and partial-knowledge scenarios controls how close peers must be to θ∗θ ; smaller r yields tighter bounds. When no globally good learners exist or can be identified, probing may still be effective if the learner has access to ranking information. Definition 3 (Preference-aware probing). Suppose all learners initialize at the parameters Θ¯=(θ¯1,…,θ¯m) =( θ_1,…, θ_m). If learner i has knowledge of the inherent preference function π(z)π(z), which identifies each user’s preferred platform, we call this the preference-aware scenario. These definitions capture different approaches to probing: Definition 2 covers settings where learners can identify or rely on peers with strong global performance, while Definition 3 addresses settings where learners must instead leverage knowledge of user preferences. The scenarios exhibit a fundamental tradeoff: when peer models are favorable (e.g., many are globally good), learner i needs little knowledge to achieve accurate probing; conversely, with stronger knowledge (e.g., knowing π(x)π(x)), the learner can probe in a more targeted way, and probing succeeds even when no peer is globally competent. In realistic markets, learners often naturally gain access to information enabling one of these approaches. For Scenarios ((i)) or ((i)), platforms may observe broad industry benchmarks [Liang et al., 2023; Chiang et al., 2024; Russakovsky et al., 2015; Bennett and Lanning, 2007; Olson et al., 2017]. For Definition˜3, it is natural to maintain knowledge of user preference patterns [Guadagni and Little, 1983; Abdullah et al., 2021; Huang et al., 2018; Irani-Kermani et al., 2023]. For Scenario (i), there are examples in the LLM literature of this explicitly happening: for instance, the Alpaca model [Taori et al., 2023] was admittedly trained on data generated by text-davinci-003 (GPT-3.5), the Vicuna model [Chiang et al., 2023] was trained on data generated by GPT-4, and the survey paper Gudibande et al. [2024] documents the prevalence of this practice. The probing rule Ti(x)T_i(x) (fourth column of Table 1) in each scenario is chosen so that median aggregation is robust: probing all peers when the majority are good, targeting the known leader when one exists, or routing to the locally-expert peer in the preference-aware case. The preference-aware scenario is particularly notable: it requires no assumption on peer quality, only knowledge of user preferences π(x)π(x), enabling learner i to aggregate specialized knowledge into global competence even when every peer suffers from overspecialization. The next lemma shows that in each scenario, the pseudo-labels obtained via the corresponding Ti(x)T_i(x) are uniformly bounded in mean-squared error, ensuring that Assumption 5 holds. Lemma 3. For each scenario in Definitions 2–3, the probing rule Ti(x)T_i(x) in Table 1 satisfies Assumption 5 with the stated accuracy parameter B. 5.4 Performance Guarantees We now characterize the full-population risk of MSGD-P stationary points. The bound decomposes into four interpretable components: an irreducible Bayes error term, a probing bias term capturing pseudo-label inaccuracy, and two regularization-dependent terms reflecting a bias-variance tradeoff. Theorem 4. Let Assumptions 1–5 hold. For any κ∈(0,1)κ∈(0,1), with probability at least 1−κ1-κ, we have for probing learner i∈[m]i∈[m], for the squared loss: ℛ(θ~i)≤O((p+1p)ϵ+B+λ‖θ⋆‖2+(p+1)Cgenpλlog(1/κ)n).R( θ_i)\;≤\;O\! ( ( p+1p )ε+B+λ\|θ \|^2\;+\; (p+1)C_genpλ (1/κ)n ). where Cgen(R,Ymax,‖θ⋆‖,maxj≠i‖θj0‖)C_gen (R,Y_ ,\|θ \|, _j≠ i\| _j^0\| ) is stated explicitly in the Appendix. The four terms admit natural interpretations: (i) p+1pϵ p+1pε is the irreducible Bayes error, scaled by the ratio of total to probing gradient weight; (i) B is the probing bias from pseudo-label inaccuracy (see Table 1); (i) λ‖θ⋆‖2λ\|θ \|^2 is the regularization bias; and (iv) the final term captures finite-sample generalization error from n probing queries. The probing weight p controls the balance between the organic distribution (users who choose learner i) and the probing distribution (the full population). A learner who prioritizes performance on their existing user base may prefer smaller p, while a learner seeking global competence benefits from larger p. The regularization parameter λ exhibits a classical bias-variance tradeoff. Larger λ increases the regularization bias (λ‖θ⋆‖2λ\|θ \|^2) but improves generalization by keeping parameter norms bounded, reducing the O(1/λn)O(1/ λ n) term. Conversely, smaller λ reduces bias but worsens the generalization bound. Corollary 1. Let Assumptions 1–5 hold. Fix λ=ϵ/‖θ⋆‖2λ=ε/\|θ \|^2 and any κ∈(0,1)κ∈(0,1). Define M0:=maxj≠i‖θj0‖M_0:= _j≠ i\| _j^0\|. If there are sufficiently many probing samples n≥n¯(p,κ,ϵ,R,Ymax,M0,‖θ⋆‖)n≥ n(p,κ,ε,R,Y_ ,M_0,\|θ \|), then with probability at least 1−κ1-κ, every stationary point Θ~ of MSGD-P satisfies, for each probing learner i, ℛ(θ~i)≤O((p+1p)ϵ+B).R( θ_i)\;≤\;O\! ( ( p+1p )ε+B ). See Appendix E for the explicit sample complexity n¯ n and proof. We note that this sample complexity bound is not tight in n: we show in Figure 5 that strong empirical recovery can occur with very small probing datasets. Remark 1 (Cross-entropy loss). An analogous performance guarantee holds for cross-entropy loss; see Assumption 6 and Appendix F for the bound, and Table 2 for the corresponding accuracy parameters. Hence, probing breaks the information barrier created by user-choice dynamics: a learner who is overspecialized cannot observe users outside its niche and thus cannot learn to serve them. While Theorem˜2 shows that the loss of a learner may be arbitrarily worse than ϵε, for sufficiently large n, the bound above presents a ceiling on the risk of any probing learner. 6 Numerical Experiments We evaluate our approach on three real-world datasets: MovieLens-10M, the ACS Employment dataset from the US Census (Alabama, 2018), and the Amazon Reviews 2023 corpus. Figure 2: MSGD full-population performance with random initialization (Preference-aware scenario). Left: Census test accuracy. Mid: Amazon sentiment test accuracy Right: MovieLens test loss. The dashed black line represents the performance of a baseline θ∗θ trained on the full dataset. In all cases, τ=0.3τ=0.3; other dataset-specific hyperparameters are given in Table 3. 6.1 Experimental Setup We evaluate on three datasets; in each case, every data point corresponds to an individual user. Movie Recommendation with Squared Loss. We use the MovieLens-10M dataset [Harper and Konstan, 2015], which contains 10 million movie ratings from 70k users across 10k movies—a natural testbed for multi-learner competition in recommendation. Following Bose et al. [2023] and Su and Dean [2024], we extract d=16d=16 dimensional user embeddings via matrix factorization and retain ratings for the top 200 most-rated movies, yielding a population of 69,474 users. Each user’s data consists of z=(x,r)z=(x,r) where x∈ℝdx ^d is the embedding and r contains their ratings. Let Ωx _x denote the set of movies rated by user x with |Ωx|| _x| movies. Each learner fits a linear model θ∈ℝd×200θ ^d× 200 using squared loss: ℓ(z;θ)=1|Ωx|∑i∈Ωx(θi⊤x−ri)2. (z;θ)= 1| _x| _i∈ _x( _i x-r_i)^2. Census Data with Logistic Loss. We use the ACSEmployment task from folktables [Ding et al., 2021], where the goal is to predict employment status from demographic features. The population consists of 38,221 individuals from the 2018 Alabama census (ages 16–90), with d=16d=16 features describing age, education, marital status, etc. Each user’s data is z=(x,y)z=(x,y) where x∈ℝdx ^d (standardized to zero mean, unit variance) and y∈0,1y∈\0,1\. Each learner uses logistic regression: ℓ(z;θ)=−ylog(σ(θ⊤x))−(1−y)log(1−σ(θ⊤x)), (z;θ)=-y (σ(θ x))-(1-y) (1-σ(θ x)), where σ is the sigmoid function. The model predicts y^=[θ⊤x>0] y=1[θ x>0]. Amazon Reviews 2023 with Logistic Loss. We use the Amazon Reviews 2023 corpus and sample up to 30,000 reviews from nine product categories. Each review is represented by a d=384d=384 sentence embedding using all-MiniLM-L6-v2, and each learner performs binary sentiment classification with logistic regression. As in the Census setting, labels are binary and predictions are thresholded logistic outputs. Full preprocessing details are provided in Appendix G. User Preferences. For Census and MovieLens (m=5m=5), we induce inherent preferences π(z)π(z) via K-means clustering on user features, assigning each user to a preferred platform based on cluster membership. For Amazon (m=9m=9), preferences are determined by product category, with all reviews from a given category preferring the same learner. Evaluation. For each dataset, the train/test split is fixed once and shared across all learners; there is no validation split, since no per-run hyperparameter tuning is performed. Census and Amazon report standard binary classification accuracy on the held-out test set, while MovieLens reports masked test MSE. 6.2 Experimental Results We present results for the preference-aware scenario from Definition˜3. The results are qualitatively similar in the other scenarios from Definition˜2 as well, and are presented in Appendix˜G. Expt 1: MSGD converges to equilibria with poor global performance. Our first set of experiments validates Theorem 2. Figure 2 shows the full-population performance trajectories of individual learners on all three datasets without probing (p=0p=0) over T=4000T=4000 rounds, when initialized randomly. In all cases, the results reveal large overspecialization gaps relative to the dashed black baseline in Figure 2. Expt 2: Peer Model Probing Mitigates Overspecialization. Figure 3: Effect of probing on full-population performance (Preference-aware scenario). Left: Census final accuracy vs probing weight p. Mid: Amazon sentiment final accuracy vs probing weight p Right: MovieLens final loss vs p. In all cases, triangle markers indicate the probing learner. Here τ=0.7τ=0.7; other dataset-specific hyperparameters are given in Table 3. Figure 3 shows learner final performance at timestep T as a function of probing weight p using the offline probing budgets in Table 3; here, one learner (indicated by triangle markers) uses preference-aware probing while other learners use standard MSGD. On Census (left), the probing learner’s accuracy improves from approximately 60% at p=0p=0 to about 78% at p=0.8p=0.8, shrinking its baseline gap from roughly 18 percentage points to about 1 percentage point. The improvement is monotonic in p: even modest probing (p=0.2p=0.2) yields noticeable gains. On MovieLens (right), the effect is equally pronounced: the probing learner’s MSE loss decreases from approximately 6.2 to 3.5. Expt 3: Probing is robust to noisy source selection. Figure 4: Effect of noisy probing-source selection. Preference-aware probing routes each probe query to the preferred peer π(x)π(x) with probability 1−κ1-κ and to a random peer with probability κ. Left: Census final test accuracy vs. probing weight p. Middle: Amazon sentiment final test accuracy vs. p. Right: MovieLens final test MSE vs. p. The green learner is the probing learner; its multiple curves show different κ values. Figure 4 tests a noisy version of preference-aware probing: for each probe query, the learner routes to π(x)π(x) with probability 1−κ1-κ and to a random peer with probability κ. Across datasets, probing remains beneficial under moderate routing noise, showing that the method does not require perfect knowledge of user preferences. Expt 4: How much probing data is needed? Figure 5 studies sample efficiency by sweeping the probing dataset size n on Census, averaged over 10 random seeds. We observe substantial gains even with very small probing sets: for the probing learner with p∈0.5,1.0p∈\0.5,1.0\, final accuracy rises from about 0.680.68 at n=5n=5 to about 0.780.78 by n=50n=50, and then saturates near 0.790.79 at n=100n=100; this is a tiny fraction of the full dataset size of 38,22138,221 examples. As n increases, mean performance improves and variability across runs decreases, consistent with the finite-sample term in Theorem 4, which scales as 1/n1/ n. Figure 5: Performance of probing learner on Census as a function of n. Error bars show one standard deviation over 10 random seeds. Expt 5: Two-layer neural learners. Figure 6: Census experiments with two-layer neural learners. We replace each linear logistic learner with a two-layer ReLU MLP (d→64→1d\!→\!64\!→\!1) trained by SGD with binary cross-entropy, while keeping the Census train/test split, K-means preference clustering, induced learner rankings, and offline pseudo-label construction fixed. Left: random initialization with standard MSGD and no probing (τ=0.3,p=0τ=0.3,p=0). Right: partition-pretrained initialization with preference-aware probing by Learner 2 (τ=0.7,κ=0τ=0.7,κ=0). Shaded bands show standard error over three seeds. Figure 6 repeats the Census preference-aware experiments with two-layer ReLU MLP learners. The same qualitative pattern persists: standard MSGD overspecializes, while probing improves the underperforming learner toward the pooled MLP baseline. 7 Discussion We studied competitive dynamics in machine learning markets where users choose platforms based on inherent preferences and predictive quality. We showed that standard learning dynamics in competitive ML markets converge to overspecialized equilibria, and that peer model probing provably mitigates this failure under identifiable informational conditions. The key insight is that optimizing for observed users creates information barriers that standard dynamics cannot overcome; probing breaks these barriers, with guarantees that degrade gracefully with pseudo-label quality. Our experiments confirm that even small probing datasets suffice to close most of the gap. User Preference Modeling. Our experiments simulate user preferences via K-means clustering, which provides a controlled environment but may not capture the full complexity of real-world platform choice. Settings with explicit preference data or richer choice models (e.g., multinomial logit with heterogeneous coefficients) merit exploration. Online Probing. Our analysis considers offline probing, where pseudo-labels are collected once at initialization; this mirrors fixed-teacher distillation workflows and avoids querying peers at different stages of adaptation. Extending to online probing, where learners continuously query adapting peers throughout training, introduces co-adaptation dynamics that may lead to instabilities reminiscent of model collapse [Shumailov et al., 2024]. Characterizing when online probing converges—and whether it outperforms offline probing—is an interesting direction for future work. Convex Losses and Linear Models. Our theoretical analysis is restricted to convex losses (squared and cross-entropy) with linear predictors. The Census MLP experiment in Figure 6 suggests that the qualitative overspecialization and probing-recovery phenomena persist for simple non-convex learners, but extending the convergence and performance guarantees to deep networks remains an important open direction. References N. A. Abdullah, R. A. Rasheed, M. H. N. Nasir, and M. M. Rahman (2021) Eliciting auxiliary information for cold start user recommendation: a survey. Applied Sciences 11 (20), p. 9608. Cited by: §5.3. R. Anil, G. Pereyra, A. Passos, R. Ormandi, G. E. Dahl, and G. E. Hinton (2018) Large scale distributed neural network training through online distillation. In International Conference on Learning Representations (ICLR), Cited by: §2. Anonymous (2023) MiniLLM: knowledge distillation of large language models. arXiv preprint arXiv:2306.08543. External Links: Link Cited by: §5. J. E. Beardow (2021) Scroll, click, like, share, repeat: the algorithmic polarisation phenomenon. ANU Journal of Law & Technology 2 (1), p. 153–164. Note: Autumn 2021 issue Cited by: §1. O. Ben-Porat and M. Tennenholtz (2017) Best response regression. Advances in Neural Information Processing Systems 30. Cited by: Appendix A, Appendix A, §2. O. Ben-Porat and M. Tennenholtz (2019) Regression equilibrium. In Proceedings of the 2019 ACM Conference on Economics and Computation, p. 173–191. Cited by: Appendix A. J. Bennett and S. Lanning (2007) The Netflix prize. In Proceedings of KDD Cup and Workshop, Cited by: §5.3. V. S. Borkar (2008) Stochastic approximation: a dynamical systems viewpoint. Vol. 9, Springer. Cited by: §4.2, Lemma 11. A. Bose, M. Curmei, D. L. Jiang, J. Morgenstern, S. Dean, L. J. Ratliff, and M. Fazel (2023) Initializing services in interactive ml systems for diverse users. arXiv preprint arXiv:2312.11846. Cited by: Appendix A, §G.1, §1, §2, §6.1. Y. Cherapanamjeri, C. Daskalakis, A. Ilyas, and M. Zampetakis (2023) What makes a good fisherman? linear regression under self-selection bias. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023. External Links: Link, Document Cited by: Appendix A, §2. W. Chiang, Z. Li, Z. Lin, Y. Sheng, Z. Wu, H. Zhang, L. Zheng, S. Zhuang, Y. Zhuang, J. E. Gonzalez, I. Stoica, and E. P. Xing (2023) Vicuna: an open-source chatbot impressing GPT-4 with 90%* ChatGPT quality. Note: https://lmsys.org/blog/2023-03-30-vicuna/Accessed: 2025 Cited by: §5.3. W. Chiang, L. Zheng, Y. Sheng, A. N. Angelopoulos, T. Li, D. Li, H. Zhang, B. Zhu, M. Jordan, J. E. Gonzalez, and I. Stoica (2024) Chatbot arena: an open platform for evaluating LLMs by human preference. In Proceedings of the 41st International Conference on Machine Learning, External Links: Link Cited by: §5.3. F. Cinus, M. Minici, C. Monti, and F. Bonchi (2022) The effect of people recommenders on echo chambers and polarization. In Proceedings of the Sixteenth International AAAI Conference on Web and Social Media (ICWSM ’22), p. 90–101. Note: ICWSM 2022 Cited by: §1. S. Dean, M. Curmei, L. Ratliff, J. Morgenstern, and M. Fazel (2024) Emergent specialization from participation dynamics and multi-learner retraining. In International Conference on Artificial Intelligence and Statistics, p. 343–351. Cited by: Appendix A, §1, §2, §3.3. F. Ding, M. Hardt, J. Miller, and L. Schmidt (2021) Retiring adult: new datasets for fair machine learning. Advances in neural information processing systems 34, p. 6478–6490. Cited by: §G.1, §6.1. T. Ginart, E. Zhang, Y. Kwon, and J. Zou (2021) Competing ai: how does competition feedback affect machine learning?. In International Conference on Artificial Intelligence and Statistics, p. 1693–1701. Cited by: Appendix A, §1, §2. A. Góis, M. Mofakhami, F. P. Santos, G. Gidel, and S. Lacoste-Julien (2025) Performative prediction on games and mechanism design. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 258, p. 1855–1863. Cited by: §2. P. M. Guadagni and J. D. Little (1983) A logit model of brand choice calibrated on scanner data. Marketing Science 2 (3), p. 203–238. Cited by: §5.3. A. Gudibande, E. Wallace, C. Snell, X. Geng, H. Liu, P. Abbeel, S. Levine, and D. Song (2024) The false promise of imitating proprietary LLMs. In International Conference on Learning Representations (ICLR), Cited by: §5.3. M. Hardt, N. Megiddo, C. Papadimitriou, and M. Wootters (2016) Strategic classification. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, p. 111–122. Cited by: §2. F. M. Harper and J. A. Konstan (2015) The movielens datasets: history and context. Acm transactions on interactive intelligent systems (tiis) 5 (4), p. 1–19. Cited by: §G.1, §6.1. K. Harris, C. Podimata, and Z. S. Wu (2023) Strategic apple tasting. Adv. Neural Inf. Process. Syst. abs/2306.06250. Cited by: Appendix A, §2. T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang (2018) Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, p. 1929–1938. Cited by: Appendix A, §2. G. Hinton, O. Vinyals, and J. Dean (2015) Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531. External Links: Link Cited by: §1, §2, §5. H. Huang, B. Zhao, H. Zhao, Z. Zhuang, Z. Wang, X. Yao, X. Wang, H. Jin, and X. Fu (2018) A cross-platform consumer behavior analysis of large-scale mobile shopping data. In Proceedings of the 2018 World Wide Web Conference, W ’18, Lyon, France, p. 1785–1794. External Links: Document, Link Cited by: §5.3. R. Interian, R. G. Marzo, I. Mendoza, and C. C. Ribeiro (2022) Network polarization, filter bubbles, and echo chambers: an annotated review of measures and reduction methods. arXiv preprint. Note: arXiv:2207.13799 Cited by: §1. R. Irani-Kermani, E. C. Jaenicke, and A. Mirshani (2023) Accommodating heterogeneity in brand loyalty estimation: application to the U.S. beer retail market. Journal of Marketing Analytics 11 (4), p. 820–835. External Links: Document, Link Cited by: §5.3. M. Jagadeesan, M. I. Jordan, and N. Haghtalab (2023a) Competition, alignment, and equilibria in digital marketplaces. Proceedings of the AAAI Conference on Artificial Intelligence 37 (5), p. 5689–5696. External Links: Document Cited by: Appendix A. M. Jagadeesan, M. I. Jordan, J. Steinhardt, and N. Haghtalab (2023b) Improved bayes risk can yield reduced social welfare under competition. arXiv preprint arXiv:2306.14670. Cited by: Appendix A. H. James, C. Nagpal, K. A. Heller, and B. Ustun (2023) Participatory personalization in classification. In Thirty-seventh Conference on Neural Information Processing Systems, Cited by: Appendix A, §2. J. Jiang, X. Ren, and E. Ferrara (2021) Social media polarization and echo chambers in the context of covid-19: case study. JMIRx med 2 (3), p. e29570. External Links: Document Cited by: §1. Y. Kwon, A. Ginart, and J. Zou (2022) Competition over data: how does data purchase affect users?. arXiv preprint arXiv:2201.10774. Cited by: Appendix A, §2. Q. Li, C. Yau, and H. Wai (2022) Multi-agent performative prediction with greedy deployment and consensus seeking agents. In Advances in Neural Information Processing Systems, Vol. 35, p. 38449–38460. Cited by: §2. Y. Li, Y. Gu, L. Dong, D. Wang, Y. Cheng, and F. Wei (2024) Direct preference knowledge distillation for large language models. arXiv preprint arXiv:2406.19774. External Links: Link Cited by: §5. P. Liang, R. Bommasani, T. Lee, D. Tsipras, D. Soylu, M. Yasunaga, Y. Zhang, D. Narayanan, Y. Wu, A. Kumar, B. Newman, B. Yuan, B. Yan, C. Zhang, C. Cosgrove, C. D. Manning, C. Ré, D. Acosta-Navas, D. A. Hudson, E. Zelikman, E. Durmus, F. Ladhak, F. Rong, H. Ren, H. Yao, J. Wang, K. Santhanam, L. Orr, L. Zheng, M. Yüksekgönül, M. Suzgun, N. Kim, N. Guha, N. Chatterji, O. Khessin, P. Henderson, Q. Huang, R. Chi, S. M. Xie, S. Santurkar, S. Ganguli, T. Hashimoto, T. Icard, T. Zhang, V. Chandu, W. Wang, X. Xie, X. Zhang, Y. Wang, Y. Zhou, and Y. Koreeda (2023) Holistic evaluation of language models. Transactions on Machine Learning Research. External Links: Link Cited by: §5.3. E. Mazumdar, L. J. Ratliff, and S. S. Sastry (2020) On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science 2 (1), p. 103–131. External Links: Document, Link Cited by: §4.2. J. Miller, J. C. Perdomo, and T. Zrnic (2021) Outside the echo chamber: optimizing the performative risk. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 7710–7720. Cited by: §2. A. Narang, E. Faulkner, D. Drusvyatskiy, M. Fazel, and L. J. Ratliff (2023) Multiplayer performative prediction: learning in decision-dependent games. Journal of Machine Learning Research 24 (202), p. 1–56. Cited by: §2. R. S. Olson, W. La Cava, P. Orzechowski, R. J. Urbanowicz, and J. H. Moore (2017) PMLB: a large benchmark suite for machine learning evaluation and comparison. BioData Mining 10 (1), p. 36. Cited by: §5.3. J. Perdomo, T. Zrnic, C. Mendler-Dünner, and M. Hardt (2020) Performative prediction. In International Conference on Machine Learning, p. 7599–7609. Cited by: §2. G. Piliouras and F. Yu (2023) Multi-agent performative prediction: from global stability and optimality to chaos. In Proceedings of the 24th ACM Conference on Economics and Computation, p. 1047–1048. Cited by: §2. R. Raab, R. Boczar, M. Fazel, and Y. Liu (2024) Fair participation via sequential policies. In AAAI Conference on Artificial Intelligence, Cited by: §2. O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei (2015) ImageNet large scale visual recognition challenge. International Journal of Computer Vision 115 (3), p. 211–252. Cited by: §5.3. H.J. Scudder (1965) Probability of error of some adaptive pattern-recognition machines. IEEE Transactions on Information Theory 11 (3), p. 363–371. Cited by: §2. E. Shekhtman and S. Dean (2024) Strategic usage in a multi-learner setting. In International Conference on Artificial Intelligence and Statistics, Cited by: Appendix A, §1. I. Shumailov, Z. Shumaylov, Y. Zhao, N. Papernot, R. Anderson, and Y. Gal (2024) AI models collapse when trained on recursively generated data. Nature 631 (8022), p. 755–759. Cited by: §7. J. Su and S. Dean (2024) Learning from streaming data when users choose. arXiv [cs.LG]. Cited by: Appendix A, §D.2, §G.1, item 1, §1, §2, §3.2, §3.3, §4.1, §4.1, §4.1, §4.2, §4.2, §4, §5, §6.1, Algorithm 1. S. Tan, W. L. Tam, Y. Wang, W. Gong, Y. Yang, H. Tang, K. He, J. Liu, J. Wang, S. Zhao, P. Zhang, and J. Tang (2023) GKD: a general knowledge distillation framework for large-scale pre-trained language model. arXiv preprint arXiv:2306.06629. External Links: Link Cited by: §5. R. Taori, I. Gulrajani, T. Zhang, Y. Dubois, X. Li, C. Guestrin, P. Liang, and T. B. Hashimoto (2023) Stanford Alpaca: an instruction-following LLaMA model. Note: https://github.com/tatsu-lab/stanford_alpacaAccessed: 2025 Cited by: §5.3. G. Wang, I. Panageas, G. Piliouras, and F. Yu (2025) Last-iterate convergence for symmetric, general-sum, 2×22× 2 games under the exponential weights dynamic. arXiv preprint arXiv:2502.08063. Cited by: §2. X. Wang, C. Yau, and H. T. Wai (2023) Network effects in performative prediction games. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 36514–36540. Cited by: §2. J. Werner (2025) Did deepseek copy off of openai? and what is distillation?. Forbes. External Links: Link Cited by: §1, §5.1, §5. X. Xu, M. Li, C. Tao, T. Shen, R. Cheng, J. Li, C. Xu, D. Tao, and T. Zhou (2024) A survey on knowledge distillation of large language models. arXiv preprint arXiv:2402.13116. External Links: Link Cited by: §5. C. Yang, W. Lu, Y. Zhu, Y. Wang, Q. Chen, C. Gao, B. Yan, and Y. Chen (2024) Survey on knowledge distillation for large language models: methods, evaluation, and application. arXiv preprint arXiv:2407.01885. External Links: Link Cited by: §5. D. Yarowsky (1995) Unsupervised word sense disambiguation rivaling supervised methods. In 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, Massachusetts, USA, p. 189–196. External Links: Document Cited by: §2. X. Zhang, M. Khaliligarekani, C. Tekin, et al. (2019) Group retention when using machine learning in sequential decision making: the interplay between user dynamics and fairness. Advances in Neural Information Processing Systems 32. Cited by: Appendix A, §2. Y. Zhang, T. Xiang, T. M. Hospedales, and H. Lu (2018) Deep mutual learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), p. 4320–4328. Cited by: §2. Z. Zhu, R. Wan, Y. Cho, H. Luo, Z. Yang, and Z. Wang (2023) Online performative gradient descent for learning nash equilibria in decision-dependent games. In Advances in Neural Information Processing Systems, Vol. 36. Cited by: §2. Appendix A Extended Related Work This section provides detailed comparisons with related work summarized in Section 1.1 of the main paper. Single-learner user agency. A body of work studies learning dynamics when users are treated as independent agents rather than passive data points. Hashimoto et al. [2018] show that empirical risk minimization can cause minority groups to opt out, creating a feedback loop that further degrades minority performance. Zhang et al. [2019] study a related dynamic where underrepresented groups receive worse predictions, leading to further data scarcity. James et al. [2023] analyze participatory data collection where users choose whether to contribute data. Ben-Porat and Tennenholtz [2017] study best-response dynamics in strategic classification. Cherapanamjeri et al. [2023] and Harris et al. [2023] study settings where data quality or availability depends on the learner’s past performance. We build on this perspective in the multi-learner setting, where inter-learner interactions create additional feedback dynamics. Multi-learner competition and user choice. Several works study multi-learner user-choice settings with explicitly strategic users who optimize their own utility functions [Shekhtman and Dean, 2024; Ben-Porat and Tennenholtz, 2017, 2019; Jagadeesan et al., 2023a, b]. Ginart et al. [2021] provide both empirical and theoretical analysis of how competition drives specialization: their Theorems 4.1–4.3 establish risk ratio bounds showing that competing predictors perform worse on the general population than a single predictor would. Their analysis considers batch retraining dynamics and characterizes the existence of performance gaps due to competition. We complement this by analyzing streaming gradient-based dynamics, proving that such dynamics converge to overspecialized equilibria (Theorem 2), and proposing probing as a mitigation. Kwon et al. [2022] study a related setting where learners may purchase user data, providing primarily empirical analysis of the resulting market dynamics. Gradient-based dynamics in choice-driven settings. Most closely related to our work, Dean et al. [2024] and Su and Dean [2024] analyze gradient-based dynamics in choice-driven settings. Su and Dean [2024] introduce the MSGD algorithm and prove convergence to stationary points of an aggregate loss across learners. We build directly on their framework: our Algorithm 1 adapts MSGD to our user selection rule (Definition 1), and our potential function (Equation 1) extends theirs. Our Theorem 1 provides an alternate proof of their convergence result using stochastic approximation techniques, which we believe better illuminates the underlying dynamics. Beyond convergence, we analyze generalization to users outside each learner’s observed population—a consideration absent from prior work—and introduce peer probing as a mechanism to restore global competence. Bose et al. [2023] propose intelligent initialization schemes to improve outcomes in similar settings, but also focus on the sum of all local losses on the observed distribution. Appendix B Terminology and Preliminary Results B.1 Dynamical systems terminology This subsection records standard definitions underlying terms such as “invariant set” and “internally chain transitive” in Lemma˜11. Let x˙(t)=h(x(t)) x(t)=h(x(t)) be an ODE with locally Lipschitz h, so that solutions are unique. Let ϕt(x) _t(x) denote the state at time t≥0t≥ 0 of the solution initialized at x at time 0. Definition 4 (Invariant set). A set A⊆ℝdA ^d is (forward) invariant for the ODE if ϕt(x)∈A _t(x)∈ A for all x∈Ax∈ A and all t≥0t≥ 0. Definition 5 ((ε,T)( ,T)-chain). Fix ε>0 >0 and T>0T>0. An (ε,T)( ,T)-chain in A from x to y is a finite sequence of points x=x0,x1,…,xk=yx=x_0,x_1,…,x_k=y in A and times t1,…,tk≥Tt_1,…,t_k≥ T such that ‖ϕti(xi−1)−xi‖<εfor all i∈1,…,k.\| _t_i(x_i-1)-x_i\|< all i∈\1,…,k\. Definition 6 (Internally chain transitive). A compact invariant set A is internally chain transitive if for every x,y∈Ax,y∈ A and every ε>0 >0, T>0T>0, there exists an (ε,T)( ,T)-chain in A from x to y. B.2 Regularity of Squared and Cross Entropy Losses Lemma 4 (Regularity of the squared‐error loss). Let ⊂ℝdX ^d, ⊂ℝY , W⊂ℝdW ^d be compact. Write ℓ(x,y;θ)=(y−x⊤θ)2,B=maxθ∈W‖θ‖. (x,y;θ)\;=\; (y-x θ )^2, B= _θ∈ W\|θ\|. Then for all (x,y)∈×(x,y) ×Y and all θ1,θ2∈W _1, _2∈ W: (i) ℓ is nonnegative, C∞C^∞ in θ, convex, and β–smooth with β=2R2β=2R^2. (i) ℓ is locally Lipschitz on W: |ℓ(x,y;θ1)−ℓ(x,y;θ2)|≤LW‖θ1−θ2‖,LW=R(2|y|+2RB). | (x,y; _1)- (x,y; _2) |≤ L_W\,\| _1- _2\|, L_W=R (2|y|+2RB ). (i) The Hessian is constant in θ, so ‖∇2ℓ(θ1)−∇2ℓ(θ2)‖=0\|∇^2 ( _1)-∇^2 ( _2)\|=0 (i.e. γℓ=0 _ =0). Proof. (i) One computes ∇θℓ=−2x(y−x⊤θ) _θ =-2\,x (y-x θ ) and ∇θ2ℓ=2xx⊤⪰0∇^2_θ =2\,x\,x 0. Hence ℓ≥0 ≥ 0, is C∞C^∞, convex, and ‖∇ℓ(θ1)−∇ℓ(θ2)‖≤2R2‖θ1−θ2‖\|∇ ( _1)-∇ ( _2)\|≤ 2R^2\| _1- _2\|. (i) Observe ℓ(θ1)−ℓ(θ2)=(y−x⊤θ1)2−(y−x⊤θ2)2=x⊤(θ2−θ1)(2y−x⊤(θ1+θ2)). ( _1)- ( _2)= (y-x _1 )^2- (y-x _2 )^2=x ( _2- _1)\; (2y-x ( _1+ _2) ). Since ‖θi‖≤B\| _i\|≤ B, |x⊤(θ2−θ1)|≤R‖θ1−θ2‖ x ( _2- _1) ≤ R\| _1- _2\| and |2y−x⊤(θ1+θ2)|≤2|y|+2RB |2y-x ( _1+ _2) |≤ 2|y|+2RB, giving the stated bound. (i) Because ∇θ2ℓ≡2xx⊤∇^2_θ ≡ 2\,x\,x is independent of θ, its difference vanishes. ∎ Lemma 5. Under Assumption 1, for all z∈z the loss ℓ(z,⋅) (z,·) is non-negative, convex, differentiable, locally Lipschitz and βℓ _ -smooth with βℓ=2R2for both the squared loss and cross-entropy loss. _ =2R^2 both the squared loss and cross-entropy loss. Moreover, let ℛ(θ)=z∼[ℓ(z,θ)],θ∗=argminθℛ(θ),ϵ=ℛ(θ∗).R(θ)= *E_z [ (z,θ)], θ^*= _θR(θ), ε=R(θ^*). Then for any θ with ‖θ−θ∗‖≤γ\|θ-θ^*\|≤γ, the following quadratic upper bound holds: ℛ(θ)≤ϵ+βℓ2‖θ−θ∗‖2≤ϵ+R2γ2.R(θ)\;≤\;ε+ _ 2\,\|θ-θ^*\|^2\;≤\;ε+R^2\,γ^2. Proof. The first part (non-negativity, convexity, differentiability, local Lipschitzness, and smoothness) follows directly by applying Lemmas 4 and 6 under Assumption 1, which together show each ℓ(z,θ) (z,θ) is βℓ _ -smooth with βℓ=2R2 _ =2R^2. Since f(θ)=z[ℓ(z,θ)]f(θ)= *E_z[ (z,θ)], differentiability and smoothness carry over to f, and we have ‖∇f(θ)−∇f(θ∗)‖≤βℓ‖θ−θ∗‖.\|∇ f(θ)-∇ f(θ^*)\|≤ _ \,\|θ-θ^*\|. At the minimizer θ∗θ^*, ∇f(θ∗)=0∇ f(θ^*)=0. Hence for any θ with ‖θ−θ∗‖≤γ\|θ-θ^*\|≤γ, the gradient satisfies ‖∇f(θ)‖≤βℓ‖θ−θ∗‖≤βℓγ.\|∇ f(θ)\|≤ _ \,\|θ-θ^*\|≤ _ \,γ. Applying the standard smoothness inequality (second-order Taylor upper bound) around θ∗θ^*, f(θ)≤f(θ∗)+⟨∇f(θ∗),θ−θ∗⟩+βℓ2‖θ−θ∗‖2=ϵ+βℓ2‖θ−θ∗‖2,f(θ)≤ f(θ^*)+ ∇ f(θ^*),\,θ-θ^* + _ 2\,\|θ-θ^*\|^2=ε+ _ 2\,\|θ-θ^*\|^2, where we used ∇f(θ∗)=0∇ f(θ^*)=0 and f(θ∗)=ϵf(θ^*)=ε. Finally, substituting βℓ=2R2 _ =2R^2 gives f(θ)≤ϵ+R2‖θ−θ∗‖2≤ϵ+R2γ2,f(θ)≤ε+R^2\,\|θ-θ^*\|^2≤ε+R^2\,γ^2, completing the proof. ∎ Lemma 6 (Regularity of the multiclass cross‐entropy loss). Let ⊂ℝdX ^d, =1,…,KY=\1,…,K\, W⊂ℝK×dW ^K× d compact, and let ‖x‖≤R\|x\|≤ R for all x∈x . Define for (x,y)∈×(x,y) ×Y and Θ=(θ1,…,θK)∈W =( _1,…, _K)∈ W ℓ(x,y;Θ)=−logexp(θy⊤x)∑k=1Kexp(θk⊤x). (x,y; )\;=\;- ( _y x) _k=1^K ( _k x). Then for all x,y,Θ1,Θ2x,y, _1, _2 as above: (i) ℓ is nonnegative, C∞C^∞ in Θ , convex, and β–smooth with β=R2.β\;=\;R^2. (i) ℓ is (locally) Lipschitz on W: |ℓ(x,y;Θ1)−ℓ(x,y;Θ2)|≤L‖Θ1−Θ2‖,L=2R. | (x,y; _1)- (x,y; _2) |\;≤\;L\,\| _1- _2\|, L= 2\,R. Proof. The proofs of each subpart are as follows: (i) Let p=softmax(Θx)∈ΔK−1p=softmax( \,x)∈ ^K-1. One checks ∇Θℓ=(p−ey)x⊤,∇Θ2ℓ=[diag(p)−pp⊤]⊗(xx⊤). _ =(p-e_y)\,x , ∇^2_ = [diag(p)-p\,p ]\; \; (x\,x ). Since diag(p)−pp⊤⪰0diag(p)-p\,p 0 ℓ≥0 ≥ 0, is C∞C^∞ and convex, and ‖∇Θ2ℓ‖≤‖x‖2λmax(diag(p)−pp⊤)≤R2,\|∇^2_ \|\;≤\;\|x\|^2\; _ (diag(p)-p\,p )\;≤\;R^2, it follows that ℓ is β–smooth with β=R2β=R^2. (i) By the mean‐value theorem, |ℓ(Θ1)−ℓ(Θ2)|≤supΘ∈W‖∇Θℓ‖‖Θ1−Θ2‖. | ( _1)- ( _2) |\;≤\; _ ∈ W\| _ \|\;\| _1- _2\|. But ‖∇Θℓ‖=‖p−ey‖‖x‖≤2R,\| _ \|=\|p-e_y\|\;\|x\|\;≤\; 2\,R, giving the claimed Lipschitz constant L=2RL= 2\,R. ∎ Lemma 7. Let hθ∈Θ\h_θ\_θ∈ be the family of softmax classifiers mapping x∈ℝdx ^d to a distribution over C classes, hθ(x)c=ex⊤θc∑j=1Cex⊤θj.h_θ(x)_c= e^x _c _j=1^Ce^x _j. Assume: (i) ‖x‖2≤R\|x\|_2≤ R for all x in the support of P. (i) There exists α>0α>0 such that for all x,θ,cx,θ,c, we have hθ(x)c≥αh_θ(x)_c≥α. (i) θ,θ∗θ,θ^* lie in a convex set Θ⊂ℝC×d ^C× d. Then the mapping θ↦hθ(x)θ h_θ(x) is Lipschitz in the ℓ1 _1–norm: for all θ,θ∗∈Θθ,θ^*∈ , ‖hθ(x)−hθ∗(x)‖1≤Lh‖θ−θ∗‖2,Lh=R2(1−α).\|h_θ(x)-h_θ^*(x)\|_1\;≤\;L_h\,\|θ-θ^*\|_2, L_h=R 2\,(1-α). Proof. By the multivariate mean‐value theorem, there exists θ¯ θ on the line segment between θ∗θ^* and θ such that hθ(x)−hθ∗(x)=Dθh(θ¯;x)(θ−θ∗),h_θ(x)-h_θ^*(x)=D_θh( θ;x)\; (θ-θ^* ), where Dθh(θ¯;x)∈ℝC×(Cd)D_θh( θ;x) ^C×(Cd) is the Jacobian w.r.t. all parameters. Write its ccth row as the gradient vector ∇θhc(θ¯;x) _θh_c( θ;x). A direct calculation shows for each class c and each block k: ∇θkhc(θ¯;x)=hc(c=k−hk)x⟹‖∇θhc(θ¯;x)‖2≤‖x‖2hc(1−hc)2+∑k≠chk2. _ _k\,h_c( θ;x)=h_c (1\c=k\-h_k )\,x \| _θh_c( θ;x)\|_2≤\|x\|_2\;h_c\; (1-h_c)^2+ _k≠ ch_k^2. Using ∑khk=1 _kh_k=1, hk≤1h_k≤ 1 for each k, and the lower‐bound hc≥αh_c≥α, one checks (1−hc)2+∑k≠chk2≤(1−hc)2+(1−hc)=(1−hc)(2−hc)≤2(1−hc)≤2(1−α),(1-h_c)^2+ _k≠ ch_k^2≤(1-h_c)^2+(1-h_c)=(1-h_c)(2-h_c)≤ 2\,(1-h_c)≤ 2\,(1-α), where the first inequality uses ∑k≠chk2≤∑k≠chk=1−hc _k≠ ch_k^2≤ _k≠ ch_k=1-h_c. Hence ‖∇θhc(θ¯;x)‖2≤Rhc2(1−α).\| _θh_c( θ;x)\|_2≤ R\,h_c\, 2\,(1-α). Therefore the operator norm from ℓ2 _2 to ℓ1 _1 satisfies ‖Dθh(θ¯;x)‖2→1=∑c=1C‖∇θhc(θ¯;x)‖2≤R2(1−α)∑c=1Chc=R2(1−α).\|D_θh( θ;x)\|_2→ 1\;=\; _c=1^C\| _θh_c( θ;x)\|_2\;≤\;R 2(1-α) _c=1^Ch_c=R 2(1-α). Putting these together gives ‖hθ(x)−hθ∗(x)‖1≤‖Dθh(θ¯;x)‖2→1‖θ−θ∗‖2≤Lh‖θ−θ∗‖2,\|h_θ(x)-h_θ^*(x)\|_1≤\|D_θh( θ;x)\|_2→ 1\,\|θ-θ^*\|_2≤ L_h\,\|θ-θ^*\|_2, as claimed. ∎ Lemma 8. Under Assumption 1, for all z∈z , the loss ℓ(z,⋅) (z,·) is non-negative, convex, differentiable, locally Lipschitz, and βℓ _ -smooth. Proof. The result follows by applying Lemmas 4 and 6 with |x|≤R|x|≤ R and choosing βℓ=max2R2,R2=2R2 _ = 2R^2,R^2=2R^2. Each loss is nonnegative, convex, differentiable, locally Lipschitz, and smooth under these bounds. ∎ Appendix C Bad Outcome Notation Recall the potential function from the main text: f(Θ)=∑i=1m(ταiz∼i[ℓ(z,θi)]+(1−τ)ai(Θ)z∼i(Θ)[ℓ(z,θi)])f( )= _i=1^m (τ _i *E_z _i[ (z, _i)]+(1-τ)a_i( ) *E_z _i( )[ (z, _i)] ) (4) From Lemma 1, we have that the MSGD iterates converge almost surely to the set ∇f(Θ)=0\∇ f( )=0\. Additionally, for learner i∈[m]i∈[m], define θ¯i θ_i as the solution that each learner would choose if they trained independently on the subpopulation of users who rank them highest: θ¯i=argminθix∼iℓ(x,θi) θ_i= _ _i *E_x _i (x, _i) (5) Example 1. Specify the family of instances bad(τ,C)G_bad(τ,C) as follows. 1. Distribution P: is defined as a mixture of subpopulations. =α1+(1−α)2P= _1+(1-α)P_2. Here, 1,2\P_1,P_2\ are 22 subpopulations. For either subpopulation, the covariates are generated from the zero mean and unit-variance uniform distribution: x∼Unif([−3,3])for(x,y)∼i, x ([- 3, 3]) (x,y) _i, (6) For each subpopulation, the response variable is generated as: y y =Cxfor(x,y)∼1 =Cx (x,y) _1 (7) y y =−xfor(x,y)∼2 =-x (x,y) _2 (8) 2. Loss function: ℓ(x,y,θ)=(y−θTx)2 (x,y,θ)=(y-θ^Tx)^2 is the squared loss 3. Ranking π(z)=iπ(z)=i for (x,y)∼i(x,y) _i. Lemma 9. Consider the 1‑D bad‑outcome family in Example 1 with mixture weight α∈(0,1)α∈(0,1) and slope parameter C>1C>1, and let ℛ(θ)=(x,y)∼[(y−θx)2]R(θ)= *E_(x,y) [(y-θ x)^2]. (i) The least‑squares predictor on the full mixture, θ⋆=αC−(1−α)θ =α C-(1-α), satisfies ℛ(θ⋆)=α(1−α)(C+1)2.R(θ )=α(1-α)(C+1)^2. (i) The specialist trained on 1P_1 is θ¯1=C θ_1=C, and its mixture risk is ℛ(θ¯1)=(1−α)(C+1)2.R( θ_1)\,=\,(1-α)(C+1)^2. (i) The specialist trained on 2P_2 is θ¯2=−1 θ_2=-1, and its mixture risk is ℛ(θ¯2)=α(C+1)2.R( θ_2)\,=\,α\,(C+1)^2. Proof. We have that [x]=0 *E[x]=0 and [x2]=1 *E[x^2]=1, so that the squared risk reduces to (β−θ)2(β-θ)^2 when the true slope is β. (i) Global compromise. On the mixture, the conditional label is linear: y=βxy=β x with β=αC+(1−α)(−1)=αC−(1−α)β=α C+(1-α)(-1)=α C-(1-α). For squared loss with [x]=0 *E[x]=0 and [x2]=1 *E[x^2]=1, the population least‑squares minimizer is the regression slope, so θ⋆=βθ =β. The corresponding risk is ℛ(θ⋆)=α(C−β)2+(1−α)(−1−β)2=α(1−α)(C+1)2.R(θ )=α\,(C-β)^2+(1-α)\,(-1-β)^2=α(1-α)(C+1)^2. (i) Specialist for 1P_1. Training least squares on 1P_1 alone yields θ¯1=C θ_1=C since [xy]=C *E[x\,y]=C and [x2]=1 *E[x^2]=1. The mixture risk is ℛ(θ¯1)=α(C−C)2+(1−α)(−1−C)2=(1−α)(C+1)2.R( θ_1)=α\,(C-C)^2+(1-α)\,(-1-C)^2=(1-α)(C+1)^2. (i) Specialist for 2P_2. Training least squares on 2P_2 gives θ¯2=−1 θ_2=-1 (its true slope). The mixture risk is ℛ(θ¯2)=α(C+1)2+(1−α)(−1−(−1))2=α(C+1)2.R( θ_2)=α\,(C+1)^2+(1-α)\,(-1-(-1))^2=α\,(C+1)^2. ∎ Lemma 10. Let (θ~1,θ~2)∈∇f(Θ)=0( θ_1, θ_2)∈\∇ f( )=0\ be a stationary point of f(Θ)f( ) (Equation 1). Then, under the assumption that τ≥12τ≥ 12, it must be true that 1(θ~1,θ~2)=1D_1( θ_1, θ_2)=P_1 and 2(θ~1,θ~2)=2D_2( θ_1, θ_2)=P_2. Proof. The proof proceeds by considering the decisions of the loss-minimizing users, and shows that the stationary point condition implies the conditions on i(Θ)D_i( ) in the lemma statement. Consider any (x,y)(x,y) from 1P_1. For any θ∈ℝθ , we have that ℓ(x,y,θ)=(Cx−θx)2=(C−θ)2x2. (x,y,θ)=(Cx-θ x)^2=(C-θ)^2x^2. (9) Hence, argmini∈1,2ℓ(x,y,θi)=argmini∈1,2(C−θi)2x2=argmini∈1,2|C−θi|. _i∈\1,2\ (x,y, _i)= _i∈\1,2\(C- _i)^2x^2= _i∈\1,2\|C- _i|. Thus every loss-minimizing user in 1P_1 picks the learner whose parameter is closer to C: M(z;Θ)=argmini∈1,2|C−θi|,z∈1.M(z; )\,=\, _i∈\1,2\|C- _i|, z _1. Likewise, every loss-minimizing user in 2P_2 picks the learner whose parameter is closer to −1-1: M(z;Θ)=argmini∈1,2|−1−θi|,z∈2.M(z; )\,=\, _i∈\1,2\|-1- _i|, z _2. Hence, within each subpopulation iP_i, all loss-minimizing users make the same choice. Consequently, for any Θ , the observed-data distributions i(Θ)D_i( ) can only take one of the following four forms: 1. 1(Θ)=D_1( )=P and 2(Θ)D_2( ) has zero mass under P 2. 1(Θ)D_1( ) has zero mass under P and 2(Θ)=D_2( )=P 3. 1(Θ)=2D_1( )=P_2 and 2(Θ)=1D_2( )=P_1 4. 1(Θ)=1D_1( )=P_1 and 2(Θ)=2D_2( )=P_2 For any stationary point (θ~1,θ~2)( θ_1, θ_2), we consider each case separately and show that all cases other than the last one lead to a contradiction. Case 1: In this case, the second learner observes only negative labels, and the first observes a mix of both positive and negative labels. Hence, it should be intuitively true that θ~1>θ~2>−1 θ_1> θ_2>-1. This would lead to a contradiction since this would imply that users from 2P_2 would strictly prefer the second learner over the first one. Now, we can verify this formally. Define the total probability masses seen by each learner M1 M_1 =τα+(1−τ)α+(1−τ)(1−α)=α+(1−τ)(1−α), =τ\,α\;+\;(1-τ)\,α\;+\;(1-τ)(1-α)\;=\;α\;+\;(1-τ)(1-α), (10) M2 M_2 =τ(1−α). =τ\,(1-α). (11) The stationary conditions are given by θ~1 θ_1 =argminθ1ταP1[(y−θ1x)2]+(1−τ)αP1[(y−θ1x)2]+(1−τ)(1−α)P2[(y−θ1x)2], = _ _1τ\,α *E_P_1 [(y- _1\,x)^2 ]+(1-τ)\,α *E_P_1 [(y- _1\,x)^2 ]+(1-τ)(1-α) *E_P_2 [(y- _1\,x)^2 ], (12) θ~2 θ_2 =argminθ2τ(1−α)P2[(y−θ2x)2]. = _ _2τ\,(1-α) *E_P_2 [(y- _2\,x)^2 ]. (13) We can solve these optimization problems in closed form: θ~1 θ_1 =αC−(1−τ)(1−α)M1, = α\,C\;-\;(1-τ)(1-α)M_1, (14) θ~2 θ_2 =−1. =-1. (15) Now, θ~1−θ~2=θ~1+1=α(C+1)M1>0, θ_1- θ_2= θ_1+1= α\,(C+1)M_1>0, which holds for every τ∈[0,1]τ∈[0,1] since α>0α>0 and C>0C>0. Since θ~2=−1 θ_2=-1 and θ~1>−1 θ_1>-1, 2P_2 users would strictly prefer learner 2 over learner 1, leading to a contradiction. Case 2: In this case, the first learner observes only positive labels, and the second observes a mix of both positive and negative labels. Hence, it is easy to verify using a similar procedure as the previous case that C>θ~1>θ~2C> θ_1> θ_2, which would lead to a contradiction since 1P_1 users would strictly prefer learner 1. Case 3: We follow a similar argument as in Case 1. Define the total probability masses seen by each learner M1 M_1 =τα+(1−τ)(1−α), =τ\,α\;+\;(1-τ)(1-α), (16) M2 M_2 =τ(1−α)+(1−τ)α. =τ\,(1-α)\;+\;(1-τ)\,α. (17) The stationary points in this case are given by θ~1=ταC−(1−τ)(1−α)τα+(1−τ)(1−α),θ~2=(1−τ)αC−τ(1−α)(1−τ)α+τ(1−α). θ_1\;=\; τ\,α\,C\;-\;(1-τ)(1-α)τ\,α\;+\;(1-τ)(1-α), θ_2\;=\; (1-τ)\,α\,C\;-\;τ(1-α)(1-τ)\,α\;+\;τ(1-α). It is easy to verify that both θ~1 θ_1 and θ~2 θ_2 are greater than −1-1. Hence, the distance from −1-1 is given by d1 d_1 =|θ~1−(−1)|=τα(C+1)τα+(1−τ)(1−α), = | θ_1-(-1) |= τ\,α\,(C+1)τ\,α\;+\;(1-τ)(1-α), d2 d_2 =|θ~2−(−1)|=(1−τ)α(C+1)(1−τ)α+τ(1−α). = | θ_2-(-1) |= (1-τ)\,α\,(C+1)(1-τ)\,α\;+\;τ(1-α). A straightforward comparison gives d1>d2⟺τM2>(1−τ)M1⟺(1−α)(2τ−1)>0⟺τ>12.d_1>d_2\; \;τ\,M_2>(1-τ)\,M_1\; \;(1-α)\,(2τ-1)>0\; \;τ> 12. Therefore, whenever τ>12τ> 12, the free users from 2P_2 strictly prefer learner 2 over learner 1. This contradicts the Case 3 hypothesis that 1(Θ)=2D_1( )=P_2. Hence Case 3 cannot be a stationary point when τ>1/2τ>1/2. Having ruled out Cases 1–3, only the fourth configuration remains, completing the proof. ∎ See 2 Proof. The proof follows by considering Example 1. Part (i) The proof follows from Lemma 9. Choosing α=ϵ(C+1)2α= ε(C+1)^2 satisfies the condition. Characterizing the stationary points From Lemma 1, we have that the MSGD iterates converge almost surely to the set ∇f(Θ)=0\∇ f( )=0\. By Lemma 10, we have that (θ~1,θ~2)∈∇f(Θ)=0( θ_1, θ_2)∈\∇ f( )=0\ if and only if 1(θ~1,θ~2)=1D_1( θ_1, θ_2)=P_1 and 2(θ~1,θ~2)=2D_2( θ_1, θ_2)=P_2. Hence, any stationary point must satisfy θ~1=argminθ∈ℝαz∼1[ℓ(z,θ)] θ_1= _θ α *E_z _1[ (z,θ)] and θ~2=argminθ∈ℝ(1−α)z∼2[ℓ(z,θ)] θ_2= _θ (1-α) *E_z _2[ (z,θ)] Clearly, (θ¯1,θ¯2)( θ_1, θ_2) is the unique solution to these equations, and MSGD must converge to this point almost surely. Characterizing the loss From Lemma 9, at the stationary point we have θ¯1=C θ_1=C and θ¯2=−1 θ_2=-1, so the mixture risks are ℛ(θ¯1)=(1−α)(C+1)2,ℛ(θ¯2)=α(C+1)2.R( θ_1)=(1-α)(C+1)^2, ( θ_2)=α(C+1)^2. Moreover, the optimal global (compromise) risk satisfies ℛ(θ∗)≤ϵR(θ^*)≤ε by our choice in Part (i). To ensure learner 1’s risk exceeds Γ , choose C=Γ+ϵ−1,α=ϵ(C+1)2.C\,=\, +ε\;-1, α\,=\, ε(C+1)^2. Then α∈(0,1)α∈(0,1) and ℛ(θ∗)=α(1−α)(C+1)2≤α(C+1)2=ϵ,R(θ^*)=α(1-α)(C+1)^2≤α(C+1)^2=ε, while ℛ(θ¯1)=(1−α)(C+1)2=(C+1)2−ϵ≥Γ.R( θ_1)=(1-α)(C+1)^2=(C+1)^2-ε≥ . Thus the two claims in the theorem are simultaneously satisfied. ∎ Appendix D Convergence of Algorithm˜1 and Algorithm˜2 D.1 Convergence of Algorithm 1 The convergence results for MSGD (Algorithm 1) follow as special cases of the MSGD-P analysis when the probing set U=∅U= . In this case, all probing terms vanish and the augmented potential f~ f reduces to the original potential f. See 2 Proof. This follows from the proof of Theorem˜3 with U=∅U= . When U=∅U= : • The indicator i∈U=01_i∈ U=0 for all i∈[m]i∈[m], so all probing terms vanish. • The augmented potential reduces to f~(Θ)=f(Θ) f( )=f( ). • The ODE (20) becomes Θ˙=−∇f(Θ) =-∇ f( ). The stochastic approximation argument proceeds identically: by Lemma˜11, verifying local Lipschitzness of −∇f-∇ f (Lemma˜8, Lemma˜14), the step-size conditions (Assumption 2), the martingale variance bound (Lemma˜12 with U=∅U= , so Kprobe=0K_probe=0), and bounded iterates (Assumption 4), the iterates converge almost surely to a compact connected internally chain transitive invariant set of Θ˙=−∇f(Θ) =-∇ f( ). ∎ See 1 Proof. Follows directly from Theorem˜3 with U=∅U= . ∎ D.2 Convergence of MSGD-P (Algorithm 2) Algorithm 3 Multi-learner Streaming Gradient Descent 1:loss function ℓ(⋅,⋅)≥0 (·,·)≥ 0; Initial models Θ0=(θ10,…,θm0) ^0=(θ^0_1,…,θ^0_m); Learning rate ηtt=1T+1\η^t\_t=1^T+1 2:for t=0,1,2,…,Tt=0,1,2,…,T do 3: Sample data point zt∼z^t 4: User selects model i=M(zt;Θt)i=M(z^t; ^t) 5: θit+1←θit−ηt∇ℓ(zt,θit)θ^t+1_i←θ^t_i-η^t∇ (z^t,θ^t_i) 6:end for 7:return ΘT ^T Define the empirical probing loss and augmented potential: L^i(θi) L_i( _i) =1n∑q=1nℓ(z~iq,θi),i∈U, = 1n _q=1^n ( z_i^q, _i), i∈ U, (18) f~(Θ) f( ) =f(Θ)+p∑i∈U(L^i(θi)+λ2‖θi‖2). =f( )+p _i∈ U ( L_i( _i)+ λ2\| _i\|^2 ). (19) Define the ordinary differential equation (ODE) Θ˙=F~(Θ) = F( ) with: F~i(Θ)=−(ταiz∼i[∇ℓ(z,θi)]+(1−τ)ai(Θ)z∼i(Θ)[∇ℓ(z,θi)]+p 1i∈U(∇L^i(θi)+λθi)) F_i( )=- (τ _i\, *E_z _i[∇ (z, _i)]+(1-τ)a_i( ) *E_z _i( )[∇ (z, _i)]+p\,1_i∈ U\, (∇ L_i( _i)+λ\, _i ) ) (20) See 3 Proof. The proof follows the stochastic approximation template by showing the iterates track the ODE Θ˙=F~(Θ) = F( ) and then using a Lyapunov argument for f~ f. Let z1∼z_1 , z2∼iz_2 _i, and z3∼i(Θt)z_3 _i( ^t). For the on-platform update, define for each coordinate i the random direction gi,platt(Θt)=∇ℓ(z2,θit),w.p. ταi,∇ℓ(z3,θit),w.p. (1−τ)ai(Θt),0,otherwise.g_i,plat^t( ^t)= cases∇ (z_2, _i^t),&w.p. τ _i,\\ ∇ (z_3, _i^t),&w.p. (1-τ)\,a_i( ^t),\\ 0,&otherwise. cases For the probing update, for each j∈Uj∈ U sample z~jt z_j^t uniformly from the fixed dataset j D_j and set gi,probet(Θt)=p 1i∈U(∇ℓ(z~it,θit)+λθit).g_i,probe^t( ^t)=p\,1_i∈ U\, (∇ ( z_i^t, _i^t)+λ\, _i^t ). Let g~it(Θt)=gi,platt(Θt)+gi,probet(Θt) g_i^t( ^t)=g_i,plat^t( ^t)+g_i,probe^t( ^t) and g~t=(g~1t,…,g~mt) g^t=( g_1^t,…, g_m^t). The algorithmic iterate satisfies Θt+1=Θt−ηtg~t(Θt)=Θt−ηt(F~(Θt)+vt), ^t+1= ^t- _t\, g^t( ^t)= ^t- _t\,( F( ^t)+v^t), where vt=g~t(Θt)−[g~t(Θt)∣ℱt]v^t= g^t( ^t)- *E[ g^t( ^t) _t]. Drift identity: By construction and by uniform sampling from i D_i, [g~it(Θt)∣ℱt] *E[ g_i^t( ^t) _t] =ταiz∼i[∇ℓ(z,θit)]+(1−τ)ai(Θt)z∼i(Θt)[∇ℓ(z,θit)] =τ _i\, *E_z _i[∇ (z, _i^t)]+(1-τ)\,a_i( ^t)\, *E_z _i( ^t)[∇ (z, _i^t)] +p 1i∈U(∇L^i(θit)+λθit) +p1_i∈ U\, (∇ L_i( _i^t)+λ\, _i^t ) =−F~i(Θt). =- F_i( ^t). Below, we verify the assumptions of Lemma˜11: • From Lemma˜8 and Lemma˜14, the drift F~(Θ) F( ) is locally Lipschitz; the probe part θi↦p(∇L^i(θi)+λθi) _i p\,(∇ L_i( _i)+λ\, _i) is a finite average of locally Lipschitz gradients plus a globally Lipschitz linear term. • From Assumption 2, the step sizes satisfy ∑tηt=∞ _t _t=∞ and ∑tηt2<∞ _t _t^2<∞. • From Lemma˜12, augmented to include the probe term, there exists K>0K>0 such that [‖vt‖2∣ℱt]≤K(1+‖Θt‖2) *E[\|v^t\|^2 _t]≤ K(1+\| ^t\|^2). • From Assumption 4, we have supt‖Θt‖<∞ _t\| ^t\|<∞ almost surely. By Lemma˜11, the iterates converge almost surely to a compact, connected, internally chain transitive invariant set of Θ˙=F~(Θ) = F( ). Since F~(Θ)=−∇f~(Θ) F( )=-∇ f( ), along ODE trajectories dtf~(Θ(t))=⟨∇f~,Θ˙⟩=−‖∇f~‖2≤0, ddt\, f( (t))= ∇ f, =-\|∇ f\|^2≤ 0, with equality iff ∇f~=0∇ f=0. Thus f~ f is a strict Lyapunov function and the only invariant sets are stationary points, yielding the claim. ∎ Lemma 11 (Borkar [2008], Chapter 2, Theorem 2). Let xn\x_n\ be a sequence generated by the stochastic approximation algorithm xn+1=xn+a(n)[h(xn)+Mn+1],n≥0,x_n+1=x_n+a(n)[h(x_n)+M_n+1], n≥ 0, where: 1. h:ℝd→ℝdh:R^d ^d is Lipschitz continuous 2. The step sizes a(n)\a(n)\ satisfy ∑na(n)=∞ _na(n)=∞ and ∑na(n)2<∞ _na(n)^2<∞ 3. Mn\M_n\ is a martingale difference sequence satisfying E[‖Mn+1‖2|ℱn]≤K(1+‖xn‖2)E[||M_n+1||^2|F_n]≤ K(1+||x_n||^2) for some K>0K>0 4. supn‖xn‖<∞ _n||x_n||<∞ almost surely Then almost surely, the sequence xn\x_n\ converges to a (possibly sample path dependent) compact connected internally chain transitive invariant set of the ODE x˙(t)=h(x(t)). x(t)=h(x(t)). Lemma 12 (Martingale variance bound). Suppose that Assumption 1 holds and that the probing datasets ii∈U\ D_i\_i∈ U are fixed finite sets. Let gt(Θt)=(g1t(Θt),…,gmt(Θt))g^t( ^t)=(g^t_1( ^t),…,g^t_m( ^t)) be the stochastic update vector defined by git(Θt)=gi,platt(Θt)+gi,probet(Θt),g^t_i( ^t)\;=\;g^t_i,plat( ^t)\;+\;g^t_i,probe( ^t), where gi,platt(Θt)=∇ℓ(zt,θit),if i=it,0,if i≠it,gi,probet(Θt)=p 1i∈U(∇ℓ(z~it,θit)+λθit),g^t_i,plat( ^t)= cases∇ (z^t,θ^t_i),&if i=i_t,\\ 0,&if i≠ i_t, cases g^t_i,probe( ^t)=p\,1_i∈ U\, (∇ ( z_i^t,θ^t_i)+λ\, _i^t ), with z~it z_i^t sampled uniformly from i D_i independently of iti_t. Define the filtration ℱt=σ(Θ0,z1,…,zt−1,ii∈U)F_t=σ( ^0,z^1,…,z^t-1,\ D_i\_i∈ U), which contains all information available prior to time t. Define the martingale difference sequence: vt=gt(Θt)−[gt(Θt)∣ℱt].v^t=g^t( ^t)-E[g^t( ^t) _t]. Then there exists a constant K>0K>0 (made explicit below) such that: [‖vt‖2∣ℱt]≤K(1+‖Θt‖2).E[\|v^t\|^2 _t]≤ K\,(1+\| ^t\|^2). Proof. Gradient bounds. From Lemmas 4 and 6, for all (x,y)(x,y) with ‖x‖≤R\|x\|≤ R and all θ we have bounds of the form ‖∇θℓ(x,y;θ)‖≤A0+A1‖θ‖,\| _θ (x,y;θ)\|≤ A_0+A_1\,\|θ\|, with (A0,A1)=(2RYmax, 2R2),(squared loss),(2R, 0),(cross-entropy).(A_0,A_1)= cases(2R\,Y_ ,\;2R^2),&(squared loss),\\ ( 2\,R,\;0),&(cross-entropy). cases For the probe term under squared loss, labels are pseudo-labels y^=median⟨x,θ0j⟩:j∈[m] y=median\ x, _0^j :j∈[m]\ so that |y^|≤Rmaxj∈[m]∥θ0j∥=:Ymax,probe| y|≤ R\, _j∈[m]\| _0^j\|=:Y_ ,probe, giving ‖∇θℓ(x,y^;θ)‖≤A~0+A1‖θ‖\| _θ (x, y;θ)\|≤ A_0+A_1\,\|θ\| with A~0:=2RYmax,probe A_0:=2R\,Y_ ,probe. Including the L2 regularization term (which appears only in the probe update) and using the triangle inequality, ‖p(∇θℓ(x,y^;θ)+λθ)‖≤pA~0+p(A1+λ)‖θ‖.\|p\,( _θ (x, y;θ)+λ\,θ)\|≤ p\, A_0+p\,(A_1+λ)\,\|θ\|. Define the block constants Kplat:=2max(A02,A12),Kprobe:=2max((pA~0)2,(p(A1+λ))2),K_plat:=2 (A_0^2,A_1^2 ), K_probe:=2 ((p\, A_0)^2, (p\,(A_1+λ) )^2 ), where for cross-entropy we take A1=0A_1=0 and use the same A0=2RA_0= 2R for both platform and probe. Variance decomposition. By definition of vtv^t and Var(Y)=[‖Y‖2]−‖[Y]‖2Var(Y)= *E[\|Y\|^2]-\| *E[Y]\|^2, [‖vt‖2∣ℱt]≤[‖gt(Θt)‖2∣ℱt]. *E[\|v^t\|^2 _t]\;≤\; *E[\|g^t( ^t)\|^2 _t]. We bound the RHS. Since gtg^t has at most one nonzero platform block and up to |U||U| nonzero probe blocks, ‖gt(Θt)‖2 \|g^t( ^t)\|^2 =∑i=1m‖gi,platt+gi,probet‖2≤ 2∑i=1m‖gi,platt‖2+2∑i=1m‖gi,probet‖2. = _i=1^m\|g^t_i,plat+g^t_i,probe\|^2\;≤\;2 _i=1^m\|g^t_i,plat\|^2+2 _i=1^m\|g^t_i,probe\|^2. Taking conditional expectations and using the selection probabilities for the platform block as in the MSGD lemma, [‖gt(Θt)‖2∣ℱt] *E[\|g^t( ^t)\|^2 _t] ≤2∑i=1mℙ(it=i∣ℱt)[‖∇ℓ(zt,θit)‖2∣ℱt,it=i] ≤ 2 _i=1^mP(i_t=i _t)\; *E[\|∇ (z^t, _i^t)\|^2 _t,i_t=i] +2∑j∈U[‖p∇ℓ(z~jt,θjt)‖2∣ℱt]. +2 _j∈ U *E[\|p\,∇ ( z_j^t, _j^t)\|^2 _t]. Applying the block bounds gives [‖gt(Θt)‖2∣ℱt] *E[\|g^t( ^t)\|^2 _t] ≤2Kplat∑i=1mℙ(it=i∣ℱt)(1+‖θit‖2) ≤ 2K_plat _i=1^mP(i_t=i _t)\,(1+\| _i^t\|^2) +2Kprobe∑j∈U(1+‖θjt‖2) +2K_probe _j∈ U(1+\| _j^t\|^2) ≤2Kplat(1+‖Θt‖2)+ 2|U|Kprobe+ 2Kprobe‖Θt‖2 ≤ 2K_plat\,(1+\| ^t\|^2)\;+\;2|U|K_probe\;+\;2K_probe\,\| ^t\|^2 =2(Kplat+|U|Kprobe)+ 2(Kplat+Kprobe)‖Θt‖2. =2 (K_plat+|U|K_probe )\;+\;2 (K_plat+K_probe )\,\| ^t\|^2. Therefore, setting K:=2maxKplat+|U|Kprobe,Kplat+KprobeK:=2 \K_plat+|U|K_probe,\;K_plat+K_probe \ yields [‖vt‖2∣ℱt]≤K(1+‖Θt‖2). *E[\|v^t\|^2 _t]≤ K\,(1+\| ^t\|^2). This completes the proof. ∎ Lemma 13 (Gradient of the augmented objective). For every i∈[m]i∈[m] the gradient of f~ f with respect to θi _i is ∇θif~(Θ) _ _i\, f( ) =ταiz∼i[∇ℓ(z,θi)]+(1−τ)ai(Θ)z∼i(Θ)[∇ℓ(z,θi)] =τ _i\, *E_z _i[∇ (z, _i)]+(1-τ)\,a_i( )\, *E_z _i( )[∇ (z, _i)] +p 1i∈U(∇L^i(θi)+λθi). +p\,1_i∈ U\, (∇ L_i( _i)+λ\, _i ). Proof. We treat a single index i; all other coordinates of Θ are held fixed. The term (1−τ)ai(Θ)z∼i(Θ)[ℓ(z,θi)](1-τ)a_i( ) *E_z _i( )[ (z, _i)] depends on θi _i both explicitly (inside ℓ ) and implicitly through ai(Θ)a_i( ) and i(Θ)D_i( ). Lemma 4.3 of Su and Dean [2024] proves that for any differentiable ℓ satisfying the stated regularity, ∇θi(ai(Θ)z∼i(Θ)[ℓ(z,θi)])=ai(Θ)z∼i(Θ)[∇ℓ(z,θi)]. _ _i\! (a_i( )\, *E_z _i( )[ (z, _i)] )=a_i( )\, *E_z _i( )[∇ (z, _i)]. Multiplying by (1−τ)(1-τ) yields the corresponding contribution, while the ταiτ _i-term is immediate. Local L-Lipschitzness of ℓ ensures the required directional limits. The probing part depends only on θi _i through the finite average L^i(θi)=1n∑q=1nℓ(z~iq,θi) L_i( _i)= 1n _q=1^n ( z_i^q, _i) and the regularization term λ2‖θi‖2 λ2\| _i\|^2, so ∇θi(p(L^i(θi)+λ2‖θi‖2))=p(∇L^i(θi)+λθi) _ _i (p\,( L_i( _i)+ λ2\| _i\|^2) )=p\,(∇ L_i( _i)+λ\, _i) if i∈Ui∈ U and zero otherwise. Summing the contributions gives the stated expression. ∎ Lemma 14 (Local Lipschitz of ai(Θ)a_i( )). Let the standard regularity and boundedness assumptions for the idealized MSGD dynamics hold. Then ai(Θ)a_i( ) is locally Lipschitz in Θ . Proof. From Lemma˜8, we know that the loss function ℓ is locally Lipschitz. In other words: for every compact set ⊂ℝk×dK ^k× d there is a constant L<∞L_K<∞ such that |ℓ(x,θ)−ℓ(x,θ′)|≤L‖θ−θ′‖∀x∈B(0,R),θ,θ′∈. | (x,θ)- (x,θ ) |\;≤\;L_K\,\|θ-θ \| ∀\,x∈ B(0,R),\;θ,θ . Fix any compact neighborhood K containing both Θ and Θ′ . Let pmax=supx∈B(0,R)p(x),Las above.p_ \;=\; _x∈ B(0,R)p(x), L_K\;as above. We will show |ai(Θ)−ai(Θ′)|≤C‖Θ−Θ′‖ |a_i( )-a_i( ) |≤ C_K\| - \| for some C_K. Case m=2m=2. With services i=1,2i=1,2, a1(Θ)−a1(Θ′)=∫X1(Θ)∖X1(Θ′)p(x)x−∫X1(Θ′)∖X1(Θ)p(x)x,a_1( )-a_1( )= _X_1( ) X_1( )p(x)\,dx\;-\; _X_1( ) X_1( )p(x)\,dx, so |a1(Θ)−a1(Θ′)|≤pmax[λ(X1(Θ)∖X1(Θ′))+λ(X1(Θ′)∖X1(Θ))]. |a_1( )-a_1( ) |\;≤\;p_ \, [λ (X_1( ) X_1( ) )+λ (X_1( ) X_1( ) ) ]. For any x∈X1(Θ′)∖X1(Θ)x∈ X_1( ) X_1( ) we have ℓ(x,θ1′)<ℓ(x,θ2′) (x,θ _1)< (x,θ _2) and ℓ(x,θ2)<ℓ(x,θ1) (x, _2)< (x, _1). Hence 0<ℓ(x,θ1)−ℓ(x,θ2)=[ℓ(x,θ1)−ℓ(x,θ1′)]+[ℓ(x,θ1′)−ℓ(x,θ2′)]+[ℓ(x,θ2′)−ℓ(x,θ2)].0\;<\; (x, _1)- (x, _2)= [ (x, _1)- (x,θ _1) ]+ [ (x,θ _1)- (x,θ _2) ]+ [ (x,θ _2)- (x, _2) ]. Since x∈X1(Θ′)x∈ X_1( ), the middle term satisfies ℓ(x,θ1′)−ℓ(x,θ2′)≤0 (x,θ _1)- (x,θ _2)≤ 0. The first and third terms are each bounded by L‖Θ−Θ′‖L_K\| - \| by Lipschitzness. Thus ℓ(x,θ1)−ℓ(x,θ2)≤2L‖Θ−Θ′‖ (x, _1)- (x, _2)≤ 2L_K\| - \|. Define S=x:|ℓ(x,θ1)−ℓ(x,θ2)|≤2L‖Θ−Θ′‖.S\;=\; \\,x: | (x, _1)- (x, _2) |≤ 2L_K\| - \| \. Since λ(S)≤(2L/C)‖Θ−Θ′‖λ(S)≤(2L_K/C)\| - \| for some constant C from ˜3 and X1(Θ′)∖X1(Θ)⊂SX_1( ) X_1( )⊂ S, we get λ(X1(Θ′)∖X1(Θ))≤C′‖Θ−Θ′‖λ(X_1( ) X_1( ))≤ C \| - \|. The same argument applies to the other set difference, so altogether |a1(Θ)−a1(Θ′)|≤ 4pmaxL‖Θ−Θ′‖. |a_1( )-a_1( ) |\;≤\;4\,p_ \,L_K\;\| - \|. General m. The same pairwise argument shows for each i and j≠ij≠ i, λ(Xi(Θ)∩Xj(Θ′))≤C‖Θ−Θ′‖λ (X_i( )∩ X_j( ) )≤ C_K\| - \|. Summing over all j≠ij≠ i gives λ(Xi(Θ)△Xi(Θ′))≤C′‖Θ−Θ′‖λ (X_i( ) X_i( ) )≤ C _K\| - \|, and hence |ai(Θ)−ai(Θ′)|≤pmaxC′‖Θ−Θ′‖ |a_i( )-a_i( ) |≤ p_ \,C _K\,\| - \|. Since all constants depend only on the compact set K, this proves that ai(Θ)a_i( ) is Lipschitz on K, i.e. locally Lipschitz in Θ . ∎ Appendix E Squared Loss: Performance Guarantee Notation. Let (xiq,yiq)q=1n\(x_i^q,y_i^q)\_q=1^n be the probing sample with true labels yiqy_i^q and pseudo-labels y~iq y_i^q. Here, the true labels yiqy_i^q are hidden from the learner, and the pseudo-labels y~iq y_i^q are observed. For any θ∈ℝdθ ^d, define L^i(θ):=1n∑q=1n(⟨xiq,θ⟩−y~iq)2, L_i(θ):= 1n _q=1^n ( x_i^q,θ - y_i^q )^2, and L^i,true(θ):=1n∑q=1n(⟨xiq,θ⟩−yiq)2. L_i,true(θ):= 1n _q=1^n ( x_i^q,θ -y_i^q )^2. Additionally, define the empirical pseudo–true discrepancy Δi2:=1n∑q=1n(y~iq−yiq)2. _i^2:= 1n _q=1^n ( y_i^q-y_i^q )^2. E.1 Proof of Lemma˜3 We restate the lemma for ease of reference, and then provide the proof. See 3 Proof. We treat each scenario in turn. (i) Majority-good. Fix any x with ‖x‖≤R\|x\|≤ R. Write the peer deviations uj:=⟨x,θj0⟩−⟨x,θ⋆⟩u_j:= x, _j^0 - x,θ . If strictly more than half of the peers satisfy ‖θj0−θ⋆‖≤r\| _j^0-θ \|≤ r, then at least half of the uj\u_j\ lie in [−Rr,Rr][-Rr,Rr], so the median obeys |y~(x)−⟨x,θ⋆⟩|≤Rr| y(x)- x,θ |≤ Rr and hence (y~−y)2=(y~−⟨x,θ⋆⟩+⟨x,θ⋆⟩−y)2≤ 2(y~−⟨x,θ⋆⟩)2+ 2(⟨x,θ⋆⟩−y)2≤ 2R2r2+ 2(⟨x,θ⋆⟩−y)2.( y-y)^2\;=\; ( y- x,θ + x,θ -y )^2\;≤\;2\,( y- x,θ )^2\;+\;2\,( x,θ -y)^2\;≤\;2R^2r^2\;+\;2\,( x,θ -y)^2. Taking expectation over (x,y)∼(x,y) yields [(y~−y)2]≤2R2r2+2[(⟨x,θ⋆⟩−y)2]=2R2r2+2ϵ *E[( y-y)^2]≤ 2R^2r^2+2\, *E[( x,θ -y)^2]=2R^2r^2+2ε. (i) Market-leader. Here y~(x)=x⊤θj∗ y(x)=x _j and by assumption [(y~−y)2]=[(x⊤θj∗−y)2]≤ξ *E [( y-y)^2 ]= *E [(x _j -y)^2 ]≤ξ, which directly verifies Accurate Probing with B=ξB=ξ. (i) Partial knowledge. Fix any x with ‖x‖≤R\|x\|≤ R. The probing rule Ti(x)=GT_i(x)=G uses median aggregation over the subset G⊆[m]∖iG [m] \i\. Write the peer deviations for j∈Gj∈ G: uj:=⟨x,θj0⟩−⟨x,θ⋆⟩u_j:= x, _j^0 - x,θ . Since all learners in G satisfy ‖θj0−θ⋆‖≤r\| _j^0-θ \|≤ r, all deviations ujj∈G\u_j\_j∈ G lie in [−Rr,Rr][-Rr,Rr]. Because |G|>(m−1)/2|G|>(m-1)/2, the set G contains more than half of the peers (excluding i), and thus the median over G obeys |y~(x)−⟨x,θ⋆⟩|≤Rr| y(x)- x,θ |≤ Rr. The remainder of the proof follows identically to case (i): (y~−y)2=(y~−⟨x,θ⋆⟩+⟨x,θ⋆⟩−y)2≤ 2(y~−⟨x,θ⋆⟩)2+ 2(⟨x,θ⋆⟩−y)2≤ 2R2r2+ 2(⟨x,θ⋆⟩−y)2.( y-y)^2\;=\; ( y- x,θ + x,θ -y )^2\;≤\;2\,( y- x,θ )^2\;+\;2\,( x,θ -y)^2\;≤\;2R^2r^2\;+\;2\,( x,θ -y)^2. Taking expectation over (x,y)∼(x,y) yields [(y~−y)2]≤2R2r2+2[(⟨x,θ⋆⟩−y)2]=2R2r2+2ϵ *E[( y-y)^2]≤ 2R^2r^2+2\, *E[( x,θ -y)^2]=2R^2r^2+2ε. (iv) Preference-aware. By the probing rule Ti(x)=π(x)T_i(x)=\π(x)\, we have y~(x)=x⊤θ¯π(x) y(x)=x θ_π(x), so [(y~−y)2]=∑i=1mαi(x,y)∼i[(y−x⊤θ¯i)2]. *E [( y-y)^2 ]\;=\; _i=1^m _i\, *E_(x,y) _i\! [(y-x θ_i)^2 ]. By optimality of θ¯i θ_i for the ERM objective on iP_i, for every i and any θ (in particular θ⋆θ ), i[(y−x⊤θ¯i)2]≤i[(y−x⊤θ⋆)2]. *E_P_i\! [(y-x θ_i)^2 ]\;≤\; *E_P_i\! [(y-x θ )^2 ]. Summing over i with weights αi _i gives [(y~−y)2]≤∑i=1mαii[(y−x⊤θ⋆)2]=ϵ. *E [( y-y)^2 ]\;≤\; _i=1^m _i\, *E_P_i\! [(y-x θ )^2 ]\;=\;ε. ∎ E.2 Proof of Theorem˜4 Proof of Corollary 1. Set λ=ϵ/‖θ⋆‖2λ=ε/\|θ \|^2 in Lemma˜15. Define S(κ,λ):=(4b⋆+6C02)2log(2/κ)+4(Ymax+BθR)BθR+bu2log(2/κ),S(κ,λ):=(4b_ +6C_0^2) 2 (2/κ)+4(Y_ +B_θR)B_θR+b_u 2 (2/κ), where BθB_θ and bub_u are the λ-dependent quantities from Lemma˜15. If n≥n¯:=S(κ,λ)2ϵ2,n\;≥\; n\;:=\; S(κ,λ)^2ε^2, then the concentration terms in Lemma˜15 satisfy S(κ,λ)/n≤ϵS(κ,λ)/ n≤ε. With this choice and λ‖θ⋆‖2=ϵλ\|θ \|^2=ε, the explicit bound yields ℛ(θ~i)≤ 6B+(4+2p)ϵ+ϵ+ϵ= 6B+(6+2p)ϵ,R( θ_i)\;≤\;6B+ (4+ 2p )ε+ε+ε\;=\;6B+ (6+ 2p )ε, which is O((p+1p)ϵ+B)O\! ( ( p+1p )ε+B ). To see the stated scaling of n¯ n, note that Bθ=Θ(1/λ)B_θ= (1/ λ) and bu=(Ymax+BθR)2=O(1/λ)b_u=(Y_ +B_θR)^2=O(1/λ) with constants depending on (R,Ymax,M0,p)(R,Y_ ,M_0,p). To surface the dominant dependence on (R,Ymax,M0,p)(R,Y_ ,M_0,p), write A:=Ymax2+pR2M02A:=Y_ ^2+pR^2M_0^2 so that BθR=R2Aλpand(BθR)2=2R2Aλp.B_θR=R 2Aλ p (B_θR)^2= 2R^2Aλ p. The leading terms (in terms of ϵε) in S(κ,λ)S(κ,λ) scale as (BθR)2(B_θR)^2, so one can take n¯=O(R4‖θ⋆‖4ϵ4(Ymax2p+R2M02)2log1κ), n=O\! ( R^4\|θ \|^4ε^4 ( Y_ ^2p+R^2M_0^2 )^2 1κ ), where we suppress lower-order terms in ϵε coming from b⋆b_ and C0C_0. ∎ See 4 Proof. By Lemma˜15, for any κ∈(0,1)κ∈(0,1) and with probability at least 1−κ1-κ, ℛ(θ~i)≤ 6B+(4+2p)ϵ+λ‖θ⋆‖2+T(κ)n,R( θ_i)\;≤\;6\,B+ (4+ 2p )ε+λ\,\|θ \|^2+ T(κ) n, where every n−1/2n^-1/2 contribution has been grouped into T(κ) T(κ) :=(4b⋆+6C02)2log(2/κ)+bu2log(2/κ)+4(Ymax+BθR)BθR. := (4b_ +6C_0^2 ) 2 (2/κ)+b_u 2 (2/κ)+4(Y_ +B_θR)B_θR. (21) The terms that depend on λ and p are through Bθ=2(Ymax2+pYmax,probe2)/(λp)B_θ= 2(Y_ ^2+p\,Y_ ,probe^2)/(λ\,p), which also appears inside bu=(Ymax+BθR)2b_u=(Y_ +B_θR)^2. Expanding the BθB_θ-dependent pieces, from (21), T(κ)=(4b⋆+6C02)2log(2/κ)+[(Ymax+BθR)22log(2/κ)+4(Ymax+BθR)BθR]⏟Bθ-dependent.T(κ)= (4b_ +6C_0^2 ) 2 (2/κ)+ [(Y_ +B_θR)^2 2 (2/κ)+4(Y_ +B_θR)B_θR ]_$B_θ$-dependent. Thus the λ-independent part is already O(log(1/κ))O\! ( (1/κ) ), so it remains to control the bracketed term. Expanding gives (Ymax+BθR)22log(2/κ)+4(Ymax+BθR)BθR=O(log(1/κ)[Ymax2+YmaxBθR+Bθ2R2]). (Y_ +B_θR)^2 2 (2/κ)+4(Y_ +B_θR)B_θR=O\! ( (1/κ)\, [Y_ ^2+Y_ \,B_θR+B_θ^2R^2 ] ). Plugging in the value of BθB_θ from Lemma 20 and assuming λ<1λ<1, we can combine with the (λ,p)(λ,p)-independent part of T(κ)T(κ) to get Cgen=R(Ymax2+Ymax,probe2)+4b⋆+6C02 C_gen=R(Y_ ^2+\,Y_ ,probe^2)+4b_ +6C_0^2 ∎ Lemma 15 (Squared-loss performance Full Statement). Let ˜5 hold with parameter B. Then, for any κ∈(0,1)κ∈(0,1), with probability at least 1−κ1-κ over the probing sample, every stationary point Θ~ of MSGD-P satisfies, for probing learner i∈[m]i∈[m], ℛ(θ~i) ( θ_i) ≤ 6B+(4+2p)ϵ+λ‖θ⋆‖2 \;≤\;6\,B+ (4+ 2p )\,ε+λ\,\|θ \|^2 +(4b⋆+6C02)2log(2/κ)n+4(Ymax+BθR)BθRn+bu2log(2/κ)n, + (4\,b_ +6\,C_0^2)\, 2 (2/κ) n+ 4\,(Y_ +B_θR)\,B_θR n+b_u\, 2 (2/κ)n, where the constants are defined as follows: • C0:=Ymax+Ymax,probe C_0\;:=\;Y_ +Y_ ,probe. • Bθ:=2(Ymax2+pYmax,probe2)λp B_θ\;:=\; 2(Y_ ^2+p\,Y_ ,probe^2)λ\,p is a radius (independent of θ⋆θ ) with Ymax,probe:=RM0,M0:=maxj≠i‖θj0‖, Y_ ,probe\;:=\;R\,M_0,\ \ M_0\;:=\; _j≠ i\| _j^0\|, which bounds the pseudo-label magnitudes via |y~iq|≤Ymax,probe| y_i^q|≤ Y_ ,probe. • b⋆:=(Ymax+R‖θ⋆‖)2. b_ \;:=\; (Y_ +R\,\|θ \| )^2. • bu:=(Ymax+BθR)2. b_u\;:=\; (Y_ +B_θR )^2. Proof. We work on the event ℰu∩ℰ⋆E_u _ where ℰuE_u is the event of Lemma 18 (probability ≥1−κ/2≥ 1-κ/2 with BθB_θ from Lemma 20) and ℰ⋆E_ is the event of Lemma 17 (probability ≥1−κ/2≥ 1-κ/2). By a union bound, ℙ(ℰu∩ℰ⋆)≥1−κ.P(E_u _ )≥ 1-κ. Bound on L^i(θ~i) L_i( θ_i). By stationarity, θ~i θ_i minimizes Φ^iprobe(θ;Θ~)=ταii[ℓ(z,θ)]+(1−τ)ai(Θ~)i(Θ~)[ℓ(z,θ)]+pL^i(θ)+λp2‖θ‖2. _i^probe(θ; )=τ _i\, *E_P_i[ (z,θ)]+(1-τ)a_i( )\, *E_D_i( )[ (z,θ)]+p\, L_i(θ)+ λ\,p2\|θ\|^2. Thus, comparing the objective at θ~i θ_i and θ⋆θ , pL^i(θ~i)≤ταii[ℓ(z,θ⋆)]+(1−τ)ai(Θ~)i(Θ~)[ℓ(z,θ⋆)]+pL^i(θ⋆)+λp2‖θ⋆‖2.p\, L_i( θ_i)\;≤\;τ _i\, *E_P_i[ (z,θ )]+(1-τ)a_i( )\, *E_D_i( )[ (z,θ )]+p\, L_i(θ )+ λ\,p2\|θ \|^2. Since ταiiℓ(θ⋆)+(1−τ)ai(Θ~)i(Θ~)ℓ(θ⋆)≤ϵ,τ _i *E_P_i (θ )+(1-τ)a_i( ) *E_D_i( ) (θ )≤ε, dividing by p, we obtain L^i(θ~i)≤ϵp+L^i(θ⋆)+λ2‖θ⋆‖2. L_i( θ_i)\;≤\; εp\;+\; L_i(θ )\;+\; λ2\,\|θ \|^2. By Lemma 16 and Lemma 17, L^i(θ⋆)≤2L^i,true(θ⋆)+2Δi2≤2ϵ+2Λ⋆+2Δi2. L_i(θ )≤ 2\, L_i,true(θ )+2\, _i^2≤ 2\,ε+2\, _ +2\, _i^2. Hence L^i(θ~i)≤ϵp+2ϵ+2Λ⋆+2Δi2+λ2‖θ⋆‖2. L_i( θ_i)\;≤\; εp+2\,ε+2\, _ +2\, _i^2\;+\; λ2\,\|θ \|^2. Bound on L^i,true(θ~i) L_i,true( θ_i). Applying Lemma 16 again gives L^i,true(θ~i)≤ 2L^i(θ~i)+2Δi2. L_i,true( θ_i)\;≤\;2\, L_i( θ_i)+2\, _i^2. Substituting the bound from Step 1, L^i,true(θ~i)≤(2p+4)ϵ+ 4Λ⋆+ 6Δi2+λ‖θ⋆‖2. L_i,true( θ_i)\;≤\; ( 2p+4 )ε\;+\;4\, _ \;+\;6\, _i^2\;+\;λ\,\|θ \|^2. By Lemma 19, on ℰ⋆E_ , Δi2≤B+C022log(2/κ)n. _i^2≤ B+C_0^2\, 2 (2/κ)n. Therefore, L^i,true(θ~i)≤ 6B+(2p+4)ϵ+ 4Λ⋆+ 6C022log(2/κ)n+λ‖θ⋆‖2. L_i,true( θ_i)\;≤\;6\,B\;+\; ( 2p+4 )ε\;+\;4\, _ \;+\;6\,C_0^2\, 2 (2/κ)n\;+\;λ\,\|θ \|^2. Bound on ℛ(θ~i)R( θ_i). Finally, on ℰuE_u (with ‖θ~i‖≤Bθ\| θ_i\|≤ B_θ from Lemma 20), ℛ(θ~i)≤L^i,true(θ~i)+Λu.R( θ_i)≤ L_i,true( θ_i)+ _u. ∎ Alternative scaling with explicit λ. If we keep λ explicit and only choose n to control the concentration terms in Lemma˜15, then for any target tolerance δ>0δ>0 it suffices to take n≥n¯(λ,δ):=S(κ,λ)2δ2,n\;≥\; n(λ,δ)\;:=\; S(κ,λ)^2δ^2, which yields ℛ(θ~i)≤ 6B+(4+2p)ϵ+λ‖θ⋆‖2+δ.R( θ_i)\;≤\;6B+ (4+ 2p )ε+λ\|θ \|^2+δ. Writing Ymax,probe=RM0Y_ ,probe=RM_0 and A:=Ymax2+pR2M02A:=Y_ ^2+pR^2M_0^2, we have Bθ=2Aλpand(Ymax+BθR)2≤2Ymax2+4R2Aλp.B_θ= 2Aλ p (Y_ +B_θR)^2≤ 2Y_ ^2+ 4R^2Aλ p. Using b⋆=(Ymax+R‖θ⋆‖)2b_ =(Y_ +R\|θ \|)^2 and C0=Ymax+RM0C_0=Y_ +RM_0, this implies S(κ,λ)2=O(log1κ)[(Ymax+R‖θ⋆‖)4+(Ymax+RM0)4+R4A2λ2p2],S(κ,λ)^2=O\! ( 1κ ) [(Y_ +R\|θ \|)^4+(Y_ +RM_0)^4+ R^4A^2λ^2p^2 ], and therefore a sufficient choice is n=O(log(1/κ)δ2[(Ymax+R‖θ⋆‖)4+(Ymax+RM0)4+R4(Ymax2+pR2M02)2λ2p2]).n=O\! ( (1/κ)δ^2 [(Y_ +R\|θ \|)^4+(Y_ +RM_0)^4+ R^4(Y_ ^2+pR^2M_0^2)^2λ^2p^2 ] ). Setting δ=ϵδ=ε yields the same bias expression as above, but now with n explicit in (R,Ymax,M0,p,λ,ϵ,κ)(R,Y_ ,M_0,p,λ,ε,κ). ∎ Lemma 16. We have L^i,true(θ)≤(L^i(θ)+Δi)2andL^i(θ)≤(L^i,true(θ)+Δi)2. L_i,true(θ)\;≤\; ( L_i(θ)+ _i )^2 L_i(θ)\;≤\; ( L_i,true(θ)+ _i )^2. In particular, L^i,true(θ)≤2L^i(θ)+2Δi2 L_i,true(θ)≤ 2\, L_i(θ)+2\, _i^2 and L^i(θ)≤2L^i,true(θ)+2Δi2 L_i(θ)≤ 2\, L_i,true(θ)+2\, _i^2. Proof of Lemma 16. Let X∈ℝn×dX ^n× d be the design matrix, :=Xθ−~a:=Xθ- y and :=~−b:= y-y. Then Xθ−=+.Xθ-y=a+b. By the triangle inequality, L^i,true(θ)=‖Xθ−‖n≤‖n+‖n=L^i(θ)+Δi. L_i,true(θ)= \|Xθ-y\| n≤ \|a\| n+ \|b\| n= L_i(θ)+ _i. Squaring yields the first inequality; the second is analogous. ∎ Lemma 17 (One–point deviation at θ⋆θ ). For any κ∈(0,1)κ∈(0,1), with probability at least 1−κ/21-κ/2, |L^i,true(θ⋆)−ℛ(θ⋆)|≤Λ⋆whereΛ⋆:=b⋆2log(2/κ)n,b⋆:=(Ymax+R‖θ⋆‖)2. | L_i,true(θ )-R(θ ) |\;≤\; _ _ \;:=\;b_ \, 2 (2/κ)n,\ \ b_ \;:=\; (Y_ +R\,\|θ \| )^2. Proof of Lemma 17. For each q, define the random variable Zq:=(⟨x~iq,θ⋆⟩−yiq)2.Z_q:=( x_i^q,θ -y_i^q)^2. Since |y|≤Ymax|y|≤ Y_ and ‖x‖≤R\|x\|≤ R a.s., we have Zq∈[0,(Ymax+R‖θ⋆‖)2]=[0,b⋆].Z_q∈[0,\,(Y_ +R\|θ \|)^2]=[0,b_ ]. By Hoeffding’s inequality, with probability at least 1−κ/21-κ/2, |1n∑q=1nZq−[Z]|≤b⋆2log(2/κ)n. | 1n _q=1^nZ_q-E[Z] |≤ b_ 2 (2/κ)n. ∎ Lemma 18 (Uniform deviation over ‖θ‖≤Bθ\\|θ\|≤ B_θ\). Fix any radius Bθ>0B_θ>0 and let κ∈(0,1)κ∈(0,1). Define the squared‐loss class ℱBθ:=fθ(x,y)=(y−⟨x,θ⟩)2|‖θ‖≤Bθ.F_B_θ\;:=\; \\,f_θ(x,y)\;=\; (y- x,θ )^2\ |\ \|θ\|≤ B_θ \. Then, with probability at least 1−κ/21-κ/2 (over the draw of the probing sample of size n), sup‖θ‖≤Bθ|L^i,true(θ)−ℛ(θ)|≤Λu, _\|θ\|≤ B_θ\ | L_i,true(θ)-R(θ) |\;≤\; _u, where Λu:=4(Ymax+BθR)BθRn+bu2log(2/κ)n,bu:=(Ymax+BθR)2. _u\;:=\; 4\,(Y_ +B_θR)\,B_θR n\;+\;b_u\, 2 (2/κ)n, b_u\;:=\;(Y_ +B_θR)^2. Proof. We apply Wainwright’s Theorem 4.10. Uniform bound b for ℱBθF_B_θ. For any ‖θ‖≤Bθ\|θ\|≤ B_θ and any (x,y)(x,y) with ‖x‖≤R\|x\|≤ R, |y|≤Ymax|y|≤ Y_ , we have |y−⟨x,θ⟩|≤|y|+|⟨x,θ⟩|≤Ymax+‖x‖‖θ‖≤Ymax+BθR. |y- x,θ |\;≤\;|y|+| x,θ |\;≤\;Y_ +\|x\|\,\|θ\|\;≤\;Y_ +B_θR. Hence 0≤fθ(x,y)=(y−⟨x,θ⟩)2≤(Ymax+BθR)2=:bu.0\ ≤\ f_θ(x,y)\;=\; (y- x,θ )^2\ ≤\ (Y_ +B_θR)^2\;=:\;b_u. Thus ℱBθF_B_θ is bub_u–uniformly bounded. Bound Rn(ℱBθ)R_n(F_B_θ) via contraction to the linear class. Fix a sample S=(xi,yi)i=1nS=\(x_i,y_i)\_i=1^n and let σ1,…,σn _1,…, _n be i.i.d. Rademacher signs. The empirical Rademacher average of ℱBθF_B_θ on S is RadS(ℱBθ):=σ[sup‖θ‖≤Bθ1n∑i=1nσi(yi−⟨xi,θ⟩)2].Rad_S(F_B_θ)\;:=\; *E_σ [ _\|θ\|≤ B_θ\ 1n _i=1^n _i (y_i- x_i,θ )^2 ]. Define ui,θ:=⟨xi,θ⟩u_i,θ:= x_i,θ and, for each i, the recentered function ψi(u):=(yi−u)2−(yi−0)2=u2−2yiu,ψi(0)=0. _i(u)\;:=\; (y_i-u )^2- (y_i-0 )^2\;=\;u^2-2\,y_i\,u, _i(0)=0. Since [σi]=0 *E[ _i]=0, the constant offsets (yi−0)2\(y_i-0)^2\ vanish in the Rademacher average. Thus RadS(ℱBθ)=σ[sup‖θ‖≤Bθ1n∑i=1nσiψi(ui,θ)].Rad_S(F_B_θ)\;=\; *E_σ [ _\|θ\|≤ B_θ\ 1n _i=1^n _i\, _i\! (u_i,θ ) ]. We now bound the Lipschitz constants of ψi _i over the relevant range. For any u,v∈[−BθR,BθR]u,v∈[-B_θR,B_θR], |ψi(u)−ψi(v)|=|(u−v)[(u−yi)+(v−yi)]|≤|u−v|(|u−yi|+|v−yi|)≤ 2(Ymax+BθR)|u−v|. | _i(u)- _i(v) |= |\,(u-v)\, [(u-y_i)+(v-y_i) ]\, |\ ≤\ |u-v|\; (\,|u-y_i|+|v-y_i|\, )\ ≤\ 2(Y_ +B_θR)\,|u-v|. Hence each ψi _i is L–Lipschitz with L:= 2(Ymax+BθR),ψi(0)=0.L\;:=\;2(Y_ +B_θR), _i(0)=0. By the Ledoux–Talagrand contraction inequality (applied elementwise to ψi\ _i\ with common Lipschitz constant L and ψi(0)=0 _i(0)=0), we have RadS(ℱBθ)≤L⋅σ[sup‖θ‖≤Bθ1n∑i=1nσiui,θ]=L⋅RadS(Bθ),Rad_S(F_B_θ)\;≤\;L· *E_σ [ _\|θ\|≤ B_θ\ 1n _i=1^n _i\,u_i,θ ]\;=\;L·Rad_S(G_B_θ), where Bθ:=(x,y)↦⟨x,θ⟩:‖θ‖≤BθG_B_θ:=\(x,y) x,θ :\ \|θ\|≤ B_θ\ is the linear class (note: dependence on y disappears). The empirical Rademacher average of BθG_B_θ on S is standard: RadS(Bθ)=σ[sup‖θ‖≤Bθ1n∑i=1nσi⟨xi,θ⟩]=Bθnσ‖∑i=1nσixi‖≤Bθnσ‖∑i=1nσixi‖2=Bθn∑i=1n‖xi‖2.Rad_S(G_B_θ)= *E_σ [ _\|θ\|≤ B_θ\ 1n _i=1^n _i\, x_i,θ ]= B_θn\, *E_σ \| _i=1^n _ix_i \|\ ≤\ B_θn\, *E_σ \| _i=1^n _ix_i \|^2= B_θn\, _i=1^n\|x_i\|^2. Using ‖xi‖≤R\|x_i\|≤ R, we conclude RadS(Bθ)≤BθR/nRad_S(G_B_θ)≤ B_θR/ n. Combining, RadS(ℱBθ)≤L⋅RadS(Bθ)≤ 2(Ymax+BθR)BθRn.Rad_S(F_B_θ)\ ≤\ L·Rad_S(G_B_θ)\ ≤\ 2(Y_ +B_θR)\; B_θR n. Taking expectation over the sample (or simply noting that this bound holds for any S satisfying ‖xi‖≤R\|x_i\|≤ R) yields Rn(ℱBθ)≤ 2(Ymax+BθR)BθRn.R_n(F_B_θ)\ ≤\ 2(Y_ +B_θR)\; B_θR n. Apply Theorem 4.10 and choose δ. By Theorem 4.10, for any δ>0δ>0, sup‖θ‖≤Bθ|L^i,true(θ)−ℛ(θ)|≤ 2Rn(ℱBθ)+δ≤4(Ymax+BθR)BθRn+δ, _\|θ\|≤ B_θ\ | L_i,true(θ)-R(θ) |\ ≤\ 2\,R_n(F_B_θ)+δ\ ≤\ 4(Y_ +B_θR)\,B_θR n+δ, with probability at least 1−exp(−nδ22bu2)1- \! (- n\,δ^22b_u^2 ). Set δ=bu2log(2/κ)nδ\!=\!b_u\, 2 (2/κ)n so that exp(−nδ22bu2)=exp(−log(2/κ))=κ/2 \! (- n\,δ^22b_u^2 )= \! (- (2/κ) )=κ/2. The stated deviation bound Λu _u follows. ∎ Lemma 19 (Concentration of Δn2 _n^2 under Accurate Probing). Assume that |y~|≤Ymax,probe| y|≤ Y_ ,probe almost surely (e.g., Ymax,probe=Rmaxj‖θj0‖Y_ ,probe\!=\!R\, _j\| _j^0\| for linear peers at initialization). Then for any κ∈(0,1)κ∈(0,1), with probability at least 1−κ/21-κ/2, Δn2≤B+C022log(2/κ)n,whereC0:=Ymax+Ymax,probe. _n^2\;≤\;B\;+\;C_0^2\, 2 (2/κ)n, C_0\;:=\;Y_ +Y_ ,probe. Proof. Let W=(y~−y)2W=( y-y)^2. By the boundedness assumptions, 0≤W≤(Ymax+Ymax,probe)2=:U0≤ W≤(Y_ +Y_ ,probe)^2=:U almost surely, and [W]≤B *E[W]≤ B by Accurate Probing. By Hoeffding’s inequality, Pr(1n∑q=1nWq−[W]≥t)≤exp(−2nt2U2). \! ( 1n _q=1^nW_q- *E[W]≥ t )\;≤\; \! (- 2nt^2U^2 ). Choosing t=U2log(2/κ)nt=U 2 (2/κ)n yields Pr(Δn2≥[W]+U2log(2/κ)n)≤κ/2 \! ( _n^2≥ *E[W]+U 2 (2/κ)n )≤κ/2. Using [W]≤B *E[W]≤ B gives the stated bound with C02=UC_0^2=U. ∎ Lemma 20 (A priori norm bound and choice of BθB_θ). For any probing learner i∈Ui∈ U, ‖θ~i‖≤BθwithBθ:=2(Ymax2+pYmax,probe2)λp.\| θ_i\|\;≤\;B_θ B_θ\;:=\; 2(Y_ ^2+p\,Y_ ,probe^2)λ\,p. Proof of Lemma 20. At any stationary point Θ~ , θ~i θ_i minimizes the convex function Φ^iprobe(θ;Θ~):=ταiz∼i[ℓ(z,θ)]+(1−τ)ai(Θ~)z∼i(Θ~)[ℓ(z,θ)]+pL^i(θ)+λp2‖θ‖2. _i^probe(θ; )\;:=\;τ _i\,E_z _i [ (z,θ) ]\;+\;(1-τ)\,a_i( )\,E_z _i( ) [ (z,θ) ]\;+\;p\, L_i(θ)\;+\; λ\,p2\,\|θ\|^2. By optimality of θ~i θ_i for Φ^iprobe(⋅;Θ~) _i^probe(·; ), Φ^iprobe(θ~i;Θ~)≤Φ^iprobe(0;Θ~). _i^probe( θ_i; )≤ _i^probe(0; ). Using squared loss and |y|≤Ymax|y|≤ Y_ , we have L^i(0)=1n∑q=1n(y~iq)2≤Ymax,probe2. L_i(0)= 1n _q=1^n( y_i^q)^2≤ Y_ ,probe^2. Hence, λp2‖θ~i‖2≤ταiYmax2+(1−τ)ai(Θ~)Ymax2+pL^i(0)≤Ymax2+pYmax,probe2. λ\,p2\,\| θ_i\|^2\;≤\;τ _i\,Y_ ^2\;+\;(1-τ)\,a_i( )\,Y_ ^2\;+\;p\, L_i(0)\;≤\;Y_ ^2+p\,Y_ ,probe^2. Thus ‖θ~i‖≤2(Ymax2+pYmax,probe2)λp=Bθ.\| θ_i\|\;≤\; 2(Y_ ^2+p\,Y_ ,probe^2)λ\,p\;=\;B_θ. ∎ Appendix F Cross-Entropy Loss: Performance Guarantee Notation. In this section, we provide a high-probability upper bound on the full-population cross-entropy risk for a probing learner in MSGD-P at a stationary point. The proof mirrors the squared-loss analysis, with key differences arising from the geometry of the softmax and cross-entropy. Throughout this section, let K denote the number of classes. Let θ≡W∈ℝK×dθ≡ W ^K× d be the matrix of class-wise linear weights and define logits z(x)=Wx∈ℝKz(x)=Wx ^K and predicted probabilities qW(x)=softmax(z(x))q_W(x)=softmax(z(x)). The multiclass cross-entropy loss is ℓCE((x,y),W)=−∑c=1KyclogqW(x)c=−logqW(x)Y, _CE((x,y),W)\;=\;- _c=1^Ky_c\, q_W(x)_c\;=\;- q_W(x)_Y, where y∈e1,…,eKy∈\e_1,…,e_K\ is one-hot and Y is the true class index. We assume ‖x‖≤R\|x\|≤ R almost surely. For a probing learner i∈Ui∈ U (with probing weight p>0p>0), we define its augmented objective at Θ (as per MSGD-P) by Φi(W;Θ)= _i(W; )\;=\; ταi(x,y)∼i[ℓCE((x,y),W)] \;τ _i\, *E_(x,y) _i [ _CE((x,y),W) ] +(1−τ)ai(Θ)(x,y)∼i(Θ)[ℓCE((x,y),W)] \;\;+\;(1-τ)\,a_i( )\, *E_(x,y) _i( ) [ _CE((x,y),W) ] +pL^probe(W)+λp2‖W‖F2, \;\;+\;p\, L_probe(W)\;+\; λ\,p2\,\|W\|_F^2, where L^probe(W)=1n∑q=1nℓCE((x~iq,y~iq),W)=−1n∑q=1n∑c=1Ky~i,cqlogqW(x~iq)c. L_probe(W)\;=\; 1n\, _q=1^n _CE (( x_i^q, y_i^q),W )\;=\;- 1n _q=1^n _c=1^K y_i,c^q q_W( x_i^q)_c. Here (x~iq)q=1n\( x_i^q)\_q=1^n are probing covariates drawn i.i.d. from XP_X, and y~iqq=1n\ y_i^q\_q=1^n are soft pseudo-labels. For analysis, let yiqy_i^q be the (hidden) true labels of x~iq x_i^q, and define the empirical “true” probing CE: L^true(W)=1n∑q=1nℓCE((x~iq,yiq),W)=−1n∑q=1nlogqW(x~iq)yiq. L_true(W)\;=\; 1n\, _q=1^n _CE (( x_i^q,y_i^q),W )\;=\;- 1n _q=1^n q_W( x_i^q)_y_i^q. Let θ⋆∈argminWℛ(W)θ ∈ _WR(W) be a (finite-norm) population minimizer of the unregularized CE risk ℛ(W)=[ℓCE((x,y),W)]R(W)= *E[ _CE((x,y),W)], with ϵ:=ℛ(θ⋆)ε:=R(θ ) and ∥θ⋆∥F=:M⋆<∞\|θ \|_F=:M_ <∞. Aggregation Rule. we define peer logits zj(x,Θ)=θj0x∈ℝKz_j(x, )= _j^0x ^K and the coordinatewise median of logits z~c(x,Θ):=median(zj,c(x,Θ):j∈Ti(x)),c∈[K]. z_c(x, ):=median(z_j,c(x, ):j∈ T_i(x)), c∈[K]. Then, we set the probing label as yagg,i(x,Θ)=softmax(z~(x,Θ))y_agg,i(x, )=softmax( z(x, )). F.1 Accurate Probing Assumption and Proofs Scenario Ti(x)T_i(x) B Majority-good [m][m] ϵ+2Rrε+2Rr Market-leader j∗\j \ ξ Partial knowledge G ϵ+2Rrε+2Rr Preference-aware π(x)\π(x)\ ϵε Table 2: Probing accuracy parameters for cross-entropy loss. Assumption 6 (Accurate Probing for CE). There exists BCE≥0B_CE≥ 0 such that [CE(y,y~)]=[−logy~Y]≤BCE, *E [CE(y, y) ]\;=\; *E [- y_Y ]\;≤\;B_CE, where the expectation is over (x,y)∼(x,y) and y~=y~(x) y= y(x) produced by the robust aggregator. We now present sufficient conditions ensuring Assumption 6. Lemma 21 (Sufficient conditions for Accurate Probing (CE)). Assumption 6 holds in each of the following scenarios: (i) Majority-good. Suppose strictly more than half of peers satisfy ‖θj0−θ⋆‖F≤r\| _j^0-θ \|_F≤ r. Then BCE=[−logy~Y]≤ϵ+ 2Rr.B_CE\;=\; *E [- y_Y ]\;≤\;ε\;+\;2\,R\,r. (i) Market-leader. Suppose learner i probes a single peer j⋆j with [ℓCE((x,y),θj⋆0)]≤ξ *E[ _CE((x,y), _j ^0)]≤ξ. If y~(x)=qθj⋆0(x) y(x)=q_ _j ^0(x), then BCE≤ξB_CE≤ξ. (i) Partial knowledge. If a known subset G of peers satisfies |G|>(m−1)/2|G|>(m-1)/2 and ‖θj0−θ⋆‖F≤r\| _j^0-θ \|_F≤ r for all j∈Gj∈ G, and the aggregator uses the coordinatewise median over G, the same bound as in case (i) holds. (iv) Preference-aware. Suppose each peer j solves the ERM on its preference partition jP_j: θ¯j∈argminW(x,y)∼j[ℓCE((x,y),W)]. θ_j∈ _W\; *E_(x,y) _j [ _CE((x,y),W) ]. If learner i probes y~(x)=qθ¯π(x)(x) y(x)=q_ θ_π(x)(x), then BCE≤∑j=1Kαjj[ℓCE((x,y),θ¯j)]≤ϵ.B_CE\;≤\; _j=1^K _j\, *E_P_j [ _CE((x,y), θ_j) ]\;≤\;ε. Proof. We treat each scenario in turn. (i) Majority-good. Fix any x with ‖x‖≤R\|x\|≤ R and write z⋆(x)=θ⋆xz (x)=θ x. For any good peer j (i.e., ‖θj0−θ⋆‖F≤r\| _j^0-θ \|_F≤ r) and any class c, |zj,c(x)−zc⋆(x)|=|(θj,c0−θc⋆)⊤x|≤‖θj,c0−θc⋆‖2⋅‖x‖≤‖θj0−θ⋆‖F⋅‖x‖≤rR.|z_j,c(x)-z _c(x)|\;=\;|( _j,c^0-θ _c) x|\;≤\;\| _j,c^0-θ _c\|_2·\|x\|\;≤\;\| _j^0-θ \|_F·\|x\|\;≤\;r\,R. Since strictly more than half of the zj,c(x)j≠i\z_j,c(x)\_j≠ i lie in [zc⋆(x)−rR,zc⋆(x)+rR][z _c(x)\!-\!rR,\;z _c(x)\!+\!rR], their coordinatewise median must also lie in this interval. Hence ‖z~(x)−z⋆(x)‖∞≤rR.\| z(x)-z (x)\|_∞\;≤\;r\,R. Let f(z)=−logsoftmax(z)Yf(z)=- (z)_Y. By Lemma 22, −logy~Y=f(z~(x))≤f(z⋆(x))+2‖z~(x)−z⋆(x)‖∞≤−logqY⋆(x)+2rR,- y_Y\;=\;f( z(x))\;≤\;f (z (x) )+2\,\| z(x)-z (x)\|_∞\;≤\;- q _Y(x)+2\,r\,R, where q⋆=softmax(z⋆)q =softmax(z ). Taking expectations over (x,y)∼(x,y) , we get BCE=[−logy~Y]≤[−logqY⋆(x)]+2rR=ϵ+2rR.B_CE\;=\; *E [- y_Y ]\;≤\; *E [- q _Y(x) ]+2\,r\,R\;=\;ε+2\,r\,R. (i) Market-leader. Direct: BCE=[−logy~Y]=[ℓCE((x,y),θj⋆0)]≤ξB_CE= *E[- y_Y]= *E[ _CE((x,y), _j ^0)]≤ξ. (i) Partial knowledge. The proof is identical to case (i), restricting the median to G. Since |G|>(m−1)/2|G|>(m-1)/2 and all learners in G satisfy ‖θj0−θ⋆‖F≤r\| _j^0-θ \|_F≤ r, the coordinatewise median over G satisfies the same bound. (iv) Preference-aware. By optimality of θ¯j θ_j for the ERM objective, j[ℓCE((x,y),θ¯j)]≤j[ℓCE((x,y),θ⋆)]. *E_P_j [ _CE((x,y), θ_j) ]\;≤\; *E_P_j [ _CE((x,y),θ ) ]. Summing over j with weights αj _j gives BCE≤∑jαjjℓCE(θ¯j)≤∑jαjjℓCE(θ⋆)=ϵ.B_CE\;≤\; _j _j *E_P_j _CE( θ_j)\;≤\; _j _j *E_P_j _CE(θ )\;=\;ε. ∎ Lemma 22 (CE is 2-Lipschitz in logits under ∥⋅∥∞\|·\|_∞). Fix a class Y∈[K]Y∈[K] and define f(z):=−logsoftmax(z)Y=−zY+logsumexp(z)f(z):=- (z)_Y=-z_Y+logsumexp(z) for z∈ℝKz ^K. Then for any z,z′∈ℝKz,z ^K, |f(z′)−f(z)|≤ 2‖z′−z‖∞. |f(z )-f(z) |\;≤\;2\,\|z -z\|_∞. Proof. We have ∇f(z)=q(z)−eY∇ f(z)=q(z)-e_Y, where q(z)=softmax(z)q(z)=softmax(z) and eYe_Y is the one-hot at Y. By the mean value inequality with dual norms (∥⋅∥∞,∥⋅∥1)(\|·\|_∞,\|·\|_1), |f(z′)−f(z)|≤supξ∈[z,z′]‖∇f(ξ)‖1⋅‖z′−z‖∞=supξ∑k=1K|qk(ξ)−(eY)k|⋅‖z′−z‖∞.|f(z )-f(z)|\;≤\; _ξ∈[z,z ]\|∇ f(ξ)\|_1·\|z -z\|_∞\;=\; _ξ _k=1^K|q_k(ξ)-(e_Y)_k|·\|z -z\|_∞. Since y=eYy=e_Y is one-hot and q∈ΔK−1q∈ ^K-1, ∑k=1K|qk−(eY)k|=|qY−1|+∑k≠Yqk=(1−qY)+(1−qY)≤2. _k=1^K|q_k-(e_Y)_k|=|q_Y-1|+ _k≠ Yq_k=(1-q_Y)+(1-q_Y)≤ 2. Hence |f(z′)−f(z)|≤2‖z′−z‖∞|f(z )-f(z)|≤ 2\,\|z -z\|_∞. ∎ F.2 Performance Bound We will use two probability floors: γ⋆:=1Kexp(−2R‖θ⋆‖F),Γ⋆:=log1γ⋆=logK+2R‖θ⋆‖F, _ \;:=\; 1K\, (-2R\,\|θ \|_F ), _ \;:=\; 1 _ \;=\; K+2R\|θ \|_F, and Bθ:=2(1+p)logKλp,γB:=1Kexp(−2RBθ),ΓB:=log1γB=logK+2RBθ.B_θ\;:=\; 2(1+p) Kλ\,p, _B\;:=\; 1K\, (-2R\,B_θ ), _B\;:=\; 1 _B\;=\; K+2RB_θ. Corollary 2 (Big-O summary). Under the assumptions of Theorem 5, with probability at least 1−κ1-κ, ℛ(θ~i)≤O((p+1p)ϵ+λ‖θ⋆‖F2+CbiasBCE+(p+1)Cgenplog(1/κ)λn),R( θ_i)≤ O\! ( ( p+1p )ε\;+\;λ\,\|θ \|_F^2\;+\;C_bias\, B_CE\;+\; (p+1)\,C_genp\, (1/κ)λ n ), where the constant Cbias=R(‖θ⋆‖F+2logK/λ)C_bias=R (\|θ \|_F+ 2 K/λ ) and Cgen=Cgen(R,‖θ⋆‖,log(K))C_gen=C_gen(R,\|θ \|, (K)) is specified in the appendix. Theorem 5 (CE performance bound with probing). Let Assumptions 1, 2, 3, 4, and 6 hold. Let Θ~ be a stationary point of MSGD-P and let θ~i θ_i be the parameter for a probing learner i∈Ui∈ U. Then for any κ∈(0,1)κ∈(0,1), with probability at least 1−κ1-κ over the probing sample, ℛ(θ~i)≤ ( θ_i)≤\, (1+1p)ϵ+λ2‖θ⋆‖F2+R(‖θ⋆‖F+Bθ)2BCE+4R(1+p)KlogKλpn (1+ 1p )ε+ λ2\|θ \|_F^2+R(\|θ \|_F+B_θ) 2B_CE+4R (1+p)K Kλ\,p\,n +(Γ⋆+ΓB+R(‖θ⋆‖F+Bθ))log(3/κ)2n. + ( _ + _B+R(\|θ \|_F+B_θ) ) (3/κ)2n. Proof. We work on the event ℰpinsker∩ℰ⋆∩ℰuE_pinsker _ _u where: • ℰpinskerE_pinsker is the event of Lemma 25 (probability ≥1−κ/3≥ 1-κ/3), • ℰ⋆E_ is the event of Lemma 26 (probability ≥1−κ/3≥ 1-κ/3), • ℰuE_u is the event of Lemma 27 (probability ≥1−κ/3≥ 1-κ/3). By a union bound, ℙ(ℰpinsker∩ℰ⋆∩ℰu)≥1−κ.P(E_pinsker _ _u)≥ 1-κ. Bound on L^probe(θ~i) L_probe( θ_i). By Lemma 23, dividing by p, L^probe(θ~i)≤ϵp+L^probe(θ⋆)+λ2‖θ⋆‖F2. L_probe( θ_i)\;≤\; εp\;+\; L_probe(θ )\;+\; λ2\,\|θ \|_F^2. By Corollary 29 applied at W=θ⋆W=θ and Lemma 26, L^probe(θ⋆)≤L^true(θ⋆)+R‖θ⋆‖FΔ1,n≤ϵ+Γ⋆log(3/κ)2n+R‖θ⋆‖FΔ1,n. L_probe(θ )\;≤\; L_true(θ )\;+\;R\,\|θ \|_F\, _1,n\;≤\;ε\;+\; _ \, (3/κ)2n\;+\;R\,\|θ \|_F\, _1,n. Hence L^probe(θ~i)≤ϵp+ϵ+λ2‖θ⋆‖F2+Γ⋆log(3/κ)2n+R‖θ⋆‖FΔ1,n. L_probe( θ_i)\;≤\; εp+ε\;+\; λ2\,\|θ \|_F^2\;+\; _ \, (3/κ)2n\;+\;R\,\|θ \|_F\, _1,n. Bound on L^true(θ~i) L_true( θ_i). By Corollary 29 at W=θ~iW= θ_i, L^true(θ~i)≤L^probe(θ~i)+R‖θ~i‖FΔ1,n. L_true( θ_i)\;≤\; L_probe( θ_i)\;+\;R\,\| θ_i\|_F\, _1,n. Substituting the bound from the previous step, L^true(θ~i)≤ϵp+ϵ+λ2‖θ⋆‖F2+Γ⋆log(3/κ)2n+R(‖θ⋆‖F+‖θ~i‖F)Δ1,n. L_true( θ_i)\;≤\; εp+ε\;+\; λ2\,\|θ \|_F^2\;+\; _ \, (3/κ)2n\;+\;R\,(\|θ \|_F+\| θ_i\|_F)\, _1,n. On ℰpinskerE_pinsker, by Lemma 25, Δ1,n≤2BCE+log(3/κ)2n. _1,n\;≤\; 2B_CE\;+\; (3/κ)2n. Therefore, L^true(θ~i)≤ϵp+ϵ+λ2‖θ⋆‖F2+R(‖θ⋆‖F+Bθ)2BCE+(Γ⋆+R(‖θ⋆‖F+Bθ))log(3/κ)2n. L_true( θ_i)\;≤\; εp+ε\;+\; λ2\,\|θ \|_F^2\;+\;R\,(\|θ \|_F+B_θ)\, 2B_CE\;+\; ( _ +R\,(\|θ \|_F+B_θ) )\, (3/κ)2n. Bound on ℛ(θ~i)R( θ_i). By Lemma 27, on ℰuE_u and since ‖θ~i‖≤Bθ\| θ_i\|≤ B_θ by Lemma 24, ℛ(θ~i)≤L^true(θ~i)+ 22RBθKn+ΓBlog(3/κ)2n.R( θ_i)\;≤\; L_true( θ_i)\;+\;2 2\,RB_θ Kn\;+\; _B\, (3/κ)2n. Combining with the previous bound and substituting Bθ=2(1+p)logK/(λp)B_θ= 2(1+p) K/(λ\,p) (which yields 22RBθK/n=4R(1+p)(KlogK)/(λpn)2 2RB_θ K/n=4R (1+p)(K K)/(λ\,p\,n)) gives the stated bound. ∎ Lemma 23 (Stationarity bound). At a stationary point Θ~ , for learner i∈Ui∈ U, pL^probe(θ~i)≤ϵ+pL^probe(θ⋆)+λp2‖θ⋆‖F2.p\, L_probe( θ_i)\;≤\;ε\;+\;p\, L_probe(θ )\;+\; λ\,p2\,\|θ \|_F^2. Proof of Lemma 23. By optimality of θ~i θ_i for Φi(⋅;Θ~) _i(·; ), Φi(θ~i;Θ~)≤Φi(θ⋆;Θ~). _i( θ_i; )\;≤\; _i(θ ; ). Subtracting the two population CE terms at W=θ~iW= θ_i and W=θ⋆W=θ , and using that ταiiℓCE(θ⋆)+(1−τ)ai(Θ~)i(Θ~)ℓCE(θ⋆)≤ϵ,τ _i\, *E_P_i _CE(θ )\;+\;(1-τ)\,a_i( )\, *E_D_i( ) _CE(θ )\;≤\;ε, we obtain the stated bound. ∎ Lemma 24 (Norm bound and probability floor). We have ‖θ~i‖F≤Bθ=2(1+p)logK/(λp)\| θ_i\|_F≤ B_θ= 2(1+p) K/(λ\,p). Consequently, for any x, minc∈[K]qθ~i(x)c≥γB=1Kexp(−2RBθ),ΓB=log1γB=logK+2RBθ. _c∈[K]q_ θ_i(x)_c\;≥\; _B\;=\; 1K (-2RB_θ ), _B\;=\; 1 _B\;=\; K+2RB_θ. Proof of Lemma 24. Compare Φi(θ~i;Θ~) _i( θ_i; ) to Φi(0;Θ~) _i(0; ). For W=0W=0, qWq_W is uniform and each CE term equals logK K. Thus λp2‖θ~i‖F2≤(1+p)logK⇒‖θ~i‖F≤2(1+p)logKλp. λ\,p2\,\| θ_i\|_F^2\;≤\;(1+p)\, K \| θ_i\|_F\;≤\; 2(1+p) Kλ\,p. For the floor, write for any c,c′c,c : |zc−zc′|=|(Wc−Wc′)⊤x|≤‖Wc−Wc′‖‖x‖≤ 2‖W‖F‖x‖≤ 2R‖W‖F.|z_c-z_c |\;=\;|(W_c-W_c ) x|\;≤\;\|W_c-W_c \|\,\|x\|\;≤\;2\,\|W\|_F\,\|x\|\;≤\;2R\|W\|_F. Hence qW(x)c≥1Kexp(−2R‖W‖F)q_W(x)_c≥ 1K (-2R\|W\|_F). ∎ Lemma 25 (Pseudo-label discrepancy). Let Δ1,n=1n∑q=1n‖y~iq−yiq‖1 _1,n= 1n _q=1^n\| y_i^q-y_i^q\|_1. Under Assumption 6, for any κ∈(0,1)κ∈(0,1), with probability at least 1−κ/31-κ/3, Δ1,n≤2BCE+log(3/κ)2n. _1,n\;≤\; 2B_CE\;+\; (3/κ)2n. Proof of Lemma 25. For one-hot y, CE(y,y~)=KL(y∥y~)CE(y, y)=KL(y\| y) and Pinsker gives ‖y−y~‖1≤2KL(y∥y~)≤2BCE *E\|y- y\|_1≤ 2\, *EKL(y\| y)≤ 2B_CE. Since ‖y−y~‖1∈[0,2]\|y- y\|_1∈[0,2], Hoeffding yields the stated bound. ∎ Lemma 26 (Concentration at θ⋆θ ). With probability at least 1−κ/31-κ/3, |L^true(θ⋆)−ϵ|≤Γ⋆log(3/κ)2n, | L_true(θ )-ε |\;≤\; _ \, (3/κ)2n, where Γ⋆=logK+2R‖θ⋆‖F _ = K+2R\|θ \|_F. Proof of Lemma 26. By Lemma 24 applied to W=θ⋆W=θ , mincqθ⋆(x)c≥γ⋆ _cq_θ (x)_c≥ _ , hence ℓCE((x,y),θ⋆)∈[0,Γ⋆] _CE((x,y),θ )∈[0, _ ]. Hoeffding’s inequality gives the result. ∎ Lemma 27 (Uniform convergence). With probability at least 1−κ/31-κ/3, sup‖W‖F≤Bθ|L^true(W)−ℛ(W)|≤ 22RBθKn+ΓBlog(3/κ)2n. _\|W\|_F≤ B_θ\, | L_true(W)-R(W) |\;≤\;2 2\,R\,B_θ\, Kn\;+\; _B\, (3/κ)2n. Proof of Lemma 27. For any sample (xi,yi)i=1n\(x_i,y_i)\_i=1^n with ‖xi‖≤R\|x_i\|≤ R, we bound the empirical Rademacher complexity of ℱBθ:=(x,y)↦ℓCE((x,y),W):‖W‖F≤Bθ.F_B_θ\;:=\; \(x,y) _CE((x,y),W):\|W\|_F≤ B_θ \. The function f(z,y)=−logsoftmax(z)Yf(z,y)=- (z)_Y has gradient ∇zf=q−y _zf=q-y with ‖∇zf‖2=‖q−y‖2≤2\| _zf\|_2=\|q-y\|_2≤ 2. Thus f is 2 2-Lipschitz in z. By the vector contraction lemma, ℜn(ℱBθ)≤2⋅[sup‖W‖F≤Bθ1n∑i=1n∑k=1Kσi,k(Wxi)k], R_n(F_B_θ)\;≤\; 2· *E [ _\|W\|_F≤ B_θ 1n _i=1^n _k=1^K _i,k\,(Wx_i)_k ], with σi,k _i,k i.i.d. Rademacher. The inner supremum equals Bθn‖∑i=1n∑k=1Kσi,kekxi⊤‖F≤Bθn‖∑i,kσi,kekxi⊤‖F2=Bθn∑k=1K∑i=1n‖xi‖2≤BθRKn. B_θn\, *E \| _i=1^n _k=1^K _i,k\,e_kx_i \|_F\;≤\; B_θn\, *E \| _i,k _i,k\,e_kx_i \|_F^2\;=\; B_θn\, _k=1^K _i=1^n\|x_i\|^2\;≤\;B_θR\, Kn. Hence ℜn(ℱBθ)≤2BθRK/n R_n(F_B_θ)≤ 2\,B_θR K/n. A standard symmetrization and bounded-difference argument (the per-sample loss range over ‖W‖≤Bθ\|W\|≤ B_θ is at most ΓB _B by Lemma 24) yields, with prob. ≥1−κ/3≥ 1-κ/3, sup‖W‖F≤Bθ|L^true(W)−ℛ(W)|≤ 2ℜn(ℱBθ)+ΓBlog(3/κ)2n, _\|W\|_F≤ B_θ\, | L_true(W)-R(W) |\;≤\;2\, R_n(F_B_θ)\;+\; _B\, (3/κ)2n, which gives the stated bound. ∎ Lemma 28 (Logits bridge for cross-entropy; no probability floors). Let W∈ℝK×dW ^K× d, z(x)=Wx∈ℝKz(x)=Wx ^K, and qW(x)=softmax(z(x))q_W(x)=softmax(z(x)). For any x∈ℝdx ^d, any one-hot label y∈e1,…,eKy∈\e_1,…,e_K\, and any soft pseudo-label y~∈ΔK−1 y∈ ^K-1 (i.e., y~c≥0 y_c≥ 0, ∑cy~c=1 _c y_c=1), the cross-entropy difference satisfies the exact identity CE(y~,qW)−CE(y,qW)=−⟨y~−y,z(x)⟩.CE( y,q_W)-CE(y,q_W)\;=\;-\, y-y,\;z(x) . Consequently, |CE(y~,qW)−CE(y,qW)|≤‖y~−y‖1⋅‖z(x)‖∞≤‖y~−y‖1⋅R‖W‖F. |CE( y,q_W)-CE(y,q_W) |\;≤\;\| y-y\|_1·\|z(x)\|_∞\;≤\;\| y-y\|_1· R\,\|W\|_F. Proof. Recall that CE(r,q)=−∑c=1KrclogqcCE(r,q)=- _c=1^Kr_c q_c for any probability vector r, and qc=ezc∑jezjq_c= e^z_c _je^z_j with z=Wxz=Wx. Hence −logqc=log(∑j=1Kezj)−zc=logsumexp(z)−zc.- q_c\;=\; ( _j=1^Ke^z_j )-z_c\;=\;logsumexp(z)-z_c. Therefore, for any r∈ΔK−1r∈ ^K-1, CE(r,qW)=∑c=1Krc(logsumexp(z)−zc)=logsumexp(z)⋅∑c=1Krc⏟= 1−∑c=1Krczc=logsumexp(z)−⟨r,z⟩.CE(r,q_W)\;=\; _c=1^Kr_c\, (logsumexp(z)-z_c )\;=\;logsumexp(z)· _c=1^Kr_c_=\,1\;-\; _c=1^Kr_c\,z_c\;=\;logsumexp(z)\;-\; r,z . Applying this twice with r=y~r= y and r=yr=y gives CE(y~,qW)−CE(y,qW)=(logsumexp(z)−⟨y~,z⟩)−(logsumexp(z)−⟨y,z⟩)=−⟨y~−y,z⟩,CE( y,q_W)-CE(y,q_W)\;=\; (logsumexp(z)- y,z )\;-\; (logsumexp(z)- y,z )\;=\;-\, y-y,z , which is the claimed identity. For the inequalities, use Hölder and the fact that ‖z‖∞=maxc|zc|\|z\|_∞= _c|z_c|: |CE(y~,qW)−CE(y,qW)|=|⟨y~−y,z⟩|≤‖y~−y‖1‖z‖∞. |CE( y,q_W)-CE(y,q_W) |\;=\;| y-y,z |\;≤\;\| y-y\|_1\,\|z\|_∞. Finally, since zc=Wc⊤xz_c=W_c x and ‖x‖≤R\|x\|≤ R, ‖z‖∞=maxc|Wc⊤x|≤maxc‖Wc‖2⋅‖x‖≤(maxc‖Wc‖2)R≤R‖W‖F,\|z\|_∞\;=\; _c|W_c x|\;≤\; _c\|W_c\|_2·\|x\|\;≤\; ( _c\|W_c\|_2 )\,R\;≤\;R\,\|W\|_F, because ‖W‖F2=∑c‖Wc‖22≥maxc‖Wc‖22\|W\|_F^2= _c\|W_c\|_2^2≥ _c\|W_c\|_2^2. Combining the bounds yields the result. ∎ Lemma 29 (Empirical bridge on the probing batch). On the probing dataset (x~iq,y~iq,yiq)q=1n\( x_i^q, y_i^q,y_i^q)\_q=1^n, define L^probe(W)=1n∑q=1nCE(y~iq,qW(x~iq)),L^true(W)=1n∑q=1nCE(yiq,qW(x~iq)),Δ1,n=1n∑q=1n‖y~iq−yiq‖1. L_probe(W)\;=\; 1n _q=1^nCE( y_i^q,q_W( x_i^q)), L_true(W)\;=\; 1n _q=1^nCE(y_i^q,q_W( x_i^q)), _1,n\;=\; 1n _q=1^n\| y_i^q-y_i^q\|_1. Then for any W, |L^probe(W)−L^true(W)|≤R‖W‖F⋅Δ1,n. | L_probe(W)- L_true(W) |\;≤\;R\,\|W\|_F· _1,n. Proof. Apply Lemma 28 termwise and average. ∎ Appendix G Experimental Details and Additional Results G.1 Dataset and Preprocessing Details MovieLens-10M [Harper and Konstan, 2015]. This dataset contains 10 million movie ratings from 70k users across 10k movies, providing a natural testbed for multi-learner competition in recommendation. Following Bose et al. [2023] and Su and Dean [2024], we extract d=16d=16 dimensional user embeddings via matrix factorization and retain ratings for the top 200 most-rated movies, yielding a population of 69,474 users. Each user’s data consists of z=(x,r)z=(x,r) where x∈ℝdx ^d is the embedding and r contains their ratings. Let Ωx _x denote the set of movies rated by user x with |Ωx|| _x| movies. Each learner fits a linear model θ∈ℝd×200θ ^d× 200 using squared loss: ℓ(z;θ)=1|Ωx|∑i∈Ωx(θi⊤x−ri)2. (z;θ)= 1| _x| _i∈ _x( _i x-r_i)^2. ACS Employment [Ding et al., 2021]. We use the ACSEmployment task from folktables, where the goal is to predict employment status from demographic features. The population consists of 38,221 individuals from the 2018 Alabama census (ages 16–90), with d=16d=16 features describing age, education, marital status, etc. Each user’s data is z=(x,y)z=(x,y) where x∈ℝdx ^d (standardized to zero mean, unit variance) and y∈0,1y∈\0,1\. Each learner uses logistic regression: ℓ(z;θ)=−ylog(σ(θ⊤x))−(1−y)log(1−σ(θ⊤x)), (z;θ)=-y (σ(θ x))-(1-y) (1-σ(θ x)), where σ is the sigmoid function. The model predicts y^=[θ⊤x>0] y=1[θ x>0]. Amazon Reviews 2023. We use the McAuley-Lab/Amazon-Reviews-2023 corpus (via HuggingFace), constructing a binary sentiment task from review text and star ratings. We sample up to 30,000 reviews from nine product categories and define labels by y=[rating≥4]y=1[rating≥ 4] (so 1–3 stars are negative, 4–5 stars are positive). Features are d=384d=384 dimensional sentence embeddings of the review text produced by all-MiniLM-L6-v2, with a stratified 95/5 train-test split. Each learner uses the same logistic regression setup as Census. User Preferences. For Census and MovieLens, we simulate a market with m=5m=5 learners and model inherent user preferences π(z)π(z) via K-means clustering (K=5K=5) on user features, assigning each user’s preferred platform based on their cluster membership. For Amazon, we use category-based partitions (m=9m=9 learners, one per product category): each review is assigned to its category group, and this group index induces the preference partition Sii=1m\S_i\_i=1^m. In all cases, the partition captures the intuition that users from different demographic or behavioral segments may have systematic affinities for different platforms. Train/test splits. Each experiment constructs one held-out test set at the start and uses the remaining users as the shared training pool for all learners. Census uses a fixed 99/1 split with random seed 0; Amazon uses a stratified 95/5 split over sentiment labels; MovieLens uses a 90/10 user split. We do not use a validation split because the experimental hyperparameters are fixed in advance rather than tuned per run. Dataset-specific hyperparameters are summarized in Table 3. Census neural experiment. The neural Census experiment in Figure 6 changes only the learner family relative to the linear Census experiments. Each learner is a two-layer ReLU MLP with architecture d→64→1d\!→\!64\!→\!1, trained with SGD on binary cross-entropy. The held-out test split, K-means preference clusters, and cluster-induced learner rankings are reused unchanged. In the bad-outcome run, learners are randomly initialized, τ=0.3τ=0.3, and no learner probes. In the good-outcome run, learners are initialized by partition pretraining on the users who rank them first, τ=0.7τ=0.7, and Learner 2 probes. Probing is offline: pseudo-labels are collected once from the initialized peer selected by the preference-aware rule Ti(x)=π(x)T_i(x)=\π(x)\, with κ=0κ=0, and the probing learner then trains on the weighted combination of organic and pseudo-labeled losses. We use T=1000T=1000 MSGD iterations, three random seeds, and the probing weights shown in Figure 6. G.2 Additional Experiments In this section, we provide additional experiments, which elaborate on Section˜6. Expt 1 for other scenarios We replicate Expt 1 from Section˜6 in the two globally-good settings from Definition˜2: market-leader and majority-good. As in the preference-aware case, standard MSGD without probing (p=0p=0, τ=0.3τ=0.3) converges to equilibria with large full-population gaps to the dashed black baseline (Figures˜8 and 10). In the market-leader setting (Figure˜8), the most overspecialized learner is about 0.320.32 below baseline on Census (≈0.47≈ 0.47 vs ≈0.79≈ 0.79), and more than 2.62.6 MSE above baseline on MovieLens (>5.6>5.6 vs ≈2.95≈ 2.95). In the majority-good setting (Figure˜10), two learners remain overspecialized with sizable baseline gaps (Census around 0.220.22–0.250.25 below baseline; MovieLens around 2.02.0–2.92.9 above baseline). These results show that poor global equilibria are not unique to the preference-aware scenario. Expt 2 for other scenarios We next replicate Expt 2 for the other scenarios. In the market-leader scenario, Learner 44 probes the known leader (Learner 0), and its final Census accuracy improves from about 0.550.55 to about 0.750.75, while its MovieLens loss drops from about 5.15.1 to about 3.13.1 as p increases (Figure˜9). Relative to the dashed baseline, this closes most of the initial gap (roughly from 0.240.24 to 0.040.04 on Census, and from about 2.22.2 to about 0.10.1 on MovieLens). In the majority-good scenario, where Learner 44 probes via median aggregation over all peers, we observe a similar pattern: Census accuracy rises from about 0.520.52 to about 0.770.77, and MovieLens loss decreases from about 4.74.7 to about 3.13.1 (Figure˜11). This again closes a large fraction of the baseline gap (roughly from 0.270.27 to 0.020.02 on Census, and from about 1.71.7 to about 0.10.1 on MovieLens). Well-performing learners change only modestly, indicating that probing primarily benefits the underperforming learner and mitigates overspecialization. Expt 4: Impact of noise in selection of probed labels Finally, we test robustness to noisy probing-source selection. For each probe query x, the probing learner queries π(x)π(x) with probability 1−κ1-κ, and with probability κ it queries a random other learner. Across Census, Amazon, and MovieLens (Figure˜4), increasing κ causes only mild changes in the probing learner’s final performance relative to the low-noise case, while preserving strong gains from probing. Thus, our method is robust to imperfect estimates of the ranking function. Expt 5: What happens when multiple learners probe? We also evaluate a preference-aware setting where multiple learners probe simultaneously. In Figure˜12, the triangle-marked learners (Learners 22 and 33) both probe while the dashed black line indicates the full-data baseline. As p increases, Learner 22 improves from about 0.600.60 to about 0.780.78, and Learner 33 improves from about 0.660.66 to about 0.790.79. Equivalently, their baseline gaps shrink from roughly 0.190.19 and 0.130.13 at p=0p=0 to about 0.010.01 and near zero at p=0.8p=0.8. The non-probing learners move only slightly, indicating that simultaneous probing remains stable and still helps underperforming learners recover most of the overspecialization gap. Figure 7: Performance of probing learner on Census as a function of n. Error bars show one standard deviation over 10 random seeds. Parameter Description Census MovieLens Amazon m Number of learners 5 5 9 T Total rounds 4000 4000 20000 λ L2 regularization 10−910^-9 10−310^-3 10−910^-9 n Offline probe dataset size 100 1000 500 Table 3: Hyperparameters by dataset. Shared values are merged across columns. Figure 8: MSGD full-population performance with random initialization (Market-leader scenario). Left: Census test accuracy. Right: MovieLens test loss. Here τ=0.3τ=0.3. Figure 9: Effect of probing on full-population performance (Market-leader scenario) Left: Final accuracy vs probing weight p on Census. Right: MovieLens final loss vs p. The triangle markers indicate Learner 44 probes the market leader, learner 0. Here τ=0.7τ=0.7. Figure 10: MSGD full-population performance with random initialization (Majority good scenario). Left: Census test accuracy. Right: MovieLens test loss. Here τ=0.3τ=0.3. Figure 11: Effect of probing on full-population performance (Majority Good Scenario) Left: Final accuracy vs probing weight p on Census. Right: MovieLens final loss vs p. Triangle markers indicate Learner 44 is probing via median aggregation over all peers. Here τ=0.7τ=0.7. Figure 12: Effect of probing on full-population performance when multiple learners probe (Preference-aware scenario). Census final accuracy vs probing weight p. Triangle markers indicate the probing learners (Learners 22 and 33). The dashed black line denotes the full-data baseline.