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