{"id":"1f9b04b8-5cf8-4612-ad24-11dea66b9d51","arxiv_id":"1908.06515","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"A column and constraint generation framework, warm-started from Lasso solutions, solves large Dantzig selector, basis pursuit, and fused Dantzig problems far faster than existing solvers.","lead":"The authors show that a classic linear programming technique, column and constraint generation, combined with a Lasso warm start and a simplex solver, can compute Dantzig selector and related sparse recovery estimators with millions of variables in minutes. A generalist might read this because it removes a long-standing computational barrier that has kept the statistically attractive Dantzig selector from being used at scale.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 2.4's inverse matrix H (Eq. 14) is not D^{-1}; the stated formula makes DH singular, so the fused Dantzig LP (Eq. 17) is not provably equivalent to the fused Dantzig selector (Eq. 7), leaving Tables 6–7 unsupported.","rationale":"The paper is a well-executed empirical study of column/constraint generation for l1-DS and basis pursuit, and those parts of the central claim are plausible and supported by the experiments. However, the fused Dantzig selector is explicitly one of the three estimator classes in the abstract and introduction, and its derivation contains a concrete mathematical error: the matrix H defined in Eq. 14 is not the inverse of D. This is not a matter of tuning or reporting; it affects whether the LP being solved is actually the claimed estimator. The reader's weakest-assumption analysis focused on sparsity and the quality of the Lasso initialization, which is a legitimate scoping condition but is disclosed and demonstrated by the paper's own Table 3. The H error is more load-bearing because if the implementation follows the printed derivation, the fused experiments solve a different problem. A small numerical verification would settle this. The l1-DS and BP results could stand independently, so I would not reject the whole paper; rather, acceptance should be conditional on correcting or clearly re-deriving the fused Dantzig formulation and confirming that the reported fused experiments solve (7).","tokens_in":17057,"tokens_out":15647,"duration_ms":167388,"concrete_test":"For p=4, compute D=[e_1^T;D^{(0)}] and H by Eq. 14 and verify whether DH=I; it will fail. Then take a small fused instance (e.g., n=p=10) and solve (7) using the correct H = inv(D), solve (17) as implemented in the public repository, and solve (16) directly with H_B^T; compare the recovered β. If (17) differs from the two correct formulations, the Tables 6–7 experiments solve a different problem and the fused Dantzig claim must be withdrawn or re-scoped.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The fused Dantzig selector is a headline application, and its derivation rests on an explicit mathematical error. Equation 14 defines H_{i,j}=1 if j=1, i−j if i>j, and 0 otherwise, claiming H=D^{-1} for D=[e_1^T; D^{(0)}]. For p=4 this H has a zero fourth column and its second row is [1,0,0,0]; multiplying by D gives (DH)_{2,4}=0, so H is not invertible and DH≠I. Consequently (16), which uses H_B^T(y−H\\alpha), and (17), which substitutes g=D^T r with g_A=0, are not equivalent: H_A^T r = \\sum_i r_i while (D^T r)_1 = r_1. Thus the LP solved for the experiments in Section 3.3 does not provably solve the fused Dantzig selector (7). The l1-DS and basis pursuit claims are not affected by this specific issue, but the fused claim, including the n=p≈5×10^5 results in Table 6 and the regression results in Table 7, is unsupported unless the implementation uses a different, correct H.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops DantzigLP, a column- and constraint-generation framework for solving large-scale linear-programming formulations of three sparse-estimation problems: the ℓ1-Dantzig selector, basis pursuit, and the fused Dantzig selector. The method solves reduced LPs over a subset of columns and constraints, checks optimality through dual violations and reduced costs, and warm-starts from solutions of related Lasso-type problems. The authors report experiments on synthetic and two real datasets showing large speedups over ADMM implementations, the parametric simplex method (PSM), and direct LP solves with Gurobi, and they provide a Julia implementation.","tokens_in":17334,"tokens_out":10360,"duration_ms":106087,"significance":"If the results hold, the paper addresses a real gap: LP-based Dantzig-type estimators are statistically attractive but are rarely used at scale because general-purpose LP solvers struggle with p in the millions. The idea of using classical column and constraint generation with a simplex solver and a Lasso initialization is clean and well motivated, and the pseudocode is precise enough to reimplement. The ℓ1-Dantzig selector and basis pursuit experiments support the central efficiency claim for sparse regimes, and the code release is a concrete strength. However, the fused Dantzig selector section contains a mathematical error in the claimed inverse matrix H, so the fused results in Tables 6 and 7 are not supported as written; in addition, the introduction's \"few minutes\" scalability claim is inconsistent with the 3,702-second Boston1M result in Table 4.","major_comments":[{"comment":"The matrix H defined by H_{i,j}=1 if j=1, H_{i,j}=i-j if i>j, and 0 otherwise is not the inverse of D=[e_1^T; D^(0)]. For p=4, the fourth column of H is zero and (DH)_{2,4}=0, so DH is not the identity; the correct inverse is the lower-triangular matrix of ones. Because this H is used in Eqs. (15)-(17), the derivation of the fused Dantzig selector LP is not valid: the constraints g_A=0 and g_B in [-lambda, lambda] in Eq. (17) do not represent H_A^T r=0 and ||H_B^T r||_inf <= lambda from Eq. (16). The regression reduction in §2.4.2 inherits the same issue, and Tables 6 and 7 therefore do not demonstrate solutions of (7) or (16) as written. Please correct H, rederive the reformulation, and either confirm that the reported experiments used the corrected formulation or regenerate the fused Dantzig experiments.","section":"§2.4, Eq. (14)"},{"comment":"The introduction claims that DantzigLP can solve instances of the ℓ1-DS problem with n≈10^3 and p≈10^6 \"within a few minutes,\" but the only p≈10^6 experiment reported, Boston1M in Table 4 with n=200, takes 3,702 seconds (about 62 minutes), and no synthetic instance with p≈10^6 is shown. As written, this scalability claim is not supported by the evidence. Please either temper the claim, distinguish the regimes in which the stated runtimes are observed, or provide an experiment with n≈10^3 and p≈10^6 that completes in the claimed time.","section":"Introduction and Table 4"},{"comment":"The efficiency of DantzigLP depends on the premise that the Dantzig selector solution is sparse and close to the Lasso support. Table 3 shows this dependence clearly: DantzigLP (Path) rises from 13.6 seconds at tau=1.0 to 209 seconds at tau=0.1 as the solution becomes denser, and the text acknowledges that DantzigLP can be slower than the full LP for small p. Because this is a central boundary condition on the method, the abstract and conclusion should state the sparsity regime explicitly rather than relying on the phrase \"in many settings.\"","section":"§2.2 and Table 3"}],"minor_comments":[{"comment":"Runtimes are reported only as means over replications; given the variability typical of simplex-based and column/constraint-generation methods, reporting standard deviations or median/interquartile ranges would make the comparisons substantially more informative.","section":"Tables 1–3, 5, 7"},{"comment":"The sentence \"Combining column and constraint generation LP techniques with methods for finding good initializations for the initial column and constraint sets I and J, we develop DantzigLP, a general framework for solving large-scale versions of the the Dantzig Selector-type problems\" contains a duplicated \"the.\"","section":"§2.1"},{"comment":"The heading \"F used Dantzig Selector\" contains an extra space and should be \"Fused Dantzig Selector.\"","section":"§2.4"},{"comment":"The sentence \"the initial solution obtained from the Lasso problem (5)\" should refer to the fused Lasso problem (5) rather than the Lasso problem (3), to avoid confusion between the two regularizers.","section":"§3.3"},{"comment":"The pseudocode in Algorithms 2 and 3 uses exact violation checks, while Section 2.2 defines a relaxed version with tolerance epsilon=10^{-4} that is used in the experiments; the pseudocode should incorporate this tolerance to match the implementation.","section":"Algorithms 2–3 and §2.2"},{"comment":"The DantzigLP runtimes include the Lasso initialization, but the table reports only the combined time; decomposing the runtime into initialization versus column/constraint generation would clarify where the 3,702 seconds for Boston1M is spent.","section":"Table 4"}],"recommendation":"major_revision","confidential_remarks":"The fused Dantzig selector section contains a substantive mathematical error that affects a headline contribution; the correction is likely local to Section 2.4, but the experimental tables for that problem will need to be regenerated or explicitly justified. The ℓ1-DS and basis pursuit material appears sound and is the strongest part of the paper. The authors should also be asked to reconcile the \"few minutes\" claim in the introduction with the Boston1M runtime."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the core idea is good: classical column and constraint generation, warmed up by a Lasso solution and run on a simplex LP solver, actually does solve Dantzig selector and basis pursuit instances at p≈10^5–10^6 in minutes. The experiments look convincing, the code is on GitHub, and this is a genuine practical advance over the ADMM and homotopy solvers they compare against. Second, the fused Dantzig section has a real mathematical error. Equation (14) defines H as a matrix that is not D^{-1}; the stated formula gives a singular H with a zero last column and wrong off-diagonal entries. Since the derivation of (16) and (17) depends on H being the inverse of D, the LP they solve in Section 3.3 is not provably the fused Dantzig selector. Tables 6 and 7 are therefore unsupported unless the implementation silently uses a different, correct H. That needs to be fixed, and the experiments rerun, before the fused claims can be taken seriously.\n\nWhat's actually new: applying column and constraint generation to the Dantzig selector, basis pursuit, and a fused-Dantzig formulation, with careful LP reformulations that avoid forming X^T X and exploit the banded difference operator. The Lasso initialization is a sensible and well-motivated trick; their ablation study in Figure 2 shows it matters. The comparisons against PSM and flare are fair and the reported speedups are plausible for the l1-DS and BP problems.\n\nSoft spots beyond the fused error: runtimes are means without error bars, and the number of replications is modest. Table 3 shows the method degrades sharply when the solution is denser, so the \"solves p≈10^6\" claim is conditional on sparsity. These are minor relative to the H problem. Also, no commit hash is given for the code, which slightly weakens reproducibility, though the repo is public.\n\nVerdict: the l1-DS and basis pursuit parts deserve serious refereeing; the fused section must be corrected before the paper is publishable as is. Send to peer review with a request for a careful check of Section 2.4, and rerun the fused experiments with the correct H. A reader primarily interested in the Dantzig selector will get real value from this paper.","headline":"Useful large-scale Dantzig selector / basis pursuit solver, but the fused Dantzig section has a wrong inverse matrix that invalidates those results as written.","tokens_in":17845,"tokens_out":4661,"would_cite":true,"duration_ms":44205,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C05","90C06","62J07"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that the Dantzig selector, basis pursuit, and fused Dantzig selector—three sparse-signal recovery problems normally too large for general LP solvers—can be solved at scales of $n\\approx 10^3$ and $p\\approx 10^6$ in…","keywords":["Dantzig selector","basis pursuit","fused Dantzig selector","column generation","constraint generation","simplex warm starts","Lasso initialization","sparse signal recovery"],"falsifier":"Construct an $\\ell_1$-DS instance with $n\\approx 10^3$, $p\\approx 10^6$ in which the true solution has about $p/2$ nonzero entries of comparable size, run DantzigLP with the Lasso warm start, and record total simplex iterations and runtime: if it still finishes in minutes the claim is stronger than the paper argues, while if it takes as long as or longer than solving the full LP, the paper's efficiency claim is limited to sparse solutions.","tokens_in":16874,"feed_emoji":"🧮","tokens_out":7321,"duration_ms":71091,"temperature":0.7,"pith_summary":"The paper argues that sparse-signal estimation problems usually treated as hard large-scale linear programs become routinely solvable when two classical LP techniques are revived. Instead of handing the full problem to a solver, the method solves small subproblems over few selected columns and few selected constraints, expanding them only when optimality conditions fail. Initializing those subproblems with the solution of the closely related Lasso keeps the number of expansions small. If the argument holds, Dantzig-selector-type estimators that were impractical at million-variable scale become usable in minutes.","feed_headline":"Column generation cracks million-variable Dantzig selector in minutes","feed_subtitle":"Lasso-warm-started column and constraint generation brings sparse recovery LPs that were out of reach down to minutes.","key_machinery":"The machinery is a reduced master LP coupled with pricing and separation. For the $\\ell_1$-DS problem, the full LP is replaced by $\\mathrm{DS}(I,J)$, which optimizes only $\\beta_j$ for $j\\in J$ while enforcing only the constraints indexed by $I$. After each solve, dual information gives reduced costs $|X_{*,j}^T\\alpha|>1$, which identify columns to add, and primal residuals $|X_{*,i}^T r|>\\lambda$, which identify violated constraints to add. The Lasso solution supplies the initial $I$ and $J$, and simplex warm starts carry basis information between subproblems. The same separation-and-pricing loop solves basis pursuit by column generation alone, and the fused Dantzig selector after a transformation that keeps the constraint matrix banded and makes each reduced-cost or constraint check cost $O(1)$.","core_discovery":"The central claim is that column generation and constraint generation, run jointly inside a simplex LP solver and warmed up by a Lasso solution, produce accurate solutions to $\\ell_1$-Dantzig selector problems at scales that commercial interior-point or first-order methods cannot reach: about $p\\approx 10^6$ variables with $n\\approx 10^3$ for the Dantzig selector, $p\\approx 10^5$ for basis pursuit, and $n=p\\approx 10^6$ for the fused Dantzig selector, all in minutes. The method relies on the optimal signal being sparse and on the active constraint set being small. The paper formulates a reduced LP over selected variable indices and selected constraint indices, checks dual reduced costs to add columns and primal violations to add constraints, and iterates until exact optimality conditions hold. It reports that the Lasso initialization is essential: random initialization, or column generation alone without constraint generation, loses most of the speed advantage.","pith_inferences":["The same pricing-and-separation loop should extend to other LP-based sparse estimators, such as group or ordered Dantzig variants, whenever a cheap surrogate provides a reasonable initial support; this is a direct extrapolation of the paper's mechanism, not a claim it tests.","The paper's own runtime table shows DantzigLP degrading sharply as $\\lambda$ shrinks and the solution densifies; read literally, the practical scope of the method is bounded by solution sparsity, not simply by $n$ and $p$.","Because the framework returns both primal and dual information at every iteration, a user could stop early with a certificate of suboptimality, trading exactness for large time savings on massive instances; the paper mentions the certificate but does not develop a stopping rule that uses it.","The reported wall-clock times depend on a warm-start-friendly simplex engine, so the advantage is not inherent to column generation alone and may not transfer to interior-point or first-order subsolvers."],"forward_implications":["The $\\ell_1$-Dantzig selector becomes solvable in minutes at $n\\approx 10^3$, $p\\approx 10^6$, with memory requirements far below methods that form $X^TX$.","Basis pursuit with $p\\approx 10^5$ is solvable in minutes, while full-LP and ADMM baselines either exceed memory limits or fail to converge at that scale.","The fused Dantzig selector in the signal-estimation case $X=I$ scales to $n=p\\approx 10^6$, and the regression case with general $X$ improves on solving the full LP.","Computing a whole path of solutions over a grid of $\\lambda$ values is efficient because each solved subproblem warm-starts the next.","The Lasso initialization, not column generation by itself, is the key to the speed: removing it or replacing it with random initialization degrades performance substantially."],"supporting_citations":[{"why":"Defines the Dantzig selector estimator whose optimization problem is the paper's main target.","marker":"[9]"},{"why":"Introduces the Lasso, whose solution the method uses to initialize the active column and constraint sets.","marker":"[28]"},{"why":"Supplies the fast coordinate-descent Lasso solver used for initialization in the experiments.","marker":"[17]"},{"why":"Origin of column generation for large-scale LPs, the algorithmic backbone of the framework.","marker":"[16]"},{"why":"Classical decomposition framework for large-scale LPs from which column generation descends.","marker":"[11]"},{"why":"Textbook treatment of column and constraint generation and LP duality used to frame optimality conditions.","marker":"[5]"},{"why":"Parametric simplex method baseline, a state-of-the-art specialized solver the paper compares against.","marker":"[26]"},{"why":"ADMM baseline for Dantzig selector; experiments show it converging slowly or failing at large scales.","marker":"[7]"},{"why":"Dynamic programming solver for the fused Lasso, used for initialization and proximal maps in the fused Dantzig selector case.","marker":"[21]"}],"fun_headline_variants":["Lasso warm start speeds Dantzig selector to scale","Column and constraint generation scales sparse recovery LP","Million-variable Dantzig selector solved in minutes","Warm-started column generation for large Dantzig selector"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole speedup rests on the assumption that the Dantzig selector solution is sparse and that the Lasso solution already identifies most of its nonzero entries and active constraints; when that fails, column and constraint generation must add many pieces and the method slows toward solving the full LP.","fun_headline_variants_meta":{"raw":{"variants":["Lasso warm start speeds Dantzig selector to scale","Column and constraint generation scales sparse recovery LP","Million-variable Dantzig selector solved in minutes","Warm-started column generation for large Dantzig selector"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000332,"raw_usage":{"total_tokens":1812,"prompt_tokens":876,"completion_tokens":936,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":492,"completion_tokens_details":{"reasoning_tokens":871}},"tokens_in":492,"tokens_out":936,"duration_ms":8923,"temperature":1.0,"reasoning_tokens":871,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:42:23.825763+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct an $\\ell_1$-DS instance with $n\\approx 10^3$, $p\\approx 10^6$ in which the true solution has about $p/2$ nonzero entries of comparable size, run DantzigLP with the Lasso warm start, and record total simplex iterations and runtime: if it still finishes in minutes the claim is stronger than the paper argues, while if it takes as long as or longer than solving the full LP, the paper's efficiency claim is limited to sparse solutions.","supporting_citations":[{"cited_title":"Candes and T","cited_arxiv_id":null,"evidence_quote":"Defines the Dantzig selector estimator whose optimization problem is the paper's main target."},{"cited_title":"Tibshirani","cited_arxiv_id":null,"evidence_quote":"Introduces the Lasso, whose solution the method uses to initialize the active column and constraint sets."},{"cited_title":"Friedman, T","cited_arxiv_id":null,"evidence_quote":"Supplies the fast coordinate-descent Lasso solver used for initialization in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Origin of column generation for large-scale LPs, the algorithmic backbone of the framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Classical decomposition framework for large-scale LPs from which column generation descends."},{"cited_title":"Bertsimas and J","cited_arxiv_id":null,"evidence_quote":"Textbook treatment of column and constraint generation and LP duality used to frame optimality conditions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Parametric simplex method baseline, a state-of-the-art specialized solver the paper compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"ADMM baseline for Dantzig selector; experiments show it converging slowly or failing at large scales."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Dynamic programming solver for the fused Lasso, used for initialization and proximal maps in the fused Dantzig selector case."}],"review_version":1}