Research map / Learning theory and algorithms / Prediction and decision losses

Learning from Streaming Data when Users Choose

ICML 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Ranking models from comparisons · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formalizes streaming users who choose among competing services with bounded rationality and proposes MSGD, a decentralized single-user gradient update, proving almost-sure convergence to stationary points of the overall user loss.

Problem

Competing services that update models incrementally from streaming user data face feedback loops, since user choices determine which data each service sees and each service observes only the users that choose it; the goal is to minimize average user loss under imperfectly rational user choice.

Approach

Users pick the lowest-loss service with probability 1-zeta and a uniform random service otherwise; each chosen service takes a single gradient step on the one user's loss. The paper shows the expected single-user update is parallel to the gradient of the overall loss, which yields convergence to stationary points of that objective.

Key results

• On ACSEmployment with k=3, MSGD achieves higher overall welfare than Full Information when zeta is small (high rationality), while Full Information wins when zeta is large.
• MSGD achieves higher accuracy on induced subpopulations than Full Information, and this accuracy grows with k, but whole-population accuracy is lower than Full Information.
• Convergence of the overall objective and iterates is shown almost surely under stepsize and compactness assumptions, with eta_t = eta_c/t for iterate convergence.

Measured effects reported in the paper

Surprising findings

• MSGD on the whole population can perform worse than Full Information, and whole-population accuracy can decrease with more training steps.
• Full Information converges more slowly than MSGD when users choose with high rationality.

Limitations

• Convergence guarantees only to stationary points of a non-convex objective, not global optima.
• Boltzmann-rational user choice is not covered theoretically; only shown empirically in appendix.
• Whole-population accuracy can be worse than full information due to specialization.

Experimental setup

Datasets: MovieLens10M ACSEmployment (folktables)

Benchmarks: MovieLens10M ACSEmployment (folktables)

Metrics: overall loss f(Theta) accuracy on induced subpopulation accuracy on whole population accumulated parameter update distance

Baselines: Full Information gradient descent

Builds on: performative prediction multi-player performative prediction stochastic gradient descent

Closest papers by meaning

• Initializing Services in Interactive ML Systems for Diverse Users (NeurIPS 2024 · similarity 0.86)
• Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets (NeurIPS 2025 · similarity 0.83)
• DICE: Data Influence Cascade in Decentralized Learning (ICLR 2025 · similarity 0.82)
• Streaming Stochastic Submodular Maximization with On-Demand User Requests (NeurIPS 2025 · similarity 0.82)
• Decongestion by Representation: Learning to Improve Economic Welfare in Marketplaces (ICLR 2024 · similarity 0.82)
• Adaptively Learning to Select-Rank in Online Platforms (ICML 2024 · similarity 0.82)