In Digital Subscriber Line (DSL) systems, the noise perceived by a DSL line fluctuates when DSL lines sharing the same bundle are switched on/off. The concept of Seamless Rate Adaptation (SRA) was introduced to seamlessly adapt the data rate of a connection to the changing channel while in operation without any service interruption. Interleavers in communication paths impose a constraint on the amount of data rate that can be changed by an SRA procedure. In the case of large changes in the channel, multiple consecutive SRA procedures have to be executed. Moreover, to keep an equal signal-to-noise-ratio margin over all tones, it is very likely that the bit loadings of all tones have to be modified in each SRA procedure. Hence, the state of the art SRA is too slow and provides means of adaptation only to slowly changing channels and will not prevent reinitializations under certain conditions such as large rapid changes in noise. In this paper, we optimize the rate adaptation procedure in terms of adaptation time and average bit error rate. We present an algorithm that solves the stated problem optimally and a sub-optimal low complex algorithm that can be used in practice by modems with limited computing power. Both algorithms lead to significant gains in terms of adaptation time and average bit error rate.