Some Worst-Case Datasets of Deterministic First-Order Methods for Solving Binary Logistic Regression

Trevor Squires; Yuyuan Ouyang

REVIEW 2 major objections 5 minor 12 references

Some Worst-Case Datasets of Deterministic First-Order Methods for Solving Binary Logistic Regression

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict A solid worst-case construction for zero-initialized first-order methods, but the 'any deterministic method' claim rests on an invalid x0=0 WLOG. read the letter →

arxiv 1908.04091 v1 pith:ZVC4MDHC submitted 2019-08-12 math.OC

Yuyuan Ouyang , Trevor Squires This is my paper · ORCID

classification math.OC MSC 90C2590C6068Q25

keywords binarylogisticregressionfirst-ordermethodslowercomplexityboundworst-casedatasetsmoothconvexoptimizationdeterministicoracleorthogonalinvariance

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

The 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.

My 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.

This 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.

Referee Report

2 major / 5 minor

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.

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 (2)

[Section 1 (after Eq. (1.4)); Proposition 3.2; Theorem 3.3 proof] 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.
[Theorem 3.3] 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.

minor comments (5)

[Abstract and Section 1.1] The phrase "at least O(1/√ε)" for a lower complexity bound is formally confusing; the intended statement is Ω(1/√ε).
[Theorem 3.3 proof] 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.
[Lemma 2.2 proof] 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".
[Concluding remarks] The word "server" should be "serve" in the first sentence.
[Theorem 3.3 statement] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is constructed from explicit worst-case data, not fitted; the sole self-citation is an auxiliary linear-algebra lemma that is not the target result.

full rationale

The paper's central claim is a lower complexity bound for deterministic first-order methods on binary logistic regression. The proof constructs explicit data matrices A_k and response vectors b_k, computes the exact minimizer x* = c(1,2,...,k)^T, establishes subspace invariance in Lemmas 2.2 and 2.3, and derives the objective and distance lower bounds arithmetically in Theorem 2.5 using the explicit constants from Lemma 2.4. The O(1/sqrt(epsilon)) rate is not assumed or imported; it follows from the constructed gap bound. The extension in Section 3 removes the linear-span assumption via Proposition 3.2, whose proof is given in the paper. The only externally cited ingredient in that extension is Lemma 3.1 from Ouyang and Xu (2019), a self-citation. That lemma is a parameter-free linear-algebra statement about orthogonal maps between nested subspaces; it does not assert the lower bound, is not an ansatz, and does not smuggle in the paper's conclusion. It is auxiliary and independently checkable, so under the stated rules it does not raise the circularity score. The potentially problematic claim that one can assume x0 = 0 without loss generality is a correctness concern about the proof's coverage, not a circular step: even if the WLOG is false for logistic loss, the lower bound would still be derived from the construction rather than being equivalent to an input or fitted parameter. No fitted-input-called-prediction, self-definitional, uniqueness-imported, or renaming step appears.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central lower-bound derivation in Section 2 is self-contained except for standard convex-analysis facts. The general result in Section 3 imports one geometric lemma from Ouyang and Xu (2019). The construction parameters σ, ζ, c are chosen or defined before the bound is derived; no constant is fitted to the target O(1/√ε) rate. The ratio σ/ζ=1.3 is a hand-picked value that makes the positive constant C(1.3)>1/2 easy to verify numerically.

free parameters (1)

σ/ζ ratio = 1.3
Hand-picked in Lemma 2.4 and Theorem 2.5 to satisfy 2ζ>σ>ζ and make the constant C(σ/ζ) exceed 1/2; it influences only constant factors, not the 1/√ε scaling.

assumptions (4)

domain assumption Deterministic first-order oracle model with x0=0 and x_t both inquiry point and candidate solution (Eq. (1.4))
Defines the algorithm class for which the lower bound is proved; standard in complexity analysis.
standard math Strict convexity of the binary logistic loss ensures unique minimizers (used in Lemma 2.1)
Justifies that x* and (x*,0) are the unique solutions; the loss is a sum of strictly convex logistic terms.
standard math Lemma 3.1 from Ouyang and Xu (2019): for X⊊X̄ there is an orthogonal V fixing X and moving any x̄ into X̄
Imported and unproved in this paper; it is the key tool that lets the authors remove the linear-span assumption in Section 3.
standard math Existence of c>0 satisfying σ tanh(σc)+ζ tanh(ζc)=σ−ζ
Proved in Lemma 2.1 via continuity; characterizes the location of the optimum in the constructed dataset.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Some Worst-Case Datasets of Deterministic First-Order Methods for Solving Binary Logistic Regression." pith.science (2026). https://pith.science/paper/ZVC4MDHC

@misc{pith2026190804091,
  author       = {Pith},
  title        = {Pith review of: Some Worst-Case Datasets of Deterministic First-Order Methods for Solving Binary Logistic Regression},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZVC4MDHC}},
  note         = {Machine review of arXiv:1908.04091}
}

abstract

We present in this paper some worst-case datasets of deterministic first-order methods for solving large-scale binary logistic regression problems. Under the assumption that the number of algorithm iterations is much smaller than the problem dimension, with our worst-case datasets it requires at least $\mathcal{O}(1/\sqrt{\varepsilon})$ first-order oracle inquiries to compute an $\varepsilon$-approximate solution. From traditional iteration complexity analysis point of view, the binary logistic regression loss functions with our worst-case datasets are new worst-case function instances among the class of smooth convex optimization problems.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages

[1]

Self-concordant analysis for logistic regression

Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4: 0 384--414, 2010

work page 2010
[2]

Lower bounds for finding stationary points I

Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I . arXiv preprint arXiv:1710.11606, 2017 a

arXiv 2017
[3]

Lower Bounds for Finding Stationary Points II: First-Order Methods

Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II : First-order methods. arXiv preprint arXiv:1711.00841, 2017 b

work page Pith review arXiv 2017
[4]

Lower Bounds for Parallel and Randomized Convex Optimization

Jelena Diakonikolas and Crist \'o bal Guzm \'a n. Lower bounds for parallel and randomized convex optimization. arXiv preprint arXiv:1811.01903, 2018

work page Pith review arXiv 2018
[5]

The exact information-based complexity of smooth convex minimization

Yoel Drori. The exact information-based complexity of smooth convex minimization. Journal of Complexity, 39: 0 1--16, 2017

work page 2017
[6]

On lower complexity bounds for large-scale smooth convex optimization

Crist \'o bal Guzm \'a n and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31 0 (1): 0 1--14, 2015

work page 2015
[7]

Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization

Anatoli Juditsky and Yuri Nesterov. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stochastic Systems, 4 0 (1): 0 44--80, 2014

work page 2014
[8]

Nemirovski and D

A. Nemirovski and D. Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV, 1983

work page 1983

Show all 12 references

[9]

A. S. Nemirovski. Information-based complexity of linear operator equations. Journal of Complexity, 8 0 (2): 0 153--175, 1992

1992
[10]

Y. E. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Massachusetts, 2004

2004
[11]

Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems

Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, pages 1--35, 2019

2019
[12]

Tight complexity bounds for optimizing composite objectives

Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in neural information processing systems, pages 3639--3647, 2016

2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Self-concordant analysis for logistic regression

Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4: 0 384--414, 2010

work page 2010

[2] [2]

Lower bounds for finding stationary points I

Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I . arXiv preprint arXiv:1710.11606, 2017 a

arXiv 2017

[3] [3]

Lower Bounds for Finding Stationary Points II: First-Order Methods

Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II : First-order methods. arXiv preprint arXiv:1711.00841, 2017 b

work page Pith review arXiv 2017

[4] [4]

Lower Bounds for Parallel and Randomized Convex Optimization

Jelena Diakonikolas and Crist \'o bal Guzm \'a n. Lower bounds for parallel and randomized convex optimization. arXiv preprint arXiv:1811.01903, 2018

work page Pith review arXiv 2018

[5] [5]

The exact information-based complexity of smooth convex minimization

Yoel Drori. The exact information-based complexity of smooth convex minimization. Journal of Complexity, 39: 0 1--16, 2017

work page 2017

[6] [6]

On lower complexity bounds for large-scale smooth convex optimization

Crist \'o bal Guzm \'a n and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31 0 (1): 0 1--14, 2015

work page 2015

[7] [7]

Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization

Anatoli Juditsky and Yuri Nesterov. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stochastic Systems, 4 0 (1): 0 44--80, 2014

work page 2014

[8] [8]

Nemirovski and D

A. Nemirovski and D. Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV, 1983

work page 1983