Independent derivation and extension of the convergence theory in Bao, Sakaue & Takezawa (NeurIPS 2025), "Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses." This repository documents the full hand-derivation of the paper's convergence proof, an identified limitation in its margin assumption, and a proposed relaxation grounded against classical perceptron theory.
The 2025 paper proves that gradient descent, run with any fixed step size, drives loss to zero on linearly separable data, for a broad family of losses (Fenchel– Young losses) generated by convex potentials. The proof requires a uniform margin condition: every data point must individually satisfy a fixed confidence threshold, for all time. This is unrealistic for non-stationary, low-SNR signal data (e.g. gravitational-wave strain), where noise is layered from multiple independent, drifting sources rather than one steady process.
papers/— the primary source (Bao, Sakaue & Takezawa 2025) plus the two classical results used to ground the proposed extension: Freund & Schapire (1999) and a modern survey (Mohri & Rostamizadeh) reproducing both the Freund–Schapire and Novikoff (1962) proofs in full.derivations/— my own hand-derivations, in order:- Gradient descent, softmax, and the Fenchel–Young loss framework from first principles.
- The perceptron argument (alignment growth / norm growth) underlying the 2025 paper's convergence theorem.
- A proposed relaxation — replacing the uniform margin with a Cesàro (running-average) margin condition — derived and compared against the classical Freund & Schapire aggregate-margin relaxation, to establish precisely how the two differ.
Given that Freund & Schapire (1999) already relax the perceptron's uniform margin condition to an aggregate one, does that make a similar relaxation for the 2025 Fenchel–Young loss convergence theorem redundant?
Short answer: no. The two relaxations differ in the algorithm analyzed
(discrete mistake-counting perceptron vs. continuous gradient descent), the
object bounded (mistake count vs. convergence rate to a loss value), the type of
relaxation (a fixed one-shot aggregate vs. a time-varying running average), and
the loss family covered (hinge loss vs. the full Fenchel–Young family). Full
reasoning in derivations/03_GD_FYLoss_FreundSchapire_Extension.docx.
This is active, independent research exploration, not a finished result. Open questions, corrections, and pointers to related work are very welcome.
See references.md.