Provably Efficient Methods For Large-Scale Learning