Source-linked AI summary
Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
Francis Bach
TL;DR
The paper addresses how averaged stochastic gradient can exploit local strong convexity in logistic regression even when global strong convexity is unavailable and the local curvature is unknown. It analyzes a constant-step-size method using generalized self-concordance and shows adaptivity to the Hessian curvature at the optimum without compactness assumptions or explicit exponential factors.
Problem
Logistic regression lacks global strong convexity, while the relevant local strong-convexity constant is not known in advance.
Method
The paper analyzes averaged stochastic gradient with a constant step size proportional to 1/R^2√N, using generalized self-concordance for logistic regression and related models.
Results
The method adapts to the local strong-convexity constant, defined by the lowest Hessian eigenvalue at the optimum, without requiring that constant in advance.
Takeaways & Limitations
Averaged stochastic gradient provides a simple analysis for logistic regression that benefits from local curvature without explicit exponential dependence on the initialization distance.
Takeaways & Limitations
The analysis notes an exponentially small curvature lower bound in a general covariance-based argument, although this bound can be overly pessimistic in practice.
Abstract
from arXiv · showhide
In this paper, we consider supervised learning problems such as logistic regression and study the stochastic gradient method with averaging, in the usual stochastic approximation setting where observations are used only once. We show that after $N$ iterations, with a constant step-size proportional to $1/R^2 \sqrt{N}$ where $N$ is the number of observations and $R$ is the maximum norm of the observations, the convergence rate is always of order $O(1/\sqrt{N})$, and improves to $O(R^2 / μN)$ where $μ$ is the lowest eigenvalue of the Hessian at the global optimum (when this eigenvalue is greater than $R^2/\sqrt{N}$). Since $μ$ does not need to be known in advance, this shows that averaged stochastic gradient is adaptive to \emph{unknown local} strong convexity of the objective function. Our proof relies on the generalized self-concordance properties of the logistic loss and thus extends to all generalized linear models with uniformly bounded features.
1. Introduction
The paper studies averaged stochastic gradient for learning problems whose objectives may lack global strong convexity, especially logistic regression. It develops an analysis that exploits local strong convexity through self-concordance without requiring its value in advance.
- Averaged stochastic gradient achieves O(1/µn) for µ-strongly convex objectives and O(1/√n) for merely convex objectives.
- Logistic regression is not globally strongly convex because its loss loses curvature outside compact prediction ranges, while feature correlations are unknown during sequential training.
- Self-concordance yields an O(R^2/µn) bound without exponentially increasing factors under suitable assumptions.
- Earlier adaptive analyses can yield O(1/µ^2n) dependence and do not directly apply to logistic regression's lack of global strong convexity.
- The paper analyzes averaged stochastic gradient for generalized linear models using a step size proportional to 1/R^2√n.
- For a finite horizon N, the method uses a constant step size decreasing with N and adapts to the Hessian's lowest eigenvalue at the optimum without knowing it beforehand.
2. Stochastic Approximation for Generalized Linear Models
The paper formulates stochastic approximation for convex, differentiable objectives with generalized self-concordance and bounded gradients. It applies the framework to logistic regression and other generalized linear models, using averaged iterates and kernel-compatible implementations.
- Assumptions: The framework assumes convexity, differentiability, generalized self-concordance, and bounded gradients for the objective and observation-level functions.
- Algorithm: Averaged iterates are maintained online through a recursion that updates the running average after each stochastic-gradient step.
- Self-concordance: Generalized self-concordance relates gradient norms to excess cost using local rather than global strong convexity.
- Examples: The assumptions cover logistic regression with uniformly bounded features, as well as multinomial regression, conditional random fields, and robust regression.
- Implementation: In finite dimensions, each iteration costs O(d), while kernel implementations can represent iterates through observation-weight combinations.
- Implementation: Without regularization in the kernel setting, previous observation weights remain constant and total complexity is O(n^2) times the cost of one kernel evaluation.
3. Related Work
Related work establishes averaged stochastic gradient rates for convex and strongly convex problems, while highlighting the challenge of adapting to unknown local curvature without global strong convexity. This paper addresses that challenge without compactness assumptions and without exponential factors.
- Non-strongly-convex problems: For convex objectives, averaging with step sizes proportional to 1/√n yields the minimax-optimal rate O(1/√n).
- Non-strongly-convex problems: The paper avoids compactness assumptions used by earlier analyses for projections, step-size optimization, and high-probability bounds.
- Non-strongly-convex problems: The analysis derives higher-order and high-probability bounds despite the greater difficulty caused by noncompact domains.
- Strongly-convex problems: For strongly convex problems, existing approaches use step sizes depending on µ or longer step sizes that can achieve optimal asymptotic behavior without knowing µ.
- Strongly-convex problems: Logistic regression lacks global strong convexity, so the paper targets adaptivity to the Hessian eigenvalue at the optimum.
- Strongly-convex problems: The resulting analysis avoids exponential terms in RD that can arise from compact-domain assumptions and traditional analyses.
4. Non-Strongly Convex Analysis
The section analyzes averaged stochastic gradient without strong-convexity assumptions, establishing O(1/√N) excess-risk behavior and stronger moment and gradient bounds. The O(1/N) gradient convergence result enables later adaptivity to local strong convexity.
- Non-strongly convex setting: The analysis first treats the non-strongly convex case and targets O(1/√N) excess-risk convergence for averaged stochastic gradient.Higher-order moments are also bounded at the same rate.
- Expected convergence: A constant step size yields an expected excess-risk bound decaying as O(γ + 1/(γn)), motivating γ proportional to 1/√N.The bound is stated for the averaged iterate under the assumptions used in this section.
- Step-size choice: The chosen step size does not require prior knowledge of the initial distance to the optimum, although knowing that distance could improve the step size.The quantity R^2∥θ0−θ∗∥^2 may implicitly scale linearly with dimension in practice.
- Higher-order and tail bounds: All moments of the iterate error and excess risk are bounded, yielding subexponential behavior without restricting iterates to a predefined bounded set.The same higher-order bounds extend from the last iterate to the averaged iterate.
- Interpretation of convergence: The iterates need not converge to a unique global optimum, even though their distances and averaged excess risks admit the stated bounds.The paper notes that the optimum itself may not be unique.
- Gradient convergence: The squared gradient norm at the averaged iterate converges at O(1/N), with subexponential behavior for its higher moments.Self-concordance links gradient deviations to function-value deviations and supports this sharper rate.
5. Self-Concordance Analysis for Strongly-Convex Problems
The paper uses generalized self-concordance to convert averaged stochastic-gradient convergence into function-value bounds governed by local strong convexity. The resulting step-size does not require prior knowledge of the local curvature, while improvements over non-strongly-convex bounds require sufficiently large Hessian curvature.
- Local strong convexity: O(1/N) gradient convergence enables function-value bounds with dependence O(1/µN) on local strong convexity.The self-concordance analysis replaces global strong convexity, which is unavailable for logistic regression, with the local strong-convexity constant.
- Self-concordance mechanism: Self-concordance links gradient norms to excess function values without retaining an explicitly exponential factor in R∥θ0 −θ∗∥.The required generalized self-concordance condition bounds the third derivative relative to the second derivative along directions in parameter space.
- Adaptivity: The step-size is independent of µ, so averaged stochastic gradient adapts to the unknown local curvature at the optimum.The local curvature constant appears in the guarantee, but not in the step-size choice.
- Regime of improvement: The improved bounds apply only when the lowest Hessian eigenvalue is sufficiently large relative to the R- and sample-size scales.The paper states that these bounds improve on the non-strongly-convex bounds only when the Hessian's lowest eigenvalue is large enough.
- Logistic-regression curvature: For logistic regression, generic global lower bounds on local curvature can be exponentially small, although the actual local curvature may be substantially larger.The pessimistic lower bound involves the covariance eigenvalue multiplied by exp(−R∥θ∗∥), whereas the paper notes that practical curvature can be closer to the covariance scale.
6. Conclusion
The conclusion presents averaged stochastic gradient with self-concordance as a way to exploit local strong convexity without an exponential dependence on initialization distance. It also identifies extensions to changing step-sizes, doubling schedules, and alternative curvature assumptions.
- Conclusion: Averaging provides adaptivity to local strong convexity, while self-concordance yields bounds without an explicitly exponential dependence on R∥θ0 −θ∗∥.These are identified as the two key aspects of the paper's analysis for logistic regression and related problems.
- Extensions: A decaying step-size γn = O(1/R^2√n) is proposed as a natural extension for settings without a fixed known horizon.The paper expects similar results up to logarithmic terms and also mentions piecewise-constant step-sizes through a doubling trick.
- Extensions: Alternative assumptions such as exp-concavity or uniform convexity may also yield similar or improved results.These are presented as possible directions rather than established results of the paper.
- Analytical basis: The self-concordance argument specifically avoids carrying the exponential Hessian lower-bound factor into the final bound.The appendix contrasts the intermediate exponential factor with the final bound obtained using self-concordance.
- Analytical basis: Self-concordance analysis relates gradient convergence to function-value convergence through a one-dimensional inequality controlled by the Hessian at the minimizer.The supporting lemmas bound function values using gradient information and control Hessian variation through self-concordance.
B.1 Proof of Lemma 9
The proof of Lemma 9 reduces the multivariate self-concordance argument to a scalar path from the optimum to an arbitrary point. It combines curvature at the optimum, gradient control, and a third-derivative bound to obtain the required relationship.
- Proof construction: The proof defines a scalar function along the segment between θ∗ and θ, then applies the one-dimensional self-concordance lemma.The scalar path has zero value and derivative at the optimum, while its curvature is controlled at the starting point.
- Proof construction: The path's initial curvature is bounded below by µ∥θ −θ∗∥^2, while its endpoint derivative is bounded by ∥f′(θ)∥∥θ −θ∗∥.These inequalities connect local Hessian curvature and gradient size along the path.
- Resulting inequality: Applying the lemma with S = R∥θ −θ∗∥ produces the desired bound without requiring an assumption on θ.The resulting inequality is then used to convert gradient control into function-value control.
Appendix C. Proof of Proposition 3
The proof of Proposition 3 develops moment and tail bounds for the stochastic-gradient recursion using martingale structure. It combines recursive moment control with almost-sure bounds for small sample sizes.
- Proof strategies: The proof offers a longer moment-based route and shorter martingale-concentration alternatives.The alternatives use Burkholder-Rosenthal-Pinelis or Freedman's inequality, with slightly worse constants or extra logarithmic factors for the shorter proofs.
- Moment recursion: The moment proof recursively bounds higher-order terms by lower-order terms and closes the argument through induction on p.Binomial expansions and coefficient bounds control the even- and odd-indexed terms in the recursion.
- Martingale setup: The stochastic-gradient errors form martingale increments, allowing their partial sums to be treated as a martingale.The conditional expectation of each increment given the previous filtration is zero.
- Small-n control: An almost-sure iterate-distance bound controls the recursion for small n: ∥θn −θ∗∥ ≤ ∥θ0 −θ∗∥ + nγR.This bound supplies the small-sample control needed when applying the moment recursion.
- Moment recursion: Coefficient bounds reduce odd-indexed terms to neighboring even-indexed terms, yielding the recursion needed for the proposition.The proof defines constants Ck and combines their bounds across the relevant index ranges.
C.4 Proof by Induction
The appendix proves the required moment bounds by induction, combining the induction hypothesis with martingale inequalities and algebraic term comparisons. The proof uses BRP and Freedman-style arguments, with explicit restrictions and some logarithmic or constant-factor losses.
- Inductive argument: The proof proceeds by induction on p, reducing the target bound to lower-order moment bounds.The induction handles cases such as n ≤ 4p separately before applying the hypothesis.
- Inductive argument: The algebraic step compares grouped terms and ratios to establish the desired inequality when A ≤ 20.The argument changes summation variables, expands binomial coefficients, and compares coefficients across powers of ∥θ0 − θ∗∥.
- Martingale inequalities: The proof framework is based on the Burkholder-Rosenthal-Pinelis inequality for adapted Hilbert-space-valued sequences.The inequality is applied to obtain moment bounds for p in [2, n/4], followed by solving a quadratic inequality.
- Martingale inequalities: Freedman’s inequality provides an alternative route from bounded martingale increments to tail bounds.The independent-variable case recovers Bernstein’s inequality, and the resulting bound is applied to the sequence Mn.
Appendix D. Proof of Proposition 7
The proof controls the averaged gradient through martingale moment bounds and then transfers this control to the gradient at the averaged iterate using self-concordance. Convexity and the resulting inequalities yield the proposition.
- Proof strategy: The proof first bounds the averaged stochastic gradient and then relates it to the gradient at the averaged iterate.The second step uses self-concordance.
- Moment control: Burkholder-Rosenthal-Pinelis and Minkowski inequalities provide the moment control needed for the averaged gradient.The proof sums the relevant inequalities over the iterations before applying these bounds.
- Self-concordant transfer: Repeated self-concordance applications, together with convexity, control the relationship between the averaged iterate and its gradient.The resulting inequalities are combined to complete the proposition.
Appendix E. Results for Small p
For p = 1, 2, 3, the appendix refines Proposition 3’s moment bound by expanding the relevant powers and collecting terms with smaller constants.
- Refined bounds: For p = 1, 2, 3, Proposition 3’s bound can be replaced by bounds with smaller constants.These refinements are intended for proofs in Section 5.
- Refined bounds: The refinement sets a = ∥θ − θ∗∥2 and b = γ2R2, then expands powers of a + 20nb.The proof sums the resulting terms over the relevant integers.
- Third-order calculation: The third-order calculation collects mixed terms in a and b into an explicit polynomial expression.The final expansion includes terms proportional to a3, nba2, b2a, and b3.
Appendix F. Proof of Proposition 10
The proof derives large-deviation bounds for the averaged gradient and uses self-concordance for small deviations, while retaining a non-strong-convexity bound for larger deviations. Tail integration then yields bounds on excess function value and distance to the optimum.
- Gradient tails: Large-deviation control follows from all-moment bounds for ∥f′(¯θn)∥ and a moments-to-tails lemma.The argument requires p ≤ n/4 for the intermediate application, while bounded gradients handle larger t.
- Strong-convexity regime: Self-concordance is applied on an event where the averaged-gradient norm is sufficiently small relative to μ.For larger deviations, the proof uses the tail bound that does not require strong convexity.
- Tail integration: The expectation bounds are obtained by expressing excess quantities as integrals of tail probabilities and splitting them into three terms.Each term is bounded using either a trivial probability bound, the strong-convexity tail estimate, or the general tail bound.
- Function-value bound: For γ = 1/(2R2√N), the proof obtains an explicit O(R2/(Nμ))-type bound for the expected excess function value under a stated condition.The displayed bound includes polynomial dependence on α = R∥θ0 − θ∗∥.
- Distance bound: The same integration strategy yields an explicit bound for E∥¯θN − θ∗∥2, with a condition involving √N/R.The proof combines the strong-convexity and non-strong-convexity bounds before simplifying the result.