Hybrid Deterministic-Stochastic Methods for Data Fitting

Abstract

Many structured data-fitting applications require the solution of an optimization problem involving a sum over a potentially large number of measurements. Incremental gradient algorithms offer inexpensive iterations by sampling a subset of the terms in the sum. These methods can make great progress initially, but often slow as they approach a solution. In contrast, full-gradient methods achieve steady convergence at the expense of evaluating the full objective and gradient on each iteration. We explore hybrid methods that exhibit the benefits of both approaches. Rate-of-convergence analysis shows that by controlling the sample size in an incremental gradient algorithm, it is possible to maintain the steady convergence rates of full-gradient methods. We detail a practical quasi-Newton implementation based on this approach. Numerical experiments illustrate its potential benefits.

26 pages. Revised proofs of Theorems 2.6 and 3.1, results unchanged

Cited by in corpus (23)

• Federated Learning via Intelligent Reflecting Surface
• Multi-Stage Hybrid Federated Learning over Large-Scale D2D-Enabled Fog Networks
• Online Learning with Inexact Proximal Online Gradient Descent Algorithms
• Interference Management for Over-the-Air Federated Learning in Multi-Cell Wireless Networks
• Joint Optimization of Communications and Federated Learning Over the Air
• Edge Federated Learning Via Unit-Modulus Over-The-Air Computation
• Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits
• Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling
• Generalized Row-Action Methods for Tomographic Imaging
• Vocabulary-informed Zero-shot and Open-set Learning
• Semi-Federated Learning: Convergence Analysis and Optimization of A Hybrid Learning Framework
• Distributed Gradient Methods with Variable Number of Working Nodes
• Automatic alignment for three-dimensional tomographic reconstruction
• A new convergence analysis and perturbation resilience of some accelerated proximal forward-backward algorithms with errors
• Beyond backpropagation: bilevel optimization through implicit differentiation and equilibrium propagation
• CoolMomentum: A Method for Stochastic Optimization by Langevin Dynamics with Simulated Annealing
• Adaptive sampling strategies for risk-averse stochastic optimization with constraints
• Projected nonlinear least squares for exponential fitting
• Federated Optimization of Smooth Loss Functions
• Beamforming and Device Selection Design in Federated Learning with Over-the-air Aggregation
• Stochastic Relaxed Inertial Forward-Backward-Forward splitting for Monotone Inclusions in Hilbert spaces
• Stochastic ADMM with batch size adaptation for nonconvex nonsmooth optimization
• Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions