Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion

Manit Paul; Raaz Dwivedi; Tathagata Sadhukhan

REVIEW 2 major objections 3 minor 37 references

Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A two-sided nearest-neighbor estimator achieves the nonparametric minimax optimal mean-squared-error rate for matrix completion under a Hölder-smooth latent factor model, without observing row or column latent factors, and the same rate…

desk verdict Plausible and important extension of two-sided nearest neighbors to Holder lambda<1, but the central MSE proof has a load-bearing gap in the B1 bias term, so the minimax claim is unproved as written. read the letter →

arxiv 2411.12965 v2 pith:RIDDFFTC submitted 2024-11-20 stat.ML cs.LGmath.STstat.MEstat.TH

Tathagata Sadhukhan , Manit Paul , Raaz Dwivedi This is my paper · ORCID

classification stat.MLcs.LGmath.STstat.MEstat.TH MSC 62G0862C2062D10

keywords nearestneighbormatrixcompletionHöldersmoothnessmissingnotatrandomminimaxoptimalratelatentfactormodelnonparametricregression

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper analyzes the two-sided nearest-neighbor (TS-NN) estimator for matrix completion when the entries satisfy $\theta_{i,j} = f(u_i, v_j)$ with unknown row and column latent factors and an unknown Hölder-continuous function $f$ with smoothness $\lambda \in (0,1]$. Its central claim is that TS-NN achieves the nonparametric minimax optimal mean-squared-error rate $(mn)^{-2\lambda/(2\lambda+d_1+d_2)}$ in a moderate row/column scaling regime, matching an oracle that knows the latent factors, even though neither the factors nor $f$ are observed. The result covers both missing-completely-at-random data and missing-not-at-random (MNAR) data, where the observation probability may depend on the latent factors and some entries may be missing deterministically. Earlier nearest-neighbor theory required Lipschitz smoothness or lower-bounded observation probabilities, so this extends simple averaging rules to rougher signals and realistic missingness. The paper also gives entrywise error bounds, an asymptotic normality result that yields confidence intervals, and simulations plus a HeartSteps mobile-health case study.

What carries the argument

The load-bearing object is the TS-NN estimator: it estimates pairwise row distances by averaging squared differences of observed entries across common columns (minus $2\sigma^2$), does the same for columns, thresholds these distances at $\eta_{\mathrm{row}}$ and $\eta_{\mathrm{col}}$ to form neighborhoods, and predicts $\hat{\theta}_{i,j}$ as the average of observed entries in the intersection of row $i$'s and column $j$'s neighborhoods. The proof rests on a distance-concentration lemma showing the estimated distances track their population counterparts, a bias–variance decomposition in which the bias is controlled by Hölder continuity and the variance by neighborhood size, and a sub-sampling step that caps neighborhood sizes so that Hoeffding-type noise concentration applies. Under MNAR, Assumption 6 replaces the MCAR observation probability $p$ by a lower bound $g(\delta)$ on the observed fraction of each neighborhood, which is shown via weighted Bernoulli concentration to hold in examples with up to roughly 50% deterministic missingness.

What would settle it

Run TS-NN on $f(u,v)=|u+v|^{0.5}\operatorname{sign}(u+v)$ with uniform latent factors, $n=m$, and an MNAR mask that sets $A_{i,j'}=0$ for a fixed target row $i$ at columns where most neighbor rows are observed while keeping Assumption 6 satisfied overall; if the pointwise error at $(i,j)$ or the population MSE decays at a rate strictly worse than $n^{-4\lambda/(2\lambda+2)}$, the bias replacement in Eq. (16) of Appendix A is doing real work and the stated rate is not a consequence of the stated assumptions.

Watch

Extended reading notes

Core claim

The paper's core discovery, stated as Corollary 1 and Theorem 2, is that TS-NN($\eta$) with $\eta_{\mathrm{row}} = \eta_{\mathrm{col}} = \Theta((mn)^{-\lambda/(2\lambda+d_1+d_2)})$ attains $\mathrm{MSE} = O((mn)^{-2\lambda/(2\lambda+d_1+d_2)})$ under the Hölder factor model, provided $n = \omega(m^{d_1/(2\lambda+d_2)})$ and $n = O(m^{(2\lambda+d_1)/d_2})$. The same rate persists under MNAR missingness when each neighborhood retains at least a constant fraction of observed pairs (Assumption 6), and the analysis is claimed to be the first to handle unknown row and column factors, Hölder smoothness with $\lambda < 1$, and missingness not at random simultaneously. At the entrywise level, Theorem 3 gives a slower pointwise rate with exponent $2\lambda/(2\lambda+d_1+d_2+d_1d_2/\lambda)$, and Theorem 4 gives asymptotic normality of each estimate, so that confidence intervals can be formed from the neighborhood average and an estimated noise level.

Load-bearing premise

The proof of the optimal rate assumes that averaging over a target row's neighbor rows can be reduced to the target row's own column differences and its own observed entries, so a neighbor row's column-to-column difference is no larger than the target row's and the target's observed entries proxy for the neighbors'; Hölder continuity does not imply this, and the replacement fails when the target entry is missing while its neighbors' entries are observed.

Editorial extensions

If this is right

TS-NN matches the minimax nonparametric rate without observing $u_i$, $v_j$, or $f$, so in the moderate scaling regime simple two-sided averaging is statistically as good as knowing the latent structure.
The MSE exponent $2\lambda/(2\lambda+d_1+d_2)$ varies continuously with the Hölder smoothness $\lambda$, so the estimator automatically benefits from smoother signals; simulations confirm steeper decay for $\lambda=0.75$ and $\lambda=1$ than for $\lambda=0.5$.
Under Assumption 6, the same rate survives missingness that depends on the latent factors, including deterministic missingness of a substantial fraction of entries, which covers realistic recommender-system and micro-randomized-trial settings such as HeartSteps.
Pointwise asymptotic normality means that uncertainty about a single entry can be reported as a confidence interval without refitting or bootstrapping, provided the noise level is consistently estimated.
Because $\eta_{\mathrm{col}} \to 0$ recovers row-nearest-neighbor and $\eta_{\mathrm{row}} \to 0$ recovers column-nearest-neighbor, TS-NN is theoretically never worse than its one-sided counterparts.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An implicit condition in the proof, not listed as an assumption, is that each target row's observed entries can serve as surrogates for its neighbors' observed entries; a testable extension is that the rate should degrade when missingness is concentrated on target rows while their neighbors stay observed, even under Assumption 6.
The moderate scaling conditions $n = \omega(m^{d_1/(2\lambda+d_2)})$ and $n = O(m^{(2\lambda+d_1)/d_2})$ suggest that for strongly rectangular matrices the two-sided method may lose its edge and one-sided NN could be preferable; this is an extrapolation from the rate conditions, not a result proved in the paper.
The same bias-variance machinery would likely extend to smoother function classes (for example, smooth reproducing-kernel-Hilbert-space functions) or to dependent latent factors, since the core argument only uses local Hölder control; the paper itself leaves these as open directions.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know. The paper works on a question that matters—two-sided nearest neighbors for matrix completion with unknown latent factors and Holder f with lambda<1—and the intended contribution would be genuinely useful. But the central MSE proof has a real gap: the step labeled (i) in the B1 bias bound (Appendix A, Eq. (16), reused in Theorem 2 as Eq. (30)) is not justified. For fixed (i,j), the proof replaces sum over i' in N_row(i) of (f(i',j')-f(i,j'))^2 A_{i',j'} by (f(i,j')-f(i,j))^2 A_{i,j'} |N_row(i)|. Holder continuity plus the row-neighborhood definition only controls an average over columns of squared row differences; it does not control the pointwise deviation at a single column j'. The missingness indicator also changes from A_{i',j'} to A_{i,j'}, so the bound fails when the target cell is missing while several neighbor rows are observed. This is not cosmetic: the optimized rate in Corollary 1 and the MNAR analogue in Theorem 2 both pass through this step. As written, the main claims do not follow.

What is genuinely new: both factors unknown, smoothness below Lipschitz, and MNAR missingness is a real extension of Yu (2022) and Dwivedi et al. (2022b), and the pointwise CLT is a useful addition if it can be proved cleanly. The simulations are honest and reasonably extensive, and the HeartSteps case study is a sensible sanity check. The self-citations to the authors' earlier papers are for auxiliary concentration tools, not for the target result, so I do not see circularity.

Other soft spots are secondary. The proof describes a subsampled, sample-split variant while Section 3 presents plain TS-NN; the appendix says the computations continue to hold without sample-splitting but does not show it. The CLT exponent issue the reader flagged looks repairable via Cauchy-Schwarz and Assumption 7, so I would not hang a rejection on that.

Bottom line: the right audience is researchers in nonparametric matrix completion; the problem is important, the paper is readable, and the gap may be patchable, but it is load-bearing. I would not accept the current version. I would send it to referees rather than desk-reject, with clear instructions that the B1 step needs a real fix or a weakened claim.

Referee Report

2 major / 3 minor

Summary. The paper studies two-sided nearest-neighbor (TS-NN) matrix completion under a non-linear latent factor model in which the latent function f is (λ,L)-Hölder with λ ≤ 1 and the row and column latent factors are unobserved. The main theoretical claims are a high-probability MSE bound for MCAR missingness (Theorem 1), an optimized rate matching the non-parametric minimax rate in a moderate scaling regime (Corollary 1), an extension to MNAR missingness under a lower-bound condition on the number of observed neighbors (Theorem 2), pointwise guarantees (Theorem 3), and asymptotic normality of the TS-NN estimate (Theorem 4). The paper also reports simulations and a HeartSteps case study. The central proof step used to control the B1 bias term in Theorem 1 is invalid, and the same step is reused in Theorem 2; as a result the main MSE optimality claims are not established as written.

Significance. If the main results were valid, the paper would be of clear interest: it claims adaptive minimax-optimal rates for TS-NN without knowledge of latent factors, handles Hölder smoothness below Lipschitz, and extends to MNAR settings with deterministic missingness. The paper is well organized, the algorithm is simple, and the simulation study is extensive. The paper also makes explicit, falsifiable rate predictions that are checked empirically. However, the central proof gap in the B1 bias bound is load-bearing: it is the step through which the optimized rates of Corollary 1 and the MNAR corollary are obtained. A secondary issue is that 'minimax optimal' is asserted without a stated or proved lower bound for the model class. These concerns outweigh the paper's strengths for the current version.

major comments (2)

[Appendix A, proof of Theorem 1, Eq. (16), step (i)] The bound for the bias term B1 replaces the double sum over neighbor rows i' and neighbor columns j' of (f(i',j')-f(i',j))^2 A_{i',j'} by a term in which the row sum is collapsed to the target row i: the displayed step (i) effectively uses |N_row(i)| (f(i,j')-f(i,j))^2 A_{i,j'} in place of the sum over i' of the corresponding quantities. This replacement is not an identity and does not follow from Hölder continuity. The row-neighborhood condition bounds an average over columns of squared row deviations; it gives no pointwise control at a fixed column j'. Moreover, the missingness indicator is changed from A_{i',j'} to A_{i,j'}: if A_{i,j'}=0 while several neighboring rows have A_{i',j'}=1, the right-hand side can be zero while the left-hand side is positive, and no event in the proof rules out such a configuration. The Chernoff bounds used nearby control row or column marginals, not this per-cell replacement. The identical aggregation step is reused in the MNAR proof of Theorem 2 at Eq. (30). Since B1 is one of the two bias components through which the tuned rate MSE = O((mn)^(-2λ/(2λ+d1+d2))) is derived, Theorems 1 and 2 and Corollary 1 are not proved as written.
[Corollary 1 and Section 6] The paper claims that TS-NN achieves the 'non-parametric minimax optimal rate' and uses the word 'minimax' in the title, but no lower bound is stated or proved for the model class defined by Assumptions 1-4 or Assumptions 1-3, 5, and 6. Matching the rate of an oracle that knows the latent factors is not by itself a minimax lower bound for the problem with unknown latent factors and Hölder f. The authors should either prove a matching lower bound for this model class or cite a precise existing lower-bound result and explain why it applies. Without this, the optimality claim in Corollary 1 and the discussion is not supported.

minor comments (3)

[Appendix D, Lemma 3] The proof of Lemma 3 writes ||g||_∞ = B and assumes g(x*) = B for a point x*, but if the supremum of |g| is attained at a point where g is negative, the displayed argument 'g(x) ≥ g(x*) - L||x-x*||^λ' is not the correct starting point. This can likely be repaired by working with |g| or by a sign flip, and it is a local issue rather than a central one.
[Appendix A, proof of Theorem 1] The appendix states that sample splitting is unnecessary and that 'all the computations will continue to hold' on a single dataset, but the proof conditions on events A1, A2, and A3 whose definitions involve the estimated neighborhoods, which depend on the same observations used in the final estimator. A short formal justification of this conditioning, or an explicit sample-splitting version of the proof, would make the argument easier to verify.
[Acknowledgments] The Acknowledgments section contains the placeholder text 'Give acknowledgements' and should be completed before resubmission.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the MSE rates are derived from the stated assumptions, the cited lemmas from the authors' prior work are auxiliary concentration tools, and the minimax benchmark is external.

full rationale

I walked the derivation chain for Theorems 1--4 and Corollary 1. The claimed MSE rate O((mn)^(-2lambda/(2lambda+d1+d2))) is obtained by optimizing an explicit high-probability upper bound with respect to the tuning parameters eta_row and eta_col; the bound itself is not defined in terms of the target rate, so Corollary 1 is an algebraic consequence rather than a self-definitional equivalence. The MNAR result (Theorem 2) is conditional on Assumption 6, a stated sufficient condition on observed-neighborhood size, not a restatement of the conclusion. The minimax optimality language invokes the lower bound of Yu (2022), which is an external benchmark and is not proved or assumed circularly here. The self-citations to Dwivedi et al. (2022a,b) are used for auxiliary tools: weighted-Bernoulli concentration (Lemma 2 of Dwivedi et al. 2022b), a calculus inequality imitated from Lemma H.2 of Dwivedi et al. (2022a), and a variance-estimation suggestion in Appendix E.1. None of these supplies the main bias-variance trade-off or the minimax rate, so they are not load-bearing circularity. I also considered the skeptic's critique of Appendix A, Eq. (16), step (i), where the proof aggregates row-neighbor terms and replaces A_{i',j'} by A_{i,j'}; this is a possible correctness gap in the B1 bias bound, and the appendix's assertion that all computations hold without sample-splitting is an unproved claim. However, a proof gap is not the same as circularity: it does not make the theorem's conclusion equivalent to its inputs by construction. For circularity, the paper would need to fit or define the claimed rate into the assumptions, and I found no such reduction.

Assumptions & free parameters 4 free parameters · 8 assumptions · 0 invented entities

The central results rest on the Holder latent-factor model, sub-Gaussian noise, uniform latent factors, and the MCAR/MNAR missingness assumptions (Assum. 1-5, 7). Assumption 6 is strong and hard to verify in practice. The proof also depends on an unproven replacement inequality in the B1 bias bound. The estimator introduces two tuning radii eta_row and eta_col whose optimal choice requires unknown λ, d1, d2.

free parameters (4)

eta_row = Θ((mn)^(-λ/(2λ+d1+d2))) in Cor. 1; tuned by 5-fold CV in experiments
Neighborhood radius for rows; the theoretical optimal choice depends on unknown smoothness λ and dimensions d1,d2; in experiments it is chosen by cross-validation.
eta_col = Θ((mn)^(-λ/(2λ+d1+d2))) in Cor. 1; tuned by 5-fold CV in experiments
Neighborhood radius for columns; same dependence on unknown λ,d1,d2 and CV tuning as eta_row.
subsampling threshold tau = tau > 1 (unspecified constant)
Introduced in Appendix A to cap neighborhood sizes; not part of the Sec. 3 algorithm; chosen to make the bias bound go through.
T_n,m = Sequence satisfying Assum. 7
Cap on the number of nearest neighbors required for the CLT in Theorem 4; no practical guidance for choosing it is given.

assumptions (8)

domain assumption Latent factor model with Holder function f (Assum. 1)
The ground truth matrix is θ_i,j = f(u_i,v_j) with f (λ,L)-Holder; this defines the model class under study.
domain assumption Sub-Gaussian noise independent of factors and missingness (Assum. 2)
Noise independence and tail bounds underlie all concentration inequalities.
domain assumption Latent factors i.i.d. Uniform[0,1]^d (Assum. 3)
Used for volume-based lower bounds on neighbor counts; claimed relaxable to any compact-supported distribution with lower-bounded density.
domain assumption MCAR missingness (Assum. 4) or MNAR with independence (Assum. 5)
Missing indicators are independent Bernoulli, either constant p or p_i,j depending on latent factors only.
domain assumption Minimum observed-neighbor fraction g(δ) (Assum. 6)
Guarantees each two-sided neighborhood contains a positive fraction of observed entries; central for the MNAR rate.
domain assumption Neighborhood-size cap T_n,m (Assum. 7)
Required for the CLT bias decay in Theorem 4.
standard math Uniform bound on noise: max |ϵ| ≤ σ√(2 log(2mn/δ))
Follows from sub-Gaussianity (Assum. 2) and a union bound; used in Lemma 1.
ad hoc to paper Unproven step: neighbor-row column-difference replacement (Appendix A step (i))
The proof assumes Σ_i' (f(i',j')-f(i',j))^2 A_i',j' can be bounded by |N_row(i)| (f(i,j')-f(i,j))^2 A_i,j'; this is not implied by Holder continuity and can fail.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion." pith.science (2026). https://pith.science/paper/RIDDFFTC

@misc{pith2026241112965,
  author       = {Pith},
  title        = {Pith review of: Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RIDDFFTC}},
  note         = {Machine review of arXiv:2411.12965}
}

read the original abstract

Nearest neighbor (NN) algorithms have been extensively used for missing data problems in recommender systems and sequential decision-making systems. Prior theoretical analysis has established favorable guarantees for NN when the underlying data is sufficiently smooth and the missingness probabilities are lower bounded. Here we analyze NN with non-smooth non-linear functions with vast amounts of missingness. In particular, we consider matrix completion settings where the entries of the underlying matrix follow a latent non-linear factor model, with the non-linearity belonging to a \Holder function class that is less smooth than Lipschitz. Our results establish following favorable properties for a suitable two-sided NN: (1) The mean squared error (MSE) of NN adapts to the smoothness of the non-linearity, (2) under certain regularity conditions, the NN error rate matches the rate obtained by an oracle equipped with the knowledge of both the row and column latent factors, and finally (3) NN's MSE is non-trivial for a wide range of settings even when several matrix entries might be missing deterministically. We support our theoretical findings via extensive numerical simulations and a case study with data from a mobile health study, HeartSteps.

Figures

Figures reproduced from arXiv: 2411.12965 by the authors.

**Figure 1.** MSE comparison for various benchmarks. Results are averaged across 10 runs. Baselines We compare TS-NN with the vanilla NNs, namely row nearest neighbors (RowNN) and its column counterpart (Col-NN) Li et al. (2019); Dwivedi et al. (2022a) each of which only use one set of neighbors, and then its doubly robust variant (DR-NN) Dwivedi et al. (2022b) which uses both row and column neighbors. We also include the conven… view at source ↗

**Figure 2.** Scatterplots of estimated and true signals for TS-NN and SoftImpute under MNAR missingness. In TS-NN the points are much more concentrated around y = x line, while SoftImpute struggles with controlling the bias. For SoftImpute, in the region θi,j ≤ 0, majority of the points lie below the y = x line indicating a pervasive negative bias among it’s estimates and vice versa for the region θi,j > 0. Results Following our… view at source ↗

**Figure 3.** Coverage as a function of n(= m). Green lines and orange lines indicate coverage given by 95% CIs obtained using the interval (5) with appropriate σbϵ and oracle σϵ respectively. 5.2 Case-study with HeartSteps HeartSteps Klasnja et al. (2019) is a micro-randomized trial aimed at improving participants’ walking activity via mobile notifications, resulting in a health intervention dataset spanning 6 weeks with 37 use… view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Held-out data root MSE (RMSE) for various algorithms in HeartSteps. RMSE of USVT and SoftImpute were too high to be competitive and are omitted for plot clarity. on their phones for tracking physical activity pre and post-intervention. The underlying recommender system…

**Figure 5.** Figure 5: MSE of different algorithms for estimating θi,t as a function of n when λ = 0.5 and SNR = 2. TS-NN demonstrates quantifiable improvements over USVT, SoftImpute, and other NNs in estimation both in terms of MSE value and MSE decay rate. Moreover, TS-NN shows similar (if…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 31 canonical work pages

[1]

Agarwal, D

A. Agarwal, D. Shah, and D. Shen. Synthetic interventions. arXiv preprint arXiv:2006.07691, 2020

arXiv 2006
[2]

Agarwal, M

A. Agarwal, M. Dahleh, D. Shah, and D. Shen. Causal matrix completion. arXiv preprint arXiv:2109.15154, 2021

arXiv 2021
[3]

Arkhangelsky, S

D. Arkhangelsky, S. Athey, D. A. Hirshberg, G. W. Imbens, and S. Wager. Synthetic difference in differences. Technical report, National Bureau of Economic Research, 2019

work page 2019
[4]

V. Bentkus. On hoeffding's inequalities. Annals of probability, pages 1650--1673, 2004

work page 2004
[5]

Bertsimas and M

D. Bertsimas and M. L. Li. Fast exact matrix completion: A unified optimization framework for matrix completion. Journal of Machine Learning Research, 21 0 (231): 0 1--43, 2020

work page 2020
[6]

Matrix completion with data-dependent missingness probabilities

S. Bhattacharya and S. Chatterjee. Matrix completion with data-dependent missingness probabilities. arXiv preprint arXiv:2106.02290, 2021

work page Pith review arXiv 2021
[7]

Burkina, I

M. Burkina, I. Nazarov, M. Panov, G. Fedonin, and B. Shirokikh. Inductive matrix completion with feature selection. Computational Mathematics and Mathematical Physics, 61 0 (5): 0 719--732, 2021

work page 2021
[8]

Chatterjee

S. Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statistics, 43 0 (1): 0 177--214, 2015

2015

Show all 37 references

[9]

Chiang, C.-J

K.-Y. Chiang, C.-J. Hsieh, and I. S. Dhillon. Matrix completion with noisy side information. Advances in neural information processing systems, 28, 2015

2015
[10]

Chiang, I

K.-Y. Chiang, I. S. Dhillon, and C.-J. Hsieh. Using side information to reliably learn low-rank matrices from missing and corrupted observations. Journal of Machine Learning Research, 19 0 (76): 0 1--35, 2018

2018
[11]

Dwivedi, K

R. Dwivedi, K. Tian, S. Tomkins, P. Klasnja, S. Murphy, and D. Shah. Counterfactual inference for sequential experiments. arXiv preprint arXiv:2202.06891, 2022 a

2022 arXiv
[12]

Dwivedi, K

R. Dwivedi, K. Tian, S. Tomkins, P. Klasnja, S. Murphy, and D. Shah. Doubly robust nearest neighbors in factor models. arXiv preprint arXiv:2211.14297, 2022 b

2022 arXiv
[13]

Eftekhari, D

A. Eftekhari, D. Yang, and M. B. Wakin. Weighted matrix completion and recovery with prior subspace information. IEEE Transactions on Information Theory, 64 0 (6): 0 4044--4071, 2018

2018
[14]

C. Gao, Y. Lu, and H. H. Zhou. Rate-optimal graphon estimation. 2015

2015
[15]

C. Gao, Y. Lu, Z. Ma, and H. H. Zhou. Optimal estimation and completion of matrices with biclustering structures. Journal of Machine Learning Research, 17 0 (161): 0 1--29, 2016

2016
[16]

Ghassemi, A

M. Ghassemi, A. Sarwate, and N. Goela. Global optimality in inductive matrix completion. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2226--2230. IEEE, 2018

2018
[17]

Y. Guo. Convex co-embedding for matrix completion with predictive side information. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017

2017
[18]

Hagerup and C

T. Hagerup and C. R \"u b. A guided tour of chernoff bounds. Information processing letters, 33 0 (6): 0 305--308, 1990

1990
[19]

Hastie, R

T. Hastie, R. Mazumder, J. D. Lee, and R. Zadeh. Matrix completion and low-rank svd via fast alternating least squares. Journal of Machine Learning Research, 16 0 (104): 0 3367--3402, 2015. URL http://jmlr.org/papers/v16/hastie15a.html

2015
[20]

Jain and I

P. Jain and I. S. Dhillon. Provable inductive matrix completion. arXiv preprint arXiv:1306.0626, 2013

2013 arXiv
[21]

Klasnja, S

P. Klasnja, S. Smith, N. J. Seewald, A. Lee, K. Hall, B. Luers, E. B. Hekler, and S. A. Murphy. Efficacy of contextually tailored suggestions for physical activity: a micro-randomized optimization trial of heartsteps. Annals of Behavioral Medicine, 53 0 (6): 0 573--582, 2019

2019
[22]

Klopp, A

O. Klopp, A. B. Tsybakov, and N. Verzelen. Oracle inequalities for network models and sparse graphon estimation. 2017

2017
[23]

Y. Li, D. Shah, D. Song, and C. L. Yu. Nearest neighbors for matrix estimation interpreted as blind regression for latent variable model. IEEE Transactions on Information Theory, 66 0 (3): 0 1760--1784, 2019

2019
[24]

J. Lu, G. Liang, J. Sun, and J. Bi. A sparse interactive model for matrix completion with side information. Advances in neural information processing systems, 29, 2016

2016
[25]

Ma and G

W. Ma and G. H. Chen. Missing not at random in matrix completion: The effectiveness of estimating missingness probabilities under a low nuclear norm assumption. arXiv preprint arXiv:1910.12774, 2019

1910 arXiv
[26]

Mazumder, T

R. Mazumder, T. Hastie, and R. Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research, 11 0 (80): 0 2287--2322, 2010. URL http://jmlr.org/papers/v11/mazumder10a.html

2010
[27]

Schnabel, A

T. Schnabel, A. Swaminathan, A. Singh, N. Chandak, and T. Joachims. Recommendations as treatments: Debiasing learning and evaluation. In M. F. Balcan and K. Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings o...

2016
[28]

D. Song, C. E. Lee, Y. Li, and D. Shah. Blind regression: Nonparametric regression for latent variable models via collaborative filtering. Advances in Neural Information Processing Systems, 29, 2016

2016
[29]

Sportisse, C

A. Sportisse, C. Boyer, and J. Josse. Imputation and low-rank estimation with missing not at random data. Statistics and Computing, 30 0 (6): 0 1629--1643, 2020 a

2020
[30]

Sportisse, C

A. Sportisse, C. Boyer, and J. Josses. Estimation and imputation in probabilistic principal component analysis with missing not at random data. Advances in Neural Information Processing Systems, 33, 2020 b

2020
[31]

Y. Wang, D. Liang, L. Charlin, and D. M. Blei. Causal inference for recommender systems. In Proceedings of the 14th ACM Conference on Recommender Systems, pages 426--431, 2020

2020
[32]

J. Xu. Rates of convergence of spectral methods for graphon estimation. In International Conference on Machine Learning, pages 5433--5442. PMLR, 2018

2018
[33]

M. Xu, R. Jin, and Z.-H. Zhou. Speedup matrix completion with side information: Application to multi-label learning. Advances in neural information processing systems, 26, 2013

2013
[34]

C. Yang, L. Ding, Z. Wu, and M. Udell. Tenips: Inverse propensity sampling for tensor completion. arXiv preprint arXiv:2101.00323, 2021

2021 arXiv
[35]

C. L. Yu. Nonparametric matrix estimation with one-sided covariates. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 892--897. IEEE, 2022

2022
[36]

Zhong, P

K. Zhong, P. Jain, and I. S. Dhillon. Efficient matrix sensing using rank-1 gaussian measurements. In Algorithmic Learning Theory: 26th International Conference, ALT 2015, Banff, AB, Canada, October 4-6, 2015, Proceedings 26, pages 3--18. Springer, 2015

2015
[37]

Z. Zhu, T. Wang, and R. J. Samworth. High-dimensional principal component analysis with heterogeneous missingness. arXiv preprint arXiv:1906.12125, 2019

1906 arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Agarwal, D

A. Agarwal, D. Shah, and D. Shen. Synthetic interventions. arXiv preprint arXiv:2006.07691, 2020

arXiv 2006

[2] [2]

Agarwal, M

A. Agarwal, M. Dahleh, D. Shah, and D. Shen. Causal matrix completion. arXiv preprint arXiv:2109.15154, 2021

arXiv 2021

[3] [3]

Arkhangelsky, S

D. Arkhangelsky, S. Athey, D. A. Hirshberg, G. W. Imbens, and S. Wager. Synthetic difference in differences. Technical report, National Bureau of Economic Research, 2019

work page 2019

[4] [4]

V. Bentkus. On hoeffding's inequalities. Annals of probability, pages 1650--1673, 2004

work page 2004

[5] [5]

Bertsimas and M

D. Bertsimas and M. L. Li. Fast exact matrix completion: A unified optimization framework for matrix completion. Journal of Machine Learning Research, 21 0 (231): 0 1--43, 2020

work page 2020

[6] [6]

Matrix completion with data-dependent missingness probabilities

S. Bhattacharya and S. Chatterjee. Matrix completion with data-dependent missingness probabilities. arXiv preprint arXiv:2106.02290, 2021

work page Pith review arXiv 2021

[7] [7]

Burkina, I

M. Burkina, I. Nazarov, M. Panov, G. Fedonin, and B. Shirokikh. Inductive matrix completion with feature selection. Computational Mathematics and Mathematical Physics, 61 0 (5): 0 719--732, 2021

work page 2021

[8] [8]

Chatterjee

S. Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statistics, 43 0 (1): 0 177--214, 2015

2015