PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval

Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma

arXiv:1803.07726v2stat.MLcs.ITcs.LGmath.NAmath.OC

TL;DR

The paper asks whether phase retrieval from quadratic measurements can be solved efficiently by vanilla gradient descent without carefully designed initialization. It analyzes randomly initialized GD under Gaussian designs using leave-one-out decoupling, proving ε-accurate recovery in O(log n + log(1/ε)) iterations with nearly minimal samples. The result provides a global convergence guarantee without sample splitting or specialized saddle-point escaping.

  • Problem

    The paper addresses efficient recovery from quadratic measurements when the least-squares objective is highly nonconvex and the necessity of carefully designed initialization for fast convergence remains unclear.

  • Method

    The paper analyzes randomly initialized vanilla gradient descent under Gaussian designs using leave-one-out sequences to establish near-independence between iterates and design vectors.

  • Results

    GD reaches ε-accuracy in O(log n + log(1/ε)) iterations with m ≳ n poly log(m) samples, using fixed stepsizes and no sample splitting.

  • Takeaways & Limitations

    Randomly initialized vanilla GD achieves global convergence for phase retrieval while avoiding carefully designed initialization, sample splitting, and sophisticated saddle-point escaping schemes.

  • Takeaways & Limitations

    The current sample complexity is m ≳ n log^13 m, which is optimal only up to logarithmic factors.

Abstract

from arXiv · show

This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest $\mathbf{x}^{\natural}\in\mathbb{R}^{n}$ from $m$ quadratic equations/samples $y_{i}=(\mathbf{a}_{i}^{\top}\mathbf{x}^{\natural})^{2}$, $1\leq i\leq m$. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficiency of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descent --- when randomly initialized --- yields an $ε$-accurate solution in $O\big(\log n+\log(1/ε)\big)$ iterations given nearly minimal samples, thus achieving near-optimal computational and sample complexities at once. This provides the first global convergence guarantee concerning vanilla gradient descent for phase retrieval, without the need of (i) carefully-designed initialization, (ii) sample splitting, or (iii) sophisticated saddle-point escaping schemes. All of these are achieved by exploiting the statistical models in analyzing optimization algorithms, via a leave-one-out approach that enables the decoupling of certain statistical dependency between the gradient descent iterates and the data.

1 Introduction

The paper studies recovery from quadratic measurements and asks whether randomly initialized vanilla gradient descent can efficiently solve the resulting nonconvex problem. Under Gaussian designs, it establishes fast convergence with near-minimal samples while avoiding specialized initialization, sample splitting, and saddle-point escaping.

  • Problem: Quadratic measurements arise in phase retrieval and related machine-learning problems, including mixed linear regression and quadratic-activation neural networks.The model recovers x^natural from samples y_i=(a_i^T x^natural)^2.
  • Approach: Vanilla gradient descent minimizes a nonconvex least-squares objective using an iterative stepsize-controlled update, also known as Wirtinger flow.Prior guarantees typically relied on carefully designed initialization and stronger sample-size conditions.
  • Mechanism: The signal-to-orthogonal-component ratio grows exponentially, while the signal component becomes dominant within several tens of iterations.These dynamics explain the short duration of Stage 1 before linear convergence begins.
  • Main findings: O(log n) iterations suffice for randomly initialized GD to enter a local region around the truth, after which the estimation error contracts linearly.The two stages correspond to an initial signal-growth phase and a subsequent geometric-decay phase.
  • Main findings: m ≳ n poly log(m) samples yield near-minimal sample complexity, optimal up to logarithmic factors because at least n samples are needed for n unknowns.The analysis uses Gaussian designs and allows a fixed stepsize with data reused across iterations.
  • Analysis: The iterates avoid saddle points and remain in a favorable geometric region, without requiring sophisticated saddle-point escaping schemes.The paper attributes the analysis to weak statistical dependence and leave-one-out constructions that decouple iterates from design vectors.

2 Why random initialization works?

Random initialization works because population dynamics amplify the signal component while suppressing the orthogonal component, and leave-one-out analysis shows finite-sample iterates remain near this favorable trajectory.

  • Population dynamics: The population dynamics have fixed points corresponding to the global minimizer, local maximizer, and saddle points of the population objective.The fixed points are (1, 0), (0, 0), and (0, 1/...).
  • Population dynamics: The signal-to-orthogonal strength ratio α_t/β_t increases exponentially fast under random initialization.This ratio captures the relative sizes of the signal and orthogonal components.
  • Population dynamics: The signal size α_t grows until it plateaus around 1, while the orthogonal size β_t eventually drops toward zero.Together, these dynamics drive (α_t, β_t) rapidly toward (1, 0).
  • Population dynamics: Randomly initialized population iterates converge rapidly to the truth without getting stuck at undesirable saddle points.Figure 4 illustrates the ratio, signal component, and orthogonal component for n = 1000 and η_t ≡ 0.1.
  • Finite-sample analysis: a heuristic treatment: The finite-sample heuristic approximates population dynamics when m ≳ n poly log(m), assuming iterates are independent of the design vectors.Under this assumption, CLT arguments control gradient fluctuations, but the independence assumption does not hold when data are reused.
  • Key analysis ingredients: near-independence and leave-one-out tricks: Leave-one-out and random-sign auxiliary sequences decouple iterates from selected design-vector components while remaining close to the original trajectory.These constructions provide the near-independence needed to control fluctuations without sample splitting.

3 Related work

Prior work spans convex relaxations, spectral-initialized Wirtinger flow, and generic saddle-point escaping methods for phase retrieval. The paper contrasts these approaches with a simpler gradient-descent analysis whose iterates remain in a region with more benign geometry than worst-case global characterizations.

  • Convex and nonconvex methods: Phase retrieval has been studied through convex relaxation and numerous nonconvex methods, but large-scale semidefinite programs are computationally prohibitive.PhaseLift requires the sample ratio to exceed a sufficiently large constant, while many nonconvex methods use carefully designed initialization.
  • Convex and nonconvex methods: Spectral-initialized Wirtinger flow established convergence guarantees for a nonconvex method without sample splitting, with later work improving sample and computation complexities through adaptive truncation.
  • Saddle-point escaping methods: Generic saddle-point escaping methods exploit global geometric properties: local minima are global, and all saddle points are strict when m is sufficiently larger than n log^3 n.
  • Saddle-point escaping methods: Worst-case saddle-escaping complexity is inflated by dimension-dependent smoothness, Hessian smoothness, and local conditioning, whereas random-GD iterates remain in a more benign restricted region.
  • Saddle-point escaping methods: Randomly initialized vanilla gradient descent avoids saddle points in phase retrieval, unlike generic settings where randomly initialized GD can require exponential time to escape them.

4 Analysis

The analysis establishes that randomly initialized gradient descent enters a local region in O(log n) iterations and then converges linearly, using approximate state evolution justified by leave-one-out arguments.

  • Theorem 2: m ≥ Cn log^13 m and an initialization independent of the data satisfy the assumptions used to analyze vanilla gradient descent.The initialization must also obey a condition involving the signal norm and a sufficiently small constant.
  • Theorem 2: The GD iterates converge linearly to x♮ after Tγ ≲ log n iterations.The first-stage duration is short, after which prior local-convergence theory applies.
  • Remarks: The sample complexity is m ≳ n log^13 m, which is optimal up to logarithmic factors, while analogous guarantees for noisy phase retrieval are stated without full theorem details.The noisy-result proofs are deferred to the last author’s Ph.D. thesis.
  • Stage 1 dynamics: The signal-to-orthogonal component ratio grows exponentially during Stage 1, driving the iterates toward the local region around the global minimizer.The signal component grows faster than the orthogonal component before Tγ.
  • Leave-one-out analysis: The proof controls the approximate state evolution by constructing leave-one-out sequences that create near-independence between iterates and selected data components.These auxiliary sequences are designed to remain close to the original iterates while being independent of particular sampling vectors or sign information.
  • Leave-one-out analysis: The perturbation terms must be controlled below order 1/log n because uniform bounds can be too large for the required control of I4.The analysis instead approximates dependent quantities by sums of independent variables and applies concentration arguments.

1. In words, (40a), (40b), (40c) specify that the leave-one-out sequences

The proof tracks gradient-descent iterates through leave-one-out and related auxiliary sequences, using induction and approximate state evolution across two phases. These constructions control signal and orthogonal components while managing dependencies with the sampling vectors.

  • Phase-wise induction: The induction hypotheses track approximation errors, signal-direction differences, orthogonality, and related quantities across Phase I and Phase II.The proof propagates these hypotheses inductively through the iterations, with separate lemmas controlling each required relation.
  • Growth rates: The signal-to-orthogonal growth-rate difference is crucial for proving the advertised convergence result.Quantities associated with the signal component grow at the rate of α_t, whereas the leave-one-out discrepancy follows β_t up to a logarithmic factor.
  • Approximate state evolution: The proof establishes approximate state evolution for both the signal size α_t and orthogonal size β_t throughout the analyzed phases.Lemma 2 gives the one-step implication in Phase I, while Lemma 8 supplies the corresponding Phase II statement.
  • Leave-one-out control: The leave-one-out sequence is used to establish near-independence between the iterates and individual sampling vectors, enabling sharp residual control.In Phase II, the leave-one-out sequence alone suffices once the signal component exceeds a polylogarithmic threshold.
  • Phase transition: After Phase I, the signal and orthogonal components become comparable, with α_T1 ≍ β_T1 ≍ 1, supporting the transition to later convergence analysis.The proof then applies established arguments for iterations beyond T_γ.

5 Discussions

The discussion presents fast global convergence from random initialization, explains the role of weak iterate–data dependence, and identifies sample-complexity and generalization questions that remain open.

  • Main result: Gradient descent with random initialization achieves relative ε-accuracy in O(log n + log(1/ε)) iterations.The guarantee is stated for phase retrieval under the paper’s Gaussian sampling model.
  • Open questions: The theorem requires m ≫ n log^13 m samples, while improving this sample complexity and locating a phase transition remain open questions.The paper explicitly identifies the logarithmic sample factor as a proviso of the result.
  • Broader scope: The paper asks whether fast global convergence extends to other nonconvex statistical estimation problems, including matrix and tensor recovery, blind deconvolution, and neural networks.It also suggests that the introduced leave-one-out and near-independence tools may help analyze those settings.
  • Sampling models: Experiments verify fast convergence under Rademacher sampling vectors, although the theoretical work assumes Gaussian sampling vectors.Figure 8 uses n = 1000, m = 10n, and constant stepsize η_t ≡ 0.1.
  • Technical mechanism: The leave-one-out construction creates an auxiliary sequence independent of selected design components and close to the original iterates.This decoupling supports the near-independence analysis used to establish the method’s efficiency.

B Proof of Lemma 1

The proof divides Stage 1 into substages that track the evolution of the signal and orthogonal components until the signal becomes sufficiently strong. These bounds establish persistent signal growth and controlled component sizes through T_γ.

  • Stage 1 decomposition: Stage 1 is divided into substages according to the size and evolution of the signal component, with Figure 9 illustrating the decomposition.The analysis uses sufficiently small η and c_4, independent of n.
  • Stage 1.2: For T_1 < t ≤ T_2, the proof maintains the required bounds on α_t and β_t through a separate inductive stage.These bounds collectively establish the target claim for this interval.
  • Stage 1.3: In the final Stage 1 substage, both α_t and β_t may decrease, but α_t remains bounded away from zero and β_t remains at least on a constant scale.The resulting bounds hold for all 0 ≤ t < T_γ.
  • Aggregate bounds: The analysis concludes with c_5 ≤ β_t ≤ 1.5 and 1/(2√n log n) ≤ α_t ≤ 2 for 0 ≤ t < T_γ.These bounds summarize the component control established across the substages.
  • Stage 1.1: During the early substage, α_t keeps increasing while β_t decreases before the signal crosses the threshold c_4.The proof bounds the duration and growth of this initial regime.

C.1 Proof of (41a)

The proof controls the signal-direction error by decomposing gradient terms into several components and bounding them with concentration, independence, and incoherence arguments.

  • Random-sign control: The random-sign sequence makes sign variables independent of selected orthogonal design components, enabling Bernstein-type bounds for weighted sums.This device is used particularly in controlling J_2 and J_4.
  • Residual control: The resulting estimates yield a residual bound for the signal-direction update under sample-size and incoherence conditions.The proof combines bounds on the decomposed terms before substituting the induction hypotheses.
  • Signal-direction conclusion: The final argument uses the induction hypotheses and α_t = ⟨x_t, x^natural⟩ to translate the aggregate gradient estimate into the desired signal-component control.The required conditions include sample-size bounds and norm relations for the iterates.

D Proof of Lemma 4

The proof establishes the required bounds by decomposing gradient-related terms, controlling each component with concentration and norm inequalities, and closing the induction under sample-size and phase-I assumptions.

  • Leave-one-out control: The induction step relies on independence between leave-one-out iterates and individual sensing vectors.This independence enables standard Gaussian concentration for terms involving ai and xt,(i).
  • Induction closure: The proof closes by combining the component estimates, applying the union bound over all sample indices, and verifying the inductive hypotheses.The final steps use the established bounds together with the phase-I assumptions and induction relations.

G Proof of Lemma 7

The proof bounds the gradient-update discrepancy through a leave-one-out comparison, decomposing the error into components and controlling them with independence, concentration, and inductive estimates.

  • Decomposition: The comparison separates the gradient-update difference into terms involving v1, v2, w1, w2, and w3.The proof further splits w3 into parallel and orthogonal entries and treats the resulting components separately.
  • Concentration: Independence between leave-one-out iterates and sensing vectors supports Gaussian and Bernstein concentration bounds for the decomposed terms.The argument explicitly invokes independence for al, xt,(l), and related leave-one-out quantities.
  • Auxiliary bounds: Cauchy–Schwarz, triangle inequalities, norm bounds, and incoherence conditions control the remaining deterministic and cross terms.These tools are used repeatedly to bound residual terms and the parallel and orthogonal components.
  • Conclusion: The component estimates are combined to bound xt+1 − xt+1,(l) − xt+1,sgn + xt+1,sgn,(l) during the induction period.The proof then uses Claim 1 and the inductive hypotheses to simplify the combined bound.

H Proof of Lemma 8

The proof combines prior appendix estimates with incoherence and sample-size assumptions to derive the target bound, concluding with a controlled residual term.

  • Direct concentration: The argument avoids the leave-one-out sequence used earlier by applying Lemma 12 directly with the incoherence condition (49a).This direct route is stated to require m ≫ n log^13 m.
  • Residual control: The proof combines the preceding estimates to obtain a residual representation with |ζt| ≪ 1/log m.The residual control completes the proof of the lemma.
  • Assumptions: Additional bounds are verified under the hypotheses (48a), sufficiently small η, and sufficiently large constants where required.The proof also invokes an appendix result and a trivial upper bound to establish the remaining conditions.

J Proof of Lemma 12

The proof establishes uniform concentration by first controlling deviations for a fixed vector, then extending the result over the sphere with a net argument and union bounds.

  • Fixed-vector bound: For a fixed vector z independent of the sensing vectors, the proof applies Bernstein’s inequality to the empirical average of centered random variables.The variables gi(z) depend only on z and ai, and their variance and magnitude parameters are bounded before concentration is applied.
  • Fixed-vector bound: 233The fixed-vector deviation bound achieves probability exceeding 1 − 2 exp(−c3 n log n) when the stated concentration quantities are sufficiently large.
  • Uniformization: A θ-net of the unit sphere converts the fixed-vector estimate into a uniform bound through approximation and the triangle inequality.The proof controls the net points with a union bound and separately bounds the approximation error.
  • Uniform conclusion: The resulting uniform estimate is obtained for all z ∈ R^n with probability at least 1 − 2 exp(−c4 n log n), subject to ε ≥ 1/n and an additional lower-bound condition.The proof also uses the high-probability event controlling maxi |ai,1|.

K Proof of Lemma 14

The proof establishes uniform bounds through concentration, covering arguments, and control of decomposed error terms. It then combines these estimates under sample-size and step-size conditions.

  • Uniform concentration: Uniform bounds over unit vectors follow by combining fixed-vector concentration with a θ-net covering argument and the triangle inequality.The net approximates every unit vector, while the resulting approximation errors are controlled using norm inequalities.
  • Term-wise control: The proof decomposes the target quantity into terms I1, I2, and I3, bounding them using union bounds, Cauchy–Schwarz, smoothness, and an auxiliary claim.The auxiliary claim holds with probability at least 1 −c2e−c3n log m.
  • Final combination: The resulting inequalities hold with high probability uniformly over unit vectors after selecting θ ≍m−α−1 and combining the bounds on θ1 and θ2.Several intermediate bounds are established with probabilities of the form 1 −O(·) or 1 −c2e−c3n log m.
  • Hessian control: m ≫ n log3 m ensures the Hessian-based bounds and permits a sufficiently small step size η such that In −η∇2f(z) ⪰ 0.The step-size restriction is stated through η < c2 max{∥z∥2,1} for sufficiently small c2.

N Proof of Theorem 3

Theorem 3 extends the convergence proof by identifying independence conditions sufficient for the initialization and leave-one-out sequences. A uniformly spherical initialization is then shown to satisfy those requirements, completing the theorem.

  • Required conditions: Theorem 3 does not require independence between x0 and the full data; it requires prescribed independence for leave-one-out constructions and the base-case conditions.The proof explicitly identifies independence of x0,(l) from (al, yl) and of x0,sgn,(l) from both the sign variables and (al, yl).
  • Random initialization: A uniformly distributed unit-sphere vector u is used to construct an initialization satisfying the required restrictions and independence properties.The first restriction is verified using concentration inequalities for the spherical distribution.
  • Base case: The constructions x0,sgn = x0 and x0,sgn,(l) = x0,(l) make two base-case relations hold trivially.The remaining base-case relations are verified using the stated initialization property (14).
  • Conclusion: Combining the base case and independence properties with the proof of Theorem 2 completes the proof of Theorem 3.The theorem’s convergence claim therefore follows for the specified random initialization.
Loading 1803.07726v2…