2023/11/26 by Liu, Kaizhao, Wang, Zihao, Wu, Lei · 2 citations
#FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Signal Processing (eess.SP) #Statistics Theory (math.ST) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.2311.15221
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(dlog 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∈ℝd: od(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 od(1)-loss solution exponentially fast. Furthermore, we show that when n=o(dlog d), there is a radius of \widetildeΘ(√(1/d)) 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.