In many machine learning tasks, high accuracy requires training on a lot of data, adding more expressive features and/or exploring complex input and output structures, often resulting in scalability problems. Nevertheless, we observe that by carefully selecting and caching samples, structures, or latent items, we can reduce the problem size and improve the training speed and eventually improve performance. Based on this observation, we develop efficient algorithms for learning structured prediction models and online clustering models. We show that our selective algorithms and caching techniques are able to learn expressive models from large amounts of annotated data and achieve state-of-the art performance on several natural language processing tasks.