Pith. sign in

REVIEW 2 major objections 3 minor 37 references

Iterative Linearized Control: Stable Algorithms and Complexity Guarantees

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read Regularized ILQR converges in O(1/epsilon^2) iterations

desk verdict First worst-case complexity bounds for ILQR-style control, with a small but repairable gap in the main line-search constant and a conditional accelerated rate. read the letter →

arxiv 1908.07615 v1 pith:POHVSHDY submitted 2019-08-20 math.OC

classification math.OC MSC 49J1549M3790C3090C55
keywords iterativelinearquadraticregulatorregularizedGauss-Newtonmethodcompositeoptimizationnonlinearcontrolautomaticdifferentiationoracleworst-casecomplexityCatalystaccelerationproximalregularization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that the iterative linear quadratic regulator (ILQR), a widely used heuristic for finite-horizon nonlinear control, can be turned into an algorithm with rigorous worst-case guarantees by adding a proximal regularization term. The key is to view the control problem as minimizing $f(\bar u)=h(\tilde x(\bar u))+g(\bar u)$, so that each ILQR step is a Gauss-Newton step on a convex model of $f$. The paper proves that the regularized Gauss-Newton method reaches an $\varepsilon$-stationary point in $O(1/\varepsilon^2)$ calls to a regularized Gauss-Newton oracle, and that a Catalyst-style accelerated variant reaches $O(1/N^2)$ objective suboptimality when the convex model lower-bounds the objective everywhere. The result matters because it supplies the missing convergence-rate analysis for a whole family of iterative linearization controllers.

What carries the argument

The load-bearing object is the regularized Gauss-Newton step (37), $\bar u_{k+1}=\bar u_k+\arg\min_{\bar v}\{c_f(\bar u_k+\bar v;\bar u_k)+(2\gamma_k)^{-1}\|\bar v\|^2\}$, with the convex model $c_f(\bar v;\bar u)=h(\tilde x(\bar u)+\nabla\tilde x(\bar u)^\top(\bar v-\bar u))+g(\bar v)$. For quadratic $h$ and $g$ this reduces to ILQR plus a proximal penalty and admits the closed form $\bar u_{k+1}=\bar u_k-(\nabla\tilde x(\bar u_k)H\nabla\tilde x(\bar u_k)^\top+G+\gamma_k^{-1}I)^{-1}\nabla f(\bar u_k)$, which is what links iterate differences to gradient norms. The supporting mechanism is the equivalence (Propositions 2.1–2.3 and 3.6) between dynamic programming for the linear-quadratic subproblem and calls to an automatic-differentiation oracle, so that the oracle count is a faithful measure of computational cost.

What would settle it

On a smooth composite control example with known smoothness constants and suboptimality gap, run the regularized Gauss-Newton method (37) with the decreasing line-search of Algorithm 13 and measure the smallest $N$ with $\|\nabla f(\bar u_N)\le\varepsilon$ for several $\varepsilon$; if the count grows faster than $2L(f(\bar u_0)-f_*)/\varepsilon^2$ (up to the logarithmic line-search term), Corollary 4.4 is contradicted. To test the accelerated claim, evaluate $\min_{\bar u,\bar v}(f(\bar v)-c_f(\bar v;\bar u))$ on a concrete convex-composite instance; if this minimum is strictly negative while the algorithm still shows a $1/N^2$ objective decrease, then the lower-bound hypothesis (42) is not necessary for the observed speed-up.

Watch

Extended reading notes

Core claim

The central claim is that iterative linearization control—ILQR in exact dynamics and ILQG in noisy dynamics—is best understood as model-minimization on the composite objective $f(\bar u)=h(\tilde x(\bar u))+g(\bar u)$, and that the model-minimization subproblem is a linear-quadratic control problem solvable by dynamic programming in time linear in the horizon $\tau$. The paper's main new result is that augmenting the ILQR model with a proximal term $(2\gamma_k)^{-1}\|\bar u-\bar u_k\|^2$ gives the regularized Gauss-Newton method (37), which with a decreasing line-search finds an $\varepsilon$-stationary point in at most $O(1/\varepsilon^2)$ calls to the regularized Gauss-Newton oracle (Corollary 4.4). It further shows that the accelerated variant in Algorithm 1 preserves this guarantee and, under the extra assumption that the convex model satisfies $c_f(\bar v;\bar u)\le f(\bar v)$ for all $\bar u,\bar v$—an assumption that forces $f$ to be convex—achieves $f(\bar u_N)-f_*\le 4\delta^{-1}\|\bar u^*-\bar u_0\|^2/(N+1)^2$ (Proposition 4.5).

Load-bearing premise

The accelerated $O(1/N^2)$ rate rests on the assumption that the convex model $c_f(\bar v;\bar u)$ never exceeds the true objective $f(\bar v)$, which forces $f$ to be convex; if that fails, the paper only claims the slower $O(1/N)$ stationary-point rate.

Editorial extensions

If this is right

  • Corollary 4.4 gives a worst-case oracle complexity for an ILQR-type method: $O(1/\varepsilon^2)$ calls to the regularized Gauss-Newton oracle for an $\varepsilon$-stationary point of the composite control objective.
  • Corollary 4.6 turns this into automatic-differentiation oracle complexity: for problems with a final-state cost the regularized method needs $(2d+1)$ times the Gauss-Newton count, so the proximal fix costs only a constant factor over a gradient step.
  • The model-minimization viewpoint unifies gradient descent, Gauss-Newton, and Levenberg-Marquardt for control: all are linear-quadratic control solves, hence all cost roughly the same as one gradient computation in the horizon length $\tau$.
  • The accelerated Algorithm 1 inherits the non-accelerated guarantee and, when the convex model lower-bounds the objective (which forces convexity), converges at rate $O(1/N^2)$ in objective value.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct extension the paper leaves open: the rollout-based iLQG/DDP variant is not analyzed, but the same proximal-regularization template would likely endow it with the same $O(1/\varepsilon^2)$ guarantee; that is an inference, not a paper claim.
  • The automatic-differentiation/dynamic-programming equivalence points beyond control: any nested composition with a convex quadratic outer cost and smooth inner maps is a candidate for the same regularized Gauss-Newton complexity analysis.
  • The lower-bound condition (42) suggests a practical design rule for model-based optimization: if the surrogate model underestimates the true cost, acceleration is provable; if not, the safe choice is the non-accelerated proximal step.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The manuscript studies finite-horizon discrete-time nonlinear control through the lens of composite optimization. It reformulates the control objective as f(\bar u)=h(\tilde x(\bar u))+g(\bar u), identifies the relevant automatic-differentiation oracle, and shows that dynamic-programming steps for linear-quadratic subproblems are equivalent to gradient back-propagation. The main results are a regularized Gauss-Newton method (regularized ILQR) with a claimed O(1/epsilon^2) iteration complexity to epsilon-stationarity (Corollary 4.4) and an accelerated variant with a claimed O(1/N^2) rate under a model lower-bound condition (Proposition 4.5). The paper also gives oracle-cost comparisons, PyTorch experiments on a pendulum and a two-link arm, and a public code repository.

Significance. If the proofs are completed, the paper gives the first worst-case complexity guarantee for ILQR-type algorithms, expressed in calls to an automatic-differentiation oracle, and it usefully connects DDP/ILQR to first-order composite optimization. The derivations of the oracle costs and of the DP/back-propagation equivalence are clean and practically relevant, and the release of code is a concrete strength. The central non-accelerated analysis is standard in structure, but as written it is not fully supported by the line-search in the appendix; the gap is localized and repairable rather than fatal.

major comments (2)
  1. [§4.2, Cor. 4.4 and Appendix E, Algo. 13–14] The line-search that supports Corollary 4.4 is not the line-search analyzed in the theorem. Condition (39) and Prop. 4.1 use f(\bar u_{k+1}) ≤ c_f(\bar u_{k+1};\bar u_k) + (1/(2γ_k))\|\bar u_{k+1}-\bar u_k\|^2, while Algorithms 13 and 14 use γ_k/2 in the same place. Under the γ_k/2 version, the strong-convexity subtraction in the proof of Prop. 4.1 cannot be combined with the line-search condition to obtain the claimed descent inequality. In addition, Algorithm 13 has no lower bound on the accepted step size: after a rejection above γ̂, the loop may accept γ < γ̂. Since Lemma 4.3 only shows that every γ ≤ γ̂ satisfies (39), this situation is possible. The constant L in Cor. 4.4 is maximized over [γ̂, γ0], so for accepted γ < γ̂ the bound from Prop. 4.1 may fail; with ℓ^2_{\tilde x,S}L_h+L_g = 1, γ̂ = 0.1, γ0 = 0.2, and γ = 0.05, one obtains γ(A+γ^{-1})^2 ≈ 22.0, whereas the maximum over [0.1,0.2] is about 12.0. The theorem can be repaired by flooring the line-search at γ̂ and by consistently using (2γ_k)^{-1} in the pseudocode, or by restating L over the accepted range [min_k γ_k, γ0]. As printed, the proof of the central O(1/ε^2) guarantee does not go through for the algorithm stated.
  2. [§4.3, Prop. 4.5, Eq. (42)] The O(1/N^2) rate is contingent on the model lower-bound condition c_f(\bar v;\bar u) ≤ f(\bar v) for all \bar u,\bar v. As the proof immediately notes, this condition implies convexity of f (via Lemma 8.3 of Drusvyatskiy and Paquette). This is a strong structural assumption, not a minor technicality: it is exactly what converts the Catalyst extrapolation into a genuinely faster rate. The paper should state in the abstract and in Section 4.3 that the accelerated rate applies to convex-composite objectives satisfying (42), and that no accelerated worst-case rate is claimed for the general nonlinear control problems used in the experiments. As it stands, the presentation invites the reader to attribute the accelerated guarantee to the algorithm at large.
minor comments (3)
  1. [§5.2] The experiments use a constant step-size tuned after a burn-in phase; they do not exercise the backtracking line-search of Cor. 4.4, so the reported speedup of the accelerated variant is empirical only. A sentence making this explicit would avoid over-reading the plots.
  2. [§2.2, Prop. 2.4] The assumption that ∇²_xx φ_t, ∇²_xw φ_t, and ∇²_ux φ_t vanish is stated without discussion; a brief remark on how restrictive this is for the noisy-dynamics model would help, since the noisy analysis is not part of the Cor. 4.4 guarantee.
  3. [§4.2, Eq. (41)] The threshold γ̂ depends on ℓ_{f,S} and M_C, which are not computable in practice; the paper should say explicitly that the guarantee is existential and that the theory does not prescribe a concrete initial step-size γ0.

Circularity Check

0 steps flagged · score 0.0 of 10

Not circular: the complexity bounds are derived from stated smoothness and regularity assumptions together with prior external optimization results, and no fitted quantity is renamed as a prediction.

full rationale

The paper's central claim, Corollary 4.4, is a direct consequence of Proposition 4.1, Lemma 4.2, and Lemma 4.3, all of which are proved in the paper from explicit assumptions on the objective and dynamics. The constant L in the bound is defined from problem data (smoothness constants, the Lipschitz constant of the trajectory map, and the step-size range) and is not fitted to experimental output. No experimental step-size or burn-in phase enters the theoretical bound, so no fitted input is relabeled as a prediction. The accelerated statement in Proposition 4.5 invokes Lemma 8.3 of Drusvyatskiy and Paquette and Lemma B.1 of Paquette et al.; these are prior works co-authored by two of the present authors, but they are external published technical lemmas with stated assumptions, and the present proof does not reduce to a self-citation chain that smuggles in the target result. The reformulation of ILQR as a regularized Gauss-Newton method is an interpretation grounded in the paper's own equations, not a renaming that carries the convergence result by definition. The possible concern that the line-search in Corollary 4.4 may accept step-sizes below gamma-hat is a correctness gap about the proof's constant, not a circularity: the derivation is self-contained and does not assume what it proves.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central theoretical claims rest on standard smoothness assumptions and on two problem-specific assumptions: the model lower bound for acceleration (Eq. 42), which implies convexity, and the zero mixed-second-derivative assumption for noisy dynamics (Prop 2.4). No new physical entities are introduced. The only fitted numbers in the paper are algorithm step-sizes in experiments, which do not enter the theoretical bounds.

free parameters (2)
  • Regularization step-size gamma for RegILQR/AccRegILQR in experiments = not reported numerically; tuned after 5-iteration burn-in
    In Section 5.2 the authors use a constant step-size sequence tuned after a 5-iteration burn-in. This is a free parameter adjusted per problem instance to obtain the reported fast convergence.
  • Initial step-size gamma_0 and decreasing factor rho in backtracking line-search = gamma_0 >= gammahat arbitrary; 0 < rho < 1
    Cor 4.4's complexity bound depends on gamma_0 and rho only through logarithmic factors, but these are algorithm hyperparameters chosen by the user, not fitted to data.
assumptions (3)
  • domain assumption The dynamics phi_t and costs h_t, g_t are sufficiently smooth (differentiable, with Lipschitz continuous gradients on compact sets).
    Used throughout Section 2 and 4, e.g., in Lemma 4.2 to bound the model error quadratically. It is standard in nonlinear control and first-order optimization.
  • ad hoc to paper The convex model c_f(v; u) lower bounds the objective f everywhere (Eq. 42) to obtain the accelerated O(1/N^2) rate.
    Prop 4.5's accelerated convergence requires cf(v; u) <= f(v) for all u,v, which as the authors note implies f is convex (citing Lemma 8.3 of Drusvyatskiy and Paquette). This is a strong, non-generic assumption not satisfied for the nonconvex swing-up and arm experiments; the accelerated practical claims therefore fall back to the non-accelerated guarantee.
  • ad hoc to paper For the noisy dynamics analysis, the second derivatives nabla^2_xx phi_t, nabla^2_xw phi_t, and nabla^2_ux phi_t are zero (Prop 2.4).
    This assumption makes the Gaussian approximation of the linearized trajectory tractable, reducing the cross terms. It is restrictive and only stated in the proposition, limiting the ILQG extension.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Iterative Linearized Control: Stable Algorithms and Complexity Guarantees." pith.science (2026). https://pith.science/paper/POHVSHDY

@misc{pith2026190807615,
  author       = {Pith},
  title        = {Pith review of: Iterative Linearized Control: Stable Algorithms and Complexity Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/POHVSHDY}},
  note         = {Machine review of arXiv:1908.07615}
}
read the original abstract

We examine popular gradient-based algorithms for nonlinear control in the light of the modern complexity analysis of first-order optimization algorithms. The examination reveals that the complexity bounds can be clearly stated in terms of calls to a computational oracle related to dynamic programming and implementable by gradient back-propagation using machine learning software libraries such as PyTorch or TensorFlow. Finally, we propose a regularized Gauss-Newton algorithm enjoying worst-case complexity bounds and improved convergence behavior in practice. The software library based on PyTorch is publicly available.

Figures

Figures reproduced from arXiv: 1908.07615 by the authors.

Figure 1
Figure 1. Control settings considered. From left to right: pendulum, two-link arm robot. [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. Convergence of ILQR, regularized ILQR and accelerated regularized ILQR on the inverted pendulum (top) [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Man\' e , D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., T...

  2. [2]

    Introduction to the mathematical theory of control processes, volume 2

    Bellman, R. Introduction to the mathematical theory of control processes, volume 2. Academic press, 1971

  3. [3]

    Bertsekas, D. P. Dynamic programming and optimal control. Athena Scientific, 3rd edition, 2005

  4. [4]

    Numerical methods for least squares problems

    Bjorck, A. Numerical methods for least squares problems. SIAM, 1996

  5. [5]

    Burke, J. V. Descent methods for composite nondifferentiable optimization problems. Mathematical Programming, 33 0 (3): 0 260--279, 1985

  6. [6]

    Cartis, C., Gould, N. I. M., and Toint, P. L. On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming. SIAM Journal on Optimization, 21 0 (4): 0 1721--1739, 2011

  7. [7]

    Pantoja, J

    De O. Pantoja, J. Differential dynamic programming and N ewton's method. International Journal of Control, 47 0 (5): 0 1539--1553, 1988

  8. [8]

    Regret bounds for robust adaptive control of the linear quadratic regulator

    Dean, S., Mania, H., Matni, N., Recht, B., and Tu, S. Regret bounds for robust adaptive control of the linear quadratic regulator. In Advances in Neural Information Processing Systems, pp.\ 4188--4197, 2018

Show all 37 references
  1. [9]

    L., Huang, M., Kolmanovsky, I

    Dontchev, A. L., Huang, M., Kolmanovsky, I. V., and Nicotra, M. M. Inexact N ewton- K antorovich methods for constrained nonlinear model predictive control. IEEE Transactions on Automatic Control, 2018

  2. [10]

    and Paquette, C

    Drusvyatskiy, D. and Paquette, C. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, pp.\ 1--56, 2018

  3. [11]

    Dunn, J. C. and Bertsekas, D. P. Efficient dynamic programming implementations of N ewton's method for unconstrained optimal control problems. Journal of Optimization Theory and Applications, 63 0 (1): 0 23--38, 1989

  4. [12]

    Global convergence of policy gradient methods for the linear quadratic regulator

    Fazel, M., Ge, R., Kakade, S., and Mesbahi, M. Global convergence of policy gradient methods for the linear quadratic regulator. In Proceedings of the 35th International Conference on Machine Learning, volume 80, 2018

  5. [13]

    and Walther, A

    Griewank, A. and Walther, A. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM, 2008

  6. [14]

    and Pannek, J

    Gr \"u ne, L. and Pannek, J. Nonlinear model predictive control. Springer, 2017

  7. [15]

    C., Pereyra, V., and Scherer, G

    Hansen, P. C., Pereyra, V., and Scherer, G. Least squares data fitting with applications. JHU Press, 2013

  8. [16]

    Jacobson, D. H. and Mayne, D. Q. Differential Dynamic Programming. Elsevier, 1970

  9. [17]

    Kakade, S. M. and Lee, J. D. Provably correct automatic sub-differentiation for qualified programs. In Advances in Neural Information Processing Systems, pp.\ 7125--7135, 2018

  10. [18]

    Iterative regularization methods for nonlinear ill-posed problems, volume 6

    Kaltenbacher, B., Neubauer, A., and Scherzer, O. Iterative regularization methods for nonlinear ill-posed problems, volume 6. Walter de Gruyter, 2008

  11. [19]

    A theoretical framework for back-propagation

    LeCun, Y., Touresky, D., Hinton, G., and Sejnowski, T. A theoretical framework for back-propagation. In Proceedings of the 1988 connectionist models summer school, volume 1, pp.\ 21--28, 1988

  12. [20]

    Lewis, A. S. and Wright, S. J. A proximal method for composite minimization. Mathematical Programming, 158: 0 501--546, 2016

  13. [21]

    and Todorov, E

    Li, W. and Todorov, E. Iterative linear quadratic regulator design for nonlinear biological movement systems. In 1st International Conference on Informatics in Control, Automation and Robotics, volume 1, pp.\ 222--229, 2004

  14. [22]

    and Todorov, E

    Li, W. and Todorov, E. Iterative linearization methods for approximately optimal control and estimation of non-linear stochastic system. International Journal of Control, 80 0 (9): 0 1439--1453, 2007

  15. [23]

    and Shoemaker, C

    Liao, L.-Z. and Shoemaker, C. A. Convergence in unconstrained discrete-time differential dynamic programming. IEEE Transactions on Automatic Control, 36 0 (6): 0 692--706, 1991

  16. [24]

    and Shoemaker, C

    Liao, L.-Z. and Shoemaker, C. A. Advantages of differential dynamic programming over N ewton's method for discrete-time optimal control problems. Technical report, Cornell University, 1992

  17. [25]

    A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems

    Mayne, D. A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems. International Journal of Control, 3 0 (1): 0 85--95, 1966

  18. [26]

    Modified G auss- N ewton scheme with worst case guarantees for global performance

    Nesterov, Y. Modified G auss- N ewton scheme with worst case guarantees for global performance. Optimization Methods & Software, 22 0 (3): 0 469--483, 2007

  19. [27]

    and Wright, S

    Nocedal, J. and Wright, S. J. Numerical Optimization. Springer, 2nd edition, 2006

  20. [28]

    Catalyst for gradient-based nonconvex optimization

    Paquette, C., Lin, H., Drusvyatskiy, D., Mairal, J., and Harchaoui, Z. Catalyst for gradient-based nonconvex optimization. In 21st International Conference on Artificial Intelligence and Statistics, pp.\ 1--10, 2018

  21. [29]

    Automatic differentiation in P y T orch, 2017

    Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A. Automatic differentiation in P y T orch, 2017. URL https://pytorch.org/

  22. [30]

    A tour of reinforcement learning: The view from continuous control

    Recht, B. A tour of reinforcement learning: The view from continuous control. Annual Review of Control, Robotics, and Autonomous Systems, 2018

  23. [31]

    N., and Morari, M

    Richter, S., Jones, C. N., and Morari, M. Computational complexity certification for real-time MPC with input constraints based on the fast gradient method. IEEE Transactions on Automatic Control, 57 0 (6): 0 1391--1403, 2012

  24. [32]

    and Bobrow, J

    Sideris, A. and Bobrow, J. E. An efficient sequential linear quadratic algorithm for solving nonlinear optimal control problems. In Proceedings of the American Control Conference, pp.\ 2275--2280, 2005

  25. [33]

    Synthesis and stabilization of complex behaviors through online trajectory optimization

    Tassa, Y., Erez, T., and Todorov, E. Synthesis and stabilization of complex behaviors through online trajectory optimization. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp.\ 4906--4913. IEEE, 2012

  26. [34]

    Control-limited differential dynamic programming

    Tassa, Y., Mansard, N., and Todorov, E. Control-limited differential dynamic programming. In IEEE International Conference on Robotics and Automation, pp.\ 1168--1175, 2014

  27. [35]

    and Li, W

    Todorov, E. and Li, W. Optimal control methods suitable for biomechanical systems. In Proceedings of the 25th Annual International Conference of the IEEE, volume 2, pp.\ 1758--1761, 2003

  28. [36]

    and Li, W

    Todorov, E. and Li, W. A generalized iterative lqg method for locally-optimal feedback control of constrained nonlinear stochastic systems. In Proceedings of the American Control Conference, pp.\ 300--306, 2005

  29. [37]

    Optimization over Time

    Whittle, P. Optimization over Time. John Wiley & Sons, Inc., New York, NY, USA, 1982

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.