📊 statistics

Functional Gradient Descent with Adaptive Representations

This paper introduces a novel, theoretically-grounded Functional Gradient Descent algorithm that adaptively updates the representation of functional gradients during optimization, achieving convergence guarantees and superior performance in efficiency and accuracy across regression, PDE solving, and computer vision tasks compared to existing fixed-approximation and neural network baselines.

Original authors: Daniel Csillag, Rodrigo Schuller, Pedro Dall'Antonia, Leonidas Guibas, Luiz Velho, Tiago Novello

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniel Csillag, Rodrigo Schuller, Pedro Dall'Antonia, Leonidas Guibas, Luiz Velho, Tiago Novello

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley. This valley represents a "loss function," and your goal is to get to the bottom (the global minimum) as quickly and accurately as possible.

In the world of machine learning, there are two main ways people usually try to do this:

The "Fixed Map" Approach (Neural Networks): You carry a map that is drawn on a fixed grid. No matter how detailed the terrain gets, your map only has a certain number of squares. If the valley has a tiny, deep hole that falls between your grid lines, your map can't see it. You might get stuck on a small bump because your map is too coarse, or you might take a long, winding path because the map is too rigid.
The "Perfect Vision" Approach (Ideal Functional Gradient Descent): You have a magical pair of eyes that can see the entire valley in infinite detail, instantly telling you the exact direction to step. This is theoretically perfect, but in reality, you can't store or process "infinite detail" in a computer's memory. It's like trying to carry the entire ocean in a bucket.

The Problem:
Existing methods try to use the "Perfect Vision" approach but are forced to use a "Fixed Map" to approximate it. They pick a grid size (like 32x32 or 128x128) and stick with it.

If the grid is too coarse (small), you miss the details and get stuck at a "good enough" spot, never reaching the true bottom.
If the grid is fine (large), you get the details, but the computer takes forever to calculate, or you run out of memory.

The Solution: Adaptive Representations
The authors of this paper propose a new method called Functional Gradient Descent with Adaptive Representations.

Think of this method as having a smart, shape-shifting map.

Start Coarse: You begin with a very rough, low-resolution map (a few big squares). You take a few steps. It's fast, and you get a general idea of where the valley goes.
Zoom In When Needed: As you get closer to the bottom, the map automatically detects that it's too blurry to see the tiny dips anymore. Instead of getting stuck, the map automatically refines itself. It splits the big squares into smaller ones, adding detail exactly where you need it.
The Guarantee: The paper proves mathematically that as long as you keep refining the map whenever the "blur" gets too high, you are guaranteed to eventually reach the true bottom of the valley, not just a fake one.

How It Works in Practice (The Analogy of the Sculptor)
Imagine a sculptor trying to carve a perfect statue from a block of stone.

Neural Networks are like a sculptor using a single, fixed-size chisel. If the chisel is too big, they can't carve the fine details of the eyes. If it's too small, it takes them a million years to carve the nose.
Fixed Approximation FGD is like a sculptor who picks a chisel size at the start and never changes it. They might finish the statue, but the details will always be slightly wrong because the tool didn't match the task.
This New Method is like a sculptor with a magic tool belt. They start with a heavy, broad chisel to remove the big chunks of stone quickly. As they get closer to the face, they swap to a medium chisel, and finally, when they are carving the eyelashes, they swap to a tiny, precision tool. They change tools dynamically based on what they are currently working on.

What the Paper Actually Claims
The authors tested this "magic tool" on three specific tasks:

Regression (Fitting Data): They tried to fit a curve to a set of points. Their method found a better fit (lower error) and did it faster than both the fixed-map methods and standard neural networks.
Solving Physics Equations (Wave Equation): They used it to simulate how waves move. Their method matched the "perfect" physics solution much more closely than neural networks, and it did so in a fraction of the time.
Computer Vision (3D Scenes): They tried to reconstruct a 3D scene from 2D photos (like making a 3D model from a video). Their method produced sharper, clearer images with fewer errors than the neural network baseline.

The Bottom Line
This paper introduces a way to do optimization that starts simple and gets more complex only when necessary. It combines the speed of a rough guess with the accuracy of a detailed calculation, all while mathematically guaranteeing that you won't get stuck in a "good enough" solution but will actually find the best possible one. It outperforms both the "fixed grid" methods and the standard "neural network" methods in speed and accuracy across the tasks they tested.

Technical Summary: Functional Gradient Descent with Adaptive Representations

Problem Statement

Functional optimization problems, central to machine learning, statistics, and scientific computing, involve minimizing a loss functional $L(f)$ over a function space $\mathcal{H}$ (e.g., a Hilbert space). The standard approach represents the target function $f$ using a fixed parametric model, such as a neural network, and optimizes the network weights via gradient descent. This approach introduces three primary challenges:

Non-convexity: The resulting optimization landscape is highly non-convex, complicating training and theoretical analysis.
Fixed Representation: The representation is typically fixed a priori, limiting the model's ability to adapt its complexity during optimization.
Theoretical Limitations: The non-convex nature of parametrized losses hinders rigorous convergence guarantees.

An alternative is Functional Gradient Descent (FGD), which performs gradient descent directly in the infinite-dimensional function space. While FGD offers strong theoretical convergence guarantees, it is difficult to implement because functional gradients reside in infinite-dimensional spaces and cannot be fully computed or stored. Existing implementations rely on fixed approximations (e.g., fixed grids or basis functions) to represent gradients. However, these fixed approximations introduce irreducible approximation errors, preventing convergence to a global minimizer.

Methodology

The authors propose a new, theoretically grounded FGD algorithm that adaptively refines the representation of functional gradients during optimization. The core idea is to approximate the functional gradient $\nabla L(f_t)$ with a finite-dimensional representation $g_t$ within a broader Banach space $\mathcal{B}$ (where $\mathcal{H} \subset \mathcal{B}$ ), while dynamically ensuring the approximation error remains within a specific bound.

Theoretical Framework

The method operates under the following assumptions:

Extension: The loss functional $L$ and gradient operator $\nabla L$ defined on Hilbert space $\mathcal{H}$ can be extended to a larger Banach space $\mathcal{B}$ .
Smoothness: The extended loss is $K$ -smooth over $\mathcal{B}$ .
Descent and Compatibility: The extended gradient direction provides sufficient descent in $\mathcal{B}$ , and the dual norm of the directional derivative is compatible with the norm of the gradient in $\mathcal{B}$ .

Convergence Guarantees:
The authors prove that if the relative error between the approximate gradient $g_t$ and the true gradient $\nabla L(f_t)$ is bounded by a constant $\epsilon < 1/2$ , the algorithm guarantees:

Convergence to a Stationary Point: For smooth losses, the minimum gradient norm over $T$ iterations decays at a rate of $O(1/\sqrt{T})$ .
Global Convergence: Under an additional Polyak-Łojasiewicz (PL) condition, the algorithm converges linearly to the global minimizer.

Crucially, these guarantees hold regardless of the specific approximation method, provided the relative error bound is maintained.

Adaptive Algorithm

To satisfy the error bound in practice, the authors introduce an adaptive loop (Algorithm 1):

Approximation: At each step $t$ , approximate the gradient $\nabla L(f_t)$ using the current representation (e.g., a decision tree or a frequency grid).
Error Bounding: Compute a tight upper bound $U_t$ on the approximation error $\|g_t - \nabla L(f_t)\|_\mathcal{B}$ .
Refinement: If the relative error condition $(1+\epsilon)U_t < \epsilon \|g_t\|_\mathcal{B}$ is not met, refine the representation (e.g., increase tree depth or grid resolution) and re-approximate.
Update: Once the condition is satisfied, perform the gradient descent step $f_{t+1} = f_t - \eta g_t$ .

This strategy ensures that the algorithm starts with a coarse, cheap representation and automatically refines it only when necessary to maintain convergence guarantees.

Key Contributions

Convergence Theory for Approximate FGD: The paper establishes sufficient conditions for the convergence of approximate FGD in a general setting where true gradients lie in a Hilbert space but are approximated in a broader Banach space. It proves that maintaining a specific relative error bound guarantees convergence to a stationary point (for smooth losses) and a global minimizer (under PL conditions).
Implementable Adaptive Algorithm: The authors develop novel gradient approximation strategies that provably satisfy the derived relative error condition using only computable quantities. This yields the first fully implementable FGD algorithms with strict, end-to-end convergence guarantees to a global minimizer in a general setting.
Empirical Validation: The method is evaluated on three distinct tasks: regression in a Reproducing Kernel Hilbert Space (RKHS), numerical solution of Partial Differential Equations (PDEs), and inverse rendering (learning radiance fields).

Experimental Results

The proposed Adaptive FGD was compared against:

Fixed-Representation FGD: FGD using static approximations (e.g., fixed grid resolutions or tree depths).
Neural Network Baselines: Standard neural networks trained with Adam.

Findings:

Regression (RKHS): Adaptive FGD consistently outperformed fixed-representation FGD (which plateaued at a resolution-dependent error floor) and neural networks (which converged more slowly). It achieved the lowest test loss and training time.
PDE Solving (Wave Equation): The adaptive method closely matched reference solutions, outperforming fixed-grid FGD which suffered from approximation errors, and significantly outperforming neural networks in both solution quality and training time (reducing wall-clock time by nearly two orders of magnitude).
Inverse Rendering (Radiance Fields): In reconstructing 3D scenes from images, adaptive FGD achieved lower test loss and sharper reconstructions than fixed-grid FGD and neural networks. It started with a coarse representation and refined it only when needed, avoiding the resolution-dependent error floor of fixed methods.

Significance

The paper claims to present the first implementable FGD method that guarantees convergence to a global minimizer in a general setting without relying on specific finite-sample structures (unlike classic representer theorems). By explicitly incorporating the approximation error into the theoretical analysis and designing an adaptive strategy to control it, the method bridges the gap between the strong theoretical guarantees of ideal FGD and the practical constraints of infinite-dimensional optimization. The results demonstrate that this approach is not only theoretically sound but also practically superior to both fixed-approximation FGD and standard neural network baselines in terms of efficiency, accuracy, and convergence behavior.