JuliaDiff / JuliaDiff/FiniteDiff.jl

Forward difference gradient has the same number of function calls as central difference

Open
#132 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Julia
Stars
304
Forks
42
Avg merge
24m
Merged PRs (30d)
2

Description

Changes to gradients.jl made in fc5a08e removed any way to reduce the number of function calls made when using forward difference for gradients as compared to central difference. The finite_difference_gradient! functions assume that f(x) will be provided in the GradientCache for forward differences, but the only constructor for GradientCache forces fx = nothing.

Here are the lines returning the only cache the constructor will give you:
https://github.com/JuliaDiff/FiniteDiff.jl/blob/9945e7d7f567dc2eb6a95a714b1de9782d0ecea4/src/gradients.jl#L52-L53

I can think of three ways to fix it:

  1. There could be a constructor that accepts an input of fx returns the a cache with fx, although fc5a08e was trying to get rid of extra constructors.
  2. Instead of using the type Nothing for the first parameter of the returned GradientCache, use Union{Nothing,returntype} so the user can manually update it later.
  3. Or, don't bother using the cache and change the following line
    https://github.com/JuliaDiff/FiniteDiff.jl/blob/9945e7d7f567dc2eb6a95a714b1de9782d0ecea4/src/gradients.jl#L138
    to _fx, c1, c2, c3 = cache.fx, cache.c1, cache.c2, cache.c3 and then before this for loop:
    https://github.com/JuliaDiff/FiniteDiff.jl/blob/9945e7d7f567dc2eb6a95a714b1de9782d0ecea4/src/gradients.jl#L144-L145
    add something along the lines of fx = _fx == Nothing ? f(x) : _fx

2 makes the most sense to me, but I'm not sure what the performance implications are.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in src/gradients.jl at the GradientCache constructor and the finite_difference_gradient! code around lines 138 and 144-145. Trace how fx is supplied for forward differences and compare the function-call behavior with central differences. Done means forward differences can reuse f(x) through the cache and require fewer function calls, with the performance implications of the chosen approach understood.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.