REVIEW 4 major objections 4 minor 2 cited by
Covariates-Adjusted Mixed-Membership Estimation: A Novel Network Model with Optimal Guarantees
T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read This paper claims that a convex logistic-likelihood estimator recovers both the covariate interaction matrix and the latent mixed-membership structure of a binary network at near-optimal rates, and that the proof can be carried out by…
desk verdict Plausible framework, unproven bridge: the convex guarantees are conditional on an unverified Assumption 7, so the main claim does not follow as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing machinery is the triple: the convex program (2) with logistic loss and nuclear norm, the nonconvex reparametrization $\Gamma=XY^\top$ with $P_Z X=P_Z Y=0$, motivated by $\|\Gamma\|_*=\min_{XY^\top=\Gamma}\tfrac12(\|X\|_F^2+\|Y\|_F^2)$, and the bridge theorem (Theorem H.1) that bounds the distance between the convex minimizer and the nonconvex solution by the projected gradient norm at the nonconvex point. The bridge uses a debiased estimator, namely one Newton step from the nonconvex solution, and a Taylor expansion of the logistic gradient around ground truth, with Assumption 7 giving the crucial spectral gap $\sigma_{r+1}\big(P_Z^\perp \tfrac1n M^*\odot(\cdot)P_Z^\perp\big)<1-\epsilon$ that makes the convex solution's subgradient condition hold.
What would settle it
Solve the linear system (77) in Appendix H.1 for the two-community example and check whether the solution really has the constant-block form asserted with the annotation 'Why???'; if not, Proposition 3.1, the only stated verification of Assumption 7, fails. More generally, simulate a CAMM instance satisfying Assumptions 2–6 but with $\sigma_{r+1}$ of the Assumption 7 matrix larger than $1-\epsilon$, and compare the convex solution with the ground-truth-initialized gradient path; a divergence between them at the predicted $1/\sqrt{n}$ separation would refute the equivalence step and the stated rates for the convex estimator.
Extended reading notes
Core claim
The central discovery, stated as Theorem 3.2 and Theorem 3.7, is that the convex estimator (2) achieves $\|\hat{H}_c-H^*\|_F \lesssim \lambda\sqrt{\mu r\kappa}/(n\sigma_{\min})$, $\|\hat{\Gamma}_c-\Gamma^*\|_F \lesssim \lambda\kappa\sqrt{\mu r}$, $\|\hat{\Gamma}_c-\Gamma^*\|_\infty \lesssim \mu r\kappa(\lambda\sigma_{\max}/(n^2\sqrt{\mu r})(1+n/\sigma_{\max})+\kappa\sqrt{\log n/n})$, and max row error $\max_i\|\hat{\pi}_i-\pi^*_i\|_1 \lesssim \lambda(\kappa^{1.5}\sqrt{\mu r}+\sqrt{\mu}\kappa r^{5/4})(\mu\kappa^{0.5}/\beta_n+\kappa\mu^{1.5}\sqrt{\beta_n})(r/(\sqrt{n}\,\bar\theta^*_2))^2$, with $\lambda\gtrsim \epsilon^{-1}(1+\mu r\sigma_{\max}/n)\sqrt{n\log n}$. In the bounded parameter regime these become $\sqrt{\log n/n}$ for $H$ and entrywise $\Gamma$, constant Frobenius error for $\Gamma$, and $\sqrt{\log n/n}$ for memberships. The argument establishes a chain: a ground-truth-initialized nonconvex gradient path stays within $1/\sqrt{n}$ of the truth; a Newton–Raphson debiased step isolates the systematic bias; and Assumption 7, controlling the $(r+1)$-th singular value of a projected weighted matrix, ensures the convex minimizer of (2) and the nonconvex solution coincide, transferring the nonconvex rates to the convex estimator.
Load-bearing premise
The load-bearing premise is Assumption 7, that a certain matrix built from unknown ground-truth parameters has its $(r+1)$-th singular value below $1-\epsilon$; this is what transfers the nonconvex guarantees to the convex estimator, it cannot be checked from data, and its only verification is a two-community example with an explicitly flagged unjustified step.
Editorial extensions
If this is right
- If Theorems 3.2 and 3.7 are correct, the CAMM estimator achieves the minimax-type $1/\sqrt{n}$ rates jointly for covariate effects and mixed memberships in binary networks, so covariates no longer need to be set aside or treated as noise.
- Entrywise control of $\hat\Gamma_c$ makes the subsequent vertex-hunting step (Mixed-SCORE style Algorithm 1) recover $\Pi^*$ at $1/\sqrt{n}$, which is the rate needed for inferential use of membership profiles.
- The convex–nonconvex transfer is proved for the logistic loss and claimed to extend to every convex loss, so pairwise-comparison ranking problems with covariates could inherit the same guarantees.
- The simulations and the S&P 500 analysis indicate the model is tractable in practice: a Nesterov-accelerated nuclear-norm program plus vertex hunting, with covariates explaining about 59% of the fitted interaction in the stock network.
Reading between the lines
- Editorial inference: Assumption 7 implicitly requires that the covariate-adjusted logistic likelihood have a unique well-separated low-rank component after projection; a data-driven proxy could be constructed by plugging estimated parameters into the same matrix and thresholding its $(r+1)$-th singular value, which would make the theory testable on real data.
- Editorial inference: if the flagged 'Why???' step in the two-community verification cannot be justified, the evidence for Assumption 7 is thinner than the theorems assume; the main results would still hold conditional on Assumption 7, but the claim that the assumption is 'nearly necessary and sufficient' and 'easy to satisfy' would remain unsubstantiated.
- Editorial inference: the same debiased-Newton bridge should adapt to logistic matrix completion and to networks with missing edges, where the noise is heteroskedastic in the same way; testing those settings would show how far the 'any convex loss' claim reaches.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Covariates-Adjusted Mixed-Membership (CAMM) model, in which edge probabilities are logistic functions of a quadratic covariate form z_i^T H* z_j plus a low-rank DCMM component Gamma*. It studies the convex regularized MLE (2) and claims near-optimal rates for H*, Gamma*, and the mixed memberships Pi*: O(sqrt(log n/n)) for H* and entrywise Gamma*, O(1) for Frobenius Gamma*, and O(sqrt(log n/n)) for the membership vectors in the bounded-parameter regime. The proof strategy is to analyze a hypothetical nonconvex gradient descent initialized at the ground truth, then to transfer its guarantees to the convex solution via a debiasing argument and a bridge theorem (Theorem H.1). The transfer is asserted to hold under Assumption 7, which is described as nearly necessary and sufficient for the equivalence of convex and nonconvex solutions. Simulation results confirm the rates in one setting (r=2, p=3), and a real-data analysis of S&P 500 stocks is presented.
Significance. If the main theorems were fully established, the paper would provide the first optimal-rate guarantees for convex mixed-membership estimation with binary edges and covariates, extending the nonconvex-to-convex transfer framework of Chen et al. (2020) to logistic loss and to general convex losses. The paper is also praiseworthy for its explicit goal of entrywise and 2-infinity control, its use of debiasing to identify the dominant error term, and its detailed leave-one-out analysis. However, the central bridge assumption (Assumption 7) is not verified for the general model, and the only special-case verification contains an explicitly flagged unjustified step. Because the main theorems are conditional on that unverified bridge, the paper's central contribution is currently unsupported. The manuscript therefore cannot be accepted in its present form.
major comments (4)
- [Section 3.1, Assumption 7; Theorems 3.2 and 3.7] The proof of the convex guarantees is entirely dependent on Assumption 7, which the paper itself describes (Section 4.2 and the paragraph after Assumption 7) as nearly necessary and sufficient for the equivalence between the convex estimator and the hypothetical nonconvex solution. No general verification of Assumption 7 is provided; it is stated in terms of unknown ground-truth quantities (D*, M*, X*, Y*, P*) and cannot be checked from data. Since the claimed optimal rates in Theorems 3.2 and 3.7 are for the convex program (2), the absence of a provable bridge means the central claim is conditional on an unverified, data-independent hypothesis. This is a load-bearing gap.
- [Appendix H.1, proof of Proposition 3.1] The only special-case verification of Assumption 7, for a two-community SBM with H*=0, is incomplete: after Eq. (77) the text reads 'Why???' before asserting that the solution must have the block-constant form (78). That block-constant form is then used to compute Delta and to verify the spectral bound sigma_3(...) < 1 - epsilon. Without a valid derivation of (78), the verification of Proposition 3.1 does not go through, and the paper's statement that Assumption 7 'holds in common settings such as stochastic block models' is unsupported. This is not a presentation issue; it is an explicit gap in the only evidence offered for the bridge assumption.
- [Section 4.2 and Theorem H.1] The bridge theorem (Theorem H.1) bounds the distance between the convex and nonconvex solutions by the projected gradient norm, but the proof of Claim H.3 repeatedly invokes Assumption 7 to control the (r+1)-th singular value of the Hessian-related matrix. No argument is given that Assumption 7 holds for the general CAMM model with nonzero H* and general covariates. The paper also claims that the analysis extends to all convex loss functions, but this claim is not substantiated beyond a remark; no formal statement or proof is given for the general loss case. These points, together, mean that the key innovation advertised in the abstract and introduction—the identification of a condition that bridges convex and nonconvex solutions—is not established for the model under study.
- [Section 5 and Theorem 3.2/3.7] The simulation study is too narrow to validate the claimed optimal rates: it fixes r=2 and p=3, uses lambda = sqrt(n) without explaining how lambda is chosen, reports no confidence intervals or slope estimates, and does not compare against any competing estimator. More importantly, the simulations do not verify Assumption 7, so they do not probe the validity of the bridge assumption. As a result, the simulations provide only weak empirical support for the central theoretical claim, even if the rates are correct under the assumptions.
minor comments (4)
- [Notation, Section 1] The paper defines vec(A) by stacking rows of A rather than columns; this is an unusual convention and should be flagged explicitly in the notation section, since readers of matrix completion papers will expect column-wise vectorization.
- [Section 6] The real-data analysis uses several ad hoc preprocessing choices (e.g., the edge threshold Sigma_ij > 0.16, lower-bound capping of covariates, and the finite-sample heuristic test based on 1000 shuffles) that are not given a formal justification. These choices are fine for an illustrative analysis, but the paper should present them as exploratory rather than as confirmatory evidence for the model.
- [Section 3.1, Assumption 7] The definition of M* and Delta involves the pseudoinverse of PD*P and the ground-truth matrices; the paper should state explicitly that Assumption 7 is a condition on the true generating mechanism and not on the data. A short discussion of when one might expect it to hold (beyond the SBM example) would improve readability.
- [Appendix H.1, Eq. (77)] The presence of the literal string 'Why???' in a published manuscript is highly unusual. Even if the step were correct, the authors should provide the missing justification; leaving the question mark in the text signals incompleteness and is not acceptable in a formal proof.
Circularity Check
No circular derivation: the convex-to-nonconvex bridge is an explicit assumption rather than a result that reduces to its own inputs, and the flagged 'Why???' is a missing proof, not a circular step.
full rationale
The central theorems are conditional: Theorem 3.2 is stated as 'Suppose Assumption 2-7 hold and n is sufficiently large,' and the convex/nonconvex transfer is proved in Theorem H.1 under Assumption 7. Assumption 7 is a spectral smallness condition on a ground-truth linearized operator; it is not identical to the conclusion of Theorem 3.2 or to the error bounds being claimed. The paper itself labels the assumption as the bridge ('Assumption 7 provides a necessary and sufficient condition for the equivalence between the convex and nonconvex solutions'), but that is an honest statement of what is assumed, not a derivation of the conclusion from itself. A genuinely circular step would require the theorem's conclusion to be inserted into its hypotheses by construction, e.g., defining the estimator so that its error is zero by definition or fitting a parameter and calling the fit a prediction. No such reduction appears here. The nonconvex path is explicitly an analyitic device initialized at the ground truth, not a fitted estimator reported as a prediction. The main weakness is evidential, not circular: Assumption 7 is not verified for the general CAMM model, and the only verification, Proposition 3.1, contains an explicitly unjustified step in Appendix H.1, where after Eq. (77) the text reads 'Based on the specific form of X* and Y*, it can be seen that the solutions must have the following form: Why???' before asserting the block-constant solution form (78). That is a missing proof or an error, and it weakens the support for the claimed general guarantees, but it does not make the derivation circular. The self-citations (notably Chen et al. 2020, which includes a coauthor) supply background technique and a technical helper claim, not a uniqueness theorem or an ansatz that smuggles in the target result, so they are not load-bearing circularity. Overall, the derivation is self-contained in the sense that every displayed bound follows from the stated assumptions; the concern is whether the key assumption is satisfied, which is a correctness and verification issue rather than a circularity issue.
Assumptions & free parameters
free parameters (3)
- lambda (regularization parameter) =
sqrt(n) in simulations; 18 in the S&P 500 analysis
- epsilon (spectral gap in Assumption 7) =
1/2 in the two-community SBM example
- Real-data preprocessing thresholds =
edge threshold 0.16; five removed principal components; covariate floors 0.01, 0.003, 0.03, 0.3
assumptions (8)
- domain assumption Identifiability: P_Z Gamma* = 0, |W*_ii| = 1, and each community contains a pure node (Assumption 1)
- domain assumption Scale and spectrum conditions: ||z_i|| <= sqrt(c_z), |P*_ij| <= c_P, and c n <= lambda_min(Z^T Z) <= lambda_max(Z^T Z) <= c_bar n (Assumptions 2-3)
- domain assumption mu-incoherence of Gamma* (Assumption 4)
- domain assumption Hessian spectrum and null-space incoherence of P D* P (Assumptions 5-6)
- ad hoc to paper Assumption 7: sigma_{r+1}(P^perp_Z (1/n M* circle (Z Delta_H Z^T + (Delta_X Y*^T + X* Delta_Y^T)/n)) P^perp_Z) < 1 - epsilon
- domain assumption Assumption 8: bounded degree heterogeneity, well-conditioned W* G, spectral gap of W* G, and positive first eigenvector (from Jin et al. 2023)
- standard math Background results: matrix Bernstein, Davis-Kahan, Weyl, Stewart's pseudoinverse perturbation, the Srebro-Shraibman nuclear norm identity, and Ma et al. (2018) Lemmas 20, 36, 37
- standard math DCMM identifiability and Mixed-SCORE guarantees of Jin et al. (2017, 2023)
Cite this review
Pith. "Pith review of Covariates-Adjusted Mixed-Membership Estimation: A Novel Network Model with Optimal Guarantees." pith.science (2026). https://pith.science/paper/QT46E4SF
@misc{pith2026250206671,
author = {Pith},
title = {Pith review of: Covariates-Adjusted Mixed-Membership Estimation: A Novel Network Model with Optimal Guarantees},
year = {2026},
howpublished = {\url{https://pith.science/paper/QT46E4SF}},
note = {Machine review of arXiv:2502.06671}
}
read the original abstract
This paper addresses the problem of mixed-membership estimation in networks, where the goal is to efficiently estimate the latent mixed-membership structure from the observed network. Recognizing the widespread availability and valuable information carried by node covariates, we propose a novel network model that incorporates both community information, as represented by the Degree-Corrected Mixed Membership (DCMM) model, and node covariate similarities to determine connections. We investigate the regularized maximum likelihood estimation (MLE) for this model and demonstrate that our approach achieves optimal estimation accuracy for both the similarity matrix and the mixed-membership, in terms of both the Frobenius norm and the entrywise loss. Since directly analyzing the original convex optimization problem is intractable, we employ nonconvex optimization to facilitate the analysis. A key contribution of our work is identifying a crucial assumption that bridges the gap between convex and nonconvex solutions, enabling the transfer of statistical guarantees from the nonconvex approach to its convex counterpart. Importantly, our analysis extends beyond the MLE loss and the mean squared error (MSE) used in matrix completion problems, generalizing to all the convex loss functions. Consequently, our analysis techniques extend to a broader set of applications, including ranking problems based on pairwise comparisons. Finally, simulation experiments validate our theoretical findings, and real-world data analyses confirm the practical relevance of our model.
Figures
Forward citations
Cited by 2 Pith papers
-
AI-Augmented Statistical Network Estimation with Proxy Gene Embeddings
PLANE jointly estimates latent gene positions from a target network and proxy embeddings on a larger gene set, with provably optimal channel weighting and demonstrated gains in network recovery and imputation.
-
Uncertainty Quantification for Ranking with Heterogeneous Preferences
A debiased regularized estimator provides entrywise-accurate scores and uncertainty quantification for heterogeneous Bradley-Terry-Luce rankings.
Reference graph
Works this paper leans on
-
[1]
We first bound (1). Note that (1)2 = vec [ Ht−H∗ FtRt−F∗ ]T (I− 2ηA +η2A2)vec [ Ht−H∗ FtRt−F∗ ] = ‖‖‖‖ [Ht−H∗ FtRt−F∗ ]‖‖‖‖ 2 F − 2ηvec [Ht−H∗ FtRt−F∗ ]T A vec [Ht−H∗ FtRt−F∗ ] +η2vec [Ht−H∗ FtRt−F∗ ]T A2 vec [Ht−H∗ FtRt−F∗ ] . By Lemma B.1, we have vec [Ht−H∗ FtRt−F∗ ]T A vec [Ht−H∗ FtRt−F∗ ] ≥C ‖‖‖‖ [Ht−H∗ FtRt−F∗ ]‖‖‖‖ 2 F , vec [Ht−H∗ FtRt−F∗ ]T A2 ve...
-
[2]
(16) Proof. See Appendix F.5. Lemma C.6. If Lemma C.1-Lemma C.4 hold for all0≤ t≤ t0 and Lemma C.5 holds for all 1≤t≤t0, we then have min 0≤t<t0 ‖‖P∇f(Ht,F t) ‖‖ 2 ≲n−5, as long asηt0≥n12. Proof. See Appendix F.6. D Properties of debiased nonconvex estimator Let t∗ := arg min0≤t<t0 ‖‖P∇f(Ht,F t) ‖‖ 2. And we denote( ˆH, ˆX, ˆY ) = (Ht∗ ,Xt∗ Rt∗ ,Y t∗ Rt∗ ...
-
[3]
Note that ∇Xfdiff(FtRt) = 4caug n2 Xt(XtTXt−YtTYt)Rt, ∇Yfdiff(FtRt) = 4caug n2 Yt(YtTYt−XtTXt)Rt
We then bound (2). Note that ∇Xfdiff(FtRt) = 4caug n2 Xt(XtTXt−YtTYt)Rt, ∇Yfdiff(FtRt) = 4caug n2 Yt(YtTYt−XtTXt)Rt. Thus, we have ∥∇fdiff(FtRt)∥2 = ‖‖‖‖‖‖ vec 0 ∇Xfdiff(FtRt) ∇Yfdiff(FtRt) ‖‖‖‖‖‖ 2 = ‖‖‖‖ [∇Xfdiff(FtRt) ∇Yfdiff(FtRt) ]‖‖‖‖ F ≤ 4caug n2 ( ∥Xt(XtTXt−YtTYt)Rt∥F +∥Yt(YtTYt−XtTXt)Rt∥F ) ≤ 4caug n2 ( ∥Xt∥ +∥Yt∥ ) ∥XtTXt−YtTYt∥F. 41 Sin...
-
[4]
We then bound (3). Note that X∗TX∗ = Y∗TY∗. Thus, we have ∇fdiff(F∗) = 0 , which implies∇faug(H∗,F∗) =∇f(H∗,F∗). By Lemma F.1, we have (3) =∥∇f(H∗,F∗)∥2 ≲cz √ p logn +λ√µrσmax ≲λ√µrσmax as long asc2 zp≪n. Consequently, we conclude that ‖‖‖‖vec [Ht−H∗−η∇Hf(Ht,F tRt) FtRt−F∗−η∇Ff(Ht,F tRt) ]‖‖‖‖ 2 ≤ ( 1− C 2η )‖‖‖‖ [Ht−H∗ FtRt−F∗ ]‖‖‖‖ F + 16ηcaug n2 ∥F∗∥∥X...
-
[5]
We first bound (1). Since Lemma C.2 and Lemma C.4 hold for thet-th iteration, we have ‖‖‖Ht,(m) +τ ( Ht−Ht,(m) ) −H∗ ‖‖‖ F ≤∥Ht−H∗∥F + (1−τ)∥Ht,(m)−Ht∥F≤c11 √n +c21≤c2 √n ‖‖‖Ft,(m)Ot,(m) +τ ( FtRt−Ft,(m)Ot,(m) ) −F∗ ‖‖‖ 2,∞ ≤∥FtRt−F∗∥2,∞ + (1−τ)∥Ft,(m)Ot,(m)−FtRt∥2,∞ ≤∥FtRt−F∗∥2,∞ +∥Ft,(m)Ot,(m)−FtRt∥F≤c41 +c21≤c3. Thus Lemma B.1 can be applied to bound t...
-
[6]
We then bound (2). Note that (2) =∇L(m)(Ht,(m),F t,(m)Ot,(m))−∇L(Ht,(m),F t,(m)Ot,(m)) = vec ∑ i̸=m ( eP∗ im 1 +eP∗ im −Aim ) zizT m 1 neieT mYt,(m)Ot,(m) 1 nemeT i Xt,(m)Ot,(m) + ∑ i̸=m ( eP∗ mi 1 +eP∗ mi −Ami ) zmzT i 1 nemeT i Yt,(m)Ot,(m) 1 neieT mXt,(m)Ot,(m) . Since the first and second terms are similar, we only focus on boundin...
-
[7]
Notice that ∥Ft,(m)∥ =∥Ft,(m)Ot,(m)∥≤∥ Ft,(m)Ot,(m)−FtRt∥ +∥FtRt−F∗∥ +∥F∗∥≤ 2∥F∗∥
We then bound (3). Notice that ∥Ft,(m)∥ =∥Ft,(m)Ot,(m)∥≤∥ Ft,(m)Ot,(m)−FtRt∥ +∥FtRt−F∗∥ +∥F∗∥≤ 2∥F∗∥. Then following the same argument as bounding term (2) in Appendix F.1, we have ∥∇Ffdiff(Ht,F tRt)∥F ≲ caug n2∥F∗∥∥XtTXt−YtTYt∥F, ∥∇Ffdiff(Ht,(m),F t,(m)Ot,(m))∥F ≲ caug n2∥F∗∥∥Xt,(m)TXt,(m)−Yt,(m)TYt,(m)∥F. Thus, it holds that ∥(3)∥2 ≲ caug n2∥F∗∥ ( ∥XtTX...
-
[8]
For (a), by Cahuchy-Schwarz, we have ∥(a)∥2≤ ‖‖‖‖ ( Xt,(m)Rt,(m)−X∗ ) m,· ‖‖‖‖ 2 ∥Yt,(m)Rt,(m)−Y∗∥F∥Y∗∥F. Note that ‖‖‖‖ ( Xt,(m)Rt,(m)−X∗ ) m,· ‖‖‖‖ 2 ≤c31 ∥Yt,(m)Rt,(m)−Y∗∥F ≤∥Yt,(m)Rt,(m)−YtRt∥F +∥YtRt−Y∗∥F ≤ 5κ∥Yt,(m)Ot,(m)−YtRt∥F +∥YtRt−Y∗∥F (by Lemma J.3) ≤ 5κc21 +c11 √n ≲c11 √n ∥Y∗∥F≤√µrσmax. Thus, we have ∥(a)∥2 ≲c11c31 √µrσmaxn. (37) 49
Show all 26 references
-
[9]
Moreover, we have ∥Yt,(m)∥≤∥ Ft,(m)Ot,(m)−FtRt∥ +∥FtRt−F∗∥ +∥F∗∥≤ 2∥F∗∥
For (b), note that ‖‖‖‖‖‖ ∑ i̸=m eci (1 +eci)2 ( ⟨Ht,(m)−H∗,zmzT i⟩ ) ei ‖‖‖‖‖‖ 2 ≤ 1 4 √∑ i̸=m ⏐⏐⟨Ht,(m)−H∗,zmzT i⟩ ⏐⏐2 ≤ 1 4∥Ht,(m)−H∗∥∥zm∥2 √∑ i̸=m ∥zi∥2 2 ≤ cz 4√n∥Ht,(m)−H∗∥. Moreover, we have ∥Yt,(m)∥≤∥ Ft,(m)Ot,(m)−FtRt∥ +∥FtRt−F∗∥ +∥F∗∥≤ 2∥F∗∥. Thus, we have ∥(b)∥2≤ cz...
-
[10]
Thus, we have ∥(c)∥2 ≲∥F∗∥∥F∗∥2,∞ ‖‖‖Yt,(m)Rt,(m)−Y∗ ‖‖‖≲√µrc11σmax
For (c), note that ‖‖‖‖‖‖ ∑ i̸=m eci (1 +eci)2 ( (Xt,(m)Rt,(m)) ( Yt,(m)Rt,(m)−Y∗ )T) mi ei ‖‖‖‖‖‖ 2 ≤ 1 4 ‖‖‖‖‖ ( (Xt,(m)Rt,(m)) ( Yt,(m)Rt,(m)−Y∗ )T) m,· ‖‖‖‖‖ 2 = 1 4 ‖‖‖‖(Xt,(m)Rt,(m))⊤ m,· ( Yt,(m)Rt,(m)−Y∗ )T‖‖‖‖ 2 ≤ 1 4 ‖‖‖(Xt,(m)Rt,(m))m,· ‖‖‖ 2 ‖‖‖Yt,(m)Rt,(m)−Y∗ ‖‖‖ ...
-
[11]
For (d), we have ∥(d)∥2≤ ‖‖‖Xt,(m)Rt,(m) ‖‖‖ 2,∞ ≤ ‖‖‖Ft,(m)Rt,(m)−F∗ ‖‖‖ 2,∞ +∥F∗∥2,∞≤ 2∥F∗∥2,∞ ≲ √µrσmax n . (40) 50
-
[12]
Finally, we bound (e). We denote (1) := Xt,(m) m,· Rt,(m)−X∗ m,·−η 1 n ∑ i̸=m ( eP t,(m) mi 1 +eP t,(m) mi − eP∗ mi 1 +eP∗ mi ) eT i Yt,(m) +λXt,(m) m,· Rt,(m) = Ir− η n2 ∑ i̸=m eci (1 +eci)2 (Y∗ i,·)(Y∗ i,·)⊤ ( Xt,(m)Rt,(m)−X∗ ) m,· − η n2 (a)− η n(b)...
2020
-
[13]
Therefore, as long asn≥ 16(r3 +rp)c2 2,∞, we have∥Qv∥2 2≥∥v∥2 2/2
(48) On the other hand, we have ∥Qv∥2 2≥ r∑ j=1 (Qv)2 p2+(m−1)r+j = r∑ j=1 ( vp2+(m−1)r+j− ((I−Q)v)p2+(m−1)r+j )2 ≥ r∑ j=1 v2 p2+(m−1)r+j− 2 r∑ j=1 ⏐⏐vp2+(m−1)r+j ⏐⏐ ∥(I−Q)v∥∞ ≥∥v∥2 2− 2√r∥v∥2∥I−Q∥2,∞∥v∥2≥ ( 1− 2c2,∞ √ r3 +rp n ) ∥v∥2 2 56 according to Assumption 6. The...
2020
-
[14]
By Lemma G.1, we have max{∥(P ˆDP)†∥2,∥(PD∗P)†∥2} ≲ 1 c2 D∗ , ∥P ˆDP−P D∗P∥ ≲ ˆc√n
For (1), by Theorem 3.3 in Stewart (1977), we have ∥(PD∗P)†− (P ˆDP)†∥≤ 1 + √ 5 2 max{∥(P ˆDP)†∥2,∥(PD∗P)†∥2}·∥P ˆDP−P D∗P∥. By Lemma G.1, we have max{∥(P ˆDP)†∥2,∥(PD∗P)†∥2} ≲ 1 c2 D∗ , ∥P ˆDP−P D∗P∥ ≲ ˆc√n. Thus, we obtain ∥(PD∗P)†− (P ˆDP)†∥ ≲ ˆc c2 D∗ √n. Further, as shown...
1977
-
[15]
DenoteVt = ˆV +t(V∗− ˆV ) and defineDt correspondingly
We then bound (2). DenoteVt = ˆV +t(V∗− ˆV ) and defineDt correspondingly. Following the same argument as in the proof of Lemma G.1, we have ∥PDtP−P D∗P∥ ≲ ˆc√n. Further, as already being shown in the proof of Lemma B.1, we have ∥∇2L(Vt)−Dt∥ ≲ 1 n· (√ c∥ ˆH−H∗∥F + 1 n∥X∗∥∥ ˆF−...
-
[16]
For (3), we have (3)≤∥ (PD∗P)†∥∥∇2L(V∗)−D∗∥∥V∗− ˆV∥F ≲ 1 cD∗ · √logn n ·c11 √n = c11 cD∗ √ logn n
-
[17]
Combine the bounds for (1)-(4), we have ‖‖‖‖ [ˆXd− ¯X ˆYd− ¯Y ]‖‖‖‖ ∞ ≲ λˆc c2 D∗ √µrσmax n + c11ˆc cD∗ +c2,∞c11 √ r2 +p =c∞
Finally, for (4), we have (4)≤ ‖‖I− (PD∗P)†(PD∗P) ‖‖ 2,∞∥V∗− ˆV∥F≤c2,∞c11 √ r2 +p, where the last inequality follows from Assumption 6. Combine the bounds for (1)-(4), we have ‖‖‖‖ [ˆXd− ¯X ˆYd− ¯Y ]‖‖‖‖ ∞ ≲ λˆc c2 D∗ √µrσmax n + c11ˆc cD∗ +c2,∞c11 √ r2 +p =c∞. Consequently, i...
-
[18]
We denote [Ht Γt ] :=c(V∗) +t(c( ˆVd)−c(V∗)), Pt ij :=zT i Htzj + Γt ij n
We first bound (1). We denote [Ht Γt ] :=c(V∗) +t(c( ˆVd)−c(V∗)), Pt ij :=zT i Htzj + Γt ij n . It then holds that ∇2Lc ( c(V∗) +t(c( ˆVd)−c(V∗)) ) −∇ 2Lc(c(V∗)) = ∑ i̸=j ( eP t ij (1 +eP t ij)2 − eP∗ ij (1 +eP∗ ij)2 )[vec(zizT j ) 1 n vec(eieT j ) ]⊗2 . Thus, we have ( c( ¯V ...
-
[19]
Note that ∇Lc(c( ˆVd))T ( c( ¯V )−c( ˆVd) ) =∇Lc(c( ˆV ))⊤ ( c( ¯V )−c( ˆVd) ) + ( c( ¯V )−c( ˆVd) )⊤∫1 0 ∇2Lc ( c( ˆV ) +t(c( ˆVd)−c( ˆV )) ) dt ( c( ˆVd)−c( ˆV ) )
We then bound (2). Note that ∇Lc(c( ˆVd))T ( c( ¯V )−c( ˆVd) ) =∇Lc(c( ˆV ))⊤ ( c( ¯V )−c( ˆVd) ) + ( c( ¯V )−c( ˆVd) )⊤∫1 0 ∇2Lc ( c( ˆV ) +t(c( ˆVd)−c( ˆV )) ) dt ( c( ˆVd)−c( ˆV ) ) . (64) 74 For the first term, recall the definition of∆′′, we have ∇Lc(c( ˆV ))T ( c( ¯V )−c...
-
[20]
We finally bound (3). By (60) withV = ¯V, we have ∇¯Lc ( c( ¯V ) ) =∇Lc (c(V∗)) +∇2Lc (c(V∗)) ( c( ¯V )−c(V∗) ) , which then implies ∇¯Lc ( c( ¯V ) )T( c( ¯V )−c( ˆVd) ) =∇Lc (c(V∗))T ( c( ¯V )−c( ˆVd) ) + ( c( ¯V )−c( ˆVd) )T ∇2Lc (c(V∗)) ( c( ¯V )−c(V∗) ) . (71) We will deal...
-
[21]
Thus, it remains to deal with1 nM∗⊙ (P−P∗)
(91) 89 Moreover, as shown in the proofs of Lemma F.1, we have ∥∇ΓLc(H∗, Γ∗)∥ ≲ √ logn n < ϵλ 10 (92) as long asϵλ> √ logn n . Thus, it remains to deal with1 nM∗⊙ (P−P∗). Note that 1 nM∗⊙ (P−P∗) = 1 nM∗⊙ ( ˆPd− ¯P ) /bracehtipupleft/bracehtipdownright/bracehtipdownleft/braceht...
-
[22]
By Theorem D.3, we obtain ∥(1)∥ ≲ √ ccd n3/4 < ϵλ 10 (94) as long asn is large enough
For (1), note that ∥(1)∥≤ ‖‖‖‖ 1 nM∗⊙ ( ˆPd− ¯P ) ‖‖‖‖ F ≤ 1 4n √∑ i̸=j ( ˆPd ij− ¯Pij)2 ≲ 1 n (√ c∥ ˆHd− ¯H∥F + 1 n∥ ˆXd ˆYd⊤− ¯X ¯Y⊤∥F ) , where the last inequality follows the same trick we used before and we omit the details here. By Theorem D.3, we obtain ∥(1)∥ ≲ √ ccd n3...
-
[23]
By Proposition D.2, we have ∥(2)∥ ≲c′ a (√ c n + √σmax n3/2 ) < ϵλ 10 (95) as long asϵλ>c ′ a (√ c n + √σmax n3/2 )
For (2), note that ∥(2)∥≤ ‖‖‖‖ 1 nM∗⊙ ( ¯P−P∗) ‖‖‖‖ F ≤ 1 4n √∑ i̸=j ( ¯Pij−P∗ ij)2 ≲ 1 n (√ c∥ ¯H−H∗∥F + 1 n∥ ¯X ¯Y⊤−X∗Y∗⊤∥F ) . By Proposition D.2, we have ∥(2)∥ ≲c′ a (√ c n + √σmax n3/2 ) < ϵλ 10 (95) as long asϵλ>c ′ a (√ c n + √σmax n3/2 ) . 90
-
[24]
We denote ˆ∆ such that ˆ∆H ˆ∆X ˆ∆Y = ˆHd−H ˆXd−X ˆYd−Y . With a little abuse of notation, we denote(∆H, ∆X, ∆Y ) such that ∆H ∆X ∆Y = (PD∗P)† 0 λX∗ λY∗ , Then by Assumption 7, we have σr+1 ( P⊥ Z ( 1 nM∗⊙ ( z⊤ i ∆Hzj + (∆XY∗T +X∗∆⊤ Y )ij n ) ij ...
1977
-
[25]
Thus, we have ˆU = ˆX(ˆΣ 1 2Q)−1, ˆU⊤ ˆX = ˆΣ 1 2Q U∗ =X∗(Σ∗ 1 2 )−1, U ∗⊤X∗ = Σ∗ 1
-
[26]
(123) It then holds that ∥ ˆU ˆR−U∗∥2,∞ =∥ ˆX(ˆΣ 1 2Q)−1 ˆR−X∗(Σ∗ 1 2 )−1∥2,∞ ≤∥ ( ˆX−X∗)(Σ∗ 1 2 )−1∥2,∞ +∥ ˆX(Q−1 ˆΣ− 1 2 ˆR− Σ∗− 1 2 )∥2,∞ ≤∥ Σ∗− 1 2∥∥ ˆX−X∗∥2,∞ +∥Q−1 ˆΣ− 1 2 ˆR− Σ∗− 1 2∥∥ ˆX∥2,∞ ≤ 1√σmin c41 + 2∥Q−1 ˆΣ− 1 2 ˆR− Σ∗− 1 2∥ √µrσmax n , (124) where the last ine...
2024
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.