×

Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis. (English) Zbl 1469.90165

In this paper, a block optimization problem is studied, in which some constraint sets are \(C^{\infty}\) Riemannian submanifolds embedded in Euclidean spaces. After obtaining a necessary optimality condition for the specific problem under investigation, the notion of an \(\varepsilon\)-stationary solution of the problem is defined. Then, a proximal gradient-based ADMM (Alternating Direction Method of Multipliers) algorithm is proposed. It is shown that the algorithm provides an \(\varepsilon\)-stationary solution. An upper bound of the number of necessary iterates is established.
For the case where computing the proximal mapping is difficult, a linearized proximal gradient-based ADMM algorithm is also provided, with similar results, another algorithm is suitable for a stochastic version of the problem. Also, a feasible curvilinear line-search variant of ADMM is provided. The paper is complemented by several applications and numerical results.

MSC:

90C60 Abstract computational complexity for mathematical programming problems
90C30 Nonlinear programming
90C90 Applications of mathematical programming
90C48 Programming in abstract spaces

Software:

BiqMac; Biq Mac; MADMM; PDCO; CVX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Absil, P.A., Baker, C.G., Gallivan, K.A.: Convergence analysis of Riemannian trust-region methods. Technical report (2006) · Zbl 1155.65325
[2] Absil, PA; Baker, CG; Gallivan, KA, Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7, 3, 303-330 (2007) · Zbl 1129.65045
[3] Absil, PA; Mahony, R.; Sepulchre, R., Optimization Algorithms on Matrix Manifolds (2009), Princeton: Princeton University Press, Princeton
[4] Absil, PA; Malick, J., Projection-like retractions on matrix manifolds, SIAM J. Optim., 22, 1, 135-158 (2012) · Zbl 1248.49055
[5] Ballani, J.; Grasedyck, L.; Kluge, M., Black box approximation of tensors in hierarchical Tucker format, Linear Algebra Appl., 438, 2, 639-657 (2013) · Zbl 1260.65037
[6] Bento, G.C., Ferreira, O.P., Melo, J.G.: Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds. https://arxiv.org/pdf/1609.04869.pdf (2016) · Zbl 1400.90277
[7] Bergmann, R.; Persch, J.; Steidl, G., A parallel Douglas-Rachford algorithm for minimizing ROF-like functionals on images with values in symmetric Hadamard manifolds, SIAM J. Imaging Sci., 9, 3, 901-937 (2016) · Zbl 1346.65006
[8] Boumal, N.; Absil, PA; Cartis, C., Global rates of convergence for nonconvex optimization on manifolds, IMA J. Numer. Anal., 39, 1, 1-33 (2018) · Zbl 1483.65092
[9] Candès, EJ; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM, 58, 3, 11 (2011) · Zbl 1327.62369
[10] Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010
[11] Chen, Y., Li, X., Xu, J.: Convexified modularity maximization for degree-corrected stochastic block models. arXiv preprint arXiv:1512.08425 (2015) · Zbl 1410.62105
[12] Clarke, FH, Nonsmooth analysis and optimization, Proc. Int. Congr. Math., 5, 847-853 (1983) · Zbl 0425.90081
[13] De Lathauwer, L.; De Moor, B.; Vandewalle, J., A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21, 4, 1253-1278 (2000) · Zbl 0962.15005
[14] Dhillon, I.S., Sra, S.: Generalized nonnegative matrix approximations with Bregman divergences. In: NIPS, vol. 18 (2005)
[15] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[16] Edelman, A.; Arias, TA; Smith, S., The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20, 2, 303-353 (1998) · Zbl 0928.65050
[17] Ferreira, OP; Oliveira, PR, Proximal point algorithm on Riemannian manifolds, Optimization, 51, 2, 257-270 (2002) · Zbl 1013.49024
[18] Frieze, A.; Jerrum, M., Improved approximation algorithms for MAX k-CUT and MAX bisection, Algorithmica, 18, 1, 67-81 (1997) · Zbl 0873.68078
[19] Fu, WJ, Penalized regressions: the bridge versus the lasso, J. Comput. Graph. Stat., 7, 3, 397-416 (1998)
[20] Ghadimi, S.; Lan, G., Stochastic first-and zeroth-order methods for nonconvex stochastic programming, SIAM J. Optim., 23, 4, 2341-2368 (2013) · Zbl 1295.90026
[21] Ghadimi, S.; Lan, G., Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program., 156, 1-2, 59-99 (2016) · Zbl 1335.62121
[22] Ghadimi, S.; Lan, G.; Zhang, H., Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization, Math. Program., 155, 1-2, 267-305 (2016) · Zbl 1332.90196
[23] Ghosh, S., Lam, H.: Computing worst-case input models in stochastic simulation. arXiv preprint arXiv:1507.05609 (2015)
[24] Ghosh, S., Lam, H.: Mirror descent stochastic approximation for computing worst-case stochastic input models. In: Winter Simulation Conference, 2015, pp. 425-436. IEEE (2015)
[25] Grant, M., Boyd, S., Ye, Y.: CVX: MATLAB software for disciplined convex programming (2008)
[26] Hong, M.: Decomposing linearly constrained nonconvex problems by a proximal primal dual approach: algorithms, convergence, and applications. arXiv preprint arXiv:1604.00543 (2016)
[27] Hong, M.; Luo, Z-Q; Razaviyayn, M., Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 26, 1, 337-364 (2016) · Zbl 1356.49061
[28] Hosseini, S.; Pouryayevali, MR, Generalized gradients and characterization of epi-Lipschitz sets in Riemannian manifolds, Fuel Energy Abstr., 74, 12, 3884-3895 (2011) · Zbl 1225.49046
[29] Huper, K., Trumpf, J.: Newton-like methods for numerical optimization on manifolds. In: Signals, Systems and Computers, 2004. Conference Record of the Thirty-Eighth Asilomar Conference, vol. 1, pp. 136-139. IEEE (2004)
[30] Jain, P., Netrapalli, P., Sanghavi, S.: Low-rank matrix completion using alternating minimization. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 665-674. ACM (2013) · Zbl 1293.65073
[31] Jiang, B.; Lin, T.; Ma, S.; Zhang, S., Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis, Comput. Optim. Appl., 72, 1, 115-157 (2019) · Zbl 1411.90274
[32] Jiang, B., Ma, S., So, A.M.-C., Zhang, S.: Vector transport-free SVRG with general retraction for Riemannian optimization: complexity analysis and practical implementation. Preprint arXiv:1705.09059 (2017)
[33] Jin, J., Fast community detection by score, Ann. Stat., 43, 1, 57-89 (2015) · Zbl 1310.62076
[34] Kasai, H., Sato, H., Mishra, B.: Riemannian stochastic variance reduced gradient on Grassmann manifold. arXiv preprint arXiv:1605.07367 (2016)
[35] Kolda, TG; Bader, BW, Tensor decompositions and applications, SIAM Rev., 51, 3, 455-500 (2009) · Zbl 1173.65029
[36] Kovnatsky, A., Glashoff, K., Bronstein, M.: MADMM: a generic algorithm for non-smooth optimization on manifolds. In: European Conference on Computer Vision, pp. 680-696. Springer (2016)
[37] Lai, R.; Osher, S., A splitting method for orthogonality constrained problems, J. Sci. Comput., 58, 2, 431-449 (2014) · Zbl 1296.65087
[38] Lai, Z.; Xu, Y.; Chen, Q.; Yang, J.; Zhang, D., Multilinear sparse principal component analysis, IEEE Trans. Neural Netw. Learn. Syst., 25, 10, 1942-1950 (2014)
[39] Lee, H.; Battle, A.; Raina, R.; Ng, AY, Efficient sparse coding algorithms, Adv. Neural Inf. Process. Syst., 19, 801 (2007)
[40] Lee, JM, Introduction to Smooth Manifolds (2013), New York: Springer, New York · Zbl 1258.53002
[41] Li, G.; Pong, TK, Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim., 25, 4, 2434-2460 (2015) · Zbl 1330.90087
[42] Liu, H., Wu, W., So, A.M.-C.: Quadratic optimization with orthogonality constraints: explicit Lojasiewicz exponent and linear convergence of line-search methods. In: ICML, pp. 1158-1167 (2016)
[43] Lu, H.; Plataniotis, KN; Venetsanopoulos, AN, MPCA: multilinear principal component analysis of tensor objects, IEEE Trans. Neural Netw., 19, 1, 18-39 (2008)
[44] Luenberger, DG, The gradient projection method along geodesics, Manag. Sci., 18, 11, 620-631 (1972) · Zbl 0253.90050
[45] Motreanu, D.; Pavel, NH, Quasi-tangent vectors in flow-invariance and optimization problems on Banach manifolds, J. Math. Anal. Appl., 88, 1, 116-132 (1982) · Zbl 0504.58037
[46] Nemirovski, A., Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Math. Program., 109, 2, 283-317 (2007) · Zbl 1156.90012
[47] Nocedal, J., Wright, S.J.: Numerical Optimization, vol. 9, no. 4, p. 1556. Springer · Zbl 0930.65067
[48] Oseledets, IV, Tensor-train decomposition, SIAM J. Sci. Comput., 33, 5, 2295-2317 (2011) · Zbl 1232.15018
[49] Oseledets, IV; Tyrtyshnikov, E., TT-cross approximation for multidimensional arrays, Linear Algebra Appl., 432, 1, 70-88 (2010) · Zbl 1183.65040
[50] Panagakis, Y.; Kotropoulos, C.; Arce, GR, Non-negative multilinear principal component analysis of auditory temporal modulations for music genre classification, IEEE Trans. Audio Speech Lang. Process., 18, 3, 576-588 (2010)
[51] Reddi, S.J., Sra, S., Poczos, B., Smola, A.J.: Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. In: Advances in Neural Information Processing Systems, pp. 1145-1153 (2016)
[52] Rockafellar, RT, Clarke’s tangent cones and the boundaries of closed sets in \(\mathbb{R}^n\), Nonlinear Anal. Theory Methods Appl., 3, 145-154 (1979) · Zbl 0443.26010
[53] Smith, ST, Optimization techniques on Riemannian manifolds, Fields Inst. Commun., 3, 3, 113-135 (1994) · Zbl 0816.49032
[54] Srebro, N., Jaakkola, T.: Weighted low-rank approximations. In: ICML, vol. 3, pp. 720-727 (2003)
[55] Sun, J.; Qu, Q.; Wright, J., Complete dictionary recovery over the sphere II: recovery by Riemannian trust-region method, IEEE Trans. Inf. Theory, 63, 2, 885-914 (2017) · Zbl 1364.94165
[56] Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B, 58, 267-288 (1996) · Zbl 0850.62538
[57] Wang, F., Cao, W., Xu, Z.: Convergence of multi-block Bregman ADMM for nonconvex composite problems. arXiv preprint arXiv:1505.03063 (2015)
[58] Wang, S., Sun, M., Chen, Y., Pang, E., Zhou, C.: STPCA: sparse tensor principal component analysis for feature extraction. In: 21st International Conference on Pattern Recognition, 2012, pp. 2278-2281. IEEE (2012)
[59] Wang, Y.; Yin, W.; Zeng, J., Global convergence of ADMM in nonconvex nonsmooth optimization, J. Sci. Comput., 78, 1, 29-63 (2019) · Zbl 1462.65072
[60] Wen, Z.; Yin, W., A feasible method for optimization with orthogonality constraints, Math. Program., 142, 1-2, 397-434 (2013) · Zbl 1281.49030
[61] Wiegele, A.: Biq Mac library—a collection of max-cut and quadratic 0-1 programming instances of medium size. Preprint (2007)
[62] Xu, Y., Alternating proximal gradient method for sparse nonnegative Tucker decomposition, Math. Program. Comput., 7, 1, 39-70 (2015) · Zbl 1320.49019
[63] Yang, L.; Pong, TK; Chen, X., Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction, SIAM J. Imaging Sci., 10, 1, 74-110 (2017) · Zbl 1364.90278
[64] Yang, WH; Zhang, L-H; Song, R., Optimality conditions for the nonlinear programming problems on Riemannian manifolds, Pac. J. Optim., 10, 2, 415-434 (2014) · Zbl 1322.90096
[65] Ye, Y., A. 699-approximation algorithm for max-bisection, Math. Program., 90, 1, 101-111 (2001) · Zbl 1059.90119
[66] Zhang, H., Reddi, S.J., Sra, S.: Riemannian SVRG: fast stochastic optimization on Riemannian manifolds. In: Advances in Neural Information Processing Systems, pp. 4592-4600 (2016)
[67] Zhang, H., Sra, S.: First-order methods for geodesically convex optimization. arXiv preprint arXiv:1602.06053 (2016)
[68] Zhang, J.; Liu, H.; Wen, Z.; Zhang, S., A sparse completely positive relaxation of the modularity maximization for community detection, SIAM J. Sci. Comput., 40, 5, A3091-A3120 (2018) · Zbl 1405.90082
[69] Zhang, T.; Golub, GH, Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl., 23, 2, 534-550 (2001) · Zbl 1001.65036
[70] Zhang, Y., Levina, E., Zhu, J.: Detecting overlapping communities in networks using spectral methods. arXiv preprint arXiv:1412.3432 (2014)
[71] Zhu, H.; Zhang, X.; Chu, D.; Liao, L., Nonconvex and nonsmooth optimization with generalized orthogonality constraints: an approximate augmented Lagrangian method, J. Sci. Comput., 72, 1, 331-372 (2017) · Zbl 1373.65043
[72] Zou, H.; Hastie, T., Regularization and variable selection via the elastic net, J. R. Stat. Soc. B, 67, 2, 301-320 (2005) · Zbl 1069.62054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.