On Local Linear Convergence of Projected Gradient Descent for Unit-Modulus Least Squares

Trung Vu, Raviv Raich, Xiao FuIEEE TSP 2023 · DOI

TL;DR

This paper analyzes the convergence of Projected Gradient Descent (PGD) for the Unit-Modulus Least Squares (UMLS) problem, a common task in signal processing. The authors demonstrate that PGD, contrary to previous findings of sublinear convergence, exhibits linear convergence near a local minimum, providing a theoretical explanation for its observed fast performance. They also introduce adaptive step-size variants of PGD that achieve this fast convergence without requiring prior knowledge of the solution.

What Problem Does This Paper Address?

The Unit-Modulus Least Squares (UMLS) problem is a fundamental optimization task with applications in areas like phase-only beamforming, phase retrieval, and sensor network localization. It involves finding a vector where each element has a unit modulus (e.g., complex numbers on the unit circle) that best fits a linear model. While PGD is a simple and efficient algorithm for this problem, existing theoretical analyses have only established sublinear convergence rates, failing to explain the rapid convergence often seen in practice. This discrepancy suggests that the existing analyses might be too conservative and not fully capture the problem's local geometry. The paper aims to bridge this gap by providing a rigorous analysis of PGD's local convergence behavior, specifically demonstrating and explaining its linear convergence rate near a local minimum.

Methods

The core of this paper is a novel convergence analysis of Projected Gradient Descent (PGD) for the UMLS problem. The authors achieve this by:

  • Real-Valued Formulation: They first reformulate the complex-valued UMLS problem into a real-valued optimization problem with unit-modulus constraints on each coordinate pair. This allows for easier mathematical manipulation.
  • Local Analysis: Instead of focusing on global convergence, the analysis centers on the behavior of PGD near a strict local minimum. This involves examining the local structure of the objective function and the constraint set.
  • Lagrangian and Hessian Analysis: They utilize Lagrangian multipliers and analyze the reduced Riemannian Hessian to characterize the local geometry around stationary points. This helps identify conditions for strict local minima.
  • Fixed-Point Analysis: PGD is viewed as a fixed-point iteration. The authors derive conditions on the step size and problem parameters that guarantee convergence to a strict local minimum.
  • Adaptive Step-Size Variants: Based on their theoretical insights, they propose two adaptive step-size variants of PGD: Backtracking PGD (Bt-PGD) and Adaptive Restart Nesterov's Accelerated PGD (ARNAPGD). These methods aim to find a good step size automatically, avoiding the need for prior knowledge of the solution.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated for numerical experiments to validate the theoretical findings. The data generation process is described in Section VI.A, where matrices and vectors are created to satisfy the conditions for a strict local minimum and a positive definite reduced Riemannian Hessian.

Key Insights and Ideas

  • Linear Convergence is Real: The most significant insight is the demonstration that PGD, under certain conditions, exhibits linear convergence to a strict local minimum for the UMLS problem. This is a crucial finding because it explains the observed fast convergence in practice, which was not accounted for by previous sublinear convergence results.
  • Local Geometry Matters: The paper highlights that while UMLS is non-convex globally, its local geometry around a strict minimum can be "benign" enough to allow for linear convergence, similar to gradient descent on strongly convex functions.
  • Exact Convergence Rate: The authors derive an exact expression for the local linear convergence rate, allowing for precise prediction of PGD's performance near a solution.
  • Adaptive Step Sizes for Practicality: The development of adaptive step-size variants (Bt-PGD and ARNAPGD) is a key practical contribution. These methods bypass the need to know the optimal step size beforehand, making PGD more robust and easier to apply in real-world scenarios.
  • Conservative Nature of Previous Bounds: The work implicitly shows that previous bounds on the step size for PGD convergence were conservative, as their adaptive methods and analysis with optimal fixed step sizes allow for larger step sizes and faster convergence.

Key Results

  • Theoretical Guarantee of Linear Convergence: The paper provides Theorem 1, which establishes the conditions (strict local minimum, specific step size constraints) under which PGD converges linearly to a strict local minimum.
  • Exact Convergence Rate Formula: An explicit formula for the linear convergence rate, $\rho(M_\eta)$, is derived, which depends on the step size $\eta$, the Lagrange multipliers $\gamma$, and the reduced Riemannian Hessian $H$.
  • Optimal Step Size Identification: The analysis allows for the identification of an optimal fixed step size $\eta^*$ that maximizes the convergence rate, as demonstrated in Figure 2(a).
  • Numerical Validation: Simulations show that the theoretical convergence rate accurately predicts the empirical rate, and that PGD with an optimal step size converges significantly faster than with a commonly used conservative step size (Figure 2(b)).
  • Adaptive Methods Outperform: The proposed adaptive step-size methods (Bt-PGD and ARNAPGD) are shown to achieve fast convergence comparable to or better than PGD with an optimal fixed step size, without requiring prior knowledge of the solution (Figures 3 and 4).

Limitations and Future Work

  • Local Convergence: The primary analysis focuses on local linear convergence. While this explains observed behavior, it doesn't guarantee convergence from arbitrary initial points. The paper does establish a region of convergence around the strict local minimum.
  • Non-Convexity Challenges: The adaptive methods (Bt-PGD and ARNAPGD) are presented without formal convergence guarantees due to the non-convex nature of the UMLS problem. However, their practical effectiveness is demonstrated.
  • Future Work:
    • Improving the bound on the region of convergence.
  • Developing theoretical convergence guarantees for the adaptive step-size methods (Bt-PGD and ARNAPGD), which is challenging due to the non-linear dependence of the spectral radius on the step size.
  • Investigating closed-form expressions for optimal step sizes in accelerated PGD variants.

Summary updated

BibTeX
@article{vu2023local,
  author = {Trung Vu and Raviv Raich and Xiao Fu},
  title = {{On Local Linear Convergence of Projected Gradient Descent for Unit-Modulus Least Squares}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
  doi = {10.1109/tsp.2023.3324181},
}

Loading related content...

Figure