Richtarik, Peter

Gondzio, Jacek

Konečný, Jakub

other

2018-08-23T11:14:21Z

2018-08-23T11:14:21Z

2017-11-30

We study optimization algorithms for the finite sum problems frequently arising in machine learning applications. First, we propose novel variants of stochastic gradient descent with a variance reduction property that enables linear convergence for strongly convex objectives. Second, we study distributed setting, in which the data describing the optimization problem does not fit into a single computing node. In this case, traditional methods are inefficient, as the communication costs inherent in distributed optimization become the bottleneck. We propose a communication-efficient framework which iteratively forms local subproblems that can be solved with arbitrary local optimization algorithms. Finally, we introduce the concept of Federated Optimization/Learning, where we try to solve the machine learning problems without having data stored in any centralized manner. The main motivation comes from industry when handling user-generated data. The current prevalent practice is that companies collect vast amounts of user data and store them in datacenters. An alternative we propose is not to collect the data in first place, and instead occasionally use the computational power of users' devices to solve the very same optimization problems, while alleviating privacy concerns at the same time. In such setting, minimization of communication rounds is the primary goal, and we demonstrate that solving the optimization problems in such circumstances is conceptually tractable.

http://hdl.handle.net/1842/31478

en

The University of Edinburgh

Jakub Konecny and Peter Richtarik: "Semi-stochastic gradient descent methods." arXiv preprint 1312.1666 (2013).

Jakub Konecny, Zheng Qu and Peter Richtarik: "Semi-stochastic coordinate descent." Optimization Methods and Software, 1-13 (2017).

Jakub Konecny, Jie Liu, Peter Richtarik and Martin Takac: "Mini-batch semi-stochastic gradient descent in the proximal setting." IEEE Journal of Selected Topics in Signal Processing 10(2), 242-255 (2016).

Chenxin Ma, Jakub Konecny, Martin Jaggi, Virginia Smith, Michael I Jordan, Peter Richtarik and Martin Takac: "Distributed optimization with arbitrary local solvers." Optimization Methods and Software, 1-36 (2017).

Jakub Konecny, Brendan McMahan, Daniel Ramage and Peter Richtarik: "Federated optimization: distributed machine learning for on-device intelligence." arXiv preprint 1610.02527 (2016).

Jakub Konecny and Peter Richtarik: "Randomized Distributed Mean Estimation: Accuracy vs Communication." arXiv preprint 1611.07555 (2016).

Jakub Konecny, Brendan McMahan, Felix Yu, Peter Richtarik, Ananda Theertha Suresh and Dave Bacon: "Federated learning: Strategies for improving communication efficiency." arXiv preprint 1610.05492 (2016)

Reza Harikandeh, Mohamed Osama Ahmed, Alim Virani, Mark Schmidt, Jakub Konecny and Scott Sallinen: "Stop wasting my gradients: Practical SVRG." Advances in Neural Information Processing Systems 28, 2251-2259 (2015).

Sashank J Reddi, Jakub Konecny, Peter Richtarik, Barnabas Poczos and Alex Smola "AIDE: Fast and communication efficient distributed optimization." arXiv preprint 1608.06879 (2016).

Filip Hanzely, Jakub Konecny, Nicolas Loizou, Peter Richtarik, Dmitry Grishchenko:. Privacy Preserving Randomized Gossip Algorithms. arXiv preprint arXiv:1706.07636. (2017)

Jakub Konecny and Peter Richtarik. "Simple complexity analysis of simplified direct search." arXiv preprint 1410.0390 (2014)

stochastic gradient descent

distributed setting

optimization problem

minimization of communication rounds

Stochastic, distributed and federated optimization for machine learning

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy