Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters

Abstract

Many key problems in machine learning and data science are routinely modeled as optimization problems and solved via optimization algorithms. With the increase of the volume of data and the size and complexity of the statistical models used to formulate these often ill-conditioned optimization tasks, there is a need for new efficient algorithms able to cope with these challenges. In this thesis, we deal with each of these sources of difficulty in a different way. To efficiently address the big data issue, we develop new methods which in each iteration examine a small random subset of the training data only. To handle the big model issue, we develop methods which in each iteration update a random subset of the model parameters only. Finally, to deal with ill-conditioned problems, we devise methods that incorporate either higher-order information or Nesterov's acceleration/momentum. In all cases, randomness is viewed as a powerful algorithmic tool that we tune, both in theory and in experiments, to achieve the best results. Our algorithms have their primary application in training supervised machine learning models via regularized empirical risk minimization, which is the dominant paradigm for training such models. However, due to their generality, our methods can be applied in many other fields, including but not limited to data science, engineering, scientific computing, and statistics.

PhD thesis, 425 pages, 75 figures

References in corpus (53)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Learning with Non-IID Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Federated Learning of a Mixture of Global and Local Models
• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
• Distributed Coordinate Descent Method for Learning with Big Data
• A Universal Catalyst for First-Order Optimization
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Global Convergence of Online Limited Memory BFGS
• Scaling Distributed Machine Learning with In-Network Aggregation
• Variational Federated Multi-Task Learning
• Optimization with First-Order Surrogate Functions
• AIDE: Fast and Communication Efficient Distributed Optimization
• Distributed Learning with Compressed Gradient Differences
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Variance Reduced Local SGD with Lower Communication Complexity
• Proximal Stochastic Dual Coordinate Ascent
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• First Analysis of Local GD on Heterogeneous Data
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• Stochastic Dual Ascent for Solving Linear Systems
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Direct Acceleration of SAGA using Sampled Negative Momentum
• Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
• Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method
• Linearly convergent stochastic heavy ball method for minimizing generalization error
• Nonconvex Variance Reduced Optimization with Arbitrary Sampling
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
• ASVRG: Accelerated Proximal SVRG
• Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization
• Semi-Cyclic Stochastic Gradient Descent
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Linearly Convergent Randomized Iterative Methods for Computing the Pseudoinverse
• Simple Complexity Analysis of Simplified Direct Search
• Approximate Steepest Coordinate Descent
• L-SVRG and L-Katyusha with Arbitrary Sampling
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
• Efficient Greedy Coordinate Descent for Composite Problems
• Stochastic Subspace Descent
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• Coordinate Descent Face-Off: Primal or Dual?