We develop two new methods for selecting the penalty parameter for the `1-penalized high-dimensional M-estimator, which we refer to as the analytic and bootstrap-aftercross-validation methods. For both methods, we derive nonasymptotic error bounds for the corresponding `1-penalized M-estimator and show that the bounds converge to zero under mild conditions, thus providing a theoretical justification for these methods. We demonstrate via simulations that the finite-sample performance of our methods is much better than that of previously available and theoretically justified methods.