Optimization Without Objective Function Evaluations

This direction is merged into another direction: noisy objective functions. Its last version stays readable and citable here.

Version 1 of 111 papers18 conceptsfrozen 2026-10-04

In traditional optimization, the objective function $f(x)$ is the ultimate arbiter of progress. Whether using line-search or trust-region methods, an algorithm typically proposes a step and then asks: "Did the function value actually decrease?" If the answer is no, the step is rejected, the search area is shrunk, and the process repeats.

However, a growing body of research suggests that in high-dimensional, noisy environments—such as training deep neural networks or solving complex partial differential equations—this "sanity check" is not only expensive but can be actively detrimental. This has led to the development of Objective-Function-Free Optimization (OFFO), a paradigm where algorithms navigate landscapes using only gradient information, bypassing the evaluation of the objective function entirely.

The Problem with Progress Checks

The primary motivation for OFFO is robustness to noise. In modern machine learning, we rarely calculate the true loss; instead, we estimate it using mini-batches. As Serge Gratton, Sadok Jerad, and Philippe L. Toint argue in Complexity of Adagrad and other first-order methods for nonconvex optimization problems with bounds constraints, these stochastic evaluations are "liars." A step might be perfectly valid, moving the parameters toward a global minimum, but a noisy mini-batch might report a higher loss, triggering a false rejection.

When a standard solver stalls because it cannot verify progress through a noisy objective function, it wastes computational cycles. By treating every iteration as successful and relying on adaptive scaling rather than step-rejection, OFFO frameworks maintain momentum in environments where traditional merit functions would fail.

If we don't check the objective function, how do we ensure the algorithm doesn't diverge? The intuition lies in the relationship between the gradient and the step size.

In papers like An optimally fast objective-function-free minimization algorithm using random subspaces, researchers demonstrate that gradient magnitudes and dynamic weighting can serve as a proxy for the trust region. Instead of comparing predicted vs. actual loss decreases, the algorithm uses the history of gradients to adjust the search space.

This is particularly effective when combined with AdaGrad-style adaptive scaling. In A Simple First-Order Algorithm for Full-Rank Equality Constrained Optimization, Serge Gratton and Philippe L. Toint introduce ADSWITCH, which alternates between minimizing the objective and satisfying constraints. By bypassing the "merit functions" usually required for constrained optimization, the algorithm remains stable even when the gradients are highly corrupted by noise.

Scaling to High Dimensions and Hierarchies

The "function-free" approach is not limited to simple first-order steps; it scales to sophisticated structural optimizations:

  1. Random Subspaces: To handle massive dimensionality, Serge Gratton and colleagues show that one can perform OFFO within random low-dimensional "sketches" of the problem, achieving optimal convergence rates without ever calculating the full objective value.
  2. Multilevel Hierarchies: In Multilevel Objective-Function-Free Optimization with an Application to Neural Networks Training, the authors merge OFFO with multigrid methods. This allows the optimizer to work across different levels of abstraction (e.g., different layers or resolutions). The key is a "gradient correction" mechanism that ensures coarse-level updates stay aligned with fine-level gradients, as detailed in Recursive Bound-Constrained AdaGrad with Applications to Multilevel and Domain Decomposition Minimization.
  3. Single Index Models: Even in statistical modeling, Ravi Ganti, Rebecca Willett, and Robert D Nowak found that optimization stability improves when the gradient depends on the transfer function's value rather than its derivative, further emphasizing the benefit of avoiding sensitive, high-variance estimators in high-dimensional spaces.

Why It Works: The Intuition

The success of OFFO rests on the idea that the gradient is a more stable signal than the objective value. In a high-dimensional landscape, the specific value of a function at a single point is highly sensitive to noise and local fluctuations. However, the vector field of the gradient provides a directional consensus. By trusting the "flow" of the landscape rather than the "altitude" at any given point, these algorithms achieve a level of robustness that allows them to converge in conditions where traditional methods would simply get stuck.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimization_without_objective_function__a37b37d1,
  title = {Optimization Without Objective Function Evaluations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-without-objective-function-evaluations/rdr_a37b37d1e63945178fb6069bcfa790d5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimization_without_objective_function__a37b37d1_v1,
  title = {Optimization Without Objective Function Evaluations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-without-objective-function-evaluations/rdr_a37b37d1e63945178fb6069bcfa790d5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}