Convergence results for projected line-search methods on varieties of low-rank matrices via \L{}ojasiewicz inequality

Reinhold Schneider; André Uschmajew

Source-linked AI summary

Convergence results for projected line-search methods on varieties of low-rank matrices via \L{}ojasiewicz inequality

Reinhold Schneider, André Uschmajew

arXiv:1402.5284v3Feb 21, 2014math.OCcs.LGcs.NAmath.NA

TL;DR

Optimization on the smooth rank-k manifold faces difficulties at its nonclosed boundary and unbounded curvature. This paper analyzes projected line-search methods on the closed rank-at-most-k variety using tangent-cone Lojasiewicz inequalities; for real-analytic costs, it establishes convergence and characterizes critical points as either rank k or zero-gradient.

Problem
The smooth rank-k manifold is nonclosed, and its manifold properties break down at lower-rank boundary points where curvature can become unbounded.
Source: §1 · pp. 2–3
Method
The paper proves convergence results for line-search methods on M≤k using Lojasiewicz inequalities for projected antigradients on tangent cones.
Source: §1 · p. 3, Contributions and outline · p. 4
Results
A critical point on M≤k either has rank k or satisfies ∇f(X*) = 0.
Source: §1 · p. 3
Takeaways & Limitations
Assuming a full-rank critical limit is justified because any rank-deficient critical point must have zero gradient.
Source: §1 · p. 3
The analysis is finite-dimensional, and the Lojasiewicz parameter θ remains unknown in the subsequent results.
Source: §2.2 · p. 7

Abstract

from arXiv · show

The aim of this paper is to derive convergence results for projected line-search methods on the real-algebraic variety $\mathcal{M}_{\le k}$ of real $m \times n$ matrices of rank at most $k$. Such methods extend Riemannian optimization methods, which are successfully used on the smooth manifold $\mathcal{M}_k$ of rank-$k$ matrices, to its closure by taking steps along gradient-related directions in the tangent cone, and afterwards projecting back to $\mathcal{M}_{\le k}$. Considering such a method circumvents the difficulties which arise from the nonclosedness and the unbounded curvature of $\mathcal{M}_k$. The pointwise convergence is obtained for real-analytic functions on the basis of a \L{}ojasiewicz inequality for the projection of the antigradient to the tangent cone. If the derived limit point lies on the smooth part of $\mathcal{M}_{\le k}$, i.e. in $\mathcal{M}_k$, this boils down to more or less known results, but with the benefit that asymptotic convergence rate estimates (for specific step-sizes) can be obtained without an a priori curvature bound, simply from the fact that the limit lies on a smooth manifold. At the same time, one can give a convincing justification for assuming critical points to lie in $\mathcal{M}_k$: if $X$ is a critical point of $f$ on $\mathcal{M}_{\le k}$, then either $X$ has rank $k$, or $\nabla f(X) = 0$.

1. Introduction.

The paper develops projected line-search methods on the closed variety of matrices of rank at most k, using tangent-cone projections to address difficulties at the boundary of the smooth rank-k manifold. For real-analytic costs, it establishes convergence results and shows that a critical point is either rank k or has zero gradient.

1. Introduction.

The closure M≤k avoids analyzing iterates solely on M_k, whose boundary contains lower-rank matrices and where curvature can become unbounded as the smallest singular value shrinks.On M_k, projection curvature scales like the inverse of the smallest singular value.Source: §1 · pp. 2–3
With a small-step safeguard, convergence rates can be estimated from the Lojasiewicz parameters, although a linear rate is established only when θ = 1/2.The value of θ cannot generally be checked in advance.Source: §1 · p. 3
A critical point on M≤k either has rank k or satisfies ∇f(X*) = 0.This makes a full-rank limit a natural condition for concluding critical-point convergence.Source: §1 · p. 3
The methods are not intended to detect or correct an overestimated target rank, so correct rank estimation remains a separate problem.Rank-increasing strategies are cited as an approach to that problem.Source: §1 · p. 4
For real-analytic costs, tangent-cone Lojasiewicz inequalities support convergence of line-search iterates on M≤k, with the limit a critical point when it lies on the smooth part.The method uses gradient-related directions in tangent cones and an Armijo-like backtracking rule.Source: §1 · p. 3, Contributions and outline · p. 4
The analysis is finite-dimensional, and hidden constants and provable rates may deteriorate with problem size.The paper notes that the Lojasiewicz inequality does not extend easily to infinite dimensions.Source: Contributions and outline · p. 4

2. Convergence of gradient methods via Lojasiewicz inequality.

The section formulates a minimization problem for a continuously differentiable, bounded-below function on a closed subset of its domain, assumed to have a solution.

The objective function f is continuously differentiable and bounded below.Source: §2 · p. 5
The minimization is posed over a closed subset M of the domain D.Source: §2 · p. 5
The problem is assumed to have a solution.Source: §2 · p. 5

2.1. Optimality condition.

The section introduces first-order optimality notions for constrained minimization, including tangent cones and projections of the antigradient. It uses criticality as the optimality condition for the paper’s convergence results.

The tangent cone at x is defined through limits of scaled displacements from points in M approaching x.Source: §2.1 · p. 5
A nearest point in a tangent cone is an orthogonal projection, but it may not be unique because the cone need not be convex.Source: §2.1 · p. 5
The norm of a projection of the antigradient onto the tangent cone is denoted g−(x), with best approximations attaining that norm.Source: §2.1 · p. 5
The paper uses its stated criticality condition as the first-order optimality condition.Source: §2.1 · p. 5
The projected-gradient norm is continuous on a differentiable manifold when the gradient is continuous, but is not generally continuous on M.Source: §2.1 · p. 5

2.2. Lojasiewicz inequality.

The section defines a Lojasiewicz inequality for the projected antigradient and establishes it locally for real-analytic objectives on sets admitting suitable real-analytic parametrizations. The inequality’s parameters, including θ, are generally unknown.

A projected-antigradient Lojasiewicz inequality requires positive δ and Λ and θ in (0, 1/2] around the point.Source: §2.2 · p. 6
For real-analytic f, the projected-antigradient inequality holds locally when M is locally the image of a real-analytic parametrization satisfying the stated neighborhood condition.Source: §2.2 · p. 6
The argument applies the classical inequality to f composed with the parametrization and uses the chain rule.Source: §2.2 · p. 6
The inequality’s actual θ and Λ may depend on the point and are typically unknown, so the value of θ remains unknown in the subsequent results.Source: §2.2 · pp. 6–7

2.3. General convergence theorem.

The general convergence theorem applies descent iterations under assumptions (A1)–(A2) when a cluster point satisfies the projected-antigradient Lojasiewicz inequality. With (A3), it also provides a convergence-rate estimate, though the constants may not be determined explicitly.

The theorem combines primary descent, stationarity, and an asymptotic small step-size safeguard with the Lojasiewicz inequality.Source: §2.3 · p. 7
Under (A1)–(A2), a cluster point satisfying (L) is the limit of the sequence; (A3) additionally yields a convergence-rate estimate.Source: §2.3 · p. 7
The projected-antigradient condition and assumptions (A1)–(A2) follow known convergence-result lines, with boundedness required for convergence of the sequence.Source: §2.3 · p. 7
Because (A3) is required only after an unknown index n0, the constants in the rate estimate cannot be determined explicitly.Source: §2.3 · p. 7
At singular points of M≤k, projected-antigradient norms tending to zero need not imply criticality, so the analysis later requires smoothness near the limit point.Source: §2.3 · p. 8

2.4. Retracted line-search methods.

Section 2.4 extends retracted line-search methods to closed sets through tangent-cone directions and retractions, then specifies gradient-related search and step-size conditions for convergence analysis.

2.4. Retracted line-search methods.

A retracted line-search step adds a scaled tangent vector to the current iterate and maps the result back to the manifold via a smooth retraction.Source: §2.4.1 · p. 8

2.4.1. Retractions.

For closed sets, a retraction maps tangent-cone steps back into the set; metric projection is a natural choice and is valid on M≤k.Source: §2.4.1 · pp. 8–9

2.4.2. Angle condition.

Search directions satisfy an ω-angle condition to remain gradient-related; Euclidean best approximation of the negative gradient attains ω=1 and vanishes exactly when the projected antigradient does.Source: §2.4.2 · p. 9

2.4.3. Armijo point.

Backtracking selects the largest tested step satisfying Armijo decrease; an Armijo point exists for descent directions under (A0), and smaller steps satisfy the same decrease.Source: §2.4.3 · pp. 9–10

2.4.4. Convergence results.

Under (A0), a cluster point satisfying the Łojasiewicz gradient inequality yields convergence; analytic bounded-below objectives and a smooth neighborhood of the limit support rate estimates with metric projection.Source: §2.4.4 · pp. 11, 13
Armijo is unnecessary for convergence under the stated decrease condition, but its choice matters when seeking (A3) and rate estimates.Source: §2.4.4 · p. 11

3. Results for matrix varieties of bounded rank.

This section extends projected, gradient-related line-search methods to matrices of rank at most k, accounting for tangent cones at singular points. It develops Łojasiewicz-based convergence guarantees for real-analytic cost functions, including methods with and without retraction.

3.1. Tangent cone and optimality.

The tangent cone at rank-s X consists of tangent-space directions on M_s plus directions in U⊥⊗V⊥ of rank at most k − s.This additional rank-bounded component describes directions available at rank-deficient points.Source: §3.1 · pp. 14–15
A critical point on M≤k either has rank k or has zero gradient; under strict convexity and coercivity, relative local minimizers have rank k when the unique ambient minimizer has rank at least k.Source: §3.1 · p. 16

3.2. Retraction by best low-rank approximation.

The best Frobenius-norm rank-at-most-k approximation is used as a retraction, and it satisfies the stated estimate with M = 1 + 2^-1/2.The approximation can be computed by singular value decomposition.Source: §3.2 · p. 17

3.3. Lojasiewicz inequality and convergence result.

For real-analytic, bounded-below f, Algorithm 3 converges to any cluster point, and at rank k that limit is critical with the stated rate estimates.The estimates apply when the limit has rank k.Source: §3.3 · pp. 18–19

3.4. A method without retraction.

Algorithm 4 also converges to any cluster point, with rate estimates even at singular limits; if the limit has rank k, it is critical.Its search directions are chosen so iterates remain feasible without retraction.Source: §3.4 · pp. 19–20
Although Algorithm 4 avoids retractions and saves some backtracking cost, retractions are expected to be cheaper than function evaluations or gradient projections, potentially offsetting that saving.Source: §3.4 · p. 20
On rank-k completion instances, Algorithm 4 was inferior to Algorithm 3 in iteration count and computation time, including for k = 80.Figure 3.1 reports tests with A ∈ R2000×2000 and rank(A) = k.Source: Figure 3.1 · p. 21, §3.4 · p. 21
When the target matrix had rank k/2, Algorithm 4 performed better, but neither method found a good approximation and the kth singular value was practically never below 10^-4.The authors note that the approach does not contribute to rank estimation.Source: §3.4 · p. 21, Figure 3.2 · p. 22
The results extend Łojasiewicz-based convergence analysis to gradient-related line-search methods on matrices of rank at most k, including tangent cones at singular points.The setting is the real-algebraic variety M≤k of real m × n matrices.Source: §4 · p. 22
Accounting for singular-point tangent cones addresses convergence-analysis difficulties caused by nonclosedness and unbounded curvature on the smooth rank-k manifold.Source: §4 · p. 22
The convergence results are currently applicable to real-analytic cost functions.Source: §4 · p. 22

4. Conclusion.

The closing material identifies bounded-rank tensor varieties as a likely extension and completes the convergence proof with estimates on the sequence's tail.

4. Conclusion.

The results may extend to tensor varieties with bounded Tucker, hierarchical Tucker, or tensor train ranks, which are intersections of low-rank matrix varieties.The paper identifies this as an important direction for future work.Source: §4 · p. 22
The convergence argument shows that an accumulation point is the sequence's limit.The proof uses the displayed induction argument and assumption (A3).Source: Acknowledgments · p. 23
When θ = 1/2, the proof obtains ν ∈ (0, 1).Source: Acknowledgments · p. 23
For 0 < θ < 1/2, induction establishes r_n ≤ s_n, completing the proof's tail estimate.The proof first defines p and a comparison sequence, then uses induction.Source: Acknowledgments · p. 23