Nonstationary Dual Averaging and Online Fair Allocation

We consider the problem of fairly allocating sequentially arriving items to a set of individuals. For this problem, the recently-introduced PACE algorithm leverages the dual averaging algorithm to approximate competitive equilibria and thus generate online fair allocations. PACE is simple, distributed, and parameter-free, making it appealing for practical use in large-scale systems. However, current performance guarantees for PACE require i.i.d. item arrivals. Since real-world data is rarely i.i.d., or even stationary, we study the performance of PACE on nonstationary data. We start by developing new convergence results for the general dual averaging algorithm under three nonstationary input models: adversarially-corrupted stochastic input, ergodic input, and block-independent (including periodic) input. Our results show convergence of dual averaging up to errors caused by nonstationarity of the data, and recover the classical bounds when the input data is i.i.d. Using these results, we show that the PACE algorithm for online fair allocation simultaneously achieves "best of many worlds" guarantees against any of these nonstationary input models as well as against i.i.d. input. Finally, numerical experiments show strong empirical performance of PACE against nonstationary inputs. not require dividing the item, and it is also completely parameter free. This makes it suitable for large-scale practical implementation. Yet in many large-scale settings, such as the context of fair recommender systems (Kroer et al., 2021; Kroer and Stier-Moses, 2022) or Internet advertising, we would not expect items to be drawn i.i.d. from a single distribution. One alternative is to assume that data arrives adversarially. However, this leads to very pessimistic negative results and is not an accurate representation of the data one would expect to see in practice. Instead, one would expect the data to have a strong stochastic component, but with changes over time, e.g., due to flow of traffic, breaking news events, or system updates (Esfandiari et al., 2018; Balseiro et al., 2020) . Motivated by the above considerations, we study online fair allocation when the data exhibits nonstationary behavior. In particular, we focus on the performance of the PACE algorithm of Gao et al. (2021). We ask How does PACE behave when nonstationarity is present in the stream of items? We show that, under several data-input models, the fairness and efficiency guarantees of the PACE algorithm are still preserved, up to errors due to the nonstationarity of the data input. In this sense, we significantly extend the main results in Gao et al. (2021). To show these results, we first consider the more general setting of nonstationary stochastic optimization and develop new performance guarantees for dual averaging in this setting. Given the ubiquitous use of dual averaging in online and stochastic optimization, our results are of broader interest beyond (fair) resource allocation. Summary of Contributions Novel convergence results for dual averaging under three nonstationary settings. We analyze the dual averaging (DA) algorithm for nonstationary stochastic optimization under different data input models, namely, (1) mildly corrupted, (2) ergodic and (3) periodic input data. Specifically, we consider the composite dual averaging algorithm, where the composite term is strongly convex. We show that, in all cases, the iterates generated by dual averaging (DA) converge to the optimal solution in mean square, where the bound on the mean-square error decomposes into two terms: i) the typical O(log t/t) guarantee known from the i.i.d. case, and ii) a term that depends on the amount of nonstationarity in the data input model. Our results recover the classical bounds under i.i.d. data input as a special case. Theoretical fairness and efficiency guarantees of PACE for nonstationary item arrivals. We consider the online fair allocation problem where item arrivals follow any of the three data input models that we consider for DA; these settings generalize the i.i.d. setting in Gao et al. (2021). Utilizing our convergence results for DA under nonstationary data input models, we show that, for item arrivals following these models, PACE ensures convergence of the pacing multipliers, again with a decomposition into a O(log t/t) term as well as a term depending on the nonstationarity. We then show that the agents' realized utilities, envy, regrets, and expenditures all obtain convergence bounds based on the convergence of pacing multipliers. Our results show that PACE as an online fair resource allocation algorithm is robust against distributional uncertainty of the input and automatically adapts to many different data input models without any parameter tuning. In Appendix F we provide numerical experiments which corroborate the above theory and demonstrate the practical efficiency of PACE under different data input models. An extensive review of related work is provided i