Newest papers

Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression

Andreea-Alexandra Muşat, Nicolas Boumal · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.26748 · cited by 0 works (OpenAlex) · open-access PDF

Hindi

हम दिखाते हैं कि $\varepsilon$ के साथ कदम आकार के साथ ग्रेडिंट डिस्चेंज (GD) $\varepsilon$ पर बहु-स्तरीय रजिस्ट्रेशन रिगर्शन नुकसान पर इष्टतम अंतर को प्राप्त कर सकता है $\varepsilon$ जो $\varepsilon$ से स्वतंत्र है। ऐसा करने के लिए, कदम आकार $η$ $\varepsilon$ (और रैखिक रूप से विभाजित डेटासेट की गुणों) के एक कार्य के रूप में पर्याप्त बड़ा चुना जाना चाहिए, जबकि $\varepsilon$ एक निरंतर है जो केवल डेटा पर निर्भर करता है। डेटा के प्रासंगिक गुणों में अंकों की संख्या और उनके मार्जिन ($\varepsilon$ के लिए) शामिल हैं, और एक अतिरिक्त राशि (

Machine translation (Meta M2M100); the English original follows.

Abstract

We show that gradient descent (GD) with step size $η$ can achieve $\varepsilon$ optimality gap on the multiclass logistic regression loss in a number of iterations $T$ that is independent of $\varepsilon$. To do so, the step size $η$ must be chosen large enough as a function of $\varepsilon$ (and properties of the linearly separable dataset), while $T$ is a constant that only depends on the data. The relevant properties of the data include the number of points and their margin (for $T$), and one additional quantity (for $η$) that turns out to be necessary in dimension $d \geq 3$. The proofs build on the known fact that, as $η\to \infty$, suitably rescaled GD becomes the perceptron algorithm, and the latter finds a perfect classifier in $T$ iterations. A similar claim was shown for two classes in dimension $d = 2$ using other proof techniques. This result adds to previous works that showed GD on the logistic regression loss can be accelerated by taking large step sizes. Those provoke a wild, oscillatory initial phase, followed by a stable phase. We provide results of this (qualitatively different) nature, too.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Mathematics, Gradient descent, Separable space, Dimension (graph theory), Mathematical proof, Logistic regression

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange