Finite-budget regularized gradient on a Stiefel constraint

For integers $1\le p\le n$, define the real Stiefel constraint set

$\mathrm{St}(n,p):=\{X\in {\mathbb{R}}^{n\times p}:X^{\mathsf{T}}X=I_p\}\mathrm{.}$

Equip ${\mathbb{R}}^{n\times p}$ with the Frobenius inner product $⟨U,V{⟩}_F=\mathrm{tr}(U^{\mathsf{T}}V)$ and norm $\mathrm{\parallel }U{\mathrm{\parallel }}_F=\sqrt{⟨U,U{⟩}_F}$. Let $H={\mathbb{R}}^{n\times p}$, let $Y$ be a real Hilbert space, let $U\subseteq H$ be open and contain $\mathrm{St}(n,p)$, and let $F:U\to Y$ be continuously Fréchet differentiable. Given data $y\in Y$, a reference matrix $X_{\mathrm{r}\mathrm{e}\mathrm{f}}\in H$, and $\lambda \ge 0$, define the residual and regularized objective by

$r(X):=\mathrm{\parallel }F(X)-y{\mathrm{\parallel }}_Y,\mathrm{\Phi }(X):=\frac{1}{2}\mathrm{\parallel }F(X)-y{\mathrm{\parallel }}_Y^2+\frac{\lambda }{2}\mathrm{\parallel }X-X_{\mathrm{r}\mathrm{e}\mathrm{f}}{\mathrm{\parallel }}_F^2\mathrm{.}$

Supply an ambient gradient oracle $G:U\to H$ satisfying $D\mathrm{\Phi }(X)[Z]=⟨G(X),Z{⟩}_F$ for every $X\in U$ and $Z\in H$, an initial frame $X_0\in \mathrm{St}(n,p)$, a residual tolerance $\tau \ge 0$, a finite integer budget $K\ge 0$, and a step schedule ${\alpha }_0,\dots ,{\alpha }_{K-1}$ with every ${\alpha }_k>0$. For a square matrix $M$, put $\mathrm{sym}(M):=(M+M^{\mathsf{T}})\mathrm{/}2$. The tangent-projection and metric-dual calculation for this $C^1$ objective, well-definedness of every tangent polar call, and finite-budget feasibility are justified by the finite-budget return and feasibility lemma. No smoothness beyond $C^1$ is required. The procedure is:

1. Set the current frame to $X_0$ and the schedule index to $k=0$. If $r(X)\le \tau$, return $(X,r(X),\mathtt{\text{target-met}})$.

2. While $k<K$, compute $G(X)$ and the Stiefel gradient $g:=G(X)-X\mathrm{sym}(X^{\mathsf{T}}G(X))$. If $g=0$, return $(X,r(X),\mathtt{\text{stationary}})$.

3. Set $\eta :=-{\alpha }_{k}g$ and form the polar-retracted candidate

   $X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}}:=(X+\eta )((X+\eta {)}^{\mathsf{T}}(X+\eta ){)}^{-1\mathrm{/}2}\mathrm{.}$

4. Evaluate $\mathrm{\Phi }(X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}})$ and $r(X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}})$. If $\mathrm{\Phi }(X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}})>\mathrm{\Phi }(X)$, return $(X,r(X),\mathtt{\text{objective-rejected}})$. Otherwise accept $X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}}$ as the current frame. If its residual is at most $\tau$, return $(X,r(X),\mathtt{\text{target-met}})$; otherwise increment $k$ by one and repeat the loop.

5. When $k=K$, return $(X,r(X),\mathtt{\text{budget-exhausted}})$.

This procedure is restricted to the stated finite-dimensional real Stiefel constraint and the displayed polar retraction. It gives no convergence, global-optimality, or noisy-data stability guarantee, and it makes no finite-precision claim. It does not apply to positivity constraints or other nonlinear manifolds without a separately specified compatible retraction and proof.

Finite-budget return, tangent metric-dual formula, and feasibility ↗

Nonlinear forward maps on real Hilbert spaces

Real Stiefel and Grassmann metric conventions

Stiefel tangent space and orthogonal projection

Polar retraction formula and domain

The polar map is a Stiefel retraction

Absil, Mahony, and Sepulchre, Optimization Algorithms on Matrix Manifolds, Chapter 3, Example 3.6.2

Absil, Mahony, and Sepulchre, Optimization Algorithms on Matrix Manifolds, Chapter 4, Example 4.1.3

Nicolas Boumal, An Introduction to Optimization on Smooth Manifolds, §§3.8 and 7.3