Minimizing Finite Sums with the Stochastic Average Gradient: SAG with Step 1/(16L) Has E[g(x̄ᵏ)] − g(x*) ≤ (32n/k)C₀, and Rate (1 − min{μ/(16L), 1/(8n)})ᵏC₀ if g Is μ-Strongly ConvexResearch Paper
Many problems in statistics and machine learning minimize a finite sum: an average of smooth convex losses, one per data point, often plus a strongly convex regularizer. The full gradient method costs component gradients per iteration and converges at rate , or linearly when the objective is strongly convex (Nesterov, 2004). The stochastic…