The Local Landscape of Phase Retrieval Under Limited Samples
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914970245005312 |
|---|---|
| author | Liu, Kaizhao Wang, Zihao Wu, Lei |
| author_facet | Liu, Kaizhao Wang, Zihao Wu, Lei |
| contents | In this paper, we present a fine-grained analysis of the local landscape of phase retrieval under the regime of limited samples. Specifically, we aim to ascertain the minimal sample size required to guarantee a benign local landscape surrounding global minima in high dimensions. Let $n$ and $d$ denote the sample size and input dimension, respectively. We first explore the local convexity and establish that when $n=o(d\log d)$, for almost every fixed point in the local ball, the Hessian matrix has negative eigenvalues, provided $d$ is sufficiently large. % Consequently, the local landscape is highly non-convex. We next consider the one-point convexity and show that, as long as $n=ω(d)$, with high probability, the landscape is one-point strongly convex in the local annulus: $\{w\in\mathbb{R}^d: o_d(1)\leqslant \|w-w^*\|\leqslant c\}$, where $w^*$ is the ground truth and $c$ is an absolute constant. This implies that gradient descent, initialized from any point in this domain, can converge to an $o_d(1)$-loss solution exponentially fast. Furthermore, we show that when $n=o(d\log d)$, there is a radius of $\widetildeΘ\left(\sqrt{1/d}\right)$ such that one-point convexity breaks down in the corresponding smaller local ball. This indicates an impossibility of establishing a convergence to the exact $w^*$ for gradient descent under limited samples by relying solely on one-point convexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15221 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Local Landscape of Phase Retrieval Under Limited Samples Liu, Kaizhao Wang, Zihao Wu, Lei Information Theory Machine Learning Signal Processing Optimization and Control Statistics Theory In this paper, we present a fine-grained analysis of the local landscape of phase retrieval under the regime of limited samples. Specifically, we aim to ascertain the minimal sample size required to guarantee a benign local landscape surrounding global minima in high dimensions. Let $n$ and $d$ denote the sample size and input dimension, respectively. We first explore the local convexity and establish that when $n=o(d\log d)$, for almost every fixed point in the local ball, the Hessian matrix has negative eigenvalues, provided $d$ is sufficiently large. % Consequently, the local landscape is highly non-convex. We next consider the one-point convexity and show that, as long as $n=ω(d)$, with high probability, the landscape is one-point strongly convex in the local annulus: $\{w\in\mathbb{R}^d: o_d(1)\leqslant \|w-w^*\|\leqslant c\}$, where $w^*$ is the ground truth and $c$ is an absolute constant. This implies that gradient descent, initialized from any point in this domain, can converge to an $o_d(1)$-loss solution exponentially fast. Furthermore, we show that when $n=o(d\log d)$, there is a radius of $\widetildeΘ\left(\sqrt{1/d}\right)$ such that one-point convexity breaks down in the corresponding smaller local ball. This indicates an impossibility of establishing a convergence to the exact $w^*$ for gradient descent under limited samples by relying solely on one-point convexity. |
| title | The Local Landscape of Phase Retrieval Under Limited Samples |
| topic | Information Theory Machine Learning Signal Processing Optimization and Control Statistics Theory |
| url | https://arxiv.org/abs/2311.15221 |