Risk and parameter convergence of logistic regression

The logistic loss is strictly convex and does not attain its infimum; consequently the solutions of logistic regression are in general off at infinity. This work provides a convergence analysis of stochastic and batch gradient descent for logistic regression. Firstly, under the assumption of separability, stochastic gradient descent minimizes the population risk at rate O(ln(t)/t) with high probability. Secondly, with or without separability, batch gradient descent minimizes the empirical risk at rate O(ln(t)/t). Furthermore, parameter convergence can be characterized along a unique pair of complementary subspaces defined by the problem instance: one subspace along which strong convexity induces parameters to converge at rate O(ln(t)/ √ t), and its orthogonal complement along which separability induces parameters to converge in direction at rate O(ln ln(t)/ ln(t)). 1 Overview Logistic regression is the task of finding a vector w ∈ R which approximately minimizes the population or empirical logistic risk, namely Rlog(w) := E [ `log(〈w,−yx〉) ] or R̂log(w) := 1 n n ∑ i=1 `log(〈w,−yixi〉), where `log(r) := ln ( 1 + exp(r) ) is the logistic loss. A traditional way to minimize Rlog or R̂log is to pick an arbitrary w0, and from there recursively construct stochastic gradient descent (SGD) or gradient descent (GD) iterates (wj)j≥0 via wj+1 := wj − ηjgj , where (ηj)j≥0 are step sizes, and gj := ` ′ log (〈 wj ,−yjxj 〉) (−yjxj) for SGD or gj := ∇R̂`log(wj) for GD. A common assumption is that the distribution on (x, y) is separable (Novikoff, 1962; Soudry et al., 2017). Under this assumption, the first result here is that SGD with constant step sizes minimizes the population risk Rlog at rate Õ(1/t) with high probability. Theorem 1.1 (Simplification of Theorem 2.1). Suppose there exists a unit vector ū with 〈ū, yx〉 ≥ γ, and |yx| ≤ 1 almost surely. Consider SGD iterates (wj)j≥0 as above, with w0 = 0 and ηj = 1. Then for any t ≥ 1, |wt| ≤ O(ln(t)), and with probability at least 1− δ, the average iterate ŵt := t−1 ∑ j<t wj satisfies Rlog(ŵt) ≤ O ( ln(t) + ln(t) ln(1/δ) t ) . This result improves upon prior work in the following ways. 1. Since `log exhibits an exponential tail and Lipschitz continuity, standard analyses give a Õ(1/ √ t) rate of SGD with step size ηj = 1/ √ j + 1, but only in expectation (Nesterov, 2004; Bubeck, 2015). With the O(ln(t)) bound on |wt| given by Theorem 1.1, Azuma-Hoeffding’s inequality gives a high-probability Õ(1/ √ t) rate. However, since standard analyses do not ensure a vanishing risk with constant step sizes, they do not give a Õ(1/t) rate. 1 ar X iv :1 80 3. 07 30 0v 2 [ cs .L G ] 1 J un 2 01 8 2. The only other prior high-probability Õ(1/t) rate is under strong convexity (e.g., (Rakhlin et al., 2012)): |wt − w̄| ≤ Õ(1/t) with high probability, where w̄ is the global optimum. However, `log is not strongly convex on R, and even in trivial cases the optimum of logistic regression may be off at infinity: suppose examples (xi) n i=1 lie on the positive real line, and labels (yi) n i=1 are all +1; then infw∈R R̂log(w) = 0, but R̂log(w) > 0 for every w ∈ R. Furthermore, not only do the guarantees here avoid strong convexity; the proofs are different. The proof of Theorem 1.1 is based on the perceptron proof, and might be of independent interest. Now consider batch gradient descent on empirical risk. In this case, a stronger result is possible: no assumption is made (separability is dropped), and the parameters may be precisely characterized. Theorem 1.2 (Simplification of Theorems 3.1, 3.2 and 3.6). Let examples ((xi, yi)) n i=1 be given with |xiyi| ≤ 1, along with a loss ` ∈ {`log, exp}, with corresponding empirical risk R̂ as above. Consider GD iterates (wj)j≥0 as above, with w0 = 0. 1. (Convergence in risk.) For any step sizes ηj ≤ 1 and any t ≥ 1, R̂(wt)− inf w∈Rd R̂(w) = O ( 1 t + ln(t) ∑ j<t ηj ) = { O(ln(t)/t) ηj = Ω(1), O(ln(t)/ √ t) ηj = Ω(1/ √ j + 1). 2. (Convergence in parameters.) There exists a unique subspace S, unique unit vector ū ∈ S⊥, and unique vector v̄ ∈ S which characterize convergence as follows. Fixing step size ηj := 1/ √ j + 1, letting ΠS denote orthogonal projection onto S, and defining optimal iterates w̄t := inf { R̂(w) : |w| ≤ |wt| } , if t = Ω(n ln(t)), then |ΠSwt| = Θ(1) and max { |ΠSwt − v̄|, |ΠSw̄t − v̄| } = O ( ln(t) √ t ) , |ΠS⊥wt| = Θ(ln(t)) and max ∣∣∣∣ wt |wt| − ū ∣∣∣∣2 , ∣∣∣∣ w̄t |w̄t| − ū ∣∣∣∣2 } = O ( ln ln t ln t ) . In particular, wt/|wt|→ ū and ΠSwt → v̄. To make sense of this, recall firstly the earlier discussion that the solutions are off at infinity in general. As will be made precise in Section 3.1, if examples are separable, then S = {0}, v̄ = 0, and ū is the unique maximum margin separator. The GD iterates not only keep driving R̂ to its infimum 0, but also closely track ū in direction, meaning wt/|wt|→ ū. Note that this is a strong mode of convergence: R̂(wt) = Õ(1/t) and |wt| = Θ(ln(t)) do not exclude the possibility that there is always a large angle between wt/|wt| and ū. The full part 2 of Theorem 1.2 gives a characterization of parameter convergence in the general setting: the parameter space can be split into a subspace S along which optimization is strongly convex, and its complement S⊥ along which the problem behaves as though separable. While there does exist recent prior work on parameter convergence of gradient descent for logistic regression (Soudry et al., 2017; Gunasekar et al., 2018; Nacson et al., 2018), it assumes separability. The analysis essentially for free gives convergence not only to (v̄, ū), but also to the optimal iterates w̄t. Consequently, logistic regression is implicitly regularized in a strong sense: it produces a sequence of iterates which closely track the outputs of a sequence of constraint optimization problems. This paper is organized as follows. SGD population risk convergence (Section 2). An online guarantee is given by a perceptron-style analysis, and transformed into a high-probability bound via a martingale Bernstein bound. Empirical samples structure (Section 3.1). The first step of the analysis is to derive the unique complementary subspaces (S, S⊥), along with unique optimal direction ū ∈ S⊥ and unique vector v̄ ∈ S. (S, S⊥) and ū are unique given the data ((xi, yi)) n i=1 and are not affected by the choice of ` or optimization method; v̄ depends on ` but not on the optimization method.