Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.26748
curl -X POST /api/v1/records/arxiv/2610.26748/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.26748/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'