Risk and parameter convergence of logistic regression

1 Introduction

• For logistic-risk gradient descent, the paper studies iterates generated by repeated gradient steps from an initial vector using step-size parameters.The theorem setup specifies initialization at zero, examples with norm at most one, and logistic or exponential loss.Source: §1 · p. 1
• The paper addresses data that are neither strongly convex-risk cases nor linearly separable, where standard analyses treat distinct regimes.For separable data, the risk infimum may be zero without being attained; strongly convex risk instead has a unique bounded optimum.Source: §1 · p. 1
• Gradient descent follows a unique ray: its direction converges to the maximum-margin predictor for a separable subset, while its projection onto S converges to the remaining data’s unique optimum.The remaining-data risk is strongly convex over bounded subsets of S.Source: §1 · p. 1
• The theorem captures both implicit bias toward the ray and implicit regularization by showing that iterates track a sequence of constrained optima.The risk itself may be minimized by any vector in a problem-defined convex cone.Source: §1 · p. 2

1.1 Notation

• The notation represents the sample with a matrix A and decomposes the data into S, the strongly convex part, and S⊥, the separable part.The text defines orthogonal projections onto these subspaces.Source: §1.1 · pp. 2–3

2 Problem structure

• In the separable example, gradient descent follows the unique maximum-margin separator, although scaling a separating vector can drive risk to zero.Source: §2 · pp. 3–4
• When the class circles overlap, the risk is coercive and strongly convex over bounded subsets, with a unique bounded optimum.Source: §2 · p. 3
• When the circles touch at the origin, the other examples remain separable, but the unavoidable origin-point loss gives the offset v̄=0.Source: §2 · p. 3
• The greedy construction builds a maximal linearly separable subset Z, while the remaining examples form the strongly convex component.Source: §2 · p. 4
• For mixed data, the remaining examples can shift the ray’s offset without affecting its maximum-margin direction.Source: §2 · p. 4
• Theorem 2.1 uniquely partitions the data into a strongly convex component with a unique minimizer and a separable component whose projection has a maximum-margin direction.Source: §2 · p. 4

3 Risk convergence

• The proof combines a generalized smoothness-based descent bound with reference point v̄+ū, enabled by Theorem 2.1.Source: §3 · pp. 4–5
• A step-dependent R(wj)-smoothness bound refines the logistic-loss analysis and is essential for proving parameter convergence.Source: §3 · p. 5
• The condition ℓ′′≤ℓ lets the Taylor remainder be bounded using R(w), and applying ln then gives ln R constant smoothness.Source: §3 · p. 6
• Since R(w0) ≤ 1, choosing ηj ≤ 1 ensures η̂j ≤ 1, and the passage states that Lemma 3.4 then holds under this condition.Source: §3 · p. 6

4 Parameter convergence

• The iterates converge in direction to the separable component ū and over S to the bounded component v̄.The section states that the corresponding parameter convergence rates are given in the subsequent case analyses.Source: §4 · p. 6

4.2 Parameter convergence over S⊥: separable case

• In the separable case, the exponential-loss analysis uses unit step sizes; the logistic-loss argument uses a warm start so small risk makes the two losses comparable.The comparison is used once the risk is at most ϵ/n, so every point’s loss is at most ϵ.Source: §4 · p. 6, §4.2 · p. 9

4 Parameter convergence

• Strong convexity of the risk over S turns risk convergence into convergence of the iterates’ S-components.The section invokes a positive strong-convexity modulus over the 1-sublevel set.Source: §4 · p. 6

4.1 Bounding |Π⊥wt|

• Bounds on iterate norms support the later parameter-rate arguments, which use both lower and upper bounds and adapt a perceptron-proof quantity.The proof controls a weighted sum of loss derivatives using the inner product with ū and the choice r = ln(t)/γ.Source: §4.1 · p. 7

4.3 Parameter convergence over S⊥: general case

• For general data, the analysis replaces risk by excess risk R(w) − R̄ to recover a separable-style argument, while accounting for cross-terms.A case analysis uses strong convexity when the error over S is larger, and a step in the ū direction when the error over S⊥ is larger.Source: §4.3 · pp. 9–10

• The structural result builds on AdaBoost analyses [Freund and Schapire, 1997; Mukherjee et al., 2011; Telgarsky, 2012, 2013], while adding the spaces S and S⊥ and a unique ū.The paper also supplies an elementary proof of the structural result.Source: §5 · p. 10
• The analysis also draws on smoothness-based gradient-descent proofs [Bubeck, 2015] and perceptron convergence ideas to bound iterate norms.Source: §5 · p. 10
• Prior separable-data analyses [Soudry et al., 2017; Gunasekar et al., 2018; Nacson et al., 2018] use a different tracking approach and achieve a better rate under separability.The paper notes that whether that rate improvement is possible for nonseparable data is unclear.Source: §5 · pp. 10–11
• Risk-convergence methods assuming bounded domains or existing optima [Bach and Moulines, 2013; Bach, 2014] acquire polynomial-in-t factors in the unbounded setting described here.The paper attributes these factors to exponential-concavity dependence on the domain bound or Hessian eigenvalue dependence when no finite optimum exists.Source: §5 · p. 11
• Unlike adversarial online-learning settings, the fixed training set allows the structural result to provide a good, small comparator.The cited comparator consequence is tied to Theorem 2.1.Source: §5 · p. 11

• The proof establishes a unique nonzero primal optimum ū and relates it to every dual optimum.It also states that every primal-dual optimal pair satisfies the displayed optimality relation.Source: A Omitted proofs from Section 2 · p. 12
• The subspaces and row partition are determined by A alone, independently of the loss ℓ.The proof constructs S from the rows assigned to AS and establishes uniqueness of the associated objects.Source: A Omitted proofs from Section 2 · p. 13
• When Ac is nonempty, the risk infimum over the full space equals the infimum over S⊥ and is zero.Source: A Omitted proofs from Section 2 · p. 13
• The restricted objective L ◦ A has compact sublevel sets over S and is strongly convex on compact subsets, so it attains a unique optimum there.Source: A Omitted proofs from Section 2 · pp. 13–14

• Theorem 3.1 applies the smoothness result to ensure function values decrease before invoking the other convergence lemmas.Source: B Omitted proofs from Section 3 · p. 14
• Summing the per-iteration inequality yields the stated cumulative bound.Source: B Omitted proofs from Section 3 · p. 14
• Under the stated loss and data-norm conditions, the proof establishes a smoothness inequality for the risk.The proof uses twice differentiability of ℓ and assumes max_i |A_i| ≤ 1.Source: B Omitted proofs from Section 3 · pp. 14–16
• The proof of Lemma 3.4 obtains its bound by recursively applying the preceding inequality.Source: B Omitted proofs from Section 3 · p. 16

• The omitted proofs are organized into subsections corresponding to those in Section 4.Source: C Omitted proofs from Section 4 · p. 16

C.1 Bounding |Π⊥wt|

• The section begins a proof of a smoothness-based convergence guarantee that accounts for Ac.Source: §C.1 · p. 16
• Lemma 4.3 is proved by establishing separate upper and lower bounds.Source: §C.1 · p. 16
• The upper-bound strategy rewrites quantities using ℓ′ so terms cancel after applying Lemma 4.4.Source: §C.1 · p. 17
• The lower-bound argument invokes Theorem 2.1 and uses smoothness from Lemma 3.4.Source: §C.1 · pp. 16, 18

C.2 Parameter convergence when separable

• Lemma 4.7 establishes a technical inequality for ℓlog using r := ℓlog(z), while its claims for ℓexp are immediate.Source: §C.2 · p. 19
• The proof handles Theorem 4.1 for the general separable case, not only for ℓexp.Source: §C.2 · p. 19
• After a warm-start time t0 with risk at most ϵ/n, the loss remains at most ϵ/n at every later iterate.Source: §C.2 · p. 19
• The proof combines upper and lower bounds on |wt|, with the constants hidden in the O notation independent of the problem.Source: §C.2 · p. 20

C.3 Parameter convergence in general

• Lemma 4.11 combines Lemmas 4.9 and 4.10 after the loss has decreased to at most ϵ/n.Source: §C.3 · p. 22
• The general proof applies Lemma 4.11’s Fenchel–Young scheme to wt or its comparison iterate, whose risk is no greater than R(wt).Source: §C.3 · p. 22
• A warm-start time t0 is chosen to meet conditions determined by an arbitrary ϵ in (0, 1).Source: §C.3 · p. 22