Scientists are increasingly leveraging modern computational methods for the analysis of experimental data and the design of new experiments in order to enable and accelerate scientific progress. Particularly valuable to scientific research are sparse, interpretable models, uncertainty quantification, and the minimization of the number of experiments that are required to achieve a scientific end. The fields of sparse and Bayesian optimization (BO) constitute a highly suitable basis for tackling these scientific problems and, despite considerable prior work, contain many questions that require further inquiry: Can we design algorithms that can outperform existing ones on key problems? What are the precise conditions under which an algorithm can determine a sparse model from little data? How can machines best design scientific experiments to minimize their cost? This thesis puts forth algorithmic and theoretical advances that aim to answer these questions. Part I provides an overview of the main contributions of this thesis. In Part II, we develop novel theoretical insights on sparsity-promoting algorithms and propose per- formant new algorithms. In Part III, we propose exact methods that reduce the complexity of a critical step in first-order BO from quadratic to linear in the dimensionality of the input. In Part IV, we focus on applications in scientific discovery, a highlight being the Scientific Autonomous Reasoning Agent (SARA), which was deployed at the Cornell High-Energy Synchrotron Source (CHESS) and the Stanford Linear Accelerator Center (SLAC), accelerating the acquisition of relevant scientific data for materials discovery by orders of magnitude. We conclude with future research directions in Part V.