REVIEW 4 cited by
Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We study gradient descent (GD) dynamics on logistic regression problems with large, constant step sizes. For linearly-separable data, it is known that GD converges to the minimizer with arbitrarily large step sizes, a property which no longer holds when the problem is not separable. In fact, the behaviour can be much more complex -- a sequence of period-doubling bifurcations begins at the critical step size $2/\lambda$, where $\lambda$ is the largest eigenvalue of the Hessian at the solution. Using a smaller-than-critical step size guarantees convergence if initialized nearby the solution: but does this suffice globally? In one dimension, we show that a step size less than $1/\lambda$ suffices for global convergence. However, for all step sizes between $1/\lambda$ and the critical step size $2/\lambda$, one can construct a dataset such that GD converges to a stable cycle. In higher dimensions, this is actually possible even for step sizes less than $1/\lambda$. Our results show that although local convergence is guaranteed for all step sizes less than the critical step size, global convergence is not, and GD may instead converge to a cycle depending on the initialization.
Forward citations
Cited by 4 Pith papers
-
Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamics
A finite-time proof shows gradient descent on separable logistic regression reaches a constant-level alignment with the max-margin direction in O(exp(exp(-δ))) iterations, tight up to constants.
-
Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse
Noisy SGD in the mean-field regime forces wide multivariate ReLU networks to an effective width of at most 2P-1, yielding a continuous piecewise-affine predictor whose hyperplanes are non-redundant with respect to the...
-
Adaptive control mechanisms in gradient descent algorithms
A feedback-feedforward adaptive stepsize law for gradient descent is shown via Lyapunov analysis to achieve O(1/k) last-iterate convergence for convex locally smooth objectives with robustness to inexact gradients.
-
Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?
On the unit sphere, gradient descent for logistic regression converges globally for every step size below the stability threshold only in one dimension; in higher dimensions, cycles persist despite the equal-norm restriction.
Discussion (0). Continue with ORCID to comment.