  We show that two polynomial time methods, a Lasso estimator with adaptively
chosen tuning parameter and a Slope estimator, adaptively achieve the exact
minimax prediction and $\ell_2$ estimation rate $(s/n)\log (p/s)$ in
high-dimensional linear regression on the class of $s$-sparse target vectors in
$\mathbb R^p$. This is done under the Restricted Eigenvalue (RE) condition for
the Lasso and under a slightly more constraining assumption on the design for
the Slope. The main results have the form of sharp oracle inequalities
accounting for the model misspecification error. The minimax optimal bounds are
also obtained for the $\ell_q$ estimation errors with $1\le q\le 2$ when the
model is well-specified. The results are non-asymptotic, and hold both in
probability and in expectation. The assumptions that we impose on the design
are satisfied with high probability for a large class of random matrices with
independent and possibly anisotropically distributed rows. We give a
comparative analysis of conditions, under which oracle bounds for the Lasso and
Slope estimators can be obtained. In particular, we show that several known
conditions, such as the RE condition and the sparse eigenvalue condition are
equivalent if the $\ell_2$-norms of regressors are uniformly bounded.
