Random Reshuffling Quadratic — Quadratic Finite-Sum Minimization
Descriptions may be stale. Consult the linked Lean sources.
Quadratic Finite-Sum Minimization · Lean proof
Quadratic Finite-Sum Minimization
We consider minimizing
Write the component objectives and their average as
Our assumptions:
Assumption 1 (Component curvature and strong
convexity). For every
Assumption 2 (Initial distance and component
gradients). There exists
At any selected index
Proved result
OracleTemplate.Convergence LongTails.Setups.QuadraticFiniteSum.spec OracleTemplate.QuadraticFiniteSum.budgetRelevant previous results
- B. T. Polyak. Some methods of
speeding up the convergence of iteration methods. 1964. Complexity:
exact component-gradient calls using the full-gradient method for objective gap at most , counting component calls per iteration; . - James W. Daniel. The
Conjugate Gradient Method for Linear and Nonlinear Operator
Equations. 1967. Complexity:
exact component-gradient calls using conjugate gradients for objective gap at most , including initialization and component queries implementing operator products; .