{"id":"daf5b885-d538-497a-a7ea-74e2a8180fed","arxiv_id":"2504.16270","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The thesis provides near-optimal streaming ellipsoidal rounding algorithms, block Lewis weight sparsification, dueling optimization with monotone adversaries, PAC analysis of backdoors, and spectral clustering robustness, all with detailed proofs.","lead":"This PhD thesis develops geometry-based algorithms and statistical models for optimization and data science problems, including streaming approximation of convex shapes, sparsification, robust regression, backdoor attacks, and graph clustering. It consolidates several published results under a high-dimensional geometry lens, with full proofs and new simplified analyses.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The fully online guarantee can be far worse than John's O(d); the near-optimality claim depends on a warm-start ball and on the restriction to monotone algorithms.","rationale":"The reader's weakest-assumption analysis already identifies the warm-start dependence, and I agree that this is the main load-bearing issue for the headline claim. The core proof of Theorem 1 appears internally sound: the two-phase argument, the volume-based evolution condition, and the monotone invariants fit together. The problem is scope rather than internal correctness. The abstract and introduction present the result as 'nearly matching John's theorem' without prominently stating that the clean O(d)-style guarantee requires a supplied initial ball and that the only lower bounds apply to monotone algorithms. These caveats are present in Chapter 2, but they materially weaken the central claim: without a good warm start, the guarantee can depend on prefix aspect ratios that are much larger than the final aspect ratio, and optimality is not established outside the monotone class. This does not justify rejection, because the warm-started algorithm is still a legitimate streaming algorithm and the lower-bound restriction is stated honestly. It does justify keeping the verdict at CONDITIONAL and asking the authors to scope the claims more carefully in the final version.","tokens_in":75350,"tokens_out":29826,"duration_ms":302995,"concrete_test":"Implement Algorithm 4 (or simulate its update equations) on the stream z1=(-1,0), z2=(1,0), z3=(0,10^-3), z4=(0,1) and record 1/alpha_4. If the final approximation factor is Theta(1/eps^2)-large (i.e., close to the max prefix aspect ratio) rather than O(d), the fully online algorithm does not nearly match John's d on this instance, confirming that the near-optimality claim must be scoped to the warm-start setting and to monotone algorithms. Conversely, if 1/alpha_4 is O(1), the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1's advertised O(min{R(Z)/r0, d log(R(Z)/r0)}) approximation is only valid when the algorithm is handed a ball c0+r0B inside the final polytope. If r0 is not close to the inradius, or if no warm start is available, the guarantee degrades. The warm-start-free Algorithm 4 (Theorem 3) replaces R(Z)/r0 with max_{t'<=t} R_t/r_{t'}, and the paper itself concedes this prefix ratio can be much larger than the final aspect ratio (Section 2.4.5, immediately after Theorem 3). Concretely, on the 2D stream z1=(-1,0), z2=(1,0), z3=(0,eps), z4=(0,1), the t=3 polytope is an O(eps)-thin triangle with aspect ratio ~1/eps^2, while the final triangle has aspect ratio O(1); the Theorem 3 bound is therefore controlled by the ephemeral t=3 ratio. Because the lower bound (Theorem 7) is proven only for monotone algorithms (Definition 4), the abstract's 'nearly worst-case optimal' and 'nearly agree with John's theorem' are stronger than what is established: the comparisons are to John's existential bound only in the warm-start regime, and to a restricted algorithmic class in the lower-bound regime.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript is a PhD thesis collecting results in optimization and data science. The first part develops streaming algorithms for approximating convex polytopes by ellipsoids and coresets, introduces block Lewis weights for sparsification and robust regression, and studies dueling optimization with a monotone adversary. The second part analyzes PAC learning under backdoor data poisoning and spectral clustering under a semirandom stochastic block model. The central, most fully developed contribution is Chapter 2, which gives a one-pass, O(d^2)-memory streaming ellipsoidal rounding algorithm for asymmetric polytopes, together with a monotone-update framework, a volume-based evolution-condition analysis, and lower bounds for the restricted class of monotone algorithms. The later chapters are presented as summaries of previously published works and were not fully assessable from the provided text.","tokens_in":75611,"tokens_out":5088,"duration_ms":53512,"significance":"If the claims in Chapter 2 hold as stated, the paper makes a genuine contribution: it provides the first efficient single-pass streaming ellipsoidal rounding for asymmetric polytopes with O(d^2) memory, and it does so through a self-contained and unusually explicit geometric analysis. The update rule is given in closed form, the monotonicity invariants are verified in detail, and the volume-evolution argument is transparent enough to be checked directly. The lower-bound constructions against monotone algorithms are also a useful step. However, the significance is substantially tempered by the gap between the advertised near-optimality with respect to John's theorem and what is actually proved: the O(min{R/r0, d log(R/r0)}) guarantee depends on a warm-start ball that the algorithm does not construct, the fully online version replaces the final aspect ratio with a worst-case prefix ratio, and the lower bounds apply only to a restricted algorithmic class. These caveats are disclosed in parts of the text, but the introduction and chapter summaries state the results in stronger terms.","major_comments":[{"comment":"The claim that these streaming algorithms 'nearly agree with John's theorem' is stronger than what is proved. John's theorem gives an O(d) bound independent of the geometry, while Theorem 1's guarantee is O(min{R(Z)/r0, d log(R(Z)/r0)}), where r0 is the radius of a user-supplied initial ball. If the supplied r0 is much smaller than the true inradius (e.g., r0 = r(Z)/T for large T), both terms in the min can be arbitrarily larger than d. Since Theorem 1 does not provide or estimate r0, the comparison to John's existential bound in the introduction is an overstatement; the correct statement is a guarantee relative to the quality of the warm start.","section":"Section 1.1, Section 1.2.1, Theorem 1 (Section 2.4)"},{"comment":"The warm-start-free Algorithm 4 does not recover the same guarantee. Theorem 3 replaces R(Z)/r0 with the prefix quantity max_{t' ≤ t} R_t / r_{t'}, and the paper itself concedes immediately after Theorem 3 that this prefix ratio can be much larger than the final aspect ratio. A concrete 2D example is the stream (-1,0), (1,0), (0,ε), (0,1): the t=3 polytope is an O(ε)-thin triangle with aspect ratio about 1/ε, while the final polytope has constant aspect ratio. Thus Theorem 3's bound is controlled by an ephemeral thin prefix and can be arbitrarily worse than John's O(d) bound for the final body. The fully online algorithm is therefore not 'nearly optimal' in the sense advertised.","section":"Section 2.4.5, Theorem 3"},{"comment":"The lower-bound claim supporting 'nearly worst-case optimal' is proved only for the restricted class of monotone algorithms defined in Definition 4, and Theorem 6 is further restricted to deterministic symmetric monotone algorithms. This leaves open the possibility that a non-monotone streaming algorithm achieves a substantially better approximation factor on the constructed instances. Consequently, the abstract and introduction's wording that the algorithms are 'nearly worst-case optimal' or 'nearly agree with John's theorem' is not supported by the established lower bounds; the upper and lower bounds together characterize only the monotone subclass.","section":"Section 2.7, Theorem 7; Definition 4"}],"minor_comments":[{"comment":"The phrase 'let r_t and R_t be the largest and smallest parameters, respectively' should be clarified: r_t is the largest inradius parameter and R_t is the smallest circumradius parameter.","section":"Theorem 3 statement"},{"comment":"Definition 4 lists invariant (2.2.1) as 𝒄_t+ℰ_t ⊇ conv((𝒄_{t-1}+ℰ_{t-1})∪{𝒛_t}), but the subsequent discussion states a weaker condition (2.2.1a). The logical relationship between the displayed invariants and the prose should be made explicit.","section":"Definition 4 and Section 2.2.1"},{"comment":"The formula defining M contains garbled notation involving '1D v'_dt, zE'; this should be rewritten in standard mathematical notation.","section":"Algorithm 4, Line 10"},{"comment":"The algorithm's output line says 'Output: Ellipsoid ℰ, center 𝒄, and scale α' but the pseudocode omits the final ellipsoid at Line 17; this inconsistency should be fixed.","section":"Section 2.4.5, Algorithm 4 header"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a thesis incorporating several previously published works. For a journal submission, the thesis format may obscure the genuinely new contribution; the streaming chapter (Chapter 2) is the core novel technical content that I could fully verify, and its claims need to be restated with the warm-start and monotone-algorithm caveats made prominent. The later chapters appear to be largely reproductions of published papers, so the editor may wish to clarify the expected contribution relative to those publications."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this is a PhD thesis that consolidates the author's own conference papers, not a new-results paper. Chapter 2 is the real meat: a careful, self-contained proof of the streaming asymmetric ellipsoidal rounding algorithm, including the monotone update rule, the evolution inequality, the volume argument, and a simplified analysis of the symmetric case. That material is worth having in one place. Chapters 3 and 4 likewise give detailed proofs for block Lewis weights and distributionally robust regression, including near-optimal sparsity rates and iteration complexities. The remaining chapters are readable restatements of prior work on dueling optimization, backdoor PAC attacks, and semirandom stochastic block models. Bibliographic notes are honest and every chapter points to the original papers.\n\nThe soft spots are exactly where the abstract oversells. The \"nearly worst-case optimal\" claim should be read with two caveats. First, Theorem 1's O(min{R/r0, d log(R/r0)}) guarantee needs a warm-start ball of radius r0 inside the final polytope; if r0 is a poor choice, the bound can be arbitrarily bad relative to John's existential d. Second, the warm-start-free guarantee in Theorem 3 depends on max_{t' <= t} R_t / r_{t'} over all prefixes, which can be much larger than the final aspect ratio. The stress-test example is correct: an early skinny triangle dominates the bound even when the final body is well-rounded. The lower bound (Theorem 7) applies only to monotone algorithms, so the abstract's \"nearly worst-case optimal\" is stronger than what is established. These are not fatal flaws in the proofs; they are claims that need to be stated honestly. The paper also includes experiments without code or data, so the numeric sections are illustrative rather than reproducible. I did not check every later proof line by line, but the chapters I read are technically coherent and I saw no circularity.\n\nWho is this for? Someone who wants the full streaming proof in one document. It is not a source of new theorems. I would cite the original conference papers rather than the thesis. If a journal editor sent this to referees with instructions to check the streaming chapter and ask for a scaled-back abstract, that would be reasonable; it is not desk-reject-quality work.","headline":"A competently written thesis that repackages the author's own conference papers; the streaming proof is solid, but the abstract overstates near-optimality once the warm-start and monotone-algorithm restrictions are factored in.","tokens_in":76165,"tokens_out":3390,"would_cite":false,"duration_ms":35729,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","52A27","68W27","52A20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The thesis's central claim is that a single-pass, low-memory algorithm can round an asymmetric convex polytope to distortion $O(\\min\\{R/r_0, d\\log(R/r_0)\\})$, nearly matching John's theorem.","keywords":["streaming algorithms","ellipsoidal approximation","convex polytopes","John's theorem","convex hull coresets","monotone algorithms","high-dimensional geometry"],"falsifier":"Run Algorithm 2 on the lower-bound adversary's stream from Section 2.7, namely the vertices of a regular simplex followed by points placed just outside the current ellipsoid, and measure the final $1/\\alpha_n$. The theorem predicts $O(\\min\\{R/r_0, d\\log(R/r_0)\\})$; a single stream where the measured distortion exceeds that bound by more than a constant factor would overturn the central claim.","tokens_in":75125,"feed_emoji":"📐","tokens_out":10174,"duration_ms":91380,"temperature":0.7,"pith_summary":"This thesis claims that high-dimensional geometry and probability can be turned into algorithmic and statistical tools across five problem areas, and its centerpiece is a streaming ellipsoidal-rounding theorem. The theorem states that there is a one-pass algorithm that, given a ball of radius $r_0$ inside an asymmetric convex polytope $Z$, maintains an enclosing ellipsoid at every timestep and ends with a rounding whose distortion is $O(\\min\\{R(Z)/r_0,\\, d\\log(R(Z)/r_0)\\})$, where $R(Z)$ is the circumradius; the algorithm stores $O(d^2)$ numbers and runs in $\\tilde O(n d^2)$ time. Since John's theorem guarantees that no ellipsoid can approximate a general convex body better than factor $d$, this nearly matches the offline optimum and is the first streaming guarantee of this kind for asymmetric polytopes. The same monotone-update machinery yields streaming convex-hull coresets, and the thesis also contributes new sparsification and regression algorithms based on block Lewis weights, a dueling-optimization algorithm with a monotone adversary, a statistical model of backdoor data-poisoning attacks, and stability guarantees for spectral clustering under helpful misspecification.","feed_headline":"Streaming algorithm rounds asymmetric polytopes near John's bound","feed_subtitle":"One pass and O(d^2) memory give near-optimal ellipsoidal approximation for any convex hull.","key_machinery":"The load-bearing object is a parameterized monotone update rule. After an affine reduction that maps the current outer ellipsoid to the unit ball and the new point to the first coordinate axis, the rule chooses the next ellipsoid from the family with horizontal semiaxis $a = e^\\gamma$, vertical semiaxis $b = 1 + (\\alpha-\\alpha')/2$, center $c = -\\alpha + \\alpha' a$, and scaling $1/\\alpha' = 1/\\alpha + 2\\gamma$, where $\\gamma$ is set so that the outer ellipsoid first covers the new point. The rule is monotone in the sense that the new outer ellipsoid contains the old outer ellipsoid and the new point, while the new inner ellipsoid is contained in the convex hull of the old inner ellipsoid and the new point. These two invariants alone imply that any such sequence is a valid rounding, and an evolution condition bounding the increase of $1/\\alpha$ by a constant times the log-volume increase of the outer ellipsoid telescopes into the final distortion bound. Irregular updates, which increase the dimension of the affine span by one, are handled separately and add at most one to the distortion each time.","core_discovery":"The central discovery, stated as Theorem 1, is that monotone update rules can solve streaming ellipsoidal rounding for asymmetric polytopes nearly as well as the best offline rounding. Algorithm 2 starts from the supplied inner ball $\\boldsymbol c_0 + r_0 B_2^d$, grows a ball around it until the aspect ratio is large enough, and then applies a one-parameter family of ellipsoidal updates; at every step the convex hull of the points seen so far lies in the current outer ellipsoid, and at the end the inner ellipsoid $\\boldsymbol c_n + \\alpha_n \\mathcal E_n$ lies inside $Z$ while $Z$ lies in $\\boldsymbol c_n + \\mathcal E_n$, with $1/\\alpha_n = O(\\min\\{R(Z)/r_0,\\, d\\log(R(Z)/r_0)\\})$. The algorithm stores $O(d^2)$ floating-point numbers and processes each point in $O(d^2 \\log d)$ time using rank-one SVD updates. A companion lower bound shows that within the natural class of monotone streaming algorithms this approximation factor is essentially best possible.","pith_inferences":["One consequence left implicit is that the same warm-start plus monotone-update recipe could be adapted to streaming membership or separation-oracle models, since the update rule only needs the previous ellipsoid and the newly revealed point or violated constraint.","A practical reading of the theorem is that the user-supplied inner ball, not the ambient dimension, controls the final distortion; investing a small offline preprocessing pass to find a large inner ball could make the streaming guarantee approach John's factor $d$ on real datasets.","The lower bound is proved only for monotone algorithms, so whether a non-monotone streaming algorithm can break the $d \\log(R/r_0)$ barrier for asymmetric polytopes remains open; the paper's symmetrization argument suggests the barrier is genuine, but it does not settle the unrestricted case.","The block Lewis weights developed in the later chapters are a separate geometric primitive; if their covering-number estimates transfer to overlapping group structures, the sparsification results could extend beyond the partition setting considered here."],"forward_implications":["If the central theorem is correct, streaming systems can maintain a near-John ellipsoidal summary of an asymmetric point stream using only $O(d^2)$ memory, which was previously achievable only for centrally symmetric polytopes.","The same framework immediately gives the first single-pass streaming coresets for the convex hull of asymmetric point sets, with $O(d \\log(R/r_0))$ selected points and the same order of distortion as the ellipsoidal rounding.","For origin-symmetric streams the approximation improves to $O(\\min\\{R/r_0, \\sqrt{d\\log(R/r_0)}\\})$, matching the symmetric lower bound up to log factors.","When the input points have integer coordinates in $[-N,N]$, the distortion becomes $O(d \\log(dN))$, independent of the stream length and aspect ratio.","No one-pass monotone algorithm can approximate the minimum-volume outer ellipsoid better than $\\sqrt{d}$ in the symmetric case, and no monotone algorithm beats $\\Omega(d \\log \\kappa / \\log d)$ in the asymmetric case, so the algorithm's dependence on the aspect ratio is not an artifact of the analysis."],"supporting_citations":[{"why":"Supplies John's theorem, the existential factor $d$ and $\\sqrt{d}$ distortion benchmarks that the streaming guarantees are measured against.","marker":"[Joh48]"},{"why":"Gives the symmetric-case streaming ellipsoidal rounding algorithm and monotone update rule that the asymmetric analysis extends and simplifies.","marker":"[MMO22]"},{"why":"Provides the earlier symmetric streaming and online coreset algorithms with online-condition-number bounds that this work compares against and generalizes to asymmetric polytopes.","marker":"[WY22a]"},{"why":"Establishes the efficient offline $O(d)$-approximation ellipsoidal rounding benchmark whose runtime of $\\tilde O(n d^2)$ the streaming algorithm matches.","marker":"[Nes08]"},{"why":"Supplies the rank-one SVD update subroutine that implements each streaming update in $O(d^2 \\log d)$ time.","marker":"[Sta08]"},{"why":"Provides the determinant identity used in the integer-coordinate proof to make the distortion independent of the aspect ratio.","marker":"[GK10]"}],"fun_headline_variants":["Streaming ellipsoid rounding nears John's bound for asymmetric polytopes","One-pass algorithm rounds convex hulls near John's ellipsoid bound","Near-optimal streaming rounding of asymmetric polytopes proven","Streaming rounding hits near-optimal for asymmetric polytopes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main algorithm's near-John guarantee is only as good as the user-supplied inner ball $\\boldsymbol c_0 + r_0 B_2^d$; if $r_0$ is far below the polytope's true inradius, the approximation factor can be arbitrarily worse than the existential factor $d$.","fun_headline_variants_meta":{"raw":{"variants":["Streaming ellipsoid rounding nears John's bound for asymmetric polytopes","One-pass algorithm rounds convex hulls near John's ellipsoid bound","Near-optimal streaming rounding of asymmetric polytopes proven","Streaming rounding hits near-optimal for asymmetric polytopes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001271,"raw_usage":{"total_tokens":5164,"prompt_tokens":874,"completion_tokens":4290,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":4214}},"tokens_in":490,"tokens_out":4290,"duration_ms":30165,"temperature":1.0,"reasoning_tokens":4214,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:07:39.713146+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on the lower-bound adversary's stream from Section 2.7, namely the vertices of a regular simplex followed by points placed just outside the current ellipsoid, and measure the final $1/\\alpha_n$. The theorem predicts $O(\\min\\{R/r_0, d\\log(R/r_0)\\})$; a single stream where the measured distortion exceeds that bound by more than a constant factor would overturn the central claim.","supporting_citations":[],"review_version":1}