Dataset Information

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

ABSTRACT: This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest x♮∈ℝn from m quadratic equations/samples yi=(ai⊤x♮)2,1≤i≤m . This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficacy 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(log n + log(1/ϵ)) 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.

SUBMITTER: Chen Y

PROVIDER: S-EPMC8025800 | biostudies-literature | 2019 Jul

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

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

Chen Yuxin Y Chi Yuejie Y Fan Jianqing J Ma Cong C

Mathematical programming 20190204 1-2

This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest x ♮ ∈ ℝ n from <i>m</i> quadratic equations/samples y i = ( a i ⊤ x ♮ ) 2 , 1 ≤ i ≤ m . This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficacy of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient des ...[more]

PMID: 33833473

Similar Datasets

Project description:BackgroundGene Regulatory Networks (GRNs) have become a major focus of interest in recent years. Elucidating the architecture and dynamics of large scale gene regulatory networks is an important goal in systems biology. The knowledge of the gene regulatory networks further gives insights about gene regulatory pathways. This information leads to many potential applications in medicine and molecular biology, examples of which are identification of metabolic pathways, complex genetic diseases, drug discovery and toxicology analysis. High-throughput technologies allow studying various aspects of gene regulatory networks on a genome-wide scale and we will discuss recent advances as well as limitations and future challenges for gene network modeling. Novel approaches are needed to both infer the causal genes and generate hypothesis on the underlying regulatory mechanisms.MethodologyIn the present article, we introduce a new method for identifying a set of optimal gene regulatory pathways by using structural equations as a tool for modeling gene regulatory networks. The method, first of all, generates data on reaction flows in a pathway. A set of constraints is formulated incorporating weighting coefficients. Finally the gene regulatory pathways are obtained through optimization of an objective function with respect to these weighting coefficients. The effectiveness of the present method is successfully tested on ten gene regulatory networks existing in the literature. A comparative study with the existing extreme pathway analysis also forms a part of this investigation. The results compare favorably with earlier experimental results. The validated pathways point to a combination of previously documented and novel findings.ConclusionsWe show that our method can correctly identify the causal genes and effectively output experimentally verified pathways. The present method has been successful in deriving the optimal regulatory pathways for all the regulatory networks considered. The biological significance and applicability of the optimal pathways has also been discussed. Finally the usefulness of the present method on genetic engineering is depicted with an example.

Dataset Information

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

Publications

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

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets