1. A method for operating a non-volatile storage system, comprising: applying voltage pulses to a substrate of a set of non-volatile storage elements in each erase operation of a plurality of erase operations over a first portion of a lifetime of the set of non-volatile storage elements, each erase operation over the first portion of the lifetime uses a first value for an erase-verify level; based on the applying, determining when a condition is met for adjusting the erase-verify level; and when the condition is met for adjusting the erase-verify level, using a second value, higher than the first value, for the erase-verify level in place of the first value in each erase operation of a plurality of erase operations over a second portion of the lifetime; the set of non-volatile storage elements include multi-level storage elements which are programmed to at least first, second and third programmed states using respective program-verify levels; in the second portion of the lifetime: at least two of the respective program-verify levels are incremented, by different amounts, relative to the first portion of the lifetime.