Text

Weakly Convex Optimization Over Stiefel Manifold Using Riemannian Subgradient-Type Methods

We consider a class of nonsmooth optimization problems over the Stiefel manifold, in which the objective function is weakly convex in the ambient Euclidean space. Such problems are ubiquitous in engineering applications but still largely unexplored. We present a family of Riemannian subgradient-type methods---namely Riemannian subgradient, incremental subgradient, and stochastic subgradient methods---to solve these problems and show that they all have an iteration complexity of O(ε−4) for driving a natural stationarity measure below ε. In addition, we establish the local linear convergence of the Riemannian subgradient and incremental subgradient methods when the problem at hand further satisfies a sharpness property and the algorithms are properly initialized and use geometrically diminishing stepsizes. To the best of our knowledge, these are the first convergence guarantees for using Riemannian subgradient-type methods to optimize a class of nonconvex nonsmooth functions over the Stiefel manifold. The fundamental ingredient in the proof of the aforementioned convergence results is a new Riemannian subgradient inequality for restrictions of weakly convex functions on the Stiefel manifold, which could be of independent interest. We also show that our convergence results can be extended to handle a class of compact embedded submanifolds of the Euclidean space. Finally, we discuss the sharpness properties of various formulations of the robust subspace recovery and orthogonal dictionary learning problems and demonstrate the convergence performance of the algorithms on both problems via numerical simulations.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.31 No.3 July-September 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1605-1634

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

DICTIONARY LEARNING
NONCONVEX OPTIMIZATION
ITERATION COMPLEXITY
LINEAR CONVERGENCE
MANIFOLD OPTIMIZATION
ORTHOGONALITY CONSTRAINT
ROBUST SUBSPACE RECOVERY

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Xiao Li, Shixiang Chen, Zengde Deng, Qing Qu, Zhihui Zhu, Anthony Man-Cho So

Versi lain/terkait

Lampiran Berkas

Komentar