CS Paper Radar

Local Certificate Repair for Asynchronous Controller Updates in Recommender Systems

Simone Mariano, Paolo Frasca

eess.SY math.OC ·submitted 2026-11-08 15:49 UTC · v1

Abstract

We study how to adapt an existing distributed recommendation controller when local dynamics or objective weights change. Starting from a quadratic stability and cost certificate, we construct positive semidefinite corrections with finite spatial support and an explicit residual. A joint admission test allocates the available dissipation margin to these residuals and to interactions among changes and corrections, including pending updates. The test covers complete declared parameter ranges, allowing different operators to progress independently. For a fixed compatible batch, the corrections define a common storage that guarantees exponential stability and bounds the cost accumulated throughout deployment. When the admitted collection evolves, a reservation protocol preserves the certificate and a rate bound on storage increases ensures exponential convergence. Regional linear-quadratic regulator (LQR) design proposes new gain rows for the operators' own users, and a separate residual-based calculation can certify that the final gain lowers the expected cost. A recommendation-network example illustrates the tradeoff between repair depth, data access, and the benefits of deploying an update.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Regret for Online Storage Control via Cumulative Policies

eess.SY math.OC ·2026-09-18 ·Kamiar Asgari, Michael J. Neely
theory similarity 0.56
Abstract

We study online control of a scalar storage system with adversarial nonnegative arrivals, known retention coefficient, and convex costs depending on both state and action. Each action must respect current resource availability and is chosen before the current arrival and cost function are revealed. For the existing simplex disturbance-action policy class, we give an exact reparameterization by cumulative allocation fractions and a decay-weighted projected subgradient update. The resulting regret bound is independent of policy memory length. For fixed retention coefficient and cost constants, the controller achieves $O(\sqrt T)$ regret against the best fixed infinite-memory policy in this class, using $O(\log T)$ memory and arithmetic operations per round and one cost-subgradient query. A storage-specific block construction gives a matching lower bound against every causal feasible controller, including randomized controllers. Writing $τ=(1-α)^{-1}$, the minimax expected regret is $Θ(\sqrt T\min\{T,τ\}^{3/2})$ for every finite-memory simplex policy class and its infinite-memory extension, when $α\in[1/2,1)$, $T\ge4$, and the positive cost constants are fixed. This identifies the joint horizon and retention-time dependence for these policy benchmarks.

0.10

Beyond Binary: Continuous State Optimization with Graph-Structured Objectives

cs.LG ·2026-08-10 ·Corinna Cortes, Yishay Mansour, Mehryar Mohri
similarity 0.55
Abstract

Large-scale learning systems often face the challenge of balancing multiple, potentially competing objectives, such as fairness, accuracy, and latency. While recent work has formalized this as an optimization problem over binary states, many real-world control parameters, such as fairness thresholds, diversity mixing rates, or resource budgets, are continuous. In this work, we extend the framework to \emph{continuous state spaces}. We model the problem as minimizing a sum of linear objectives subject to \emph{movement costs} that penalize system instability. We capture the local structure of the objectives using a \emph{dependency graph} (or factor graph), where each objective is determined by a subset of the state attributes. To address the tension between exploration and stability, we propose \emph{Lazy Graph-LinUCB}, an algorithm that performs lazy updates to minimize switching costs while maintaining near-optimal regret. Beyond stability, we introduce three advanced mechanisms to exploit the underlying graph structure: (1) an \emph{asynchronous} update schedule that eliminates synchronization overhead in sparse graphs; (2) an \emph{adaptive} algorithm that learns the graph structure from data; and (3) a \emph{joint estimator} that leverages data sharing among correlated objectives to significantly tighten regret bounds. Empirically, we demonstrate that these structural exploitations reduce movement costs by more than a factor of three in heterogeneous systems while maintaining similar cumulative losses.

0.04

Personalized Rollout Allocation for Federated LQR Policy Optimization under Heterogeneous Process Noise

cs.MA cs.LG ·2026-10-31 ·Mohammadreza Rostami, Shahriar Talebi, Solmaz S. Kia
similarity 0.55
Abstract

We study federated model-free learning of a common linear quadratic regulator (LQR) gain under a limited uplink communication budget, with clients that share dynamics and costs but experience different process-noise levels. Conventionally, clients transmit gradient matrices whose dimension equals the number of controller parameters. Exploiting the structure of two-point zeroth-order estimates, we consider an implementation in which clients transmit only one scalar cost-difference coefficient per rollout pair, while the server regenerates the associated perturbation directions from shared seeds. Communication thus scales with the number of rollout pairs rather than the controller dimension, turning the uplink budget into a rollout budget. Because noise heterogeneity produces gradient estimates of widely differing variance and every client carries equal weight in the fleet objective, uniform rollout allocation allows noisy clients to dominate the aggregated update and increases the probability of destabilizing updates. We propose a rollout-allocation scheme that assigns rollout pairs in proportion to the standard deviation of each client's estimates and show that it minimizes the variance of the aggregated update. The scheme is implemented exactly through a greedy integer allocation rule whose weights are estimated from the communicated scalars. We further prove that a single allocation factor quantifies its improvement over uniform allocation in a one-round instability bound, the certified step size, and the error floor of a joint stability and convergence guarantee. Simulations show that, under the same communication budget, personalized allocation reduces the one-step instability rate from $37\%$ to $0.3\%$.

0.14

Reference-Tail Trust:Certified Probability Floors for Learned Updates Inside a Deployed Network

cs.LG cs.AI ·2026-09-28 ·Abdolvahab Khalili Sadaghiani, Jose Nunez-Yanez
theory similarity 0.54
Abstract · 37 pages, 10 figures

Graph neural networks (GNNs) need to exploit improved message passing without surrendering control over predictions already trusted in deployment. We introduce Reference-Tail Trust (RTT), a framework that admits learned updates inside a frozen GNN and certifies the prediction actually served. RTT couples graph-based proposal states with a constrained internal optimizer: each displacement is charged for its worst-case terminal cross-entropy increase through the incumbent's remaining message-passing layers. A trajectory-validated tube and an independent checker enforce per-node probability floors, $p^{\mathrm{s}}_{ic} \ge e^{-H_{\mathrm{row}}} p^{\mathrm{r}}_{ic}$, and a call-level budget, $\sum_i w_i D_\infty(p^{\mathrm{r}}_i \| p^{\mathrm{s}}_i) \le H^+$, uniformly over labels. Calls whose adapted outputs pass certification require no separate full incumbent rollout; failed certificates trigger whole-call fallback. We derive the exact probability-floor frontier by water-filling, characterize architecture-constrained efficiency, and establish conditions under which internal propagation exploits evidence unavailable to restricted output correctors. In the reported ogbn-arxiv audit, RTT achieves $6.5\times 10^{-3}$ nats of mean gain per call, with a one-sided 95% regression-rate upper bound of 0.95% and a 95% negative-flip upper bound of 0.51% on the uninspected part of the reserved node population. Its mean gain is 61% of a cross-fitted posterior-based frontier estimate and exceeds the strongest matched one-pass corrector by $+0.9\times 10^{-3}$ nats. Reported experiments span eight proposals, six graph-incumbent families, structural and temporal graph shifts, and molecular prediction, with additional image and tabular evaluations. RTT makes GNN adaptation a budgeted, certifiable inference decision rather than an unconditional model replacement.

0.25

Discount Yourself: Self-inclusive Freshness-weighted Gossip for Decentralised Learning under Client Outages

cs.LG cs.DC ·2026-10-20 ·Qiyuan Wang, Ke Xiao, Christos Anagnostopoulos
similarity 0.53
Abstract · 52 pages, 9 figures, 35 tables; includes appendices

Decentralised federated learning (DFL) trains personalised models on devices that average with their neighbours rather than with a central server. Real devices, however, are often offline for hours or days, and a client returning from an outage can recover only by aggregating the models its neighbourhood holds. We observe that the stalest of these models is usually the client's own, a case that existing staleness-aware rules, which discount only the models a client receives, do not address. We formalise aggregation after an outage as estimating the state of a fully available network and derive three principles. First, the receiver must be discounted like any neighbour. Every rule that weights it at least as much as each neighbour has an error that grows without bound with the outage, whereas discounting all candidates by relative staleness keeps the error bounded. Second, staleness must be measured as inherited lag rather than age, since local training resets a model's age but not the lag it absorbed from stale neighbours. We introduce the effective lag, which tracks this quantity at the cost of one scalar per message. Third, the discount must be steep, because absorbed lag persists in every later round. These principles define Self-inclusive Freshness-weighted Gossip (SFG), a family of drop-in aggregation rules with the communication and computation of decentralised federated averaging, whose guarantees hold for the stale receiver itself. On three image benchmarks and eight outage processes, including real smartphone availability traces, the lag-based members SFG-L and SFG-Cut consistently outperform decentralised federated averaging and recent age-of-information rules, and ablations show that each principle is necessary. The analysis also explains why tuned limited merging from gossip learning is effective.

0.17

Dynamic $k$-Median with Worst-Case Update Time and Recourse

cs.DS ·2026-11-12 ·Chenglin Fan
similarity 0.53
Abstract · 81 pages

We study fully dynamic metric $k$-median under unit-weight client insertions and deletions. After each update, the algorithm must maintain at most $k$ centers chosen from the current client locations. We give a randomized constant-factor approximation algorithm with $\widetilde O(k)$ worst-case update time and $O((1+\logΔ)^3)$ worst-case center recourse, where $Δ$ is the aspect ratio of the underlying metric space. The approximation guarantee holds simultaneously over any prescribed finite adaptive update sequence with high probability, while the update time and recourse bounds hold on every execution. We also obtain the same asymptotic guarantees for metric $k$-means.

0.25

FAIRGate: Agentic Runtime Policy Selection and Verified Repair for Fairer Recommendation Delivery

cs.IR ·2026-10-21 ·Navkar Jain, Enock Ayiku, Kenneth Fletcher
top venue similarity 0.53
Abstract · Accepted at the 1st IEEE International Conference on Responsible Artificial Intelligence (IRAI 2026), Melbourne, Australia. 6 pages, 2 figur…

Fairness-aware recommender systems often encode one fairness objective during training or apply a fixed re-ranking rule after scoring. In deployment, however, the appropriate fairness action can vary across requests because the candidate pool, item metadata, exposure debt, user preference history, and utility budget all change at runtime. We propose FAIRGate, a model-agnostic delivery controller that places an agentic policy-selection layer between a base ranker and the final top-K list. The agent does not define fairness objectives from scratch. It chooses from a predefined policy library covering long-tail exposure, item-group exposure balance, concentration control, calibration protection, and abstention. A deterministic executor then applies the selected policy through constrained repair, and a validator accepts the result only when relevance, feasibility, metadata, calibration, and audit constraints are satisfied. The final language-model component receives only the verified audit trace and produces evidence-linked narration after the ranking decision is fixed. This design gives the agent runtime responsibility while keeping fairness enforcement measurable, bounded, and replayable.

0.36

SafeLink-Agent: Agentic Maintenance for Adaptive Bitrate Controllers over Dynamic Starlink Networks

eess.SY ·2026-08-28 ·Hongjun Xie, Bowen Zhang, Genke Yang, Pengcheng Luo
similarity 0.52
Abstract

Low Earth orbit (LEO) satellite broadband, represented by Starlink, is making high-resolution video streaming feasible beyond fixed terrestrial coverage. However, Starlink access links change across time and regions, exposing adaptive bitrate (ABR) streaming to shifting throughput tails, latency, volatility, and handover conditions. Existing ABR controllers are usually designed, tuned, or trained for specific network conditions, making it difficult to handle newly exposed hard Starlink profiles. This paper proposes SafeLink-Agent, an agentic maintenance framework for ABR controllers over dynamic Starlink networks. SafeLink-Agent summarizes exposed failures and uses a large language model (LLM)-based agentic patch proposer to generate candidate patches, while replay verification determines whether each patch can be safely committed. The framework supports both rule-based controllers and learned controllers under the same maintenance workflow. Experiments on real Starlink networks show that SafeLink-Agent reduces the severe-session ratio of RobustMPC from 2.60% to 0.40% and reduces cumulative severe sessions from 45 to 7 in rolling maintenance. For learned controllers, verified adaptive auditing lowers the average severe-session ratio from 39.01% to 9.79%. These results demonstrate that agentic maintenance can improve ABR robustness under dynamic Starlink access conditions.

0.27