A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints

Thank you for your efforts in evaluating our manuscript and providing encouraging feedback.

Question 1: In Figure 1, the objective function values of other methods seem unchanged. Could the authors explain the reason and elaborate more about the performance of other methods?

Response. This is because, while other methods often become trapped in poor local minima, OBCD successfully escapes these minima and generally achieves lower objective values. This observation aligns with our theory, which suggests that our methods converge to stronger stationary points.

Question 2: Besides, sharper notions of stationarity do not necessarily lead to lower objective function values. It can be better to present some average results based on multiple tests.

Response. Since OBCD is the first greedy descent method developed for this class of composite problems, we have demonstrated the clear advantages of the proposed approach. For simplicity, we have reported results from a single run, as we thought that multiple-run comparisons are not always necessary.

However, upon request, we will include average results based on multiple tests in the revised manuscript. Thank you for your thoughtful suggestions.

Question 3: Could the authors add some discussion on the possible parallel implementation of OBCD? Or explain possible difficulties of parallel implementation. Because this aspect would greatly strengthen the practical popularity of OBCD.

Response.

1. We have discussed the potential parallel implementation of OBCD, such as the Jacobi update strategy, as mentioned in Lines 108–109 of the paper.

2. Another possible avenue for parallel acceleration of the proposed method is the incorporation of variance reduction techniques to further decrease its oracle complexity.

Question 4: From Proposition 4.6, the KL holds locally. To apply the KL property, it is required that the iterates stay in the local region. However, the randomness in the algorithm can make the iterates fail to stay in the local region. Could the authors explain how to overcome this difficulty?

Response.

1. OBCD is a greedy descent algorithm. Specifically, when $X^t$ is sufficiently close to $\ddot{X}$, all subsequent solutions remain sufficiently close to $\ddot{X}$ as well.

2. We have added a strongly convex term $0.5 \alpha ||V-I||_F^2$ to the majorization function, as shown in Equation (9), to ensure that the iterates do not increase excessively.

Question 5: Could the authors revise the presentation and flow of this paper to make it more readable?

Response. We will make every effort to improve the presentation and logical flow of this paper in future revisions.

Question 6: Could the authors add some discussion on how this BCD framework can be generalized to other manifold?

Response.

1. The proposed method can be extended to the generalized Stiefel manifold (https://arxiv.org/abs/2405.01702), defined as $\Omega =\{X | X^TBX = I\}$. Assume that $X \in \Omega$. We denote $C = B^{1/2}$ and $D = B^{-1/2}$. It is straightforward to verify that the following update rule:

$X^+=X + D U_B (V-I) U_B^T CX$

ensures that the next iterate remains on the generalized Stiefel manifold, i.e., $X^+\in \Omega$.

2. The proposed method is also adaptable to other manifolds, such as the J-orthogonal manifold, the symplectic Stiefel manifold (https://arxiv.org/abs/2006.15226), and others, demonstrating its flexibility in addressing a broader class of constrained optimization problems.

Question 7: There are also other papers that tackle nonsmooth manifold opt using BCD (e.g., https://arxiv.org/pdf/2409.01770). Could the authors add some related references?

Response. As this paper is highly relevant to our work, we will include this reference in the updated version of our paper.

Thank you for your efforts in evaluating our manuscript.

Weakness 1: The authors write the update in an unusual form in eq. (4), this fact is, in my opinion, less apparent, than by using orthogonality of $V_B$.

Response: We present equivalent expressions using matrix multiplication and matrix addition. These two forms of expressing the update rule play a crucial role in our analysis, particularly the matrix addition rule in (4). This specific rule is indispensable for theoretical analysis and for performing the majorization-minimization procedure.

Weakness 2: Inaccuracies: Similarly, there is a discussion of using not only Givens rotations, stating the advantage of using Jacobi reflections since it will generate whole Stiefel manifold. This is also not entirely accurate I think. Givens rotations generate the whole SO(n) which is sufficient in solving PCA since there is an inherent ambiguity in the solution up to $\pm 1$ sign anyway.

Response:

1. For the PCA problem, there is no additional benefit since the objective function is symmetric (without a linear term).

2. However, for certain quadratic functions that include a linear term, consider the example in Line 1008: $\min_V ||V-A||_F^2, s.t. V\in St(2,2)$, where $A=[1, 0;-1, -1]$ is a reflection matrix. In this simple example, the reflection matrix plays a crucial role and leads to improved optimality, achieving a strictly lower objective value compared to using only a rotation matrix.

Other minor 1: Other minor typos/writing fixes Another difficulty I had was understanding the notation, for example: $[\cdot]_{BB}$ appearing for the first time in line 199, becomes slightly clear only later in line 224.

Response: We adopt the Matlab colon notation to denote indices that describe submatrices. See Line 726-727 in the paper. In our revision, we will explicitly mention this notation for clarity.

Other minor 2: Overall, I would also suggest to bring more focus on the computational advantages of the formulation.

Response:

1. OBCD operates on k rows of the solution matrix, offering lower computational complexity per iteration for $k\geq 2$.

2. OBCD is a greedy descent method with monotonicity for this problem class, offering provable convergence guarantees.

Other minor 3: The notation of M in line 187 should be Stiefel manifold I think.

Response: $M = St(n, r)$ denotes the Stiefel manifold. See Line37.

Questions 1: What is the impact of different strategies for choosing $B_k$?

Response:

1. When the subgradient provides a good estimate, the greedy strategy often results in faster convergence. Otherwise, random strategies are recommended.

2. Random strategies frequently achieve faster convergence compared to cyclic strategies.

3. The cyclic strategy has the advantage of being a deterministic approach.

Questions 2: How is the problem in (10) solved when Q is not diagonal?

1. When $h(\cdot)=0$ and $Q$ is not diagonal, Problem (10) can be solved to local optimality using gradient projection methods.

2. When $h(\cdot)\neq 0$ and $k=2$, Problem (10) can be addressed using one-dimensional search strategies, such as the break-point search method.

Questions 3: In the proof of the convergence Theorem 4.2, in line 1495, how come you can upper bound the inequality with the stationary point of the algorithm?

Note that $\ddot{X}$ is a limit point of the sequence $(X^0,X^1,X^2,X^3,\ldots,X^{\infty})$. The proposed algorithm is a descent method, and it is evident that $F(\ddot{X}) =F(\ddot{X}^{\infty}) \leq F(\ddot{X}^k)$ for all $k$.

We have extensively revised the manuscript based on the reviewers' suggestions, including improvements to both the writing and the technical content. We have made every effort to enhance its quality and sincerely hope the reviewers will take the time to review the updated version.

Thank you for your careful reading and the effort you put into evaluating our manuscript.

Weakness 1: The paper does not read very well. This is partly because of the style of the paper writing, which puts most of texts within proposition, lemma, remarks and there are not much narratives that connects them. There are numerous places that quantities are not properly defined. Important equations are written in line within text, which makes it extremely hard to read. Space constraints granted, there are still well-written, easy-to-read theoretical papers in top ML conferences. The current manuscript looks like it is a math paper crammed into 10 pages without much effort to make it readable.(1) In the very first paragraph, the authors state assumptions in text. This is extremely hard to read and almost impossible to refer back when reading further into the paper.

Response. We will present the small-sized subproblem in a formal mathematical formulation.

Weakness 2: Assumptions: In (2), the authors assume that the objective $f$ admits a quadratic surrogate of very specific form. This looks like some kind of restricted smoothness property but with the inner product depending on an additional kernel $H$. The authors should discuss if this is a reasonable assumption (e.g., if $f$ is $L$-smooth in the Euclidean or Riemannian sense, is it satisfied?) Otherwise, it is unclear if the paper's framework applies beyond a handful of objective functions (essentially $||X-B||_F^2$ plus some nonsmooth regularization terms) and this makes the paper's scope very narrow.

Response.

1. Inequality (2) can be interpreted as a generalized smoothness condition. By setting $H = L \cdot I$, it reduces to the classical $L$-smoothness condition.

2. To achieve greater generality, we adopt the notion of $H$-smoothness, which provides a tighter upper bound and can potentially lead to improved optimality. (Note that for a quadratic function, inequality (2) holds with equality.)

Weakness 3: Optimality measure: While the optimality measure based on the authors' notion of block-k stationary points is interesting, it is hard to assess how it compares with the usual optimality measure based on (sub)gradient norms or the ones that directly relaxes the variational inequality defining stationary points. Also, another complication is that this measure involves the chosen surrogate as part of the definition, so it is not clear that if one has small BS_k measure then one has small subgradient norm or other standard stationarity measure.

Response. We have demonstrated in Lines 315–316 that any block-2 stationary point must be a critical point, where its (sub)gradient norm is zero.

Weakness 4: Furthermore, the authors does not show asymptotically this proposed measure goes to zero. If this result is given, then using their hierarchy between optimality measures, one can deduce that any limit point of the algorithm is a BS_k-point, which is stationary point with additional potentially desirable properties.

Response. We have shown in Theorem 4.2 that the proposed measure converges to zero. Specifically, after $T$ iterations, OBCD identifies an $\epsilon$-$BS_k$-point (see Lines 1507–1509 and 1535–1536).

Weakness 5: Analysis assumes exact solver for the sub-problems: While in Remark 2.5 the authors claim that "For general k and h(·), the subproblem may not be solved globally, but a critical point can still be reached. Although strong optimality may be lost, a critical point (discussed later) for the final configuration X∞ remains achievable." This claim is never justified in the paper.

Response. Assume that $\bar{V}^t$ is a local critical stationary point of the subproblem $\min_{V\in St(k,k)} K(V;X^t,B)$ and that the solution $\bar{V}^t$ satisfies $K(\bar{V}^t;X^t,B)\leq K(I_k;X^t,B)$, where $I_k$ is an identity matrix. By employing similar strategies as those outlined in Theorem 4.2, we can readily establish the sufficient condition $F(X^{t+1})-F(X^t) \leq - 0.5 \alpha ||V^t - I_k||_F^2$ and confirm the validity of this conclusion.

Weakness 6: First, even with exact computation of sub-problems, they do not show that the iterates asymptotically converge to the stationary points.

Response. In Theorem 4.2, we have demonstrated that OBCD asymptotically converges to the Block-k stationary points, regardless of whether the coordinates are selected randomly or cyclically.

Weakness 7: Second, to support their claim, the authors extend their analysis for Thm. 4.2 with the first point here under the assumption that the sub-problems are inexactly solved. Justifying this is in fact is a non-trivial problem. See [1] for such a result for block inexact Riemannian coordinate descent. [1] Yuchen Li, Laura Balzano, Deanna Needell, Hanbaek Lyu, “Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms.” ICML 2024

Response. We assume that the objective function of the small-sized subproblem satisfies the descent property, expressed as $K(\bar{V}^t;X^t,B) \leq K(I_k;X^t,B)$. The suggested references will be cited in the updated manuscript.

Weakness 8: Analysis under KL: Thm. 4.8 states that essentially the iterates converge after a finite number of iterations under the additional KL assumption. The authors do not specify the the exponent $\sigma\in[0,1)$ in the desingularization function $\phi$. This cannot be true for all range of and it should only hold when $\sigma=0$. See Thm. 2.9 in [1]. [1] Xu, Yangyang, and Wotao Yin. "A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion." SIAM Journal on imaging sciences 6.3 (2013): 1758-1789.

Response. We note that our analysis establishes only the finite-length property of OBCD, which is independent of the KL exponent $\sigma$. In the future, we aim to extend this work by incorporating the convergence rate of OBCD through a deeper exploration of the KL exponent. Nonetheless, the finite-length property itself is a significant and state-of-the-art theoretical result.

Minor Comments 1: (1) Below (2), the norm on $H$: is it the spectral norm?

Response. The H-norm is not an operator norm; it is essentially a vector norm obtained by stacking the matrix into a vector.

Minor Comments 2: (2) L47: $||X||_p$ is not coordinate-wise separable.

Response. $||X\||_p$ is defined as $||X||_p= \sum_{i} \sum_j |X_{i,j}|_p$, where $p=0$ or $p=1$. Clearly, it can be decomposed into $n\times r$ components with $X\in R^{n\times r}$. Therefore, it is coordinate-wise separable.

Minor Comments 3: (3) L88: The authors imply that subgradient descent with dimihsing stepwise is a limitation. If the stepsizes diminish at a rate not too fast (e.g., $O^{-1/2}$), it still give an optimal iteration complexity. Please specify.

Response. Although it theoretically guarantees an optimal rate of $O^{-1/2}$, it may result in a conservative step size and slower convergence in practice.

Minor Comments 4: (4) The authors are recommended to cite the following references and discuss their relevance/differences. [1] Breloy, Kumar, Sun, and Palomar, "Majorization-Minimization on the Stiefel Manifold With Application to Robust Sparse PCA", IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 69, 2021 [2] Yuchen Li, Laura Balzano, Deanna Needell, Hanbaek Lyu, “Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms.” ICML 2024 [3] Yuchen Li, Laura Balzano, Deanna Needell, Hanbaek Lyu, “Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization” arXiv:2312.10330 (2023)

Response.

Generally speaking, none of the three references list above address Problem (1) when $h(X) \neq 0$. OBCD is the first greedy descent method with monotonicity for this class of nonsmooth composite problem.

Minor Comments 5: (5) Summary: The authors state that there are not much known results about block marjoziation-minimization or similar type of algorithms for nonconvex nonsmooth problems. This is simply not true. Please revise this assessment.

Response. We appreciate the reviewer for highlighting relevant references on block majorization-minimization algorithms. We will carefully review these works and include appropriate citations in the revised manuscript to provide a more comprehensive context.

Minor Comments 6: (6) In Lemma 2.1, the authors define $X^+$ and then specify $X$. They should first say "For any $X$, define $X^+=..$.."

Response. Thank you for your suggestion; we will make the necessary adjustments accordingly.

Minor Comments 7: (7) In Algorithm 1, $K$ is not defined nor referred.

Response. $K$ is defined in Equation (9) and referenced in the proof.

Minor Comments 8: (8) In eq. (6), remove comma.

Response. The comma in Equation (6) appears to be correctly placed.

Minor Comments 9: (9) The construction of quadratic surrogate in (9) resembles very much the discussion in Breloy et a. [1]. The authors should discuss the relation.

Response. We will include a citation to Breloy et al. [1] in the updated manuscript and discuss the relation in detail.

Minor Comments 10: (10) L215: The authors claim that the so-constructed quadratic surrogate can be exactly minimized over $St(k,k)$. But this is the case only if the nonsmooth part is zero (by SVD) or if $k=2$. This should be clearly stated.

Response. Please refer to the subsections "Solving the General OBCD Subproblems" and "Smallest Possible Subproblems When $k=2$" for a detailed explanation.

Minor Comments 11: (11) Table 1: The numbers are too small to read. There is no point of adding this kind of table since it is unreadable anyways.

Response. We will retain only some part of the table to ensure readability and clarity.

Minor Comments 12: (12) Appendix C.3: The authors compared computational complexity of computing the Riemannian gradient directly v.s. incrementally updating the gradient using their k-row approach.

Response. Yes, this comparison highlights the merits of coordinate descent, which is known for its reduced computational overhead and efficiency in handling large-scale problems.

The reviewers have provided a series of constructive and valuable comments that have greatly helped improve the quality of our paper, for which we are deeply grateful.

Below, we address the key points raised by the reviewers.

K1. Complexity of OBCD using the optimality measure of Riemannian subgradient.

Response. In the updated manuscript (see attached), we have established the ergodic convergence rates of OBCD using the optimality measure based on the Riemannian subgradient. See Theorem 4.6 in L368-370.

K2. The paper does not give a through literature review, especially on BCD/BMM on Riemannian manifolds

Response. In the updated manuscript (see attached), we have expanded the literature review to include discussions on BCD/BMM methods on Riemannian manifolds. See lines 92-98.

K4. the authors does not show asymptotically this proposed measure goes to zero

Response. We have established the non-ergodic/last-iterate convergence rate for OBCD in Theorem 4.11.

K5. The subproblem is solved approximately.

Response. We show that, as long as the proposed algorithm exhibits some descent property that $\mathcal{K}(\bar{V}^t;X^t,B) \leq \mathcal{K}(I_k;X^t,B)$, sufficient descent condition is still guaranteed (See Theorem 4(a)). Thus, convergence to a weaker optimality condition for the final solution $X^{\infty}$ is achievable. This condition can be achieved with reasonable initialization, and differs slightly from the condition of the approximate solution in Reference [1] mentioned by the reviewer.

K6. Other Important Writing Issues

1. "OBCD is the first greedy descent method with monotonicity for this class of nonsmooth composite problem". We have removed this sentence (Note that our small-sized subproblem can be solved exactly, while most existing methods can only solve it approximately).

2. "No existing BCD methods can address Problem (1) when $h(X)\neq 0$". We have removed this sentence.

3. We have added a pointer to the location where the notation $\mathcal{K}$ is defined.

4. We use $||X||sp$ to denote the spectral norm of the matrix $X$, and $||X||p=\sum_{i,j}|X_{i,j}|_p$ with $p=1$ or $p=0$.