{"id":"236992f7-c162-43ab-af1c-15a72320bad5","arxiv_id":"1908.04091","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"The authors give worst-case logistic regression datasets on which every deterministic first-order method needs Ω(1/√ε) oracle queries for an ε-approximate solution.","lead":"This paper constructs specific data sets for binary logistic regression on which any deterministic first-order optimization method needs at least about 1/sqrt(epsilon) steps to reach epsilon accuracy. It shows that logistic regression can be as hard as general smooth convex optimization in the worst case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3 is proved only for methods starting from x0=0; the WLOG claim in Section 1 is false for logistic loss, so the 'any deterministic first-order method' statement is unsupported.","rationale":"The reader identified Lemma 3.1 as the weakest assumption, but that lemma is actually true: given nested subspaces X⊊X̄, the orthogonal complement X̄∩X^⊥ is nonzero, and the orthogonal group acts transitively on spheres in X^⊥, so one can map any vector's X^⊥-component into X̄. The genuinely load-bearing gap is the asserted WLOG x0=0 in Section 1. The logistic regression model class is not closed under translations of the variable, so the standard reduction used in convex optimization lower bounds does not apply. Proposition 3.2's induction depends on the initial iterate being in the one-dimensional subspace K_1 (an invariant subspace for the initial gradient), and no argument is given for why an arbitrary deterministic method's start can be assumed to lie there. This affects the scope of Theorem 3.3: the proof only establishes the lower bound for methods whose initial iterate is 0 (or in span of A^T b). The paper's Section 2 construction and the lower bound under the linear-span assumption remain sound, and the constants are not fitted, so the result is likely salvageable by either proving the arbitrary-start case or clearly restricting the theorem's statement. For this reason the verdict category stays CONDITIONAL, matching the reader, but the condition that must be met differs: the authors must address the x0=0 assumption, not merely the sign typo.","tokens_in":13017,"tokens_out":28888,"duration_ms":282806,"concrete_test":"Check whether the WLOG reduction in Section 1 holds by substituting x' = x - x0 into (1.3) and requiring the result to be of logistic form (1.3) for the constructed A_k: this forces A_k x0 = α 1 for some α. Compute A_k e_1 from (2.2); it is (−2σ,0,…,0; 2ζ,0,…,0; 2σ,0,…,0; −2ζ,0,…,0)^T, which is not a multiple of the all-ones vector. Hence the shifted loss is not in the model class, so the proof's assumption x0=0 is not WLOG. Additionally, run Proposition 3.2 with M having x0=e_1 and k=6; the base case requires e_1∈span{e_6}, which is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central lower bound (Theorem 3.3) is established by induction in Proposition 3.2, whose base case requires the method's initial iterate to lie in K_{1,k} = span{e_{k,k}} (the proof says 't=0 is trivial by setting U0=I'). Section 1 asserts 'Without loss of generality, we can assume that x0 = 0' immediately after defining deterministic first-order methods. That WLOG is not valid for the logistic class: the standard translation argument would replace f(x)=l_{A,b}(x) by f(x+x0)=l_{A,b}(x+x0). Writing this shifted loss as h(Ax+Ax0) - b^T Ax + const, it is of the logistic form (1.3) only if Ax0 is a constant vector. For the constructed A_k in (2.2), A_k x0 is not constant for a generic x0 (e.g., x0=e_1), so the shifted function leaves the model class. Consequently, a method with initial iterate x0 outside K_1 cannot be handled by the proof: its first gradient at x0 is not confined to K_{2,k}, and the subspace invariant fails. The reader's weakest assumption, Lemma 3.1, is actually correct (an orthogonal map fixing X and sending x̄ into X̄ exists because X̄∩X^⊥ is nonzero), so the true load-bearing gap is the unjustified x0=0 normalization.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper constructs explicit worst-case data matrices for binary logistic regression and proves that deterministic first-order methods require Ω(1/√ε) oracle calls to reach ε accuracy. Section 2 builds datasets A_k,b_k from a bidiagonal matrix W_k, establishes a subspace-invariance lemma (Lemma 2.2), verifies the exact minimizer and minimum value (Lemma 2.1), and derives a lower bound under the linear-span assumption (Theorem 2.5). Section 3 removes the linear-span assumption by applying a rotation lemma from Ouyang and Xu (Lemma 3.1), yielding the main claim (Theorem 3.3): for any deterministic first-order method and any T, there is a logistic dataset with n=4T+2, N=16T+8 on which the T-th iterate has objective gap at least 3‖A‖²‖x0−z*‖²/(32(4T+3)(8T+5)) and distance satisfying ‖x_T−z*‖²>‖x0−z*‖²/8.","tokens_in":13276,"tokens_out":15624,"duration_ms":157906,"significance":"If the main claim is established, this is a useful contribution: it provides the first worst-case instances inside the binary logistic regression class that match the O(1/√ε) lower bound for general smooth convex optimization, showing that the logistic structure alone does not yield better deterministic first-order complexity. The construction is explicit, the subspace-invariance machinery in Lemma 2.2 is clean, and the lower-bound arithmetic in Theorem 2.5 checks out. The paper also gives reproducible constants (σ/ζ=1.3, C>1/2) and a transparent use of the Ouyang–Xu rotation lemma. However, the proof of the extension to arbitrary deterministic methods has a load-bearing gap concerning the initial point x0, and the main theorem is printed with the objective-gap inequality in the wrong direction.","major_comments":[{"comment":"The normalization \"Without loss of generality, we can assume that x0 = 0\" is not a valid WLOG reduction for the logistic model class (1.3). For f(x)=h(Ax)-b^T Ax, the shifted function f(x0+z)=h(Az+Ax0)-b^T Az-b^T Ax0 can be written as h(A'z)-b'^T A'z only if Ax0 is a constant vector (up to the intercept formulation), which is false for the constructed matrices A_k in (2.2) and generic x0. This assumption is load-bearing: Lemma 2.3 uses ∇f_k(0)=-A_k^T b_k to place x1 in K_{1,k}; Proposition 3.2 takes its base case t=0 as trivial with U0=I, which requires x0∈K_{1,k}=span{e_k}; and the final distance computation in Theorem 3.3 uses \"recalling that M starts at x0=0\". Since an orthogonal matrix fixing e_k cannot send an arbitrary x0 into span{e_k}, the induction cannot start for general initial iterates. The result appears repairable by choosing U0 to rotate x0 into K_{1,k} and weakening property 1 of Proposition 3.2 to invariance of U_t^T A^T b under t, in which case the distance ratio still holds; but as printed the \"any deterministic first-order method\" claim is unsupported.","section":"Section 1 (after Eq. (1.4)); Proposition 3.2; Theorem 3.3 proof"},{"comment":"The objective-gap inequality is printed in the wrong direction. The theorem states l_{A,b}(x_T)-l*_{A,b} ≤ 3‖A‖²‖x0-z*‖²/(32(4T+3)(8T+5)), whereas every lower-complexity claim in the paper requires ≥, and the proof derives ≥ (see the chain following (3.10)). If the printed inequality were correct, the result would be an upper bound and would not imply the O(1/√ε) lower bound claimed in the abstract. This must be corrected.","section":"Theorem 3.3"}],"minor_comments":[{"comment":"The phrase \"at least O(1/√ε)\" for a lower complexity bound is formally confusing; the intended statement is Ω(1/√ε).","section":"Abstract and Section 1.1"},{"comment":"In the distance estimate, \"max_{x∈K_{2T+1}} ‖x-x*‖\" should be \"min\" (or the lower bound should be derived directly from x_T∈U^T K_{2T+1}); as written, the displayed inequality is not a valid consequence.","section":"Theorem 3.3 proof"},{"comment":"In the second part of the proof, the notation \"x^T=(0^T_{k-1},u^T)^T\" appears to be a typo for \"x^T=(0^T_{k-t},u^T)^T\".","section":"Lemma 2.2 proof"},{"comment":"The word \"server\" should be \"serve\" in the first sentence.","section":"Concluding remarks"},{"comment":"The two displayed inequalities should be joined by \"and\" so that the statement is read as a conjunction; currently the second line appears as a sentence fragment.","section":"Theorem 3.3 statement"}],"recommendation":"major_revision","confidential_remarks":"The central construction is sound, and I believe the x0 issue is repairable along the lines indicated in the major comment. However, the printed proof of Theorem 3.3 and Proposition 3.2 does not support the stated generality, and the reversed inequality in Theorem 3.3 is a serious statement-level error. If the authors can supply the repaired induction and correct the inequality direction, the paper would be a valid, if modest, contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the paper really does construct logistic-regression datasets that force Omega(1/sqrt(epsilon)) iterations for deterministic first-order methods, but only for methods that start at the origin. The claim that x0=0 is without loss of generality is false for this model class, so Theorem 3.3 as stated is not proved.\n\nWhat is new and good: the dataset construction in (2.2) is explicit and simple. Lemma 2.2 shows that gradients stay in nested coordinate subspaces, giving a clean lower bound under the linear-span assumption with concrete constants. Section 3 removes that assumption using the standard Nemirovski rotation trick via Lemma 3.1 from Ouyang and Xu; the induction is valid for x0=0. The arithmetic in Theorems 2.5 and 3.3 checks out, and the constants are not fitted post hoc.\n\nThe soft spot is the normalization. Shifting a problem by x0 turns l_{A,b}(x) into h(Az+Ax0) - b^T A(z+x0). That is not generally of the same logistic form h(A'z) - b'^T A'z: it would require Ax0 to be a constant vector, which does not hold for the constructed A_k. The induction base in Proposition 3.2 needs x0 in K_{1,k}; the paper obtains it only by setting x0=0. So the proof covers methods with zero initial iterate, not arbitrary x0. This is a load-bearing gap, not a cosmetic one. There is also a smaller sign error: the printed Theorem 3.3 writes <= where the proof and abstract need >=; that is plainly a typo.\n\nMy sense is the underlying construction is sound and the gap is locatable. A revised version might extend to arbitrary x0 by using the intercept form (1.1) rather than the homogeneous form, or by letting the data matrix depend on x0. But as submitted, the headline theorem overstates what is proved.\n\nThis paper is for optimization theorists interested in lower bounds for logistic regression or smooth convex problems. It should go to a serious referee, but the referee should send it back for major revision to fix the starting-point issue and the typo. I would not cite the arXiv version in its current form.","headline":"A solid worst-case construction for zero-initialized first-order methods, but the 'any deterministic method' claim rests on an invalid x0=0 WLOG.","tokens_in":13815,"tokens_out":5815,"would_cite":false,"duration_ms":59494,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every deterministic first-order method and every iteration count T, there exists a binary logistic regression dataset on which the method's error after T steps is still at least order 1/T², so ε-accuracy requires Ω(1/√ε) oracle queries.","keywords":["binary logistic regression","first-order methods","lower complexity bound","worst-case dataset","smooth convex optimization","deterministic oracle","orthogonal invariance"],"falsifier":"Exhibit a deterministic first-order method and an iteration count $T$ for which, on every dataset of size $n=4T+2$, $N=16T+8$ (in particular every orthogonal rotation of the constructed $(A_k,b_k)$), the function-value gap after $T$ queries is smaller than the corresponding claimed lower bound; this would contradict Theorem 3.3. A narrower check is to verify Lemma 3.1 numerically on the nested subspaces used in Proposition 3.2: if an orthogonal $V$ fixing $K_{2s,k}$ and moving a random point into $K_{2s+1,k}$ fails to exist for some $s$, the induction that removes the linear-span assumption breaks.","tokens_in":12776,"feed_emoji":"📉","tokens_out":16685,"duration_ms":156610,"temperature":0.7,"pith_summary":"This paper tries to establish that binary logistic regression, despite its special structure, offers no worst-case advantage over general smooth convex optimization for deterministic first-order methods. For any such method and any prescribed iteration budget $T$, the authors construct a dataset with $n=4T+2$ features and $N=16T+8$ samples such that after $T$ oracle queries the function-value gap is at least $\\frac{3\\|A\\|^2\\|x_0-z^\\ast\\|^2}{32(4T+3)(8T+5)}$ and the iterate stays farther than $(1/\\sqrt{8})\\|x_0-z^\\ast\\|$ from the optimum. The gap decays like $1/T^2$, so reaching $\\varepsilon$-accuracy forces $T=\\Omega(1/\\sqrt{\\varepsilon})$ first-order oracle inquiries, matching the existing upper bound for all smooth convex problems. The hard instances are genuine logistic losses with zero optimal intercept, rather than quadratics or smoothed piecewise-linear functions, and the lower bound holds without assuming the iterates lie in the span of past gradients. If the result stands, accelerated first-order methods that are optimal for smooth convex optimization are also worst-case optimal for logistic regression.","feed_headline":"First-order methods need Ω(1/√ε) queries on some logistic data","feed_subtitle":"For any deterministic solver, adversarial binary logistic datasets keep the gap at 1/T² after T steps","key_machinery":"The hard instances are built from the $k\\times k$ bidiagonal matrix $W_k$ with $-1$ on the diagonal and $1$ on the superdiagonal; the data matrix is $A_k=(2\\sigma W_k;\\,-2\\zeta W_k;\\,-2\\sigma W_k;\\,2\\zeta W_k)\\in\\mathbb{R}^{4k\\times k}$ and the response is $b_k=(1_k,1_k,-1_k,-1_k)$, with $\\sigma>\\zeta>0$ (the paper takes $\\sigma=1.3\\zeta$ for explicit constants). The unique minimizer is $x^\\ast=c(1,2,\\dots,k)$, where $c>0$ solves $\\sigma\\tanh(\\sigma c)+\\zeta\\tanh(\\zeta c)=\\sigma-\\zeta$, and the optimal intercept is zero. The argument's engine is the nested subspace family $K_{t,k}=\\mathrm{span}\\{e_{k-t+1,k},\\dots,e_{k,k}\\}$: gradients of the loss at points in $K_{t,k}$ lie in $K_{t+1,k}$, so any method whose iterates stay in the span of past gradients never sees the first $k-t$ coordinates of the optimum, leaving a large function-value gap. A numerical comparison (Lemma 2.4) turns this into the explicit $1/T^2$ constants. For general methods, an orthogonal-invariance argument using the nested-subspace rotation lemma from Ouyang and Xu (2019) rotates the data so that the iterates of any deterministic first-order method are confined to rotated subspaces $U^\\top K_{2i+1,k}$ while retaining the same loss values and gradients, which removes the linear-span assumption.","core_discovery":"The paper's central result is that for every deterministic first-order method $\\mathcal{M}$ and every iteration count $T$, there exist a data matrix $A\\in\\mathbb{R}^{(16T+8)\\times(4T+2)}$ and a response vector $b\\in\\{-1,1\\}^{16T+8}$ such that the binary logistic loss $l_{A,b}(x)=h(Ax)-b^\\top Ax$, with $h(u)=\\sum_i 2\\log(1+e^{-u_i})$, has a unique minimizer $z^\\ast$ satisfying $l_{A,b}(x_T)-l_{A,b}^\\ast \\ge \\frac{3\\|A\\|^2\\|x_0-z^\\ast\\|^2}{32(4T+3)(8T+5)}$ and $\\|x_T-z^\\ast\\|^2>\\frac{1}{8}\\|x_0-z^\\ast\\|^2$, where $x_0=0$ is the algorithm's start and $x_T$ its $T$-th iterate. Since the objective gap after $T$ queries is only guaranteed to decay as $O(1/T^2)$, any deterministic first-order method needs $\\Omega(1/\\sqrt{\\varepsilon})$ oracle calls to compute an $\\varepsilon$-approximate solution. The paper first proves this under a linear-span assumption on the iterates, then removes that assumption through orthogonal rotations of the data matrix, yielding the general theorem.","pith_inferences":["A natural benchmarking test is to run an accelerated first-order method on the constructed family and check whether the gap after $T$ iterations follows the $1/T^2$ envelope; the construction supplies explicit finite-$T$ certificates for such tests.","The same subspace-nesting mechanism may carry over to other smooth generalized linear losses with odd saturating link functions (for example probit-style losses), provided an analogue of the fixed-point equation for $c$ holds; this is an extension the paper does not discuss.","The result is a worst-case certificate, not a typical-case prediction; on separable, low-rank, or otherwise structured datasets, practical logistic regression solvers can still perform far better than this bound.","Because the proof is tied to deterministic oracle queries, a separate argument would be needed to decide whether randomized or parallel first-order methods can circumvent this $\\Omega(1/\\sqrt{\\varepsilon})$ barrier."],"forward_implications":["No deterministic first-order method can guarantee a faster worst-case rate than $\\Omega(1/\\sqrt{\\varepsilon})$ on binary logistic regression, so accelerated gradient methods already achieve the optimal worst-case complexity for this problem class.","The constructed logistic losses provide new explicit worst-case function instances inside smooth convex optimization, alongside the existing quadratic and smoothed-maximum instances.","The lower bound applies exactly in the large-scale regime $T\\ll n$: the dataset dimension grows linearly in the iteration budget ($n=4T+2$).","The distance bound $\\|x_T-z^\\ast\\|^2>(1/8)\\|x_0-z^\\ast\\|^2$ shows that the failure is not merely in the objective value; the iterates themselves remain far from the optimal parameter vector.","If zero optimal intercept is not required, the authors note that a simpler two-block dataset $(A_k=(2\\sigma W_k;2\\zeta W_k),\\,b_k=(1_k,-1_k))$ suffices."],"supporting_citations":[{"why":"supplies the seminal orthogonal-invariance technique used to remove the linear-span assumption in Section 3.","marker":"Nemirovski (1992)"},{"why":"provides Lemma 3.1, the nested-subspace rotation lemma on which Proposition 3.2 and Theorem 3.3 rest.","marker":"Ouyang and Xu (2019)"},{"why":"gives the accelerated gradient method and the $O(1/\\sqrt{\\varepsilon})$ upper bound that the lower bound matches.","marker":"Nesterov (2004)"},{"why":"provides the earlier smooth-convex worst-case instances against which the paper positions its logistic-loss instances as new.","marker":"Guzmán and Nemirovski (2015)"}],"fun_headline_variants":["Adversarial data force Ω(1/√ε) queries for any deterministic solver","Worst-case binary logistic sets pin first-order methods to 1/T² rate","New lower bound: binary logistic regression needs Ω(1/√ε) calls","Crafted data show 1/T² is the floor for all first-order methods"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's load-bearing premise is a cited geometric lemma: for nested subspaces $X\\subsetneq \\bar{X}$, an orthogonal rotation can fix $X$ pointwise while moving any given vector into $\\bar{X}$; if this lemma fails or cannot be applied to the specific nested subspaces $K_{2i+1,k}$ used in the induction, the general linear-span-free lower bound would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Adversarial data force Ω(1/√ε) queries for any deterministic solver","Worst-case binary logistic sets pin first-order methods to 1/T² rate","New lower bound: binary logistic regression needs Ω(1/√ε) calls","Crafted data show 1/T² is the floor for all first-order methods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001183,"raw_usage":{"total_tokens":4878,"prompt_tokens":933,"completion_tokens":3945,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":3857}},"tokens_in":549,"tokens_out":3945,"duration_ms":33081,"temperature":1.0,"reasoning_tokens":3857,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:52:34.881793+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a deterministic first-order method and an iteration count $T$ for which, on every dataset of size $n=4T+2$, $N=16T+8$ (in particular every orthogonal rotation of the constructed $(A_k,b_k)$), the function-value gap after $T$ queries is smaller than the corresponding claimed lower bound; this would contradict Theorem 3.3. A narrower check is to verify Lemma 3.1 numerically on the nested subspaces used in Proposition 3.2: if an orthogonal $V$ fixing $K_{2s,k}$ and moving a random point into $K_{2s+1,k}$ fails to exist for some $s$, the induction that removes the linear-span assumption breaks.","supporting_citations":[{"cited_title":"Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems","cited_arxiv_id":null,"evidence_quote":"provides Lemma 3.1, the nested-subspace rotation lemma on which Proposition 3.2 and Theorem 3.3 rest."},{"cited_title":"On lower complexity bounds for large-scale smooth convex optimization","cited_arxiv_id":null,"evidence_quote":"provides the earlier smooth-convex worst-case instances against which the paper positions its logistic-loss instances as new."}],"review_version":1}