Variance-Reduced Fast Krasnosel’skiǐ-Mann Methods for Finite-Sum Root-Finding Problems

References

• [1] Adly S, Attouch H (2021) First-order inertial algorithms involving dry friction damping. Math. Programming 193:405–445.Crossref, Google Scholar
• [2] Alacaoglu A, Malitsky Y (2022) Stochastic variance reduction for variational inequality methods. Proc. 35th Conf. Learn. Theory, vol. 178 (PMLR), 778–816.Google Scholar
• [3] Alacaoglu A, Böhm A, Malitsky Y (2023) Beyond the golden ratio for variational inequality algorithms. J. Mach. Learn. Res. 24(172):1–33.Google Scholar
• [4] Allen-Zhu Z, Yuan Y (2016) Improved SVRG for non-strongly-convex or sum-of-non-convex objectives. Balcan MF, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol 48 (PMLR, New York), 1080–1089.Google Scholar
• [5] Attouch H, Cabot A (2020) Convergence of a relaxed inertial proximal algorithm for maximally monotone operators. Math. Programming 184(1):243–287.Crossref, Google Scholar
• [6] Attouch H, Fadili J (2022) From the Ravine method to the Nesterov method and vice versa: A dynamical system perspective. SIAM J. Optim. 32(3):2074–2101.Crossref, Google Scholar
• [7] Attouch H, Peypouquet J (2016) The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than O(1/k2). SIAM J. Optim. 26(3):1824–1834.Crossref, Google Scholar
• [8] Attouch H, Peypouquet J (2019) Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators. Math. Programming 174(1–2):391–432.Crossref, Google Scholar
• [9] Attouch H, Peypouquet J, Redont P (2018) Backward–forward algorithms for structured monotone inclusions in Hilbert spaces. J. Math. Anal. Appl. 457(2):1095–1117.Crossref, Google Scholar
• [10] Bauschke HH, Combettes P (2017) Convex Analysis and Monotone Operators Theory in Hilbert Spaces, 2nd ed., CMS Books in Mathematics (Springer, Cham, Switzerland).Crossref, Google Scholar
• [11] Bauschke HH, Moursi WM, Wang X (2021) Generalized monotone operators and their averaged resolvents. Math. Programming 189(Series B):55–74.Crossref, Google Scholar
• [12] Beznosikov A, Gorbunov E, Berard H, Loizou N (2023) Stochastic gradient descent-ascent: Unified theory and new efficient methods. Ruiz F, Dy J, van de Meent JW, eds. Proc. 26th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol 206 (PMLR, New York), 172–235.Google Scholar
• [13] Bohm A, Sedlmayer M, Csetnek RE, Bot RI (2022) Two steps at a time—Taking GAN training in stride with Tseng’s method. SIAM J. Math. Data Sci. 4(2):750–771.Crossref, Google Scholar
• [14] Bot RI, Nguyen DK (2023) Fast Krasnoselśkii-Mann algorithm with a convergence rate of the fixed point iteration of o(1/k). SIAM J. Numer. Anal. 61(6):2813–2843.Crossref, Google Scholar
• [15] Bot RI, Mertikopoulos P, Staudigl M, Vuong PT (2021) Forward-backward-forward methods with variance reduction for stochastic variational inequalities. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan JW, eds. Adv. Neural Inform. Processing Systems 34 (NeurIPS 2021) (Curran Associates Inc., Red Hook, NY), 24199–24210.Google Scholar
• [16] Burachik RS, Iusem A (2008) Set-Valued Mappings and Enlargements of Monotone Operators (Springer, New York).Google Scholar
• [17] Cai Y, Zheng W (2023) Accelerated single-call methods for constrained min-max optimization. 11th Internat. Conf. Learn. Representations (ICLR 2023).Google Scholar
• [18] Cai X, Alacaoglu A, Diakonikolas J (2024) Variance reduced Halpern iteration for finite-sum monotone inclusions. Proc. 12th Internat. Conf. Learn. Representations (ICLR 2024) (OpenReview.net, Vienna, Austria), 1–33.Google Scholar
• [19] Cai Y, Oikonomou A, Zheng W (2022a) Accelerated algorithms for monotone inclusions and constrained nonconvex-nonconcave minmax optimization. Jain P, Pedregosa F, eds. OPT 2022: 14th Workshop Optim. Machine Learn. (NeurIPS 2022 Workshop), Proceedings of Machine Learning Research, vol 209 (PMLR, New Orleans), 1–25.Google Scholar
• [20] Cai X, Song C, Guzmán C, Diakonikolas J (2022a) A stochastic Halpern iteration with variance reduction for stochastic monotone inclusion problems. Proc. 10th Internat. Conf. Learn. Representations (ICLR 2022) (OpenReview.net, Vienna, Austria), 1–36.Google Scholar
• [21] Carmon Y, Jin Y, Sidford A, Tian K (2019) Variance reduction for matrix games. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, eds. NIPS’19: Proc. 33rd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 11381–11392.Google Scholar
• [22] Chambolle A, Dossal C (2015) On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm. J. Optim. Theory Appl. 166(3):968–982.Crossref, Google Scholar
• [23] Chavdarova T, Gidel G, Fleuret F, Lacoste-Julien S (2019) Reducing noise in GAN training with variance reduced extragradient. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, eds. NIPS’19: Proc. 33rd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 393–403.Google Scholar
• [24] Chen Y, Lan G, Ouyang Y (2017) Accelerated schemes for a class of variational inequalities. Math. Programming 165(1):113–149.Crossref, Google Scholar
• [25] Combettes PL, Pesquet JC (2015) Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping. SIAM J. Optim. 25(2):1221–1248.Crossref, Google Scholar
• [26] Cominetti R, Soto JA, Vaisman J (2014) On the rate of convergence of Krasnosel’skiĭ–Mann iterations and their connection with sums of Bernoullis. Israel J. Math. 199:757–772.Crossref, Google Scholar
• [27] Cui S, Shanbhag U (2021) On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems. Set.-Valued Variational Anal. 29(2):453–499.Crossref, Google Scholar
• [28] Daskalakis C, Ilyas A, Syrgkanis V, Zeng H (2018) Training GANs with optimism. Proc. 6th Internat. Conf. Learn. Representations (ICLR 2018) (OpenReview.net, Vancouver), 1–9.Google Scholar
• [29] Davis D (2016) SMART: The stochastic monotone aggregated root-finding algorithm. Preprint, submitted January 4, https://arxiv.org/abs/1601.00698.Google Scholar
• [30] Davis D (2022) Variance reduction for root-finding problems. Math. Programming 197:375–410.Crossref, Google Scholar
• [31] Defazio A, Bach F, Lacoste-Julien S (2014) SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. NIPS’14: Proc. 28th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 1646–1654.Google Scholar
• [32] Diakonikolas J (2020) Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. Abernethy J, Agarwal S, eds. Proc. 33rd Conf. Learn. Theory, Proceedings of Machine Learning Research, vol 125 (PMLR, New York), 1428–1451.Google Scholar
• [33] Driggs D, Ehrhardt MJ, Schönlieb CB (2020) Accelerating variance-reduced stochastic gradient methods. Math. Programming 191:671–715.Crossref, Google Scholar
• [34] Facchinei F, Pang JS (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. 1–2, Springer Series in Operations Research and Financial Engineering (Springer, New York).Google Scholar
• [35] Friedman J, Hastie T, Tibshirani R (2001) The Elements of Statistical Learning, vol. 1 (Springer, New York).Google Scholar
• [36] Fukushima M (1992) Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Programming 53:99–110.Crossref, Google Scholar
• [37] Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y (2014) Generative adversarial nets. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. NIPS’14: Proc. 28th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 2672–2680.Google Scholar
• [38] Gorbunov E, Hanzely F, Richtárik P (2020) A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. Chiappa S, Calandra R, eds. Proc. 23rd Internat. Conf. Artificial Intelligence and Statist., Proceedings of Machine Learning Research, vol 108 (PMLR, New York), 680–690.Google Scholar
• [39] Gorbunov E, Berard H, Gidel G, Loizou N (2022) Stochastic extragradient: General analysis and improved rates. Camps-Valls G, Ruiz F, Valera I, eds. Proc. 25th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol 151 (PMLR, New York), 7865–7901.Google Scholar
• [40] Gower RM, Loizou N, Qian X, Sailanbayev A, Shulgin E, Richtárik P (2019) SGD: General analysis and improved rates. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol 97 (PMLR, New York), 5200–5209.Google Scholar
• [41] Halpern B (1967) Fixed points of nonexpanding maps. Bull. Amer. Math. Soc. 73(6):957–961.Crossref, Google Scholar
• [42] He Y, Monteiro RD (2016) An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems. SIAM J. Optim. 26(1):29–56.Crossref, Google Scholar
• [43] Huang K, Wang N, Zhang S (2026) An accelerated variance reduced extra-point approach to finite-sum VI and optimization. SIAM J. Optim. 36(2):1154–1181.Crossref, Google Scholar
• [44] Iusem AN, Jofré A, Oliveira RI, Thompson P (2017) Extragradient method with variance reduction for stochastic variational inequalities. SIAM J. Optim. 27(2):686–724.Crossref, Google Scholar
• [45] Johnson R, Zhang T (2013) Accelerating stochastic gradient descent using predictive variance reduction. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. NIPS’13: Proc. 27th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 315–323.Google Scholar
• [46] Juditsky A, Nemirovski A, Tauvel C (2011) Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems 1(1):17–58.Link, Google Scholar
• [47] Kannan A, Shanbhag UV (2019) Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants. Comput. Optim. Appl. 74(3):779–820.Crossref, Google Scholar
• [48] Khalafi M, Boob D (2023) Accelerated primal-dual methods for convex-strongly-concave saddle point problems. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol 202 (PMLR, New York), 16250–16270.Google Scholar
• [49] Khaled A, Sebbouh O, Loizou N, Gower RM, Richtárik P (2023) Unified analysis of stochastic gradient methods for composite convex and smooth optimization. J. Optim. Theory Appl. 199(2):499–540.Crossref, Google Scholar
• [50] Kim D (2021) Accelerated proximal point method for maximally monotone operators. Math. Programming 190:57–87.Crossref, Google Scholar
• [51] Kolossoski O, Monteiro RD (2017) An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex–concave saddle-point problems. Optim. Methods Software 32(6):1244–1272.Crossref, Google Scholar
• [52] Kotsalis G, Lan G, Li T (2022) Simple and optimal methods for stochastic variational inequalities-I: Operator extrapolation. SIAM J. Optim. 32(3):2041–2073.Crossref, Google Scholar
• [53] Kovalev D, Horváth S, Richtárik P (2020) Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. Kontorovich A, Verdier G, eds. Proc. 31st Internatt. Conf. Algorithmic Learn. Theory, Proceedings of Machine Learning Research, vol 117 (PMLR, New York), 451–467.Google Scholar
• [54] Krasnosel’skiǐ MA (1955) Two remarks on the method of successive approximations. Uspekhi Matematicheskikh Nauk. 10(1):123–127.Google Scholar
• [55] Kuhn D, Shafiee S, Wiesemann W (2025) Distributionally robust optimization. Acta Numer. 34:579–804.Crossref, Google Scholar
• [56] Lee S, Kim D (2021) Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. NIPS’21: Proc. 35th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 22588–22600.Google Scholar
• [57] Lieder F (2021) On the convergence rate of the Halpern-iteration. Optim. Lett. 15(2):405–418.Crossref, Google Scholar
• [58] Loizou N, Berard H, Gidel G, Mitliagkas I, Lacoste-Julien S (2021) Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. NIPS’21: Proc. 35th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 19095–19108.Google Scholar
• [59] Madry A, Makelov A, Schmidt L, Tsipras D, Vladu A (2018) Towards deep learning models resistant to adversarial attacks. Proc. 6th Internat. Conf. Learn. Representations (ICLR 2018) (OpenReview.net, Vancouver), 1–28.Google Scholar
• [60] Maingé PE (2021) Accelerated proximal algorithms with a correction term for monotone inclusions. Appl. Math. Optim. 84(2):2027–2061.Crossref, Google Scholar
• [61] Mann WR (1953) Mean value methods in iteration. Proc. Amer. Math. Soc. 4(3):506–510.Crossref, Google Scholar
• [62] Mishchenko K, Kovalev D, Shulgin E, Richtárik P, Malitsky Y (2020) Revisiting stochastic extragradient. Chiappa S, Calandra R, eds. Proc. 23rd Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol 108 (PMLR, New York), 4573–4582.Google Scholar
• [63] Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course, Applied Optimization, vol. 87 (Springer, Boston).Crossref, Google Scholar
• [64] Nesterov Y (2007) Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Programming 109(2–3):319–344.Crossref, Google Scholar
• [65] Nguyen LM, Liu J, Scheinberg K, Takáč M (2017) SARAH: A novel method for machine learning problems using stochastic recursive gradient. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn. Proceedings of Machine Learning Research, vol 70 (PMLR, New York), 2613–2621.Google Scholar
• [66] Palaniappan B, Bach F (2016) Stochastic variance reduction methods for saddle-point problems. Lee DD, von Luxburg U, Garnett R, Sugiyama M, Guyon I, eds. NIPS’16: Proc. 30th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 1416–1424.Google Scholar
• [67] Park J, Ryu EK (2022b) Exact optimal accelerated complexity for fixed-point iterations. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol 162 (PMLR, New York), 17420–17457.Google Scholar
• [68] Peng Z, Xu Y, Yan M, Yin W (2016) ARock: An algorithmic framework for asynchronous parallel coordinate updates. SIAM J. Sci. Comput. 38(5):2851–2879.Crossref, Google Scholar
• [69] Pethick T, Fercoq O, Latafat P, Patrinos P, Cevher V (2023) Solving stochastic weak Minty variational inequalities without increasing batch size. Proc. 11th Internat. Conf. Learn. Representations (ICLR 2023) (OpenReview.net, Kigali, Rwanda), 1–34.Google Scholar
• [70] Phelps RR (2009) Convex Functions, Monotone Operators and Differentiability, Notes in Mathematics, vol. 1364 (Springer, Berlin, Heidelberg).Google Scholar
• [71] Robbins H, Siegmund D (1971) A convergence theorem for non negative almost supermartingales and some applications. Rustagi JS, ed. Optimizing Methods in Statistics (Academic Press, New York), 233–257.Google Scholar
• [72] Rockafellar R, Wets R (2004) Variational Analysis, Grundlehren der mathematischen Wissenschaften, vol. 317 (Springer, Berlin, Heidelberg).Google Scholar
• [73] Ryu EK, Boyd S (2016) Primer on monotone operator methods. Appl. Comput. Math. 15(1):3–43.Google Scholar
• [74] Ryu E, Yin W (2022) Large-Scale Convex Optimization: Algorithms & Analyses via Monotone Operators (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [75] Sabach S, Shtern S (2017) A first order method for solving convex bilevel optimization problems. SIAM J. Optim. 27(2):640–660.Crossref, Google Scholar
• [76] Tran-Dinh Q (2024a) Extragradient-type methods with O(1/k)-convergence rates for co-hypomonotone inclusions. J. Global Optim. 89(1):197–221.Crossref, Google Scholar
• [77] Tran-Dinh Q (2024b) From Halpern’s fixed-point iterations to Nesterov’s accelerated interpretations for root-finding problems. Comput. Optim. App. 87(1):181–218.Crossref, Google Scholar
• [78] Tran-Dinh Q, Luo Y (2021) Halpern-type accelerated and splitting algorithms for monotone inclusions. Preprint, submitted February 9, https://arxiv.org/abs/2110.08150.Google Scholar
• [79] Tran-Dinh Q, Pham NH, Phan DT, Nguyen LM (2022) A hybrid stochastic optimization framework for stochastic composite nonconvex optimization. Math. Programming 191:1005–1071.Crossref, Google Scholar
• [80] von Neumann J (1928) Zur theorie der gesellshaftsspiele. Math. Ann. 100:295–320.Crossref, Google Scholar
• [81] Yang J, Zhang S, Kiyavash N, He N (2020) A catalyst framework for minimax optimization. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. NIPS’20: Proc. 34th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 5667–5678.Google Scholar
• [82] Yoon T, Ryu EK (2021) Accelerated algorithms for smooth convex-concave minimax problems with O(1/k2) rate on squared gradient norm. Meila M, Zhang T, eds. Proce. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol 139 (PMLR, New York), 12098–12109.Google Scholar
• [83] Yousefian F, Nedić A, Shanbhag UV (2018) On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: Randomized block coordinate and optimal averaging schemes. Set.-Valued Variational Anal. 26:789–819.Crossref, Google Scholar
• [84] Yu Y, Lin T, Mazumdar EV, Jordan MI (2022) Fast distributionally robust learning with variance-reduced min-max optimization. Camps-Valls G, Ruiz F, Valera I, eds. Proc. 25th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol 151 (PMLR, New York), 1219–1250.Google Scholar
• [85] Zhang J, Hong M, Zhang S (2022) On lower iteration complexity bounds for the convex-concave saddle point problems. Math. Programming 194(1):901–935.Crossref, Google Scholar
• [86] Zhou D, Xu P, Gu Q (2018) Stochastic nested variance reduction for nonconvex optimization. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, eds. NIPS’18: Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 3925–3936.Google Scholar