{"id":"cf14eec6-3abe-4e96-8c6c-4858f3d45119","arxiv_id":"1908.07615","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Regularized iterative linear quadratic regulator converges to a stationary point with O(1/epsilon^2) calls to an automatic differentiation oracle, with an accelerated variant under convexity.","lead":"This paper gives convergence guarantees for a regularized version of the iterative linear quadratic regulator, a standard algorithm for nonlinear control. It also shows how the algorithm's steps can be computed with automatic differentiation in machine learning libraries.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Cor 4.4's O(1/epsilon^2) bound is not fully proven: the line-search can accept step-sizes below gamma-hat, so the quoted constant L need not bound the accepted iterates.","rationale":"I read the paper's main contribution as Cor 4.4: regularized ILQR obtains an epsilon-stationary point in O(1/epsilon^2) calls to the regularized Gauss-Newton oracle. The proof structure is standard and essentially sound: Prop 4.1 correctly derives a gradient bound from the sufficient-decrease condition, Lemma 4.2 gives the local model approximation, and Lemma 4.3 shows that sufficiently small step-sizes guarantee the sufficient-decrease condition. The soft spot is the step-size interval used in the final constant. The line-search described in Appendix E starts each trial from the previous accepted step-size and only decreases it, so it is possible for an accepted gamma_k to fall below gamma-hat when a rejected trial jumps past the threshold. In that case gamma_k is no longer in [gamma-hat, gamma_0], and the pointwise factor gamma_k(A + gamma_k^{-1})^2 used in the proof of Prop 4.1 need not be bounded by the quoted L. This makes Cor 4.4 formally unproven as written, although the defect is localized and easily repaired. I do not elevate the reader's chosen weakest assumption, the model lower bound (42) underlying the accelerated O(1/N^2) rate, to the primary concern: that assumption is explicitly stated, it only affects Prop 4.5, and the main non-accelerated complexity guarantee does not need it. The reader did mention the line-search issue in the rationale, so my agreement is partial. Since the identified issue is addressable without changing the qualitative result, the appropriate verdict remains CONDITIONAL, matching the reader's verdict.","tokens_in":35421,"tokens_out":16941,"duration_ms":199401,"concrete_test":"Analytical check: fix A = ell^2_{tilde x,S} L_h + L_g = 1, gamma-hat = 0.1, gamma_0 = 0.2, and rho = 0.5. Evaluate F(gamma) = gamma(A + gamma^{-1})^2 at gamma = 0.05, obtaining 22.0025, and compare with max_{gamma in [0.1,0.2]} F(gamma) = 12.01. Then simulate the line-search of Algorithm 13 on a one-dimensional quadratic composite objective with these constants and an initial point where the trial gamma = 0.2 is rejected while gamma = 0.05 satisfies the sufficient-decrease condition; this is compatible with Lemma 4.2 and Lemma 4.3. If the accepted step-size is gamma = 0.05, the proof of Prop 4.1 cannot use L as defined in Cor 4.4, confirming that the corollary needs either a floor at gamma-hat or a redefinition of L over [min_k gamma_k, gamma_0].","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central non-accelerated guarantee is Cor 4.4: the regularized Gauss-Newton method with a decreasing line-search finds an epsilon-stationary point in O(1/epsilon^2) calls to the regularized Gauss-Newton oracle. The proof of Prop 4.1 bounds the gradient at iterate k by gamma_k (ell^2_{tilde x,S} L_h + L_g + gamma_k^{-1})^2 times the normalized step length, and then controls this by L = max_{gamma in [gamma-hat, gamma_0]} gamma(ell^2_{tilde x,S} L_h + L_g + gamma^{-1})^2. This step requires every accepted step-size to lie in [gamma-hat, gamma_0]. The line-search in Algorithm 13 does not enforce a lower bound of gamma-hat: if a trial gamma > gamma-hat is rejected and rho gamma < gamma-hat, the accepted step-size is below gamma-hat, and subsequent iterations restart from that smaller value. For such a gamma, the factor gamma(A + gamma^{-1})^2 with A = ell^2_{tilde x,S} L_h + L_g can exceed the maximum over [gamma-hat, gamma_0]. For example, with A = 1, gamma-hat = 0.1, gamma_0 = 0.2 and gamma = 0.05, one gets gamma(A + gamma^{-1})^2 = 22.0025, while max over [0.1, 0.2] is 12.01. Thus the constant L quoted in Cor 4.4 is not necessarily a valid bound for the accepted sequence. This is a formal gap in the stated theorem, not merely a loose constant: as written, the proof of the central complexity result does not go through. It is repairable by flooring the line-search at gamma-hat, or by defining L over [min_k gamma_k, gamma_0]. The accelerated O(1/N^2) claim in Prop 4.5 additionally rests on the strong model lower bound (42), which is not verified for the experiments; I regard that as a separate limitation rather than the primary defect in the central O(1/epsilon^2) claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":35969,"tokens_out":11794,"duration_ms":319593,"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":[{"comment":"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.","section":"§4.2, Cor. 4.4 and Appendix E, Algo. 13–14"},{"comment":"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.","section":"§4.3, Prop. 4.5, Eq. (42)"}],"minor_comments":[{"comment":"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.","section":"§5.2"},{"comment":"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.","section":"§2.2, Prop. 2.4"},{"comment":"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.","section":"§4.2, Eq. (41)"}],"recommendation":"major_revision","confidential_remarks":"The main flaw is a formal gap in the link between the line-search pseudocode and the theorem, not a conceptual flaw in the regularized Gauss-Newton framework. I expect the authors can repair it by flooring the line-search at γ̂ and correcting the factor in the sufficient-decrease condition, then restating the theorem. The accelerated-rate assumption should be foregrounded in the revision. The paper fits the scope of the journal and has no citation or attribution problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper delivers more than most theory papers in control: it takes the classic ILQR algorithm and actually pins down a worst-case rate in terms of a natural automatic-differentiation oracle. The composite optimization reformulation is clean, and the regularized Gauss-Newton view of ILQR is the right way to get a convergence guarantee. The O(1/eps^2) bound for regularized ILQR is the first I know of for this family, and the oracle complexity accounting is a service to the field.\n\nThe proofs of Prop 4.1 and Lemmas 4.2-4.3 are standard and I did not find errors. The inclusion of the full dynamic programming details in the appendix is helpful.\n\nThe main soft spot is exactly the one flagged in the stress test. Corollary 4.4 defines L over [gamma-hat, gamma_0], but the line-search in Algorithm 13 only guarantees accepted step-sizes stay above rho*gamma-hat, not gamma-hat. A simple example shows the constant L can be too small. This is a genuine formal gap in the central complexity claim as stated. It is not deep: redefine L over [rho*gamma-hat, gamma_0], or floor the line-search at gamma-hat, and the proof goes through. A referee should ask for that fix, but not treat it as a fatal flaw.\n\nThe accelerated O(1/N^2) rate in Prop 4.5 is conditional on the model lower bound (42), which the proof notes implies f is convex. That is a genuine restriction; for the nonconvex control problems in the experiments, the paper only gets the non-accelerated guarantee. The authors do not overclaim this, but the experiments do not test the convex case, so the accelerated rate is a theoretical possibility, not a demonstrated practical speedup.\n\nExperiments are limited to two problems with tuned step-sizes. They do show stable convergence and the software is public, which is real credit. I would not ask for a large experimental campaign, but a third problem and a non-tuned baseline would strengthen the empirical claim.\n\nOverall: this is a solid, careful paper. The central idea is right, the gap is repairable, and the contribution is worth preserving. I would send it to a serious referee.","headline":"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.","tokens_in":36435,"tokens_out":2958,"would_cite":true,"duration_ms":478140,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49J15","49M37","90C30","90C55"],"pacs":[],"model":"deepseek-v4-flash","headline":"Regularized ILQR converges in O(1/epsilon^2) iterations","keywords":["iterative linear quadratic regulator","regularized Gauss-Newton method","composite optimization","nonlinear control","automatic differentiation oracle","worst-case complexity","Catalyst acceleration","proximal regularization"],"falsifier":"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.","tokens_in":35240,"feed_emoji":"⚙️","tokens_out":10311,"duration_ms":92909,"temperature":0.7,"pith_summary":"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.","feed_headline":"Regularized ILQR converges in O(1/epsilon^2) iterations","feed_subtitle":"Adding a proximal stabilization term to ILQR turns a heuristic into an algorithm with proven complexity bounds.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the ILQR algorithm whose complexity is analyzed and whose missing proximal regularization is supplied.","marker":"Li & Todorov (2004)"},{"why":"Defines the ILQG variant for noisy dynamics and the line-search heuristic without convergence rates.","marker":"Todorov & Li (2005)"},{"why":"Provides the modified Gauss-Newton scheme with worst-case guarantees that motivates regularizing the ILQR model.","marker":"Nesterov (2007)"},{"why":"Supplies the composite-optimization framework and the lemma that the lower-bound model condition (42) implies convexity, used in Proposition 4.5.","marker":"Drusvyatskiy & Paquette (2018)"},{"why":"Provides the Catalyst extrapolation coefficient estimate used in the accelerated rate of Algorithm 1.","marker":"Paquette et al. (2018)"}],"fun_headline_variants":["ILQR with proximal term hits O(1/ε²) complexity guarantee","Proximal stabilization turns ILQR heuristic into a proven algorithm","Regularized ILQR: guaranteed convergence and practical gains","New complexity bound for iterative linear quadratic control","O(1/ε²) complexity for regularized ILQR via Gauss-Newton"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["ILQR with proximal term hits O(1/ε²) complexity guarantee","Proximal stabilization turns ILQR heuristic into a proven algorithm","Regularized ILQR: guaranteed convergence and practical gains","New complexity bound for iterative linear quadratic control","O(1/ε²) complexity for regularized ILQR via Gauss-Newton"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000337,"raw_usage":{"total_tokens":1841,"prompt_tokens":895,"completion_tokens":946,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":511,"completion_tokens_details":{"reasoning_tokens":858}},"tokens_in":511,"tokens_out":946,"duration_ms":8621,"temperature":1.0,"reasoning_tokens":858,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:01:34.964044+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"and Li, W","cited_arxiv_id":null,"evidence_quote":"Defines the ILQG variant for noisy dynamics and the line-search heuristic without convergence rates."},{"cited_title":"Modified G auss- N ewton scheme with worst case guarantees for global performance","cited_arxiv_id":null,"evidence_quote":"Provides the modified Gauss-Newton scheme with worst-case guarantees that motivates regularizing the ILQR model."},{"cited_title":"and Paquette, C","cited_arxiv_id":null,"evidence_quote":"Supplies the composite-optimization framework and the lemma that the lower-bound model condition (42) implies convexity, used in Proposition 4.5."},{"cited_title":"Catalyst for gradient-based nonconvex optimization","cited_arxiv_id":null,"evidence_quote":"Provides the Catalyst extrapolation coefficient estimate used in the accelerated rate of Algorithm 1."}],"review_version":1}