Misspecified nonconvex statistical optimization for sparse phase retrieval

Zhuoran Yang, Lin F. Yang, Ethan X. Fang, Tuo Zhao, Zhaoran Wang, Matey Neykov

TL;DR

This paper tackles a crucial problem in statistical optimization: how to reliably estimate parameters when the underlying data-generating model is not perfectly known (model misspecification). The authors propose a robust variant of the Thresholded Wirtinger Flow (TWF) algorithm for phase retrieval problems, demonstrating that it achieves optimal statistical accuracy even with misspecified link functions, a significant step beyond existing methods that assume perfect model knowledge.

What Problem Does This Paper Address?

Phase retrieval is a fundamental problem in various scientific fields, aiming to recover a signal from its magnitude measurements. A common approach involves solving a nonconvex optimization problem. While theoretical guarantees exist for algorithms like Thresholded Wirtinger Flow (TWF), these guarantees typically rely on the assumption that the data is generated precisely according to a known statistical model. This is a strong assumption, as real-world data often deviates from idealized models. This paper addresses the critical challenge of model misspecification in high-dimensional sparse phase retrieval. Specifically, it investigates what happens when the "link function" (which relates the signal to the observed data) is unknown or incorrectly specified, and how existing optimization algorithms perform under such conditions. The authors aim to develop an algorithm that is robust to these deviations and still achieves statistically optimal results.

Methods

The core contribution is a modified version of the Thresholded Wirtinger Flow (TWF) algorithm. The standard TWF algorithm relies on the precise specification of the data-generating model. The authors adapt TWF by:

  • A Robust Loss Function: Instead of minimizing the standard least-squares loss, they propose minimizing the variance of the observed data minus the squared signal estimate. This variance-based loss function is shown to be more robust to misspecification, particularly when the expected value of the observed data is not positive.
  • Thresholded Spectral Initialization: To ensure good performance, the algorithm requires a strong initial guess for the sparse signal. The authors introduce a Thresholded Spectral Method (TSM) that leverages spectral properties of the data to obtain an initial estimate. This method is designed to be robust to noise and to identify the support of the sparse signal.
  • Theoretical Guarantees: The paper provides theoretical guarantees for the proposed algorithm, proving that it achieves linear convergence to an estimator with optimal statistical accuracy, even under model misspecification. This is a significant theoretical advancement, as most existing work assumes perfect model specification.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulated experiments.

Key Insights and Ideas

  • Robustness is Key: The most significant insight is that statistical optimization algorithms can be made robust to model misspecification. This is crucial for applying these methods to real-world problems where perfect model knowledge is rare.
  • Variance Loss for Robustness: The choice of a variance-based loss function over a standard least-squares loss is a clever way to handle misspecification, especially when the expected data values are not strictly positive.
  • Initialization Matters: The success of TWF-like algorithms heavily relies on a good initialization. The proposed Thresholded Spectral Method provides a principled way to obtain such an initialization, even in the presence of misspecification.
  • Optimal Performance Under Misspecification: Surprisingly, the authors show that their algorithm achieves the same optimal statistical rate of convergence and sample complexity as algorithms designed for the correctly specified model. This suggests that the proposed approach is highly efficient and resilient.

Key Results

  • The proposed modified TWF algorithm achieves linear convergence to an estimator.
  • The estimator achieves optimal statistical accuracy, matching the best known results for the correctly specified phase retrieval problem.
  • The sample complexity is $n = \Omega(s^2 \log p)$, and the statistical rate of convergence is $\sqrt{s \log p / n}$, where $s$ is the sparsity and $p$ is the dimensionality. These rates are optimal.
  • Extensive numerical experiments on simulated data with various misspecified link functions demonstrate the algorithm's effectiveness and robustness.
  • A real-world image processing example (Starry Night image reconstruction) shows the algorithm's practical utility and superior performance compared to initialization-based reconstruction.

Limitations and Future Work

  • Identifiability: The paper notes that the single index model (SIM) is not identifiable without additional constraints, as the norm of $\beta^*$ can be absorbed into the link function $h$. The authors address this by assuming $||\beta^*||_2 = 1$. They also mention that the model is only identifiable up to the global sign of $\beta^*$.
  • Computational Complexity: While the algorithm achieves optimal statistical rates, the computational complexity of the initialization step and the iterative updates, though analyzed, might still be a consideration for extremely high-dimensional problems.
  • Generalization: The authors express hope that their techniques can be extended to more general nonconvex optimization problems and to address other forms of model misspecification.
  • Specific Link Functions: While the theory covers a broad family of link functions satisfying certain conditions, exploring performance with specific, complex, or highly non-linear link functions could be a future direction.

Summary updated

Abstract

Existing nonconvex statistical optimization theory and methods crucially rely on the correct specification of the underlying “true” statistical models. To address this issue, we take a first step towards taming model misspecification by studying the high-dimensional sparse phase retrieval problem with misspecified link functions. In particular, we propose a simple variant of the thresholded Wirtinger flow algorithm that, given a proper initialization, linearly converges to an estimator with optimal statistical accuracy for a broad family of unknown link functions. We further provide extensive numerical experiments to support our theoretical findings.
BibTeX
@inproceedings{yang2019misspecified,
  author = {Zhuoran Yang and Lin F. Yang and Ethan X. Fang and Tuo Zhao and Zhaoran Wang and Matey Neykov},
  title = {{Misspecified nonconvex statistical optimization for sparse phase retrieval}},
  booktitle = {Math. Program},
  year = {2019},
  url = {https://openreview.net/forum?id=aJF4OcD_L5Y},
}

Loading related content...

Figure