Abstract: In Semi-Private (SP) learning, the learner has access to both public and private data, and the differential privacy requirement is imposed solely on the private data. We propose a computationally efficient algorithm that, under mild assumptions on the data, provably achieves significantly lower sample complexity and can be efficiently run on realistic datasets. To achieve this, we leverage the features extracted by pre-trained networks. To validate its empirical effectiveness, we propose a particularly challenging set of experiments under tight privacy constraints ($\epsilon=0.1$) and with a focus on low-data regimes. In all the settings, our algorithm exhibits significantly improved performance over the available baseline.