Exploiting Higher Order Smoothness in Optimization

40 concepts27 papers1 proposal

Introduction: Beyond Linear and Quadratic Approximations

When we optimize a function or learn an environment's dynamics, we typically rely on local approximations. Standard first-order optimization assumes a function is $L$-smooth, meaning its gradient changes at a bounded rate. Geometrically, this allows us to place a quadratic bowl over the function to safely choose a step size.

However, many real-world objective functions possess much richer structural properties: their higher-order derivatives (such as the Hessian or third-order derivatives) are also stable and Lipschitz continuous. Standard optimization techniques fail to fully leverage this information, missing opportunities for faster convergence (Alexander Gasnikov et al.; Alexander Gasnikov et al.).

If we know that a function's curvature changes predictably—meaning it has high-order smoothness—we can construct higher-order local approximations (like Taylor expansions) that remain accurate over much larger regions. This insight forms the foundation of a research direction that spans derivative-free optimization, continuous bandits, reinforcement learning, and sampling.

Kernel-Based Gradient Estimation in Zeroth-Order Optimization

The power of higher-order smoothness is most vividly illustrated in zeroth-order (derivative-free) optimization, where we can only query function values, not gradients.

Traditionally, zeroth-order methods estimate gradients using simple finite differences or Gaussian smoothing. While intuitive, these methods only assume basic smoothness, leading to high variance and sub-optimal sample complexity. If the underlying function is highly smooth, these simple filters fail to capture the predictable nature of the function's curvature.

To exploit higher-order smoothness, researchers replace standard Gaussian smoothing with higher-order kernel functions (such as those constructed from Legendre polynomials). The core mathematical intuition is elegant: we choose a smoothing kernel that is orthogonal to all polynomials up to a specific degree $p$.

When we take a Taylor expansion of the objective function, the kernel's orthogonality completely cancels out the lower-order error terms. As a result, the approximation error decreases rapidly as the smoothness of the objective function increases, allowing the algorithm to extract a highly precise gradient signal from noisy function evaluations (Francis Bach et al.).

This strategy has been successfully deployed across several settings:

  • Distributed Optimization: Arya Akhavan et al. developed a distributed zero-order technique utilizing $2d$ queries per iteration combined with a smoothness-aware kernel, achieving resilience against adversarial noise.
  • Saddle-Point Problems: For non-convex/non-concave stochastic saddle-point problems satisfying the Polyak-Łojasiewicz condition, S. I. Sadykov et al. demonstrated that Legendre polynomial kernels provide tighter convergence bounds than traditional Gaussian smoothing.
  • Stochastic and Overparameterized Regimes: Aleksandr Lobanov and Georgii Bychkov et al. showed that explicitly incorporating higher-order smoothness into two-point feedback estimators dramatically improves iteration complexity, especially when paired with modern overparameterized models.

Higher-Order Oracles and Tensor Methods

When higher-order derivatives are directly accessible via an oracle, we can move beyond standard gradient descent and Newton's method. Instead of approximating a function with a parabola, we can use a $p$-th order Taylor expansion.

Sebastien Bubeck et al. introduced Accelerated Taylor Descent (ATD), which systematically generalizes Nesterov's classical acceleration to higher-order derivatives. By leveraging a $p$-th order Taylor oracle, the authors achieved a near-optimal convergence rate. Similarly, the optimal tensor methods proposed by Alexander Gasnikov et al. close the theoretical gap between lower and upper complexity bounds by utilizing these stable higher-order derivatives. Even in non-convex optimization, assuming a Lipschitz continuous third derivative allows algorithms to construct precise local models that significantly improve accuracy dependencies (Oliver Hinder).

Continuous Dynamics and High-Order Integrators

Another perspective views optimization as a continuous-time physical system described by an Ordinary Differential Equation (ODE), such as the heavy-ball method.

If an objective function has bounded higher-order derivatives, the underlying continuous trajectory is exceptionally smooth. As Jingzhao Zhang demonstrated, this smoothness allows us to discretize the ODE using high-order numerical integrators (like Runge-Kutta methods) rather than standard Euler discretization. Because high-order integrators match the Taylor expansion of the continuous dynamics more closely, the algorithm can take significantly larger, stable steps without drifting off-course, translating function smoothness directly into accelerated convergence.

This principle extends naturally to sampling. In Markov Chain Monte Carlo (MCMC), Wenlong Mou et al. proposed a high-order Langevin diffusion algorithm. By utilizing smoothness-adaptive gradient interpolation (such as Lagrange interpolation with Chebyshev nodes), the authors exploited the higher-order derivatives of the target distribution, breaking long-standing dimensional barriers in mixing time.

Frontiers and Theoretical Gaps

While the benefits of higher-order smoothness are clear, establishing tight theoretical bounds across all learning paradigms remains an active frontier.

In continuum-armed bandits and online learning, exploiting predictable curvature allows algorithms to navigate continuous reward spaces with significantly reduced cumulative regret (Yusha Liu et al.). For instance, Baihe Huang et al. established the minimax sample complexity for stochastic zeroth-order optimization under a Lipschitz Hessian, proving an optimal error rate via a robust two-stage algorithm. In reinforcement learning, K. Lakshmanan 0002 et al. showed that swapping simple histogram models for higher-order Kernel Density Estimation (KDE) enables continuous RL agents to close the regret gap faster by exploiting smooth transition dynamics.

However, several open questions persist:

  • Bandit Optimization Gaps: Shashank Singh et al. and Su Jia et al. highlighted a persistent theoretical gap between proven lower bounds and algorithmic performance when the smoothness parameter is greater than one or two, leaving optimal regret bounds for highly smooth non-stationary environments as an open conjecture.
  • Distributed and Composite Frameworks: In distributed learning, Arsalan Sharif-Nassab et al. noted that while optimal scaling is well-understood for once-differentiable functions, leveraging higher-order smoothness in data-scarce, massive-machine regimes remains open. Similarly, Andrei Kulunchakov et al. pointed out that unified surrogate-based optimization frameworks have yet to fully incorporate higher-order smoothness properties like those found in cubic regularization.
  • Score Estimation: In generative modeling, Andre Wibisono et al. proved that standard Gaussian kernels cannot exploit higher-order smoothness when estimating score functions, demonstrating that achieving optimal minimax rates requires the development of higher-order kernels that can take negative values.

Key Foundational Work

Improved Regret Bounds for Undiscounted Continuous Reinforcement Learning (2015) — contributed 1 concept elements to this direction.
Nonparametric Regression Analysis of Growth Curves (1984) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_high_order_smoothness_exploitation_6123ad92,
  title = {high-order smoothness exploitation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-order-smoothness-exploitation/rdr_6123ad92222a44d791f58939a7e60033},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_high_order_smoothness_exploitation_6123ad92_v1,
  title = {high-order smoothness exploitation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-order-smoothness-exploitation/rdr_6123ad92222a44d791f58939a7e60033/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake