{"id":"1cac5df1-4464-425f-b28b-46d3d8fac4b9","arxiv_id":"2608.08979","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A randomized two-point direct-search algorithm for nonconvex time-varying optimization with inexact bandit feedback reaches epsilon-stationarity in O(p/epsilon^2) iterations under constant probing, and O(p/epsilon^2 log^2(sqrt(p)/epsilon)) iterations under diminishing probing.","lead":"The paper gives a randomized two-query-per-step direct-search algorithm for nonconvex optimization problems whose objectives change over time, with convergence guarantees that tolerate noisy measurements. It is worth reading because it supplies the first explicit iteration-complexity bounds for direct search in online nonconvex bandit settings, with a concrete connection to feedback control and equilibrium selection.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's sup-norm drift and oracle-error assumptions over R^p are violated by its own examples and simulations: a time-varying linear term and the quadratic control cost make d_t (and often b_t) infinite, so the main complexity theorems are vacuous exactly where the paper claims applicability.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: the global sup-norm drift and oracle-error measures over R^p, together with the global y-Lipschitz condition on Psi, are incompatible with the paper's own examples and Section 6 numerics. The main theorem is proven correctly under those assumptions; the issue is that the assumptions exclude the problem class the paper claims to address. This warrants a conditional acceptance: the mathematical argument is sound, but the paper should either restrict the domain to a bounded set U, replace sup-norm drift and oracle error with pointwise or expectation-based measures, or change the examples and simulation terminal cost so that Assumptions 2.1 and 4.3 are actually satisfied. The absence of shipped code makes the numerical validation difficult to audit independently, though the reported decay rates are consistent with the theorem's predictions when condition (3.21) is met. My read does not change the verdict: CONDITIONAL remains appropriate, so no adjustment is needed.","tokens_in":27054,"tokens_out":13285,"duration_ms":125648,"concrete_test":"Analytically compute d_t for the Section 6 model objective (6.3): whenever w_{t+1} differs from w_t and G^T H (w_{t+1}-w_t) is nonzero, d_t = sup_{u in R^p} gamma |2 u^T G^T H (w_{t+1}-w_t) + ||H w_{t+1}||^2 - ||H w_t||^2| is infinite, so D_T is infinite and the right-hand side of (3.1) becomes infinite. This single computation settles that the standing assumption after (2.1) is violated by the paper's own numerical model. As a complementary check, re-derive Theorem 3.1 with pointwise one-step drifts at the queried points to see whether the finite decay observed in Figure 2 can be certified under the weaker condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.1 is the load-bearing result, and its proof is internally sound: the potential-function argument and Gaussian one-sided moment lemma check out, and the D_T and B_T terms correctly bound cumulative drift and oracle error. The problem is the standing definition of these quantities. Equations (2.1) and (2.3) define d_t and b_t as suprema over the whole of R^p, and the footnote after (2.1) explicitly keeps R^p to avoid projections. For any problem whose temporal variation is an affine or quadratic perturbation of the decision variable, exactly the structure of the control application, these suprema are infinite. Example 2.2(ii) with a_{t+1} not equal to a_t gives d_t = sup_{u in R^p} |(a_{t+1}-a_t)^T u| = +infinity, so D_T = +infinity and every bound in (3.1), (3.2), (3.14), and (3.24) has an infinite right-hand side. The same holds for the simulation objective (6.3): Phi_{t+1}(u)-Phi_t(u) is linear in u, so d_t is infinite unless G^T H (w_{t+1}-w_t) = 0. In addition, Assumption 4.3 requires Psi to be globally L_{Psi,y}-Lipschitz in y, but (6.1) is quadratic in y with unbounded gradient in y, so Lemma 4.7 and Corollaries 4.10 and 4.11 do not apply to the reported numerics. This is not a contradiction inside the proof of Theorem 3.1; it is a mismatch between the assumptions and the paper's stated scope, and it makes the headline complexity claims carry no information for the paper's own examples. A trajectory-dependent or bounded-domain reformulation of D_T and B_T would repair the mismatch without changing the descent argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a randomized two-point direct-search algorithm for time-varying nonconvex optimization under inexact zeroth-order feedback. The main theoretical result is Theorem 3.1, a potential-function bound on the cumulative expected gradient norm in terms of the initial gap, the probing ratios, the cumulative temporal drift D_T, and the cumulative oracle error B_T. The paper then derives iteration-complexity bounds under constant and diminishing probing ratios, claims to recover classical zeroth-order rates in the time-invariant case, and applies the framework to feedback optimization and equilibrium selection in dynamical systems. The proof of Theorem 3.1 is structurally sound: the descent inequality (3.8) follows from Lemma A.2, the drift terms telescope, and the complexities follow from the stated choices of delta. The central weakness is that the standing definitions of drift and oracle error as suprema over the whole of R^p are violated by the paper's own examples and numerical experiments, so the headline complexity claims are vacuous for those instances.","tokens_in":27394,"tokens_out":3376,"duration_ms":35393,"significance":"If the assumptions were repaired, the paper would make a genuine contribution: it would give the first direct-search iteration complexity for time-varying nonconvex bandit optimization, with an explicit dependence on drift and oracle error, and it would recover static zeroth-order rates in the limit of zero drift and zero oracle error. The control application is also natural, and the trajectory-dependent reformulation in Remark 4.9 and Lemma 4.13 is an interesting step toward making the bounds meaningful. However, the current formulation of d_t and b_t as global suprema over R^p is not a cosmetic issue: it invalidates the applicability of the main theorems to the motivating examples, including the linear-perturbation drift model and the quadratic control cost used in the simulations. The central proof mechanism is sound, but the assumptions need to be reformulated before the advertised claims are supported.","major_comments":[{"comment":"The definition d_t = sup_{u in R^p} |Phi_{t+1}(u) - Phi_t(u)| is infinite for the paper's own drift examples. For the time-varying linear perturbation Phi_t(u) = Phi(u) + a_t^T u in Example 2.2(ii), d_t = sup_u |(a_{t+1}-a_t)^T u| = +infinity unless a_{t+1}=a_t. The sentence following the example, claiming d_t <= sup_u ||u|| ||a_{t+1}-a_t||, is therefore incorrect as written because sup_u ||u|| is infinite. Since D_T is built from such d_t, every bound in (3.1), (3.2), (3.14), and (3.24) has an infinite right-hand side for these instances, and the convergence conditions (3.11) and (3.21) cannot be satisfied. This is not a flaw in the proof of Theorem 3.1, but it makes the headline complexity claims carry no information for the paper's own examples.","section":"Eq. (2.1), footnote after (2.1), Example 2.2(ii)"},{"comment":"The same global-supremum issue affects the numerical experiments. The exact oracle (6.3) satisfies Phi_{t+1}(u) - Phi_t(u) = gamma(||Gu+Hw_{t+1}||^2 - ||Gu+Hw_t||^2), which is a nonconstant linear function of u, so d_t = +infinity whenever G^T H(w_{t+1}-w_t) is nonzero. The inexact oracle (6.4) has the same structure. Consequently, the simulated problem does not satisfy the standing finiteness assumption d_t < infinity, and the theoretical guarantees of Theorems 3.2, 3.4, and 4.14 do not apply to the reported experiments. A trajectory-dependent or bounded-domain reformulation of D_T and B_T, as partially anticipated in the footnote after (2.1), is needed.","section":"Eq. (2.3) and simulation objective (6.3)"},{"comment":"Assumption 4.3 requires Psi(u,y) to be globally L_{Psi,y}-Lipschitz in y, but the terminal cost used in the simulations, Psi(u,y) = u^T R1 u + R2^T u + gamma ||y||^2, is not globally Lipschitz in y on R^q because its gradient in y is 2 gamma y, which is unbounded. This means that Lemma 4.7, Corollary 4.10, Corollary 4.11, and Theorem 4.14 do not apply to the numerical setting. The paper should either use a bounded domain, a locally Lipschitz argument with bounded iterates, or a different terminal cost that satisfies the stated global Lipschitz condition.","section":"Assumption 4.3 and Lemma 4.7"}],"minor_comments":[{"comment":"The displayed bound 'd_t <= sup_u ||u|| ||a_{t+1}-a_t||' should be replaced by a correct statement: d_t = +infinity unless a_{t+1}=a_t. This will help readers see that the example is not admissible under the standing assumption.","section":"Example 2.2(ii)"},{"comment":"The green curve is labelled 'upper bound' in the legend, but the text in Section 6.1 correctly states that it is an empirical surrogate, not a certified upper bound. The legend should be changed to avoid giving readers the impression that the displayed quantity is a proven bound.","section":"Figure 2"},{"comment":"The sentence 'By iterating the arguments in the proof of Theorem 3.2' omits the derivation of the bound on the first two terms of (3.24) from condition (3.22). The result is plausible and the statement is correct, but a few lines of algebra would make the proof self-contained.","section":"Proof of Theorem 3.4"},{"comment":"There is a typo in the abstract: 'methods in this seting' should be 'methods in this setting'.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The paper's central proof is sound, but the assumptions are the bottleneck. My main concern is the mismatch between the global-supremum definitions of d_t and b_t and the examples in the paper, which are infinite for the paper's own drift and simulation models. This is fixable by reformulating D_T and B_T as trajectory-dependent quantities or by restricting the domain to a bounded set, and the paper already contains a trajectory-dependent version (B_fo_T in Section 4). I would therefore recommend major revision rather than rejection, provided the authors either restrict the domain, reformulate the drift and oracle-error assumptions, or clearly state the theorems only for problems where the global suprema are finite and give separate treatment for the control examples."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the potential-function analysis is correct and the method is genuinely new, but the paper's own examples violate its standing assumptions on drift and oracle error, so the headline complexity bounds are vacuous for the motivating applications.\n\nThe paper gives a randomized two-point accept/reject direct-search method for nonconvex time-varying optimization with an inexact zeroth-order oracle. Theorem 3.1 is a clean potential-function bound: cumulative expected gradient norm over even iterates is bounded by the initial gap, a sum of squared probing radii, and 2D_T + 2B_T. I went through the proof and the algebra is sound. The Gaussian one-sided moment lemma is exactly the right tool, the drift and oracle-error terms telescope correctly, and Theorems 3.2 and 3.4 follow from the stated choices of delta. The diminishing-probing case recovers the static O(p epsilon^{-2} log^2) rate when D_T and B_T vanish. That is a genuine extension, and the comparison with static STP [2] and steady-state direct search [15] is fair.\n\nThe soft spot is the definition of d_t and b_t as suprema over all of R^p. Equation (2.1) requires d_t < infinity, but Example 2.2(ii), a time-varying linear perturbation, gives d_t = +infinity unless a_t is constant. The simulation objective (6.1) is quadratic in y, so Psi is not globally L_{Psi,y}-Lipschitz in y; Assumption 4.3 does not hold for the reported numerics. This is not a flaw in the proof of Theorem 3.1, which is correctly conditional, but it means the headline complexity claims carry no information for the paper's own motivating examples. The fix is straightforward: work on a bounded domain, or redefine d_t and b_t as trajectory-dependent quantities, as Remark 4.9 already anticipates for B_T. Without that repair, the control application with quadratic terminal costs is not actually covered.\n\nMinor points: Proposition 3.8's regret comparison is quick and requires a bounded-gradient assumption stronger than needed elsewhere; no code is shipped, so the numerics are not independently checkable, though the plots look consistent with the stated rates.\n\nThis paper deserves a serious referee. The proof technique is worth keeping and the novelty is real. But the revision must reconcile the assumptions with the examples, probably by restricting the domain to a compact set or by reformulating drift and oracle error along the trajectory. I would send it to review with that expectation.","headline":"A correct potential-function bound for online direct search, but the sup-norm drift assumption is violated by the paper's own examples; a bounded-domain or trajectory-dependent reformulation would repair it.","tokens_in":27991,"tokens_out":4787,"would_cite":false,"duration_ms":42329,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C56","90C60","93C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a two-query direct-search algorithm finds near-stationary points in time-varying nonconvex optimization, with explicit dependence on drift and oracle noise.","keywords":["direct search","bandit feedback","zeroth-order optimization","time-varying nonconvex optimization","iteration complexity","inexact oracle","feedback optimization","equilibrium selection"],"falsifier":"Take $p=1$, $\\Phi_t(u)=u^2+a_t u$ with $a_{t+1}-a_t=1$, and an exact oracle. The paper's definition gives $d_t=\\sup_{u\\in\\mathbb{R}}|u|=\\infty$ for every $t$, so $D_T=\\infty$ and Theorem 3.2's premise $E_T\\le\\varepsilon^2/(9\\pi p L_{\\nabla\\Phi})$ cannot hold; observing that the algorithm still tracks the moving minimizer would show the gap is in the worst-case drift measure, not necessarily in the method. Conversely, running the algorithm on a bounded interval $[-M,M]$ where $d_t$ is finite and checking whether the empirical $\\varepsilon$-complexity matches $O(p\\varepsilon^{-2})$ would verify or refute the mechanism under its stated assumptions.","tokens_in":26790,"feed_emoji":"🎯","tokens_out":7977,"duration_ms":70026,"temperature":0.7,"pith_summary":"This paper seeks to show that direct search, meaning accept-or-reject probing along random directions, can work when the objective changes between queries and only noisy function values are available. The authors propose a randomized two-point method that evaluates the loss at the current point and one perturbed point per step, accepts the move if it lowers the measured value, and prove that after $T$ steps the best expected gradient norm among even iterates is controlled by the initial suboptimality, the probing radii, and two cumulative error terms: temporal drift $D_T$ and oracle inexactness $B_T$. With constant probing radius this yields $\\varepsilon$-stationarity in $O(p\\varepsilon^{-2})$ iterations, and with diminishing radius $\\delta_t=1/\\sqrt{t+1}$ in $O(p\\varepsilon^{-2}\\log^2(\\sqrt{p}/\\varepsilon))$ iterations, under conditions on how fast drift and oracle error can grow. A sympathetic reader should care because this extends classical zeroth-order direct-search guarantees to the online, time-varying regime where only bandit feedback is available, and gives the first such iteration-complexity bounds for direct search in that setting.","feed_headline":"Two probes per step reach near-stationary points in drifting nonconvex problems","feed_subtitle":"New bounds match static zeroth-order rates and make the cost of drift and oracle noise explicit.","key_machinery":"The load-bearing identity is the Gaussian one-sided moment calculation: for $v\\sim\\mathcal{N}(0,I_p/p)$ and any nonzero $g$, $\\mathbb{E}[(-\\langle g,v\\rangle)_+]=\\|g\\|/\\sqrt{2\\pi p}$. It converts the expected improvement from one random probe into a signal proportional to the gradient norm, while the accept-reject update guarantees $\\Phi_{t+2}(u_{t+2})\\le\\min\\{\\Phi_t(u_t),\\Phi_t(u_{t+1})\\}$ plus drift and oracle terms. Telescoping this descent inequality over even steps produces the main bound; in the diminishing-probing case, elementary sum estimates on $\\sum \\delta_t$ and $\\sum \\delta_t^2$ supply the logarithmic factor.","core_discovery":"The paper's central claim is Theorem 3.1: for any even horizon $T$, the two-point accept-reject algorithm satisfies $$(1/\\sqrt{2\\pi p})\\sum_{t\\in[T]_2} \\delta_t\\,\\mathbb{E}\\|\\nabla\\Phi_t(u_t)\\| \\le \\Phi_0(u_0)-\\Phi_{\\mathrm{low}} + (L_{\\nabla\\Phi}/4)\\sum_{t\\in[T]_2}\\$delta_t^{2}$ + 2D_T + 2B_T,$$ where $D_T$ sums one-step worst-case drifts $\\sup_u|\\Phi_{t+1}(u)-\\Phi_t(u)|$ and $B_T$ sums worst-case oracle errors $\\sup_u|\\tilde\\Phi_t(u)-\\Phi_t(u)|$. From this inequality, constant probing delivers a point with expected gradient norm at most $\\varepsilon$ in $O(p\\varepsilon^{-2})$ iterations when the average drift plus error is $O(\\varepsilon^2/p)$, and diminishing probing delivers the same in $O(p\\varepsilon^{-2}\\log^2(\\sqrt{p}/\\varepsilon))$ iterations when cumulative drift plus error grows at most $O(\\sqrt{T})$. When drift and error vanish, the bounds recover the static zeroth-order complexity; when applied to feedback control, the oracle is the transient plant output, and the same analysis gives stationarity bounds in terms of disturbance variation and transient/steady-state mismatch.","pith_inferences":["The paper leaves implicit that the worst-case drift $d_t$ is infinite for its own Example 2.2(ii), a time-varying linear term, on $\\mathbb{R}^p$; a natural correction is to re-run the analysis on a bounded feasible set with projections, where the same argument would yield finite $D_T$ and explicit dependence on the set's diameter.","The simulation's quadratic terminal cost (6.1) does not satisfy the global Lipschitz-in-$y$ assumption used in the control section; testing the same algorithm on a globally Lipschitz cost such as $\\sqrt{1+\\|y\\|^2}$ would separate the effect of this assumption from the algorithm's actual behavior.","A testable extension suggested by the numerics is that the plateau level of the gradient norm scales linearly with the disturbance scale $\\sigma$; one could try to prove a matching lower bound for the specific disturbance model, which would show the vanishing-drift condition in Theorem 3.4 is not merely an artifact of the proof technique.","The one-point and three-point variants are only conjectured, and a direct comparison of their empirical constants on the same quadratic plant suggests the three-point method's improvement is a constant factor, matching the paper's guess; deriving the analogue of Theorem 3.1 for those updates would settle the conjecture."],"forward_implications":["Under the constant probing choice $\\delta = 4\\varepsilon/(3\\sqrt{2\\pi p}L_{\\nabla\\Phi})$, the algorithm reaches an $\\varepsilon$-stationary point in $O(p\\varepsilon^{-2})$ iterations, matching the classical dimension and accuracy scalings of static zeroth-order methods.","With diminishing probing $\\delta_t=1/\\sqrt{t+1}$, the algorithm reaches an $\\varepsilon$-stationary point in $O(p\\varepsilon^{-2}\\log^2(L_{\\nabla\\Phi}\\sqrt{p}/\\varepsilon))$ iterations, and if $E_T\\sqrt{T}\\to0$ then the expected gradient norm tends to zero asymptotically.","The constant-probing regime tolerates cumulative drift and oracle error growing linearly with the horizon, while the diminishing-probing regime requires at most $O(\\sqrt{T})$ growth; uniform drift and error bounds translate into explicit conditions such as $d+b\\le \\varepsilon^2/(18\\pi p L_{\\nabla\\Phi})$ or $d+b=O(\\varepsilon/(\\sqrt{pT}))$.","Specialized to feedback optimization, the online oracle using the transient plant output instead of the steady-state map has cumulative error $B_T^{\\mathrm{fo}}=O(\\sqrt{T})$ under constant disturbances, so the same complexity holds and the method selects near-stationary equilibria without waiting for the plant to settle.","The stationarity bounds imply an instantaneous local-regret bound $R_1^{\\mathrm{even}}(T)=O(T)$ for constant probing and $O(\\sqrt{pT}(\\log T+D_T+B_T))$ for diminishing probing."],"supporting_citations":[{"why":"Supplies the static stochastic three-point direct-search baseline whose complexity and probing schedule the paper extends to the time-varying setting.","marker":"[2]"},{"why":"Defines the local-regret framework and the worst-case drift growth $D_T=O(T)$ used for comparison in Section 3.4 and Table 1.","marker":"[22]"},{"why":"Provides the descent-based zeroth-order method with the $O(p\\varepsilon^{-2})$ complexity that the proposed method matches, and the comparison baseline used in simulations.","marker":"[30]"},{"why":"Initiates bandit online convex optimization and provides the smoothing-oracle model used in Example 2.3(i).","marker":"[14]"},{"why":"Formulates feedback optimization and equilibrium selection as time-varying optimization, the control application analyzed in Section 4.","marker":"[4]"},{"why":"Supplies the regularity assumptions for the loss and the residual-feedback oracle context that motivate the inexact-oracle model.","marker":"[38]"},{"why":"Provides the timescale-separation direct-search approach for steady-state optimization against which the online, no-separation method is contrasted.","marker":"[15]"}],"fun_headline_variants":["Two probes per step beat drift: direct search for online nonconvex bandits","Bandit feedback no barrier: direct search tracks nonconvex drift","Two-point search matches static rates when nonconvex drift fades","Direct search handles inexact feedback for drifting nonconvex optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The analysis assumes the one-step drift $d_t=\\sup_{u\\in\\mathbb{R}^p}|\\Phi_{t+1}(u)-\\Phi_t(u)|$ and the oracle error $b_t=\\sup_{u\\in\\mathbb{R}^p}|\\tilde\\Phi_t(u)-\\Phi_t(u)|$ are finite on all of $\\mathbb{R}^p$; this fails for natural instances like a time-varying linear perturbation or the quadratic cost used in the simulations, so when it fails the $D_T$ and $B_T$ terms in the main bound become infinite and the complexity theorems carry no information.","fun_headline_variants_meta":{"raw":{"variants":["Two probes per step beat drift: direct search for online nonconvex bandits","Bandit feedback no barrier: direct search tracks nonconvex drift","Two-point search matches static rates when nonconvex drift fades","Direct search handles inexact feedback for drifting nonconvex optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001626,"raw_usage":{"total_tokens":6528,"prompt_tokens":1064,"completion_tokens":5464,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":5387}},"tokens_in":680,"tokens_out":5464,"duration_ms":41538,"temperature":1.0,"reasoning_tokens":5387,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:19:56.061936+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $p=1$, $\\Phi_t(u)=u^2+a_t u$ with $a_{t+1}-a_t=1$, and an exact oracle. The paper's definition gives $d_t=\\sup_{u\\in\\mathbb{R}}|u|=\\infty$ for every $t$, so $D_T=\\infty$ and Theorem 3.2's premise $E_T\\le\\varepsilon^2/(9\\pi p L_{\\nabla\\Phi})$ cannot hold; observing that the algorithm still tracks the moving minimizer would show the gap is in the worst-case drift measure, not necessarily in the method. Conversely, running the algorithm on a bounded interval $[-M,M]$ where $d_t$ is finite and checking whether the empirical $\\varepsilon$-complexity matches $O(p\\varepsilon^{-2})$ would verify or refute the mechanism under its stated assumptions.","supporting_citations":[{"cited_title":"2024 , pdf =","cited_arxiv_id":null,"evidence_quote":"Provides the timescale-separation direct-search approach for steady-state optimization against which the online, no-separation method is contrasted."}],"review_version":1}