Smart Gradient

More accurate numerical gradients, by remembering where you came from.

The problem: numerical gradients are noisy

Many optimization methods, including Newton's method, quasi-Newton (BFGS, L-BFGS), and trust-region, assume you can compute the gradient ∇f(x). When no analytical gradient is available, we approximate it with finite differences:

This works in theory, but in floating-point arithmetic it's a tightrope walk:

And it gets worse inside an iterative optimizer: every step uses a fresh, noisy gradient. Errors compound. The optimizer can stall, oscillate, or report convergence at a point that isn't quite a minimum.

The idea: rotate your basis toward where the action is

The standard finite difference probes along the canonical axes e₁, e₂, …, e_n. But during optimization, the function isn't equally sensitive in every direction. It changes a lot along the directions you've been descending in, and much less along the rest.

Smart Gradient exploits this. At iteration k it builds an orthonormal basis from the recent descent directions d_k−1, d_k−2, …, d_k−m (limited-memory: keep only the last m), completes it with axis directions, and finite-differences in that basis. Then it rotates the resulting gradient back to the original coordinates.

Why this reduces noise

Finite-difference error has two parts: truncation (proportional to h) and round-off (proportional to ε_mach/h, where ε_mach is machine precision). What dominates the relative error is how much the function actually changes over the probe:

Along a recent descent direction, |Δf| is large by construction: the optimizer moved in that direction because the function was decreasing fast there. Along a generic axis, |Δf| can be tiny, so the round-off term blows up. Smart Gradient buys you bigger |Δf| for free: same h, same number of function evaluations, but the signal-to-noise ratio improves.

Algorithm sketch

At each iteration k:

1. 1Take the last m descent directions d_k−1, …, d_k−m; orthonormalize them (e.g., Gram–Schmidt) to get q₁, …, q_m.
2. 2Complete to an orthonormal basis Q = [q₁, …, q_n] by adding axis directions.
3. 3Compute finite differences of f along each column of Q; this gives the gradient in the rotated basis, ∇̃f.
4. 4Rotate back: ∇f ≈ Q ∇̃f. Pass to the optimizer as usual.

When does Smart Gradient help most?

• Ill-conditioned problems: long, narrow valleys (think Rosenbrock-style functions) where axis-aligned probes are nearly perpendicular to the descent direction.
• Expensive black-box objectives, like likelihoods from simulators or hyperparameter losses, where you can't reduce h indefinitely because evaluations are costly or noisy.
• Quasi-Newton methods that rely on accurate gradient differences: BFGS and L-BFGS use successive gradients to build curvature estimates, so cleaner gradients mean better curvature.

It is most useful when the analytical gradient is unavailable or hard to maintain (legacy code, complex simulators) but optimization is still being done seriously.

Try it in R

Installation

library("devtools")
install_github("esmail-abdulfattah/Smart-Gradient", subdir = "smartGrad")

1. Define your objective

Here we use the Extended Rosenbrock function, a classic ill-conditioned test case where the minimum sits at the bottom of a curved, narrow valley:

myfun <- function(x) {
  res <- 0.0
  for (i in 1:(length(x) - 1))
    res <- res + 100 * (x[i+1] - x[i]^2)^2 + (1 - x[i])^2
  return(res)
}

2. Provide a standard finite-difference gradient

mygrad <- function(fun, x) {
  h <- 1e-3
  grad <- numeric(length(x))
  for (i in 1:length(x)) {
    e <- numeric(length(x)); e[i] <- 1
    grad[i] <- (fun(x + h*e) - fun(x - h*e)) / (2*h)
  }
  return(grad)
}

3. Wrap it with makeSmart() and optimize

library("stats")
library("smartGrad")

x_initial <- rnorm(5)
result <- optim(
  par    = x_initial,
  fn     = myfun,
  gr     = makeSmart(fn = myfun, gr = mygrad),
  method = "BFGS"
)

That's it. makeSmart() takes your existing numerical gradient and returns a drop-in replacement that maintains the rotated basis internally. The optimizer doesn't need to know anything has changed.

Links & references

• 📦 Code: esmail-abdulfattah/Smart-Gradient (R, C++ header-only, and Python implementations).
• 📄 Paper: Published in Foundations of Data Science (FoDS).

← Back to main site