{"id":"81b72305-14e6-4371-a9bc-517b3ccb9caa","arxiv_id":"1908.00735","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Counterfactual explanations for LVQ classifiers can be computed by solving closed-form linear, quadratic, or non-convex QCQP programs derived from the nearest-prototype rule, yielding faster and closer counterfactuals than generic optimizers.","lead":"The paper derives convex and non-convex optimization programs that compute counterfactual explanations for learning vector quantization classifiers, replacing generic black-box search with model-specific solvers. A reader interested in practical explainability or recourse for prototype-based models would read this for faster, higher-quality counterfactual computation that also allows domain constraints.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"LGMLVQ results rest on an approximate QCQP solver whose success rate is unreported; Table 1 may include invalid counterfactuals in the 'Ours' column.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: the local-metric counterfactual claim rests on an approximate non-convex QCQP solver whose feasibility of returned solutions is never verified. This is the single most load-bearing issue because the central contribution has two parts: exact convex programs for global metrics and approximate programs for local metrics. The first part is rigorously derived and empirically supported; the second part is only as strong as the heuristic solver's ability to produce valid counterfactuals. Without a success rate or feasibility check, the LGMLVQ rows in Table 1 cannot be interpreted. The reader's CONDITIONAL verdict is appropriate, so no verdict change is needed. I see no comparable concern in the global-metric derivations; the minor factor-of-two in the epsilon margin between Eq. (9b) and Eq. (12) is a harmless constant, and the lack of error bars is secondary to the feasibility gap.","tokens_in":11213,"tokens_out":8770,"duration_ms":85995,"concrete_test":"Using the released code, re-run the LGMLVQ experiments (three datasets, 4-fold CV) and for each returned x' evaluate the original constraints d(x', p_i) + epsilon <= d(x', p_j) for every non-yc prototype p_j, with the same epsilon used in the paper. Record the percentage of returned points that violate any constraint, and recompute the mean Manhattan distance both for all returned points and for the subset that satisfies all constraints. If the violation rate is above a few percent or the recomputed mean differs materially from Table 1's LGMLVQ column, the paper must report and discuss the discrepancy; if the violation rate is zero and the means are stable, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction in Eq. (9) is algebraically sound: for global-metric LVQ the constraints (9b) become linear inequalities (Eq. 12-13), so the GLVQ/GMLVQ claims are supported by exact LP or convex QP solvers. The load-bearing weakness is the localized-metric case. For LGMLVQ the constraints are the non-convex QCQP (14). Section 6.4 proposes to solve this with the penalty convex-concave procedure within the Suggest-Improve framework, but the paper never reports the success rate of this heuristic on the actual LGMLVQ experiments. Table 1's caption explicitly reports the baseline failure rate ('in 5% to 60% of the cases no solution was found') but is silent about 'Ours'. If cvx-qcqp returned solutions that violate (9b) and those were discarded or silently accepted, the mean Manhattan distances in the LGMLVQ rows could be artificially low (if infeasible solutions were discarded) or not correspond to counterfactuals at all (if violations were accepted). Because the QCQP is NP-hard, approximate solvers can return infeasible points; feasibility is not automatic. This gap does not affect the global-metric claims but directly undermines the local-metric empirical claim in Section 4.4.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses efficient computation of counterfactual explanations for learning vector quantization (LVQ) classifiers. The authors formulate the search for a counterfactual x' with desired label yc as minimizing a change penalty theta(x', x) subject to d(x', p_i) + eps <= d(x', p_j) for a chosen target prototype p_i of label yc and every prototype p_j of another label. For global-metric LVQ (GLVQ/GMLVQ) the constraints are linear, yielding an LP for weighted Manhattan and a convex QP for Euclidean regularization. For localized matrix LVQ (LGMLVQ) the constraints form a non-convex QCQP, which the authors propose to solve approximately with the Suggest-Improve framework using penalty CCP. Experiments on three datasets compare mean Manhattan distances with Downhill-Simplex and CMA-ES baselines and report speed-ups of 1.5 to 158 times. The algebraic derivations in Section 6 are self-contained and the convex reductions are exact.","tokens_in":11487,"tokens_out":7476,"duration_ms":69400,"significance":"The central reduction is valuable and largely sound. The derivation of the linear constraints for global-metric LVQ is exact, the formulation is free of fitted parameters, and the release of code supports reproducibility. The identification of LGMLVQ counterfactuals as a difference-of-convex program is a useful observation. If the empirical gaps described below are closed, the paper would provide a practical improvement over black-box counterfactual search for prototype classifiers. The current experimental support is incomplete for the local-metric case, so the full strength of the claims is not yet established.","major_comments":[{"comment":"The LGMLVQ comparison is not currently interpretable because the success rate of the proposed approximate solver is not reported. The caption only reports that DS/CMA-ES fail in 5% to 60% of cases for LGMLVQ; no analogous information is given for the 'Ours' column. Since the QCQP in Eq. (14) is NP-hard and the penalty CCP heuristic can return points violating the constraints in Eq. (9b), the reported mean Manhattan distances for LGMLVQ may be computed over a biased subset (if infeasible solutions were discarded) or may not correspond to valid counterfactuals (if constraint violations were accepted). Please report the fraction of runs in which the returned solution satisfies all constraints of Eq. (14), and either report means over all runs or explicitly separate feasible and infeasible outcomes.","section":"Section 4.4, Table 1"},{"comment":"The experimental comparison reports only mean Manhattan distances over 4-fold cross-validation, with no standard deviations, confidence intervals, or significance tests. Some differences are small (e.g., LGMLVQ digits: 8.12 vs 7.88 vs 7.53), and without variance information the claim that the proposed method yields counterfactuals that are closer is not statistically supported. Add error bars, per-fold values, or a statistical test.","section":"Section 4.4, Table 1"},{"comment":"The efficiency claim that the method is between 1.5 and 158.0 times faster is stated without reporting actual runtime measurements or the experimental setup for timing. Since efficiency is one of the two main empirical contributions, please include a table of runtimes with variance and describe the hardware/software environment.","section":"Section 4.4"}],"minor_comments":[{"comment":"The statement that the formulation 'does not include hyperparameters' is imprecise because the margin epsilon in Eq. (9b) is a user-chosen constant; rephrase to say there is no regularization-weight hyperparameter C as in Eq. (1).","section":"Section 4.1, Eq. (9)"},{"comment":"In the expansion of d(x', p_i) < d(x', p_j), the term p_j^T Omega_i p_j should read p_j^T Omega_j p_j; the subsequent definition of r_ij in Eq. (27) is consistent with the corrected version.","section":"Appendix 6.3, Eq. (24)"},{"comment":"The left-hand sides of these equivalences are written as d(x, p_i) < d(x, p_j) but should refer to x'; the constraints are about the counterfactual x'.","section":"Appendix 6.3, Eq. (28) and Eq. (31)"},{"comment":"The assertion that p_i is always feasible in Eq. (9) assumes the distance functions are positive definite; for PSD localized matrices another prototype could be at zero distance from p_i, making the epsilon margin infeasible. Please state the required positive-definiteness assumption or describe how ties are handled.","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and the core derivation is sound. The main risk is the unreported feasibility rate of the heuristic solver for the LGMLVQ experiments; if the authors supply feasibility counts and variance estimates, the manuscript would be acceptable. I see no concerns about novelty disclosure or citation behavior."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a look if you care about counterfactual explanations for prototype-based classifiers. The core idea is simple and correct: for LVQ models, the condition that a counterfactual be closer to a target prototype than to all others can be written down explicitly. For global-metric LVQ (GLVQ/GMLVQ), the constraints expand to linear inequalities, so the counterfactual search becomes an LP or a convex QP. For localized matrix LVQ (LGMLVQ), the constraints become a non-convex QCQP, which they solve approximately with the Suggest-Improve framework. The derivations in the appendix are algebraically sound, and the paper is honest that the QCQP case is NP-hard.\n\nWhat is genuinely useful: the model-specific encodings are new relative to the model-agnostic baselines (Wachter et al., Laugel et al.), and they are exact for the global-metric case. The formulation also makes it easy to add box constraints or other domain knowledge, which is a nice practical feature. The code is on GitHub, so the work is reproducible.\n\nThe soft spots are in the empirical section. The LGMLVQ rows in Table 1 rely on an approximate solver whose success rate is never reported. The caption gives failure rates for the DS and CMA-ES baselines (5–60% of cases), but says nothing about how often their own QCQP solver returns a feasible point. If infeasible solutions were discarded, the reported means are biased; if they were accepted, the numbers may not be counterfactuals at all. The paper needs to report feasibility counts and, ideally, what happens on the failed cases. This does not hurt the global-metric claims, which rest on exact convex solvers, but it directly undermines the localized-metric comparison.\n\nTwo smaller issues: Table 1 reports only means across the four folds, with no error bars or spread; and the epsilon margin in constraint (9b) is never specified, even though it affects the achievable distance. The speed-up claim (1.5x–158x) is stated but no timing table is included.\n\nOverall, the central derivation holds up. The global-metric contribution is solid and should be published; the localized-metric empirical claim needs an additional feasibility analysis. The paper deserves peer review, but a serious referee should ask for the missing numbers before it is accepted.","headline":"Solid LP/QP encodings for LVQ counterfactuals; the LGMLVQ empirical claims need a feasibility report before they are fully trusted.","tokens_in":11979,"tokens_out":3055,"would_cite":true,"duration_ms":30854,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","90C20","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"For LVQ classifiers, a counterfactual explanation is an exact LP or convex QP under a global metric and an efficiently approximated QCQP under prototype-specific metrics.","keywords":["counterfactual explanations","learning vector quantization","prototype-based classifiers","convex optimization","quadratically constrained quadratic programming","metric learning","localized matrix LVQ","explainable AI"],"falsifier":"Run the approximate solver for the localized-metric counterfactual program on a test set, check constraint (9b) exactly for each returned point, and count violations; if a substantial fraction violate the constraint, the reported mean distances for the localized-metric case would not represent valid counterfactuals.","tokens_in":1953,"feed_emoji":"🎯","tokens_out":4691,"duration_ms":112806,"temperature":0.7,"pith_summary":"This paper argues that for learning vector quantization models, counterfactual explanations can be computed by exploiting the winner-takes-all structure instead of treating the model as a black box. It reduces the search to Eq. (9), a per-prototype constrained optimization that is a linear program for Manhattan distance, a convex quadratic program for Euclidean distance with a global metric, and a non-convex quadratically constrained quadratic program when each prototype has its own distance matrix. The consequence is that counterfactuals can be found exactly or approximately much faster and with smaller changes than model-agnostic search, and domain knowledge can be added as extra constraints. Experiments on three datasets support the speed and closeness advantages.","feed_headline":"Counterfactuals for LVQ models become fast convex programs","feed_subtitle":"Global-metric LVQ yields exact LPs and QPs; local metrics get a structured approximation.","key_machinery":"The load-bearing object is Eq. (9), the per-target-prototype program: minimize $\\theta(\\vec x', \\vec x)$ subject to $d(\\vec x', \\vec p_i)+\\epsilon \\le d(\\vec x', \\vec p_j)$ for every prototype $\\vec p_j$ whose label differs from the requested label $y_c$. The small positive $\\epsilon$ keeps the counterfactual off the decision boundary. Expanding the distance inequality gives linear constraints $\\vec x'^\\top \\vec q_{ij} + r_{ij} + \\epsilon \\le 0$ when one global metric $\\Omega$ is used, and quadratic constraints $\\tfrac{1}{2}\\vec x'^\\top Q_{ij}\\vec x' + \\vec x'^\\top \\vec q_{ij} + r_{ij} + \\epsilon \\le 0$ with $Q_{ij}=\\Omega_i-\\Omega_j$ when metrics are prototype-specific. The indefinite difference matrix is what turns the localized-metric case into an NP-hard non-convex QCQP; the paper's approximate route splits each constraint into a difference of convex functions $f(\\vec x')-g(\\vec x')\\le 0$, linearizes $g$ around the current iterate, and uses the penalty convex-concave procedure within the Suggest-Improve framework.","core_discovery":"The central claim is that because an LVQ model labels a point by its nearest prototype, a counterfactual for a desired label $y_c$ can be obtained by solving, for each prototype $\\vec p_i$ with label $y_c$, the problem of minimizing the change $\\theta(\\vec x', \\vec x)$ under the constraints $d(\\vec x', \\vec p_i) + \\epsilon \\le d(\\vec x', \\vec p_j)$ for every prototype $\\vec p_j$ of a different label, then keeping the solution with the smallest change. When all prototypes share one metric, the constraints are linear in $\\vec x'$, so the problem is a linear program (weighted Manhattan regularization) or a convex quadratic program (Euclidean regularization) and can be solved exactly and efficiently. When each prototype or class has its own metric, the constraints become quadratic with matrices $Q_{ij}=\\Omega_i-\\Omega_j$, which are symmetric but indefinite, making the problem a non-convex QCQP that the paper solves approximately by rewriting it as a difference of convex functions and applying the penalty convex-concave procedure. On breast cancer, handwritten digits, and house-price data, the method returns counterfactuals with smaller mean Manhattan distance than Downhill-Simplex or CMA-ES baselines and runs 1.5 to 158 times faster.","pith_inferences":["The same reduction should apply to any nearest-prototype classifier whose distance is a quadratic form, such as metric-based nearest-centroid classifiers; convexity depends only on whether each prototype has its own distance matrix.","A reader extending the method should measure the fraction of approximate QCQP solutions that actually satisfy constraint (9b); the paper only reports failure rates for the baseline methods, so an invalid-solution count would clarify whether the localized-metric comparison is representative.","Counterfactuals computed in a PCA-reduced space may not be minimal in the original feature space; an extension would enforce the constraints and measure the change directly in the original space."],"forward_implications":["For any LVQ with a global metric, counterfactual computation becomes an off-the-shelf LP or convex QP, removing the need for expensive black-box search and giving exact or unique (up to equivalence) solutions.","Because Eq. (9) has no regularization hyperparameter $C$, counterfactual selection no longer depends on tuning a loss-versus-change trade-off.","Domain knowledge such as box constraints, frozen features, or linear inequalities between features can be added as convex constraints without changing the problem class or its complexity.","The per-target-prototype loop parallelizes directly, so runtime scales with the number of prototypes carrying the requested label.","Experiments report smaller mean Manhattan distances and speedups between 1.5 and 158 times over Downhill-Simplex and CMA-ES baselines, with the baselines failing to find any counterfactual in 5% to 60% of localized-metric cases."],"supporting_citations":[{"why":"Defines counterfactual explanations as Eq. (1), the loss-plus-penalty optimization that this paper replaces with a constraint formulation.","marker":"[19]"},{"why":"Reviews LVQ and supplies the nearest-prototype winner-takes-all classification rule formalized in Eq. (5).","marker":"[22]"},{"why":"Introduces GMLVQ with a global relevance matrix, the setting in which Section 4.2 derives linear constraints.","marker":"[23]"},{"why":"Introduces localized matrix-LVQ models with prototype-specific metric matrices, yielding the difference $Q_{ij}=\\Omega_i-\\Omega_j$ in the constraints.","marker":"[24]"},{"why":"Gives the linear and quadratic convex programming theory that makes the global-metric cases exactly solvable.","marker":"[28]"},{"why":"Supplies the Suggest-Improve heuristic and penalty convex-concave procedure used to approximately solve the non-convex QCQP.","marker":"[29]"},{"why":"Provides the baseline optimizer implementation used in the comparison experiments.","marker":"[33]"},{"why":"Provides the breast cancer dataset used in all three model comparisons.","marker":"[30]"},{"why":"Provides the handwritten digits dataset used in all three model comparisons.","marker":"[31]"},{"why":"Provides the Ames housing dataset and its binary target construction used in the experiments.","marker":"[32]"}],"fun_headline_variants":["LVQ counterfactuals become exact convex programs","Exact counterfactuals for LVQ via convex optimization","Counterfactuals for LVQ: convex programs for speed and exactness","LVQ counterfactuals: fast exact LPs, QPs, and approximate QCQPs","Prototype-based counterfactuals solved as convex programs"],"cache_read_input_tokens":14080,"weakest_assumption_plain":"For localized-metric LVQ, the paper relies on an approximate solver returning points that genuinely satisfy the nearest-prototype constraints, but it reports the failure rate of the baselines only, not its own solver's validity rate.","fun_headline_variants_meta":{"raw":{"variants":["LVQ counterfactuals become exact convex programs","Exact counterfactuals for LVQ via convex optimization","Counterfactuals for LVQ: convex programs for speed and exactness","LVQ counterfactuals: fast exact LPs, QPs, and approximate QCQPs","Prototype-based counterfactuals solved as convex programs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000976,"raw_usage":{"total_tokens":4126,"prompt_tokens":907,"completion_tokens":3219,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":3130}},"tokens_in":523,"tokens_out":3219,"duration_ms":22055,"temperature":1.0,"reasoning_tokens":3130,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:33:40.548220+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the approximate solver for the localized-metric counterfactual program on a test set, check constraint (9b) exactly for each returned point, and count violations; if a substantial fraction violate the constraint, the reported mean distances for the localized-metric case would not represent valid counterfactuals.","supporting_citations":[{"cited_title":"Est´ evez","cited_arxiv_id":null,"evidence_quote":"Reviews LVQ and supplies the nearest-prototype winner-takes-all classification rule formalized in Eq. (5)."},{"cited_title":"Ad aptive relevance matrices in learning vector quantization","cited_arxiv_id":null,"evidence_quote":"Introduces GMLVQ with a global relevance matrix, the setting in which Section 4.2 derives linear constraints."},{"cited_title":"Di stance learning in discriminative vector quantization","cited_arxiv_id":null,"evidence_quote":"Introduces localized matrix-LVQ models with prototype-specific metric matrices, yielding the difference $Q_{ij}=\\Omega_i-\\Omega_j$ in the constraints."},{"cited_title":"Convex Optimization","cited_arxiv_id":null,"evidence_quote":"Gives the linear and quadratic convex programming theory that makes the global-metric cases exactly solvable."},{"cited_title":"Ceml: Counterfactuals for explaining m achine learning models - a python toolbox","cited_arxiv_id":null,"evidence_quote":"Provides the baseline optimizer implementation used in the comparison experiments."},{"cited_title":"Mangasarian William H","cited_arxiv_id":null,"evidence_quote":"Provides the breast cancer dataset used in all three model comparisons."},{"cited_title":"Alpaydin and C","cited_arxiv_id":null,"evidence_quote":"Provides the handwritten digits dataset used in all three model comparisons."},{"cited_title":"Ames, iowa: Alternative to the boston hous ing data as an end of semester regression project","cited_arxiv_id":null,"evidence_quote":"Provides the Ames housing dataset and its binary target construction used in the experiments."}],"review_version":1}