Consider the class of learning schemes which is composed of a sum of losses over every data point and a regularizer that imposes special structures on the model parameter and controls the model complexity. A tuning parameter, typically adjusting the amount of regularization, is necessary for this framework to work well. Finding the optimal tuning is a challenging problem in high-dimensional regimes where both the sample size and the dimension of the parameter space are large. We propose two frameworks to obtain a computationally efficient approximation of the leave-one-out cross validation (LOOCV) risk for nonsmooth losses and regularizers. Our two frameworks are based on the primal and dual formulations of the aforementioned learning scheme. We then prove the equivalence of the two approaches under smoothness conditions. This equivalence enables us to justify the accuracy of both methods under such conditions. Finally we apply our approaches to several standard problems, including generalized LASSO and support vector machines, and empirically demonstrate the effectiveness of our results.