Due to its simplicity the adaptive Least Mean Square (LMS) algorithm is widely used in Code-Division Multiple access (CDMA) detectors. However its convergence speed is highly dependent on the eigen value spread of the input covariance matrix. For highly correlated inputs the LMS algorithm has a slow convergence which require long training sequences and therefore low transmission speeds. Another drawback of the LMS is the trade-off between convergence speed and steady-state error since both are controlled by the same parameter, the step-size. In order to eliminate these drawbacks, the class of Variable Step-Size LMS (VSSLMS) algorithms was introduced. In this paper, we study the behavior of some algorithms belonging to the class of VSSLMS for training based multiuser detection in a CDMA system. We show that the proposed Complementary Pair Variable Step-Size LMS algorithms highly increase the speed of convergence while reducing the trade-off between the convergence speed and the output error.