Techniques are provided for optimizing a program operation in a memory device to compensate for program speed variations due to block oxide thinning. In one approach, during a program operation, a program voltage which indicates program speed is acquired from sub-blocks with the highest and lowest program speeds. An initial program voltage for intermediate sub-blocks can be determined based on the acquired program voltages and the positions of the intermediate sub-blocks. The technique can accommodate a loss of one or both acquired program voltages if the programming is interrupted. In another approach, a program voltage which indicates program speed is acquired from one sub-block, and for a later-programmed sub-block, an appropriate offset is located from a table and summed with the acquired program voltage to determine an optimum initial program voltage.