Tracking Solutions of Time-Varying Variational Inequalities

References

• [1] Anagnostides I, Panageas I, Farina G, Sandholm T (2024) On the convergence of no-regret learning dynamics in time-varying games. Adv. Neural Inform. Processing Systems, vol. 36 (Curran Associates Inc., Red Hook, NY), 16367–16405.Google Scholar
• [2] Antonakopoulos K, Vu DQ, Cevher V, Levy K, Mertikopoulos P (2022) Undergrad: A universal black-box optimization method with almost dimension-free convergence rate guarantees. Internat. Conf. Machine Learn. (PMLR, New York), 772–795.Google Scholar
• [3] Armijo L (1966) Minimization of functions having Lipschitz continuous first partial derivatives. Pacific J. Math. 16(1):1–3.Crossref, Google Scholar
• [4] Baby D, Wang YX (2022) Optimal dynamic regret in proper online learning with strongly convex losses and beyond. Internat. Conf. Artificial Intelligence Statist. Proc. Mach. Learn. Res, vol. 151 (PMLR, New York), 1805–1845. Google Scholar
• [5] Barnsley M, Vince A (2011) The eigenvalue problem for linear and affine iterated function systems. Linear Algebra Appl. 435(12):3124–3138.Crossref, Google Scholar
• [6] Bartlett PL, Hazan E, Rakhlin A (2007) Adaptive online gradient descent. Proc. 20th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 65–72.Google Scholar
• [7] Baudin L, Scarsini M, Venel X (2023) Strategic behavior and no-regret learning in queueing systems. Preprint, submitted February 7, https://arxiv.org/abs/2302.03614.Google Scholar
• [8] Bauschke HH, Combettes PL (2011) Convex Analysis and Monotone Operator Theory in Hilbert Spaces (Springer, Berlin).Crossref, Google Scholar
• [9] Bauschke HH, Moffat SM, Wang X (2011) Firmly nonexpansive mappings and maximally monotone operators: Correspondence and duality. Set-Valued Variational Anal. 20(1):131–153.Crossref, Google Scholar
• [10] Besbes O, Gur Y, Zeevi A (2015) Non-stationary stochastic optimization. Oper. Res. 63(5):1227–1244.Link, Google Scholar
• [11] Bielawski J, Chotibut T, Falniowski F, Kosiorowski G, Misiurewicz M, Piliouras G (2021) Follow-the-regularized-leader routes to chaos in routing games. Proc. 38th Internat. Conf. Machine Learn., vol. 139 (PMLR, New York), 925–935.Google Scholar
• [12] Block LS, Coppel WA (2006) Dynamics in One Dimension (Springer, Berlin).Google Scholar
• [13] Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [14] Chen X, Balasubramanian K, Ghosal P, Agrawalla B (2023) From stability to chaos: Analyzing gradient descent dynamics in quadratic regression. Preprint, submitted October 2, https://arxiv.org/abs/2310.01687.Google Scholar
• [15] Cohen JM, Kaur S, Li Y, Kolter JZ, Talwalkar A (2021) Gradient descent on neural networks typically occurs at the edge of stability. Preprint, submitted February 26, https://arxiv.org/abs/2103.00065.Google Scholar
• [16] Deng Y, Mirrokni V, Zuo S (2021) Non-clairvoyant dynamic mechanism design with budget constraints and beyond. Proc. 22nd ACM Conf. Econom. Comput. (ACM, New York), 369.Google Scholar
• [17] De Rooij S, Van Erven T, Grünwald PD, Koolen WM (2014) Follow the leader if you can, hedge if you must. J. Machine Learn. Res. 15(1):1281–1316.Google Scholar
• [18] Duvocelle B, Mertikopoulos P, Staudigl M, Vermeulen D (2023) Multiagent online learning in time-varying games. Math. Oper. Res. 48(2):914–941.Link, Google Scholar
• [19] Facchinei F, Kanzow C (2007) Generalized Nash equilibrium problems. 4OR 5(3):173–210.Crossref, Google Scholar
• [20] Facchinei F, Pang JS (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems (Springer, Berlin).Google Scholar
• [21] Falconer K (1990) Fractal Geometry—Mathematical Foundations and Applications (Wiley, New York).Crossref, Google Scholar
• [22] Falniowski F, Mertikopoulos P (2025) On the discrete-time origins of the replicator dynamics: From convergence to instability and chaos. Internat. J. Game Theory 54(1):7.Crossref, Google Scholar
• [23] Feng Y, Fu H, Hu Q, Li P, Panageas I, Peng B, Wang X (2023) On the last-iterate convergence in time-varying zero-sum games: Extra gradient succeeds where optimism fails. Adv. Neural Inform. Processing Systems, vol. 36 (Curran Associates Inc., Red Hook, NY), 21933–21944. Crossref, Google Scholar
• [24] Fiez T, Sim R, Skoulakis S, Piliouras G, Ratliff L (2021) Online learning in periodic zero-sum games. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates Inc., Red Hook, NY), 10313–10325. Google Scholar
• [25] Foster DP (1991) Prediction in the worst case. Ann. Statist. 19(2):1084–1090.Crossref, Google Scholar
• [26] Hart S (2005) Adaptive heuristics. Econometrica 73(5):1401–1430.Crossref, Google Scholar
• [27] Hazan E (2022) Introduction to Online Convex Optimization, Adaptive Computation and Machine Learning Series, 2nd ed. (MIT Press, Cambridge, MA).Google Scholar
• [28] Hodgkinson L, Simsekli U, Khanna R, Mahoney MW (2021) Generalization properties of stochastic optimizers via trajectory analysis. Preprint, submitted August 2, https://arxiv.org/abs/2108.00781.Google Scholar
• [29] Juditsky AB, Nemirovsky AS (2019) Signal recovery by stochastic optimization. Automation Remote Control 80(10):1878–1893.Crossref, Google Scholar
• [30] Karimi H, Nutini J, Schmidt MW (2016) Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak- Lojasiewicz Condition. ECML/PKDD (University of British Columbia, Vancouver), 1–25.Google Scholar
• [31] Kavis A, Levy KY, Bach F, Cevher V (2019) Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates Inc., Red Hook, NY).Google Scholar
• [32] Kelly FP, Maulloo AK, Tan DKH (1998) Rate control for communication networks: Shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49(3):237–252.Crossref, Google Scholar
• [33] Kinderlehrer D, Stampacchia G (2000) An Introduction to Variational Inequalities and Their Applications (SIAM, Philadelphia).Google Scholar
• [34] Klén R, Visuri M, Vuorinen M (2010) On Jordan type inequalities for hyperbolic functions. J. Inequalities Appl. 2010(1):362548.Crossref, Google Scholar
• [35] Korpelevich GM (1976) The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody 12:747–756.Google Scholar
• [36] Larsson T, Patriksson M (1994) A class of gap functions for variational inequalities. Math. Programming 64:53–79.Crossref, Google Scholar
• [37] Leśniak K, Snigireva N, Strobin F, Vince A (2022) Transition phenomena for the attractor of an iterated function system. Nonlinearity 35(10):5396–5426.Crossref, Google Scholar
• [38] Levy KY, Yurtsever A, Cevher V (2018) Online adaptive methods, universality and acceleration. Adv. Neural Inform. Processing Systems, vol. 31 (Curran Associates Inc., Red Hook, NY), 781–789.Google Scholar
• [39] Li TY, Yorke JA (1975) Period three implies chaos. Amer. Math. Monthly 82(10):985–992.Crossref, Google Scholar
• [40] Mertikopoulos P, Staudigl M (2021) Equilibrium tracking and convergence in dynamic games. 60th IEEE Conf. Decision Control (IEEE, Piscataway, NJ), 930–935.Google Scholar
• [41] Mishchenko K, Khaled A, Richtarik P (2020) Random reshuffling: Simple analysis with vast improvements. Adv. Neural Inform. Processing Systems, vol. 33 (PMLR, New York), 17309–17320.Google Scholar
• [42] Mokhtari A, Shahrampour S, Jadbabaie A, Ribeiro A (2016) Online optimization in dynamic environments: Improved regret rates for strongly convex problems. IEEE 55th Conf. Decision Control (IEEE, Piscataway, NJ), 7195–7201.Google Scholar
• [43] Nedelec T, Calauzènes C, El Karoui N, Perchet V (2022) Learning in repeated auctions. Foundations Trends Machine Learn. 15(3):176–334.Crossref, Google Scholar
• [44] Nedic A, Bertsekas DP (2001) Incremental subgradient methods for nondifferentiable optimization. SIAM J. Optim. 12(1):109–138.Crossref, Google Scholar
• [45] Piliouras G, Yu FY (2023) Multi-agent performative prediction: From global stability and optimality to chaos. Proc. 24th ACM Conf. Econom. Comput. (ACM, New York).Google Scholar
• [46] Rahme J, Jelassi S, Weinberg SM (2021) Auction learning as a two-player game. Internat. Conf. Learn. Representations (Princeton University, Princeton, NJ).Google Scholar
• [47] Rakhlin A, Sridharan K (2013) Online learning with predictable sequences. Conf. Learn. Theory (PMLR, New York), 993–1019.Google Scholar
• [48] Rivera Cardoso A, Abernethy J, Wang H, Xu H (2019) Competing against Nash equilibria in adversarially changing zero-sum games. Proc. 36th Internat. Conf. Machine Learn., vol. 97 (PMLR, New York), 921–930.Google Scholar
• [49] Rockafellar RT, Wets RJB (1998) Variational Analysis (Springer, Berlin).Crossref, Google Scholar
• [50] Rosen JB (1965) Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33(3):520–534.Crossref, Google Scholar
• [51] Rota GC, Strang G (1960) A note on the joint spectral radius. Indagationes Mathematicae 63:379–381.Google Scholar
• [52] Ruette S (2017) Chaos on the Interval, vol. 67 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [53] Shalev-Shwartz S, Ben-David S (2014) Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [54] The MathWorks, Inc. (2020) incrementalRegressionLinear: Linear regression model for incremental learning. MATLAB Statistics and Machine Learning Toolbox Documentation (R2020a), https://nl.mathworks.com/help/stats/incrementalregressionlinear.html.Google Scholar
• [55] Van Erven T, Koolen WM, Van der Hoeven D (2021) Metagrad: Adaptation using multiple learning rates in online learning. J. Machine Learn. Res. 22(161):1–61.Google Scholar
• [56] Vovk VG (1995) A game of prediction with expert advice. Proc. Eighth Annual Conf. Comput. Learn. Theory (ACM, New York), 51–60.Google Scholar
• [57] Wei CY, Lee CW, Zhang M, Luo H (2021) Linear last-iterate convergence in constrained saddle-point optimization. ICLR’21 (University of Southern California, Los Angeles, CA).Google Scholar
• [58] Yan YH, Zhao P, Zhou ZH (2023) Fast rates in time-varying strongly monotone games. Proc. 40th Internat. Conf. Machine Learn., vol. 202 (PMLR, New York), 39138–39164.Google Scholar
• [59] Zhang L, Lu S, Zhou ZH (2018) Adaptive online learning in dynamic environments. Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (ACM, New York), 1330–1340.Google Scholar
• [60] Zhang M, Zhao P, Luo H, Zhou ZH (2022) No-regret learning in time-varying zero-sum games. Internat. Conf. Machine Learn. (PMLR, New York), 26772–26808.Google Scholar
• [61] Zhao P, Zhang L (2021) Improved analysis for dynamic regret of strongly convex and smooth functions. Learning for Dynamics and Control (PMLR, New York), 48–59.Google Scholar
• [62] Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent. Proc. 20th Internat. Conf. Machine Learn. (School of Computer Science Carnegie Mellon University Pittsburgh, PA), 928–936.Google Scholar