Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation

Abstract

Many machine learning approaches are characterized by information constraints on how they interact with the training data. These include memory and sequential access constraints (e.g. fast first-order methods to solve stochastic optimization problems); communication constraints (e.g. distributed learning); partial access to the underlying data (e.g. missing features and multi-armed bandits) and more. However, currently we have little understanding how such information constraints fundamentally affect our performance, independent of the learning problem semantics. For example, are there learning problems where any algorithm which has small memory footprint (or can use any bounded number of bits from each example, or has certain communication constraints) will perform worse than what is possible without such constraints? In this paper, we describe how a single set of results implies positive answers to the above, for several different settings.

Full version of NIPS 2014 paper

References in corpus (4)

• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• The on-line shortest path problem under partial monitoring
• Efficient Learning with Partially Observed Attributes
• Stochastic Optimization of PCA with Capped MSG

Cited by in corpus (21)

• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Communication Complexity of Distributed Convex Learning and Optimization
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Deep learning with Elastic Averaging SGD
• On-Device Machine Learning: An Algorithms and Learning Theory Perspective
• Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
• Distributed Simulation and Distributed Inference
• Distributed Nonparametric Regression under Communication Constraints
• On the Randomized Complexity of Minimizing a Convex Quadratic Function
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning
• Efficient Communications in Training Large Scale Neural Networks
• A General Memory-Bounded Learning Algorithm
• Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
• Information Theoretically Secure Databases
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Towards Tight Communication Lower Bounds for Distributed Optimisation
• Distributed stochastic optimization for deep learning (thesis)
• Distributed Learning of Average Belief Over Networks Using Sequential Observations
• Online Optimization for Large-Scale Max-Norm Regularization