We consider the problem of constrained M-estimation when both explanatory and response variables have heavy tails (bounded 4-th moments), or a fraction of arbitrary corruptions. We focus on the high-dimensional regime where the underlying parameter has a low-dimensional constraint, such as sparsity or low rankness. Modeling with sparsity of low rank constraint in high dimensions is NP-hard in the worst case. Thus theoretical recovery guarantees for most computationally tractable approaches rely on strong assumptions on the probabilistic models of the data, such as sub-Gaussianity. Under such assumptions, existing approaches achieve the minimax optimal recovery guarantees. But heavy-tails and arbitrary corruptions in the data violate the assumptions required for convergence of the usual algorithms. This thesis tackles these challenges for a few statistical learning problems: robust sparse regression, robust Gaussian graphical model estimation and robust low rank matrix recovery. We provide a novel robust gradient descent approach for these problems in a high dimensional regime and we present optimal statistical guarantees and computational efficient algorithms under the heavy-tails and arbitrary corruptions. We demonstrate the effectiveness of our approach in sparse linear, logistic regression, sparse precision matrix estimation and low rank matrix recovery on synthetic and real-world data.