Nonuniform sampling (NUS) of multidimensional NMR data offers significant time savings while improving spectral resolution or increasing sensitivity per unit time. However, NUS has not been widely used for quantitative analysis because of the nonlinearity of most methods used to model NUS data, which leads to problems in estimating signal intensities, relaxation rate constants, and their error bounds. Here, we present an approach that avoids these limitations by combining accordion spectroscopy and NUS in the indirect dimensions of multidimensional spectra and then applying sparse exponential mode analysis, which is well suited for analyzing accordion-type relaxation data in a NUS context. By evaluating the Cramer-Rao lower bound of the variances of the estimated relaxation rate constants, we achieve a robust benchmark for the underlying reconstruction model. Furthermore, we design NUS schemes optimized with respect to the information theoretical lower bound of the error in the parameters of interest, given a specified number of sampling points. The accordion-NUS method compares favorably with conventional relaxation experiments in that it produces identical results, within error, while shortening the length of the experiment by an order of magnitude. Thus, our approach enables rapid acquisition of NMR relaxation data for optimized use of spectrometer time or accurate measurements on samples of limited lifetime.