In this paper we propose novel computationally efficient schemas for a large class of on-line adaptive algorithms with variable self-adaptive learning rates. The learning rate is adjusted automatically providing relatively fast convergence at early stages of adaptation while ensuring small final misadjustment for cases of stationary environments. For non-stationary environments, the algorithms proposed have good tracking ability and quick adaptation to new conditions. Their validity and efficiency are illustrated for a nonstationary blind separation problem.