Bootstrap is a popular methodology for simulating input uncertainty. However, it can be computationally expensive when the number of samples is large. We propose a new approach called Orthogonal Bootstrap that reduces the number of required Monte Carlo replications. We decomposes the target being simulated into two parts: the non-orthogonal part which has a closed-form result known as Infinitesimal Jackknife and the orthogonal part which is easier to be simulated. We theoretically and numerically show that Orthogonal Bootstrap significantly reduces the computational cost of Bootstrap while improving empirical accuracy and maintaining the same width of the constructed interval.

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. We next consider the one-point convexity and show that, as long as$n=\omega (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 {\Theta } \left ({{\sqrt {1/d}}}\right)$such that one-point convexity breaks down in the corresponding smaller local ball. This indicates an impossibility to establish a convergence to the exact$w^{*}$for gradient descent under limited samples by relying solely on one-point convexity.