MISO is Making a Comeback With Better Proofs and Rates

Understand

MISO, also known as Finito, was one of the first stochastic variance reduced methods discovered, yet its popularity is fairly low.

• Its initial analysis was significantly limited by the so-called Big Data assumption.
• Although the assumption was lifted in subsequent work using negative momentum, this introduced a new parameter and required knowledge of strong convexity and smoothness constants, which is rarely possible in practice.
• We rehabilitate the method by introducing a new variant that needs only smoothness constant and does not have any extra parameters.