{"id":"91c6c419-7dad-4114-8913-4b2a2c319831","arxiv_id":"2505.11093","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Partially-rotated designs make Lasso's prediction error independent of arbitrarily correlated off-support columns.","lead":"This paper shows that if a design matrix's off-support columns are randomly rotated relative to the support columns, Lasso's prediction error depends only on how well-conditioned the support columns are, not on arbitrary correlations among the rest. It introduces a new condition, restricted normalized orthogonality, to prove this for a new family of semirandom designs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1.11 is false as stated: the partial-rotation tail bound is applied to net points whose coefficient vectors depend on the random matrix, so the uniform RNO bound does not follow; Theorem 1.5's proof is unsound.","rationale":"The reader's verdict ACCEPTs the paper after checking the proof chain, but the proof of Lemma 1.11 contains a substantive logical gap: the net argument relies on pointwise partial-rotation tail bounds for directions determined by bases that are themselves functions of the random matrix. This is not a minor omission; the lemma is false as stated. A concrete counterexample uses an n x n Gaussian submatrix for F_S: the pointwise partial-rotation condition holds, yet the uniform RNO condition fails because the column space covers the whole sphere. Since Theorem 1.5 depends on Lemma 1.11, the main theorem is not rigorously established. The support-knowledge caveat identified by the reader is a limitation on applicability, but it is not a correctness issue; the Lemma 1.11 flaw is a correctness issue affecting the central proof. A corrected version might restrict RNO to q=O(n/log d) and supply a rigorous argument, or add assumptions on the smallest restricted singular value of F_S, but as written the result is not proven. The verdict should therefore be conditional on repairing this lemma.","tokens_in":27895,"tokens_out":50294,"duration_ms":471864,"concrete_test":"Simulation: n=1000, S=[n], F_S with i.i.d. N(0,1/n) entries, F_{S^c}=sqrt(n)e_1. Compute max over unit c of |<F_S c/||F_S c||, e_1>| — it equals 1, so (n,S,0.02)-RNO fails. Independently, for random fixed c,d the probability that |<F_S c/||F_S c||, e_1>| > 0.01 is about 0.75, which is at most e^{-nu n} with nu=1e-5 (e^{-0.01}=0.990), so the (0.01, 1e-5)-partial-rotation condition holds. With C=1e-6, the lemma's sample-complexity condition n >= C nu^{-1} q log d is satisfied. This falsifies Lemma 1.11 and indicates the need for a corrected proof or a restricted q regime.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 5, proof of Lemma 1.11: after fixing support sets S_alpha, S_beta, the proof takes orthonormal bases U_alpha, U_beta of the spans of the corresponding columns of F_S and F_{S^c}, and for net elements u_c,u_d writes the normalized inner product as <U_alpha u_c, U_beta u_d>. It then invokes the (alpha,nu)-partial-rotation tail bound for 'each u_c and u_d'. This step is invalid: the coefficient vectors c,d for which U_alpha u_c = F_S c / ||F_S c|| depend on the random realization of F through U_alpha, whereas Definition 1.2 bounds the probability only for fixed, deterministic c,d. The union bound over the net therefore does not prove that F satisfies RNO. The issue is not merely technical: for an n x n Gaussian F_S and a single fixed off-support column, F is partially rotated with a constant nu, but for q = n the normalized column space of F_S covers the unit sphere, so the RNO constant is 1 with probability 1. Thus Lemma 1.11 is false. Theorem 1.5 invokes Lemma 1.11 to obtain the RNO condition, so the proof of the main theorem does not go through as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a semirandom family of designs called partially-rotated designs, in which a subset of the design columns is randomized so as to decorrelate them from the remaining columns. The main claim is that, for such designs, the restricted eigenvalue (RE) constant with respect to subsets of the randomized support block is, up to a 0.9 factor, equal to the RE constant of the support submatrix alone, independently of the arbitrary off-support columns. From this the authors derive a Lasso prediction error bound O(k log d / (gamma n)) in which gamma is the RE constant of the support submatrix. The technical route is to introduce a deterministic condition called restricted normalized orthogonality (RNO), prove that RNO implies the desired RE lower bound (Proposition 1.10), and then prove that partially-rotated matrices satisfy RNO with high probability (Lemma 1.11). The paper also provides two constructions of partially-rotated designs, a semirandom Gaussian design and a rotated-adversary design, and discusses the relation of RNO to RIP and to the restricted orthogonality condition.","tokens_in":28073,"tokens_out":30970,"duration_ms":325595,"significance":"If the main theorem were valid, the result would be a clean and useful addition to the literature on semirandom designs: it would show that Lasso's fast rate can be made independent of arbitrarily ill-conditioned off-support columns once the support block is randomized. The RNO framework is conceptually appealing, the sparsification argument in Section 3 and the algebra in Proposition 1.10 are correct, and the paper is clearly written. However, the central probabilistic step, Lemma 1.11, is not proven and, in the regime used by the proof, is actually false. Since Theorem 1.5 and Corollary 1.6 rely directly on this lemma, the paper's main contribution is not established as written.","major_comments":[{"comment":"The net argument is invalid because the net elements depend on the random realization of F. After fixing support sets S_alpha and S_beta, the proof takes orthonormal bases U_alpha and U_beta of the spans of the corresponding columns of F_S and F_{S^c}, and then applies the (alpha,nu)-partial-rotation tail bound 'for each u_c and u_d'. But Definition 1.2 bounds probabilities only for fixed deterministic coefficient vectors c,d, whereas the vectors u_c,u_d are coordinates of the normalized random vectors in bases U_alpha,U_beta that themselves depend on F. A union bound over such random net points does not yield the uniform RNO condition. This is not a cosmetic issue: the statement being proved requires a bound over all q-sparse c,d, and the proof supplies no valid mechanism to pass from fixed-c,d tail bounds to a uniform bound.","section":"Section 5, proof of Lemma 1.11"},{"comment":"Lemma 1.11 is false as stated. For a numerical illustration of the failure mode, take S={1,...,q} with q=n/200, let F_S be an n x q matrix with iid N(0,1) entries, and let the off-support block be a single fixed unit vector f. For fixed c,d the vector F_S c / ||F_S c|| is uniformly distributed on the unit sphere and independent of f, so F is (0.01,nu)-partially rotated with nu=Omega(1). For the type of constant C that a net union bound yields (say C=100), the premise n >= C nu^{-1} q max(log d, log(1/0.01)) can be satisfied by taking d of size about e^{100/C} and q = n/(2 C log(1/0.01)); explicitly q/n is about 1/920, so the premise holds. Yet with probability 1-o(1) the maximum inner product of f with the span of F_S is at least (1-o(1)) sqrt(q/n) > 0.02, so there exists c with |<F_S c/||F_S c||, f>| > 0.02. Thus the (q,S,0.02)-RNO conclusion of Lemma 1.11 fails. Since the proof of Theorem 1.5 in Section 6 invokes Lemma 1.11 to obtain the RNO condition, the proof of the main theorem does not go through.","section":"Lemma 1.11 and Theorem 1.5"}],"minor_comments":[{"comment":"The abstract's example says a random rotation is applied to the columns indexed by supp(beta), while Lemma 1.3 and Model 1.8 rotate the complementary columns; the abstract wording appears inconsistent with the formal definitions.","section":"Abstract and Section 1.1"},{"comment":"The proof introduces orthonormal bases U_alpha,U_beta without explicitly noting that they are random and depend on F; clarifying this dependence would make the invalidity of the subsequent partial-rotation step more visible.","section":"Section 5, proof of Lemma 1.11"},{"comment":"The Lasso step is described as a 'straightforward adjustment' of Theorem 7.20b in [Wai19]; if the main theorem is repaired, this derivation should be written out in full, since the definition of the RE constant used here is weaker than the one in some standard references.","section":"Appendix B, proof of Corollary 1.6"}],"recommendation":"reject","confidential_remarks":"The reader's acceptance appears to overlook the dependence of the net points in Lemma 1.11 on the random matrix. The counterexample described in the major comments is simple and directly targets the step where the partial-rotation tail bound is applied to random coefficient vectors. Even if Theorem 1.5 might be salvageable by a different argument, the present manuscript does not provide such an argument, and the central proof chain is broken."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the deterministic half is sound and worth reading: RNO is a nice condition, and the sparsification argument (Prop 1.10) showing that RNO implies an RE constant independent of the off-support columns checks out. Second, the probabilistic half—the proof that partially-rotated matrices satisfy RNO (Lemma 1.11)—has a serious gap. The proof picks orthonormal bases U_c, U_d of the random column spans and then applies the partial-rotation tail bound to net points u_i, u_j. But partial rotation is a pointwise bound for fixed coefficient vectors c, d. The vector U_c u_i has coefficients that depend on the random realization through the basis, so the event the tail bound controls is not the event the net argument needs. The union bound over the net doesn't cover this. In fact, the pointwise bound alone cannot imply a uniform bound over the continuum: for a Gaussian n×q support matrix and a fixed off-support column, the maximum inner product over q-sparse c is the largest principal cosine between the random subspace and that column, roughly sqrt(q/n), which can be far above 0.02 even when the pointwise tail holds with constant nu. So Theorem 1.5 is not proved by the argument given. The stress-test note lands on the right spot.\n\nCredit where it's due: the idea of partially-rotated designs is new and natural; RNO is a clean way to isolate the off-support columns; Lemmas 1.3 and 1.4 give genuine examples of partial rotation; and the deterministic reduction from RNO to RE is properly proved. The paper also honestly flags that the design requires knowing the support, and the appendix counterexample for the alternative RE definition is a good sanity check.\n\nCaveats in proportion: aside from the proof gap, the contribution is narrow—same fast rate as standard Lasso, new design family. The support-known-at-design-time assumption is an explicit semirandom modeling choice, not a hidden flaw, but it determines who will use this.\n\nBottom line: the paper deserves a serious referee because the conceptual contribution is real and the gap may be repairable, but I would not accept it in current form. If you referee it, ask the authors to fix Lemma 1.11—for instance by strengthening the partial-rotation definition to a uniform bound, or by proving RNO directly via subspace concentration for the Gaussian/rotation models. As written, the main theorem is unproven.","headline":"A promising new design family and a clean deterministic reduction, but the main probabilistic lemma has a real gap and the central theorem is unproven as written.","tokens_in":28672,"tokens_out":12010,"would_cite":false,"duration_ms":118793,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62J07","60B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that for partially-rotated designs, Lasso's prediction error depends only on the support submatrix's restricted eigenvalue, not on arbitrary correlations among the other columns.","keywords":["Lasso","restricted eigenvalue","partially-rotated designs","semirandom designs","restricted normalized orthogonality","sparse linear regression","high-dimensional statistics","prediction error"],"falsifier":"Take a fixed well-conditioned support submatrix $F_S$, attach any fixed off-support columns, and apply one random orthogonal rotation to the support columns. For $n \\ge C k \\log d/\\gamma_S(F_S)$, compute $\\gamma_S(F)/\\gamma_S(F_S)$ over many independent rotations; the theorem predicts the ratio is at least $0.9$ except with probability $e^{-\\Omega(n)}$. A single fixed off-support block for which this ratio falls below $0.9$ with non-negligible frequency would refute the main theorem.","tokens_in":27605,"feed_emoji":"🎲","tokens_out":10147,"duration_ms":97500,"temperature":0.7,"pith_summary":"The paper introduces partially-rotated designs, a semirandom family of design matrices for sparse linear regression, and proves that once a subset of columns is randomly rotated, the restricted eigenvalue (RE) constant with respect to any smaller set is, up to a factor of $0.9$, exactly the RE constant of that submatrix alone. The main payoff is a Lasso prediction error bound of $O(k \\log d/(\\gamma_S(F_S) n))$ with high probability, independent of arbitrary correlations among the columns outside the support. This matters because strongly correlated irrelevant features are a classic obstruction to fast Lasso rates; the paper shows that one random rotation of the support columns removes the obstruction. The proof is carried by a new deterministic property, restricted normalized orthogonality, which may be useful beyond this construction.","feed_headline":"Randomly rotating the support columns fixes Lasso's prediction error","feed_subtitle":"Prediction error no longer depends on arbitrarily correlated off-support columns, matching the fully well-conditioned rate.","key_machinery":"The load-bearing object is restricted normalized orthogonality (RNO): a matrix satisfies $(m,S,\\rho)$-RNO if every $m$-sparse linear combination of columns in $S$ has normalized inner product at most $\\rho$ with every $m$-sparse linear combination of columns outside $S$. The proof has two links. First, partial rotation plus a covering argument shows that the matrix satisfies RNO with high probability for $m$ proportional to $|S'|/\\gamma_{S'}(F_S)$. Second, a deterministic reduction shows that RNO implies the desired RE lower bound: a convex-geometric subsampling lemma approximates arbitrary off-support coefficient vectors by sparse ones, so the sparse RNO bound can be applied after a small approximation error. Choosing $m$ large enough absorbs the error and yields the $0.9$ factor.","core_discovery":"In the sparse linear model $y = F\\beta + w$ with $k$-sparse $\\beta$, assume $F$ is $(0.01,\\nu)$-partially rotated with respect to a set $S$ containing $\\operatorname{supp}(\\beta)$: every normalized linear combination of $S$-columns has inner product at most $0.01$ with every normalized linear combination of the remaining columns, except with probability $e^{-\\Omega(\\nu n)}$. Theorem 1.5 states that, with probability $1 - e^{-\\Omega(n)}$, for every $S' \\subseteq S$ with $n \\geq C |S'| \\log d/\\gamma_{S'}(F_S)$, the full-design RE constant satisfies $\\gamma_{S'}(F) \\geq 0.9\\,\\gamma_{S'}(F_S)$. Since the reverse inequality is immediate, the RE constant is preserved up to the constant $0.9$ once the sample size condition holds. Corollary 1.6 converts this into a Lasso prediction error bound $O(k\\log d/(\\gamma_S(F_S) n))$, matching the rate the design would have if all off-support columns were perfectly well-conditioned.","pith_inferences":["Going beyond the paper: the RNO-to-RE reduction is deterministic, so any design that can be certified to satisfy RNO with the right parameters—not only rotated ones—should inherit the same support-only prediction guarantee; certifying RNO for structured designs is a natural next step.","Going beyond the paper: because the construction needs $S$ at design time, a two-stage protocol is conceivable: use a pilot sample to guess a superset of the support, then randomize those columns; whether pilot errors propagate is a testable extension the paper does not address.","Going beyond the paper: the alternative-RE counterexample in the appendix suggests the gap between prediction-oriented recovery and global $\\ell^2$ recovery is real, so one might probe empirically whether parameter $\\ell^2$ error degrades in partially-rotated designs even when prediction error stays at the fast rate."],"forward_implications":["Under the sample condition $n \\ge C k \\log d/\\gamma_S(F_S)$, Lasso's prediction error is $O(k\\log d/(\\gamma_S(F_S) n))$ with high probability, regardless of how the off-support columns are correlated.","If the support submatrix itself is well-conditioned, with smallest eigenvalue $\\lambda_{\\min}$ of $\\frac{1}{n}F_S^\\top F_S$, the error becomes $O(k\\log d/(\\lambda_{\\min} n))$, the same rate as a fully Gaussian design.","The RE statement is uniform over all subsets $S' \\subseteq S$ satisfying the sample condition, so the guarantee applies simultaneously to every sparse support contained in $S$.","The $\\ell^1$ and support-coordinate recovery bounds for Lasso carry over with $\\gamma_S(F_S)$ in place of the full-design RE constant; the stronger global $\\ell^2$ recovery bound is not obtained in this framework."],"supporting_citations":[{"why":"Supplies the fast-rate Lasso guarantee that Corollary 1.6 plugs into, along with the covering bound used in the RNO proof.","marker":"[Wai19]"},{"why":"Provides the weak restricted-eigenvalue definition and the oracle-type Lasso guarantees that the paper adopts.","marker":"[vdGB09]"},{"why":"Defines the Lasso estimator whose prediction error is the object of Corollary 1.6.","marker":"[Tib96]"},{"why":"Supplies the convex-geometric subsampling lemma used to derive the sparsification result at the heart of Proposition 1.10.","marker":"[Ver18]"},{"why":"Introduces the restricted orthogonality condition that RNO is compared with and the RIP notion shown to imply RNO in Appendix C.","marker":"[CT05]"}],"fun_headline_variants":["Rotating support columns sharpens Lasso's error bound","Partially-rotated designs fix Lasso under arbitrary correlations","Random rotation of support columns restores Lasso's rate","Lasso prediction error decoupled from off-support correlations","Semirandom designs give Lasso a well-conditioned rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction requires the set $S$ to be known when the design is randomized, and the secret's support must lie inside $S$; if the support is unknown at design time, the partial-rotation premise is not met and the conclusion is not claimed.","fun_headline_variants_meta":{"raw":{"variants":["Rotating support columns sharpens Lasso's error bound","Partially-rotated designs fix Lasso under arbitrary correlations","Random rotation of support columns restores Lasso's rate","Lasso prediction error decoupled from off-support correlations","Semirandom designs give Lasso a well-conditioned rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000211,"raw_usage":{"total_tokens":1546,"prompt_tokens":1206,"completion_tokens":340,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":822,"completion_tokens_details":{"reasoning_tokens":258}},"tokens_in":822,"tokens_out":340,"duration_ms":3638,"temperature":1.0,"reasoning_tokens":258,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:59:07.029429+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a fixed well-conditioned support submatrix $F_S$, attach any fixed off-support columns, and apply one random orthogonal rotation to the support columns. For $n \\ge C k \\log d/\\gamma_S(F_S)$, compute $\\gamma_S(F)/\\gamma_S(F_S)$ over many independent rotations; the theorem predicts the ratio is at least $0.9$ except with probability $e^{-\\Omega(n)}$. A single fixed off-support block for which this ratio falls below $0.9$ with non-negligible frequency would refute the main theorem.","supporting_citations":[],"review_version":1}