Phase transition of \emph{descending} phase retrieval algorithms

• URL: http://arxiv.org/abs/2506.18275v1
• Date: Mon, 23 Jun 2025 04:10:35 GMT
• Title: Phase transition of \emph{descending} phase retrieval algorithms
• Authors: Mihailo Stojnic,
• Abstract summary: We study theoretical limits of emphdescending phase retrieval algorithms.<n>We identify the concepts of emphparametric manifold and its emphfunneling points as key mathematical objects.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study theoretical limits of \emph{descending} phase retrieval algorithms. Utilizing \emph{Random duality theory} (RDT) we develop a generic program that allows statistical characterization of various algorithmic performance metrics. Through these we identify the concepts of \emph{parametric manifold} and its \emph{funneling points} as key mathematical objects that govern the underlying algorithms' behavior. An isomorphism between single funneling point manifolds and global convergence of descending algorithms is established. The structure and shape of the parametric manifold as well as its dependence on the sample complexity are studied through both plain and lifted RDT. Emergence of a phase transition is observed. Namely, as sample complexity increases, parametric manifold transitions from a multi to a single funneling point structure. This in return corresponds to a transition from the scenarios where descending algorithms generically fail to the scenarios where they succeed in solving phase retrieval. We also develop and implement a practical algorithmic variant that in a hybrid alternating fashion combines a barrier and a plain gradient descent. Even though the theoretical results are obtained for infinite dimensional scenarios (and consequently non-jittery parametric manifolds), we observe a strong agrement between theoretical and simulated phase transitions predictions for fairly small dimensions on the order of a few hundreds.

Related papers

• Robust Multi-Manifold Clustering via Simplex Paths [10.304857373037596]
  This article introduces a novel, geometric approach for multi-manifold clustering (MMC)<n>We first compute a locality graph on d-simplices, using the dihedral angle in between adjacent simplices as the graph weights, and then compute infinity path distances in this simplex graph.<n>We analyze the properties of LAPD under random sampling, and prove that with an appropriate denoising procedure, this metric separates the manifold components with high probability.
  arXiv  Detail & Related papers  (2025-07-14T18:22:50Z)
• Phase retrieval with rank $d$ measurements -- \emph{descending} algorithms phase transitions [0.0]
  [118] developed a powerful emphRandom duality theory (RDT) based analytical program.<n>We show how it can be utilized to handle rank $d$ positive definite phase retrieval (PR) measurements.
  arXiv  Detail & Related papers  (2025-06-23T04:28:46Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms [19.99781875916751]
  We show that textttZo-RASA achieves optimal sample complexities for generating $epsilon$-approximation first-order stationary solutions. We improve the algorithm's practicality by using geometrics and vector transport, instead of exponential mappings and parallel transports.
  arXiv  Detail & Related papers  (2023-09-25T20:13:36Z)
• Multi-Frequency Joint Community Detection and Phase Synchronization [22.683901672480353]
  This paper studies the joint community detection and phase synchronization problem on the textitstochastic block model with relative phase We show this problem exhibits a textitmulti-frequency'' structure by closely examining its maximum likelihood estimation (MLE) formulation. Two simple yet efficient algorithms that leverage the MLE formulation and benefit from the information across multiple frequencies are proposed.
  arXiv  Detail & Related papers  (2022-06-16T23:08:27Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic [4.94128206910124]
  We introduce a fully decentralized Actor-Critic (AC) algorithm, where actor, critic, and global reward estimator are updated in an alternating manner. We show that our algorithm has sample complexity of $tildemathcalO(epsilon-2)$ under Markovian sampling. We also provide a local action privacy-preserving version of our algorithm and its analysis.
  arXiv  Detail & Related papers  (2022-06-12T13:14:14Z)
• Orbital MCMC [82.54438698903775]
  We propose two practical algorithms for constructing periodic orbits from any diffeomorphism. We also perform an empirical study demonstrating the practical advantages of both kernels.
  arXiv  Detail & Related papers  (2020-10-15T22:25:52Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  Although model-agnostic metalearning (MAML) is a very successful algorithm meta-learning practice, it can have high computational complexity. Our paper shows that such complexity can significantly affect the overall convergence performance of ANIL.
  arXiv  Detail & Related papers  (2020-06-16T19:57:48Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.