Adaptive Precision for Inexact Subproblem Solving

128 concepts87 papers1 proposal

Many powerful optimization frameworks operate via a nested, two-tier structure: an outer loop that tracks global progress toward an optimal solution, and an inner loop that solves a localized subproblem. Examples include computing a step direction via a Taylor-series approximation in Newton-type methods, evaluating a policy in Markov Decision Processes, or running a physical simulation to compute gradients in differentiable physics.

Traditionally, these inner subproblems are solved to a high, fixed level of precision. However, this introduces a severe computational mismatch. When the outer loop's current estimate is far from the true global optimum, the local subproblem model is only a crude representation of the broader objective landscape. Expending massive computational resources to solve this local subproblem perfectly is wasteful.

Adaptive precision optimization solves this bottleneck by dynamically tuning the inner loop's termination criteria based on the outer loop's progress. By using coarse, rapid approximations early in the optimization process and progressively tightening precision as the solver nears convergence, this strategy maximizes computational efficiency without compromising the final result.

The Core Mechanism: Forcing Sequences and Residual Scaling

To implement adaptive precision without causing the global algorithm to diverge, the inner loop's tolerance must be mathematically coupled to the outer loop's proximity to the solution. If the outer loop is making large leaps, the inner loop is permitted to be highly inexact. As the outer loop's progress slows, the inner loop must become more precise.

A foundational realization of this principle can be traced back to work by J. N. Holt in An inexact Levenberg-Marquardt method for large sparse nonlinear least squres, which demonstrated that terminating linear subproblem solvers once the residual falls below a threshold proportional to the current gradient magnitude prevents computational waste far from the solution. This proportional threshold acts as a forcing sequence, regulating inner-loop effort relative to potential global progress.

In modern composite and second-order optimization, this concept is critical. As explained by Yuekai Sun in Proximal Newton-Type Methods for Minimizing Composite Functions, solving quadratic subproblems to high precision early on yields no global benefit because the local quadratic model itself is highly inaccurate far from the optimum. By employing an adaptive stopping criterion governed by a forcing sequence, the optimizer avoids oversolving intermediate subproblems while maintaining global convergence.

Similarly, Ilan Adler et al. in New Proximal Newton-Type Methods for Convex Optimization utilize the norm of the composite gradient to dynamically adjust solver precision, automatically tightening accuracy requirements only as convergence is approached.

Far from Optimum:
[Outer Loop: Large Gradient] ──> [Inner Loop: High Tolerance / Coarse & Fast Step]

Near Optimum:
[Outer Loop: Small Gradient] ──> [Inner Loop: Low Tolerance / Fine & Precise Step]

Generalization Across Paradigms

The strategy of matching inner-loop fidelity to outer-loop maturity manifests across a wide variety of computational domains, changing how "precision" is defined depending on the context.

Policy Iteration and Hierarchical Optimization

In large-scale reinforcement learning, Matilde Gargiani et al. apply this to Markov Decision Processes in Inexact GMRES Policy Iteration for Large-Scale Markov Decision Processes. They use an adaptive stopping condition based on the Bellman residual to prevent over-solving the policy evaluation step when the current policy is far from optimal. For nested variational inequalities, Meggie Marschner in Tikhonov regularized exterior penalty methods for hierarchical variational inequalities utilizes a merit function norm as a dynamic stopping criterion, ensuring that auxiliary subproblems are solved only to the precision required by the outer loop's current state.

Randomized Sketching and Sub-sampling

Precision can also be controlled by adjusting data fidelity rather than iteration counts. In Sub-sampled Cubic Regularization for Non-convex Optimization, Jonas K Kohler et al. link the sample size of gradient and Hessian estimates directly to the proximity of the solution, requiring fewer samples when far from the optimum. Similarly, Jonathan Lacotte et al. in Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality propose an adaptive doubling strategy that starts with a minimal matrix sketch size and increases it only when progress stalls, minimizing computational overhead during early iterations.

Physical Simulations and Grids

When optimization involves continuous physical models or integrations, precision is modulated via grid resolution or solver steps. Kanishk Bhatia et al. introduce this to deep learning in PRDP: Progressively Refined Differentiable Physics, where they adapt simulator fidelity to model maturity. By avoiding unnecessary precision during early and middle phases of training, they reduce total solver iterations by over 80% while preserving final model accuracy. For density estimation, Rahul Mazumder in A new computational framework for log-concave density estimation dynamically scales up the precision of numerical integration grids across iterations, utilizing cheap, coarse grids initially and shifting to fine grids near the solution.

Why It Works: Preserving Fast Local Convergence

The intuitive concern with using inexact subproblem solutions is that it might destroy the rapid local convergence rates (such as linear, superlinear, or quadratic rates) that make high-order optimization methods attractive in the first place.

The mathematical elegance of adaptive precision is that it avoids this pitfall by design. Because the subproblem tolerance is tied directly to the global error or gradient norm, the inner solver automatically becomes exact precisely when it needs to be: in the local neighborhood of the optimum.

As demonstrated in Inexact Tensor Methods with Dynamic Accuracies, setting the subproblem accuracy to be inversely proportional to the progress made allows for massive wall-clock speedups during the early phases of optimization while fully preserving the high-order theoretical convergence rates near the solution. By dynamically balancing the computational cost per step with the overall rate of convergence, adaptive precision breaks the traditional trade-off between execution speed and final numerical exactness.

Key Foundational Work

Fast Krylov Methods for N-Body Learning (2005) — contributed 3 concept elements to this direction.
An inexact Levenberg-Marquardt method for large sparse nonlinear least squres (1985) — contributed 2 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_adaptive_precision_optimization_ff76a13a,
  title = {adaptive precision optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-precision-optimization/rdr_ff76a13a62134bf58b373a63a3312f31},
  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_adaptive_precision_optimization_ff76a13a_v1,
  title = {adaptive precision optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-precision-optimization/rdr_ff76a13a62134bf58b373a63a3312f31/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake