{"id":"ed4af021-9a17-460c-8199-24511dfbe1f3","arxiv_id":"2505.09612","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"AWNN assigns weights to neighboring rows by solving a convex bias-variance objective and claims the same row-MSE rates as optimally tuned unweighted nearest neighbors.","lead":"This paper introduces AWNN, a nearest-neighbor method for filling in missing matrix entries that chooses its weights and neighborhood automatically instead of by cross-validation. The method matters because recommender systems and policy evaluation routinely average similar rows, and removing the tuning step would make these procedures faster and more principled.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop. 1's substitution of Eq. (3) drops a 4σ² term; the corrected bound has an O(1) additive constant, so the O(n^{-2λ/(d1+2λ)}) rate in Cor. 1/2 is not established.","rationale":"The paper's central claims are the finite-sample MSE bounds and the automatic rate guarantee O(n^{-2λ/(d1+2λ)}) under MCAR missingness. All of these depend on Prop. 1, whose proof contains the incorrect substitution of Eq. (3). The reader identified exactly this algebraic error, and my independent reading confirms it: the bias term in App. S.1 is expanded as 2/m Σ_{i'} w_{i'} Σ_j (θ_{i,j}-θ_{i',j})², which by the paper's own definition of ρ equals 2Σ w ρ + 4σ², not 2Σ w ρ. This is not a loose constant that can be absorbed by the o(1) in Cor. 2; it is an additive O(1) term in the claimed upper bound, so the rate proof fails. The missing constant does not affect weight selection, so the algorithm could in principle be repairable, but the current manuscript does not establish the stated guarantees. The simulations are suggestive but cannot substitute for the broken proof. I therefore agree with the reader's REJECT verdict and recommend no change.","tokens_in":23642,"tokens_out":10302,"duration_ms":109519,"concrete_test":"Independently re-derive App. S.1 with Eq. (3) applied correctly: replace the line '(3)= 2Σ_{i'}w_{i'}ρ_{i',i}' with '= 2Σ_{i'}w_{i'}ρ_{i',i} + 4σ²', and propagate the extra 4σ² into Prop. 1, Thm. 1, and the display preceding Cor. 2. Then check whether the claimed bound before Cor. 2, 1/m Σ_j (bθ_{i,j}-θ_{i,j})² ≤ (1+o(1))(2/m Σ_j \\bar bρ_{i;j}) + 4 log(2m/δ)σ²/m Σ_j 1/K_{i,j}, survives with the additive 4σ². If the constant remains, evaluate the corrected RHS at η = O(n^{-λ/(d1+2λ)}): it is 4σ² + o(1), so the stated O(n^{-2λ/(d1+2λ)}) rate does not follow.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix S.1 contains the load-bearing algebraic slip. The proof of Prop. 1 writes\n\n2/m Σ_{i'} w_{i'} Σ_j (θ_{i,j}-θ_{i',j})² (3)= 2 Σ_{i'} w_{i'} ρ_{i',i}.\n\nBut Eq. (3) defines ρ_{i',i} = (1/m)Σ_j(θ_{i,j}-θ_{i',j})² − 2σ². Since Σ_{i'} w_{i'} = 1, the correct identity is\n\n2/m Σ_{i'} w_{i'} Σ_j (θ_{i,j}-θ_{i',j})² = 2 Σ_{i'} w_{i'} ρ_{i',i} + 4σ².\n\nThe missing +4σ² propagates into Prop. 1, Thm. 1, Lem. 1, Cor. 1, Thm. 2, and the display preceding Cor. 2. In the no-missingness bound, the RHS is smaller by exactly 4σ² than the quantity derived in the proof, so the advertised upper bound is not established by the argument. The constant does not change the argmin of (4), but it changes the asymptotic claim: after substituting η = O(n^{-λ/(d1+2λ)}) in Cor. 2's derivation, the corrected RHS is 4σ² + o(1), i.e. Θ(1), not O(n^{-2λ/(d1+2λ)}). Thus the central rate claim does not follow. The algorithm may still have good behavior, but the proof route in this version is broken. A separate gap is condition (9), assumed without proof, which is also needed for the rate statement.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes AWNN, a row-nearest-neighbor matrix completion method in which the weights and the effective neighborhood are selected by minimizing a penalized objective that combines a variance proxy with estimated centered row distances, using a plug-in estimate of the noise variance. The paper claims finite-sample data-dependent row-MSE upper bounds (Prop. 1, Thms. 1 and 2), a dominance result over optimally tuned unweighted row nearest neighbors (Lem. 1), and an adaptive rate O(n^{-2\\lambda/(d_1+2\\lambda)}) under MCAR missingness without hyperparameter tuning (Cors. 1 and 2). The experiments compare AWNN with RowNN, Oracle-AWNN, and USVT on synthetic Hölder factor models.","tokens_in":24052,"tokens_out":19034,"duration_ms":202996,"significance":"If the theoretical claims were valid, AWNN would be a genuinely useful contribution: a tuning-free nearest-neighbor matrix completion method with closed-form weights, no low-rank or sparsity assumptions, and rate-adaptive guarantees. The algorithmic idea is appealing, the weight computation is simple, and the reported synthetic results are encouraging. However, the proof of the central results contains several load-bearing errors, including an incorrect substitution of Eq. (3), a confusion between centered and uncentered distance in the proof of Thm. 2, and an internally inconsistent argument in Lem. 1. As a consequence, the headline rate claims are not established by the arguments given.","major_comments":[{"comment":"The proof of Prop. 1 substitutes Eq. (3) incorrectly. It writes 2/m \\sum_{i'} w_{i'} \\sum_j (\\theta_{i,j}-\\theta_{i',j})^2 = 2 \\sum_{i'} w_{i'} \\rho_{i',i}, but Eq. (3) defines \\rho_{i',i} = (1/m)\\sum_j(\\theta_{i,j}-\\theta_{i',j})^2 - 2\\sigma^2, so the correct identity is 2\\sum_{i'}w_{i'}\\rho_{i',i} + 4\\sigma^2, using \\sum_{i'}w_{i'}=1. The stated upper bound in Prop. 1 therefore omits a 4\\sigma^2 term and is not a valid upper bound; it can even be negative when the estimated centered distances are negative. Since Prop. 1 is invoked in Thm. 1, Lem. 1, Cor. 1, Thm. 2, and Cor. 2, the chain of rate claims is not established. In particular, inserting the missing 4\\sigma^2 into the display preceding Cor. 2 and substituting \\eta=O(n^{-\\lambda/(d_1+2\\lambda)}) yields an O(1) rather than O(n^{-2\\lambda/(d_1+2\\lambda)}) bound. This is not a cosmetic constant: because \\hat{\\rho}_{i',i} is centered at -2\\sigma^2, a small threshold on \\hat{\\rho} does not by itself control the uncentered signal-distance term appearing in the row MSE.","section":"S.1 (Prop. 1), Eq. (3)"},{"comment":"The proof of Thm. 2 defines \\rho^*_{i',i}=E[(\\theta_{i,j}-\\theta_{i',j})^2] and later claims that |\\rho_{i',i}-\\rho^*_{i',i}| is bounded by the vanishing concentration term 8M^2\\sqrt{\\log(2/\\delta)}(\\|\\hat{w}_{i',\\cdot}\\|_2/\\|\\hat{w}_{i',\\cdot}\\|_1). But \\rho_{i',i} is defined in Eq. (3) as the same average minus 2\\sigma^2, i.e. \\rho_{i',i}=\\rho^*_{i',i}-2\\sigma^2 up to sampling fluctuations. The difference is therefore of constant order \\sigma^2 and cannot be made o(1) by concentration. This invalidates the bias bound in Thm. 2 and hence the derivation of Cor. 2 in the missing-data setting.","section":"S.7 (Thm. 2)"},{"comment":"The proof of Lem. 1 states that AWNN's selected neighborhood size satisfies K_i = \\arg\\max_{K\\in(0,K_{\\max}]} MSE(K); since AWNN minimizes the objective in Eq. (4), the correct statement would be K_i = \\arg\\min_K MSE(K), and the inequality MSE(K_i)\\le MSE(K) used in Eq. (E.12) only follows for a minimizer. As written, the proof of the central dominance lemma is internally inconsistent. Moreover, Lemma 1 compares deterministic upper bounds, not actual row-wise MSE or risk; the sentence that AWNN 'guarantees a lower row wise mean squared error than the best-performing unweighted row-nearest-neighbour estimator' overstates what a bound-to-bound comparison establishes.","section":"S.4 (Lem. 1)"},{"comment":"Cor. 2's rate is conditional on Eq. (9), an o() negligibility assumption involving the estimated weights, which is asserted without proof. The surrounding text says the term is 'generally o(...)', but no argument is supplied. Under the stated goal of guarantees 'under minimal assumptions', an unverified data-dependent condition that is needed for the main completion rate is a substantial gap; even if the earlier algebra were corrected, Cor. 2 would only be a conditional statement.","section":"Section 3.2, Eq. (9)"}],"minor_comments":[{"comment":"The theory assumes \\sigma^2 is known, while Algorithm 1 initializes \\hat{\\sigma}^2 as Var/10 and uses a fixed-point iteration; no convergence analysis or consistency proof is given for this iteration, so the practical algorithm and the analyzed procedure are not fully matched.","section":"Algorithms 1 and 2"},{"comment":"The statement of Lem. 2 uses '4\\log(2m\\delta)\\sigma^2' where '4\\log(2m/\\delta)\\sigma^2' is evidently intended; this appears in several places and should be corrected.","section":"Lem. 2"},{"comment":"Algorithm 2 explicitly sets the diagonal of the estimated distance matrix to 0, but under Eq. (3) the self-distance is -2\\sigma^2; this discrepancy between the analyzed objective and the implemented algorithm is not discussed.","section":"Algorithm 2, line 1"},{"comment":"The axis labels of Figure 1 appear garbled (e.g., '2 5', '2 3', '2 1'), and the reported decay slopes are embedded in the legend; a table or clearer axis labels would improve readability.","section":"Figure 1"}],"recommendation":"reject","confidential_remarks":"The manuscript's central contribution is a set of rate guarantees that are invalidated by several independent proof errors, including an algebraic slip in Prop. 1 and a mismatch between centered and uncentered distances in Thm. 2. The encouraging simulations do not compensate for the absence of a valid proof of the headline claims. I recommend rejection; a corrected theoretical treatment of the actual algorithm would be needed before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: the AWNN algorithm is a genuine idea with a clean write-up, but the main theoretical result has a load-bearing algebraic slip. In the proof of Prop. 1 (App. S.1) the bias term is rewritten as 2∑ w_i' ρ_i',i using Eq. (3), which defines ρ_i',i = (1/m)∑(θ_i,j − θ_i',j)² − 2σ². Since the weights sum to 1, the correct identity carries an extra +4σ². The bound in Prop. 1 is missing that constant, and the omission propagates to Thm. 1, Lem. 1, Cor. 1, Thm. 2, and Cor. 2. After substituting the optimal η into Cor. 2's derivation, the corrected bound is Θ(1), not O(n^{−2λ/(d1+2λ)}). So the central rate claim is not established.\n\nWhat is actually good: the idea of solving a convex bias-variance trade-off to choose both the neighborhood and the weights, with a closed-form solution and a fixed-point variance estimate, is new in the matrix-completion NN literature. The algorithm is simple, and the simulations are reasonably convincing that the method works in practice. That deserves credit.\n\nThe other soft spot is condition (9), assumed without proof and needed for the Cor. 2 rate; it may be true under MCAR, but it isn't shown. The fixed-point estimator for σ² is also unanalyzed; the empirical coincidence of AWNN and O-AWNN is suggestive but not a guarantee. And Lem. 1 is a bound-to-bound comparison, so the claim of lower MSE than the best unweighted NN is only about upper bounds, not actual MSE.\n\nThe paper is a technical note, and the error looks repairable. If the authors fix the constant and either prove (9) or state it as a conjecture with clear scope, the note could be worth publishing. As written, I would not cite it for the rate.\n\nI'd send it to referees, because the algorithmic contribution is real and a serious referee might help repair the proof. But I'd expect heavy revision, and I wouldn't accept it as is.","headline":"A neat algorithmic idea undermined by a dropped 4σ² term in the main proof; the claimed rates do not follow as written.","tokens_in":24592,"tokens_out":3861,"would_cite":false,"duration_ms":35283,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G05","62G20","62D10"],"pacs":[],"model":"deepseek-v4-flash","headline":"An adaptively weighted nearest-neighbor method that sets its own weights and neighborhood by convex optimization matches the radius-tuned estimator's error rate without cross-validation.","keywords":["matrix completion","weighted nearest neighbors","adaptive weights","bias-variance trade-off","Hölder smooth factor model","minimax nonparametric rate","missing data","noise variance estimation"],"falsifier":"One algebraic check in Appendix S.1 settles the central claim: expanding the bias term of Proposition 1 directly, the quantity the proof equates with $2\\sum_{i'}w_{i'}\\rho_{i',i}$ is in fact $2\\sum_{i'}w_{i'}\\rho_{i',i} + 4\\sigma^2$, so the displayed MSE upper bound omits a positive $4\\sigma^2$ term and can be smaller than the true error; if that is so, Lemma 1 and the rate corollaries do not follow from the given proof. A reader can also check empirically whether AWNN's realized row MSE stays at or below that of the cross-validated unweighted RowNN on the Hölder-factor experiments of Section 4 at low signal-to-noise.","tokens_in":23423,"feed_emoji":"🧩","tokens_out":33386,"duration_ms":265209,"temperature":0.7,"pith_summary":"Row-nearest-neighbor methods for matrix completion have always needed an external choice: the search radius and the weights given to the neighboring rows, usually selected by cross-validation. This paper proposes AWNN, which sets both by minimizing a convex objective that mirrors the bias–variance decomposition of the estimator's row-wise error, with the noise variance estimated internally by a fixed-point iteration. The authors claim two things: AWNN's row-wise mean-squared-error bound is never worse than the unweighted nearest-neighbor estimator's bound, even when that estimator's radius is optimally tuned, and under a Hölder-smooth factor model with missing entries AWNN attains the rate $O(n^{-2\\lambda/(d_1+2\\lambda)})$ without any hyperparameter selection. If these claims are right, nearest-neighbor matrix completion becomes a turnkey procedure for recommender systems and panel-data counterfactual prediction, where the choice of radius and weights has been the standing obstacle.","feed_headline":"Nearest neighbors that tune themselves match hand-tuned ones","feed_subtitle":"The method chooses its own weights and neighbor set, so no cross-validation or radius tuning is needed.","key_machinery":"The engine of the argument is Proposition 1's decomposition of the row-wise MSE into a bias term, a weighted average of row distances, and a variance term, the noise level times $\\|\\mathbf{w}\\|_2^2$; this decomposition licenses the convex surrogate $2\\log(2m/\\delta)\\hat{\\sigma}^2\\|\\mathbf{w}\\|_2^2 + \\sum_{i'}w_{i'}\\hat{\\rho}_{i',i}$ as the objective to minimize. The geometry comes from the noise-floor-subtracted distance $\\rho_{i',i} = (1/m)\\sum_j(\\theta_{i,j}-\\theta_{i',j})^2 - 2\\sigma^2$, which lets the optimization recognize the self row in the noiseless limit. Proposition 2 solves the program in closed form as a soft-thresholded weighting over an automatically chosen neighbor set $R(i)$, and the fixed-point update of $\\hat{\\sigma}^2$ (Algorithm 1) keeps the whole procedure a function of the observed matrix alone. Lemma 1's comparison against the unweighted neighbor estimator is what converts the optimized bound into a parameter-free rate: because AWNN's bound dominates the best radius-tuned bound, the tuned estimator's rate is inherited by AWNN.","core_discovery":"The paper's central claim is that the bias–variance trade-off in row-nearest-neighbor regression can be resolved by optimization instead of tuning. AWNN estimates the noise variance $\\sigma^2$ internally by a fixed-point iteration, computes empirical row distances $\\hat{\\rho}_{i',i}$, then for each target row solves the convex program $\\min_{\\mathbf{w}: w_{i'} \\ge 0,\\ \\sum_{i'}w_{i'}=1} 2\\log(2m/\\delta)\\hat{\\sigma}^2\\|\\mathbf{w}\\|_2^2 + \\sum_{i'}w_{i'}\\hat{\\rho}_{i',i}$. Proposition 2 gives the closed-form solution: within an automatically selected neighbor set $R(i)$, row $i'$ receives weight $1/|R(i)| - (\\hat{\\rho}_{i',i}-\\bar{\\rho}_i)/(4\\log(2m/\\delta)\\sigma^2)$, so closer rows are up-weighted and distant rows are excluded. The authors prove (Lemma 1) that the resulting row-wise mean-squared-error bound is no larger than that of the unweighted nearest-neighbor estimator under any radius, and (Corollary 2) that under a Hölder-smooth factor model with MCAR missingness the row-wise MSE decays as $O(n^{-2\\lambda/(d_1+2\\lambda)})$ — the same rate as the optimally tuned neighbor rule — with no hyperparameter selected by the user.","pith_inferences":["The weight formula is a shrinkage rule — uniform $1/K$ minus a distance deviation scaled by the noise level — so the same convex surrogate could plausibly be applied to kernel regression, where bandwidth choice has resisted a parameter-free resolution; that extension is not in the paper.","If the internal noise-variance estimate is as accurate as the Section 4 experiments suggest, AWNN recovers the optimal weighting without knowing $\\sigma^2$, making it a candidate drop-in replacement for cross-validated neighbor methods in recommender and panel-data pipelines.","The analysis is row-symmetric, so the same weight-optimization could be run on columns or on two-sided neighbor sets; transferring the dominance lemma to those estimators is a natural next test.","The paper states that Theorem 2 covers missing-not-at-random patterns without modification, but its experiments vary only MCAR missingness; simulating missingness correlated with the signal would test whether the bias condition (9) stays negligible in that regime."],"forward_implications":["Nearest-neighbor matrix completion no longer needs cross-validation or a grid search over the radius $\\eta$: the user supplies the observed matrix and a confidence level, and the weights and neighbor sets come out of the closed-form solution.","The guarantees do not require the ground-truth matrix to be low rank or sparse — only that rows and columns follow a Hölder-smooth factor model — so the method is claimed to stay reliable where ERM-based completion degrades, including missing-not-at-random patterns, where the authors state Theorem 2 applies unchanged.","In the noiseless limit the self-tuning weights collapse to the optimal extreme: full weight on the target row when self-neighbors are allowed, and on the nearest distinct row otherwise, which is the best any estimator could do without extra information.","Under MCAR missingness, AWNN is claimed to match the row-wise MSE rate of the radius-optimized unweighted nearest-neighbor estimator, so automatic weighting costs nothing asymptotically while removing the tuning burden (Corollary 2).","Because the weights have a closed form, the only iterative part is a scalar fixed-point update of the noise variance; the experiments report that this internal estimate lands on the true variance, so the fully automatic version matches the oracle version of the algorithm."],"supporting_citations":[{"why":"supplies the unweighted row-nearest-neighbor MSE bound with radius $\\eta$ that AWNN is compared against and whose minimax rate the paper claims to match without tuning.","marker":"[DTT+22a]"},{"why":"defines the vanilla row-nearest-neighbor estimator (uniform weights over a fixed neighbor set) that AWNN generalizes by optimizing the weights.","marker":"[DTT+22b]"},{"why":"provides the Lemma-2 lower bound on the number of rows within a radius that converts the dominance of Lemma 1 into the stated $O(n^{-2\\lambda/(d_1+2\\lambda)})$ rate.","marker":"[SPD24]"},{"why":"the Hoeffding-type sub-gaussian concentration used in the proof of Proposition 1 to control the noise (variance) term of the row-wise MSE bound.","marker":"[Ben04]"},{"why":"the Nagy inequality used to lower-bound the within-neighborhood spread of estimated distances, giving AWNN its debiasing gain over uniform weights in Theorem 1.","marker":"[KS20]"},{"why":"the universal singular value thresholding baseline that AWNN is benchmarked against in the synthetic experiments.","marker":"[Cha15]"},{"why":"the earlier nearest-neighbor matrix-estimation method cited as the RowNN baseline in the simulation study.","marker":"[LSSY19]"}],"fun_headline_variants":["Self-tuning nearest neighbors match hand-tuned ones","AWNN finds its own weights and radii, no cross-validation needed","Adaptive weights solve the bias-variance tradeoff in matrix completion","Theoretical guarantees for hyperparameter-free matrix completion"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Every stated error bound rests on one algebraic step in the proof of Proposition 1 — rewriting the weighted mean of squared row differences in terms of the paper's row-distance measure — that is asserted without derivation; if that step is off by even a constant, the mean-squared-error bound and everything built on it (Lemma 1, Theorem 2, both rate corollaries) no longer follow, and the claimed missing-data rate additionally assumes the unproved negligibility condition (9).","fun_headline_variants_meta":{"raw":{"variants":["Self-tuning nearest neighbors match hand-tuned ones","AWNN finds its own weights and radii, no cross-validation needed","Adaptive weights solve the bias-variance tradeoff in matrix completion","Theoretical guarantees for hyperparameter-free matrix completion"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00019,"raw_usage":{"total_tokens":1368,"prompt_tokens":1003,"completion_tokens":365,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":298}},"tokens_in":619,"tokens_out":365,"duration_ms":3511,"temperature":1.0,"reasoning_tokens":298,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:29:00.786434+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One algebraic check in Appendix S.1 settles the central claim: expanding the bias term of Proposition 1 directly, the quantity the proof equates with $2\\sum_{i'}w_{i'}\\rho_{i',i}$ is in fact $2\\sum_{i'}w_{i'}\\rho_{i',i} + 4\\sigma^2$, so the displayed MSE upper bound omits a positive $4\\sigma^2$ term and can be smaller than the true error; if that is so, Lemma 1 and the rate corollaries do not follow from the given proof. A reader can also check empirically whether AWNN's realized row MSE stays at or below that of the cross-validated unweighted RowNN on the Hölder-factor experiments of Section 4 at low signal-to-noise.","supporting_citations":[],"review_version":1}