PaperlayerView exact revision on arXiv

Source-linked AI summary

Retraction-Based Gradient Projection Algorithms on Manifolds

Conglong Xu, Hao Wu

arXiv:2609.30885v1math.OCcs.LG

TL;DR

Gradient projection methods on manifolds have had limited relevance to convex optimization, while geodesic convexity provides one existing framework. This paper introduces retraction-specific convex sets and manifold gradient projection algorithms, establishing stationary-limit convergence guarantees under several stepsize rules and applying the framework to weighted low-rank approximation.

  • Problem

    Prior manifold gradient-projection attempts were scarce and concerned tangent-space projection rather than convex optimization, while geodesic convexity is the existing framework the paper seeks to generalize.

    Source: §1 · p. 1

  • Method

    The paper defines retraction-specific convex sets through tangent-space bundles and develops retraction-based gradient projection algorithms with multiple stepsize rules.

    Source: §1 · p. 1

  • Results

    Every limit point is stationary under Stepsize Rules 3.1–3.3, and also under Rule 3.4 when the gradient is R-Lipschitz over the feasible set and 0 < s < 2L.

    Source: §3.4 · p. 4

  • Takeaways & Limitations

    The framework is applied to weighted low-rank approximation, with convergence numerically validated on image completion.

    Source: §1 · p. 1, §5 · p. 6

    The numerical results are not intended as a comprehensive comparison with other Riemannian optimization algorithms on image completion.

    Source: §4.2 · p. 6

Abstract

from arXiv · show

We introduce a framework for retraction-based convex optimization on Riemannian manifolds, which includes a notion of retraction-specific convex sets and retraction-based gradient projection algorithms. The standard theory of gradient projection algorithms generalizes easily to this framework. Within this framework, we establish convergence results for retraction-based gradient projection algorithms with various stepsize rules. As an application, we use our framework to study the weighted low-rank approximation. We also provide numerical validation of our convergence results on the image completion task.

1 Introduction

The paper extends gradient projection theory to Riemannian manifolds through retraction-specific convex sets, offering a framework broader than geodesic convexity. It applies the algorithms to weighted low-rank approximation and validates convergence on image completion.

Related Work and Our Contributions

  • The framework extends Euclidean gradient projection theory to Riemannian manifolds, drawing on classical projection and feasible-direction methods.The paper adapts Armijo sufficient-decrease and feasible-direction convergence ideas for backtracking line searches.Source: §1 · p. 1
  • Retraction-specific convex sets encode manifold convexity through tangent bundles and generalize geodesically convex sets.The paper uses this notion as the basis for its manifold gradient projection framework.Source: §1 · p. 1
  • Earlier manifold gradient-projection attempts were scarce and addressed tangent-space projections, not convex optimization on manifolds.The paper distinguishes those works from its convex-optimization framework.Source: §1 · p. 1
  • The algorithms are applied to weighted low-rank approximation and numerically validated on image completion.The paper frames image completion as a variation of matrix completion in computer vision and image processing.Source: §1 · pp. 1–2

2 Retraction-Specific Convex Sets on Manifolds

This section defines convex subsets relative to a chosen retraction by assigning convex tangent-space fibers to points in the set. The definition generalizes geodesic convexity while allowing properties such as disconnection.

Retraction and projections

  • A retraction is a C1 map from the tangent bundle to the manifold whose pointwise maps fix the base point and have identity differential at zero.These conditions are stated for each tangent space.Source: §2 · p. 2
  • Projection onto a closed convex subset of a finite-dimensional inner-product space gives a unique nearest point, and the projection map is continuous and non-expansive.The supplied passage also characterizes when a point is the projection.Source: §2 · p. 2

Retraction-specific convex sets

  • An R-convex set is a closed manifold subset equipped with a bundle of closed convex tangent-space fibers whose retraction images remain in the set and contain zero.The definition also requires local surjectivity and projective continuity.Source: §2 · p. 2

Properties of R-convex sets

  • With the exponential-map retraction, geodesically totally or strongly convex sets are R-convex, but R-convex sets need not be geodesically convex and may be disconnected.R-convexity is described as a local property; the paper notes that the bundle over a set need not be unique.Source: §2 · p. 2

3 Retraction-based Gradient Projection Algorithms on Manifolds

The paper formulates gradient projection on a manifold using projections in tangent-space fibers and retraction-based updates. It gives convergence guarantees for several stepsize rules, with an additional R-Lipschitz-gradient condition for constant stepsize.

3 Retraction-based Gradient Projection Algorithms on Manifolds

  • The algorithmic framework considers a C1 objective on an Riemannian manifold and an R-convex feasible set with a fixed convexity bundle.The section's goal is to generalize gradient projection algorithms to the restriction of the objective to that set.Source: §3 · p. 3

3.1 Retraction-based gradient projection

  • Algorithm 1 projects directions onto the current tangent-space fiber and generates feasible iterates using the manifold retraction.The algorithm assumes a Riemannian manifold, a C1 objective, an R-convex set with a fixed bundle, and a stepsize rule.Source: §3.1 · p. 3

3.2 Stepsize rules for Algorithm 1

  • The four stepsize choices comprise limited minimization, Armijo search along the feasible direction, Armijo search along the projection arc, and constant stepsize.The two Armijo rules vary whether the search adjusts the direction scale or the stepsize sequence.Source: §3.2 · p. 3

3.3 Stationary points

  • A feasible point is stationary when its differential is nonnegative on every vector in its associated tangent-space fiber.A local minimum of the objective composed with the retraction is stationary.Source: §3.3 · p. 3

3.4 Convergence results

  • For Stepsize Rules 3.1–3.3, every limit point of the generated iterates is stationary for the constrained objective.The result applies to sequences generated by Algorithm 1.Source: §3.4 · p. 4
  • Under Rule 3.4, every limit point is stationary when the gradient is R-Lipschitz over the feasible set and the constant stepsize satisfies 0 < s < 2L.R-Lipschitzness is defined using the gradient of the objective composed with the retraction.Source: §3.4 · p. 4

4 Application: Weighted Low-Rank Approximation with Retraction-Specific Convex Constraint

The paper formulates weighted low-rank approximation (WLRA) on a product manifold and constrains the problem using a retraction-specific convex set. It applies the resulting gradient projection routines to image completion and reports that they can outperform the benchmark in a sampled MNIST setting.

4.1 Formulation

  • The formulation represents the regularized WLRA objective on a product manifold, with Stiefel factors and a Euclidean low-rank factor.The manifold objective is equivalent to the regularized WLRA problem in the ambient matrix formulation.Source: §4.1 · pp. 4–5
  • The constrained WLRA solution set Cr is R-convex for the specified retraction, and the regularized WLRA solution lies in Cr when r is chosen as specified.The constraint is presented as a way to alleviate ill-posedness and degeneracy; the supplied passage does not give the value of r.Source: §4.1 · p. 5

4.2 Numerical Validation

  • The experiments model image completion as WLRA and compare Feasible Direction and Projection Arc with Regularized Armijo using RMSE across ranks, regularization values, and two retractions.The sampled training data comprise 6,000 MNIST images and 5,000 grayscale CIFAR-10 images, with a 0.5 masking rate.Source: §4.2 · pp. 5–6
  • The main routines could outperform Regularized Armijo over short and long horizons on sampled MNIST with the QR retraction and low-rank p = 128.The authors state that their experiments validate convergence results, while noting that the benchmark comparison is not comprehensive.Source: §4.2 · p. 6

5 Conclusion and Final Remarks

The paper concludes that it has established retraction-based convex optimization and gradient projection algorithms on Riemannian manifolds, with convergence results and an application to WLRA. It identifies extensions to Cayley transforms and stochastic algorithms as future directions.

5 Conclusion and Final Remarks

  • The framework comprises retraction-specific convex sets and gradient projection algorithms, with convergence results, and is applied to WLRA with numerical validation.The experiments concern convergence on image completion; the conclusion also identifies extensions to Cayley transforms and stochastic gradient projection as possible future work.Source: §5 · p. 6
  • The framework is limited to retractions and deterministic algorithms; Cayley transforms and stochastic gradient projection remain proposed extensions.Source: §5 · p. 6
  • Figure 1 reports routine comparisons across MNIST and CIFAR-10 configurations, with outcomes varying by retraction and low-rank setting.For example, it reports Feasible Direction outperforming the benchmark on sampled MNIST with the polar retraction at p = 128, and Projection Arc doing so with the QR retraction at p = 64.Source: Figure 1 · p. 8

A Proofs of Results in Section 3

  • The proofs use local surjectivity of the retraction to relate a constrained local minimum to stationarity of the objective on the feasible set.At the zero tangent vector, the differential of the retraction is the identity, linking the retracted objective's derivative to the original objective's derivative.Source: A Proofs of Results in Section 3 · p. 12
  • The convergence proofs follow Euclidean gradient projection arguments, handling limited minimization and feasible-direction Armijo steps before projection-arc Armijo steps.Source: A Proofs of Results in Section 3 · p. 12

A.1 The limited minimization rule and the Armijo rule along the feasible direction

This section defines retraction-based gradient projection algorithms on the product manifold M using QR- and polar-decomposition-based retractions and specified stepsize rules, and establishes stationary-limit guarantees for several rules. It also provides supplemental geometric and gradient formulas for the weighted low-rank approximation problem.

A.1 The limited minimization rule and the Armijo rule along the feasible direction

  • A point is stationary for f|C exactly when its projection of −s∇f(x∗) onto Cx∗ is zero for some, equivalently every, s > 0.Source: §A.1 · p. 12
  • The limited-minimization and feasible-direction Armijo rules ensure that every limit point is stationary for f|C.The limited-minimization update uses αk = β^mk; the feasible-direction rule minimizes along the retraction arc.Source: §A.1 · pp. 13–14

A.2 The constant stepsize rule

  • With an R-Lipschitz gradient over C, the constant-stepsize rule yields stationary limit points.The proof establishes descent and uses projective continuity to show the projected gradient vanishes at any limit point.Source: §A.2 · pp. 14–15

A.3 The Armijo rule along the projection arc

  • The projection-arc Armijo rule admits a positive acceptable stepsize and ensures that every limit point is stationary for f|C.For each x and σ ∈ (0, 1), some sx ∈ (0, 1] satisfies the rule for all s ∈ [0, sx].Source: §A.3 · pp. 15–17

B Supplemental Results for Section 4

B.1 Orthogonal Projection onto M

  • The product-manifold projection applies the Stiefel projections to the U and V components and leaves the x component unchanged.The ambient projection is (ΠU(ξ), y, ΠV(η)).Source: §B.1 · p. 17

B.2 Gradient of the WLRA Loss on M

  • The WLRA loss gradient on M is obtained by projecting the ambient gradient onto the product-manifold tangent space.Its components are specified through GU, GV, and Gx, with Stiefel projections applied to the U and V components.Source: §B.2 · p. 18

B.3 Projection-like Retractions on M

  • The QR-based retraction maps (U, x, V) and tangent direction (ξ, ˆx, η) to (qf(U + ξ), x + ˆx, qf(V + η)), and is a retraction on M.Here qf returns the orthonormal factor from a QR decomposition.Source: The QR-Decomposition-Based Retraction… · p. 18
  • The polar-based retraction maps (U, x, V) and (ξ, ˆx, η) to (pf(U, ξ), x + ˆx, pf(V, η)), and is a retraction on M.For small p, evaluating the polar map involves an eigenvalue decomposition of the p × p matrix I_p + ξ^T ξ.Source: The Polar-Decomposition-Based… · p. 19

B.4 Retraction-Based Gradient Projection

  • Algorithm 2 applies gradient projection to the R-convex set C_r using a QR- or polar-based retraction and a stepsize rule from Rule 3.2 or 3.3.Its inputs include a feasible initial point, the objective H, and its gradient.Source: §B.4 · p. 19

B.5 Proofs of Proposition 4.4 and Lemma 4.5

The proofs use radius-r balls to build feasible fibers, then establish fiber properties including convexity, feasibility under retraction, local surjectivity, and projective continuity.

B.5 Proofs of Proposition 4.4 and Lemma 4.5

  • Br(x) denotes the open ball centered at x with radius r, and the proof uses Br(-x) to form the Euclidean component of each fiber.Source: §B.5 · p. 19
  • Each C_r fiber is closed and convex, contains the zero vector, and remains feasible under the retraction.The proof uses Br(-x) for the Euclidean component of the fiber.Source: §B.5 · p. 19
  • The family of C_r fibers is locally surjective and projectively continuous.Source: §B.5 · p. 20

C Supplementary Numerical Results and Discussion

The supplementary results provide further numerical validation of the convergence results in Proposition 3.7, using two proposed routines and a benchmark routine.

C Supplementary Numerical Results and Discussion

C.1 Our Design of The Grid Search Experiments

The grid-search design combines Armijo-rule parameters into grid points and repeats the search across configurations and routines for each dataset.

C.1 Our Design of The Grid Search Experiments

  • Each combination of β, σ, and s defines one of 27 Armijo grid points per routine within a retraction-rank-regularization configuration.Source: Table 2 · p. 21
  • Each dataset uses 18 retraction-rank-regularization configurations and three routines, yielding 1458 grid-search runs.Source: Table 2 · p. 21
  • The Armijo tolerance is numerical slack in computing the stepsize rules.Source: Table 2 · p. 21

C.2 More Two-Stage Experiments on the Sampled Datasets

Across the sampled datasets, the main routines sometimes outperform Regularized Armijo across short and long runs, with advantages depending on masking rate, dataset, retraction, and rank. The experiments repeat the two-stage evaluation at masking rates 0.25 and 0.75.

Experimental setup

Masking Rate = 0.75

  • At masking rate 0.75, the main routines could outperform Regularized Armijo over both short and long horizons on MNIST with QR retraction and p = 64, and on CIFAR-10 with polar retraction and p = 64 or 128.The short-run results are in Table 3 and the long-run RMSE curves are in Figure 2.Source: Masking Rate = 0.75 · p. 21, Table 3 · p. 22, Figure 2 · p. 23

Masking Rate = 0.25

  • At masking rate 0.25, the main routines could outperform Regularized Armijo over both horizons on MNIST with polar retraction and p = 128, although the best-performing main routine differed between stages.The short-run results are in Table 4 and the long-run RMSE curves are in Figure 3.Source: Masking Rate = 0.25 · p. 24, Figure 3 · p. 24, Table 4 · p. 25

C.3 Grid Search Experiments on the Full Training Splits

Full-training-split grid-search results show that the best-performing routine varies by configuration, and successful-run RMSE comparisons must be read alongside failures. The CIFAR-10 results cover 200-iteration Stage 1 runs rather than long-run superiority.

Grid-search setup

  • Table 5 reports best and mean final RMSE and failures for each configuration on the full MNIST training split at masking rate 0.5.Failed runs reached the 200-step backtracking limit and are excluded from the two RMSE metrics.Source: §C.3 · p. 26, Table 5 · p. 26

Full-training CIFAR-10

  • On full-training CIFAR-10, the best-performing routine depends on configuration, with 1276 of 1458 grid runs succeeding and 182 failing at the backtracking limit.The RMSE comparisons are conditional on successful runs; these Stage 1 results describe 200 iterations, not long-run superiority.Source: §C.3 · p. 27, Table 6 · p. 27
  • With QR retraction, Projection Arc was uniquely best in four configurations and Feasible Direction in two; with polar retraction, Feasible Direction was uniquely best in five.Regularized Armijo was uniquely best in two QR and three polar configurations; both retraction ties occurred at p = 32 and λ = 10^-6.Source: §C.3 · p. 27

C.4 Paired, One-Sided t-Tests Across the Experiment Results

Paired tests support lower grid-search RMSE for both main routines across pooled configurations, but not lower final RMSE in the sampled-dataset long-run experiments. RMSE provides a common comparison metric because the routines’ objectives differ.

C.4 Paired, One-Sided t-Tests Across the Experiment Results

  • Across 144 matched configurations, both main routines had significantly lower best and mean RMSE than Regularized Armijo at the unadjusted 0.05 level.Feasible Direction differences were −2.617 × 10^-4 for best RMSE and −4.821 × 10^-5 for mean RMSE; Projection Arc differences were −2.472 × 10^-4 and −4.902 × 10^-5, respectively.Source: §C.4 · p. 28, Table 7 · p. 28
  • Across 108 sampled-dataset long-run pairs, the tests did not support lower final RMSE for either main routine at the unadjusted 0.05 level.The mean differences were −2.463 × 10^-4 for Feasible Direction and −2.206 × 10^-4 for Projection Arc; the pooled result does not rule out configuration-specific advantages.Source: §C.4 · p. 28, Table 8 · p. 28

C.5 Our Choice of RMSE as the Primary Evaluation Metric

  • The convergence result establishes stationary limit points for the specified Armijo rules, not an asymptotic convergence-rate guarantee.Accordingly, the experiments compare completion accuracy through RMSE rather than infer empirical convergence rates from objective values.Source: §C.5 · p. 28
  • RMSE was chosen because the routines’ objective values are not directly comparable, while RMSE uses the same definition for all three routines.The benchmark objective includes a regularization term that the main-routine objective does not.Source: §C.5 · p. 29

D.1 Datasets and Preprocessing

The appendix specifies the image-completion datasets and preprocessing, experiment configurations, evaluation metrics, test procedures, computing environment, and reproduction artifacts.

D.1 Datasets and Preprocessing

  • Sampled experiments use 6,000 balanced MNIST and 5,000 balanced grayscale CIFAR-10 training images, with masking rates 0.25, 0.5, and 0.75.Full-training Stage 1 experiments use 60,000 MNIST and 50,000 CIFAR-10 images at masking rate 0.5; images are flattened into matrix columns, and routines share the same initialization for each fixed configuration.Source: §D.1 · p. 29

D.2 Grid Searches and Long Runs

  • Grid searches vary ranks 32, 64, and 128; regularization values 10^-2, 10^-4, and 10^-6; and 27 Armijo parameter combinations per configuration.Selected parameters seed 1,000-iteration runs on sampled datasets; full-training tables report Stage 1 grid-search results only.Source: §D.2 · p. 29

D.3 Metrics and Statistical Tests

  • RMSE is evaluated on masked entries, and grid-search tables report best and mean final RMSE plus failed-grid counts; paired tests use one-sided alternatives at an unadjusted 0.05 threshold.The mean Armijo-check statistic averages checks per iteration across successful runs, excluding failed runs; it is not a 200-iteration total or a wall-clock cost.Source: §D.3 · p. 29

D.4 Hardware and Software

  • Experiments ran on an Apple M5 Pro CPU with 18 cores and 48 GB memory, using the listed Python, PyTorch, NumPy, SciPy, and Matplotlib versions on macOS.The exhaustive shards limited several numerical-library thread settings to two.Source: §D.4 · p. 30

D.5 Commands and Artifact Provenance

  • The public release includes implementation, experiment and analysis code, processed tables, and reference figures, but not the serialized dataset tensors.Reproduction requires obtaining and converting the public training data, rerunning grid-search and selected-history experiments, then regenerating summaries, tests, and plots from the new records.Source: §D.5 · p. 30

Related papers

Loading 2609.30885v1…