Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
Cong Ma, Kaizheng Wang, Yuejie Chi, Yuxin Chen
Introduction
A wide spectrum of science and engineering applications call for solutions to a nonlinear system of equations. Imagine we have collected a set of data points , generated by a nonlinear sensing system,
where is the unknown object of interest, and the ’s are certain nonlinear maps known a priori. Can we reconstruct the underlying object in a faithful yet efficient manner? Problems of this kind abound in information and statistical science, prominent examples including low-rank matrix recovery [KMO10a, CR09], robust principal component analysis [CSPW11, CLMW11], phase retrieval [CSV13, JEH15], neural networks [SJL19, ZSJ+17], to name just a few.
In principle, it is possible to attempt reconstruction by searching for a solution that minimizes the empirical loss, namely,
Unfortunately, this empirical loss minimization problem is, in many cases, nonconvex, making it NP-hard in general. This issue of non-convexity comes up in, for example, several representative problems that epitomize the structures of nonlinear systems encountered in practice.Here, we choose different pre-constants in front of the empirical loss in order to be consistent with the literature of the respective problems. In addition, we only introduce the problem in the noiseless case for simplicity of presentation.
where are the known design vectors. One strategy is thus to solve the following problem
within some index subset of cardinality . These entries can be viewed as nonlinear measurements about the low-rank factor . The task of completing the true matrix can then be cast as solving
2 Nonconvex optimization via regularized gradient descent
First-order methods have been a popular heuristic in practice for solving nonconvex problems including (1). For instance, a widely adopted procedure is gradient descent, which follows the update rule
where is the learning rate (or step size) and is some proper initial guess. Given that it only performs a single gradient calculation per iteration (which typically can be completed within near-linear time), this paradigm emerges as a candidate for solving large-scale problems. The concern is: whether converges to the global solution and, if so, how long it takes for convergence, especially since (1) is highly nonconvex.
Fortunately, despite the worst-case hardness, appealing convergence properties have been discovered in various statistical estimation problems; the blessing being that the statistical models help rule out ill-behaved instances. For the average case, the empirical loss often enjoys benign geometry, in a local region (or at least along certain directions) surrounding the global optimum. In light of this, an effective nonconvex iterative method typically consists of two stages:
a carefully-designed initialization scheme (e.g. spectral method);
an iterative refinement procedure (e.g. gradient descent).
This strategy has recently spurred a great deal of interest, owing to its promise of achieving computational efficiency and statistical accuracy at once for a growing list of problems (e.g. [KMO10a, JNS13, CW15, SL16, CLS15, CC17, LLSW18, LLB17]). However, rather than directly applying gradient descent (4), existing theory often suggests enforcing proper regularization. Such explicit regularization enables improved computational convergence by properly “stabilizing” the search directions. The following regularization schemes, among others, have been suggested to obtain or improve computational guarantees. We refer to these algorithms collectively as Regularized Gradient Descent.
Trimming / truncation, which discards/truncates a subset of the gradient components when forming the descent direction. For instance, when solving quadratic systems of equations, one can modify the gradient descent update rule as
where is an operator that effectively drops samples bearing too much influence on the search direction. This strategy [CC17, ZCL16, WGE17] has been shown to enable exact recovery with linear-time computational complexity and optimal sample complexity.
Regularized loss, which attempts to optimize a regularized empirical risk
Projection, which projects the iterates onto certain sets based on prior knowledge, that is,
where is a certain projection operator used to enforce, for example, incoherence properties. This strategy has been employed in both low-rank matrix completion [CW15, ZL16] and blind deconvolution [LLSW18].
Equipped with such regularization procedures, existing works uncover appealing computational and statistical properties under various statistical models. Table 1 summarizes the performance guarantees derived in the prior literature; for simplicity, only orderwise results are provided.
There is another role of regularization commonly studied in the literature, which exploits prior knowledge about the structure of the unknown object, such as sparsity to prevent overfitting and improve statistical generalization ability. This is, however, not the focal point of this paper, since we are primarily pursuing solutions to (1) without imposing additional structures.
3 Regularization-free procedures?
The regularized gradient descent algorithms, while exhibiting appealing performance, usually introduce more algorithmic parameters that need to be carefully tuned based on the assumed statistical models. In contrast, vanilla gradient descent (cf. (4)) — which is perhaps the very first method that comes into mind and requires minimal tuning parameters — is far less understood (cf. Table 1). Take matrix completion and blind deconvolution as examples: to the best of our knowledge, there is currently no theoretical guarantee derived for vanilla gradient descent.
The situation is better for phase retrieval: the local convergence of vanilla gradient descent, also known as Wirtinger flow (WF), has been investigated in [CLS15, SWW17]. Under i.i.d. Gaussian design and with near-optimal sample complexity, WF (combined with spectral initialization) provably achieves -accuracy (in a relative sense) within O\big{(}n\log\left({1}/{\varepsilon}\right)\big{)} iterations. Nevertheless, the computational guarantee is significantly outperformed by the regularized version (called truncated Wirtinger flow [CC17]), which only requires O\big{(}\log\left({1}/{\varepsilon}\right)\big{)} iterations to converge with similar per-iteration cost. On closer inspection, the high computational cost of WF is largely due to the vanishingly small step size \eta_{t}=O\big{(}{1}/({n\|\bm{x}^{\star}\|_{2}^{2}})\big{)} — and hence slow movement — suggested by the theory [CLS15]. While this is already the largest possible step size allowed in the theory published in [CLS15], it is considerably more conservative than the choice \eta_{t}=O\big{(}{1}/{\|\bm{x}^{\star}\|_{2}^{2}}\big{)} theoretically justified for the regularized version [CC17, ZCL16].
The lack of understanding and suboptimal results about vanilla gradient descent raise a very natural question: are regularization-free iterative algorithms inherently suboptimal when solving nonconvex statistical estimation problems of this kind?
4 Numerical surprise of unregularized gradient descent
To answer the preceding question, it is perhaps best to first collect some numerical evidence. In what follows, we test the performance of vanilla gradient descent for phase retrieval, matrix completion, and blind deconvolution, using a constant step size. For all of these experiments, the initial guess is obtained by means of the standard spectral method. Our numerical findings are as follows:
In all of these numerical experiments, vanilla gradient descent enjoys remarkable linear convergence, always yielding an accuracy of (in a relative sense) within around 200 iterations. In particular, for the phase retrieval problem, the step size is taken to be although we vary the problem size from to . The consequence is that the convergence rates experience little changes when the problem sizes vary. In comparison, the theory published in [CLS15] seems overly pessimistic, as it suggests a diminishing step size inversely proportional to and, as a result, an iteration complexity that worsens as the problem size grows.
In short, the above empirical results are surprisingly positive yet puzzling. Why was the computational efficiency of vanilla gradient descent unexplained or substantially underestimated in prior theory?
5 This paper
The main contribution of this paper is towards demystifying the “unreasonable” effectiveness of regularization-free nonconvex iterative methods. As asserted in previous work, regularized gradient descent succeeds by properly enforcing/promoting certain incoherence conditions throughout the execution of the algorithm. In contrast, we discover that
Vanilla gradient descent automatically forces the iterates to stay incoherent with the measurement mechanism, thus implicitly regularizing the search directions.
This “implicit regularization” phenomenon is of fundamental importance, suggesting that vanilla gradient descent proceeds as if it were properly regularized. This explains the remarkably favorable performance of unregularized gradient descent in practice. Focusing on the three representative problems mentioned in Section 1.1, our theory guarantees both statistical and computational efficiency of vanilla gradient descent under random designs and spectral initialization. With near-optimal sample complexity, to attain -accuracy,
Phase retrieval (informal): vanilla gradient descent converges in O\big{(}\log n\log\frac{1}{\epsilon}\big{)} iterations;
Matrix completion (informal): vanilla gradient descent converges in O\big{(}\log\frac{1}{\epsilon}\big{)} iterations;
Blind deconvolution (informal): vanilla gradient descent converges in O\big{(}\log\frac{1}{\epsilon}\big{)} iterations.
In words, gradient descent provably achieves (nearly) linear convergence in all of these examples. Throughout this paper, an algorithm is said to converge (nearly) linearly to in the noiseless case if the iterates obey
As a byproduct of our theory, gradient descent also provably controls the entrywise empirical risk uniformly across all iterations; for instance, this implies that vanilla gradient descent controls entrywise estimation error for the matrix completion task. Precise statements of these results are deferred to Section 3 and are briefly summarized in Table 2.
Notably, our study of implicit regularization suggests that the behavior of nonconvex optimization algorithms for statistical estimation needs to be examined in the context of statistical models, which induces an objective function as a finite sum. Our proof is accomplished via a leave-one-out perturbation argument, which is inherently tied to statistical models and leverages homogeneity across samples. Altogether, this allows us to localize benign landscapes for optimization and characterize finer dynamics not accounted for in generic gradient descent theory.
6 Notations
Additionally, the standard notation or means that there exists a constant such that , means that there exists a constant such that , and means that there exist constants such that . Also, means that there exists some large enough constant such that . Similarly, means that there exists some sufficiently small constant such that .
Implicit regularization – a case study
To reveal reasons behind the effectiveness of vanilla gradient descent, we first examine existing theory of gradient descent and identify the geometric properties that enable linear convergence. We then develop an understanding as to why prior theory is conservative, and describe the phenomenon of implicit regularization that helps explain the effectiveness of vanilla gradient descent. To facilitate discussion, we will use the problem of solving random quadratic systems (phase retrieval) and Wirtinger flow as a case study, but our diagnosis applies more generally, as will be seen in later sections.
In the convex optimization literature, there are two standard conditions about the objective function — strong convexity and smoothness — that allow for linear convergence of gradient descent.
as long as the step size is chosen as . Here, denotes the global minimum. This immediately reveals the iteration complexity for gradient descent: the number of iterations taken to attain -accuracy (in a relative sense) is bounded by
In other words, the iteration complexity is dictated by and scales linearly with the condition number — the ratio of smoothness to strong convexity parameters.
Moving beyond convex optimization, one can easily extend the above theory to nonconvex problems with local strong convexity and smoothness. More precisely, suppose the objective function satisfies
Then the contraction result (8) continues to hold, as long as the algorithm is seeded with an initial point that falls inside .
2 Local geometry for solving random quadratic systems
Population-level analysis. Consider the case with an infinite number of equations or samples, i.e. , where converges to its expectation. Simple calculation yields that
It it straightforward to verify that for any sufficiently small constant , one has the crude bound
meaning that is -strongly convex and -smooth within a local ball around . As a consequence, when we have infinite samples and an initial guess such that \|\bm{x}^{0}-\bm{x}^{\star}\|_{2}\leq\delta\big{\|}\bm{x}^{\star}\big{\|}_{2}, vanilla gradient descent with a constant step size converges to the global minimum within logarithmic iterations.
Finite-sample regime with . Now that exhibits favorable landscape in the population level, one thus hopes that the fluctuation can be well-controlled so that the nice geometry carries over to the finite-sample regime. In the regime where (which is the regime considered in [CLS15]), the local strong convexity is still preserved, in the sense that
occurs with high probability, provided that is sufficiently small (see [Sol14, SWW17] and Lemma 1). The smoothness parameter, however, is not well-controlled. In fact, it can be as large as (up to logarithmic factors)To demonstrate this, take in (10), one can easily verify that, with high probability, \big{\|}\nabla^{2}f(\bm{x})\big{\|}\geq\left|3(\bm{a}_{1}^{\top}\bm{x})^{2}-y_{1}\right|\big{\|}\bm{a}_{1}\bm{a}_{1}^{\top}\big{\|}/m-O(1)\gtrsim{\delta^{2}n^{2}}/{m}\asymp\delta^{2}{n}/{\log n}.
and, as a consequence, a high iteration complexity O\big{(}n\log(1/{\epsilon})\big{)}. This underpins the analysis in [CLS15].
Notably, due to Gaussian designs, the phase retrieval problem enjoys more favorable geometry compared to other nonconvex problems. In matrix completion and blind deconvolution, the Hessian matrices are rank-deficient even at the population level. In such cases, the above discussions need to be adjusted, e.g. strong convexity is only possible when we restrict attention to certain directions.
3 Which region enjoys nicer geometry?
where is some small numerical constant. As will be formalized in Lemma 1, with high probability the Hessian matrix satisfies
simultaneously for in the RIC. In words, the Hessian matrix is nearly well-conditioned (with the condition number bounded by ), as long as (i) the iterate is not very far from the global minimizer (cf. (11a)), and (ii) the iterate remains incoherentIf is aligned with (and hence very coherent with) one vector , then with high probability one has \big{|}\bm{a}_{j}^{\top}\big{(}\bm{x}-\bm{x}^{\star}\big{)}|\gtrsim\big{|}\bm{a}_{j}^{\top}\bm{x}|\asymp\sqrt{n}\|\bm{x}\|_{2}, which is significantly larger than . with respect to the sensing vectors (cf. (11b)). Another way to interpret the incoherence condition (11b) is that the empirical risk needs to be well-controlled uniformly across all samples. See Figure 3(a) for an illustration of the above region.
4 Implicit regularization
However, is regularization really necessary for the iterates to stay within the RIC? To answer this question, we plot in Figure 4(a) (resp. Figure 4(b)) the incoherence measure (resp. ) vs. the iteration count in a typical Monte Carlo trial, generated in the same way as for Figure 1(a). Interestingly, the incoherence measure remains bounded by for all iterations . This important observation suggests that one may adopt a substantially more aggressive step size throughout the whole algorithm.
The main objective of this paper is thus to provide a theoretical validation of the above empirical observation. As we will demonstrate shortly, with high probability all iterates along the execution of the algorithm (as well as the spectral initialization) are provably constrained within the RIC, implying fast convergence of vanilla gradient descent (cf. Figure 3(c)). The fact that the iterates stay incoherent with the measurement mechanism automatically, without explicit enforcement, is termed “implicit regularization”.
5 A glimpse of the analysis: a leave-one-out trick
In order to rigorously establish (11b) for all iterates, the current paper develops a powerful mechanism based on the leave-one-out perturbation argument, a trick rooted and widely used in probability and random matrix theory. Note that the iterate is statistically dependent with the design vectors . Under such circumstances, one often resorts to generic bounds like the Cauchy-Schwarz inequality, which would not yield a desirable estimate. To address this issue, we introduce a sequence of auxiliary iterates for each (for analytical purposes only), obtained by running vanilla gradient descent using all but the th sample. As one can expect, such auxiliary trajectories serve as extremely good surrogates of in the sense that
since their constructions only differ by a single sample. Most importantly, since is independent with the th design vector, it is much easier to control its incoherence w.r.t. to the desired level:
Combining (12) and (13) then leads to (11b). See Figure 5 for a graphical illustration of this argument. Notably, this technique is very general and applicable to many other problems. We invite the readers to Section 5 for more details.
Main results
This section formalizes the implicit regularization phenomenon underlying unregularized gradient descent, and presents its consequences, namely near-optimal statistical and computational guarantees for phase retrieval, matrix completion, and blind deconvolution. Note that the discrepancy measure may vary from problem to problem.
The Wirtinger flow (WF) algorithm, first introduced in [CLS15], is a combination of spectral initialization and vanilla gradient descent; see Algorithm 1.
Our finding is summarized in the following theorem.
Theorem 1 reveals a few intriguing properties of Algorithm 1.
Implicit regularization: Theorem 1 asserts that the incoherence properties are satisfied throughout the execution of the algorithm (see (19b)), which formally justifies the implicit regularization feature we hypothesized.
Near-constant step size: Consider the case where . Theorem 1 establishes near-linear convergence of WF with a substantially more aggressive step size . Compared with the choice admissible in [CLS15, Theorem 3.3], Theorem 1 allows WF / GD to attain -accuracy within iterations. The resulting computational complexity of the algorithm is
which significantly improves upon the result O\big{(}mn^{2}\log\left({1}/{\epsilon}\right)\big{)} derived in [CLS15]. As a side note, if the sample size further increases to , then a constant step size is also feasible, resulting in an iteration complexity . This follows since with high probability, the entire trajectory resides within a more refined incoherence region \max_{j}\big{|}\bm{a}_{j}^{\top}\big{(}\bm{x}^{t}-\bm{x}^{\star}\big{)}\big{|}\lesssim\|\bm{x}^{\star}\|_{2}. We omit the details here.
As it turns out, a carefully designed initialization is not pivotal in enabling fast convergence. In fact, randomly initialized gradient descent provably attains -accuracy in iterations; see [CCFM19] for details.
2 Low-rank matrix completion
Consider a random sampling model such that each entry of is observed independently with probability , i.e. for ,
where the entries of are independent sub-Gaussian noise with sub-Gaussian norm (see [Ver12, Definition 5.7]). We denote by the set of locations being sampled, and represents the projection of onto the set of matrices supported in . We note here that the sampling rate , if not known, can be faithfully estimated by the sample proportion .
To fix ideas, we consider the following nonconvex optimization problem
The vanilla gradient descent algorithm (with spectral initialization) is summarized in Algorithm 2.
Before proceeding to the main theorem, we first introduce a standard incoherence parameter required for matrix completion [CR09].
A rank- matrix with eigendecomposition is said to be -incoherent if
In addition, recognizing that is identifiable only up to orthogonal transformation, we define the optimal transform from the th iterate to as
where is the set of orthonormal matrices. With these definitions in place, we have the following theorem.
Let be a rank , -incoherent PSD matrix, and its condition number is a fixed constant. Suppose the sample size satisfies for some sufficiently large constant , and the noise satisfies
With probability at least , the iterates of Algorithm 2 satisfy
for all , where , , , , and are some absolute positive constants and , provided that .
Theorem 2 provides the first theoretical guarantee of unregularized gradient descent for matrix completion, demonstrating near-optimal statistical accuracy and computational complexity.
Near-minimal Euclidean error: In view of (28a), as increases, the Euclidean error of vanilla GD converges to
which coincides with the theoretical guarantee in [CW15, Corollary 1] and matches the minimax lower bound established in [NW12, KLT11].
where the last line follows from (28b) as well as the facts that and . Compared with the Euclidean loss (29), this implies that when , the entrywise error of is uniformly spread out across all entries. As far as we know, this is the first result that reveals near-optimal entrywise error control for noisy matrix completion using nonconvex optimization, without resorting to sample splitting.
Theorem 2 remains valid if the total number of iterations obeys . In the noiseless case where , the theory allows arbitrarily large .
Finally, we report the empirical statistical accuracy of vanilla gradient descent in the presence of noise. Figure 6 displays the squared relative error of vanilla gradient descent as a function of the signal-to-noise ratio (SNR), where the SNR is defined to be
3 Blind deconvolution
Suppose we have collected bilinear measurements
The (Wirtinger) gradient descent algorithm (with spectral initialization) is summarized in Algorithm 3; here, and stand for the Wirtinger gradient and are given in (77) and (78), respectively; see [CLS15, Section 6] for a brief introduction to Wirtinger calculus.
In light of this, we will measure the discrepancy between
Before proceeding, we need to introduce the incoherence parameter [ARR14, LLSW18], which is crucial for blind deconvolution, whose role is similar to the incoherence parameter (cf. Definition 3) in matrix completion.
Let the incoherence parameter of be the smallest number such that
The incoherence parameter describes the spectral flatness of the signal . With this definition in place, we have the following theorem, where for identifiability we assume that .
Suppose the number of measurements obeys for some sufficiently large constant , and suppose the step size is taken to be some sufficiently small constant. Then there exist constants such that with probability exceeding , the iterates in Algorithm 3 satisfy
for all . Here, we denote as the alignment parameter,
Theorem 3 provides the first theoretical guarantee of unregularized gradient descent for blind deconvolution at a near-optimal statistical and computational complexity. A few remarks are in order.
Implicit regularization: Theorem 3 reveals that the unregularized gradient descent iterates remain incoherent with the sampling mechanism (see (37b) and (37c)). Recall that prior works operate upon a regularized cost function with an additional penalty term that regularizes the global scaling and the incoherence [LLSW18, HH18, LS18]. In comparison, our theorem implies that it is unnecessary to regularize either the incoherence or the scaling ambiguity, which is somewhat surprising. This justifies the use of regularization-free (Wirtinger) gradient descent for blind deconvolution.
Constant step size: Compared to the step size suggested in [LLSW18] for regularized gradient descent, our theory admits a substantially more aggressive step size (i.e. ) even without regularization. Similar to phase retrieval, the computational efficiency is boosted by a factor of , attaining -accuracy within iterations (vs. iterations in prior theory).
Incoherence of spectral initialization: As in phase retrieval, Theorem 3 demonstrates that the estimates returned by the spectral method are incoherent with respect to both and . In contrast, [LLSW18] recommends a projection operation (via a linear program) to enforce incoherence of the initial estimates, which is dispensable according to our theory.
Related work
Solving nonlinear systems of equations has received much attention in the past decade. Rather than directly attacking the nonconvex formulation, convex relaxation lifts the object of interest into a higher dimensional space and then attempts recovery via semidefinite programming (e.g. [RFP10, CSV13, CR09, ARR14]). This has enjoyed great success in both theory and practice. Despite appealing statistical guarantees, semidefinite programming is in general prohibitively expensive when processing large-scale datasets.
Nonconvex approaches, on the other end, have been under extensive study in the last few years, due to their computational advantages. There is a growing list of statistical estimation problems for which nonconvex approaches are guaranteed to find global optimal solutions, including but not limited to phase retrieval [NJS13, CLS15, CC17], low-rank matrix sensing and completion [TBS+16, BNS16, CW15, ZL15, GLM16], blind deconvolution and self-calibration [LLSW18, LS18, LLB17, LLJB17], dictionary learning [SQW17], tensor decomposition [GM17], joint alignment [CC18], learning shallow neural networks [SJL19, ZSJ+17], robust subspace learning [NNS+14, MZL19, LM17, CJN17]. In several problems [SQW16, SQW17, GM17, GLM16, LWL+16, LT17, MBM18, MZL19, DDP17], it is further suggested that the optimization landscape is benign under sufficiently large sample complexity, in the sense that all local minima are globally optimal, and hence nonconvex iterative algorithms become promising in solving such problems. See [CLC18] for a recent overview. Below we review the three problems studied in this paper in more details. Some state-of-the-art results are summarized in Table 1.
Phase retrieval. Candès et al. proposed PhaseLift [CSV13] to solve the quadratic systems of equations based on convex programming. Specifically, it lifts the decision variable into a rank-one matrix and translates the quadratic constraints of in (14) into linear constraints of . By dropping the rank constraint, the problem becomes convex [CSV13, CL14, CCG15, CZ15, Tro15a]. Another convex program PhaseMax [GS18, BR17, HV18, DTL17] operates in the natural parameter space via linear programming, provided that an anchor vector is available. On the other hand, alternating minimization [NJS13] with sample splitting has been shown to enjoy much better computational guarantee. In contrast, Wirtinger Flow [CLS15] provides the first global convergence result for nonconvex methods without sample splitting, whose statistical and computational guarantees are later improved by [CC17] via an adaptive truncation strategy. Several other variants of WF are also proposed [CLM16, KÖ16, Sol19], among which an amplitude-based loss function has been investigated [WGE17, ZZLC17, WZG+18, WGSC17]. In particular, [ZZLC17] demonstrates that the amplitude-based loss function has a better curvature, and vanilla gradient descent can indeed converge with a constant step size at the order-wise optimal sample complexity. A small sample of other nonconvex phase retrieval methods include [SBE14, SR15, CL16, CFL15, DR18, GX16, Wei15, BEB17, TV18, CLW19, QZEW17], which are beyond the scope of this paper.
Matrix completion. Nuclear norm minimization was studied in [CR09] as a convex relaxation paradigm to solve the matrix completion problem. Under certain incoherence conditions imposed upon the ground truth matrix, exact recovery is guaranteed under near-optimal sample complexity [CT10, Gro11, Rec11, Che15, DR16]. Concurrently, several works [KMO10a, KMO10b, LB10, JNS13, HW14, HMLZ15, ZWL15, JN15, TW16, JKN16, WCCL16, ZWL15] tackled the matrix completion problem via nonconvex approaches. In particular, the seminal work by Keshavan et al. [KMO10a, KMO10b] pioneered the two-stage approach that is widely adopted by later works. Sun and Luo [SL16] demonstrated the convergence of gradient descent type methods for noiseless matrix completion with a regularized nonconvex loss function. Instead of penalizing the loss function, [CW15, ZL16] employed projection to enforce the incoherence condition throughout the execution of the algorithm. To the best of our knowledge, no rigorous guarantees have been established for matrix completion without explicit regularization. A notable exception is [JKN16], which uses unregularized stochastic gradient descent for matrix completion in the online setting. However, the analysis is performed with fresh samples in each iteration. Our work closes the gap and makes the first contribution towards understanding implicit regularization in gradient descent without sample splitting. In addition, entrywise eigenvector perturbation has been studied by [JN15, AFWZ17, CCF18] in order to analyze the spectral algorithms for matrix completion, which helps us establish theoretical guarantees for the spectral initialization step. Finally, it has recently been shown that the analysis of nonconvex gradient descent in turn yields near-optimal statistical guarantees for convex relaxation in the context of noisy matrix completion; see [CCF+19, CFMY19].
Blind deconvolution. In [ARR14], Ahmed et al. first proposed to invoke similar lifting ideas for blind deconvolution, which translates the bilinear measurements (31) into a system of linear measurements of a rank-one matrix . Near-optimal performance guarantees have been established for convex relaxation [ARR14]. Under the same model, Li et al. [LLSW18] proposed a regularized gradient descent algorithm that directly optimizes the nonconvex loss function (32) with a few regularization terms that account for scaling ambiguity and incoherence. In [HH18], a Riemannian steepest descent method is developed that removes the regularization for scaling ambiguity, although they still need to regularize for incoherence. In [AAHJ19], a linear program is proposed but requires exact knowledge of the signs of the signals. Blind deconvolution has also been studied for other models – interested readers may refer to [Chi16, LS18, LLJB17, LS15, LTR18, ZLK+17, WC16].
On the other hand, our analysis framework is based on a leave-one-out perturbation argument. This technique has been widely used to analyze high-dimensional problems with random designs, including but not limited to robust M-estimation [EKBB+13, EK15], statistical inference for sparse regression [JM18], likelihood ratio test in logistic regression [SCC17], phase synchronization [ZB18, AFWZ17], ranking from pairwise comparisons [CFMW19], community recovery [AFWZ17], and covariance sketching [LMCC18]. In particular, this technique results in tight performance guarantees for the generalized power method [ZB18], the spectral method [AFWZ17, CFMW19], and convex programming approaches [EK15, ZB18, SCC17, CFMW19], however it has not been applied to analyze nonconvex optimization algorithms.
Finally, we note that the notion of implicit regularization — broadly defined — arises in settings far beyond the models and algorithms considered herein. For instance, it has been conjectured that in matrix factorization, over-parameterized stochastic gradient descent effectively enforces certain norm constraints, allowing it to converge to a minimal-norm solution as long as it starts from the origin [GWB+17]. The stochastic gradient methods have also been shown to implicitly enforce Tikhonov regularization in several statistical learning settings [LCR16]. More broadly, this phenomenon seems crucial in enabling efficient training of deep neural networks [ZBH+17, SHN+18].
A general recipe for trajectory analysis
In this section, we sketch a general recipe for establishing performance guarantees of gradient descent, which conveys the key idea for proving the main results of this paper. The main challenge is to demonstrate that appropriate incoherence conditions are preserved throughout the trajectory of the algorithm. This requires exploiting statistical independence of the samples in a careful manner, in conjunction with generic optimization theory. Central to our approach is a leave-one-out perturbation argument, which allows to decouple the statistical dependency while controlling the component-wise incoherence measures.
General Recipe (a leave-one-out analysis) Step 1: characterize restricted strong convexity and smoothness of , and identify the region of incoherence and contraction (RIC). Step 2: introduce leave-one-out sequences and for each , where (resp. ) is independent of any sample involving (resp. ); Step 3: establish the incoherence condition for and via induction. Suppose the iterates satisfy the claimed conditions in the th iteration: (a) show, via restricted strong convexity, that the true iterates and the leave-one-out version are exceedingly close; (b) use statistical independence to show that (resp. ) is incoherent w.r.t. (resp. ), namely, and are both well-controlled; (c) combine the bounds to establish the desired incoherence condition concerning and .
Consider the following problem where the samples are collected in a bilinear/quadratic form as
For this setting, the empirical loss function is given by
where we denote . To minimize , we proceed with vanilla gradient descent
following a standard spectral initialization, where is the step size. As a remark, for complex-valued problems, the gradient (resp. Hessian) should be understood as the Wirtinger gradient (resp. Hessian).
It is clear from (39) that can only be recovered up to certain global ambiguity. For clarity of presentation, we assume in this section that such ambiguity has already been taken care of via proper global transformation.
2 Outline of the recipe
We are now positioned to outline the general recipe, which entails the following steps.
Step 1: characterizing local geometry in the RIC. Our first step is to characterize a region — which we term as the region of incoherence and contraction (RIC) — such that the Hessian matrix obeys strong convexity and smoothness,
or at least along certain directions (i.e. restricted strong convexity and smoothness), where scales slowly (or even remains bounded) with the problem size. As revealed by optimization theory, this geometric property (40) immediately implies linear convergence with the contraction rate for a properly chosen step size , as long as all iterates stay within the RIC.
In the three examples, the above incoherence condition translates to:
Phase retrieval: \max_{j}{\big{|}\bm{a}_{j}^{\top}(\bm{x}-\bm{x}^{\star})\big{|}} is well-controlled;
Matrix completion: \big{\|}\bm{X}-\bm{X}^{\star}\big{\|}_{2,\infty} is well-controlled;
Blind deconvolution: \max_{j}{\big{|}\bm{a}_{j}^{\top}(\bm{x}-\bm{x}^{\star})\big{|}} and \max_{j}{\big{|}\bm{b}_{j}^{\top}(\bm{h}-\bm{h}^{\star})\big{|}} are well-controlled.
Step 2: introducing the leave-one-out sequences. To justify that no iterates leave the RIC, we rely on the construction of auxiliary sequences. Specifically, for each , produce an auxiliary sequence such that (resp. ) is independent of any sample involving (resp. ). As an example, suppose that the ’s and the ’s are independently and randomly generated. Then for each , one can consider a leave-one-out loss function
that discards the th sample. One further generates by running vanilla gradient descent w.r.t. this auxiliary loss function, with a spectral initialization that similarly discards the th sample. Note that this procedure is only introduced to facilitate analysis and is never implemented in practice.
Step 3: establishing the incoherence condition. We are now ready to establish the incoherence condition with the assistance of the auxiliary sequences. Usually the proof proceeds by induction, where our goal is to show that the next iterate remains within the RIC, given that the current one does.
Step 3(a): proximity between the original and the leave-one-out iterates. As one can anticipate, and remain “glued” to each other along the whole trajectory, since their constructions differ by only a single sample. In fact, as long as the initial estimates stay sufficiently close, their gaps will never explode. To intuitively see why, use the fact to discover that
Indeed, (restricted) strong convexity is crucial in controlling the size of leave-one-out perturbations.
Step 3(b): incoherence condition of the leave-one-out iterates. The fact that and are exceedingly close motivates us to control the incoherence of instead, for . By construction, (resp. ) is statistically independent of any sample involving the design vector (resp. ), a fact that typically leads to a more friendly analysis for controlling \left\|\bm{\phi}_{l}^{\mathsf{H}}\big{(}\bm{X}^{t+1,(l)}-\bm{X}^{\star}\big{)}\right\|_{2} and \left\|\bm{\psi}_{l}^{\mathsf{H}}\big{(}\bm{H}^{t+1,(l)}-\bm{H}^{\star}\big{)}\right\|_{2}.
Step 3(c): combining the bounds. With these results in place, apply the triangle inequality to obtain
where the first term is controlled in Step 3(a) and the second term is controlled in Step 3(b). The term \big{\|}\bm{\psi}_{l}^{\mathsf{H}}\big{(}\bm{H}^{t+1}-\bm{H}^{\star}\big{)}\big{\|}_{2} can be bounded similarly. By choosing the bounds properly, this establishes the incoherence condition for all as desired.
Analysis for phase retrieval
In this section, we instantiate the general recipe presented in Section 5 to phase retrieval and prove Theorem 1. Similar to the Section 7.1 in [CLS15], we are going to use instead of as the step size for analysis. This is because with high probability, and are rather close in the relative sense. Without loss of generality, we assume throughout this section that \big{\|}\bm{x}^{\star}\big{\|}_{2}=1 and
In addition, the gradient and the Hessian of for this problem (see (15)) are given respectively by
We start by characterizing the region that enjoys both strong convexity and the desired level of smoothness. This is supplied in the following lemma, which plays a crucial role in the subsequent analysis.
Fix any sufficiently small constant and any sufficiently large constant , and suppose the sample complexity obeys for some sufficiently large constant . With probability at least ,
In words, Lemma 1 reveals that the Hessian matrix is positive definite and (almost) well-conditioned, if one restricts attention to the set of points that are (i) not far away from the truth (cf. (45a)) and (ii) incoherent with respect to the measurement vectors (cf. (45b)).
1.2 Error contraction
There exists an event that does not depend on and has probability , such that when it happens and obeys the conditions (45), one has
provided that the step size satisfies .
With the help of Lemma 2, we can turn the proof of Theorem 1 into ensuring that the trajectory lies in the RIC specified by (47).Here, we deliberately change in (45a) to in the definition of the RIC (47a) to ensure the correctness of the analysis. This is formally stated in the next lemma.
Suppose for all , the trajectory falls within the region of incoherence and contraction (termed the RIC), namely,
2 Step 2: introducing the leave-one-out sequences
To be precise, for each , we define the leave-one-out empirical loss function as
and the auxiliary trajectory is constructed by running WF w.r.t. . In addition, the spectral initialization is computed based on the rescaled leading eigenvector of the leave-one-out data matrix
Clearly, the entire sequence is independent of the th sampling vector . This auxiliary procedure is formally described in Algorithm 4.
3 Step 3: establishing the incoherence condition by induction
As revealed by Lemma 3, it suffices to prove that the iterates satisfies (47) with high probability. Our proof will be inductive in nature. For the sake of clarity, we list all the induction hypotheses:
Here is some universal constant. For any , define to be the event where the conditions in (51) hold for the -th iteration. According to Lemma 2, there exists some event with probability such that on one has
This subsection is devoted to establishing (51b) and (51c) for the th iteration, assuming that (51) holds true up to the th iteration. We defer the justification of the base case (i.e. initialization at ) to Section 6.4.
Step 3(a): proximity between the original and the leave-one-out iterates. The leave-one-out sequence behaves similarly to the true WF iterates while maintaining statistical independence with , a key fact that allows us to control the incoherence of th leave-one-out sequence w.r.t. . We will formally quantify the gap between and in the following lemma, which establishes the induction in (51b).
The proof relies heavily on the restricted strong convexity (see Lemma 1) and is deferred to Appendix A.4. ∎
holds for some constant and sufficiently large. Here, (i) comes from the triangle inequality, and (ii) arises from the proximity bound (53) and the condition (52).
Step 3(c): combining the bounds. We are now prepared to establish (51c) for the ()th iteration. Specifically,
Using mathematical induction and the union bound, we establish (51) for all with high probability. This in turn concludes the proof of Theorem 1, as long as the hypotheses are valid for the base case.
4 The base case: spectral initialization
In the end, we return to verify the induction hypotheses for the base case (), i.e. the spectral initialization obeys (51). The following lemma justifies (51a) by choosing sufficiently small.
Fix any small constant , and suppose for some large constant . Consider the two vectors and as defined in Algorithm 1, and suppose without loss of generality that (42) holds. Then with probability exceeding , one has
This result follows directly from the Davis-Kahan sin theorem. See Appendix A.5. ∎
We then move on to justifying (51b), the proximity between the original and leave-one-out iterates for .
Suppose for some large constant . Then with probability at least , one has
This is also a consequence of the Davis-Kahan sin theorem. See Appendix A.6.∎
The final claim (51c) can be proved using the same argument as in deriving (55), and hence is omitted.
Analysis for matrix completion
In this section, we instantiate the general recipe presented in Section 5 to matrix completion and prove Theorem 2. Before continuing, we first gather a few useful facts regarding the loss function in (23). The gradient of it is given by
We define the expected gradient (with respect to the sampling set ) to be
and also the (expected) gradient without noise to be
The first step is to characterize the region where the empirical loss function enjoys restricted strong convexity and smoothness in an appropriate sense. This is formally stated in the following lemma.
where and .
1.2 Error contraction
Suppose that for some sufficiently large constant , the noise satisfies (27). There exists an event that does not depend on and has probability , such that when it happens and (28a), (28b) hold for the th iteration, one has
provided that , , and is sufficiently large.
The proof is built upon Lemma 7. See Appendix B.2. ∎
Further, if the current iterate satisfies all three conditions in (28), then we can derive a stronger sense of error contraction, namely, contraction in terms of the spectral norm.
Suppose for some sufficiently large constant and the noise satisfies (27). There exists an event that does not depend on and has probability , such that when it happens and (28) holds for the th iteration, one has
provided that and .
The key observation is this: the iterate that proceeds according to the population-level gradient reduces the error w.r.t. , namely,
2 Step 2: introducing the leave-one-out sequences
In order to establish the incoherence properties (28b) for the entire trajectory, which is difficult to deal with directly due to the complicated statistical dependence, we introduce a collection of leave-one-out versions of , denoted by for each . Specifically, is the iterates of gradient descent operating on the auxiliary loss function
Here, (resp. and ) represents the orthogonal projection onto the subspace of matrices which vanish outside of the index set (resp. and ); that is, for any matrix ,
The gradient of the leave-one-out loss function (65) is given by
The full algorithm to obtain the leave-one-out sequence (including spectral initialization) is summarized in Algorithm 5.
Rather than simply dropping all samples in the th row/column, we replace the th row/column with their respective population means. In other words, the leave-one-out gradient forms an unbiased surrogate for the true gradient, which is particularly important in ensuring high estimation accuracy.
3 Step 3: establishing the incoherence condition by induction
We will continue the proof of Theorem 2 in an inductive manner. As seen in Section 7.1.2, the induction hypotheses (28a) and (28c) hold for the th iteration as long as (28) holds at the th iteration. Therefore, we are left with proving the incoherence hypothesis (28b) for all . For clarity of analysis, it is crucial to maintain a list of induction hypotheses, which includes a few more hypotheses that complement (28), and is given below.
hold for some absolute constants and . Here, and are orthonormal matrices defined by
Clearly, the first three hypotheses (70a)-(70c) constitute the conclusion of Theorem 2, i.e. (28). The last two hypotheses (70d) and (70e) are auxiliary properties connecting the true iterates and the auxiliary leave-one-out sequences. Moreover, we summarize below several immediate consequences of (70), which will be useful throughout.
Suppose for some sufficiently large constant and the noise satisfies (27). Under the hypotheses (70), one has
In the sequel, we follow the general recipe outlined in Section 5 to establish the induction hypotheses. We only need to establish (70b), (70d) and (70e) for the th iteration, since (70a) and (70c) have been established in Section 7.1.2. Specifically, we resort to the leave-one-out iterates by showing that: first, the true and the auxiliary iterates remain exceedingly close throughout; second, the th leave-one-out sequence stays incoherent with due to statistical independence.
Step 3(a): proximity between the original and the leave-one-out iterates. We demonstrate that is well approximated by , up to proper orthonormal transforms. This is precisely the induction hypothesis (70d) for the th iteration.
provided that , and is sufficiently large.
The fact that this difference is well-controlled relies heavily on the benign geometric property of the Hessian revealed by Lemma 7. Two important remarks are in order: (1) both points and satisfy (63a); (2) the difference forms a valid direction for restricted strong convexity. These two properties together allow us to invoke Lemma 7. See Appendix B.5.∎
Step 3(b): incoherence of the leave-one-out iterates. Given that is sufficiently close to , we turn our attention to establishing the incoherence of this surrogate w.r.t. . This amounts to proving the induction hypothesis (70e) for the th iteration.
so long as , , and .
The key observation is that is statistically independent from any sample in the th row/column of the matrix. Since there are an order of samples in each row/column, we obtain enough information that helps establish the desired incoherence property. See Appendix B.6. ∎
Step 3(c): combining the bounds. The inequalities (70d) and (70e) taken collectively allow us to establish the induction hypothesis (70b). Specifically, for every , write
The second term has already been bounded by (75). Since we have established the induction hypotheses (70c) and (70d) for the th iteration, the first term can be bounded by (73a) for the th iteration, i.e.
Plugging the above inequality, (74) and (75) into (76), we have
as long as and are sufficiently large. This establishes the induction hypothesis (70b). From the deduction above we see and thus finish the proof.
4 The base case: spectral initialization
Finally, we return to check the base case, namely, we aim to show that the spectral initialization satisfies the induction hypotheses (70a)-(70e) for . This is accomplished via the following lemma.
Suppose the sample size obeys for some sufficiently large constant , the noise satisfies (27), and . Then with probability at least , the claims in (70a)-(70e) hold simultaneously for .
This follows by invoking the Davis-Kahan sin theorem [DK70] as well as the entrywise eigenvector perturbation analysis in [AFWZ17]. We defer the proof to Appendix B.7. ∎
Analysis for blind deconvolution
In this section, we instantiate the general recipe presented in Section 5 to blind deconvolution and prove Theorem 3. Without loss of generality, we assume throughout that .
Before presenting the analysis, we first gather some simple facts about the empirical loss function in (32). Recall the definition of in (33), and for notational simplicity, we write . Since is complex-valued, we need to resort to Wirtinger calculus; see [CLS15, Section 6] for a brief introduction. The Wirtinger gradient of (32) with respect to and are given respectively by
It is worth noting that the formal Wirtinger gradient contains and as well. Nevertheless, since is a real-valued function, the following identities always hold
In light of these observations, one often omits the gradient with respect to the conjugates; correspondingly, the gradient update rule (35) can be written as
We can also compute the Wirtinger Hessian of as follows,
Last but not least, we say is aligned with , if the following holds,
To simplify notations, define as
with the alignment parameter given in (38). Then we can see that is aligned with and
The first step is to characterize the region of incoherence and contraction (RIC), where the empirical loss function enjoys restricted strong convexity and smoothness properties. To this end, we have the following lemma.
Let be a sufficiently small constant and
Suppose the sample size satisfies for some sufficiently large constant . Then with probability , the Wirtinger Hessian obeys
is aligned with , and they satisfy
Here, are numerical constants.
Lemma 14 characterizes the restricted strong convexity and smoothness of the loss function used in blind deconvolution. To the best of our knowledge, this provides the first characterization regarding geometric properties of the Hessian matrix for blind deconvolution. A few interpretations are in order.
Similar to matrix completion, the Hessian matrix is rank-deficient even at the population level. Consequently, we resort to a restricted form of strong convexity by focusing on certain directions. More specifically, these directions can be viewed as the difference between two pre-aligned points that are not far from the truth, which is characterized by (83).
Finally, the diagonal matrix accounts for scaling factors that are not too far from (see (84)), which allows us to account for different step sizes employed for and .
1.2 Error contraction
The restricted strong convexity and smoothness allow us to establish the contraction of the error measured in terms of as defined in (34) as long as the iterates stay in the RIC.
Suppose the number of measurements satisfies for some sufficiently large constant , and the step size is some sufficiently small constant. There exists an event that does not depend on and has probability , such that when it happens and
hold for some constants , one has
Here, and are defined in (81), and .
As a result, if satisfies the condition (85) for all , then
where . Furthermore, similar to the case of phase retrieval (i.e. Lemma 3), as soon as we demonstrate that the conditions (85) hold for all , then Theorem 3 holds true. The proof of this claim is exactly the same as for Lemma 3, and is thus omitted for conciseness. In what follows, we focus on establishing (85) for all .
When is sufficiently large, the following two claims hold true.
The initial condition \big{|}|\alpha^{0}|-1\big{|}<1/4 will be guaranteed to hold with high probability by Lemma 19.
2 Step 2: introducing the leave-one-out sequences
As demonstrated by the assumptions in Lemma 15, the key is to show that the whole trajectory lies in the region specified by (85a)-(85c). Once again, the difficulty lies in the statistical dependency between the iterates and the measurement vectors . We follow the general recipe and introduce the leave-one-out sequences, denoted by for each . Specifically, is the gradient sequence operating on the loss function
The whole sequence is constructed by running gradient descent with spectral initialization on the leave-one-out loss (86). The precise description is supplied in Algorithm 6.
For notational simplicity, we denote \bm{z}^{t,(l)}=\left[\begin{array}[]{c}\bm{h}^{t,(l)}\\ \bm{x}^{t,(l)}\end{array}\right] and use interchangeably. Define similarly the alignment parameters
and denote \widetilde{\bm{z}}^{t,(l)}=\left[\begin{array}[]{c}\widetilde{\bm{h}}^{t,\left(l\right)}\\ \widetilde{\bm{x}}^{t,\left(l\right)}\end{array}\right] where
3 Step 3: establishing the incoherence condition by induction
As usual, we continue the proof in an inductive manner. For clarity of presentation, we list below the set of induction hypotheses underlying our analysis:
where and are defined in (81). Here, are some sufficiently small constants, while are some sufficiently large constants. We aim to show that if these hypotheses (90) hold up to the th iteration, then the same would hold for the ()th iteration with exceedingly high probability (e.g. ). The first hypothesis (90a) has already been established in Lemma 15, and hence the rest of this section focuses on establishing the remaining three. To justify the incoherence hypotheses (90c) and (90d) for the ()th iteration, we need to leverage the nice properties of the leave-one-out sequences, and establish (90b) first. In the sequel, we follow the steps suggested in the general recipe.
Step 3(a): proximity between the original and the leave-one-out iterates. We first justify the hypothesis (90b) for the ()th iteration via the following lemma.
provided that the step size is some sufficiently small constant.
As usual, this result follows from the restricted strong convexity, which forces the distance between the two sequences of interest to be contractive. See Appendix C.3.∎
Step 3(b): incoherence of the leave-one-out iterate w.r.t. . Next, we show that the leave-one-out iterate — which is independent of — is incoherent w.r.t. in the sense that
with probability exceeding . To see why, use the statistical independence and the standard Gaussian concentration inequality to show that
with probability exceeding . It then follows from the triangle inequality that
where (i) follows from Lemmas 15 and 17, and (ii) holds as soon as is sufficiently large. Combining the preceding two bounds establishes (91).
Step 3(c): combining the bounds to show incoherence of w.r.t. . The above bounds immediately allow us to conclude that
with probability at least , which is exactly the hypothesis (90c) for the ()th iteration. Specifically, for each , the triangle inequality yields
Here (i) follows from Cauchy-Schwarz, (ii) is a consequence of (197), Lemma 17 and the bound (91), and the last inequality holds as long as is sufficiently large and .
Step 3(d): incoherence of w.r.t. . It remains to justify that is also incoherent w.r.t. its associated design vectors . This proof of this step, however, is much more involved and challenging, due to the deterministic nature of the ’s. As a result, we would need to “propagate” the randomness brought about by to in order to facilitate the analysis. The result is summarized as follows.
as long as is sufficiently large, and is taken to be some sufficiently small constant.
With these steps in place, we conclude the proof of Theorem 3 via induction and the union bound.
4 The base case: spectral initialization
In order to finish the induction steps, we still need to justify the induction hypotheses for the base cases, namely, we need to show that the spectral initializations and satisfy the induction hypotheses (90) at .
Fix any small constant . Suppose the sample size obeys for some sufficiently large constant . Then with probability at least , we have
and .
This follows from Wedin’s sin theorem [Wed72] and [LLSW18, Lemma 5.20]. See Appendix C.5.∎
as long as for some sufficiently large constant . Here (i) follows from the elementary inequality that for positive and , (ii) holds since the feasible set of the latter one is strictly smaller, and (iii) follows directly from Lemma 19. This finishes the proof of (90a) for . Similarly, with high probability we have
Next, when properly aligned, the true initial estimate and the leave-one-out estimate are expected to be sufficiently close, as claimed by the following lemma. Along the way, we show that is incoherent w.r.t. the sampling vectors . This establishes (90b) and (90d) for .
Suppose that for some sufficiently large constant . Then with probability at least , one has
Finally, we establish (90c) regarding the incoherence of with respect to the design vectors .
Suppose that for some sufficiently large constant . Then with probability exceeding , we have
Discussions
This paper showcases an important phenomenon in nonconvex optimization: even without explicit enforcement of regularization, the vanilla form of gradient descent effectively achieves implicit regularization for a large family of statistical estimation problems. We believe this phenomenon arises in problems far beyond the three cases studied herein, and our results are initial steps towards understanding this fundamental phenomenon. There are numerous avenues open for future investigation, and we point out a few of them.
Improving sample complexity. In the current paper, the required sample complexity for matrix completion is sub-optimal when the rank of the underlying matrix is large. While this allows us to achieve a dimension-free iteration complexity, it is slightly higher than the sample complexity derived for regularized gradient descent in [CW15]. We expect our results continue to hold under lower sample complexity , but it calls for a more refined analysis (e.g. a generic chaining argument).
Leave-one-out tricks for more general designs. So far our focus is on independent designs, including the i.i.d. Gaussian design adopted in phase retrieval and partially in blind deconvolution, as well as the independent sampling mechanism in matrix completion. Such independence property creates some sort of “statistical homogeneity”, for which the leave-one-out argument works beautifully. It remains unclear how to generalize such leave-one-out tricks for more general designs (e.g. more general sampling patterns in matrix completion and more structured Fourier designs in phase retrieval and blind deconvolution). In fact, the readers can already get a flavor of this issue in the analysis of blind deconvolution, where the Fourier design vectors require much more delicate treatments than purely Gaussian designs.
Uniform stability. The leave-one-out perturbation argument is established upon a basic fact: when we exclude one sample from consideration, the resulting estimates/predictions do not deviate much from the original ones. This leave-one-out stability bears similarity to the notion of uniform stability studied in statistical learning theory [BE02]. We expect our analysis framework to be helpful for analyzing other learning algorithms that are uniformly stable.
Other iterative methods and other loss functions. The focus of the current paper has been the analysis of vanilla GD tailored to the natural squared loss. This is by no means to advocate GD as the top-performing algorithm in practice; rather, we are using this simple algorithm to isolate some seemingly pervasive phenomena (i.e. implicit regularization) that generic optimization theory fails to account for. The simplicity of vanilla GD makes it an ideal object to initiate such discussions. That being said, practitioners should definitely explore as many algorithmic alternatives as possible before settling on a particular algorithm. Take phase retrieval for example: iterative methods other than GD and / or algorithms tailored to other loss functions have been proposed in the nonconvex optimization literature, including but not limited to alternating minimization, block coordinate descent, and sub-gradient methods and prox-linear methods tailed to non-smooth losses. It would be interesting to develop a full theoretical understanding of a broader class of iterative algorithms, and to conduct a careful comparison regarding which loss functions lead to the most desirable practical performance.
Connections to deep learning? We have focused on nonlinear systems that are bilinear or quadratic in this paper. Deep learning formulations/architectures, highly nonlinear, are notorious for their daunting nonconvex geometry. However, iterative methods including stochastic gradient descent have enjoyed enormous practical success in learning neural networks (e.g. [ZSJ+17, SJL19, FMZ19]), even when the architecture is significantly over-parameterized without explicit regularization. We hope the message conveyed in this paper for several simple statistical models can shed light on why simple forms of gradient descent and variants work so well in learning complicated neural networks.
Finally, while the present paper provides a general recipe for problem-specific analyses of nonconvex algorithms, we acknowledge that a unified theory of this kind has yet to be developed. As a consequence, each problem requires delicate and somewhat lengthy analyses of its own. It would certainly be helpful if one could single out a few stylized structural properties / elements (like sparsity and incoherence in compressed sensing [CP11]) that enable near-optimal performance guarantees through an over-arching method of analysis; with this in place, one would not need to start each problem from scratch. Having said that, we believe that our current theory elucidates a few ingredients (e.g. the region of incoherence and leave-one-out stability) that might serve as crucial building blocks for such a general theory. We invite the interested readers to contribute towards this path forward.
Acknowledgements
Y. Chen is supported in part by the AFOSR YIP award FA9550-19-1-0030, by the ARO grant W911NF-18-1-0303, by the ONR grant N00014-19-1-2120, by the NSF grants CCF-1907661 and IIS-1900140, and by the Princeton SEAS innovation award. Y. Chi is supported in part by the grants AFOSR FA9550-15-1-0205, ONR N00014-18-1-2142 and N00014-19-1-2404, ARO W911NF-18-1-0303, NSF CCF-1826519, ECCS-1818571, CCF-1806154. Y. Chen would like to thank Yudong Chen for inspiring discussions about matrix completion.
References
Appendix A Proofs for phase retrieval
Before proceeding, we gather a few simple facts. The standard concentration inequality for random variables together with the union bound reveals that the sampling vectors obey
with probability at least . In addition, standard Gaussian concentration inequalities give
with probability exceeding .
We start with the smoothness bound, namely, . It suffices to prove the upper bound . To this end, we first decompose the Hessian (cf. (44)) into three components as follows:
where we have used . In the sequel, we control the three terms , and in reverse order.
The third term can be easily bounded by
The second term can be controlled by means of Lemma 32:
for an arbitrarily small constant , as long as for sufficiently large.
It thus remains to control . Towards this we discover that
Under the assumption and the fact (99), we can also obtain
where the last inequality is a direct consequence of Lemma 31.
Combining the above bounds on , and yields
as long as is sufficiently large. This establishes the claimed smoothness property.
Next we move on to the strong convexity lower bound. Picking a constant and enforcing proper truncation, we get
We begin with the simpler term . Lemma 32 implies that with probability at least ,
holds for any small constant , as long as is sufficiently large. This reveals that
To bound , invoke Lemma 33 to conclude that with probability at least (for some constants ),
for any small constant , provided that is sufficiently large. Here,
where the expectation is taken with respect to . By the assumption , one has
Recognizing that (resp. ) approaches 2 (resp. 1) as grows, we can thus take small enough and large enough to guarantee that
Putting the preceding two bounds on and together yields
A.2 Proof of Lemma 2
Using the update rule (cf. (17)) as well as the fundamental theorem of calculus [Lan93, Chapter XIII, Theorem 4.2], we get
where we denote , . Here, the first equality makes use of the fact that . Under the condition (45), it is self-evident that for all ,
This means that for all ,
in view of Lemma 1. Picking (and hence ), one sees that
A.3 Proof of Lemma 3
We start with proving (19a). For all , invoke Lemma 2 recursively with the conditions (47) to reach
This finishes the proof of (19a) for and also reveals that
provided that . Applying the Cauchy-Schwarz inequality and the fact (98) indicate that
leading to the satisfaction of (45). Therefore, invoking Lemma 2 yields
One can then repeat this argument to arrive at for all
We are left with (19b). It is self-evident that the iterates from satisfy (19b) by assumptions. For , we can use the Cauchy-Schhwarz inequality to obtain
where the penultimate relation uses the conditions (98) and (103).
A.4 Proof of Lemma 4
First, going through the same derivation as in (54) and (55) will result in
for some , which will be helpful for our analysis.
We use the gradient update rules once again to decompose
where the last line comes from the definition of and .
We first control the term , which is easier to deal with. Specifically,
for any small constant . Here (i) follows since (98) and, in view of (99) and (104),
And (ii) holds as long as .
For the term , the fundamental theorem of calculus [Lan93, Chapter XIII, Theorem 4.2] tells us that
where we abuse the notation and denote . By the induction hypotheses (51) and the condition (104), one can verify that
for all , as long as . The second line follows directly from (104). To see why (105) holds, we note that
where the second inequality follows from the induction hypotheses (51b) and (51a). This combined with (51a) gives
as long as is large enough, thus justifying (105). Hence by Lemma 1, is positive definite and almost well-conditioned. By choosing , we get
Combine the preceding bounds on and as well as the induction bound (51b) to arrive at
This establishes (53) for the th iteration.
A.5 Proof of Lemma 5
In view of the assumption (42) that and the fact that for some (which we will verify below), it is straightforward to see that
One can then invoke the Davis-Kahan sin theorem [YWS15, Corollary 1] to obtain
To connect this bound with , we need to take into account the scaling factor . To this end, it follows from Weyl’s inequality and (56) that
and, as a consequence, when . This further implies that
where we have used the elementary identity . With these bounds in place, we can use the triangle inequality to get
A.6 Proof of Lemma 6
To begin with, repeating the same argument as in Lemma 5 (which we omit here for conciseness), we see that for any fixed constant ,
We start by controlling \big{\|}\widetilde{\bm{x}}^{0}-\widetilde{\bm{x}}^{0,\left(l\right)}\big{\|}_{2}. Combining (57) and (108) yields
For sufficiently small, this implies that \big{\|}\widetilde{\bm{x}}^{0}-\widetilde{\bm{x}}^{0,\left(l\right)}\big{\|}_{2}\leq\big{\|}\widetilde{\bm{x}}^{0}+\widetilde{\bm{x}}^{0,\left(l\right)}\big{\|}_{2}, and hence the Davis-Kahan sin theorem [DK70] gives
Here, the second inequality uses Weyl’s inequality:
We now connect with . Applying the Weyl’s inequality and (56) yields
and, similarly, . Invoke Lemma 34 to arrive at
where the last inequality comes from (109).
Everything then boils down to controlling . Towards this we observe that
The inequality (i) makes use of the fact (cf. (99)), the bound (cf. (98)), and (due to statistical independence and standard Gaussian concentration). As long as is sufficiently large, substituting the above bound (112) into (111) leads us to conclude that
Appendix B Proofs for matrix completion
Before proceeding to the proofs, let us record an immediate consequence of the incoherence property (25):
where is the condition number of . This follows since
Unless otherwise specified, we use the indicator variable to denote whether the entry in the location is included in . Under our model, is a Bernoulli random variable with mean .
By the expression of the Hessian in (61), one can decompose
The basic idea is to demonstrate that: is bounded both from above and from below, and the first three terms are sufficiently small in size compared to .
We start by controlling . It is immediate to derive the following upper bound
When it comes to the lower bound, one discovers that
where the last line comes from the assumptions that
With our assumption in mind, it comes down to controlling
From the definition of , we see from Lemma 35 that (and hence ) is a symmetric matrix, which implies that
For , we consider the following quantity
This then calls for upper bounds on the following two terms
The injectivity of (cf. [CR09, Section 4.2] or Lemma 38)—when restricted to the tangent space of —gives: for any fixed constant ,
with probability at least , provided that is sufficiently large. In addition,
with probability exceeding , which holds as long as is sufficiently large. Taken collectively, the above bounds yield that for any small constant ,
where the last inequality makes use of the assumption . The same analysis can be repeated to control . Altogether, we obtain
where (i) utilizes the incoherence condition (114) and (ii) holds with the proviso that .
To bound , apply the Cauchy-Schwarz inequality to get
In view of Lemma 43, with probability at least ,
as soon as , where we utilize the incoherence condition (114). This in turn implies that
Notably, this bound holds uniformly over all satisfying the condition in Lemma 7, regardless of the statistical dependence between and the sampling set .
The last term can also be controlled using the injectivity of when restricted to the tangent space of . Specifically, it follows from the bounds in [CR09, Section 4.2] or Lemma 38 that
for any such that is a small constant, as soon as .
Taking all the preceding bounds collectively yields
for all satisfying our assumptions, and
for all . Since this upper bound holds uniformly over all , we conclude that
B.2 Proof of Lemma 8
Given that is chosen to minimize the error in terms of the Frobenius norm (cf. (26)), we have
For the second term in (117), it is easy to see that with probability at least ,
For the first term in (117), the fundamental theorem of calculus [Lan93, Chapter XIII, Theorem 4.2] reveals
where we denote . Taking the squared Euclidean norm of both sides of the equality (118) leads to
where in (119) we have used the fact that
Based on the condition (28b), it is easily seen that ,
Taking and in Lemma 7, one can easily verify the assumptions therein given our sample size condition and the noise condition (27). As a result,
Substituting these two inequalities into (119) yields
as long as , which further implies that
Combining the preceding bounds on both and and making use of the hypothesis (28a), we have
as long as , and is sufficiently large. This completes the proof of the contraction with respect to the Frobenius norm.
B.3 Proof of Lemma 9
To facilitate analysis, we construct an auxiliary matrix defined as follows
With this auxiliary matrix in place, we invoke the triangle inequality to bound
We start with the second term and show that the auxiliary matrix is also not far from the truth. The definition of allows one to express
where we have used the triangle inequality to separate the population-level component (i.e. ), the perturbation (i.e. ), and the noise component. In what follows, we will denote
which, by Lemma 35, satisfies the following symmetry property
The population-level component is easier to control. Specifically, we first simplify its expression as
The leading term can be upper bounded by
where the second identity follows from the symmetry property (124). By choosing , one has and , and further one can ensure
Next, regarding the higher order term , we can easily obtain
The bounds (125) and (126) taken collectively give
We now turn to the perturbation part by showing that
For the first term in (128), the th row of is given by
where, as usual, . Lemma 41 together with the union bound reveals that
for all with high probability. This gives
For the second term in (128), denote
Recalling the induction hypotheses (28b) and (28c), we define
With these two definitions in place, we now introduce a “truncation level”
that allows us to bound in terms of the following two terms
We will apply different strategies when upper bounding the terms and , with their bounds given in the following two lemmas under the induction hypotheses (28b) and (28c).
Under the conditions in Lemma 9, there exist some constants such that with probability exceeding ,
holds simultaneously for all obeying (130) and (131). Here, is defined in (130).
Under the conditions in Lemma 9, with probability at least ,
holds simultaneously for all obeying (130) and (131). Here, is defined in (130).
The bounds (133) and (134) together with the incoherence condition (114) yield
Next, we assert that the third term in (128) has the same upper bound as . The proof follows by repeating the same argument used in bounding , and is hence omitted.
Take the previous three bounds on , and together to arrive at
Substituting the preceding bounds on and into (123), we reach
for some constant . Here, (i) uses the definition of (cf. (130)), (ii) holds if is small enough and , and (iii) follows from Lemma 40 as well as the incoherence condition (114). An immediate consequence of (135) is that under the sample size condition and the noise condition of this lemma, one has
We then move on to the first term in (121), which can be rewritten as
First, we claim that satisfies
meaning that is already rotated to the direction that is most “aligned” with . This important property eases the analysis. In fact, in view of Lemma 35, (138) follows if one can show that is symmetric and positive semidefinite. First of all, it follows from Lemma 35 that is symmetric and, hence, by definition,
where the second inequality holds according to (136). Weyl’s inequality guarantees that
With (137) and (138) in place, we resort to Lemma 37 to establish the bound. Specifically, take and , and it comes from (136) that
for some absolute constant . Here the last inequality follows from Lemma 40 and Lemma 43. As a consequence,
Under our sample size condition and the noise condition (27) and the induction hypotheses (28), one can show
Combining the above bounds on and , we arrive at
with the proviso that , is a constant, and .
In what follows, we first assume that the ’s are independent, and then use the standard decoupling trick to extend the result to symmetric sampling case (i.e. ).
To begin with, we justify the concentration bound for any independent of , followed by the standard covering argument that extends the bound to all . For any independent of , one has
where and are defined respectively in (130) and (131). Here, the last line makes use of the fact that
as long as is sufficiently large. Apply the matrix Bernstein inequality [Tro15b, Theorem 6.1.1] to get
This upper bound on is exactly the truncation level we introduce in (132). With this in mind, we can easily verify that
is a sub-Gaussian random variable with variance proxy not exceeding . Therefore, invoking the concentration bounds for quadratic functions [HKZ12, Theorem 2.1] yields that for some constants , with probability at least ,
Now that we have established an upper bound on any fixed matrix (which holds with exponentially high probability), we can proceed to invoke the standard epsilon-net argument to establish a uniform bound over all feasible . This argument is fairly standard, and is thus omitted; see [Tao12, Section 2.3.1] or the proof of Lemma 42. In conclusion, we have that with probability exceeding ,
B.3.2 Proof of Lemma 23
where is as defined in (131) and is as defined in Lemma 41. Here, the last inequality follows from Lemma 41, namely, for some constant , the following holds with probability at least
where we also use the incoherence condition (114) and the sample complexity condition . Hence, the event
together with (142) and (147) necessarily implies that
where the last inequality follows from the bound (140). As a result, with probability at least (i.e. when (151) holds for all ’s) we can upper bound by
where the indicator functions are now specified with respect to .
Next, we divide into multiple cases based on the size of . By Lemma 42, for some constants , with probability at least ,
for any and any . We claim that it suffices to consider the set of sufficiently large obeying
which contradicts the event . Consequently, we divide all indices into the following sets
defined for each integer obeying (153). Under the condition (153), it follows from (152) that
meaning that the cardinality of satisfies
which decays exponentially fast as increases. Therefore, when restricting attention to the set of indices within , we can obtain
where (i) follows from the bound (147) and the constraint (154) in , (ii) is a consequence of (153) and (iii) uses the incoherence condition (114).
Now that we have developed an upper bound with respect to each , we can add them up to yield the final upper bound. Note that there are in total no more than different sets, i.e. if for sufficiently large. This arises since
if is sufficiently large. One can thus conclude that
leading to . The proof is finished by taking for some sufficiently large constant .
B.4 Proof of Lemma 10
To obtain (73a), we invoke Lemma 37. Setting and , we get
where (i) follows from (70c) and (ii) holds as long as and the noise satisfies (27). In addition,
where (i) utilizes (70d), (ii) follows since , and (iii) holds if and the noise satisfies (27). With these in place, Lemma 37 immediately yields (73a).
The first inequality in (73b) follows directly from the definition of . The second inequality is concerned with the estimation error of with respect to the Frobenius norm. Combining (70a), (70d) and the triangle inequality yields
where the last step holds true as long as .
To obtain (73c), we use (70d) and (70b) to get
Finally, to obtain (73d), one can take the triangle inequality
where the second line follows from (73a). Combine (70d) and (70c) to yield
where the second inequality uses the incoherence of (cf. (114)) and the last inequality holds as long as .
B.5 Proof of Lemma 11
From the definition of (see (72)), we must have
The gradient update rules in (24) and (69) allow one to express
where we have used the following relationship between and :
The last term is controlled via the following lemma.
Suppose that the sample size obeys for some sufficiently large constant . Then with probability at least , the matrix as defined in (156) satisfies
The third term can be bounded as follows
where the second inequality comes from Lemma 40.
For the second term , we have the following lemma.
Suppose that the sample size obeys . Then with probability exceeding , the matrix as defined in (156) satisfies
Regarding the first term , apply the fundamental theorem of calculus [Lan93, Chapter XIII, Theorem 4.2] to get
where we abuse the notation and denote . Going through the same derivations as in the proof of Lemma 8 (see Appendix B.2), we get
with the proviso that .
Applying the triangle inequality to (156) and invoking the preceding four bounds, we arrive at
for some absolute constant . Here the last inequality holds as long as , which is satisfied under our noise condition (27). This taken collectively with the hypotheses (70d) and (73c) leads to
as long as is sufficiently large, where we have used the sample complexity assumption and the step size . This finishes the proof.
By the unitary invariance of the Frobenius norm, one has
where all nonzero entries of the matrix reside in the th row/column. Decouple the effects of the th row and the th column of to reach
where indicates whether the -th entry is observed. Since is independent of and , we can treat the first term as a sum of independent vectors . It is easy to verify that
where denotes the sub-exponential norm [Kol11, Section A.1]. Further, one can calculate
Invoke the matrix Bernstein inequality [Kol11, Theorem 2.7] to discover that with probability at least ,
Additionally, the remaining term in (161) can be controlled using the same argument, giving rise to
We then complete the proof by observing that
where the last inequality follows by combining (73c), the sample complexity condition , and the noise condition (27).
B.5.2 Proof of Lemma 25
Since the Frobenius norm is unitarily invariant, we have
Again, all nonzero entries of the matrix reside in its th row/column. We can deal with the th row and the th column of separately as follows
where and the second line relies on the fact that . It follows that
Here, (i) is a consequence of (162). In addition, (ii) follows from
where the last inequality comes from (73b), the sample complexity condition , and the noise condition (27). The matrix Bernstein inequality [Tro15b, Theorem 6.1.1] reveals that
with probability exceeding , and as a result,
To finish up, we make the observation that
where the last line arises from (162). This combined with (164) gives
where (i) comes from (165), and (ii) makes use of the incoherence condition (114).
B.6 Proof of Lemma 12
With this in place, we can use the triangle inequality to obtain
In what follows, we bound the two terms and separately.
Regarding the second term of (167), we see from the definition of (see (166)) that
where we also utilize the definitions of and in (67). For notational convenience, we denote
Here, the last line follows from the fact that . To see this, one can use the induction hypothesis (70e) to get
as long as and . By taking , we have , and hence can obtain
An immediate consequence of the above two inequalities and (73d) is
The first term of (167) can be equivalently written as
Here, to bound the the second term we have used
where the last inequality follows from (172). It remains to upper bound and . For both and , a central quantity to control is . By the definition of in (166) and the gradient update rule for (see (69)), one has
for sufficiently small. Here, (i) uses the elementary fact that the spectral norm of a submatrix is no more than that of the matrix itself, (ii) arises from Lemma 40 and (iii) is a consequence of the noise condition (27). Therefore, in order to control (173), we need to upper bound the following quantity
To this end, we make the observation that
where is defined in (66). An application of Lemma 43 reveals that
where is defined in (72). Let as in (163), and one can bound the other term by taking advantage of the triangle inequality and the symmetry property:
where (i) comes from the standard Chernoff bound , and in (ii) we utilize the bound established in (165). The previous two bounds taken collectively give
for some constant and sufficiently small. The last inequality follows from (73c), the incoherence condition (114) and our sample size condition. In summary, we obtain
for sufficiently small. With the estimate (177) in place, we can continue our derivation on and .
With regard to , in view of (173) we can obtain
where (i) follows from the definitions of and (see (67) and note that all entries in the th row of are identically zero), and the identity (ii) is due to the definition of in (169).
whose justification follows similar reasonings as that of (138), and is therefore omitted. In particular, it gives rise to the facts that is symmetric and
We are now ready to invoke Lemma 36 to bound . We abuse the notation and denote \bm{C}:=\big{(}\widetilde{\bm{X}}^{t+1,\left(l\right)}\big{)}^{\top}\bm{X}^{\star} and \bm{E}:=\big{(}\bm{X}^{t+1,\left(l\right)}\widehat{\bm{H}}^{t,\left(l\right)}-\widetilde{\bm{X}}^{t+1,\left(l\right)}\big{)}^{\top}\bm{X}^{\star}. We have
The first inequality arises from (177), namely,
where (i) holds since and (ii) holds true for sufficiently small and . Invoke Lemma 36 to obtain
where (181) follows since from (180), and the last line comes from (177).
Putting the previous bounds (178) and (182) together yields
Here, (i) follows since and is sufficiently small, (ii) invokes the hypotheses (70e) and (73d) and recognizes that
holds under the sample size and noise condition, while is valid as long as , and .
B.7 Proof of Lemma 13
For notational convenience, we define the following two orthonormal matrices
The problem of finding (see (26)) is called the orthogonal Procrustes problem [TB77]. It is well-known that the minimizer always exists and is given by
for any matrix with singular value decomposition , where the columns of and are left and right singular vectors, respectively.
Before proceeding, we make note of the following perturbation bounds on and (as defined in Algorithm 2 and Algorithm 5, respectively):
for some universal constant . Here, (i) arises from the triangle inequality, (ii) utilizes Lemma 39 and Lemma 40, (iii) follows from the incoherence condition (114) and (iv) holds under our sample complexity assumption that and the noise condition (27). Similarly, we have
Combine Weyl’s inequality, (185) and (186) to obtain
We start by proving (70a), (70b) and (70c). The key decomposition we need is the following
For the spectral norm error bound in (70c), the triangle inequality together with (189) yields
where we have also used the fact that . Recognizing that (see (185)) and the assumption , we can apply Lemma 47, Lemma 46 and Lemma 45 to obtain
These taken collectively imply the advertised upper bound
where we also utilize the fact that \big{\|}\left(\bm{\Sigma}^{0}\right)^{1/2}\big{\|}\leq\sqrt{2\sigma_{\max}} (see (188)) and the bounded condition number assumption, i.e. . This finishes the proof of (70c).
With regard to the Frobenius norm bound in (70a), one has
The proof of (70b) follows from similar arguments as used in proving (70c). Combine (189) and the triangle inequality to reach
Plugging in the estimates (185), (188), (190a) and (190b) results in
It remains to study the component-wise error of . To this end, it has already been shown in [AFWZ17, Lemma 14] that
under our assumptions. These combined with the previous inequality give
where the last relation is due to the observation that
Note that and, by construction of ,
In order to control this, we first see that
where the penultimate inequality uses (188) and the last inequality arises from Lemma 46. Additionally, Lemma 45 gives
Plugging the previous two bounds into (193), we reach
where the last relation follows from and the estimate (186). Note that this also implies that . To see this, one has by the unitary invariance of ,
Substituting the above bounds back to (192) yields in
where the second line relies on Lemma 47, the bound (186), and the condition . This establishes (70e).
we can use the triangle inequality to bound
In view of Lemma 46 and the bounds (185) and (186), one has
From Davis-Kahan’s sin theorem [DK70] we see that
These estimates taken together with (188) give
then taking the previous bounds collectively establishes the desired bound
On the other hand, by the Davis-Kahan theorem [DK70] we obtain
since the th row of is identically zero by construction. In addition,
which combined with (195) and the assumption yields
The claim (194) then follows by combining the above estimates:
where we have utilized the unitary invariance of . ∎
Appendix C Proofs for blind deconvolution
Before proceeding to the proofs, we make note of the following concentration results. The standard Gaussian concentration inequality and the union bound give
with probability at least . In addition, with probability exceeding for some constants ,
In addition, the population/expected Wirtinger Hessian at the truth is given by
First, we find it convenient to decompose the Wirtinger Hessian (cf. (80)) into the expected Wirtinger Hessian at the truth (cf. (198)) and the perturbation part as follows:
The proof then proceeds by showing that (i) the population Hessian \nabla^{2}F\big{(}\bm{z}^{\star}\big{)} satisfies the restricted strong convexity and smoothness properties as advertised, and (ii) the perturbation \nabla^{2}f\left(\bm{z}\right)-\nabla^{2}F\big{(}\bm{z}^{\star}\big{)} is well-controlled under our assumptions. We start by controlling the population Hessian in the following lemma.
Instate the notation and the conditions of Lemma 14. We have
The next step is to bound the perturbation. To this end, we define the set
Suppose the sample complexity satisfies , is a sufficiently small constant, and . Then with probability at least , one has
Combining the two lemmas, we can easily see that for ,
which verifies the smoothness upper bound. In addition,
where (i) uses the triangle inequality, (ii) holds because of Lemma 27 and the fact that , and (iii) follows if . This establishes the claim on the restricted strong convexity.
We start by proving the identity . Let
Recalling that , we can easily check that these four vectors form an orthonormal set. A little algebra reveals that
We now turn attention to the restricted strong convexity. Since is the complex conjugate of as both and are Hermitian, we will focus on the first term . This term can be rewritten as
where (i) uses the definitions of and , and (ii) follows from the definition of . In view of the assumption (84), we can obtain
where the last inequality utilizes the identity
It then boils down to controlling . Toward this goal, we decompose into the following four terms
Since and are both small by (83), and are well-bounded. Specifically, regarding , we discover that
where the second inequality is due to (83) and the last one holds since . Similarly, we can obtain
where both lines make use of the facts that
Combine the previous three bounds to reach
where we utilize the elementary inequality and the identity (220).
The only remaining term is thus . Recalling that and are aligned by our assumption, we can invoke Lemma 56 to obtain
which allows one to rewrite as
Here, (i) arises from the triangle inequality that
and (ii) occurs since and (see (221)).
To finish up, note that for . Substitute these bounds into (219) to obtain
C.1.2 Proof of Lemma 27
In view of the expressions of and (cf. (80) and (198)) and the triangle inequality, we get
where the four terms on the right-hand side are defined as follows
In what follows, we shall control for separately.
Regarding the first term , the triangle inequality gives
To control , the key observation is that and are extremely close. We can rewrite as
the second relation (ii) comes from the triangle inequality, and the third line (iii) follows from (196) and the assumption (82b). Substitution into (223) gives
where the last inequality comes from the fact that .
The other term can be bounded through Lemma 59, which reveals that with probability ,
Taken collectively, the preceding two bounds give
The second term is easy to control. To see this, we have
where the penultimate relation uses the assumption that and hence
For the first term , we define a new set
It is easily seen that . We plan to use the standard covering argument to show that
To this end, we define for every . It is straightforward to check that
for . In the above argument, we have used the facts that and
together with the definition of . Lemma 57 combined with (225) and (226) readily yields that for any fixed and any ,
where are some universal constants.
Now we are in a position to strengthen this bound to obtain uniform control of over . Note that for any ,
Define an event . When happens, the previous estimates give
Let , and be an -net covering (see [Ver12, Definition 5.1]). We have
for some constant . Under the sample complexity , the right-hand side of the above display is at most . Combine the estimates above to establish the desired high-probability bound for .
As a consequence, we can write .
where is some absolute constant. This motivates us to divide the entries in into multiple groups based on their magnitudes.
To be precise, introduce sets , where
and \mathcal{I}_{R}=\{1,\cdots,m\}\,\backslash\,\big{(}\bigcup_{r=1}^{R-1}\mathcal{I}_{r}\big{)}. An immediate consequence of the definition of and the norm constraints in (228) is the following cardinality bound
for . Since form a partition of the index set , it is easy to see that
where denotes the submatrix of induced by the rows and columns of having indices from and , respectively, and refers to the submatrix formed by the rows from the index set . As a result, one can invoke the triangle inequality to derive
Recognizing that , we obtain
for every . In addition, by construction of , we have
for , and specifically for , one has
which follows from the definition of , i.e. . Regarding , we discover that and in view of (229),
Substitute the above estimates into (230) to get
It remains to upper bound and . Lemma 57 tells us that with probability at least . Furthermore, we can invoke Lemma 58 to bound for each . It is easily seen from our assumptions and that . In addition,
By Lemma 58 we obtain that for some constants
Taking the union bound and substituting the estimates above into (231), we see that with probability at least ,
Note that , , and
Therefore, with probability exceeding ,
By taking to be small enough in , we get
Finally, it remains to justify (228). For all , the triangle inequality tells us that
for some large constant , where we have used the definition of and the fact (196). The claim (228b) follows directly from [LLSW18, Lemma 5.14]. To avoid confusion, we use to refer to the parameter therein. Let , , , , and . Then
and the sample complexity condition is satisfied because we have assumed . Therefore with probability exceeding , we obtain that for all ,
The claim (228b) can then be justified by observing that
It remains to control , for which we make note of the following inequality
with denoting the entrywise conjugate of . Since has the same joint distribution as , by the same argument used for bounding we obtain control of the first term, namely,
Note that and . According to [LLSW18, Lemma 5.20],
Combining all the previous bounds for and (222), we deduce that with probability ,
C.2 Proofs of Lemma 15 and Lemma 16
In view of the definition of (see (38)), one has
The gradient update rules (79) imply that
where we denote and as in (81). Let and . We further get
The fundamental theorem of calculus (see Appendix D.3.1) together with the fact that tells us
where we denote and is the Wirtinger Hessian. To further simplify notation, denote . The identity (249) allows us to rewrite (248) as
Take the squared Euclidean norm of both sides of (250) to reach
Since lies between and , we conclude from the assumptions (85) that for all ,
for sufficiently small. Moreover, it is straightforward to see that
as long as is sufficiently small. We can now readily invoke Lemma 14 to arrive at
When , this implies that
Reuse the notation in this subsection, namely, \widehat{\bm{z}}^{t+1}=\left[\begin{array}[]{c}\widehat{\bm{h}}^{t+1}\\ \widehat{\bm{x}}^{t+1}\end{array}\right] with and . From (266), one can tell that
Invoke Lemma 52 with to get
This combined with the assumption implies that
This finishes the proof of the first claim.
for sufficiently large. The proof is then complete by induction. ∎
C.3 Proof of Lemma 17
Define the alignment parameter between and as
Further denote, for simplicity of presentation, with
Clearly, is aligned with .
where (267) follows by taking . The latter bound is more convenient to work with when controlling the gap between and .
We can then apply the gradient update rules (79) and (89) to get
By construction, we can write the leave-one-out gradients as
which allow us to continue the derivation and obtain
In what follows, we bound the three terms , , and separately.
Regarding the first term , one can adopt the same strategy as in Appendix C.2. Specifically, write
The fundamental theorem of calculus (see Appendix D.3.1) reveals that
where we abuse the notation and denote . In order to invoke Lemma 14, we need to verify the conditions required therein. Recall the induction hypothesis (90b) that
and the fact that lies between and . For all :
If , then
where we have used the induction hypotheses (90a) and (90b);
which follows from the bound (197) and the induction hypotheses (90b) and (90c);
which makes use of the fact as well as the induction hypotheses (90b) and (90d).
These properties satisfy the condition (82) required in Lemma 14. The other two conditions (83) and (84) are also straightforward to check and hence we omit it. Thus, we can repeat the argument used in Appendix C.2 to obtain
In terms of the second term , it is easily seen that
We first note that the upper bound on (which essentially provides a Lipschitz constant on the gradient) in Lemma 14 forces
where the first identity follows since , and the last inequality comes from the induction hypothesis (90a). Additionally, recognizing that , one can easily verify that
A similar bound holds for the other term involving . Combining the estimates above thus yields
When it comes to the last term , one first sees that
The bounds (196) and (279) taken collectively yield
In addition, the same argument as in obtaining (280) tells us that
Combine the previous two bounds to obtain
Putting these bounds together indicates that
The above bounds taken together with (270) and (278) ensure the existence of a constant such that
Here, (i) holds as long as is sufficiently large such that and
which is guaranteed by Lemma 16. The inequality (ii) arises from the induction hypothesis (90b) and taking is sufficiently large.
Finally we establish the second inequality claimed in the lemma. Take and in Lemma 55. Since both and are close enough to , we deduce that
C.4 Proof of Lemma 18
Before going forward, we make note of the following inequality
for some small , where the last relation follows from Lemma 16 that
for sufficiently large. In view of the above inequality, the focus of our subsequent analysis will be to control .
The gradient update rule for (cf. (79a)) gives
where and . Here and below, we denote for notational convenience. The above formula can be further decomposed into the following terms
where we use the fact that . In the sequel, we shall control each term separately.
We start with by making the observation that
Combining the induction hypothesis (90c) and the condition (196) yields
as long as is sufficiently large. This further implies
Substituting it into (284) and taking Lemma 48, we arrive at
with the proviso that is sufficiently small.
We then move on to , which obeys
Regarding the first term, we have the following lemma, whose proof is given in Appendix C.4.1.
Suppose for some sufficiently large constant . Then with probability at least , one has
For the remaining term, we apply the same strategy as in bounding to get
where the second line follows from the incoherence (36), the induction hypothesis (90c), the condition (196) and Lemma 48. Combining the above three inequalities and the incoherence (36) yields
We will now bound each term in (286) separately.
Before bounding the first term in (286), we first bound the pre-factor \left|\sum_{j=1}^{\tau}\big{(}|\bm{a}_{l+j}^{\mathsf{H}}\bm{x}^{\star}|^{2}-\|\bm{x}^{\star}\|_{2}^{2}\big{)}\right|. Notably, the fluctuation of this quantity does not grow fast as it is the sum of i.i.d. random variables over a group of relatively large size, i.e. . Since follows the distribution, by standard concentration results (e.g. [RV13, Theorem 1.1]), with probability exceeding ,
With this result in place, we can bound the first term in (286) as
It is straightforward to see from the proof of Lemma 48 that
Substituting (288) into the previous inequality (287) gives
as long as and .
where the first inequality is due to Cauchy-Schwarz, and the second one holds because of the following lemma, whose proof can be found in Appendix C.4.2.
Suppose for some sufficiently large constant . Then with probability exceeding ,
With the above bound in mind, we can sum over all bins of size to obtain
Here, the last line arises from Lemma 51, which says that for any small constant , as long as
where the last line relies on the inequality
owing to Lemma 29 and the Cauchy-Schwarz inequality. Summing over all bins gives
where the last relation makes use of (288) with the proviso that . It then boils down to bounding \max_{0\leq l\leq m-\tau,\,1\leq j\leq\tau}\big{|}\left(\bm{b}_{l+j}-\bm{b}_{l+1}\right)^{\mathsf{H}}\widetilde{\bm{h}}^{t}\big{|}. Without loss of generality, it suffices to look at \big{|}(\bm{b}_{j}-\bm{b}_{1})^{\mathsf{H}}\widetilde{\bm{h}}^{t}\big{|} for all . Specifically, we claim for the moment that
for some sufficiently small constant , provided that . As a result,
Putting the above results together, we get
Combining the preceding bounds guarantees the existence of some constant such that
Here, (i) uses the induction hypothesis (90d), and (ii) holds as long as is sufficiently small (so that ) and is some sufficiently small constant. In order for the proof to go through, it suffices to pick
for some sufficiently large constant . Accordingly, we need the sample size to exceed
Finally, it remains to verify the claim (289), which we accomplish in Appendix C.4.3.
where is some universal constant. By taking , we see there exists some constant such that
We conclude the proof by observing that as stated in the assumption.
C.4.2 Proof of Lemma 29
From the elementary inequality , we see that
where the last identity holds true since . It thus suffices to control . Let , which is a standard complex Gaussian random variable. Since the ’s are statistically independent, one has
for some constant . It then follows from the hypercontractivity concentration result for Gaussian polynomials that [SS12, Theorem 1.9]
for some constants , with the proviso that . As a consequence, with probability at least ,
which together with (290) concludes the proof.
C.4.3 Proof of Claim (289)
We will prove the claim by induction. Again, observe that
for some , which allows us to look at instead.
Use the gradient update rule for (cf. (79a)) once again to get
where we denote This further gives rise to
where the last identity makes use of the fact that . For , one can get
where we utilize the incoherence condition (36) and the fact that and are extremely close, i.e.
Regarding the second term , we have
The term can be bounded as follows
Here, we have used the incoherence condition (36) and the facts that
which are immediate consequences of (90c) and (196). Combining this with Lemma 50, we see that for any small constant
Making use of the induction hypothesis (85c) and the fact that , we reach
Recall that . As a result, if is some sufficiently small constant and if
Therefore, this concludes the proof of the claim (289) by induction, provided that the base case is true, i.e. for some sufficiently small
The claim (291) is proved in Appendix C.6 (see Lemma 30).
C.5 Proof of Lemma 19
Recall that and are the leading left and right singular vectors of , respectively. Applying a variant of Wedin’s sin theorem [Dop00, Theorem 2.1], we derive that
for some universal constant . Regarding the numerator of (292), it has been shown in [LLSW18, Lemma 5.20] that for any ,
with probability exceeding , provided that
for some universal constant . For the denominator of (292), we can take (293) together with Weyl’s inequality to demonstrate that
Since are also the leading left and right singular vectors of , we can invoke Lemma 60 to get
In addition, we can apply Weyl’s inequality once again to deduce that
where the last inequality comes from (293). Substitute (296) into (295) to obtain
Taking the minimum over , one can thus conclude that
where the last inequality comes from (294). Since is arbitrary, by taking to be large enough, we finish the proof for (92). Carrying out similar arguments (which we omit here), we can also establish (93).
The last claim in Lemma 19 that is a direct corollary of (92) and Lemma 52.
C.6 Proof of Lemma 20
In the first step, we show that the normalized singular vectors of and are close enough; see (305).
We then proceed by passing this proximity result to the scaled singular vectors; see (308).
Here comes the formal proof. Recall that and are respectively the leading left and right singular vectors of , and and are respectively the leading left and right singular vectors of . Invoke Wedin’s sin theorem [Dop00, Theorem 2.1] to obtain
for some universal constant . Using the Weyl’s inequality we get
where the penultimate inequality follows from
for sufficiently large, and the last inequality comes from [LLSW18, Lemma 5.20], provided that for some sufficiently large constant . As a result, denoting
It then boils down to controlling the two terms on the right-hand side of (299). By construction,
where we use the fact that , the incoherence condition (36), the bound (196) and the fact that with probability exceeding ,
due to the independence between and .
To bound the second term, for any obeying one has
Here, (i) arises from the incoherence condition (36) together with the bounds (196) and (197), the inequality (ii) comes from the triangle inequality, and the last line (iii) holds since and .
Substitution of the above bounds into (299) yields
Since the previous inequality holds for all , we can choose and rearrange terms to get
Under the condition that , one has , and therefore
We then move on to . The aim is to show that can also be upper bounded by the left-hand side of (301). By construction, we have , which further leads to
where is as defined in (298). Here, (i) comes from the lower bound . The bound (ii) follows by combining the incoherence condition (36), the bound (196), the triangle inequality, as well as the estimate from Lemma 48. The last line uses the upper estimate and (197). Our bound (302) further implies
The above bound (303) taken together with (301) gives
As long as we have . Rearranging terms, we are left with
for some constant . Further, this bound combined with (303) yields
for some constant , with the proviso that .
We now translate the preceding bounds to the scaled version. Recall from the bound (296) that
Taking the previous two bounds collectively yields
which together with (300) and (305) implies
for some constant , as long as is sufficiently small. Moreover, we have
for any , where is defined in (38) and, according to Lemma 19, satisfies
where the second line follows since the latter is minimizing over a smaller feasible set. This completes the proof for the claim (96).
Regarding \big{|}\bm{b}_{l}^{\mathsf{H}}\widetilde{\bm{h}}^{0}\big{|}, one first sees that
where the last relation holds due to (306) and (307). Hence, using the property (309), we have
which finishes the proof of the claim (97).
Before concluding this section, we note a byproduct of the proof. Specifically, we can establish the claim required in (291) using many results derived in this section. This is formally stated in the following lemma.
Fix any small constant . Suppose the number of samples obeys . Then with probability at least , we have
Instate the notation and hypotheses in Appendix C.6. Recognize that
where the last inequality comes from (307) and (309). It thus suffices to prove that for some small enough. To this end, it can be seen that
where (i) comes from Lemma 50, the incoherence condition (36), and the estimate (196). The last line (ii) holds since we have already established (see (302) and (305))
C.7 Proof of Lemma 21
Recall that and are the alignment parameters between and , and between and , respectively, that is,
The triangle inequality together with (94) and (310) then tells us that
where the last relation holds as long as .
It is easy to see that satisfy the assumptions in Lemma 55, which implies
where the last line comes from (310). With this upper estimate at hand, we are now ready to show that with high probability,
where (i) follows from the triangle inequality, (ii) uses Cauchy-Schwarz and the independence between and , (iii) holds because of (95) and (312) under the condition , and (iv) holds true as long as .
Appendix D Technical lemmas
as long as for some sufficiently large constant . Here, are some universal constants.
This is an immediate consequence of [Ver12, Corollary 5.35].∎
provided that for some sufficiently large constant .
This is adapted from [CLS15, Lemma 7.4]. ∎
holds for some absolute constants , where
with being a standard Gaussian random variable.
This is supplied in [CC17, supplementary material]. ∎
D.1.2 Matrix perturbation bounds
Let , be the leading eigenvalue and eigenvector of a symmetric matrix , respectively, and , be the leading eigenvalue and eigenvector of a symmetric matrix , respectively. Suppose that for some . Then,
where the last inequality follows since . Using the identity , we have
where the last inequality comes from our assumptions on and . This combined with (313) yields
To control \left|\lambda_{1}\big{(}\bm{A}\big{)}-\lambda_{1}(\widetilde{\bm{A}})\right|, use the relationship between the eigenvalue and the eigenvector to obtain
D.2 Technical lemmas for matrix completion
The first lemma is concerned with the characterization of the minimizer of (315).
This is an immediate consequence of [TB77, Theorem 2]. ∎
where is defined above.
This is an immediate consequence of [Mat93, Theorem 2.3]. ∎
With Lemma 36 in place, we are ready to present the following bounds on two matrices after “aligning” them with .
Then the following two inequalities hold true:
Before proving the claims, we first gather some immediate consequences of the assumptions (317). Denote and . It is easily seen that is invertible since
where (i) follows from the assumption (317a) and (ii) is a direct application of Weyl’s inequality. In addition, is also invertible since
where (i) arises from the assumption (317b) and (ii) holds because of (318). When both and are invertible, the orthonormal matrices and admit closed-form expressions as follows
Moreover, we have the following bound on :
where (i) is the triangle inequality, (ii) uses the assumption (317a) and (iii) arises from the fact that .
where the first inequality uses the fact that and the last inequality comes from (319). An application of Lemma 36 leads us to conclude that
where (321) utilizes (318). Combine (320) and (322) to reach
which finishes the proof by noting that . ∎
D.2.2 Matrix concentration inequalities
This section collects various measure concentration results regarding the Bernoulli random variables , which is ubiquitous in the analysis for matrix completion.
Fix any small constant , and suppose that . Then with probability exceeding , one has
This result has been established in [CR09, Section 4.2] for asymmetric sampling patterns (where each , is included in independently). It is straightforward to extend the proof and the result to symmetric sampling patterns (where each , is included in independently). We omit the proof for conciseness. ∎
See [KMO10a, Lemma 3.2]. Similar to Lemma 38, the result therein was provided for the asymmetric sampling patterns but can be easily extended to the symmetric case. ∎
and for any constant , with probability exceeding
By the definition of and the triangle inequality, one has
Therefore, it suffices to control the first term. It can be seen that are i.i.d. zero-mean random matrices. Letting
and invoking matrix Bernstein’s inequality [Tro15b, Theorem 6.1.1], one has for all ,
We can thus find an upper bound on by finding a value that ensures the right-hand side of (323) is smaller than . Using this strategy and some simple calculations, we get
holds with probability at least . As a consequence, we have
and with probability exceeding ,
Suppose the sample size obeys . Then for any and large enough, with probability at least ,
where are some absolute constants.
For simplicity of presentation, we will prove the claim for the asymmetric case where are independent. The results immediately carry over to the symmetric case as claimed in this lemma. To see this, note that we can always divide into
which implies that is -Lipschitz with respect to the metric . Moreover,
according to our assumption. Hence, Talagrand’s inequality [CC18, Proposition 1] reveals the existence of some absolute constants such that for all
where the last relation holds since , which follows by combining the definitions of and , the sample size condition , and the incoherence condition (114). Thus, substitution into (324) and taking give
for any . Furthermore, invoking [AS08, Corollary A.1.14] and using the bound (325), one has
for any . Choose to obtain
So far we have demonstrated that for any fixed obeying our assumptions, is well controlled with exponentially high probability. In order to extend the results to all feasible , we resort to the standard -net argument. Clearly, due to the homogeneity property of , it suffices to restrict attention to the following set:
where . We then proceed with the following steps.
Clearly, this function is sandwiched between two indicator functions
Note that is more convenient to work with due to continuity.
Consider an -net [Tao12, Section 2.3.1] of the set as defined in (327). For any , one can find such a net with cardinality . Apply the union bound and (326) to yield
as long as is chosen to be sufficiently large.
One can then use the continuity argument to extend the bound to all outside the -net, i.e. with exponentially high probability,
This is fairly standard (see, e.g. [Tao12, Section 2.3.1]) and is thus omitted here.
Suppose the sample size obeys for some sufficiently large constant . Then with probability at least ,
where is any fixed constant.
To simplify the notations hereafter, we denote . With this notation in place, one can decompose
which together with the triangle inequality implies that
In the sequel, we bound and separately.
Recall from [Mat90, Theorem 2.5] the elementary inequality that
where for any matrix . In addition, for any matrix such that for all and , one has \big{\|}|\bm{C}|\big{\|}\leq\big{\|}|\bm{D}|\big{\|}. Therefore
Lemma 39 then tells us that with probability at least ,
for some universal constant , as long as . This together with the triangle inequality yields
provided that . Putting together the previous bounds, we arrive at
Regarding the second term , apply the elementary inequality (330) once again to get
In what follows, for simplicity of presentation, we will denote
To be precise, each is defined such that
which clearly satisfy (337); in words, is constructed by rounding up those entries of within a prescribed magnitude interval. Thus, it suffices to bound for every . To this end, we start with and use the definition of to get
where (i) arises from Lemma 44, with being a crude upper bound on the number of nonzero entries in each row and each column. This can be derived by applying the standard Chernoff bound on . The second inequality (ii) relies on the definitions of and . The last one (iii) follows from the incoherence condition (114). Besides, for any , by construction one has
where is as defined in (334). Here, we have used the fact that the magnitude of each entry of is at most 2 times that of . An immediate implication is that there are at most
nonzero entries in each row of and at most
for each . Combining all, we arrive at
where the last relation holds under the condition . This further gives
In order to finish the proof of this part, we need to justify the claim (334). Observe that
for every , where indicates whether the entry with the index is observed or not. Invoke Lemma 41 to yield
with high probability, as soon as . Combining (339) and (340) yields
Taken together, the preceding bounds (329), (333) and (338) yield
The proof is completed by substituting the assumption ∎
In the end of this subsection, we record a useful lemma to bound the spectral norm of a sparse Bernoulli matrix.
This immediately follows from the elementary inequality (see [Hig92, equation (1.11)]), where and are the induced 1-norm (or maximum absolute column sum norm) and the induced -norm (or maximum absolute row sum norm), respectively. ∎
D.2.3 Matrix perturbation bounds
Then there is some numerical constant such that
Define . The triangle inequality gives
as long as . For the remaining term in (341), one can use to obtain
which together with the Davis-Kahan sin theorem [DK70] reveals that
for some constant . Combine the estimates on \big{\|}\widehat{\bm{Q}}-\bm{Q}\big{\|}, and (341) to reach
for some numerical constant , where we have utilized the fact that . ∎
then there exists some numerical constant such that
where and are the matrix square roots of and , respectively. In view of the matrix square root perturbation bound [Sch92, Lemma 2.1],
where the last inequality follows from the lower estimates
and, similarly, . Recognizing that and , one gets
where the last relation holds due to the upper estimate
Invoke the Davis-Kahan sin theorem [DK70] to obtain
for some constant , where the last inequality follows from the bounds
Combine (342), (343), (344) and the fact to reach
Assume , and suppose is bounded by some constant . Then there exists a numerical constant such that
We first collect several useful facts about the spectrum of . Weyl’s inequality tells us that , which further implies that
It can be easily seen that , and
Regarding , use [AFWZ17, Lemma 3] to reach
where (i) and (iii) come from the unitary invariance of , and (ii) follows from the matrix square root perturbation bound [Sch92, Lemma 2.1]. We can further take the triangle inequality to obtain
where the last inequality uses the Weyl’s inequality and the fact that .
Rearrange the previous bounds to arrive at
for some numerical constant , where we have used the assumption that is bounded.
Recognizing that (see definition in (184)), we are ready to invoke Lemma 36 to deduce that
D.3 Technical lemmas for blind deconvolution
In this section, we formally prove the fundamental theorem of calculus and the mean-value form of Taylor’s theorem under the Wirtinger calculus; see (375) and (382), respectively.
With these relationships in place, we are ready to verify the fundamental theorem of calculus using the Wirtinger derivatives. Recall from [Lan93, Chapter XIII, Theorem 4.2] that
Substitute the identities (345) into (346) to arrive at
where , and
Repeating the above arguments, one can also show that
where is some point lying on the vector connecting and . This is the mean-value form of Taylor’s theorem under the Wirtinger calculus.
D.3.2 Discrete Fourier transform matrices
where with representing the imaginary unit. It is seen that for any ,
For any and any , we have
We first make use of the identity (383) to obtain
Without loss of generality, we focus on the case when in the sequel. Recall that for , we denote by the largest integer that does not exceed . We can continue the derivation to get
where (i) follows from and , and (ii) relies on the fact that . The property that for any allows one to further derive
where in (i) we extend the range of the summation, (ii) uses the elementary inequality and (iii) holds true as long as . ∎
The next lemma considers the difference of two inner products, namely, .
For all , we have
In addition, for any and , the following uniform upper bound holds
Given (383), we can obtain for and ,
where we also utilize the assumption . Then for , one has
Therefore, utilizing the property for any , we arrive at
where the last inequality holds since . Similarly we can obtain the upper bound for using nearly identical argument (which is omitted for brevity).
The uniform upper bound can be justified as follows
The last relation holds since for all . ∎
Next, we list two consequences of the above estimates in Lemma 50 and Lemma 51.
Fix any constant that is independent of and . Suppose for some sufficiently large constant , which solely depends on . If , then one has
For some constant , we can split the index set into the following three disjoint sets
With this decomposition in place, we can write
We first look at . By Lemma 49, one has for any ,
where the last inequality arises from and .
Similarly, for , we have
Regarding , we observe that
This together with the simple bound gives
The previous three estimates taken collectively yield
as long as and .∎
Fix any constant that is independent of and . Consider an integer , and suppose that for some large constant , which depends solely on . Then we have
The proof strategy is similar to the one used in Lemma 50. First notice that
As before, for some , we can split the index set into three disjoint sets
where the last inequality follows since and . A similar bound can be obtained for .
For the remaining set , observe that
This together with the crude upper bound gives
The previous estimates taken collectively yield
as long as and . ∎
D.3.3 Complex-valued alignment
which is the key function in the definition (34). Therefore, the alignment parameter of to is the minimizer of . This section is devoted to studying various properties of . To begin with, the Wirtinger gradient and Hessian of can be calculated as
The first lemma reveals that, as long as is sufficiently close to , the minimizer of cannot be far away from .
The first inequality is a direct consequence of the triangle inequality. Hence we concentrate on the second one. Notice that by assumption,
which immediately implies that . It thus suffices to show that for any obeying , one has , and hence it cannot be the minimizer. To this end, we lower bound as follows:
Given that and , we have
which together with the fact that implies
Taking the previous estimates collectively yields
It is self-evident that once one gets and hence cannot be the minimizer as according to (388). This concludes the proof. ∎
The next lemma reveals the local strong convexity of when is close to one.
where stands for the Wirtinger Hessian of .
We would like to demonstrate that this is at least on the order of . We first develop a lower bound on . Given the assumption that , one necessarily has
Thus, for any obeying , one has
as long as is sufficiently small. Regarding the second term , we utilizes the conditions , and to get
where the last relation holds since and is sufficiently small. Combining the previous bounds on and , we arrive at
as long as is sufficiently small. This completes the proof. ∎
for some sufficiently small constant . Denote by and the minimizers of and , respectively. Then we have
Since minimizes , the mean-value form of Taylor’s theorem (see Appendix D.3.1) gives
where is some complex number lying between and , and and are the Wirtinger gradient and Hessian of , respectively. Rearrange the previous inequality to obtain
as long as . This calls for evaluation of the Wirtinger gradient and Hessian of .
Regarding the Wirtinger Hessian, by the assumption (389), we can invoke Lemma 52 with to reach . This together with Lemma 53 implies
since lies between and .
For the Wirtinger gradient, since is the minimizer of , the first-order optimality condition [KD09, equation (38)] requires , which gives
Plug in the gradient expression (386) to reach
where the last line follows from the triangle inequality. It is straightforward to see that
under the condition (389) and the assumption , where the first inequality follows from Lemma 52. Taking these estimates together reveals that
The proof is accomplished by substituting the two bounds on the gradient and the Hessian into (390). ∎
Further, if two vector pairs are both close to the optimizer, then their distance after alignement (w.r.t. the optimizer) cannot be much larger than their distance without alignment, as revealed by the following lemma.
for some sufficiently small constant . Denote by and the minimizers of and , respectively. Then we have
To start with, we control the magnitudes of and . Lemma 52 together with the assumption (391) guarantees that
Now we can prove the lemma. The triangle inequality gives
where (i) holds since and , and (ii) arises from Lemma 54 that . Similarly,
where the last inequality comes from Lemma 54 as well as the facts that and as shown above. Combining all of the above bounds and recognizing that , we conclude the proof. ∎
Finally, there is a useful identity associated with the minimizer of as defined below.
Let and , then we have
We can rewrite the function as
The first-order optimality condition [KD09, equation (38)] requires
since , , and (otherwise and cannot be the minimizer). Furthermore, this condition is equivalent to
D.3.4 Matrix concentration inequalities
The proof for blind deconvolution is largely built upon the concentration of random matrices that are functions of . In this subsection, we collect the measure concentration results for various forms of random matrices that we encounter in the analysis.
Suppose for every , and are a set of fixed numbers. Then there exist some universal constants such that for all
This is a simple variant of [Ver12, Theorem 5.39], which uses the Bernstein inequality and the standard covering argument. Hence we omit its proof. ∎
Suppose for every . Then there exist some absolute constants such that for all , one has
where and denotes its cardinality.
The proof relies on Lemma 57 and the union bound. First, invoke Lemma 57 to see that for any fixed and for all , we have
for some constants , and as a result,
where denotes the smallest integer that is no smaller than . Here, (i) holds since we take the supremum over a larger set and (ii) results from (392) and the union bound. Apply the elementary inequality for any to obtain
where the second inequality uses whenever .
The proof is then completed by taking and . To see this, it is easy to check that since . In addition, one has , and . Combine the estimates above with (393) to arrive at
as claimed. Here (i) holds due to the facts that and . The inequality (ii) arises from the estimates listed above. ∎
Suppose . With probability exceeding , we have
The identity allows us to rewrite the quantity on the left-hand side as
where the ’s are independent zero-mean random matrices. To control the above spectral norm, we resort to the matrix Bernstein inequality [Kol11, Theorem 2.7]. To this end, we first need to upper bound the sub-exponential norm (see definition in [Ver12]) of each summand , i.e.
We further need to bound the variance parameter, that is,
where the last relation holds under the assumption that .∎
D.3.5 Matrix perturbation bounds
We also need the following perturbation bound on the top singular vectors of a given matrix. The following lemma is parallel to Lemma 34.
Let , and be the leading singular value, left and right singular vectors of , respectively, and let , and be the leading singular value, left and right singular vectors of , respectively. Suppose and are not identically zero, then one has
With regards to the second claim, we see that
Add these two inequalities to complete the proof. ∎