In theoretical optimization, we often treat complex algorithms as sequences of clean, atomic operations. For instance, proximal gradient methods assume we can instantly compute a gradient and evaluate a proximal operator. Primal-dual frameworks assume perfect projections, and bilevel optimization algorithms assume we can perfectly solve a lower-level optimization problem before updating the upper-level variables.
In practice, this assumption of perfect precision breaks down. Many foundational operations—such as the proximal mapping of a non-smooth regularizer—do not have closed-form solutions. Instead, they must be solved numerically using an internal, nested optimization loop. This creates a fundamental tension: if every internal step introduces a small numerical error, why doesn't the global algorithm accumulate these errors and diverge?
The answer lies in the framework of inexact subproblem optimization. By precisely matching the decay rate of internal approximation errors to the convergence rate of the outer loop, we can guarantee that an algorithm remains stable, robust, and mathematically sound—even when every single subproblem is solved incorrectly.
The Core Mechanism: Summable Errors
To understand why inexact algorithms work, consider an iterative optimization process where each step is perturbed by an error vector $e_k$ at iteration $k$. If these errors are static, they can act as persistent noise, forcing the algorithm to bounce around a neighborhood of the solution rather than converging to it.
However, as shown by Peichao Duan et al. in New inertial proximal gradient methods for unconstrained convex optimization problems, global convergence is preserved as long as the sequence of errors is summable ($\sum_{k=1}^{\infty} \|e_k\| < \infty$).
Intuitive understanding comes from viewing the algorithm's trajectory as a path bound by a strict computational budget. Every time an inner loop provides an inexact solution, it pushes the outer loop slightly off-course. If the cumulative sum of these deviations is bounded, the algorithm can only drift a finite distance away from its ideal path.
This principle extends far beyond standard Euclidean spaces. For example, Yuchen Li et al. demonstrate in Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms that optimization on curved geometric spaces (manifolds) tolerates inexact gradients and approximate manifold retractions. As long as the geometric distortions introduced by these cheap approximations diminish at a summable rate, the algorithm reliably reaches a true stationary point.
Preserving Convergence Rates
Allowing for inexactness is highly practical, but does it slow the algorithm down? Remarkably, if the inner loop's precision is scheduled correctly, the global algorithm can maintain its exact theoretical convergence rate.
In Inexact first-order primal-dual algorithms, Antonin Chambolle et al. establish the exact relationship between error decay and global convergence speed. They prove that if the approximation error of an inner proximal subproblem decreases at a specific rate relative to the outer iteration count, the global algorithm preserves its optimal sublinear ($O(1/N)$) or even linear convergence rates.
Outer Loop (Iteration k) ───> Schedules Tolerance ε_k ───> Inner Loop
▲ │
│ ▼
Updates State x_{k+1} <─── Returns Approximate Solution <─── Computes until Error ≤ ε_k
This error-scheduling strategy acts as a dynamic tolerance envelope. Early in the optimization process, the outer loop is far from the global minimum, meaning highly precise subproblem solutions are a waste of computational effort. As the outer loop approaches the solution, the tolerance envelope shrinks, forcing the inner loop to solve subproblems with increasing precision.
This balance is also vital for momentum-based methods. Qunwei Li et al. show in Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization that accelerated frameworks—which are notoriously sensitive to gradient noise—can tolerate inexact proximal mappings and gradients without losing their acceleration benefits, provided the errors diminish sufficiently over time.
Robustness in Nested and Bilevel Optimization
The power of inexact optimization becomes fully apparent in nested architectures like bilevel optimization and saddle-point (min-max) problems. In these settings, evaluating the objective function of the upper-level problem requires solving an entire optimization problem at the lower level.
In First-Order Methods for Linearly Constrained Bilevel Optimization, Guy Kornowski et al. address the reality that lower-level problems are rarely solved to exact optimality. By designing an optimization framework inspired by online learning, the authors prevent the estimation errors of the lower-level solutions from accumulating or destabilizing the upper-level trajectory.
Similarly, Tristan van Leeuwen demonstrates in Derivative-free stochastic bilevel optimization for inverse problems that explicitly modeling the computational errors of subordinate tasks allows derivative-free solvers to remain stable. Rather than treating the inner loop as a black box that must return a perfect answer, the outer loop treats it as an inexact oracle with bounded, predictable noise.
The Catch: The Paradox of Error Verification
While the theory behind inexact subproblem solving is elegant, implementing it introduces a practical paradox: How do you measure the error of an approximate solution if you do not know the exact solution?
Many theoretical accuracy conditions depend directly on the distance between the approximate solution and the unknown true solution. As noted by Wen Huang et al. in An inexact Riemannian proximal gradient method, this dependency makes direct implementation and hyperparameter tuning exceptionally difficult.
To bypass this issue, practitioners often resort to heuristics, such as running the inner loop for a fixed number of iterations. However, as Wei Peng et al. caution in Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions, a fixed iteration count does not guarantee that the required accuracy bounds are met across all regions of the optimization landscape.
Modern research continues to focus on developing computable error criteria—such as monitoring the residual of the inner problem's optimality conditions—to bridge the gap between theoretical error-decay schedules and practical, executable algorithms.