An adaptive regularized proximal Newton-type methods for composite optimization over the Stiefel manifold

Qinsi Wang, Wei Hong YangComput. Optim. Appl 2024 · DOI

TL;DR

This paper introduces two novel algorithms, ARPQN and ARPN, for a specific type of optimization problem on the Stiefel manifold. These methods aim to efficiently solve problems involving both smooth and non-smooth functions, a common challenge in areas like compressed sensing and principal component analysis. The proposed algorithms demonstrate strong theoretical convergence properties and promising performance in numerical experiments.

What Problem Does This Paper Address?

Many real-world problems involve optimizing a function that is a sum of two parts: one that is "smooth" (meaning its rate of change is well-behaved) and another that is "non-smooth" (like absolute values or indicator functions, which can have sharp corners or jumps). This is particularly true when the optimization is constrained to a specific mathematical structure, such as the Stiefel manifold. The Stiefel manifold is a set of matrices with orthonormal columns, frequently encountered in areas like dimensionality reduction, signal processing, and machine learning.

Existing methods for such problems on manifolds often struggle with efficiency or theoretical guarantees. This paper addresses the challenge of developing robust and efficient algorithms for composite optimization problems specifically on the Stiefel manifold. The goal is to find solutions that are not only accurate but also computationally feasible, especially for large-scale problems.

Methods

The paper proposes two main algorithms: ARPQN (Adaptive Regularized Proximal Quasi-Newton) and ARPN (Adaptive Regularized Proximal Newton). Both are built upon the foundation of Newton-type methods, which are known for their fast convergence but can be computationally expensive.

The key innovations include:

  • Adaptive Regularization: Both algorithms incorporate an adaptive regularization term. This term is dynamically adjusted during the optimization process to ensure that the subproblems (smaller, simpler optimization tasks solved at each step) are well-behaved and can be solved efficiently. This is crucial for handling the non-smooth part of the objective function.
  • Proximal Operators: The methods utilize proximal operators, which are standard tools for dealing with non-smooth functions in optimization.
  • Quasi-Newton and Newton Updates: ARPQN uses a quasi-Newton approach to approximate the Hessian (second derivative) of the smooth part of the function, while ARPN uses a more direct Newton approach (approximating the Hessian with the actual Hessian or a related matrix).
  • Manifold Constraints: The algorithms are specifically designed to handle the constraints of the Stiefel manifold, employing techniques like retractions to stay within the manifold during the optimization steps.

Datasets

The paper evaluates the proposed algorithms on two types of problems:

  • Compressed Modes (CM) problems: These problems arise in areas like signal processing and are used to find spatially localized sparse solutions.
  • Sparse Principal Component Analysis (Sparse PCA) problems: This is a statistical technique used for dimensionality reduction where the resulting components are sparse.

The authors generated random instances for these problems with varying dimensions and parameters to test the algorithms' performance.

Key Insights and Ideas

  • Adaptive Regularization is Key: The adaptive regularization strategy is shown to be crucial for both accelerating convergence and improving the robustness of the algorithms, especially when dealing with non-smooth functions on manifolds. It helps to manage the ill-conditioning that can arise from the non-smooth components.
  • NLS-ARPQN Outperforms ARPQN: The nonmonotone line search version of ARPQN (NLS-ARPQN) consistently shows better performance in terms of iteration count and CPU time compared to the standard ARPQN. This highlights the benefit of flexible line search strategies.
  • Retraction Choice Matters: For NLS-ARPQN, the choice of retraction method (how the algorithm stays on the Stiefel manifold) significantly impacts performance. The SVD-based retraction generally yields the best results.
  • Practical Efficiency: While ARPN offers theoretical advantages (superlinear convergence), its computational cost for solving subproblems makes ARPQN (and its NLS variant) more practical for large-scale applications.

Key Results

  • Global Convergence: Both ARPQN and ARPN are proven to converge globally to a stationary point under mild assumptions.
  • Local Convergence: ARPQN is shown to achieve local linear convergence, while ARPN can achieve local superlinear convergence under certain conditions.
  • Numerical Performance: In experiments on CM and Sparse PCA problems, NLS-ARPQN consistently outperformed other compared methods (ManPG, ManPG-Ada, ALMSSN, ManPQN) in terms of iteration number and CPU time, especially for larger problem dimensions. For instance, NLS-ARPQN often required fewer iterations and less time to converge.
  • Parameter Sensitivity: The performance of NLS-ARPQN was found to be relatively insensitive to the choice of its parameters, suggesting robustness.

Limitations and Future Work

  • ARPN's Computational Cost: The authors acknowledge that ARPN's subproblem solving is computationally expensive, limiting its direct applicability to very large-scale problems. They suggest exploring first-order methods for solving these subproblems as a future direction.
  • Generalization to Other Manifolds: The current work focuses on the Stiefel manifold. The authors propose extending ARPQN and ARPN to more general Riemannian manifolds as a future research avenue.
  • Further Investigation of ARPN: While ARPN offers theoretical superlinear convergence, its practical implementation and comparison with ARPQN on a wider range of problems would be valuable.

Summary updated

BibTeX
@article{wang2024adaptive,
  author = {Qinsi Wang and Wei Hong Yang},
  title = {{An adaptive regularized proximal Newton-type methods for composite optimization over the Stiefel manifold}},
  journal = {Comput. Optim. Appl.},
  year = {2024},
  doi = {10.1007/s10589-024-00595-3},
}
Figure