{"id":"c793c470-cf21-4702-aa42-050a1182c14d","arxiv_id":"2411.16074","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Gradient descent with step size alpha in (0, 2/L) globally converges for functions with sector-bounded gradients, proved through a discrete-time passivity argument, with a boundary case treated via the weak passivity theorem.","lead":"This paper uses passivity theory from control engineering to prove when gradient descent, the workhorse optimization algorithm, is stable and converges for a broad class of functions, including some nonconvex ones. It also introduces a scaled variant of gradient descent with variable step size.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The loop-transformed nonlinearity \\barΔ can be set-valued for f∈S_{m,L}, so the strong passivity theorem, stated for operators, does not directly apply without a well-posedness argument.","rationale":"The reader's weakest assumption was the equivalence of the loop transformation. My concern is adjacent but more specific: even if the closed-loop dynamics are preserved, the transformed open-loop system \\barΔ may fail to be a well-defined operator because the positive feedback around a non-monotone, non-Lipschitz gradient can have multiple solutions. This is not merely a presentational issue: Theorem 2 and Definitions 4-5 are stated for operators ℓ2e→ℓ2e, and Lemma 4 only establishes an inequality for pairs (u,y) satisfying the relation, not existence or uniqueness. The scalar example in S_{1,3} demonstrates the failure of single-valuedness for a permissible objective and a permissible D. I do not claim the central convergence result is false: for zero external signals the D terms cancel and the GD trajectory is uniquely recovered, and a direct combination of the passivity inequalities would give the ℓ2 conclusion without needing \\barΔ to be an operator. But the paper's stated proof route is incomplete, and a careful reader cannot follow from Lemma 4 to Theorem 3(i) without an additional well-posedness or relation-based argument. This warrants a conditional verdict: the authors should add a rigorous treatment of the loop-transformed nonlinearity, either proving single-valuedness or explicitly working in a passivity-relation framework. The numerical and gain-scheduling extensions are secondary and do not affect this assessment.","tokens_in":10388,"tokens_out":25923,"duration_ms":244480,"concrete_test":"For f(x) = x² + (1 - cos(x²))/2, f'(x) = x(2 + sin(x²)), m=1, L=3, choose D=0.3 and input \\bar u=1. Compute the roots of F(x) = x(2 + sin(x²)) - (x - 1)/0.3 on the interval [1,3]. If F changes sign on both (1.5,2) and (2.5,3), then \\barΔ is set-valued, confirming that the passivity theorem for operators is not directly applicable. A repair would be either to prove well-posedness of the positive feedback relation for all f∈S_{m,L}, or to state and prove a relation-based version of the strong passivity theorem and show the conclusion still holds for every branch.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section III applies the strong passivity theorem (Theorem 2) to the loop-transformed interconnection of Figure 3, treating \\barΔ as a system mapping ℓ2e to ℓ2e. Lemma 4 proves only an algebraic passivity inequality: whenever \\bar u = u - D y and y = Δ(u), inequality (15) holds. It does not prove that the positive-feedback equation y = ∇f(\\bar u + D y + x*) has a unique solution y for every input \\bar u. This matters because S_{m,L} explicitly contains nonconvex functions whose gradients need not be monotone or Lipschitz, so the fixed-point equation can have multiple solutions even for D < 1/L. A concrete scalar example is f(x) = x² + (1 - cos(x²))/2, with f'(x) = x(2 + sin(x²)) ∈ S_{1,3} and unique minimizer at x=0. Take D=0.3 < 1/3 and \\bar u=1. The equation y = f'(\\bar u + D y) is equivalent to F(x) = x(2 + sin(x²)) - (x-1)/0.3 = 0. Evaluating, F(1.5) > 0, F(2) < 0, F(2.5) < 0, and F(3) > 0, so there are at least two distinct roots and \\barΔ is not single-valued. Thus Theorem 2 cannot be invoked in its stated operator form. The closed-loop GD trajectory itself is well-posed because the D terms cancel in the specific feedback interconnection, so the convergence claim may be repairable; but the proof as written leaves a load-bearing gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a discrete-time passivity-based analysis of the gradient descent (GD) method for functions whose gradients satisfy a sector bound (the class S_{m,L}, which includes nonconvex functions with a unique global minimizer). The GD update is recast as a negative feedback interconnection of an LTI controller G_GD and a static nonlinearity Delta (the shifted gradient). Since G_GD is strictly proper and hence not passive, a loop transformation introduces a feedthrough term D, yielding a modified controller \\bar{G}_GD and a modified nonlinearity \\bar{\\Delta}. Lemma 2 shows \\bar{G}_GD is passive iff D >= alpha/2; Lemma 3 shows Delta is very strictly passive (VSP) with constants epsilon=1/(m+L), delta=mL/(m+L); Lemmas 4 and 5 show \\bar{\\Delta} is VSP for D<1/L and input strictly passive (ISP) for D=1/L when m<L. The strong passivity theorem is then invoked to conclude that for alpha in (0,2/L) the loop signals y1+Du1 and y2 lie in l2, which is used to prove global convergence to the unique minimizer. The weak passivity theorem is invoked for alpha=2/L, yielding only a weaker stability conclusion; this is illustrated with Polyak's counterexample. Finally, a gain-scheduled GD variant with variable step size is proposed and tested numerically.","tokens_in":10753,"tokens_out":13575,"duration_ms":113022,"significance":"If the technical issue identified below is repaired, the paper provides a clean, self-contained passivity derivation of the classical step-size bound 2/L for a class of possibly nonconvex functions. The modular structure (controller passivity condition plus nonlinearity VSP property) is conceptually appealing and may be applicable to other first-order methods. The paper also gives a useful comparison with existing IQC and dissipativity approaches, and the proposed gain-scheduled variant is an interesting extension. The derivations in Lemmas 2-5 are correct as algebraic/inequality statements, and the numerical experiments are carefully done. The main concern is that the proof of the central theorem invokes the strong passivity theorem for an interconnection that is not shown to be well-posed as an operator from l2e to l2e.","major_comments":[{"comment":"The proof of Theorem 3 applies the strong passivity theorem (Theorem 2) to the feedback interconnection of \\bar{G}_GD and \\bar{\\Delta}, but the paper does not establish that \\bar{\\Delta}, defined as the positive feedback interconnection of Delta and D1, is a single-valued operator from l2e to l2e. Lemma 4 only proves an algebraic inequality: whenever y=Delta(u) and \\bar{u}=u-Dy, the inequality (15) holds. For f in S_{m,L}, the equation y=nabla f(\\bar{u}+Dy+x*) can have multiple solutions. A scalar example is f(x)=x^2+(1-cos(x^2))/2, for which f'(x)=x(2+sin(x^2)) lies in the sector [1,3] with unique minimizer x*=0; taking D=0.3<1/3 and \\bar{u}=1 gives at least two distinct solutions y. Thus \\bar{\\Delta} is set-valued, and Theorem 2, stated for operators, cannot be invoked as written. The closed-loop GD trajectory is well-posed because the D terms cancel in the specific interconnection, but this cancellation is not proved, and the proof of the main input-output stability claim therefore has a load-bearing gap. Please add a rigorous well-posedness argument for the closed-loop interconnection of Figure 3, or provide a direct proof of the l2 conclusions using the passivity inequalities (without relying on \\bar{\\Delta} being an operator).","section":null}],"minor_comments":[{"comment":"The statement says the step size satisfies alpha in (0,2/L), but the proof and the subsequent discussion in Section IV.A concern alpha=2/L. The statement should read alpha=2/L (or alpha in (0,2/L] with the endpoint resolved through the weak passivity theorem).","section":null},{"comment":"There is a notation inconsistency in the claim 'y1+Du1 in l2'. The state-space realization of \\bar{G}_GD is given with output y1 = C xi + D u1, so the modified controller output already includes the term D u1. Clarify whether 'y1' denotes the original output xi (in which case y1+Du1 is the modified output) or the modified controller output (in which case the '+Du1' is redundant).","section":null},{"comment":"The equations shown inside the block for \\bar{G}_GD in Figure 3 appear to be the original controller equations (y_k^1 = xi_k), which contradicts the stated realization (A,B,C,D)=(1,alpha,1,D1). Make the figure consistent with the text or clarify that the modified output is y_k^1 + D u_k^1.","section":null},{"comment":"The implication from (20) and (21) to x_k -> x* is correct but terse; it would be clearer to write x_k = (x_k - D nabla f(x_k)) + D nabla f(x_k) and then take limits.","section":null},{"comment":"The condition for the gain-scheduled method, max_{k in T} |s_k| in (0, sqrt(2/L)], is not fully derived. Specify whether the endpoint uses Lemma 5 (ISP) rather than Lemma 4, and state whether \\bar{r}_2=0 is required, as in Theorem 3(ii).","section":null}],"recommendation":"major_revision","confidential_remarks":"The paper is mathematically sound in its algebraic developments, and the central idea of deriving the 2/L step-size bound via passivity is attractive. However, the application of the strong passivity theorem currently has a genuine well-posedness gap: \\bar{\\Delta} can be a relation rather than an operator for the class S_{m,L}. This is not a rejection-level flaw because the closed-loop GD dynamics are well-posed and the passivity inequalities (15) are strong enough to support the conclusion once the argument is made carefully. I recommend requiring the authors to add a well-posedness lemma or an explicit relation-based passivity proof. The notation inconsistencies in Theorem 3 and Figure 3 should also be fixed in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Moalemi and Forbes recast GD as a passive controller in feedback with a very strictly passive shifted gradient, and recover the classical alpha < 2/L condition for f in S_{m,L} via the strong passivity theorem. The passivity derivation is genuinely new even though the convergence region is Polyak's. The weak passivity treatment at alpha = 2/L is a nice boundary extension, and the gain-scheduling variant is a reasonable exercise, though not a major algorithmic contribution.\n\nThe lemmas are correct. Lemma 2 uses the discrete positive real lemma cleanly. Lemma 3's VSP property of the shifted gradient follows from the sector bound. Lemmas 4 and 5 give the right D-bounds. The paper is self-contained and does not lean on circular arguments.\n\nThe soft spot is in the application of the passivity theorem after the loop transformation. The paper treats \\barΔ as an input-output operator, but Lemma 4 only proves an algebraic inequality for pairs (u,y) satisfying y = Δ(u - Dy). It never shows that the positive feedback equation has a unique solution y for every input \\bar u. For S_{m,L} containing nonconvex gradients, uniqueness can fail. The stress-test example f(x)=x^2 + (1-cos(x^2))/2 with D=0.3 and \\bar u=1 gives at least two solutions. This means the strong passivity theorem cannot be invoked in its stated operator form. The closed-loop GD dynamics themselves are well-posed because the D terms cancel in the specific interconnection, so the convergence result may be repairable, but the proof as written has a load-bearing gap. I'd want the authors to add a well-posedness argument, or switch to the relational passivity framework that handles set-valued maps.\n\nAlso minor: Theorem 3(ii) has a typo in the stated step-size range; it should be alpha in (0, 2/L] with alpha=2/L as the interesting case. The gain-scheduled section is under-explored and the numerical comparison is only against simple baselines, but that is fine for a short paper.\n\nOverall, this is a worthwhile paper for a control-theoretic optimization audience. It deserves peer review, with a request for revision addressing the well-posedness of \\barΔ and the typos. I would cite it in my own work on passivity-based algorithm analysis.","headline":"A clean passivity-based proof of the classical GD step-size bound, with a real well-posedness gap in the loop-transformed nonlinearity that a revision should fix.","tokens_in":11264,"tokens_out":2384,"would_cite":true,"duration_ms":20543,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93D10","93C55","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Passivity-based proof shows gradient descent converges for step sizes below 2/L.","keywords":["gradient descent","passivity-based analysis","input-output stability","sector-bounded gradient","very strictly passive","loop transformation","gain scheduling","global convergence"],"falsifier":"Run gradient descent on the paper's nonconvex example $f(x)=\\frac{L-m}{4}\\left(\\frac{L+m}{L-m}x^2+2\\sin x-2x\\cos x\\right)$ with $m=1$, $L=100$, using step $\\alpha=1.99/L$ from any initial condition; the theorem predicts convergence of $x_k$ to $x^*$, so observing $x_k$ stay bounded away from $x^*$ or diverge for a single initial condition would falsify the claim. Alternatively, directly test the very strict passivity inequality $\\langle u_2,y_2\\rangle_T\\ge \\delta\\|u_2\\|_{2T}^2+\\varepsilon\\|y_2\\|_{2T}^2$ for $\\Delta$ on a long finite horizon; a violation would refute Lemma 3.","tokens_in":56,"feed_emoji":"📉","tokens_out":5873,"duration_ms":115785,"temperature":0.7,"pith_summary":"Gradient descent iterates as $x_{k+1}=x_k-\\alpha\\nabla f(x_k)$, and the paper proves that for continuously differentiable functions whose gradient lies in a sector between slopes $m$ and $L$ and that have a unique minimizer, the method is input-output stable and globally convergent for every step size $\\alpha\\in(0,2/L)$. The proof recasts the algorithm as a feedback system: a linear controller in negative feedback with the gradient nonlinearity, then applies a loop transformation so the controller becomes passive. Because the shifted gradient is very strictly passive for this function class, the strong passivity theorem yields square-summable signals, and those signal bounds imply $\\nabla f(x_k)\\to 0$ and $x_k\\to x^*$. The result recovers the classical step-size bound for $L$-smooth functions and extends it to a class that may include nonconvex objectives with sector-bounded gradients.","feed_headline":"Passivity proof shows gradient descent converges below step size 2/L","feed_subtitle":"A feedback-control argument proves global convergence for a nonconvex function class, up to the classical 2/L step-size limit.","key_machinery":"The central object is the loop-transformed feedback representation of gradient descent: an LTI controller with state $\\xi_{k+1}=\\xi_k+\\alpha u_1^k$ and output $y_1^k=\\xi_k$, in negative feedback with the static memoryless nonlinearity $\\Delta$. Because the original controller is strictly proper and therefore cannot be passive, a loop transformation inserts a feedthrough term $D$, yielding a modified controller $\\bar{G}_{\\mathrm{GD}}$ and a modified nonlinearity $\\bar{\\Delta}$; this transformation preserves the closed-loop dynamics. The load-bearing identities are the sector inequality from (2), which makes $\\Delta$ very strictly passive, and the discrete positive-real LMI in Lemma 1, which yields the passivity condition $D\\ge\\alpha/2$. The strong passivity theorem then converts the dissipated energy into $\\ell_2$ signal bounds, and those bounds produce convergence.","core_discovery":"The central claim is that gradient descent is a negative feedback interconnection between a modified linear time-invariant controller $\\bar{G}_{\\mathrm{GD}}$ with feedthrough $D=\\alpha/2$ and the shifted gradient nonlinearity $\\Delta: u_2\\mapsto \\nabla f(u_2+x^*)$. Lemma 2 shows $\\bar{G}_{\\mathrm{GD}}$ is passive if and only if $D\\ge \\alpha/2$. Lemma 3 shows that for $f\\in S_{m,L}$, $\\Delta$ is very strictly passive with $\\delta=mL/(m+L)$ and $\\varepsilon=1/(m+L)$. Lemma 4 shows the positive feedback interconnection of $\\Delta$ with $D$ remains very strictly passive when $D<1/L$. Combining these with the strong passivity theorem gives $y_1+Du_1\\in\\ell_2$ and $y_2\\in\\ell_2$ for $\\alpha\\in(0,2/L)$; Section IV.A interprets these $\\ell_2$ bounds as $\\nabla f(x_k)\\to 0$ and $x_k-D\\nabla f(x_k)\\to x^*$, hence $x_k\\to x^*$. For $m<L$ and $\\alpha=2/L$, $\\bar{\\Delta}$ is only input strictly passive, so the weak passivity theorem guarantees $y_1+Du_1\\in\\ell_2$ but not pointwise convergence; the paper proposes the stopping criterion $\\|\\nabla f(x_k)+\\nabla f(x_{k-1})\\|_2^2<\\epsilon$. It then gain-schedules the passive controller to obtain a variable-step-size variant $x_{k+1}=x_k-s_k\\nabla f(s_kx_k)$ and numerically tests it on a nonconvex sector-bounded example with $m=1$, $L=100$.","pith_inferences":["The explicit energy parameters $\\delta=mL/(m+L)$ and $\\varepsilon=1/(m+L)$ suggest that convergence-rate estimates for this nonconvex class could be derived from the passivity inequalities themselves, although the paper does not provide explicit rates.","The same loop-transformation argument could be applied to strictly proper momentum-type updates by replacing the scalar feedthrough $D$ with a matrix feedthrough and solving the analogous LMI; this is a natural extension the paper leaves implicit.","For the boundary case $\\alpha=2/L$, the two-dimensional example suggests that Ces\\`aro averages of the iterates might still converge to $x^*$; a testable conjecture is that averaged iterates converge even when pointwise convergence fails.","The time-varying scheduling function $s_k$ defines a genuinely new algorithm when $s_k$ is not constant, and its convergence behavior could be tuned further, for example by scheduling $s_k$ based on the local gradient magnitude."],"forward_implications":["For every $f\\in S_{m,L}$, including nonconvex functions with sector-bounded gradients, gradient descent is globally convergent for all $\\alpha\\in(0,2/L)$ without assuming a separate Lipschitz-gradient condition.","For $m<L$, the boundary step size $\\alpha=2/L$ remains input-output stable, so the practical stopping rule based on consecutive gradients $\\nabla f(x_k)+\\nabla f(x_{k-1})$ being small is justified even though the iterates may oscillate without converging.","The gain-scheduled variant $x_{k+1}=x_k-s_k\\nabla f(s_kx_k)$ is input-output stable whenever $\\max_k |s_k|\\in(0,\\sqrt{2/L})$; for constant $s$ it reduces to standard gradient descent with step size $s^2$.","The analysis gives a systematic recipe for other first-order algorithms: cast the algorithm as a feedback interconnection, solve the passivity LMI for the minimal feedthrough, compare with the sector bounds, and apply the weak or strong passivity theorem.","The passivity framework extends stability guarantees known for strongly convex $L$-smooth functions to the larger sector-bounded nonconvex class, matching the classical convergence region of gradient descent at the $2/L$ limit."],"supporting_citations":[{"why":"Supplies the sector-bound inequality in (2) that makes the shifted gradient very strictly passive.","marker":"[9]"},{"why":"Supplies the definitions of passivity, $\\ell_2$ stability, and the weak and strong passivity theorems used for the main stability conclusions.","marker":"[13]"},{"why":"Provides the discrete positive-real lemma used in Lemma 2 to derive the passivity condition $D\\ge\\alpha/2$.","marker":"[14]"},{"why":"Establishes the feedback-control interpretation for first-order optimization methods and the function class $S_{m,L}$.","marker":"[5]"},{"why":"Provides the classical convergence analysis and the counterexample for $\\alpha\\ge2/L$, which motivates the stopping criterion and the boundary discussion.","marker":"[18]"},{"why":"Supports the claim that a strictly proper discrete-time system cannot be passive, motivating the loop transformation.","marker":"[16]"},{"why":"Supplies the gain-scheduling architecture adapted in Section IV.B for the new variable-step-size gradient descent variant.","marker":"[12]"},{"why":"Provides the equivalence between positive realness and passivity for LTI systems used when applying Lemma 1.","marker":"[15]"}],"fun_headline_variants":["Passivity proof shows gradient descent converges below 2/L","Gradient descent as passive feedback guarantees convergence","New step-size rule from passivity theory for larger steps","Variable step-size gradient descent from passivity theory"],"cache_read_input_tokens":13312,"weakest_assumption_plain":"The loop transformation shown in Figure 3 is assumed to preserve the closed-loop dynamics of the original gradient descent update while adding the feedthrough term $D$; if this equivalence failed, the passivity-based stability conclusions would not apply to the actual algorithm.","fun_headline_variants_meta":{"raw":{"variants":["Passivity proof shows gradient descent converges below 2/L","Gradient descent as passive feedback guarantees convergence","New step-size rule from passivity theory for larger steps","Variable step-size gradient descent from passivity theory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0012,"raw_usage":{"total_tokens":5006,"prompt_tokens":1063,"completion_tokens":3943,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":679,"completion_tokens_details":{"reasoning_tokens":3881}},"tokens_in":679,"tokens_out":3943,"duration_ms":24532,"temperature":1.0,"reasoning_tokens":3881,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:35:15.922253+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run gradient descent on the paper's nonconvex example $f(x)=\\frac{L-m}{4}\\left(\\frac{L+m}{L-m}x^2+2\\sin x-2x\\cos x\\right)$ with $m=1$, $L=100$, using step $\\alpha=1.99/L$ from any initial condition; the theorem predicts convergence of $x_k$ to $x^*$, so observing $x_k$ stay bounded away from $x^*$ or diverge for a single initial condition would falsify the claim. Alternatively, directly test the very strict passivity inequality $\\langle u_2,y_2\\rangle_T\\ge \\delta\\|u_2\\|_{2T}^2+\\varepsilon\\|y_2\\|_{2T}^2$ for $\\Delta$ on a long finite horizon; a violation would refute Lemma 3.","supporting_citations":[{"cited_title":"Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints,","cited_arxiv_id":null,"evidence_quote":"Supplies the sector-bound inequality in (2) that makes the shifted gradient very strictly passive."},{"cited_title":"Desoer and M","cited_arxiv_id":null,"evidence_quote":"Supplies the definitions of passivity, $\\ell_2$ stability, and the weak and strong passivity theorems used for the main stability conclusions."},{"cited_title":"Discrete Positive-Real Functions and their Application to System Stability,","cited_arxiv_id":null,"evidence_quote":"Provides the discrete positive-real lemma used in Lemma 2 to derive the passivity condition $D\\ge\\alpha/2$."},{"cited_title":"Control Interpretations for First-Order Opti- mization Methods,","cited_arxiv_id":null,"evidence_quote":"Establishes the feedback-control interpretation for first-order optimization methods and the function class $S_{m,L}$."},{"cited_title":"Polyak, Introduction to Optimization","cited_arxiv_id":null,"evidence_quote":"Provides the classical convergence analysis and the counterexample for $\\alpha\\ge2/L$, which motivates the stopping criterion and the boundary discussion."},{"cited_title":"Losslessness, Feedback Equivalence, and the Global Stabilization of Discrete-Time Nonlinear Systems,","cited_arxiv_id":null,"evidence_quote":"Supports the claim that a strictly proper discrete-time system cannot be passive, motivating the loop transformation."},{"cited_title":"Gain-Scheduled SPR Controllers for Nonlinear Flexible Systems,","cited_arxiv_id":null,"evidence_quote":"Supplies the gain-scheduling architecture adapted in Section IV.B for the new variable-step-size gradient descent variant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the equivalence between positive realness and passivity for LTI systems used when applying Lemma 1."}],"review_version":1}