{"id":"00fda7a6-b4e7-4a4c-a43b-b06079eaf23b","arxiv_id":"2501.13786","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"F3I learns neighbor weights for KNN imputation by maximizing a concave density-ratio objective and comes with high-probability bounds on imputation error and cumulative regret.","lead":"The paper introduces F3I, an imputation method that iteratively reweights K nearest neighbors to keep imputed values close to a learned data density, and a version that trains jointly with a classifier. It also derives error and regret bounds for several missing-data mechanisms and tests the method on drug repurposing and handwritten-digit recognition data.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The distribution-preserving guarantee is not established: F3I maximizes pointwise log-density ratios, a mode-seeking objective that under the paper's independent-Gaussian assumption shrinks imputed values toward feature means instead of preserving the data distribution.","rationale":"The reader's weakest assumption points at Assumption B.1; I agree that it makes the problem acute, because observed features are uninformative about the missing feature and the density objective therefore favors mean-shrinking imputations. I would phrase the load-bearing issue slightly more broadly: even without B.1, the objective G is a pointwise density-ratio (mode-seeking) objective, and no theorem in the paper bounds a distributional divergence such as variance, MMD, or Wasserstein distance between imputed and complete data. Thus the label 'distribution-preserving' overstates what Theorems 4.2 and 4.4 deliver. The empirical study is broad and the algorithm is fast, and the Appendix H validation confirms the stated regret and MSE upper bounds on Gaussian synthetic data, so the work has real value as a fast, theoretically analyzable KNN imputer. The correct fix is to reframe the guarantees as likelihood-improvement/MSE bounds and either drop or substantiate the distribution-preservation claim with an explicit distributional metric. This does not move me away from the reader's CONDITIONAL verdict; it confirms it.","tokens_in":49541,"tokens_out":11555,"duration_ms":108538,"concrete_test":"Generate synthetic data per Algorithm 3 with N=200, F=100, sigma=0.5, mu=0, MCAR pmiss=0.5; run F3I with the paper's default settings. For a fixed feature f, compare the empirical distribution of the final imputed values (x_t)_i^f for missing entries against the ground-truth (x*)_i^f and against N(mu_f, sigma^2). If the imputed values have standard deviation substantially below sigma (say ratio <0.6) and the Wasserstein distance to the ground truth is large, while the Theorem 4.4 regret bound is small, then the objective is confirmed to be mode-seeking, not distribution-preserving. The same test on a correlated-feature dataset (violating B.1) would show whether the issue persists outside the independence assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, in the title and abstract, is distribution-preserving guarantees. What is proved is different. The objective G(alpha, X) averages pointwise log-density ratios log D0(x_i(alpha))/D0(x_i); Theorem 4.4 bounds regret for this same objective, with D* replacing D0. Increasing pointwise density is mode-seeking: the maximum is achieved by moving imputed points toward the mode of D0, not by drawing them from D0. Under Assumption B.1, features are independent Gaussians, so observed coordinates give no information about a missing coordinate; the MSE-optimal imputation is the feature mean mu_f. Any non-degenerate convex combination of K neighbors has predictive variance at least sigma^2 (1 + sum_k alpha_k^2) > sigma^2, and the density objective favors small-sum-of-squares weights, collapsing the variance of imputed values. Theorems 4.2 and 4.4 may be valid as bounds on MSE and cumulative log-density regret, but neither bounds a distributional divergence between imputed and true values. This is a conceptual gap in the paper's main selling point, not a constant looseness. It also explains why mean imputation is competitive in the paper's own synthetic Gaussian experiments (Appendix H.1.2).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces F3I, an iterative K-nearest-neighbor imputation method that learns neighbor weights via AdaHedge to maximize a concave kernel-density log-ratio objective G. It also introduces PCGrad-F3I for joint imputation and classification. The paper states high-probability bounds on imputation MSE (Theorem 4.2), on cumulative regret against the best fixed weights for the 'true' objective G* (Theorem 4.4), and a joint-training regret bound (Theorem 5.1). Experiments on real and synthetic data, including drug repurposing and MNIST, are used to support claims of competitive accuracy and much lower runtime than deep-learning baselines.","tokens_in":49782,"tokens_out":8909,"duration_ms":79848,"significance":"F3I is a simple, fast, and reproducible imputer; the theoretical machinery (AdaHedge regret, concentration bounds on sub-Gaussian imputation errors) is internally coherent under Assumptions B.1-B.6, and the experimental study is extensive. The main advertised value is a distribution-preserving imputer with guarantees. However, the advertised distribution-preservation property is not what is proved: Theorem 4.4 bounds regret of a pointwise log-density ratio, which is a mode-seeking objective, and under the paper's independent-Gaussian assumption this objective shrinks imputed values toward feature means rather than preserving the true distribution. The MSE bound in Theorem 4.2 does not depend on the learned weights and therefore does not establish a benefit of F3I over initial KNN imputation. These issues substantially weaken the paper's central claim.","major_comments":[{"comment":"The title and abstract promise 'distribution-preserving guarantees,' but the quantity bounded in Theorem 4.4 is the cumulative regret of G*(alpha,X)=1/N sum_i log(D*(x_i(alpha))/D*(x_i))-eta||alpha||^2. This is a pointwise log-density ratio, not a divergence between the imputed and true distributions. Maximizing G is mode-seeking: it moves imputed points toward high-density regions of D* rather than sampling from D*. Under Assumption B.1 the features are independent Gaussians, so observed coordinates are independent of a missing coordinate; the MSE-optimal imputation is the feature mean, and every non-degenerate convex combination of K neighbors has excess variance. The density objective then favors weights that shrink imputed values toward the mean. This is the opposite of preserving the data distribution, and it explains why mean imputation is reported as competitive or better on MCAR/MAR synthetic data (Appendix H.1.2). A low regret bound with respect to G* therefore does not substantiate the paper's central distribution-preservation claim.","section":"Section 3.2 and Theorem 4.4"},{"comment":"The MSE bound is essentially a bound on the initial KNN imputation, not on the learned imputation weights. In the proof of Theorem D.1, Jensen's inequality is applied to an arbitrary alpha in Delta_K, and the resulting bound depends only on max_{i,j}||(x0)_j-(x*)_i||^2 via Corollary G.6; none of the steps use the F3I updates or the objective G. Consequently, the theorem does not show that F3I improves over uniform-KNN initial guesses, and it is not a distribution-preservation result. If the intended statement is 'any convex combination of the K initial neighbors has MSE O((sigma_miss)^2+ln N/F),' the theorem should say so explicitly.","section":"Theorem 4.2 and Appendix D"},{"comment":"Theorem 5.1 is conditional on Assumption B.8, which essentially assumes the full set of hypotheses of Theorem 2 of Yu et al. (PCGrad), including the angle condition, a step-size condition, and the Hessian inequality H(-G,alpha,alpha') >= w||g||^2. The appendix verifies convexity and Lipschitz continuity of -G (Proposition C.5 and Lemma F.1), but it does not verify the additional angle and curvature conditions for the specific F3I objective and logistic loss. As stated, the theorem is an application of an external result under unverified hypotheses. The authors should either prove those hypotheses for their setting or mark them explicitly as assumptions on the loss and step-size, rather than presenting Theorem 5.1 as a derived guarantee of PCGrad-F3I.","section":"Section 5, Eq. (2), and Assumption B.8"}],"minor_comments":[{"comment":"Proposition C.2 states that eta<4KN suffices for strict concavity, but the proof around Eq. (4) uses eta<4S^2K=4K; the statement and proof need to be reconciled.","section":"Proposition C.2"},{"comment":"Algorithm 2's neighbor-selection line ('1,2,...,K arg min_{j<=N} ...') is difficult to parse; it should explicitly say that K indices are chosen by increasing Chebyshev distance to x.","section":"Algorithm 2"},{"comment":"Assumption B.1's text writes (x*)_i ~ N_F(mu_f, sigma^2 I) with a scalar mu_f, while Algorithm 3 samples each coordinate from N(mu_f, sigma^2); use a vector mu in R^F consistently.","section":"Assumption B.1"},{"comment":"Figure 1 caption contains a typo: 'Emprical' should be 'Empirical.'","section":"Figure 1 caption"},{"comment":"The statement in Table 16's caption that TDM failed on Gottlieb is irrelevant because TDM is not among the selected baselines in that table; remove or clarify.","section":"Table 16 caption"}],"recommendation":"major_revision","confidential_remarks":"The manuscript contains a solid algorithmic core and transparent code, but the framing overclaims. I would be willing to consider a revised version that either proves a genuine distributional guarantee for a modified objective or explicitly redefines the contribution as a fast KNN imputer with MSE and log-density-regret bounds and removes the distribution-preservation language from the title and abstract. As it stands, the paper is likely to mislead readers about what is guaranteed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: F3I is a genuinely new algorithm and the paper is worth a serious referee, but the headline claim outruns the theorems. What is proved is a bound on pointwise log-density regret; what the title promises is distribution preservation, and that is not established.\n\nThe stress-tester's concern lands. Maximizing (1/N)Σ log[D0(x_i(α))/D0(x_i)] is mode-seeking: it moves imputed points toward the high-density region of D0, not toward draws from D0. Theorem 4.4 bounds cumulative regret on G*, a likelihood-improvement measure; no divergence between imputed and true distributions is bounded, no KL, Wasserstein, or variance match. Under Assumption B.1, observed features carry no information about a missing coordinate, so the MSE-optimal value is the feature mean, and any non-degenerate convex combination inflates variance. The density objective therefore shrinks imputed values toward the mean, which is the opposite of preserving the distribution. The paper's own synthetic experiments confirm this: mean imputation is the top contender under MCAR and MAR (Appendices H.1.2 and H.1.4). This is a conceptual gap in the central selling point, not a matter of loose constants.\n\nCredit where it is due. The algorithm is a real new combination: AdaHedge on KNN-combination weights against a Gaussian-kernel density-ratio objective, plus a PCGrad joint-training extension. It is fast, orders of magnitude faster than GAIN, GRAPE, and NewImp in the reported runs, and the empirical work is broad and honest: synthetic data up to 20,000 features, drug-repurposing sets, MNIST, and a candid limitations section. The subgaussian concentration analysis in Technical lemma 3, including the MNAR Gaussian self-masking case, is careful, and the MSE and regret bounds are genuine derivations under the stated assumptions.\n\nSoft spots, in proportion. The concavity proof (Proposition C.2) drops a factor of N: Technical lemma 1 bounds each ‖Z_{n_i}v‖² by 2KS‖v‖², so summing over i ≤ N gives 2KNS, not the 2KS written. The claim probably survives with adjusted constants, but the proof as written has a real gap. Also, the text says code is provided as supplementary material, but no link appears anywhere in the paper. Minor: the paper describes its own empirical results as 'superior performance' when F3I is often merely on par.\n\nBottom line: this paper is for imputation researchers, especially in high-dimensional biology, who want a fast KNN-style imputer and can read the guarantee as 'pointwise likelihood improvement' rather than distribution preservation. I would send it to peer review; the referee's main job is to force a reframing of the guarantee, a repaired concavity proof, and released code.","headline":"A genuinely new and fast KNN-based imputer with careful bounds, but the 'distribution-preserving guarantees' in the title are not what the theorems prove.","tokens_in":50347,"tokens_out":7418,"would_cite":true,"duration_ms":62999,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H12","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"F3I is a fast K-nearest-neighbor imputer that provably preserves the data distribution while bounding imputation error.","keywords":["missing data imputation","distribution preservation","K-nearest neighbors","online learning","AdaHedge","missingness mechanisms","not-missing-at-random","joint training"],"falsifier":"Take any dataset generated exactly by the paper's Algorithm 3 with the stated Gaussian assumptions and run F3I for all three missingness mechanisms across many seeds; if the imputation MSE ever exceeds the claimed bound $O((\\sigma_{\\mathrm{miss}})^2 + \\ln N / F)$ or the cumulative regret exceeds $C_{\\mathrm{AH}}\\sqrt{t} + H_{\\mathrm{miss}} h^{-1} t$ at the stated $1-1/N$ confidence, the theorem fails. A more behavior-level test, valid even where the assumptions fail, is to generate strongly correlated features and compare the probability of F3I's imputed values under the true data density with the probability of the initial KNN guesses: if maximizing $G$ lowers true-density probability, the algorithm is not preserving the distribution it claims to preserve.","tokens_in":49300,"feed_emoji":"🧩","tokens_out":9526,"duration_ms":81975,"temperature":0.7,"pith_summary":"The paper tries to show that missing values can be filled in quickly without destroying the shape of the data. Its algorithm, F3I, starts from a K-nearest-neighbor imputation and iteratively reweights the K neighbors by maximizing a concave objective that scores how much more probable the imputed point is under a Gaussian kernel density estimate than the previous guess. Under Gaussian data assumptions and for missing-completely-at-random, missing-at-random, and Gaussian self-masking not-missing-at-random mechanisms, the paper proves an imputation-error bound of $O((\\sigma_{\\mathrm{miss}})^2 + \\ln N / F)$ with probability $1 - 1/N$ and a cumulative-regret bound of $C_{\\mathrm{AH}}\\sqrt{t} + H_{\\mathrm{miss}} h^{-1} t$ against the best fixed neighbor weights. These guarantees matter because they make distribution preservation a provable property rather than a heuristic hope, and the same machinery extends to joint training with a classifier.","feed_headline":"KNN imputation can be both fast and distribution-preserving","feed_subtitle":"F3I reweights neighbors via online learning, bounding imputation error and regret for MCAR, MAR, and MNAR data.","key_machinery":"The central object is the function $G(\\alpha, X) = \\frac{1}{N}\\sum_{i\\le N}\\log\\frac{D_0(x_i(\\alpha))}{D_0(x_i)} - \\eta\\|\\alpha\\|_2^2$, where $\\alpha$ is a simplex of $K$ weights, $x_i(\\alpha)$ is the convex combination of the $K$ nearest neighbors of sample $i$, and $D_0$ is a Gaussian kernel density estimate over the initially imputed points. The function quantifies how much more probable the reweighted imputation is than the current guess. Concavity of $G$ for small regularization $\\eta$ and large enough bandwidth $h$ turns weight learning into convex optimization; Lipschitz gradients let the authors apply AdaHedge's no-regret bound and, with PCGrad, a joint-training bound. The telescoping sum identity is what connects per-round optimization to an end-to-end log-density improvement.","core_discovery":"On its own terms, the discovery is that the neighbor weights in a K-nearest-neighbor imputer can be tuned online so that imputed values are, with high probability, at least as probable under the data density as the initial guesses, while the mean squared error stays controlled. F3I formalizes distribution preservation through the ratio $D_0(x_i(\\alpha))/D_0(x_i)$ inside a Gaussian kernel density estimate, and the paper proves this objective is concave with a Lipschitz gradient. The no-regret learner AdaHedge then supplies the weight sequence, and the paper's Theorem 4.4 bounds the cumulative regret of that sequence against the a posteriori best fixed weights; Theorem 4.2 bounds the MSE. The proofs use a high-probability concentration bound on the initial KNN error, which is where the independence-in-Gaussians assumption enters.","pith_inferences":["If the independence assumption B.1 is violated, as it is in most real data, the theoretical bounds do not apply, and the density-ratio objective may actually favor shrinking values toward the mean, which would reduce variance rather than preserve the data distribution; the real-data experiments, not the theorems, carry the practical case.","Re-estimating the kernel density on the currently imputed points at each round, which the paper names as future work, would likely replace the linear $H_{\\mathrm{miss}} h^{-1} t$ regret term with a vanishing term and make the distribution-preservation guarantee match the objective being optimized.","The same online-reweighting scheme could be combined with any base imputer whose output is a convex combination with Lipschitz-continuous gradient, potentially extending the guarantees to linear or shallow-network imputers without changing the regret analysis."],"forward_implications":["Under the assumed Gaussian model, the imputation MSE is $O((\\sigma_{\\mathrm{miss}})^2 + \\ln N / F)$ with probability $1-1/N$, so larger data variance worsens imputation while more features or more samples improve it.","The cumulative regret against the best fixed neighbor weights is $C_{\\mathrm{AH}}\\sqrt{t} + H_{\\mathrm{miss}} h^{-1} t$, meaning the online learner is not asymptotically worse than the optimal static weight vector, apart from a linear term that the paper attributes to using a fixed initial density estimate.","The joint-training version PCGrad-F3I has the same guarantee with a classifier loss: setting $\\beta=0$ recovers the imputation-only bound and $\\beta=1$ recovers the classical AdaHedge regret bound on the downstream loss.","Because weight updates are single online steps, the per-iteration cost is $O(NK(\\log N + F))$ after an $O(FN\\log N)$ preprocessing step, which is why the method runs orders of magnitude faster than graph, diffusion, and GAN imputers in the experiments."],"supporting_citations":[{"why":"Supplies the uniform-weight K-nearest-neighbor imputation that F3I starts from and the distance-weighted KNN baseline.","marker":"[19]"},{"why":"Provides AdaHedge, the no-regret online learner whose regret bound underpins Theorems 4.4 and 5.1.","marker":"[24]"},{"why":"Gives the subgaussian concentration inequalities used to bound the initial imputation error in Technical lemma 3 and Corollary G.6.","marker":"[68]"},{"why":"Defines the Gaussian self-masking MNAR mechanism adopted as Assumption B.4 and supplies the NeuMiss baseline.","marker":"[18]"},{"why":"Contributes PCGrad gradient surgery, whose assumptions are invoked in Theorem 5.1 for joint imputation-classification training.","marker":"[35]"}],"fun_headline_variants":["Online KNN reweighting preserves data distribution with bounds","F3I imputation learns weights online, guarantees distribution fit","Imputation with no-regret learning: KNN reweighted for distribution","Adaptive KNN weights keep imputed data distributional quality","Theoretical guarantees for fast KNN imputation via AdaHedge"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every entry of the complete data matrix is drawn independently from a Gaussian with the same spread, meaning the observed features carry no information about a missing value; if real data have correlated features or heavy tails, the paper's mathematical guarantees stop applying.","fun_headline_variants_meta":{"raw":{"variants":["Online KNN reweighting preserves data distribution with bounds","F3I imputation learns weights online, guarantees distribution fit","Imputation with no-regret learning: KNN reweighted for distribution","Adaptive KNN weights keep imputed data distributional quality","Theoretical guarantees for fast KNN imputation via AdaHedge"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000198,"raw_usage":{"total_tokens":1341,"prompt_tokens":890,"completion_tokens":451,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":362}},"tokens_in":506,"tokens_out":451,"duration_ms":3924,"temperature":1.0,"reasoning_tokens":362,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:36:58.946992+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any dataset generated exactly by the paper's Algorithm 3 with the stated Gaussian assumptions and run F3I for all three missingness mechanisms across many seeds; if the imputation MSE ever exceeds the claimed bound $O((\\sigma_{\\mathrm{miss}})^2 + \\ln N / F)$ or the cumulative regret exceeds $C_{\\mathrm{AH}}\\sqrt{t} + H_{\\mathrm{miss}} h^{-1} t$ at the stated $1-1/N$ confidence, the theorem fails. A more behavior-level test, valid even where the assumptions fail, is to generate strongly correlated features and compare the probability of F3I's imputed values under the true data density with the probability of the initial KNN guesses: if maximizing $G$ lowers true-density probability, the algorithm is not preserving the distribution it claims to preserve.","supporting_citations":[{"cited_title":"Missing value estimation methods for dna microarrays","cited_arxiv_id":null,"evidence_quote":"Supplies the uniform-weight K-nearest-neighbor imputation that F3I starts from and the distance-weighted KNN baseline."},{"cited_title":"Follow the leader if you can, hedge if you must","cited_arxiv_id":null,"evidence_quote":"Provides AdaHedge, the no-regret online learner whose regret bound underpins Theorems 4.4 and 5.1."},{"cited_title":"Neumiss networks: differentiable programming for supervised learning with missing values","cited_arxiv_id":null,"evidence_quote":"Defines the Gaussian self-masking MNAR mechanism adopted as Assumption B.4 and supplies the NeuMiss baseline."},{"cited_title":"Gradient surgery for multi-task learning","cited_arxiv_id":null,"evidence_quote":"Contributes PCGrad gradient surgery, whose assumptions are invoked in Theorem 5.1 for joint imputation-classification training."}],"review_version":1}