{"id":"fe236432-8636-40cb-858d-514333fb2d09","arxiv_id":"2501.01801","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new lazy-update algorithm claims near-linear O(ε^{-1}nd log(n/d)) time for approximate John ellipsoids, but key proof steps and complexity accounting contain gaps.","lead":"Woodruff and Yasuda propose faster algorithms for computing approximate John ellipsoids, a classic geometric problem, by delaying high-precision leverage score updates and using fast matrix multiplication. The paper also gives low-space streaming variants, but the headline near-linear running time claim rests on proof steps that do not close as written.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(nd) time for leverage scores rests on a sketch width t independent of d; this is impossible for full-rank A, so Theorem 1.6's dominant term is unsupported.","rationale":"The reader's weakest_assumption identifies the same load-bearing premise: Theorem 1.3 assumes a d×t sketch with t = O(ε^{-2} log(n/δ)) independent of d can yield (1±ε)-approximate leverage scores for any n×d matrix. This is exactly where the paper's central O(nd) claim becomes insecure. My analysis confirms the concern and goes slightly deeper: the impossibility is not merely about DMMW12's theorem but about the geometry of leverage scores. For a full-rank n×d matrix, leverage scores are the diagonal of the projection onto a d-dimensional subspace after whitening; any rank-t representation (t < d) has trace at most t, whereas the true leverage scores sum to d, so a t-independent-of-d sketch cannot approximate all n leverage scores to relative error. The example A = [I_d; (1/√d) 1^T] makes this concrete: the last row's row norm is 1 but its leverage score is only 1/2, and no rank-t sketch with t << d can fix that factor without knowing the whitening transform, which itself requires d-dimensional information. Since the same O(nd) low-accuracy leverage score computation is used inside Algorithm 2 (Line 6) and in Section 1.2.2, the dominant term of Theorem 1.6 is unsupported. I did not identify a separate more-load-bearing concern; the other issues (Lemma 2.2's proof at s = k/2, the unaccounted initialization cost, the mismatch between the abstract and Theorem 1.6) are real but secondary. Therefore, the reader's REJECT verdict stands without modification.","tokens_in":13994,"tokens_out":32389,"duration_ms":294392,"concrete_test":"Construct A = [I_d; (1/√d) 1^T] for d = 1000 (so n = d+1). Compute exact leverage scores τ_i = a_i^T (A^T A)^{-1} a_i. Implement the claimed DMMW12-style estimation: let R be a d×t Gaussian matrix with t = ceil(10 log n) (independent of d), form B = A R, and estimate τ'_i from the row norms of B (or from a basis of the column space of B). Compute max_i |τ'_i/τ_i - 1|. If the error for the last row (true τ = 1/2, row norm estimate ≈ 1) exceeds ε = 0.1, the t-independent-d premise is refuted, and Theorem 1.3 and the O(nd) time in Theorem 1.6 are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central O(nd) running-time claim of Theorem 1.6 depends on the ability to approximate (even low-accuracy) leverage scores of dense n×d matrices in O(nd) time. In Section 1.2.1, this is justified by the assertion that 'The work of [DMMW12] shows that the leverage scores of A can be written as the row norms of AR for a d×t matrix with t = O(ε^{-2} log(n/δ))' independent of d. This assertion is not correct for general full-rank A. Leverage scores are τ_i = ||(A^T A)^{-1/2} a_i||^2, i.e., the squared norms of the rows of A after whitening by the covariance, equivalently the squared row norms of an orthonormal basis of the column space. Row norms of A R for a d×t matrix R with t < d give the squared norms of the rows after a rank-t projection; they cannot reproduce the d-dimensional whitening. Concretely, for A = [I_d; (1/√d) 1^T] (full column rank d), the last row has row norm squared 1 but leverage score 1/2; any rank-t sketch with t independent of d (and t << d) cannot capture this factor-of-2 gap. Since t must be at least d to represent the row space or whitening, the O(nd) time for leverage scores is unsupported. The same O(nd) low-accuracy leverage score computation is invoked in Section 1.2.2 and in Algorithm 2 (Line 6), so the dominant O(ε^{-1}nd log(n/d)) term in Theorem 1.6 is not justified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes faster algorithms for computing approximate John ellipsoids for a set of n points in d dimensions. The main contribution is a claimed O(ε^{-1}nd) log(n/d)-time algorithm, improving on the O(ε^{-1}nd^{ω-1}) log(n/d) iterative-leverage-score algorithm of CCLY19. The technical strategy is to (i) compute approximate leverage scores in O(nd) time via fast rectangular matrix multiplication, (ii) use a 'lazy update' scheme to avoid high-accuracy leverage score computations at every iteration, and (iii) periodically recompute the weights using fast rectangular matrix multiplication. A streaming variant is also stated. The central claims rest on Theorem 1.3 (linear-time leverage scores) and Theorem 1.6 (the final running-time bound), with correctness argued through a sequence of lemmas on products of χ² variables and leverage-score sampling.","tokens_in":14310,"tokens_out":20913,"duration_ms":193288,"significance":"If the main results were correct, they would represent a significant improvement for dense John ellipsoid computation: the O(ε^{-1}nd) log(n/d) running time would be nearly linear in the input size for n≫d, and the streaming result would be a useful low-space multi-pass algorithm. The paper is clearly written and the high-level idea (delaying high-accuracy leverage-score computations, then batching them via rectangular matrix multiplication) is attractive. However, the main theorem is not established in the submitted version: the leverage-score time claim rests on a misstatement of the DMMW12 result, the proof of a key concentration lemma is invalid, and the running-time statement omits important matrix-multiplication costs. These are load-bearing issues, not presentation details.","major_comments":[{"comment":"The claim that 'the leverage scores of A can be written as the row norms of AR for a d×t matrix with t=O(ε^{-2}log(n/δ))' is false. Leverage scores of A are the squared row norms of U = A(A^T A)^{-1/2}, not of A R; they are invariant under right-multiplication of A by any invertible matrix, whereas row norms of A R are not. For A=[I_d; (1/√d)1^T] and R=I, the last row has row norm 1 but leverage score 1/2. Approximating leverage scores by row norms of U R requires forming or implicitly multiplying by the whitening matrix (A^T A)^{-1/2}; the paper provides no O(nd)-time procedure for this step, and the cited DMMW12 result (which computes an orthonormal basis first) does not establish it. Consequently, Theorem 1.3's O(nd) leverage-score bound is unsupported, and the dominant O(ε^{-1}nd) log(n/d) term in Theorem 1.6 and the abstract is not justified.","section":"Section 1.2.1, Theorem 1.3"},{"comment":"The proof of Lemma 2.2 sets s=k/2 in the lower-tail bound of Lemma 2.1. For this value, C_{-s,k}=2^{-k/2} Γ(0)/Γ(k/2) is infinite, so the bound Pr{∏X_i ≤ 1/R} ≤ C_{-s,k}^T R^{-s} is vacuous. The high-probability event on products of χ² variables, which Lemma 2.4 and the proof of Theorem 1.6 condition on, is therefore not established. A different proof (e.g., tail bounds for sums of log-χ² variables) might salvage the lemma, but the submitted argument is invalid as written.","section":"Lemma 2.2"},{"comment":"The running time stated in Theorem 1.6 contains the term O(n^{0.1})d^{ω+1}ε^{-3}(log n)^2, but the abstract and Table 1 advertise only O(ε^{-1}nd) log(n/d). These are not equivalent in the stated regime n≫d≫poly(ε^{-1}log n): for d=n^{0.8}, the extra term is n^{0.1}·(n^{0.8})^{ω+1} ≈ n^{0.1+0.8×3.37} = n^{2.8}, whereas ε^{-1}nd ≈ n^{1.8}, so the omitted term dominates. Moreover, the algorithm does not account for the cost of forming Q(0)=A^T W(0)A in Algorithm 2, Line 2, or the final product A^T \\tildeWA in Algorithm 3, Line 11; each of these products costs O(nd^{ω-1}) with fast matrix multiplication and can dominate the claimed bound. The running-time statement is therefore incomplete.","section":"Theorem 1.6, Table 1"}],"minor_comments":[{"comment":"The definition of v_i^{(t)} in Lemma 2.4 uses a product up to t−1, while Algorithm 2, Line 7 sets v_i^{(t)} as a product up to t; these should be reconciled to avoid an off-by-one error in the correctness argument.","section":"Lemma 2.4, Algorithm 2"},{"comment":"Theorem 2.6 states the JL lemma for an m×d Gaussian matrix G, while Algorithm 3, Line 6 uses a d×m Gaussian; the transpose convention should be fixed for clarity.","section":"Theorem 2.6, Algorithm 3"},{"comment":"The proof of the streaming result is only a sketch; the claim that Sherman-Morrison updates lead to O(d^2T) update time per row should be made explicit, since the pseudocode in Algorithm 1 does not show the pseudoinverse update.","section":"Theorem 1.8"},{"comment":"There is a minor typo in Remark 1.7 ('can be be viewed'), and the paper contains a few other small typographical errors (e.g., inconsistent use of t vs. T in the proof of Lemma 2.2).","section":"Remark 1.7"}],"recommendation":"reject","confidential_remarks":"The main theorem's dominant term relies on a misreading of DMMW12: leverage scores are row norms of the orthonormal basis U, not of A R, and the paper does not show how to whiten A in O(nd) time. The stress-test concern about a rank-t sketch being unable to separate leverage scores from row norms is not the right formulation (a sketch of U does preserve that separation), but the manuscript's own derivation is nonetheless invalid. The missing initial/final matrix-product costs and the flawed χ²-product concentration proof are further load-bearing gaps. The paper's high-level approach is interesting and may be repairable, but substantial new algorithmic work is needed to justify even the stated running time."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know three things about this paper. The lazy-update scheduler is a real idea: it delays high-accuracy weight computations in the CCLY19 fixed-point iteration so they can be batched into one rectangular matrix multiplication. That is the right kind of thing to try. Second, the streaming algorithm (Theorem 1.8) looks plausible and, if correct, gives the first low-space multi-pass method with O(d^2T) words. Third, the main running-time claim in the dense case is not supported as written; there are two concrete proof bugs and one unsupported premise.\n\nThe construction is genuinely new. The authors see that you can run the leverage-score reweighting for O(log n) steps using only cheap low-accuracy estimates, then recompute all weights at once via A times a d×m Gaussian matrix, with fast rectangular matrix multiplication making that O(nd) rather than O(nd^{ω-1}). That is a meaningful improvement over CCLY19's per-iteration O(nd^{ω-1}). The streaming idea of storing the quadratic forms and using Sherman-Morrison updates is also natural and likely correct.\n\nNow the soft spots. Theorem 1.3, the O(nd)-time (1+ε)-leverage-score result, rests on the assertion that DMMW12 writes leverage scores as row norms of AR, where R is d×t with t independent of d. That is false for general full-rank A. Take A = [I_d; v^T] with v = (1/√d)1. The last row has norm 1 but leverage 1/2. No d×t sketch with t < d can recover that gap, so the row-norm argument cannot work. This is load-bearing for Theorem 1.3, and the same claim is used to justify the low-accuracy sampling in Section 1.2.2. Second, Lemma 2.2's proof sets s=k/2 in the lower-tail Chernoff bound; C_{-s,k} contains Γ(k/2-s), which is infinite at s=k/2. The bound is vacuous. You might fix this with s=k/4 and tuned constants, but the proof as printed is wrong. Third, Algorithm 2 initializes ~Q(0)=A^T W(0)A, and the cost of forming that is O(nd^{ω-1}) (or O(nd^2)) in the dense case, which is not in the stated bounds; the paper doesn't explain how to avoid that.\n\nNone of this kills the lazy-update skeleton. The low-accuracy leverage scores in Algorithm 2 might be obtainable by existing input-sparsity methods, and the Lemma 2.2 bug may be patchable. But as it stands, the central O(ε^{-1}nd) claim is not established, and the abstract and Table 1 overstate Theorem 1.6.\n\nVerdict: send to peer review. A serious referee can separate the salvageable streaming result and the batching technique from the broken leverage-score premise. I would not cite the O(nd) leverage-score claim yet, but the paper deserves referee time rather than a desk rejection.","headline":"The lazy-update scheduler is worth reading, but the O(nd) leverage-score claim rests on a false premise and the main proof has a bug.","tokens_in":14865,"tokens_out":11764,"would_cite":false,"duration_ms":104259,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68Q25","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The authors show that approximate John ellipsoids of n dense points in d dimensions can be computed in nearly O(ε^{-1}nd) time, removing the matrix-multiplication exponent from the dominant term of the best prior algorithm, and give a…","keywords":["John ellipsoid","leverage scores","lazy updates","fast rectangular matrix multiplication","streaming algorithms","randomized numerical linear algebra","D-optimal design","convex hull approximation"],"falsifier":"Take A = diag(1, 100, 1, ..., 1) in d dimensions with n−d zero rows appended, so the true leverage score of every nonzero row is 1. For any random d×t matrix R with t independent of d, the squared row norms of A R for the first two rows will be proportional to 1 and 10000 (after scaling), differing by a factor of $10^{4}$; observing this ratio for d ≥ 2 and t = O($ε^{{-2}}$ log n) would directly contradict the claimed representation of leverage scores as row norms of A R, which is the stated basis for Theorem 1.3.","tokens_in":13756,"feed_emoji":"⚡","tokens_out":13503,"duration_ms":126912,"temperature":0.7,"pith_summary":"The paper claims that the classic fixed-point iteration for computing an approximate John ellipsoid—repeatedly reweighting points by their leverage scores—can be simulated in nearly O($ε^{{-1}}$nd) time for dense inputs, improving on the previous best of O($ε^{{-1}}$$nd^{{ω-1}}$) log(n/d) with ω the matrix multiplication exponent. The key is to defer high-accuracy leverage score computations, using low-accuracy scores for all rows to sample a small set, and then to compute batches of high-accuracy weights at once via fast rectangular matrix multiplication. The paper also gives a multi-pass streaming algorithm with O($d^{2}$/ε) space using the same lazy-update idea. If correct, this removes the superlinear dependence on the matrix multiplication exponent from the dominant term and makes John ellipsoid computation nearly input-sparsity time for dense matrices.","feed_headline":"Lazy updates cut John ellipsoid time to near-linear","feed_subtitle":"Batching precise leverage scores removes the d^{ω-1} factor from the prior dense-matrix bound.","key_machinery":"The central object is the leverage score fixed-point iteration: $w^{{(t)}}$_i = τ_i(√$W^{{(t-1)}}$ A), where the John ellipsoid is given by the quadratic form A^T W A. The acceleration mechanism is 'lazy updates': the algorithm maintains only approximate quadratics Q̃(t), computes low-accuracy leverage scores for all rows in O(nd) time to drive a row sample, evaluates exact-weight products only on the sampled rows, and periodically batches the full weight update into a single product of A with a d×m Gaussian-sketch matrix, exploiting the fast rectangular matrix multiplication bound that an n×d by d×m product costs O(nd + n $m^{{1/α}}$) poly-log time for a constant α≥0.1.","core_discovery":"The authors establish that the iterative John ellipsoid algorithm of [CCLY19]—which alternates between computing leverage scores of the reweighted matrix and reweighting rows—can be accelerated by a 'lazy update' scheme. Instead of computing all n high-accuracy leverage scores in every one of the T=O($ε^{{-1}}$ log(n/d)) iterations, the algorithm computes only low-accuracy leverage scores for all rows in O(nd) time, samples a small subset of rows using those scores, evaluates high-accuracy weights on just the sampled rows, and accumulates approximate quadratics. After O(log n) rounds, it resets the weights by a single multiplication of A by a d×m Gaussian-sketched matrix, using fast rectangular matrix multiplication to do this in O(nd) poly-log time. The resulting Algorithm 3 returns an ellipsoid Q with 1/√(1+ε) Q ⊆ P ⊆ √d Q in time O($ε^{{-1}}$nd)(log(n/d)+poly log($ε^{{-1}}$log n)) + O(n) poly($ε^{{-1}}$log n) + O($n^{{0.1}}$) $d^{{ω+1}}$ $ε^{{-3}}$ (log n)^2, and the same machinery yields a streaming algorithm with O($d^{2}$T) space that passes over the data T times.","pith_inferences":["The technique of 'delaying large matrix multiplications to exploit economies of scale' could apply to other iterative algorithms that repeatedly compute leverage scores, such as ℓ_p Lewis weight algorithms, where the bottleneck is similar; the paper raises this as a future question but the transfer may be direct.","The practical speedup over prior work depends on the hidden constants in the fast rectangular matrix multiplication (currently α≥0.1) and the poly(ε^{-1}) factors; at moderate d and n, the O(nd^{ω-1}) baseline may still win on real hardware until ε is quite small.","A testable extension is to implement the streaming algorithm and verify the O(d^2T)-word space bound in the real-number model, while acknowledging the paper leaves the bit-complexity version open.","The near-linear per-iteration cost suggests John ellipsoid computation could become practical for massive online learning and D-optimal design instances where prior dense-matrix algorithms were infeasible."],"forward_implications":["If correct, the algorithm gives the first nearly O(ε^{-1} n d) algorithm for approximating John ellipsoids of dense matrices, removing the superlinear d^{ω-1} factor from prior bounds.","The lazy-update scheme is a general template: any iterative reweighting algorithm whose bottleneck is repeated full-matrix leverage-score computations could be accelerated by batching the precise computations and using fast rectangular matrix multiplication, as the paper notes for parallelization in Remark 1.7.","The streaming algorithm yields a multi-pass algorithm using O(d^2/ε) space, improving on prior streaming ellipsoid algorithms that either used more passes or allowed only O(√log n) approximation.","The approximate leverage score result (Theorem 1.3), if established, gives a near-linear time algorithm for (1+ε)-approximate leverage scores of dense matrices, a central primitive in randomized numerical linear algebra.","For n≫ d, the running time bound implies that even constant-factor volume-optimal ellipsoids (approximating the maximal volume up to (1+ε)) can be computed in O(ε^{-1} n d^2 log(n/d)) time."],"supporting_citations":[{"why":"Defines the iterated leverage-score fixed-point algorithm for John ellipsoids and provides the convergence guarantee (Theorem 2.5) that the new algorithm inherits.","marker":"[CCLY19]"},{"why":"Provides the sketching-based leverage score approximation that Theorem 1.3 claims to speed up, and whose premise the paper relies on for the O(nd) time.","marker":"[DMMW12]"},{"why":"Gives the fast rectangular matrix multiplication result (Theorem 1.4) used to multiply A by a d×m sketch matrix in nearly O(nd) time.","marker":"[Cop82, Wil11, Wil24]"},{"why":"The Johnson–Lindenstrauss lemma (Theorem 2.6) is used to approximate the row norms of the sketched matrix via Gaussian matrices in the resetting step.","marker":"[JL84]"},{"why":"Supplies the leverage score sampling theorem (Theorem 2.3) that ensures the sampled rows spectrally approximate the quadratic form.","marker":"[SS11]"},{"why":"Gives the low-accuracy leverage score computation used to drive the row sampling in each iteration.","marker":"[LMP13]"},{"why":"Provides the tail bounds for products of χ² variables (Lemma 2.1) that control the error accumulation over the lazy-update rounds.","marker":"[SSK17]"}],"fun_headline_variants":["Lazy sampling speeds up John ellipsoids","Near-linear John ellipsoids via lazy updates","John ellipsoids: lazy updates drop costly factor","Sampling trick makes John ellipsoids faster","Fast John ellipsoids with lazy leverage scores"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The near-linear running time depends on the premise that all leverage scores can be approximated to a (1±ε) factor as the squared row norms of A times a random d×t matrix with t = O($ε^{{-2}}$ log(n/δ)) independent of d.","fun_headline_variants_meta":{"raw":{"variants":["Lazy sampling speeds up John ellipsoids","Near-linear John ellipsoids via lazy updates","John ellipsoids: lazy updates drop costly factor","Sampling trick makes John ellipsoids faster","Fast John ellipsoids with lazy leverage scores"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000139,"raw_usage":{"total_tokens":1135,"prompt_tokens":899,"completion_tokens":236,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":164}},"tokens_in":515,"tokens_out":236,"duration_ms":2921,"temperature":1.0,"reasoning_tokens":164,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:23:40.380239+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take A = diag(1, 100, 1, ..., 1) in d dimensions with n−d zero rows appended, so the true leverage score of every nonzero row is 1. For any random d×t matrix R with t independent of d, the squared row norms of A R for the first two rows will be proportional to 1 and 10000 (after scaling), differing by a factor of $10^{4}$; observing this ratio for d ≥ 2 and t = O($ε^{{-2}}$ log n) would directly contradict the claimed representation of leverage scores as row norms of A R, which is the stated basis for Theorem 1.3.","supporting_citations":[],"review_version":1}