{"id":"03e5d9b5-bdf7-4e2d-948e-b743820227c2","arxiv_id":"2411.11732","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A distributed asynchronous block coordinate descent algorithm tracks time-varying quadratic programs with bounded error when objective sampling, computation, and communication are all asynchronous.","lead":"A multi-agent optimization paper proves that time-varying quadratic programs can be tracked with bounded error even when agents sample, compute, and communicate asynchronously. It addresses an open problem in time-varying optimization and could simplify deployments where sampling clocks cannot be synchronized.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's proof misapplies Lemma 2: it bounds minimizer distance, not the value gap |g(x*)-f*|; a permitted constant offset in g makes the claimed error bound false for large offsets.","rationale":"The reader's identified weakness, Assumption 7 and the uncomputable k_hat_z, is a genuine scope limitation and would justify a CONDITIONAL verdict if the proof were otherwise sound. However, the proof of the main theorem has a more fundamental flaw: Lemma 2 bounds the distance between minimizers of two strongly convex functions, while Theorem 3 needs to bound the difference in optimal values between g and f. A constant additive shift in g, which the paper explicitly permits in Assumption 6, changes the value gap arbitrarily without changing any minimizer, so no minimizer-distance bound can control the quantity in (9). The 1D constant-offset example is a permitted instance under the paper's assumptions and makes the theorem's stated inequality fail by orders of magnitude. This is not a matter of missing constants or conservative estimates; the scaling is wrong (the left side is linear in C, while the bounding term grows only as C^{1/(n+2)} in n=1). Therefore the central claim cannot be accepted as proved. If the theorem were reformulated as a bound on ||x - argmin f|| rather than on the cost gap, the constant-offset objection would disappear, but the theorem and the abstract's 'bounded error' claim would need to be restated, and the proof would still need to supply the missing bridge from suboptimality to distance. As written, the main result is unsound.","tokens_in":28366,"tokens_out":29224,"duration_ms":278772,"concrete_test":"Settle by checking the static instance n=1, X=[-1,1], f(x)=x^2/2, g(x)=x^2/2+1000, which satisfies Assumptions 1-6 (and Assumption 7 with kappa_z chosen large). After Algorithm 1 converges, x=0 and the left side of Theorem 3 is 1000. Compute the right side: K1=1/32, K2=max(||f-g||_L2^2, ||f-h||_L2^2) with h=0.5x^2+Mg,z gives K2 approximately 2,002,000, u_bar=1, phi=1, and the first term az rho^{r-1} can be made below 1 for large r_z. The second term evaluates to roughly 25.2, so the claimed inequality 1000 <= 25.2 fails. Alternatively, analytically verify that |h(argmin g)-f*| is not bounded by Lemma 2's minimizer-distance bound, since argmin h=argmin f=0 while the value gap is 1000.5.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim rests on Theorem 3, whose proof bounds |g(x*(tz);tz)-f*(tz)| by invoking Lemma 2. But Lemma 2 bounds ||argmin f - argmin h||, i.e., a distance between minimizers, not a difference between optimal values. This distinction is fatal because Assumption 6 explicitly permits adding constants to objectives. Take n=1, X=[-1,1], f(x)=x^2/2, g(x)=x^2/2+C with C>0. Both are in S with phi=psi=1 and u_bar=1, g>=0, and minimizers coincide at 0, so any distance-based bound is 0. Yet the value gap is |g(0)-f*(0)|=C. The theorem's second term is approximately (4)^{1/6}(2C^2/K1)^{1/6} with K1=1/32, which grows like const*C^{1/3}; for C=1000 it is about 25 while the gap is 1000. The first term az rho^{r-1} can be made arbitrarily small by taking r_z large, so the stated inequality fails. The proof's Case 3 asserts |g(b)-f*| <= |h(b)-f*| and then that Lemma 2 applies to (9); but Lemma 2 gives no control of |h(b)-f*| when b is not argmin h. Thus the bounded-error guarantee is not established and is false as stated.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed asynchronous optimization of time-varying quadratic programs, allowing agents to sample their objectives, compute, and communicate asynchronously. Agents' asynchronous sampling produces an aggregate quadratic objective (Problem 2) that can be nonconvex, even when the original problem is strongly convex (Theorem 1). The authors analyze a projected block coordinate descent algorithm (Algorithm 1) and prove a bounded suboptimality result for tracking the aggregate problem (Theorem 2), then attempt to relate the aggregate problem to the original one via a minimizer-distance bound (Lemma 2) to obtain the main claim (Theorem 3) that the agents' objective value at the iterate tracks the original optimal value within a known error ball. Synchronous special cases are derived as corollaries, and two numerical experiments illustrate the algorithm's performance.","tokens_in":28669,"tokens_out":14441,"duration_ms":151694,"significance":"The asynchronous-sampling problem is well motivated, and the paper introduces a useful modeling framework in which asynchronous objective sampling creates a nonconvex aggregate quadratic program. Theorem 1 gives an explicit, checkable construction of this phenomenon, and the detailed constant-level analysis of asynchronous block coordinate descent is a nontrivial contribution that may be of independent interest. If a correct tracking guarantee could be established, this would be the first bounded-tracking result for distributed time-varying quadratic programs with asynchronous objective sampling. However, the main result connecting the aggregate problem to the original QP (Theorem 3) is not established as stated and is in fact false under the paper's own assumptions; consequently, the advertised open-problem solution is not realized in the current version.","major_comments":[{"comment":"The proof bounds the wrong quantity. Lemma 2 bounds the distance between minimizers of two functions in S, not the difference between their optimal values. In Eq. (9), after bounding alpha by Lemma 1, the remaining term is the value gap |g(x*_k(tz);tz) - f*(tz)|, and Lemma 2 gives no control of this term. The inequality asserted in Case 3, |g(x*_k(tz);tz) - f*(tz)| <= |h(x*_k(tz);tz) - f*(tz)|, is not generally valid: if h(x*_k(tz);tz) < f*(tz), the right-hand side is smaller than the left-hand side. Moreover, the claimed bound contains no factor such as L_g or L_h, so it cannot be obtained by combining Lemma 2 with Lipschitz continuity of the objective. The theorem is false as stated. For example, take X=[-1,1], phi=1, psi=2, f(x)=x^2/2, and g(x)=x^2/2+C with C>0 large. All standing assumptions are satisfied, g is in S and nonnegative, the minimizers of f and g coincide, and the auxiliary h(x)=x^2/2+Mg,z is also in S. The value gap is |g(0)-f*|=C, while the second term of Theorem 3 grows like O(C^{1/3}) and the first term can be made arbitrarily small by taking r_z large. The claimed bounded-value-gap guarantee therefore fails.","section":"Section IV-C, Theorem 3 and its proof"},{"comment":"The auxiliary function h(x;tz)=1/2||x||^2+Mg,z need not belong to the class S defined in Section II. The class S requires 0<phi<psi, but h has Hessian equal to the identity, giving equal strong-convexity and smoothness constants; unless the problem's psi is chosen strictly larger than 1, h is not in S. In addition, the membership condition in S requires the gradient bound u_bar >= max_{x in X} ||x||, which is not guaranteed by the standing assumptions. The assertion in Case 3 that \"f,h are in S for this choice of h\" is therefore unsupported, and Lemma 2 cannot be invoked as written.","section":"Section IV-C, Theorem 3, Case 3"},{"comment":"The claim that the first term on the right-hand side of Eq. (7) goes to zero as z increases because each rho_i lies in (0,1) is not generally true. Lemma 1 and Theorem 2 allow r_z in N_0, so when r_i=0 the exponent r_i-1 is -1 and the corresponding factor rho_i^{-1} is greater than 1; if this happens infinitely often, the product need not vanish. The uniform ultimate boundedness interpretation in Remark 1 is therefore not justified by the displayed argument. The theorem would need either an assumption that r_z >= 1 for all z or a separate argument controlling the accumulated terms.","section":"Section IV-B, Remark 1 and Eq. (7)"},{"comment":"The existence of the time k_hat_z is load-bearing for Assumption 7 and hence for Lemma 1 and Theorem 3, but the proof does not close the gap between Eq. (38) and Eq. (33). Eq. (38) bounds ||s(k)||, the block update at time k, while Lemma 4 and Eq. (33) require a bound on the full projected gradient ||x(k) - Pi_X[x(k) - grad_x g(x(k);tz)]||. The text asserts this implication without showing how the unupdated blocks and stale information are controlled; the beta sums alone do not immediately imply that all block residuals vanish simultaneously. As written, the derivation of k_hat_z is incomplete.","section":"Appendix C, Lemma 19 and Assumption 7"}],"minor_comments":[{"comment":"The constant nu_X is used in the definition of K1 but is never defined geometrically or otherwise; the paper only states nu_X in (0,1). Please provide a definition or a precise citation for this constant from the source of Lemma 2.","section":"Section IV-A and Lemma 2"},{"comment":"Figure 2 is described as comparing Algorithm 1 with a consensus algorithm on an example with N=2 agents, while the main numerical setup in Section V-A uses N=10 agents. Please state the problem parameters used for the comparison in Figure 2 and clarify how the two settings relate.","section":"Section V-A"},{"comment":"The simulations demonstrate qualitative tracking behavior, but they do not compare the empirical suboptimality gap with the bound in Theorem 3. Since the theorem is the paper's central quantitative claim, a comparison (even with conservative estimates of the constants) would help the reader calibrate the result.","section":"Section V"},{"comment":"The axis label in Figure 4 reads \"R efer ence\"; this should be corrected to \"Reference\".","section":"Figure 4"}],"recommendation":"major_revision","confidential_remarks":"I am recommending major revision rather than outright rejection because the paper's underlying problem is well chosen and the analysis of Algorithm 1 for the aggregate problem may be salvageable. However, the current Theorem 3 is false as stated, and the proof cannot be repaired by a local edit. The authors should either replace the value-gap theorem with a minimizer-distance tracking theorem that follows from Lemma 2 plus Lipschitz/error-bound arguments, or add the additional terms and assumptions needed to make the value-gap claim true. The revised manuscript should also address the h-in-S issue and the product-convergence issue in Remark 1 before I could recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe genuinely new thing here is asynchronous objective sampling for distributed time-varying QPs, with the observation (Theorem 1) that asynchrony makes the aggregate problem nonconvex even when the original QP is strongly convex. That is a real phenomenon and the construction is clean. The paper also gives a careful analysis of asynchronous BCD on the aggregate problem (Theorem 2), using standard machinery from Tseng and Luo-Tseng, and the simulations support the qualitative behavior.\n\nThe soft spot is Theorem 3, the claim that agents track the original QP's solution to within a known error ball. The proof misapplies Lemma 2: that lemma bounds the distance between minimizers of two strongly convex functions, not the difference in optimal values. Under Assumption 6, you can add a constant C to one objective without changing its minimizer; the value gap is C, while the distance bound is zero. The example f=x^2/2, g=x^2/2+C with C large shows the stated inequality fails. Case 3 is also invalid: the bound on |h(x*_k)-f*| is not controlled by Lemma 2 since x*_k is not the minimizer of h. So the bounded-error guarantee for the original problem is not established and is false as stated. This is load-bearing, not a cosmetic issue.\n\nThere are minor issues too: Remark 1's claim that the product term in (7) vanishes because each rho_i is in (0,1) is not generally true; products of numbers below 1 can fail to converge to zero. And Assumption 7's dwell time depends on constants that are not computable from problem data, which the paper concedes.\n\nThe paper is worth engaging: Theorem 1 and the aggregate tracking analysis are solid, and the flaw in Theorem 3 might be repairable if restated as a bound on the value gap in terms of the function difference norm without the constant-offset problem. But as written, the main advertised result doesn't hold.\n\nRecommendation: send it to peer review, but the reviewers should focus on Theorem 3 and the constant-offset issue. I would not cite the paper in its current form.","headline":"Asynchronous sampling and the nonconvex aggregate are genuinely new, but Theorem 3 is false as stated: it bounds minimizer distance, not value gaps, and constant offsets break the claimed error ball.","tokens_in":29191,"tokens_out":3907,"would_cite":false,"duration_ms":35360,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C20","90C25","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that multi-agent systems can track the minimizer of a time-varying quadratic program with bounded error even when each agent samples the objective asynchronously, and that a known-size error ball is achievable.","keywords":["asynchronous optimization","time-varying optimization","quadratic programming","distributed optimization","block coordinate descent","nonconvex optimization","tracking error","objective sampling"],"falsifier":"Run Algorithm 1 on a two-agent strongly convex quadratic problem where one agent samples twice as often as the other, shrink the sampling interval so that the objective changes before the iterates reach the required dwell stage $\\hat{k}_z$ (for instance, let the minimizer move at a rate comparable to the algorithm's contraction speed), and measure $|g(x(\\eta_z);t_z) - f^*(t_z)|$ over many sample times; the central claim fails if this error grows without bound or systematically exits the ball predicted by Theorem 3.","tokens_in":28124,"feed_emoji":"🧮","tokens_out":5980,"duration_ms":52987,"temperature":0.7,"pith_summary":"This paper proves that a network of agents can keep tracking the moving minimizer of a time-varying quadratic program even when each agent samples the objective at its own unsynchronized times, on top of asynchronous computation and communication. The paper first shows that asynchronous sampling makes the agents' combined objective behave like a different, possibly nonconvex quadratic program, then proves that a classic asynchronous block coordinate descent algorithm tracks the solutions of that phantom problem with bounded error, and finally bounds the gap between the phantom minimizers and the true ones. The result is a suboptimality bound of the form $a_z \\rho_z^{r_z-1} + (4\\bar{u}/\\phi)^{n/(2n+4)}(K_2/K_1)^{1/(2n+4)}$ for each sampled time $t_z$, so the agents' error stays inside a ball of known size. It answers an open problem in time-varying optimization, though only for quadratic programs and only under a dwell-time assumption that the paper concedes cannot be checked from problem data.","feed_headline":"Async objective sampling still yields bounded QP tracking","feed_subtitle":"Agents sample a moving quadratic objective at different times yet keep error inside a provable ball — an open problem solved.","key_machinery":"The load-bearing mechanism is the asynchronous projected block coordinate descent law $x_i^i(k+1) = \\Pi_{X_i}[x_i^i(k) - \\gamma_z(Q_{[i]}(\\theta_i(t_z))x(k) + r_{[i]}(\\theta_i(t_z)))]$ combined with a partial-asynchrony delay bound $B$. The analysis tracks the suboptimality gap $\\alpha(k;t_z) = g(x(k);t_z) - g(x_k^*(t_z);t_z)$ and the recent-update energy $\\beta(k) = \\sum_{\\tau=k-B}^{k-1}\\|s(\\tau)\\|^2$, and the engine of the proof is an inequality (Lemma 12) of the form $\\alpha(k+B) \\le \\gamma_z^{-2}F_z\\beta(k+B) + \\gamma_z^{-1}G_z\\beta(k)$, which yields the linear contraction rate $\\rho_z = 1-\\gamma_z c_z$. A second engine is Lemma 2, a minimizer-distance bound expressed through the $L^2$ difference of the two objectives, which converts tracking of the phantom problem into tracking of the original one.","core_discovery":"The paper's central claim is that asynchronous objective sampling, previously an open problem in time-varying multi-agent optimization, can be handled for quadratic programs by reusing the classic asynchronous block coordinate descent algorithm without modification. When agents sample the continuously varying objective at different times, each gradient evaluation uses a different snapshot of the data, and the paper shows (Theorem 1) that the agents are then implicitly minimizing an aggregate quadratic program $g(x;t_z)$ that need not be convex. It proves (Theorem 2) that this nonconvex aggregate is still tracked with an error that decays geometrically in the number of update blocks, and it derives (Theorem 3) a bound on $|g(x(\\eta_z);t_z) - f^*(t_z)|$ that combines that tracking error with a minimizer-shift term coming from a new $L^2$-norm bound on how far the aggregate's minimizers lie from the original problem's minimizers. The significance is that no agent needs to know or coordinate the other agents' sampling times; a bounded error guarantee holds anyway.","pith_inferences":["The nonconvex phantom-objective result suggests a general principle: asynchrony in data acquisition converts a convex problem into a nonconvex one at the aggregate level, so the real design question is not algorithm choice but how to control sampling drift; a testable extension is to quantify the largest sampling skew (max $|\\theta_i(t_z)-\\theta_j(t_z)|$) that preserves convexity of the aggregate.","Because $\\hat{k}_z$ is not computable from data, a practitioner cannot verify Assumption 7 before deployment; a natural empirical test is whether a fixed heuristic dwell time (say $\\kappa_z = cB$) yields bounded error in practice, which the paper's theory does not cover.","The minimizer-shift exponent $1/(2n+4)$ means the guaranteed ball grows slowly with dimension; in high-dimensional QPs the bound may be loose even with frequent sampling, suggesting the need for dimension-dependent refinements that the paper does not address.","The same $L^2$-perturbation technique might extend to strongly convex problems beyond quadratics, but it would need an error-bound condition and compact polyhedral structure analogous to Lemmas 4-5, so the quadratic assumption is likely doing real work."],"forward_implications":["Synchronizing sampling across agents sharpens the bound to just $a_z\\rho_z^{r_z-1}$, recovering (up to constants) the linear convergence of earlier time-varying distributed algorithms.","Synchronizing sampling, computation, and communication ($B=1$) recovers the centralized gradient-descent rate for time-varying strongly convex functions, showing the async result generalizes the existing theory.","Agents can sample probabilistically (the simulations use sampling probabilities 0.5 and 0.1) and still keep bounded error, so no coordination of sampling schedules is needed.","Increasing the rate of sampling shrinks the $K_2$ term, and increasing computation/communication activity shrinks the $a_z\\rho_z^{r_z-1}$ term, so the error ball can be tuned by the designer."],"supporting_citations":[{"why":"Supplies the partial-asynchrony model and classic asynchronous block coordinate descent framework, including the projection lemma and delay bound used throughout.","marker":"[10]"},{"why":"Provides the convergence-rate machinery for partially asynchronous gradient projection that Lemmas 5, 9-12 adapt to the time-varying setting.","marker":"[13]"},{"why":"Supplies the error bound condition (Lemma 4) that lets the analysis handle the nonconvex aggregate problem.","marker":"[14]"},{"why":"Its Proposition A.2 is the starting point for Lemma 2's minimizer-distance bound.","marker":"[36]"},{"why":"The survey that named asynchronous sampling as an open problem, and whose centralized rate is recovered in Corollary 2.","marker":"[4]"},{"why":"The authors' prior totally-asynchronous algorithm for time-varying convex problems with synchronous sampling, which this work extends.","marker":"[18]"},{"why":"The consensus optimization algorithm used as the comparison baseline in the numerical section.","marker":"[37]"}],"fun_headline_variants":["Async sampling in QP tracking: bounded error proven","Asynchronous objective sampling: open problem solved for QPs","No sync needed: agents track time-varying QPs with bounded error","Nonconvex aggregate? Still bounded error for async QP tracking","Uncoordinated sampling times: QP tracking error stays bounded"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes each sampled objective stays fixed for a dwell time $\\kappa_z$ that must be long enough for the iterates to reach a special time $\\hat{k}_z$ at which the nearest optimal points all have equal cost, and $\\hat{k}_z$ depends on constants that cannot be computed from the problem data; if objectives change faster than this, the claimed bounded-error guarantees are not covered (and the paper concedes they would no longer hold).","fun_headline_variants_meta":{"raw":{"variants":["Async sampling in QP tracking: bounded error proven","Asynchronous objective sampling: open problem solved for QPs","No sync needed: agents track time-varying QPs with bounded error","Nonconvex aggregate? Still bounded error for async QP tracking","Uncoordinated sampling times: QP tracking error stays bounded"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001236,"raw_usage":{"total_tokens":5017,"prompt_tokens":828,"completion_tokens":4189,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":444,"completion_tokens_details":{"reasoning_tokens":4114}},"tokens_in":444,"tokens_out":4189,"duration_ms":26714,"temperature":1.0,"reasoning_tokens":4114,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:13:10.990428+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a two-agent strongly convex quadratic problem where one agent samples twice as often as the other, shrink the sampling interval so that the objective changes before the iterates reach the required dwell stage $\\hat{k}_z$ (for instance, let the minimizer move at a rate comparable to the algorithm's contraction speed), and measure $|g(x(\\eta_z);t_z) - f^*(t_z)|$ over many sample times; the central claim fails if this error grows without bound or systematically exits the ball predicted by Theorem 3.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the partial-asynchrony model and classic asynchronous block coordinate descent framework, including the projection lemma and delay bound used throughout."},{"cited_title":"On the rate of convergence of a partially asynchronous gradient projection algorithm,","cited_arxiv_id":null,"evidence_quote":"Provides the convergence-rate machinery for partially asynchronous gradient projection that Lemmas 5, 9-12 adapt to the time-varying setting."},{"cited_title":"Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem,","cited_arxiv_id":null,"evidence_quote":"Supplies the error bound condition (Lemma 4) that lets the analysis handle the nonconvex aggregate problem."},{"cited_title":"Differentially private distributed convex optimization via functional perturbation,","cited_arxiv_id":null,"evidence_quote":"Its Proposition A.2 is the starting point for Lemma 2's minimizer-distance bound."},{"cited_title":"Time-varying convex optimization: Time- structured algorithms and applications,","cited_arxiv_id":null,"evidence_quote":"The survey that named asynchronous sampling as an open problem, and whose centralized rate is recovered in Corollary 2."},{"cited_title":"A totally asynchronous algorithm for time-varying convex optimization problems,","cited_arxiv_id":null,"evidence_quote":"The authors' prior totally-asynchronous algorithm for time-varying convex problems with synchronous sampling, which this work extends."},{"cited_title":"Convergence rate for consensus with delays,","cited_arxiv_id":null,"evidence_quote":"The consensus optimization algorithm used as the comparison baseline in the numerical section."}],"review_version":1}