Stochastic, Distributed and Federated Optimization for Machine Learning

Abstract

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.

PhD thesis

References in corpus (47)

• Deep Learning with Differential Privacy
• Federated Learning: Strategies for Improving Communication Efficiency
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Revisiting Distributed Synchronous SGD
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Optimal Distributed Online Prediction using Mini-Batches
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Stochastic Variance Reduction for Nonconvex Optimization
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Distributed Coordinate Descent Method for Learning with Big Data
• Practical Secure Aggregation for Federated Learning on User-Held Data
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• AIDE: Fast and Communication Efficient Distributed Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Why Random Reshuffling Beats Stochastic Gradient Descent
• SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• A Simple Practical Accelerated Method for Finite Sums
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Tight Complexity Bounds for Optimizing Composite Objectives
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Asynchronous stochastic convex optimization
• SDCA without Duality
• Distributed Mini-Batch SDCA
• Randomized Block Coordinate Descent for Online and Stochastic Optimization
• Importance Sampling for Minibatches
• LOCO: Distributing Ridge Regression with Random Projections
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Privacy Preserving Randomized Gossip Algorithms
• Analysis of Distributed Stochastic Dual Coordinate Ascent
• Simple Complexity Analysis of Simplified Direct Search
• Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms
• L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• ASAGA: Asynchronous Parallel SAGA
• Parallel coordinate descent methods for composite minimization: convergence analysis and error bounds
• Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
• Randomized Distributed Mean Estimation: Accuracy vs Communication
• Coordinate Descent Face-Off: Primal or Dual?
• Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
• Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization?
• An efficient distributed learning algorithm based on effective local functional approximations
• On Randomized Distributed Coordinate Descent with Quantized Updates

Cited by in corpus (5)

• On the Convergence of FedAvg on Non-IID Data
• Edge Intelligence: Architectures, Challenges, and Applications
• Communication-Efficient Local Decentralized SGD Methods
• Deploying Federated Learning in Large-Scale Cellular Networks: Spatial Convergence Analysis
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications