Metraipolis › archive › dc_0e567bb993fd

Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability — arXiv:2610.01459

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.01459
License (as archived)
CC0-1.0
Archived
2026-10-06T15:33:53.171Z
SHA-256 of the archived text
20a519fa7f33241dd7e65aabd8a6894c2e671835fd3fcbcb8b003029c401a1b2
Stable URL of this page
https://metraipolis.com/documento/dc_0e567bb993fd

How to cite

Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability — arXiv:2610.01459 — arXiv (en), https://arxiv.org/abs/2610.01459 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0e567bb993fd (Metraipolis archive dc_0e567bb993fd, sha256 20a519fa7f33241dd7e65aabd8a6894c2e671835fd3fcbcb8b003029c401a1b2)
BibTeX
@misc{dc0e567bb993fd,
  title = {Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability — arXiv:2610.01459},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.01459},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0e567bb993fd; sha256 20a519fa7f33241dd7e65aabd8a6894c2e671835fd3fcbcb8b003029c401a1b2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.01459. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study logistic regression on linearly separable data under gradient descent with a large constant stepsize $\eta$. Such dynamics may exhibit a characteristic Edge of Stability phenomenon, in which the loss initially oscillates before transitioning to a stable phase of monotone decrease. Existing work provides a tight $\Theta(1)$ bound in dimension $d=2$ as $\eta \to \infty$ and conjectures a bound independent of $\eta$ in arbitrary dimensions $d\geq 2$. In this paper, we disprove this conjecture by showing that, for every fixed sample size $n\geq 2$ and sufficiently small margin $\gamma$, the worst-case transition time is $$\Theta\!\left((\log\eta)^{\min\{n-2,d-2\}}\right)$$ uniformly over $d\geq2$. The key challenge in establishing a tight bound is that the sample contributing most strongly to the gradient can change repeatedly across iterations. To address this issue, we control such changes by induction on dimension and sample size, and construct matching hard instances.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-10-02 in stat.ML).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.01459 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T15:12:55.903Z dalla pagina https://arxiv.org/catchup/stat.ML/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).