AoI-aware Federated Unlearning for Streaming Data with Online Client Selection and Pricing

Models trained on static datasets often fail to adapt to evolving streaming data, leading to significant accuracy degradation. Federated unlearning can address this by removing outdated data and updating the model with fresh data. However, limited bandwidth prevents all clients from acquiring fresh data in a time-varying environment. Thus, the server must optimally select a subset of clients to update their data in an online manner and compensate them for their costs. To address these challenges, we first propose an efficient federated unlearning algorithm for streaming data and theoretically characterize the model optimality gap as a function of client selection with heterogeneous data freshness and criticality. This allows us to formulate a stochastic optimization problem to minimize the unlearned model loss and total payment. Using Lyapunov optimization, we derive an optimal client selection policy with a closed-form threshold that condenses clients' multi-dimensional heterogeneity into a one-dimensional metric. Furthermore, we model clients’ asking prices for fresh data collection as a non-cooperative game and derive its closed-form Nash Equilibrium. Experimental results on a real dataset show that our proposed mechanism reduces the server's cost by up to 32.31% compared to two state-of-the-art baselines.