The Local Landscape of Phase Retrieval Under Limited Samples

Lei Wu (吴磊), Kaizhao Liu, Zihao Wang, Lei WuIEEE Trans. Information Theory 2023

TL;DR

This paper analyzes the "local landscape" of the phase retrieval problem, specifically how the loss function behaves around the true solution when we have fewer data samples than dimensions. The authors show that with very few samples, the landscape becomes highly non-convex, making it difficult for standard gradient descent to find the correct solution. However, they also identify a sweet spot where the landscape is "one-point strongly convex," guaranteeing convergence to a good-enough solution.

What Problem Does This Paper Address?

Phase retrieval is a fundamental problem in signal processing and imaging where we aim to recover a signal from its magnitude measurements. This is often formulated as a non-convex optimization problem. While gradient descent methods are widely used and often surprisingly effective, understanding why they work, especially in scenarios with limited data, is crucial. This paper focuses on the "local landscape" of the loss function – its behavior in the vicinity of the true solution – when the number of samples ($n$) is significantly smaller than the dimensionality of the signal ($d$). Specifically, it investigates the minimal sample size required to ensure a "benign" landscape that allows for efficient optimization.

Methods

The authors employ a detailed analysis of the Hessian matrix of the loss function to understand its local curvature. They investigate two key properties:

  • Local Convexity: They analyze the eigenvalues of the Hessian matrix. They show that when $n = o(d \log d)$, the landscape is generally non-convex, meaning it has negative curvatures, making it difficult for optimization.
  • One-Point Strong Convexity: This is a weaker condition than standard strong convexity, ensuring that the gradient always points towards the true solution. The authors prove that this property holds when $n = \omega(d)$, allowing for fast convergence to an approximate solution. They also show that this property breaks down when $n = o(d \log d)$, indicating that exact recovery might be impossible with very few samples.

A novel "add-one trick" is introduced to handle the statistical dependencies that arise when analyzing sums of random variables with an adversarially chosen index.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Critical Role of Sample Size: The paper highlights a sharp transition in the landscape's behavior based on the ratio of samples to dimensions. There's a clear threshold around $n = \omega(d)$ for achieving one-point strong convexity and another around $n = o(d \log d)$ where the landscape becomes highly non-convex.
  • "Benign" vs. "Spurious" Landscapes: The work distinguishes between landscapes that are conducive to optimization (benign) and those that are not (spurious). They show that with very few samples, the landscape can be quite spurious, even near the true solution.
  • The Power of "One-Point" Convexity: The concept of one-point strong convexity is shown to be a powerful tool for guaranteeing convergence to approximate solutions, even when the overall landscape is non-convex.
  • "Add-One Trick" for Statistical Analysis: The introduction of the "add-one trick" is a significant methodological contribution, enabling a more rigorous analysis of statistical dependencies in the problem.

Key Results

  • Non-convexity with Limited Samples: When $n = o(d \log d)$, the local landscape is shown to be non-convex, with the degree of non-convexity increasing with dimension $d$.
  • One-Point Strong Convexity with Sufficient Samples: When $n = \omega(d)$, the landscape is one-point strongly convex in a local annulus, guaranteeing convergence to an $o_d(1)$-loss solution.
  • Impossibility of Exact Recovery with Very Few Samples: The breakdown of one-point convexity when $n = o(d \log d)$ suggests that guaranteeing convergence to the exact ground truth might be impossible with such limited samples using gradient descent alone.
  • Numerical Validation: Experiments support the theoretical findings, showing that the non-convexity (quantified by the minimum eigenvalue of the Hessian) increases as $d$ grows for a fixed $n/d$ ratio.

Limitations and Future Work

  • Focus on Local Landscape: The analysis is primarily focused on the local behavior around the true solution. While this is crucial for understanding gradient descent convergence, it doesn't fully characterize the global landscape.
  • Specific Model: The analysis is for a specific model of phase retrieval (least squares formulation with Gaussian inputs). Extending to other models or noise distributions could be valuable.
  • Future Directions: The authors suggest exploring alternative conditions for local convergence (e.g., Polyak-Łojasiewicz conditions), analyzing the full dynamics of gradient descent, and extending the analysis to complex phase retrieval settings.

Summary updated

Abstract

In this paper, we present a fine-grained analysis of the local landscape of phase retrieval under the regime of limited samples. Specifically, we aim to ascertain the minimal sample size required to guarantee a benign local landscape surrounding global minima in high dimensions. Let $n$ and $d$ denote the sample size and input dimension, respectively. We first explore the local convexity and establish that when $n=o(d\log d)$, for almost every fixed point in the local ball, the Hessian matrix has negative eigenvalues, provided $d$ is sufficiently large. % Consequently, the local landscape is highly non-convex. We next consider the one-point convexity and show that, as long as $n=ω(d)$, with high probability, the landscape is one-point strongly convex in the local annulus: $\{w\in\mathbb{R}^d: o_d(1)\leqslant \|w-w^*\|\leqslant c\}$, where $w^*$ is the ground truth and $c$ is an absolute constant. This implies that gradient descent, initialized from any point in this domain, can converge to an $o_d(1)$-loss solution exponentially fast. Furthermore, we show that when $n=o(d\log d)$, there is a radius of $\widetildeΘ\left(\sqrt{1/d}\right)$ such that one-point convexity breaks down in the corresponding smaller local ball. This indicates an impossibility of establishing a convergence to the exact $w^*$ for gradient descent under limited samples by relying solely on one-point convexity.
BibTeX
@article{2023local,
  author = {Lei Wu (吴磊) and Kaizhao Liu and Zihao Wang and Lei Wu},
  title = {{The Local Landscape of Phase Retrieval Under Limited Samples}},
  journal = {IEEE Trans. Information Theory},
  year = {2023},
}
Figure