In this paper, we propose an optimal adaptive FIR filter, in which the step-size and error nonlinearity are simultaneously optimized to maximize the decrease of the mean square deviation (MSD) of the weight error vector at each iteration. The optimal step-size and error nonlinearity are derived, and a variable step-size stochastic information gradient (VS-SIG) algorithm is developed to approximately implement the optimal adaptation. Simulation results indicate that this new algorithm achieves faster convergence rate and lower misadjustment error in comparison with other adaptive algorithms.