A Riemannian Alternating Descent Ascent Algorithmic Framework for Nonconvex-Linear Minimax Problems on Riemannian Manifolds

References

• [1] Absil PA, Malick J (2012) Projection-like retractions on matrix manifolds. SIAM J. Optim. 22(1):135–158.Crossref, Google Scholar
• [2] Absil PA, Mahony R, Sepulchre R (2008) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ). Crossref, Google Scholar
• [3] Barzilai J, Borwein JM (1988) Two-point step size gradient methods. IMA J. Numerical Anal. 8(1):141–148.Crossref, Google Scholar
• [4] Beck A (2017) First-Order Methods in Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• [5] Beck A, Rosset I (2023) A dynamic smoothing technique for a class of nonsmooth optimization problems on manifolds. SIAM J. Optim. 33(3):1473–1493.Crossref, Google Scholar
• [6] Bendokat T, Zimmermann R, Absil PA (2024) A Grassmann manifold handbook: Basic geometry and computational aspects. Adv. Comput. Math. 50(1):1–51.Crossref, Google Scholar
• [7] Borckmans PB, Selvan SE, Boumal N, Absil PA (2014) A Riemannian subgradient algorithm for economic dispatch with valve-point effect. J. Comput. Appl. Math. 255:848–866.Crossref, Google Scholar
• [8] Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [9] Boumal N, Absil PA, Cartis C (2019) Global rates of convergence for nonconvex optimization on manifolds. IMA J. Numerical Anal. 39(1):1–33.Crossref, Google Scholar
• [10] Chen L, Sun D, Toh KC (2017) An efficient inexact symmetric Gauss–Seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Programming 161:237–270.Crossref, Google Scholar
• [11] Chen S, Ma S, So AMC, Zhang T (2020) Proximal gradient method for nonsmooth optimization over the Stiefel manifold. SIAM J. Optim. 30(1):210–239.Crossref, Google Scholar
• [12] Chen S, Ma S, So AMC, Zhang T (2024) Nonsmooth optimization over the Stiefel manifold and beyond: Proximal gradient method and recent variants. SIAM Rev. 66(2):319–352.Crossref, Google Scholar
• [13] Deng K, Peng Z (2023) A manifold inexact augmented Lagrangian method for nonsmooth optimization on Riemannian submanifolds in Euclidean space. IMA J. Numerical Anal. 43(3):1653–1684.Crossref, Google Scholar
• [14] Deng K, Hu J, Wu J, Wen Z (2025) Oracle complexities of augmented Lagrangian methods for nonsmooth manifold optimization. Math. Oper. Res. Forthcoming.Link, Google Scholar
• [15] Drusvyatskiy D, Paquette C (2019) Efficiency of minimizing compositions of convex functions and smooth maps. Math. Programming 178(1):503–558.Crossref, Google Scholar
• [16] Gao B, Liu X, Chen X, Yuan Y (2018) A new first-order algorithmic framework for optimization problems with orthogonality constraints. SIAM J. Optim. 28(1):302–332.Crossref, Google Scholar
• [17] Hajinezhad D, Hong M (2019) Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization. Math. Programming 176(1):207–245.Crossref, Google Scholar
• [18] Han A, Mishra B, Jawanpuria P, Gao J (2023) Nonconvex-nonconcave min-max optimization on Riemannian manifolds. Trans. Machine Learn. Res.Google Scholar
• [19] Han A, Mishra B, Jawanpuria P, Kumar P, Gao J (2023) Riemannian Hamiltonian methods for min-max optimization on manifolds. SIAM J. Optim. 33(3):1797–1827.Crossref, Google Scholar
• [20] He J, Zhang H, Xu Z (2024) An approximation proximal gradient algorithm for nonconvex-linear minimax problems with nonconvex nonsmooth terms. J. Global Optim. 90(1):73–92.Crossref, Google Scholar
• [21] Hosseini S, Uschmajew A (2017) A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM J. Optim. 27(1):173–189.Crossref, Google Scholar
• [22] Hosseini S, Huang W, Yousefpour R (2018) Line search algorithms for locally Lipschitz functions on Riemannian manifolds. SIAM J. Optim. 28(1):596–619.Crossref, Google Scholar
• [23] Hu J, Liu X, Wen Z, Yuan Y (2020) A brief introduction to manifold optimization. J. Oper. Res. Soc. China 8(1):199–248.Crossref, Google Scholar
• [24] Hu J, Milzarek A, Wen Z, Yuan Y (2018) Adaptive quadratically regularized Newton method for Riemannian optimization. SIAM J. Matrix Anal. Appl. 39(3):1181–1207.Crossref, Google Scholar
• [25] Hu X, Xiao N, Liu X, Toh KC (2024) A constraint dissolving approach for nonsmooth optimization over the Stiefel manifold. IMA J. Numerical Anal. 44(6):3717–3748.Crossref, Google Scholar
• [26] Huang F, Gao S (2023) Gradient descent ascent for minimax problems on Riemannian manifolds. IEEE Trans. Pattern Anal. Machine Intelligence 45(7):8466–8476.Google Scholar
• [27] Huang W, Wei K (2022) Riemannian proximal gradient methods. Math. Programming 194(1):371–413.Crossref, Google Scholar
• [28] Huang W, Wei K (2023) An inexact Riemannian proximal gradient method. Comput. Optim. Appl. 85(1):1–32.Crossref, Google Scholar
• [29] Iannazzo B, Porcelli M (2018) The Riemannian Barzilai-Borwein method with nonmonotone line search and the matrix geometric mean computation. IMA J. Numerical Anal. 38(1):495–517.Crossref, Google Scholar
• [30] Jiang B, Dai YH (2015) A framework of constraint preserving update schemes for optimization on Stiefel manifold. Math. Programming 153(2):535–575.Crossref, Google Scholar
• [31] Jiang B, Liu YF (2023) A Riemannian exponential augmented Lagrangian method for computing the projection robust Wasserstein distance. Proc. Adv. Neural Inform. Processing Systems, vol. 36 (Curran Associates, Inc., Red Hook, NY), 79999–80023.Crossref, Google Scholar
• [32] Jin C, Netrapalli P, Jordan M (2020) What is local optimality in nonconvex-nonconcave minimax optimization? Proc. Internat. Conf. Machine Learn., vol. 119 (PMLR, New York), 4880–4889.Google Scholar
• [33] Jolliffe IT, Trendafilov NT, Uddin M (2003) A modified principal component technique based on the LASSO. J. Comput. Graphical Statist. 12(3):531–547.Crossref, Google Scholar
• [34] Jordan M, Lin T, Vlatakis-Gkaragkounis EV (2022) First-order algorithms for min-max optimization in geodesic metric spaces. Proc. Adv. Neural Inform. Processing Systems, vol. 35 (Curran Associates, Inc., Red Hook, NY), 6557–6574.Crossref, Google Scholar
• [35] Kelly M, Longjohn R, Nottingham K (2007) The UCI Machine Learning Repository. Accessed April 29, 2024, https://archive.ics.uci.edu.Google Scholar
• [36] Kong W, Monteiro RDC (2021) An accelerated inexact proximal point method for solving nonconvex-concave min-max problems. SIAM J. Optim. 31(4):2558–2585.Crossref, Google Scholar
• [37] Kong W, Monteiro RDC (2024) Global complexity bound of a proximal ADMM for linearly constrained nonseparable nonconvex composite programming. SIAM J. Optim. 34(1):201–224.Crossref, Google Scholar
• [38] Kovnatsky A, Glashoff K, Bronstein MM (2016) MADMM: A generic algorithm for non-smooth optimization on manifolds. Proc. Comput. Vision (Springer, Cham, Switzerland), 680–696.Crossref, Google Scholar
• [39] Lai R, Osher S (2014) A splitting method for orthogonality constrained problems. J. Sci. Comput. 58(1):431–449.Crossref, Google Scholar
• [40] Li J, Ma S, Srivastava T (2024) A Riemannian alternating direction method of multipliers. Math. Oper. Res. 50(4):3222–3242.Link, Google Scholar
• [41] Li X, Sun D, Toh KC (2016) A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Programming 155(1):333–373.Crossref, Google Scholar
• [42] Li X, Sun D, Toh KC (2019) A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications. Math. Programming 175(1):395–418.Crossref, Google Scholar
• [43] Li J, Zhu L, So AMC (2025) Nonsmooth nonconvex-nonconcave minimax optimization: Primal-dual balancing and iteration complexity analysis. Math. Programming 214(1):591–641.Crossref, Google Scholar
• [44] Li X, Chen S, Deng Z, Qu Q, Zhu Z, So AMC (2021) Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods. SIAM J. Optim. 31(3):1605–1634.Crossref, Google Scholar
• [45] Lin T, Jin C, Jordan MI (2020) Near-optimal algorithms for minimax optimization. Proc. Conf. Learn. Theory, vol. 125 (PMLR, New York), 2738–2779.Google Scholar
• [46] Lin T, Jin C, Jordan M (2020) On gradient descent ascent for nonconvex-concave minimax problems. Proc. Internat. Conf. Machine Learn. vol. 119 (PMLR, New York), 6083–6093.Google Scholar
• [47] Liu C, Boumal N (2020) Simple algorithms for optimization on Riemannian manifolds with constraints. Appl. Math. Optim. 82(3):949–981.Crossref, Google Scholar
• [48] Liu H, So AMC, Wu W (2019) Quadratic optimization with orthogonality constraint: Explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods. Math. Programming 178(1):215–262.Crossref, Google Scholar
• [49] Liu X, Xiao N, Yuan Y (2024) A penalty-free infeasible approach for a class of nonsmooth optimization problems over the Stiefel manifold. J. Sci. Comput. 99(2):30.Crossref, Google Scholar
• [50] Liu YF, Chang TH, Hong M, Wu Z, So AMC, Jorswieck EA, Yu W (2024) A survey of recent advances in optimization methods for wireless communications. IEEE J. Selected Areas Comm. 42(11):2992–3031.Crossref, Google Scholar
• [51] Lu C, Yan S, Lin Z (2016) Convex sparse spectral clustering: Single-view to multi-view. IEEE Trans. Image Processing 25(6):2833–2843.Crossref, Google Scholar
• [52] Lu C, Feng J, Lin Z, Yan S (2018) Nonconvex sparse spectral clustering by alternating direction method of multipliers and its convergence analysis. Proc. AAAI Conf. Artificial Intelligence, vol. 32 (AAAI Press, Palo Alto, CA).Google Scholar
• [53] Lu S, Tsaknakis I, Hong M, Chen Y (2020) Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications. IEEE Trans. Signal Processing 68:3676–3691.Crossref, Google Scholar
• [54] Nene SA, Nayar SK, Murase H (1996) Columbia object image library (COIL-100). Technical Report CUCS-006-96, http://www.cs.columbia.edu/CAVE/software/softlib/coil-100.php.Google Scholar
• [55] Nesterov Y (2018) Lectures on Convex Optimization, vol. 137 (Springer, Cham, Switzerland).Crossref, Google Scholar
• [56] Nouiehed M, Sanjabi M, Huang T, Lee JD, Razaviyayn M (2019) Solving a class of non-convex min-max games using iterative first order methods. Proc. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 14934–14942.Google Scholar
• [57] Ostrovskii DM, Lowy A, Razaviyayn M (2021) Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems. SIAM J. Optim. 31(4):2508–2538.Crossref, Google Scholar
• [58] Pan W, Shen J, Xu Z (2021) An efficient algorithm for nonconvex-linear minimax optimization problem and its application in solving weighted maximin dispersion problem. Comput. Optim. Appl. 78(1):287–306.Crossref, Google Scholar
• [59] Peng Z, Wu W, Hu J, Deng K (2023) Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact Riemannian submanifold embedded in Euclidean space. Appl. Math. Optim. 88(3):85.Crossref, Google Scholar
• [60] Rafique H, Liu M, Lin Q, Yang T (2022) Weakly-convex-concave min-max optimization: Provable algorithms and applications in machine learning. Optim. Methods Software 37(3):1087–1121.Crossref, Google Scholar
• [61] Rockafellar RT, Wets RJB (2009) Variational Analysis, vol. 317 (Springer Science & Business Media, Berlin, Germany).Google Scholar
• [62] Samadi S, Tantipongpipat U, Morgenstern JH, Singh M, Vempala S (2018) The price of fair PCA: One extra dimension. Proc. Adv. Neural Inform. Processing Systems, vol. 31 (Curran Associates, Inc., Red Hook, NY), 10999–11010.Google Scholar
• [63] Sato H, Iwai T (2014) Optimization algorithms on the Grassmann manifold with application to matrix eigenvalue problems. Japan J. Indust. Appl. Math. 31(2):355–400.Crossref, Google Scholar
• [64] Shen J, Wang Z, Xu Z (2023) Zeroth-order single-loop algorithms for nonconvex-linear minimax problems. J. Global Optim. 87(2):551–580.Crossref, Google Scholar
• [65] Shen J, Davis AJ, Lu D, Bai Z (2026) Fair principal component analysis via eigenvalue optimization. BIT Numer. Math. 66:17.Google Scholar
• [66] Strehl A, Ghosh J (2002) Cluster ensembles—A knowledge reuse framework for combining multiple partitions. J. Machine Learn. Res. 3:583–617.Google Scholar
• [67] Sun K, Sun XA (2024) Dual descent augmented Lagrangian method and alternating direction method of multipliers. SIAM J. Optim. 34(2):1679–1707.Crossref, Google Scholar
• [68] Thekumparampil KK, Jain P, Netrapalli P, Oh S (2019) Efficient algorithms for smooth minimax optimization. Proc. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 12659–12670.Google Scholar
• [69] Tian L, So AMC (2024) No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians. Math. Programming 208(1):51–74.Crossref, Google Scholar
• [70] Wang Z, Liu B, Chen S, Ma S, Xue L, Zhao H (2022) A manifold proximal linear method for sparse spectral clustering with application to single-cell RNA sequencing data analysis. INFORMS J. Optim. 4(2):200–214.Link, Google Scholar
• [71] Wen Z, Yin W (2013) A feasible method for optimization with orthogonality constraints. Math. Programming 142(1):397–434.Crossref, Google Scholar
• [72] Wu Z, Jiang B, Liu YF, Shao M, Dai YH (2024) Efficient CI-based one-bit precoding for multiuser downlink massive MIMO systems with PSK modulation. IEEE Trans. Wireless Comm. 23(5):4861–4875.Crossref, Google Scholar
• [73] Xiao N, Liu X, Yuan Y (2021) Exact penalty function for ℓ2,1 norm minimization over the Stiefel manifold. SIAM J. Optim. 31(4):3097–3126.Crossref, Google Scholar
• [74] Xu Z, Wang Z, Shen J, Dai Y (2024) Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems. SIAM J. Optim. 34(2):1879–1908.Crossref, Google Scholar
• [75] Xu Z, Zhang H, Xu Y, Lan G (2023) A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems. Math. Programming. 201(1):635–706.Crossref, Google Scholar
• [76] Xu M, Jiang B, Pu W, Liu YF, So AMC (2024) An efficient alternating Riemannian/projected gradient descent ascent algorithm for fair principal component analysis. Proc. IEEE Internat. Conf. Acoustics Speech Signal Processing (IEEE, Los Alamitos, CA), 7195–7199.Google Scholar
• [77] Yang J, Orvieto A, Lucchi A, He N (2022) Faster single-loop algorithms for minimax optimization without strong concavity. Proc. Internat. Conf. Artificial Intelligence Statist., vol. 151 (PMLR, New York), 5485–5517.Google Scholar
• [78] Yang J, Zhang S, Kiyavash N, He N (2020) A Catalyst framework for minimax optimization. Proc. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 5667–5678.Google Scholar
• [79] Zalcberg G, Wiesel A (2021) Fair principal component analysis and filter design. IEEE Trans. Signal Processing 69:4835–4842.Crossref, Google Scholar
• [80] Zhang C, Chen X, Ma S (2024) A Riemannian smoothing steepest descent method for non-Lipschitz optimization on embedded submanifolds of Rn. Math. Oper. Res. 49(3):1710–1733.Link, Google Scholar
• [81] Zhang P, Zhang J, Sra S (2023) Sion’s minimax theorem in geodesic metric spaces and a Riemannian extragradient algorithm. SIAM J. Optim. 33(4):2885–2908.Crossref, Google Scholar
• [82] Zhang J, Xiao P, Sun R, Luo Z (2020) A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems. Proc. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 7377–7389.Google Scholar
• [83] Zhou Y, Bao C, Ding C, Zhu J (2023) A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds. Math. Programming 201(1):1–61.Crossref, Google Scholar
• [84] Zou H, Xue L (2018) A selective overview of sparse principal component analysis. Proc. IEEE 106(8):1311–1320.Crossref, Google Scholar