{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T20:24:31Z","timestamp":1768335871907,"version":"3.49.0"},"reference-count":39,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We present a new algorithm to solve min-max or min-min problems out of the convex world. We use rigidity assumptions, ubiquitous in learning, making our method \u2013 the backtrack H\u00f6lder algorithm applicable to many optimization problems. Our approach takes advantage of hidden regularity properties and allows us, in particular, to devise a simple algorithm of ridge type. An original feature of our method is to come with automatic step size adaptation which departs from the usual overly cautious backtracking methods. In a general framework, we provide convergence theoretical guarantees and rates. We apply our findings on simple Generative Adversarial Network (GAN) problems obtaining promising numerical results. It is worthwhile mentioning that a byproduct of our approach is a simple recipe for general H\u00f6lderian backtracking optimization.<\/jats:p>","DOI":"10.5802\/ojmo.24","type":"journal-article","created":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T05:16:46Z","timestamp":1703135806000},"page":"1-17","source":"Crossref","is-referenced-by-count":1,"title":["The backtrack H\u00f6lder gradient method with application to min-max and min-min problems"],"prefix":"10.5802","volume":"4","author":[{"given":"J\u00e9r\u00f4me","family":"Bolte","sequence":"first","affiliation":[]},{"given":"Lilian","family":"Glaudin","sequence":"additional","affiliation":[]},{"given":"Edouard","family":"Pauwels","sequence":"additional","affiliation":[]},{"given":"Mathieu","family":"Serrurier","sequence":"additional","affiliation":[]}],"member":"3842","published-online":{"date-parts":[[2023,12,21]]},"reference":[{"issue":"2","key":"key2025101710011321924_1","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/040605266","article-title":"Convergence of the iterates of descent methods for analytic cost functions","volume":"16","author":"Absil, Pierre-Antoine","year":"2005","unstructured":"[1] Absil, Pierre-Antoine; Mahony, Robert; Andrews, Benjamin Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim., Volume 16 (2005) no. 2, pp. 531-547","journal-title":"SIAM J. Optim."},{"key":"key2025101710011321924_2","first-page":"291","article-title":"Sorting Out Lipschitz Function Approximation","volume":"97","author":"Anil, Cem","year":"2019","unstructured":"[2] Anil, Cem; Lucas, James; Grosse, Roger, Proceedings of the 36th International Conference on Machine Learning (Chaudhuri, Kamalika; Salakhutdinov, Ruslan, eds.) (Proceedings of Machine Learning Research), Volume 97, PMLR (2019), pp. 291-301","journal-title":"Proceedings of the 36th International Conference on Machine Learning"},{"key":"key2025101710011321924_3","first-page":"214","article-title":"Wasserstein Generative Adversarial Networks","volume":"70","author":"Arjovsky, Martin","year":"2017","unstructured":"[3] Arjovsky, Martin; Chintala, Soumith; Bottou, L\u00e9on Wasserstein Generative Adversarial Networks, Proceedings of the 34th International Conference on Machine Learning (Precup, Doina; Teh, Yee Whye, eds.) (Proceedings of Machine Learning Research), Volume 70, PMLR (2017), pp. 214-223","journal-title":"Proceedings of the 34th International Conference on Machine Learning"},{"issue":"2","key":"key2025101710011321924_4","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1287\/moor.1100.0449","article-title":"Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-\u0141ojasiewicz inequality","volume":"35","author":"Attouch, H\u00e9dy","year":"2010","unstructured":"[4] Attouch, H\u00e9dy; Bolte, J\u00e9r\u00f4me; Redont, Patrick; Soubeyran, Antoine Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-\u0141ojasiewicz inequality, Math. Oper. Res., Volume 35 (2010) no. 2, pp. 438-457","journal-title":"Math. Oper. Res."},{"issue":"1-2","key":"key2025101710011321924_5","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10107-011-0484-9","article-title":"Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward\u2013backward splitting, and regularized Gauss\u2013Seidel methods","volume":"137","author":"Attouch, Hedy","year":"2013","unstructured":"[5] Attouch, Hedy; Bolte, J\u00e9r\u00f4me; Svaiter, Benar Fux Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward\u2013backward splitting, and regularized Gauss\u2013Seidel methods, Math. Program., Volume 137 (2013) no. 1-2, pp. 91-129","journal-title":"Math. Program."},{"issue":"1","key":"key2025101710011321924_6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s10957-020-01632-x","article-title":"On the Quality of First-Order Approximation of Functions with H\u00f6lder Continuous Gradient","volume":"185","author":"Berger, Guillaume O.","year":"2020","unstructured":"[6] Berger, Guillaume O.; Absil, Pierre-Antoine; Jungers, Rapha\u00ebl M.; Nesterov, Yurii On the Quality of First-Order Approximation of Functions with H\u00f6lder Continuous Gradient, J. Optim. Theory Appl., Volume 185 (2020) no. 1, pp. 17-33","journal-title":"J. Optim. Theory Appl."},{"key":"key2025101710011321924_7","author":"Bertsekas, Dimitri P.","year":"2014","unstructured":"[7] Bertsekas, Dimitri P. Constrained optimization and Lagrange multiplier methods, Academic Press Inc., 2014","journal-title":"Constrained optimization and Lagrange multiplier methods"},{"key":"key2025101710011321924_8","volume":"12","author":"Bochnak, Jacek","year":"1987","unstructured":"[8] Bochnak, Jacek; Coste, Michel; Roy, Marie-Fran\u00e7oise G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle, 12, Springer, 1987","journal-title":"G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle"},{"issue":"1-2","key":"key2025101710011321924_9","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10107-013-0701-9","article-title":"Proximal Alternating Linearized Minimization for Nonconvex and Nonsmooth Problems","volume":"146","author":"Bolte, J\u00e9r\u00f4me","year":"2014","unstructured":"[9] Bolte, J\u00e9r\u00f4me; Sabach, Shoham; Teboulle, Marc Proximal Alternating Linearized Minimization for Nonconvex and Nonsmooth Problems, Math. Program., Volume 146 (2014) no. 1-2, pp. 459-494","journal-title":"Math. Program."},{"issue":"4","key":"key2025101710011321924_10","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1287\/moor.2017.0900","article-title":"Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence","volume":"43","author":"Bolte, J\u00e9r\u00f4me","year":"2018","unstructured":"[10] Bolte, J\u00e9r\u00f4me; Sabach, Shoham; Teboulle, Marc Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence, Math. Oper. Res., Volume 43 (2018) no. 4, pp. 1210-1232","journal-title":"Math. Oper. Res."},{"key":"key2025101710011321924_11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","author":"Boyd, Stephen P.","year":"2004","unstructured":"[11] Boyd, Stephen P.; Vandenberghe, Lieven Convex Optimization, Cambridge University Press, 2004","journal-title":"Convex Optimization"},{"key":"key2025101710011321924_12","author":"Castera, Camille","year":"2019","unstructured":"[12] Castera, Camille; Bolte, J\u00e9r\u00f4me; F\u00e9votte, C\u00e9dric; Pauwels, Edouard An Inertial Newton Algorithm for Deep Learning (2019)","journal-title":"An Inertial Newton Algorithm for Deep Learning"},{"key":"key2025101710011321924_13","author":"Combettes, Patrick L.","year":"2017","unstructured":"[13] Combettes, Patrick L.; Bauschke, Heinz H. Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2017","journal-title":"Convex Analysis and Monotone Operator Theory in Hilbert Spaces"},{"key":"key2025101710011321924_14","article-title":"An Introduction to Semialgebraic Geometry","author":"Coste, Michel","year":"1999","unstructured":"[14] Coste, Michel An Introduction to Semialgebraic Geometry, RAAG Notes (1999)","journal-title":"RAAG Notes"},{"key":"key2025101710011321924_15","first-page":"2292","article-title":"Sinkhorn distances: Lightspeed computation of optimal transport","author":"Cuturi, Marco","year":"2013","unstructured":"[15] Cuturi, Marco Sinkhorn distances: Lightspeed computation of optimal transport, Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2, Curran Associates Inc. (2013), pp. 2292-2300","journal-title":"Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2"},{"key":"key2025101710011321924_16","author":"Genevay, Aude","year":"2017","unstructured":"[16] Genevay, Aude; Peyr\u00e9, Gabriel; Cuturi, Marco GAN and VAE from an Optimal Transport Point of View (2017)","journal-title":"GAN and VAE from an Optimal Transport Point of View"},{"key":"key2025101710011321924_17","first-page":"1608","article-title":"Learning Generative Models with Sinkhorn Divergences","volume":"84","author":"Genevay, Aude","year":"2018","unstructured":"[17] Genevay, Aude; Peyr\u00e9, Gabriel; Cuturi, Marco Learning Generative Models with Sinkhorn Divergences, Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (Storkey, Amos; Perez-Cruz, Fernando, eds.) (Proceedings of Machine Learning Research), Volume 84, PMLR (2018), pp. 1608-1617","journal-title":"Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics"},{"key":"key2025101710011321924_18","article-title":"A Variational Inequality Perspective on Generative Adversarial Networks","author":"Gidel, Gauthier","year":"2019","unstructured":"[18] Gidel, Gauthier; Berard, Hugo; Vignoud, Ga\u00ebtan; Vincent, Pascal; Lacoste-Julien, Simon A Variational Inequality Perspective on Generative Adversarial Networks, International Conference on Learning Representations (2019) https:\/\/openreview.net\/forum?id=r1laena5ym","journal-title":"International Conference on Learning Representations"},{"key":"key2025101710011321924_19","first-page":"2672","article-title":"Generative Adversarial Nets","author":"Goodfellow, Ian","year":"2014","unstructured":"[19] Goodfellow, Ian; Pouget-Abadie, Jean; Mirza, Mehdi; Xu, Bing; Warde-Farley, David; Ozair, Sherjil; Courville, Aaron; Bengio, Yoshua Generative Adversarial Nets, Proceedings of the 27th International Conference on Neural Information Processing Systems (Ghahramani, Z.; Welling, M.; Cortes, C.; Lawrence, N. D.; Weinberger, K. Q., eds.), Curran Associates, Inc., 2014, pp. 2672-2680","journal-title":"Proceedings of the 27th International Conference on Neural Information Processing Systems"},{"key":"key2025101710011321924_20","author":"Grapiglia, Geovani N.","year":"2019","unstructured":"[20] Grapiglia, Geovani N.; Nesterov, Yurii Tensor Methods for Minimizing Functions with H\u00f6lder Continuous Higher-Order Derivatives (2019)","journal-title":"Tensor Methods for Minimizing Functions with H\u00f6lder Continuous Higher-Order Derivatives"},{"key":"key2025101710011321924_21","first-page":"5769","article-title":"Improved Training of Wasserstein GANs","author":"Gulrajani, Ishaan","year":"2017","unstructured":"[21] Gulrajani, Ishaan; Ahmed, Faruk; Arjovsky, Martin; Dumoulin, Vincent; Courville, Aaron, Proceedings of the 31st International Conference on Neural Information Processing Systems, Curran Associates Inc. (2017), pp. 5769-5779","journal-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems"},{"key":"key2025101710011321924_22","first-page":"6936","article-title":"On the convergence of single-call stochastic extra-gradient methods","author":"Hsieh, Yu-Guan","year":"2019","unstructured":"[22] Hsieh, Yu-Guan; Iutzeler, Franck; Malick, J\u00e9r\u00f4me; Mertikopoulos, Panayotis On the convergence of single-call stochastic extra-gradient methods, Proceedings of the 32th International Conference on Neural Information Processing Systems (2019), pp. 6936-6946","journal-title":"Proceedings of the 32th International Conference on Neural Information Processing Systems"},{"issue":"4","key":"key2025101710011321924_23","first-page":"747","article-title":"An extragradient method for finding saddle points and for other problems","volume":"12","author":"Korpelevich, G. M.","year":"1976","unstructured":"[23] Korpelevich, G. M. An extragradient method for finding saddle points and for other problems, Ehkon. Mat. Metody, Volume 12 (1976) no. 4, pp. 747-756","journal-title":"Ehkon. Mat. Metody"},{"issue":"3","key":"key2025101710011321924_24","doi-asserted-by":"publisher","first-page":"769","DOI":"10.5802\/aif.1638","article-title":"On gradients of functions definable in o-minimal structures","volume":"48","author":"Kurdyka, Krzysztof","year":"1998","unstructured":"[24] Kurdyka, Krzysztof On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier, Volume 48 (1998) no. 3, pp. 769-783","journal-title":"Ann. Inst. Fourier"},{"key":"key2025101710011321924_25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26646-2","author":"Laraki, Rida","year":"2019","unstructured":"[25] Laraki, Rida; Renault, J\u00e9r\u00f4me; Sorin, Sylvain Mathematical foundations of game theory, Springer, 2019","journal-title":"Mathematical foundations of game theory"},{"key":"key2025101710011321924_26","author":"Lin, Tianyi","year":"2020","unstructured":"[26] Lin, Tianyi; Jin, Chi; Jordan, Michael I. On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2020)","journal-title":"On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems"},{"key":"key2025101710011321924_27","article-title":"Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile","author":"Mertikopoulos, Panayotis","year":"2019","unstructured":"[27] Mertikopoulos, Panayotis; Lecouat, Bruno; Zenati, Houssam; Foo, Chuan-Sheng; Chandrasekhar, Vijay; Piliouras, Georgios Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile, International Conference on Learning Representations (2019) https:\/\/openreview.net\/forum?id=bkg8jjc9kq","journal-title":"International Conference on Learning Representations"},{"issue":"1","key":"key2025101710011321924_28","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/S1052623403425629","article-title":"Prox-Method with Rate of Convergence <span class=\"mathjax-formula\" data-tex=\"${O}(1\/t)$\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mrow><mi>O<\/mi><mo>(<\/mo><mn>1<\/mn><mo>\/<\/mo><mi>t<\/mi><mo>)<\/mo><\/mrow><\/math><\/span> ) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems","volume":"15","author":"Nemirovski, Arkadi","year":"2004","unstructured":"[28] Nemirovski, Arkadi Prox-Method with Rate of Convergence O(1\/t) ) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems, SIAM J. Optim., Volume 15 (2004) no. 1, pp. 229-251","journal-title":"SIAM J. Optim."},{"issue":"1-2","key":"key2025101710011321924_29","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s10107-014-0790-0","article-title":"Universal Gradient Methods for Convex Optimization Problems","volume":"152","author":"Nesterov, Yu","year":"2015","unstructured":"[29] Nesterov, Yu Universal Gradient Methods for Convex Optimization Problems, Math. Program., Volume 152 (2015) no. 1-2, pp. 381-404","journal-title":"Math. Program."},{"key":"key2025101710011321924_30","first-page":"14905","article-title":"Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods","author":"Nouiehed, Maher","year":"2019","unstructured":"[30] Nouiehed, Maher; Sanjabi, Maziar; Huang, Tianjian; Lee, Jason D.; Razaviyayn, Meisam Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods, Proceedings of the 32th International Conference on Neural Information Processing Systems (Wallach, H.; Larochelle, H.; Beygelzimer, A.; dAlch\u00e9-Buc, F.; Fox, E.; Garnett, R., eds.), Curran Associates, Inc., 2019, pp. 14905-14916","journal-title":"Proceedings of the 32th International Conference on Neural Information Processing Systems"},{"key":"key2025101710011321924_31","first-page":"14934","article-title":"Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods","author":"Nouiehed, Maher","year":"2019","unstructured":"[31] Nouiehed, Maher; Sanjabi, Maziar; Huang, Tianjian; Lee, Jason D.; Razaviyayn, Meisam Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods, Proceedings of the 32th International Conference on Neural Information Processing Systems (Wallach, H.; Larochelle, H.; Beygelzimer, A.; d\u2019Alch\u00e9-Buc, F.; Fox, E.; Garnett, R., eds.), Curran Associates, Inc., 2019, pp. 14934-14942","journal-title":"Proceedings of the 32th International Conference on Neural Information Processing Systems"},{"issue":"3","key":"key2025101710011321924_32","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1287\/moor.6.3.424","article-title":"Proximal subgradients, marginal values, and augmented Lagrangians in nonconvex optimization","volume":"6","author":"Rockafellar, R. Tyrrell","year":"1981","unstructured":"[32] Rockafellar, R. Tyrrell Proximal subgradients, marginal values, and augmented Lagrangians in nonconvex optimization, Math. Oper. Res., Volume 6 (1981) no. 3, pp. 424-436","journal-title":"Math. Oper. Res."},{"issue":"317","key":"key2025101710011321924_33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02431-3","author":"Rockafellar, R. Tyrrell","year":"1998","unstructured":"[33] Rockafellar, R. Tyrrell; Wets, Roger J.-B. Variational Analysis, Grundlehren der Mathematischen Wissenschaften, Springer, 1998 no. 317","journal-title":"Variational Analysis"},{"key":"key2025101710011321924_34","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/bs.hna.2019.04.002","article-title":"Lagrangian Methods for Composite Optimization","volume":"20","author":"Sabach, Shoham","year":"2019","unstructured":"[34] Sabach, Shoham; Teboulle, Marc Lagrangian Methods for Composite Optimization, Processing, analyzing and learning of images, shapes, and forms. Part 2 (Handbook of Numerical Analysis), Volume 20, Elsevier, 2019, pp. 401-436","journal-title":"Processing, analyzing and learning of images, shapes, and forms. Part 2"},{"issue":"2","key":"key2025101710011321924_35","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1214\/aoms\/1177703591","article-title":"A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices","volume":"35","author":"Sinkhorn, Richard","year":"1964","unstructured":"[35] Sinkhorn, Richard A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices, Ann. Math. Stat., Volume 35 (1964) no. 2, pp. 876-879","journal-title":"Ann. Math. Stat."},{"issue":"1","key":"key2025101710011321924_36","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01448847","article-title":"Zur theorie der gesellschaftsspiele","volume":"100","author":"Von Neumann, John","year":"1928","unstructured":"[36] Von Neumann, John Zur theorie der gesellschaftsspiele, Math. Ann., Volume 100 (1928) no. 1, pp. 295-320","journal-title":"Math. Ann."},{"issue":"2","key":"key2025101710011321924_37","doi-asserted-by":"publisher","first-page":"401","DOI":"10.2307\/1969463","article-title":"On Rings of Operators. Reduction Theory","volume":"50","author":"Von Neumann, John","year":"1949","unstructured":"[37] Von Neumann, John On Rings of Operators. Reduction Theory, Ann. Math., Volume 50 (1949) no. 2, pp. 401-485","journal-title":"Ann. Math."},{"key":"key2025101710011321924_38","author":"Wang, Jingkang","year":"2019","unstructured":"[38] Wang, Jingkang; Zhang, Tianyun; Liu, Sijia; Chen, Pin-Yu; Xu, Jiacen; Fardad, Makan; Li, Bo Towards A Unified Min-Max Framework for Adversarial Exploration and Robustness (2019)","journal-title":"Towards A Unified Min-Max Framework for Adversarial Exploration and Robustness"},{"issue":"6","key":"key2025101710011321924_39","doi-asserted-by":"publisher","first-page":"1361","DOI":"10.1007\/s11590-015-0936-x","article-title":"On the Global Convergence Rate of the Gradient Descent Method for Functions with H\u00f6lder Continuous Gradients","volume":"10","author":"Yashtini, Maryam","year":"2016","unstructured":"[39] Yashtini, Maryam On the Global Convergence Rate of the Gradient Descent Method for Functions with H\u00f6lder Continuous Gradients, Optim. Lett., Volume 10 (2016) no. 6, pp. 1361-1370","journal-title":"Optim. Lett."}],"container-title":["Open Journal of Mathematical Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/ojmo.centre-mersenne.org\/item\/10.5802\/ojmo.24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T08:02:53Z","timestamp":1760688173000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojmo.centre-mersenne.org\/articles\/10.5802\/ojmo.24\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,21]]},"references-count":39,"alternative-id":["10.5802\/ojmo.24"],"URL":"https:\/\/doi.org\/10.5802\/ojmo.24","relation":{},"ISSN":["2777-5860"],"issn-type":[{"value":"2777-5860","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,21]]},"article-number":"8"}}