Derivative-free - or zeroth-order - optimization (DFO) has gained recent\nattention for its ability to solve problems in a variety of application areas,\nincluding machine learning, particularly involving objectives which are\nstochastic and/or expensive to compute. In this work, we develop a novel\nmodel-based DFO method for solving nonlinear least-squares problems. We improve\non state-of-the-art DFO by performing dimensionality reduction in the\nobservational space using sketching methods, avoiding the construction of a\nfull local model. Our approach has a per-iteration computational cost which is\nlinear in problem dimension in a big data regime, and numerical evidence\ndemonstrates that, compared to existing software, it has dramatically improved\nruntime performance on overdetermined least-squares problems.\n