Using the Chebyshev polynomials, we first give the bounds on the conjugate gradient iterates’ error in bounds on the spectrum of the SPD Hessian of the cost function. Then, we present two methods of improving the rate of convergence of conjugate gradients, in particular, preconditioning using specific information about the problem and preconditioning by the conjugate projector. The latter method does not transform variables so that it can be applied to problems with separable constraints. Finally, we present the algorithm cgSLS for solving the least square problems with symmetric positive semidefinite Hessian. We validate the theory by numerical experiments.