Almost sure mixing rates for non-uniformly expanding maps

We consider random perturbations of non-uniformly expanding maps, possibly having a non-degenerate critical set. We prove that, if the Lebesgue measure of the set of points failing the non-uniform expansion or the slow recurrence to the critical set at a certain time, for almost all random orbits, decays in a (stretched) exponential fashion, then the decay of correlations along random orbits is stretched exponential, up to some waiting time. As applications, we obtain almost sure stretched exponential decay of random correlations for Viana maps, as for a class of non-uniformly expanding local diffeomorphisms and a quadratic family of interval maps.