Parameter Agnostic Optimization for Unknown Problem Constants

927 concepts728 papers4 proposals

Mathematical optimization models frequently promise spectacular convergence rates on paper. However, a glaring gap often separates theoretical guarantees from practical performance: many algorithms require precise, prior knowledge of the objective function's geometric constants to function correctly.

Whether it is the Lipschitz smoothness constant ($L$) needed to set a stable step size, the strong convexity parameter ($\mu$) required to tune acceleration momentum, or the noise variance ($\sigma^2$) used to calibrate stochastic updates, these values are rarely known in advance. When practitioners guess these parameters incorrectly, algorithms can easily diverge or stall. As a result, a major research direction focuses on developing parameter-agnostic optimization methods—algorithms that automatically discover or bypass these hidden constants, providing robust convergence without manual hyperparameter tuning.

The Burden of Problem-Specific Constants

To understand why parameter dependency is a bottleneck, consider the classic gradient descent update rule: $x_{t+1} = x_t - \eta \nabla f(x_t)$. Theory dictates that to guarantee convergence on a smooth function, the step size $\eta$ must be strictly bounded by $2/L$. If $L$ is unknown, choosing $\eta$ becomes an expensive game of trial and error.

This dependency scales poorly as algorithms grow more sophisticated:

How Adaptivity Replaces Prior Knowledge

The core intuition behind parameter-agnostic optimization is simple: let the history of observed gradients serve as a dynamic proxy for the local landscape geometry. Instead of demanding a global constant up front, the algorithm infers the landscape's properties on the fly.

Gradient History as a Geometry Proxy

Consider the AdaGrad step size mechanism. Instead of a fixed step size calibrated to a global Lipschitz constant $L$, AdaGrad scales the learning rate inversely with the running sum of past gradient norms:

$$\eta_t = \frac{\alpha}{\sqrt{\sum_{i=1}^t \|\nabla f(x_i)\|^2}}$$

Why does this work intuitively? If the algorithm enters a steep or highly volatile region of the loss landscape (implying a large local $L$ or high noise variance), the observed gradients will be large. This inflates the denominator, automatically shrinking the step size to prevent divergence. Conversely, in flat regions, the gradients shrink, preserving a larger step size to maintain steady progress.

Amit Attia et al. prove in SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance that this adaptive scaling allows the algorithm to achieve optimal convergence rates without any prior knowledge of smoothness or noise levels. Furthermore, Anton Rodomanov et al. show in Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction that this property makes AdaGrad stepsizes "universal"—they automatically adapt whether the underlying function is smooth, non-smooth, or intermediate Hölder-smooth.

Scale Invariance via Normalization

Another elegant mechanism for bypassing unknown constants is gradient normalization. In heavy-tailed stochastic settings where gradients can explode unpredictably, trying to find a static clipping threshold is notoriously difficult.

As an alternative, Florian Hübler et al. demonstrate that Normalized SGD—which updates using $\frac{\nabla f(x)}{\|\nabla f(x)\|}$—completely strips away the scale of the gradient. By focusing purely on the directional geometry rather than the magnitude, the algorithm becomes naturally immune to extreme noise spikes, eliminating the need for parameter-dependent clipping thresholds.

Expanding to Complex and Constrained Environments

The push for parameter-agnostic design extends far beyond basic stochastic gradient descent, transforming complex, structured optimization paradigms.

Frank-Wolfe and Constrained Optimization

Projection-free methods like the Frank-Wolfe algorithm traditionally require exact line searches or knowledge of the global curvature to determine step sizes. Sebastian Pokutta notes in The Frank-Wolfe Algorithm: A Short Introduction that direct function-value comparisons can introduce numerical instability. To resolve this, Geoffrey Négiar et al. develop adaptive backtracking line-search strategies in Linearly Convergent Frank-Wolfe without Line-Search that estimate local smoothness dynamically, preserving linear convergence without requiring global parameters.

Parameter-Free Variance Reduction

Variance-reduction methods (like SVRG or SPIDER) track historical gradients to accelerate non-convex optimization, but they typically require knowing the exact Lipschitz constant to set the inner loop lengths and step sizes. The ADASPIDER algorithm, introduced by Ali Kavis et al. in Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization, elegantly solves this by marrying recursive gradient estimation with an AdaGrad-inspired step size, creating the first parameter-free variance-reduction framework for non-convex landscapes.

Distributed Minimax Games

In multi-agent or minimax optimization (such as GAN training), setting learning rates is doubly challenging because the ideal step size depends on the interaction between both players' local smoothness constants. Yan Huang et al. tackle this in Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes. By introducing a lightweight "stepsize tracking" protocol that communicates scalar variables between agents, they allow distributed systems to achieve near-optimal convergence without requiring any agent to know the global smoothness or strong concavity constants of the game.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 725 papers
  2. Version 1 · 2026-10-04 · 623 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_hyperparameter_sensitivity_parameter_dep_d93f8279,
  title = {hyperparameter sensitivity (parameter-dependent optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hyperparameter-sensitivity-parameter-dependent-optimization/rdr_d93f82793c6545cab976e805f2654cc8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_hyperparameter_sensitivity_parameter_dep_d93f8279_v2,
  title = {hyperparameter sensitivity (parameter-dependent optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hyperparameter-sensitivity-parameter-dependent-optimization/rdr_d93f82793c6545cab976e805f2654cc8/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake