Regularized regression problems are ubiquitous in statistical modeling,signal processing, and machine learning. Sparse regression in particular hasbeen instrumental in scientific model discovery, including compressed sensingapplications, variable selection, and high-dimensional analysis. We propose abroad framework for sparse relaxed regularized regression, called SR3. The keyidea is to solve a relaxation of the regularized problem, which has threeadvantages over the state-of-the-art: (1) solutions of the relaxed problem aresuperior with respect to errors, false positives, and conditioning, (2)relaxation allows extremely fast algorithms for both convex and nonconvexformulations, and (3) the methods apply to composite regularizers such as totalvariation (TV) and its nonconvex variants. We demonstrate the advantages of SR3(computational efficiency, higher accuracy, faster convergence rates, greaterflexibility) across a range of regularized regression problems with syntheticand real data, including applications in compressed sensing, LASSO, matrixcompletion, TV regularization, and group sparsity. To promote reproducibleresearch, we also provide a companion MATLAB package that implements theseexamples.