math.OCJun 15, 2026

Functional Gradient Descent with Adaptive Representations

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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Functional optimization problems are typically solved by optimizing the parameters of a fixed representation, such as a neural network, resulting in highly nonconvex losses that complicate both training and theoretical analysis. An interesting alternative is functional gradient descent (FGD), that is, gradient descent directly in function space, which benefits from strong convergence results and admits a clean theory. However, FGD is difficult to implement in practice because functional gradients are infinite-dimensional, and thus cannot be fully computed nor stored in memory. Existing implementations therefore rely on fixed approximations, which introduce approximation error. We propose a new, theoretically-grounded FGD algorithm that adapts the representation of the functional gradients over the course of optimization. By explicitly incorporating this approximation into the analysis, we establish convergence to a stationary point (for smooth losses) and to a global minimizer (under smoothness + a Polyak-Lojasiewicz-type condition) regardless of our approximations. To the best of our knowledge, this is the first implementable FGD method with such guarantees in a general setting. We demonstrate the effectiveness of our method on regression, numerical solution of PDEs, and modern computer vision. Across settings, our method consistently outperforms both FGD with fixed approximations and neural network baselines in efficiency and accuracy.

Explore similar work

CardsList
May 3, 2026cs.LG

Floating-Point Networks with Automatic Differentiation Can Represent Almost All Floating-Point Functions and Their Gradients

Theoretical studies show that for any differentiable function on a compact domain, there exists a neural network that approximates both the function values and gradients. However, such a result cannot be used in practice since it assumes real parameters and exact internal operations. In contrast, real implementations only use a finite subset of reals and machine operations with round-off errors. In this work, we investigate whether a similar result holds for neural networks under floating-point arithmetic, when the gradient with respect to the input is computed by the automatic differentiation algorithm DADD^\mathtt{AD}. We first show that given a floating-point function φφ (e.g., a loss function), arbitrary function values and gradients can be represented by a floating-point network ff and DAD(φ∘f)D^\mathtt{AD}(φ\circ f), respectively. We further extend this result: given φ1,…,φnφ_1,\dots,φ_n, DAD(φi∘f)D^\mathtt{AD}(φ_i\circ f) can simultaneously represent arbitrary gradients while ff represents the target values, under mild conditions. Our results hold for practical activation functions, e.g., ReLU\mathrm{ReLU}, ELU\mathrm{ELU}, GeLU\mathrm{GeLU}, Swish\mathrm{Swish}, Sigmoid\mathrm{Sigmoid}, and tanh\mathrm{tanh}.
Sejun Park, Yeachan Park, Geonho Hwang
Floating-PointActivation FunctionsAutomatic DifferentiationLoss Function
AskPDF
Nov 14, 2025math.OC

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates

Recently, several instances of non-Euclidean SGD, including SignSGD, Lion, and Muon, have attracted significant interest from the optimization community due to their practical success in training deep neural networks. Consequently, a number of works have attempted to explain this success by developing theoretical convergence analyses. Unfortunately, these results cannot properly justify the superior performance of these methods, as they could not beat the convergence rate of vanilla Euclidean SGD. We resolve this important open problem by developing a new unified convergence analysis under the structured smoothness and gradient noise assumption. In particular, our results indicate that non-Euclidean SGD (i) can exploit the sparsity or low-rank structure of the upper bounds on the Hessian and gradient noise, (ii) can provably benefit from popular algorithmic tools such as extrapolation or momentum variance reduction, and (iii) can match the state-of-the-art convergence rates of adaptive and more complex optimization algorithms such as AdaGrad and Shampoo.
Dmitry Kovalev, Ekaterina Borodich
Stochastic Gradient DescentConvergence AnalysisPrompt OptimizationImprovement
AskPDF
May 4, 2026math.OC

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with  O~(ε−5/3)\tilde{\mkern1mu O}(ε^{-5/3}) Global Rate

We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve O(ε−5/3log⁡(1/ε))O(ε^{-5/3}\log(1/ε)) oracle complexity bound when minimizing sufficiently smooth, non-convex functions; this is the best-known bound for first-order methods on smooth non-convex objectives. Unlike existing methods possessing this rate that require a priori knowledge of smoothness constants, we use an adaptive backtracking scheme and a gradient-based restart mechanism to estimate local curvature. This yields a practical algorithm that matches best-known theoretical rates. Empirically, PF-AGD outperforms the practical variant of AGD-Until-Guilty (Carmon et al., 2017), as well as other parameter-free variants, and is a viable alternative to nonlinear conjugate gradient methods.
Sichao Xiong, Sadok Jerad, Coralia Cartis
Convex OptimizationZeroth-Order OptimizationSharp Joint-Kl Oracle TheorySpectral Preconditioning
AskPDF