Alecton Riemannian-Rescaled Stochastic Gradient Descent for Non-Convex Low-Rank Matrix Problems

For the quartic factorized objective f_tilde(Y) = tr(Y Y^T Y Y^T) - 2*tr(Y A_tilde Y^T) + ||A_tilde||_F^2, standard SGD with any iterate-independent step size alpha_k >= alpha * C^{-2k} (C > 1) diverges super-exponentially as x_k^2 > alpha^{-1} C^{2k} (C + 1) whenever initialized with x_0^2 >= alpha^{-1}(C + 1) (Proposition 1, Appendix A); in contrast, equipping the quotient manifold M = R^{n x p}/O_p with the Riemannian metric <U, V>_Y = tr(U (I + eta Y^T Y) V^T) yields the rescaled update Y_{k+1} = (I + eta A_tilde_k) Y_k (I + eta Y_k^T Y_k)^{-1}, which has the exact same column space C(Y_k) = C(Y_bar_k) at every step k as the unnormalized iteration Y_bar_{k+1} = (I + eta A_tilde_k) Y_bar_k (Section 2, Eq. 3-4, Algorithm 1).

Under the Alecton Variance Condition (Condition 1: E[y^T A_tilde^T W A_tilde y] <= sigma_a^2 tr(W) ||y||^2 and E[(y^T A_tilde y)^2] <= sigma_r^2 ||y||^4), Rank Condition (Condition 2: p = 1 or rank(A_tilde) = 1), and Step Size Condition (Condition 3: gamma = 2*n*sigma_a^2*p^2*(p + epsilon)*eta / (Delta*epsilon) <= 1 where Delta = lambda_q - lambda_{q+1}), the determinant ratio tau_k = |Y_k^T U Y_k| / |Y_k^T W Y_k| (with W = gamma*n^{-1}*p^{-2}*q*I + (1 - gamma*n^{-1}*p^{-2}*q)*U) satisfies the dominant mass submartingale drift E[tau_{k+1} | F_k] >= tau_k * (1 + eta*Delta*(1 - tau_k)) before stopping time T (Lemmas 6-12 and 15-16); applying Doob's optional stopping theorem (Theorem 2) to tau_k and the supermartingale psi_k = log(1 - tau_k) + (1/2)*eta*Delta*k proves that angular failure up to step t is bounded by P(F_t) <= Z_p(gamma) + (4*n*sigma_a^2*p^2*(p + epsilon) / (Delta^2*gamma*epsilon*t)) * log(n*p^2 / (gamma*q*epsilon)) with Z_1(gamma) = sqrt(2*pi*gamma)*exp(gamma/2)*erfc(sqrt(gamma/2)) <= sqrt(2*pi*gamma) and radial error P(||R_bar - Y_hat^T A Y_hat||_F^2 >= psi) <= p^2*sigma_r^2 / (L*psi), yielding global convergence in O(epsilon^{-1}*n*p^3*log n) steps (Theorem 1, Lemma 1, Lemmas 13-14) with a matching Omega(1/(K + 1)) rate lower bound (Theorem 3, Appendix E).

The Alecton Variance Condition holds for uniform entrywise matrix completion on mu-incoherent symmetric matrices with sigma_a^2 = mu^4*||A||_F^2 and sigma_r^2 = mu^4*tr(A)^2 (Lemma 2), rectangular entrywise sampling with M_{ij}^2 <= xi*m^{-1}*n^{-1}*||M||_F^2 giving sigma_a^2 = sigma_r^2 = 2*xi*||M||_F^2 (Lemma 3), isotropic unit-sphere trace sensing A_tilde = n^2 v v^T A w w^T for n > 50 giving sigma_a^2 = 16*||A||_F^2 and sigma_r^2 = 16*tr(A)^2 (Lemma 4, Lemmas 20-21), and m-entry subspace tracking on mu-incoherent rank-r projectors giving sigma_a^2 = sigma_r^2 = r^2*(1 + mu*r*m^{-1})^2 (Lemma 5, Lemma 22); moreover, when a linear measurement operator Omega satisfies 3p-RIP with constant delta, the factorized objective f(Y) = ||Omega(Y Y^T - A)||^2 has directional Hessian nabla_V^2 f(Y) >= 2*((1 - delta)*lambda_p - (3 + delta)*||Y Y^T - A||_F)*I (Theorem 4, Appendix G), establishing strong convexity in an O(1)-radius ball reached by Alecton.