{"id":"8af61a3a-d301-424d-80f1-431696deeb13","arxiv_id":"2411.12965","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A two-sided nearest-neighbor estimator is claimed to match the oracle minimax rate for matrix completion under Holder-smooth, possibly non-Lipschitz latent factor models, even when entries are missing not at random.","lead":"This paper analyzes a two-sided nearest-neighbor estimator for matrix completion when entries follow a non-linear function of unobserved row and column factors, and the function may be less smooth than Lipschitz. The authors claim mean-squared-error rates that match the oracle minimax rate in a moderate regime, even under missingness that is not at random.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed minimax MSE rate rests on an invalid 'aggregation' step in the B1 bias bound (Appendix A, Eq. (16), step (i)); without a replacement bound, Theorems 1-2 and Corollary 1 are not proved as written.","rationale":"The reader's weakest assumption identifies the same invalid replacement in the B1 bias bound, and my reading confirms that it is the single most load-bearing obstruction to the central claim. The upper bound in Theorem 1 is obtained by separately bounding B1 and B2; B2 is controlled by the column-neighbor structure and yields eta_row^2 terms, but B1 needs the swapped row/column argument to yield eta_col^2. The proof's step (i) in Eq. (16) is the only place that supplies this control, and it changes both the function evaluation point and the missingness indicator. Counterexamples are immediate, so the step is not a harmless inaccuracy. The same step appears verbatim in the MNAR proof, so both main theorems and their corollaries inherit the gap. The empirical results and the distance-concentration lemma are useful and may be salvageable, but the theoretical headline rate is not established as written. Because the reader already reached REJECT on the same ground, my stress-test does not change the verdict; if the authors supply a corrected B1 bound or weaken the claims accordingly, the manuscript should be re-evaluated.","tokens_in":32706,"tokens_out":3423,"duration_ms":35817,"concrete_test":"Build a direct counterexample to Eq. (16) step (i): take a row i with one neighbor i' at Euclidean distance epsilon, choose f(u,v)=|u-v|^lambda, set v_j=0 and v_j'=1, and set A_{i,j'}=0 while A_{i',j'}=1 (all other indicators arbitrary). Then the substituted right-hand side is 0 while the original sum is |epsilon-1|^(2 lambda) > 0, showing the aggregation step is not an identity. As an analytic check, re-derive the B1 bound using only Holder continuity and Lemma 1 without the replacement; if the resulting bound contains a max over j' of row-neighbor pointwise deviations rather than eta_col^2, the optimized rate in Corollary 1 is not attained and the proof strategy requires a genuinely new argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central rate claim depends on the B1 bias bound in the proof of Theorem 1, specifically the step labeled (i) in Appendix A, Eq. (16). For fixed (i,j), the proof 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 of the form |N_row(i)| (f(i,j')-f(i,j))^2 A_{i,j'} summed over j'. This is not a consequence of Holder continuity, and it is not an identity: (1) the row-neighborhood condition bd^2_row(i,i') <= eta_row^2 only bounds an average over columns of squared deviations between rows i and i'; it does not control the pointwise deviation at the single column j' that appears after the replacement. (2) The missingness indicator is changed: A_{i',j'} becomes A_{i,j'}, so if A_{i,j'}=0 while several neighboring rows have A_{i',j'}=1, the right-hand side is zero while the left-hand side is positive. The proof gives no event that prevents such configurations; the Chernoff bounds used nearby control column or row marginals, not the required per-cell replacement. The identical aggregation step is reused in the MNAR proof of Theorem 2 (Eq. (30)). Because the optimized rate MSE = O((mn)^(-2 lambda/(2 lambda + d1 + d2))) is obtained from a bound whose B1 component is controlled only through this step, the main MSE claims, including the minimax optimality of Corollary 1 and the corresponding MNAR statement, do not follow from the written proof. The appendix's assertion that all computations hold without sample-splitting is also not demonstrated, but the B1 step alone is sufficient to block the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":33086,"tokens_out":9420,"duration_ms":100932,"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":[{"comment":"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.","section":"Appendix A, proof of Theorem 1, Eq. (16), step (i)"},{"comment":"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.","section":"Corollary 1 and Section 6"}],"minor_comments":[{"comment":"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.","section":"Appendix D, Lemma 3"},{"comment":"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.","section":"Appendix A, proof of Theorem 1"},{"comment":"The Acknowledgments section contains the placeholder text 'Give acknowledgements' and should be completed before resubmission.","section":"Acknowledgments"}],"recommendation":"reject","confidential_remarks":"I agree with the reader's report on the central proof gap. The invalid B1 bound at Eq. (16) is not a minor technical slip: it is the step that produces the advertised MSE rate, and no alternative argument is supplied in the manuscript. I therefore recommend rejection rather than major revision. If the authors can provide a correct treatment of the B1 term, or prove the rate under additional assumptions, the work may be worth reconsidering."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nOther 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.\n\nBottom 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.","headline":"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.","tokens_in":33701,"tokens_out":6102,"would_cite":false,"duration_ms":62172,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G08","62C20","62D10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["nearest neighbor","matrix completion","Hölder smoothness","missing not at random","minimax optimal rate","latent factor model","nonparametric regression"],"falsifier":"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.","tokens_in":32473,"feed_emoji":"📊","tokens_out":9769,"duration_ms":90862,"temperature":0.7,"pith_summary":"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.","feed_headline":"Two-sided nearest neighbors match the oracle completion rate","feed_subtitle":"It reaches the best possible error rate for non-smooth signals and missing-not-at-random data.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the prior one-sided NN estimator that achieves the minimax rate only with known column latent factors; the paper's TS-NN removes that knowledge requirement and is compared against it.","marker":"Yu (2022)"},{"why":"Provides the row-nearest-neighbor analysis under a Lipschitz latent factor model, the distance-estimate construction, and the pointwise guarantee that Theorem 3 generalizes to Hölder smoothness.","marker":"Dwivedi et al. (2022a)"},{"why":"Gives the doubly robust NN baseline and the weighted-Bernoulli concentration lemma used to derive the distance-concentration bounds and the Assumption 6 examples.","marker":"Dwivedi et al. (2022b)"},{"why":"Establishes the nearest-neighbor-as-blind-regression viewpoint for matrix estimation that motivates the two-sided averaging rule and serves as a baseline.","marker":"Li et al. (2019)"},{"why":"Introduces the blind-regression nonparametric latent variable model class to which this paper's factor model belongs.","marker":"Song et al. (2016)"},{"why":"Supplies the Chernoff bounds used throughout to lower-bound neighborhood sizes and observation counts.","marker":"Hagerup and Rüb (1990)"},{"why":"Supplies the Hoeffding-type inequality used to concentrate the noise terms in the variance part of the MSE bound.","marker":"Bentkus (2004)"}],"fun_headline_variants":["Two-sided NN matches oracle rate for non-smooth matrix factors","Adaptive NN: oracle-optimal matrix completion with missing-not-at-random","Nearest neighbors achieve minimax bound despite rough signals and MNAR","Two-sided NN: oracle error even when data missing not at random","Matrix completion: two-sided NN adapts to rough latent functions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two-sided NN matches oracle rate for non-smooth matrix factors","Adaptive NN: oracle-optimal matrix completion with missing-not-at-random","Nearest neighbors achieve minimax bound despite rough signals and MNAR","Two-sided NN: oracle error even when data missing not at random","Matrix completion: two-sided NN adapts to rough latent functions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000683,"raw_usage":{"total_tokens":3130,"prompt_tokens":1003,"completion_tokens":2127,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":2037}},"tokens_in":619,"tokens_out":2127,"duration_ms":13217,"temperature":1.0,"reasoning_tokens":2037,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:03:10.246906+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}