PaperlayerView exact revision on arXiv

Source-linked AI summary

Decoupled Learning and Selection in Slate Recommendation for Privacy and Stability Under Noisy Scores

Sam Urmian, Qinyi Liu, Mohammad Khalil

arXiv:2609.29453v1cs.LGcs.IR

TL;DR

Slate recommenders often apply deterministic selection after learned scoring, leaving privacy and score-stability guarantees dependent on the selector’s inputs and decisions. The paper formalizes those scopes and derives a logged margin certificate for unchanged ordered slates. Controlled tests support near-linear stability scaling, while real-anchor sweeps and certificate checks examine stability across datasets and closed-loop outcomes remain setting-dependent.

  • Problem

    Guarantees for a learned scorer do not by themselves characterize privacy, replay, or score sensitivity after deterministic slate selection.

    Source: §1 · p. 1

  • Method

    The paper separates a randomized score learner from deterministic selection and uses an input-admissibility contract for privacy plus a logged margin certificate for slate stability.

    Source: §1 · p. 1

  • Results

    The independent-Gaussian calibration fits slope -0.220 (95% tCI [-0.231, -0.210]) against the reference -1/4, supporting the predicted linear form with a slightly shallower finite-sample slope.

    Source: §6.3 · p. 7

  • Takeaways & Limitations

    The framework separates privacy inheritance from stability: a non-private anchor can support stability analysis, but does not provide end-to-end DP.

    Source: §7 · p. 7

    The released artifact does not establish the sampler or protected-unit clipping needed to verify nominal privacy configurations, so those comparisons are stress tests rather than verified privacy–utility curves.

    Source: §5.2 · p. 6, §7 · p. 8

Abstract

from arXiv · show

We formalize slate recommendation as a randomized score learner followed by deterministic selection. First, an appropriately scoped differential-privacy guarantee passes through selection and its audit trace by post-processing. End-to-end privacy holds only when selector inputs are public or independent, previous private outputs, or separately privacy-accounted; fixing raw state or candidate information instead yields only a conditional guarantee. Second, we derive a logged margin certificate: bounded score-induced objective movement below half the smallest greedy decision margin guarantees that the ordered slate is unchanged. Controlled fixed-margin tests show near-linear exponent scaling, with an empirical slope of $-0.220$ (95% CI $[-0.231,-0.210]$) against the independent-noise reference $-1/4$. Real-anchor experiments on OULAD, MovieLens-25M, and Amazon Musical Instruments show that greater anchor weight reduces score-noise-induced ranking churn. OULAD and EdNet certificate checks validate the implementation of the logged inequality, while closed-loop simulations show bounded target drift and setting-dependent downstream utility. The contribution is therefore a privacy-scope contract and a certifiable score-to-slate stability mechanism, not a universal utility claim.

1 Introduction

Slate recommendations often apply a deterministic rule layer after learned scoring, so guarantees for the scorer alone do not settle privacy, replay, or stability questions for the final list. The paper separates learning from selection and gives a privacy-scope contract and a logged margin certificate for ordered-slate stability.

1 Introduction

  • A recommender’s final list may depend on deterministic filtering, diversity, operational rules, and slate length, which scorer guarantees do not automatically cover.The paper separates questions about training-data privacy, replayability, and sensitivity of the final slate to score changes.Source: §1 · p. 1
  • End-to-end privacy requires selector inputs to be public or independent, previous DP outputs, or separately accounted; fixing raw state or candidate information yields only a conditional claim.A non-private anchor may support stability analysis but does not preserve end-to-end DP.Source: §1 · p. 1
  • Bounded score-induced objective movement below half the smallest positive stepwise margin certifies that a deterministic greedy selector’s ordered slate cannot change.The certificate uses logged margins and perturbation envelopes, and specializes to raw top-K and greedy-slate results under their stated assumptions.Source: §1 · p. 1
  • The contributions are a privacy-scope contract, a logged ordered-slate margin certificate, and mechanism-focused tests plus scoped closed-loop simulations.The testbed uses adaptive practice, with OULAD and EdNet for interaction-density contrasts and MovieLens-25M and Amazon Musical Instruments for raw score-stability checks.Source: §1 · p. 1

2 Setting and Model Class

The paper models slate recommendation as learned item scores followed by a deterministic selector with explicit state, side inputs, and bounded controls. This separation makes privacy scope, replay, drift, and score-to-slate stability distinct claims with distinct assumptions.

2.1 Setting

  • The setting has a candidate pool, selector inputs such as features and target proxies, and feedback on attempts and response success after a slate is shown.One exposure round is the protected record; user-level neighboring datasets differ in all rounds for a user.Source: §2.1 · p. 2
  • Selector inputs of the first three privacy statuses support end-to-end claims with applicable composition; explicitly conditioned inputs support only a conditional statement.A non-private anchor trained on protected data may support stability analysis but not end-to-end DP.Source: §2.1 · p. 2, §2.2 · p. 2

2.2 Two Operators: Learning and Selection

  • The learner maps logged interactions to item scores, while the deterministic selector maps scores, state, and bounded side inputs to a slate and audit trace.Privacy passes through selection only when every non-learner input meets the stated admissibility or accounting conditions.Source: §2.2 · p. 2, Figure 1 · p. 2

2.3 Governed Policy Class

  • The governed selector uses bounded target-shaping, exploration, diversity, and slate-size levers, then shapes scores, assembles a slate, and breaks ties deterministically.The window-enforcing SCPO variant replaces soft-window greedy assembly with a feasibility-constrained selector.Source: §2.3 · p. 2, Figure 2 · p. 3

2.4 Auditability

  • Replay requires decision inputs and tie-breaking to be logged or deterministically retrievable; the same trace quantities supply margins and perturbation envelopes for stability checks.Exact replay avoids a dense candidate-similarity matrix, while certificate-only monitoring stores margins, the movement bound, and versioned input references.Source: §2.4 · p. 3

2.5 What This Model Class Buys

  • The model class supports privacy inheritance under its input contract, a scorer-independent drift envelope from window enforcement, and anchor-based raw top-K stability linked to greedy-slate margins.Evaluation includes closed-loop runs on two educational corpora, raw score-stability checks on two ratings corpora, and component-removal tests.Source: §2.5 · p. 3

3 Related Work

Prior work often studies private scoring, deterministic re-ranking, bandit exploration, or ranking stability separately. This paper focuses on how an explicitly scoped learner guarantee and score perturbations relate to deterministic slate selection.

3 Related Work

  • Differentially private recommendation studies protection in learned models or training procedures, but does not by itself characterize post-score selection or audit logging.The paper uses standard post-processing and group-privacy tools while distinguishing end-to-end protection from conditioning on raw selector inputs.Source: §3 · p. 3
  • Deterministic re-ranking methods study objectives such as diversity and fair exposure [23], while private bandit work couples exploration to particular learners [15] [22].The paper describes its LinUCB result as a scoped recovery statement when other selector terms are disabled.Source: §3 · p. 3
  • Adjacent ranking-stability work considers training-interaction sensitivity [21] or stable and fair ranking rules under uncertain predictions [7], rather than a logged sufficient certificate for deterministic greedy slate construction.Private top-K selection uses stability to decide when a set can be released privately [28]; here the direction is propagation of an already-private learner through a selector.Source: §3 · pp. 3–4
  • The paper’s stated gap is the margin-certified connection between score perturbations, top-K ranking stability, and greedy-slate stability under named assumptions.It presents this as distinct from proposing a new scorer or re-ranking objective.Source: §3 · p. 4

4 Theoretical Guarantees

The guarantees for a deterministic slate selector depend on which inputs are admissible and what the decision trace records. Bounded score-induced objective movement below half the smallest greedy margin certifies an unchanged ordered slate, while privacy, drift, and recovery claims remain scoped to their assumptions.

4.1 Privacy Scope

  • A deterministic selector inherits learner privacy only when its side inputs meet the admissibility contract; fixing raw state or candidate information gives only a conditional statement.The audit trace follows the same privacy conditions, and a non-private anchor trained on protected data is outside the end-to-end claim.Source: §4 · p. 4, §4.1 · p. 4

4 Theoretical Guarantees

  • The central stability test is whether score noise moves the selector objective by less than half the separation between the chosen item and its closest alternative.This margin-and-movement condition underlies both the top-K and greedy-slate certificates.Source: §4 · p. 4

4.2 Selector Drift

  • A window-enforcing selector bounds round-to-round movement in the average target value of accepted items, independently of the scorer.For soft-window MMR, the guarantee applies only on logged rounds when selected items satisfy the window condition.Source: §4.2 · p. 4

4.3 Margin-Certified Stability

  • If the smallest positive stepwise margin Γ exceeds twice the bounded objective movement M, the selector produces the same ordered slate.The proof bounds each candidate's movement by M, so a reference gap can shrink by at most 2M; logged margins and a valid envelope make the certificate auditable, while failure to certify does not establish a slate change.Source: §4.3 · p. 4

4.4 What Anchor Blending Buys

  • For raw top-K selection, larger anchor weight reduces the noisy adaptive score's influence, while larger score-difference noise makes flips more likely.The bound is exponential in the anchor gap and noise scale; an imperfect anchor consumes part of the usable gap.Source: §4.4 · pp. 4–5

4.5 From Raw Scores to Greedy Slates

  • The greedy-slate certificate accounts for score, bonus, and novelty/state movement; with other inputs fixed, their movement terms vanish.Unlike the simpler raw top-K result, the final-slate result uses logged stepwise margins and a richer decision trace; its high-probability version follows for sub-Gaussian score errors.Source: §4.5 · p. 5

4.6 Scoped Recovery and Threat Model

  • The LinUCB recovery result applies only when target shaping, diversity, novelty, and slate-size adaptation are disabled, not to the full active-lever selector.Stability may hold for a non-private anchored system, but composes with DP only when the anchor is public, independent of the protected data, or separately accounted.Source: §4.6 · p. 5

5 Experimental Methodology

The experiments test score-ranking stability and selector behavior through controlled perturbations and simulated closed-loop recommendation. Their protocol uses matched candidate pools and defines checks and outcome measures, while treating privacy configurations and simulator comparisons within explicit limits.

5 Experimental Methodology

  • The closed-loop testbed uses adaptive practice, with OULAD as a denser interaction corpus and EdNet as a sparse, longer-horizon corpus.MovieLens-25M and Amazon Musical Instruments provide raw-ranking checks outside education; OULAD and EdNet lack exposure logs, so simulated comparisons support trends rather than absolute field-effect claims.Source: §5 · p. 5, §5.1 · p. 5

5.1 Closed-loop recommendation setting

  • Matched candidate pools, seeds, and 20-round sessions support paired comparisons of learner and selector modes, with one 50-round variant.The simulated feedback is aggregated for state updates, and response-simulator checks do not establish absolute field effects.Source: §5.1 · p. 5

5.2 Modes and privacy

  • The modes compare adaptive neural scoring, fixed ALS scoring, and their blend; the non-private ALS anchor makes anchored runs stability tests, not end-to-end DP experiments.The released artifact does not establish the sampler, protected-unit clipping, or per-round aggregation needed to validate nominal privacy configurations, which are reported only as stress-test labels.Source: §5.2 · pp. 5–6

5.3 Direct theorem checks

  • The fitted-slope 95% interval was [-0.231, -0.210] across eight selected cells from 32,000 fixed-margin perturbation trials.The protocol uses this fit to test the -1/4 exponent for independent Gaussian noise; the eight-cell selection rule was not preregistered.Source: §5.3 · p. 6
  • The selector-margin diagnostic fixes other selector inputs and checks whether a realized perturbation satisfying M_t < Γ_t/2 changes the slate, making it an ex post implementation check.The separate OULAD learner-update diagnostic is descriptive, with pair draws sharing training seeds, pools, and item scores rather than serving as independent inferential observations.Source: §5.3 · p. 6

5.4 Outcome metrics and statistics

  • Flip@K measures the frequency of top-K set changes, while Jaccard@K reports change magnitude when flips saturate.Closed-loop comparisons are paired by session with bootstrap 95% intervals; exploratory sign-test p-values have no multiplicity correction.Source: §5.4 · p. 6

6 Results

Direct diagnostics support the predicted score-stability patterns, while closed-loop outcomes are more mixed and depend on the simulator setting. The results distinguish certificate checks from downstream utility measurements.

6 Results

  • The results separate direct theorem checks from downstream closed-loop behavior, where target shaping, diversity, slate-size adaptation, and response feedback make outcomes more mixed.Direct diagnostics test stability claims; closed-loop runs test behavior inside the simulator.Source: §6 · p. 6

6.1 Selector components and drift

  • Against pure ALS, full Adaptive on OULAD improves correctness by 0.121, attempts per round by 0.714, and utility probe by 14.824×10^-3; EdNet gains are smaller.On EdNet, attempts per round increase by 0.140 and utility-probe change is 0.032×10^-3; SCPO probe differences versus Adaptive have opposite signs across datasets.Source: §6.1 · p. 6

6.2 Target-value drift

  • Observed consecutive target-value jumps stay within the configured envelope; Adaptive-SCPO is exact on nonrelaxation rounds, while soft-window MMR inherits the bound only on more than 98% of round pairs.On relaxation rounds, Adaptive-SCPO uses the realized relaxed window.Source: §6.2 · pp. 6–7

6.3 Raw score-ranking stability

  • The fixed-margin independent-Gaussian fit has slope −0.220 (95% CI [−0.231, −0.210]) versus reference −1/4, supporting linear scaling but showing a shallower finite-sample slope.The interval excludes −0.25.Source: §6.3 · p. 7
  • Increasing anchor weight from 0 to 0.75 reduces Flip@K across OULAD, MovieLens-25M, and Amazon Musical Instruments under independent noise.For example, on OULAD at σ=0.02, Flip@K falls from 0.167 to 0.032; low-rank correlated noise and rating-threshold checks preserve the pattern.Source: §6.3 · p. 7
  • On OULAD and EdNet, all 320 logged pools have positive selector margins, and no certified perturbation trial changes the greedy slate.The authors characterize these checks as implementation tests of the logged certificate, not independent theorem evidence, because margins are computed from each realized perturbation.Source: §6.3 · p. 7

6.4 Configured-update stress tests and closed-loop behavior

  • An 80-update run raises τ̂ from about 0.67 to 1.17 and lowers anchor-weight-0.75 Jaccard from about 0.72 to 0.63; closed-loop comparisons are stress tests, not verified privacy–utility curves.The released artifact does not establish the complete DP mechanism, so the diagnostic supports observed tail shape rather than a particular privacy tier or ε.Source: §6.4 · p. 7
  • Across 16 response-model and user-profile settings, minimum paired deltas versus ALS are positive for correctness, post-test utility, and uptake on both datasets, though EdNet gains are smaller and more variable.The authors claim score-noise attenuation, not universal downstream utility improvement.Source: §6.4 · p. 7

7 Discussion

The discussion scopes privacy inheritance to selector inputs that are public, independent, previous DP outputs, or separately accounted. It presents logged margins as the core stability guarantee and identifies limits on interpreting the experiments.

7 Discussion

  • End-to-end privacy requires public or independent selector inputs, prior DP outputs, or separately accounted inputs; fixing raw state or candidate information yields only a conditional statement.A non-private anchor supports stability analysis, not the private-regime claim.Source: §7 · pp. 7–8
  • The main stability contribution is a logged margin certificate for ordered-slate invariance under bounded score-induced movement.Figure 3 reports increasing raw top-K churn with score-noise scale and decreasing churn with anchor weight, alongside a fixed-margin slope of −0.220 (95% CI [−0.231, −0.210]) versus −1/4.Source: §7 · p. 8, Figure 3 · p. 8
  • Because OULAD and EdNet lack exposure logs, engagement is simulated; the released artifact also does not establish the sampler and protected-unit clipping needed to validate nominal privacy configurations.A user-level guarantee additionally requires a contribution cap B, and a failed sufficient margin certificate does not imply that the slate changes.Source: §7 · p. 8

A Supplementary setting details

The supplement specifies a deterministic selector and replay trace for the experimental setup, then describes SCPO as a window-enforcing alternative. Replay and privacy claims depend on how selector inputs are sourced.

A Supplementary setting details

  • The experimental setting uses deterministic, public rules fixed before policy evaluation, with a round trace containing selector state, inputs, slate, and tie-breaking information for replay.Public or immutable entries may be stored as identifiers with deterministic lookup rules.Source: A Supplementary setting details · pp. 9–10
  • The learner maps logged interactions to item scores, and the full pipeline applies a deterministic selector to candidate pools, pre-round state, and selector levers.The supplement describes a bounded governed lever vector and a default greedy selector that assembles a slate to the configured size with deterministic tie-breaking.Source: A Supplementary setting details · pp. 9–10
  • The selector state is based on prior displayed slates, prior responses, and the current candidate pool; uncertainty widths are normalized using a reference fixed before evaluation.Lever maps are deterministic clipped affine functions with pre-specified coefficients.Source: A Supplementary setting details · p. 10
  • Replay requires candidate identities and selector inputs to be stored or reconstructed; if any input derives from protected data, it must be a previous DP output or separately accounted for end-to-end privacy.Merely fixing such an input protects the learner output only conditionally on that value.Source: A Supplementary setting details · p. 10

B Window-enforcing selector (SCPO)

  • SCPO replaces greedy MMR assembly with a feasibility-constrained selector that enforces the target window when possible; on relaxation rounds, the drift envelope uses the realized relaxed width.If no size-K_t subset satisfies the window, SCPO relaxes it to the smallest width making at least K_t candidates feasible.Source: B Window-enforcing selector (SCPO) · pp. 10–11

C Supplementary proof details

The appendix formalizes when privacy passes through deterministic selection and when bounded score perturbations preserve the ordered slate. It also gives related bounds for top-K ranking, user-level privacy, target-value drift, and a restricted LinUCB regime.

Privacy post-processing

  • Selection and its audit trace preserve the learner’s (ε, δ)-DP guarantee when selector-side inputs are public, independent, prior DP outputs, or separately accounted.Conditioning on raw inputs gives only a conditional statement and does not protect those inputs.Source: C Supplementary proof details · pp. 11–12

User-level privacy

  • When each user contributes at most B records, record-level privacy lifts to a user-level pipeline guarantee under the selection lemma’s hypotheses.The stated second component is at most B e^((B−1)ε)δ.Source: C Supplementary proof details · pp. 11–12

Target-value drift

  • Under window enforcement and bounded movement in the window center, the change in mean accepted-item target value is bounded by η + 2Δ_max + w_t + w_(t+1).For a fixed window w, the bound becomes η + 2Δ_max + 2w; soft-window MMR inherits the statement only when both accepted sets satisfy the window.Source: C Supplementary proof details · pp. 11–12

Margin-certified selector stability

  • If the perturbation envelope is below half the minimum positive stepwise margin, the deterministic selector returns the same ordered slate.The proof bounds each candidate objective’s movement by M, so a reference gap can shrink by at most 2M; induction preserves each greedy choice.Source: C Supplementary proof details · p. 11

Greedy-slate stability

  • With fixed bonus inputs and two-sided sub-Gaussian coordinate errors, the greedy-slate change probability is bounded by 2|C_t| exp(−Γ_t^2/[8(1 − λ_t)^2σ^2]).This bound applies when λ_t < 1.Source: C Supplementary proof details · p. 12

LinUCB recovery

  • Disabling shaping, diversity, novelty, and variable slate size recovers the single-item LinUCB rule with Õ(d√T) regret under standard realizability and confidence assumptions.The result uses the standard LinUCB confidence radius and usual bounded-feature and bounded-noise assumptions.Source: C Supplementary proof details · pp. 12–13

Raw top-K stability

  • The top-K flip bound depends on the anchor gap and pairwise-noise tail; an anchor with sup-norm error at most β reduces the effective gap to (γ − 2β)+.The bound follows by considering cross-boundary item pairs that could overturn the anchor ranking.Source: C Supplementary proof details · pp. 11–12

D Supplementary methodology details

The supplementary methodology describes the closed-loop evaluation and its corpus and simulator diagnostics, alongside the fixed-margin and real-anchor stability experiments.

Corpus and simulator diagnostics

  • The corpus summary defines density as interactions per thousand possible user–item pairs and reports user-stratified splits; simulator validation covers target-value versus correctness, user-level correctness distributions, and interaction counts on a log scale.The split uses random seed 42.Source: Table 3 · p. 13, Figure 4 · p. 14

Closed-loop protocol

  • The closed-loop protocol pairs policy comparisons across four response simulators and four user profiles, replaying matched candidate pools and testing selector components by removal.Each round generates a slate, simulates item-level responses, and updates policy state from the observed responses.Source: D Supplementary methodology details · p. 14

Stability experiment design

  • The fixed-margin calibration fit has slope −0.220 (95% CI [−0.231, −0.210]) across eight selected cells; real-anchor tests use 64 OULAD pools and 48 pools each for MovieLens-25M and Amazon Musical Instruments.The fit uses cells with smoothed Flip@K in [10^-4, 0.25], a rule that was not preregistered; each real-anchor pool receives 200 noise draws.Source: D Supplementary methodology details · p. 14

E Supplementary related-work object map

The related-work object map describes the analytic objects commonly emphasized by related families without characterizing those families as deficient.

Related-work object map

  • The table maps related-work families by their usually studied analytic objects and explicitly does not assess whether any family is deficient.The supplied caption does not enumerate the map’s entries.Source: Table 5 · p. 15

F Additional tables

The additional tables report stability calibration, real-anchor and certificate checks, and several closed-loop and configured-update diagnostics.

Fixed-margin calibration

  • The fixed-margin calibration fit gives slope −0.220 (95% CI [−0.231, −0.210]) against reference −1/4, with R^2 = 0.998.The eight-cell fit uses a non-saturation rule that was not preregistered.Source: Table 8 · p. 16

Real-anchor checks

  • Real-anchor tables report reduced raw top-K flips at higher anchor weight under independent and low-rank correlated noise, with the stabilizing effect at w = 0.75 persisting across rating thresholds.The tables cover one educational corpus and two ratings corpora.Source: Table 10 · p. 16, Table 11 · p. 17

Selector-margin checks

  • OULAD and EdNet tables report positive anchor gaps and greedy margins in logged pools, and zero certified violations in the selector-margin perturbation checks.Certification is defined by M_t < Γ_t/2 under the fixed-bonus envelope.Source: Table 12 · p. 17, Table 13 · p. 17, Table 14 · p. 17

Pairwise-noise diagnostics

  • The OULAD pairwise-tail table reports measured upper tails below the sub-Gaussian envelope after normalization by the pairwise τ proxy.The fixed-margin fit table distinguishes independent Gaussian noise from low-rank correlated noise and uses different scale parameters for each.Source: Table 9 · p. 16, Table 16 · p. 18

Additional diagnostics

  • The remaining tables cover closed-loop paired deltas, telemetry–utility sign agreement, configured-update diagnostics, applied score-noise stress tests, and subgroup gaps.The configured-update tables caution that nominal settings are not independently verified DP mechanisms; the EdNet 25k table describes a mixed pattern rather than a privacy–utility curve.Source: Table 18 · p. 18, Table 19 · p. 19, Table 20 · p. 19

Related papers

Loading 2609.29453v1…