Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression

By Francis R. Bach. 2013

177 citations recorded by the source corpus.

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/R2√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/√N), and improves to O(R2/µN) where µ is the lowest eigenvalue of the Hessian at the global optimum (when this eigenvalue is greater than R2/√N. Since µ does not need to be known in advance, this shows that averaged stochastic gradient is adaptive to 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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “This type of analysis has been successfully used recently (Bach and Moulines, 2011; Dieuleveut et al., 2017; Godichon and Saadane, 2017; Gadat and Panloup, 2017). For quadratic functions, larger steps can be used, as pointed by Bach and Moulines (2013). Indeed, even with non-decaying step size, the ”
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) (2013, background): “Assumption(B3) is satisfied for the logistic loss and extends to all generali zed linear models (see more details in [22]), and the relationship between the thir d derivative and second derivative of the lossl is often referred to aself-concordance(see [9, 25] and references therein).”
On the rates of convergence of parallelized averaged stochastic gradient algorithms (2017, background): “Then, let n = åp i=1 n i, lim n!¥ v u u t p å i=1 n i (mb n m) ˘N 0,G 1 mSG 1 , where S := E[r hg (X,m) r hg (X,m)]. Remark: Among the classical examples, one can think about logistic regression [1], which leads to minimize E[ln(1 +exp( Y hX,hi))], where Y 2f 1,1gand X 2Rd. One can also think abou”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, methodology): “Several efforts consider SGD in this oracle (Bach and Moulines, 2011; Bach, 2014; Dieuleveut and Bach, 2015; Frostig et al., 2015; Needell et al., 2016) presenting non-asymptotic results, often with iterate averaging.”
Accelerating Stochastic Gradient Descent (2017, background): “Along these lines, non-asymptotic rates towards statistically optimal estimators are given by Bach and Moulines (2013); Bach (2014); Défossez and Bach (2015); Dieuleveut and Bach (2015); Needell et al. (2016); Frostig et al. (2015b); Jain et al. (2016).”
Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance (2019, unknown): “While Assumption 3 is standard in the analysis of such models [8, 33, 35, 3], Assumption 5 imposes that the model is “well-specified”, that is, for supervised learning situations from Example 1, we have chosen a rich enough representation Φ.”
Risk and parameter convergence of logistic regression (2018, background): “ound D, the exponential concavity term is 1== eD. In the unbounded setting considered in this paper, this term is a factor of poly(t) since jw tj= ( ln(t)) (cf. Lemma 4.3). (Bach and Moulines, 2013; Bach, 2014) assume optima exist, and the rates depend inversely on the smallest eigenvalue of the Hes”
Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression (2016, methodology): “This rate is optimal without assumption on the spectrum of the covariance matrix, but comes from a worst-case analysis: we show in the next paragraphs that we can derive a tighter and optimal rate for both averaged-SGD (recovering results from Dieuleveut and Bach (2015)) and accelerated-SGD, for a l”
Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis (2013, background): “Note that since α < 1 , this bound is much smaller than that of the standard group lasso.”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, unknown): “[7] Francis Bach.”
Bridging the gap between constant step size stochastic gradient descent and Markov chains (2017, background): “Our work opens up several avenues for future work: (a) show that Richardson-Romberg trick can be applied to the decreasing step-sizes setting, (b) study the extension of our results under self-concordance condition [3].”
Communication trade-offs for Local-SGD with large step size (2019, methodology): “Though both of these approaches are often considered to be nearly equivalent [44, 45], fundamental differences exist in their convergence properties.”
Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity (2017, background): “…condition β > 1 / 2 and β 1 is necessary to obtain the tight constant Tr(Σ ⋆ ), and the choice β = 1 / 2 does not seem appropriate in a general situation according to what is claimed in [BM11] and contrary to what is claimed in [Bac14] in the particular case of the on-line logistic regression.”
Proximity Without Consensus in Online Multiagent Optimization (2016, result): “In doing so, we attain comparable rates to stochastic gradient method for the weakly convex unconstrained stochastic case [32], [33] for the primal sub-optimality, but slower rates for the reduction of constraint violation.”
Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization (2016, methodology): “Other SA methods with provable complexities for solving convex stochastic optimization problems were also studied in [19, 26, 27, 28, 29, 30, 2, 13, 1, 51, 54].”
Finite-sample Analysis of M-estimators using Self-concordance (2018, methodology): “For growing sample size n = 10, k ∈ [1, 3], we generate an i.”
Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients (2018, methodology): “The assumption of a stable Hessian was previously used to analyze the statistical properties of logistic regression in [3], and to analyze the convergence of SGD on logistic regression in [4, 5].”
Asynchronous Saddle Point Algorithm for Stochastic Optimization in Heterogeneous Networks (2019, background): “2.19], or [47, Section 4], convergence to the neighborhood of size O ( (cid:8)T ) is well known.”