New Math Method Slashes the Data AI Needs to Learn
Less data, same results — this could make AI training far cheaper.
A new arXiv paper analyzes a stochastic inertial Krasnosel'skii–Mann (iKM) method for finding a fixed point of a nonexpansive operator in a real Hilbert space. The method is made by adding two inertial extrapolations to stochastic KM [Bravo and Cominetti, 2024], and it retains one call to a possibly biased stochastic oracle per update.
With the authors' proposed parameter schedule, they prove a last-iterate fixed-point residual bound of O(1/K + σ log K / √K + B_K log K / K), where K is the horizon, σ is the noise level, and B_K is the accumulated root-mean-square bias. When B_K = O(√K), this yields Õ(ε⁻²) sample complexity, which matches — up to a logarithmic factor — the stochastic-oracle lower bound given under the unbiased subclass of the model [Foster et al., 2019, Theorem 2], and improves the best-known O(ε⁻⁴) random-iterate guarantee for stochastic KM [Bravo and Cominetti, 2024, Corollary 5.4].
The authors state that to their knowledge this is the first single-loop method for general nonexpansive fixed-point problems to attain this near-optimal sample complexity without variance reduction or batching. When the oracle is exact, the same method attains the worst-case-optimal O(K⁻¹) last-iterate residual rate [Park and Ryu, 2022, Theorem 4.6], improving the O(K⁻¹ᐟ²) rate of classical KM [Cominetti et al., 2014; Bravo and Cominetti, 2018].
- A new math recipe lets computers reach accurate answers using far fewer examples — close to the theoretical minimum.
- The team claims a big jump over the previous best method: for ten times more accuracy, old methods needed about 10,000 times more data; this one needs about 100 times.
- No app or code exists yet — this is a proof, so real-world savings will take years of engineering.
Why It Matters
Cheaper, faster AI training could lower costs for everyday apps — and mean less of your data is needed.