Randomized Forward Mode of Automatic Differentiation For Optimization Algorithms

Khemraj Shukla, Yeonjong Shin
10/22/2023
math.OCcs.AIcs.LG

Official code: Astuary/Spry (13 stars, last commit 2024-10-08).

Abstract

We present a randomized forward mode gradient (RFG) as an alternative to backpropagation. RFG is a random estimator for the gradient that is constructed based on the directional derivative along a random vector. The forward mode automatic differentiation (AD) provides an efficient computation of RFG. The probability distribution of the random vector determines the statistical properties of RFG. Through the second moment analysis, we found that the distribution with the smallest kurtosis yields the smallest expected relative squared error. By replacing gradient with RFG, a class of RFG-based optimization algorithms is obtained. By focusing on gradient descent (GD) and Polyak's heavy ball (PHB) methods, we present a convergence analysis of RFG-based optimization algorithms for quadratic functions. Computational experiments are presented to demonstrate the performance of the proposed algorithms and verify the theoretical findings.

View on arXivView PDF

Code Implementations(1)

Astuary/SpryOfficial100%

Code for "Thinking Forward: Memory-Efficient Federated Finetuning of Language Models" (NeurIPS 2024). Spry is a federated learning algorithm that enables finetuning LLMs using Forward-mode Auto Differentiation; to achieve low memory footprint, high accuracy, and fast convergence.

131Shell, PythonMay 24, 20242 years ago

Similar Papers

Beyond Backpropagation: Optimization with Multi-Tangent Forward Gradients

81% match1 repo62024

LPGD: A General Framework for Backpropagation through Embedded Optimization Layers

80% match1 repo32024

Can Forward Gradient Match Backpropagation?

80% match2 repos132023

Second-Order Forward-Mode Automatic Differentiation for Optimization

80% match1 repo42024

Gradient Estimation and Variance Reduction in Stochastic and Deterministic Models

79% match2024

Efficient Sampling for Data-Driven Frequency Stability Constraint via Forward-Mode Automatic Differentiation

78% match1 repo62024

Cite this paper

@article{shukla2023randomized,
  title  = {Randomized Forward Mode of Automatic Differentiation For Optimization Algorithms},
  author = {Khemraj Shukla and Yeonjong Shin},
  year   = {2023},
  eprint = {2310.14168},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2310.14168v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2310.14168.svg)](https://codeofpaper.com/paper/2310.14168)

Discussion