We are very excited to join forces with MLCommons and OctoML.ai! Contact Grigori Fursin for more details!

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

lib:87184dc88254090a (v1.0.0)

Authors: Ohad Shamir
Where published: NeurIPS 2014 12
ArXiv: 1311.3494
Document:  PDF  DOI 
Abstract URL: http://arxiv.org/abs/1311.3494v6


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.

Relevant initiatives  

Related knowledge about this paper Reproduced results (crowd-benchmarking and competitions) Artifact and reproducibility checklists Common formats for research projects and shared artifacts Reproducibility initiatives

Comments  

Please log in to add your comments!
If you notice any inapropriate content that should not be here, please report us as soon as possible and we will try to remove it within 48 hours!