{"id":"a1f2d1bc-5f01-4e85-83a8-bd10d28d30fd","arxiv_id":"2412.16830","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A metric-routing version of continual learning task ordering is NP-hard, and a Christofides-style polynomial algorithm achieves 3/2 and 3/2+r^{1-T} approximation ratios against an upper-bound objective.","lead":"This paper designs a route-planning algorithm for a continual learning agent that must travel between tasks while balancing forgetting loss against travel cost. The authors prove the combined optimization is NP-hard and give a polynomial-time Christofides-style algorithm with stated approximation ratios.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Approximation guarantees are proved only for the upper-bound objective (7)/(11); the paper never bounds the gap to the true expected loss (3), so loose Δ bounds can make Algorithm 1 arbitrarily suboptimal on the actual CL objective.","rationale":"The reader's weakest_assumption correctly identifies the surrogate-to-true gap as the central risk. My read agrees: the formal approximation ratios are only for E[π-bar], and the simulations verify only those surrogate ratios. The proof of Proposition 2 also contains an invalid inequality of the form (A+B)/(C+D) < B/D, but that error is repairable by using (A+B)/(C+D) ≤ max(A/C, B/D), with A/C ≤ 1 and B/D ≤ 3/2, so it does not threaten the theorem's truth. The surrogate gap, by contrast, is not a proof repair: it is a missing link between the optimized objective and the true CL loss. Because Δ values are only upper bounds, an adversary or even noisy estimation can make the surrogate objective's optimum arbitrarily far from the true optimum, and the paper gives no condition on Δ tightness and no bound on E[π-bar(τ)] - E[π(τ)]. A concrete exhaustive simulation with controlled Δ looseness would settle whether this concern actually lands in practice. Since the reader already conditions acceptance on addressing exactly this issue, the verdict remains CONDITIONAL and no adjustment is needed.","tokens_in":10045,"tokens_out":22448,"duration_ms":207130,"concrete_test":"Run a small exhaustive experiment with T ≤ 8 and m,n chosen for the underparameterized case. Draw ground-truth vectors w*_i from separated clusters and compute the true dissimilarities d_{ij}; set travel costs so that the shortest travelling route ends at a region with large d_{ij} to the others. For the tight case set Δ_{ij}=d_{ij}; for the loose case set Δ_{ij}=C for all i≠j with C much larger than all d_{ij}. Run Algorithm 1 on (7) and compare E[π(τ*)] with the true optimum min_τ E[π(τ)] found by exhaustive enumeration, using the closed forms (6) and (10). If the true-loss ratio grows with C or exceeds the claimed surrogate ratios, the surrogate-to-true gap is real; if it stays near 1.5/3.5, the concern is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Propositions 2 and 3 bound the ratio to the optimum of the surrogate upper-bound objective E[π-bar] in (7) and (11), not to the true expected loss E[π] in (3). Under Assumption 1, each Δ_{i,j} is only an upper bound on the true dissimilarity ||w*_i - w*_j||², and no lower bound or tightness condition is imposed. Since Algorithm 1 minimizes E[π-bar], the forgetting-loss term in the surrogate can be made order-independent by taking all Δ equal to a large constant, while the true forgetting loss may strongly favor a different final region. In that case the surrogate-optimal route can be the travel-cheapest route, and the true loss ratio E[π(τ*)]/min_τ E[π(τ)] can be unbounded because the forgotten dissimilarities of the chosen final region can be arbitrarily large. Section IV-C never exercises this gap: the simulations only generate Δ and c directly and compute R = E[π-bar*]/E[π-bar**], so they measure the surrogate ratio and not the actual CL loss. Thus the paper's central practical claim—that routing opportunistically reduces true forgetting loss—is not supported by either a theorem or a simulation once the surrogate-to-true gap is taken into account.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a continual-learning problem in which an IoT agent chooses an order in which to visit T geographically separated tasks, trading off the expected forgetting loss of the final trained predictor against traveling cost. Because the ground-truth parameter dissimilarities are unknown, the authors upper-bound them by quantities Δ and solve the resulting surrogate objectives (7) and (11) for the underparameterized and overparameterized linear-regression settings. They prove NP-hardness, propose a Christofides-style Algorithm 1, and claim approximation ratios of 3/2 and 3/2 + r^{1-T} with O(T^3) complexity, followed by simulations comparing the surrogate objective value of the algorithm with a computed optimum.","tokens_in":10325,"tokens_out":21141,"duration_ms":200310,"significance":"If the claims hold, the paper proposes a genuinely new task-ordering variant of continual learning with a clean combinatorial formulation and a parameter-free, polynomial-time algorithm. The explicit approximation ratios, the O(T^3) complexity, and the use of known closed-form expected forgetting losses from [14] are attractive features. The main weaknesses are that the guarantees are stated for the upper-bound surrogate rather than the true expected loss, that the proof of Proposition 2 uses an invalid inequality, and that the NP-hardness argument is not a valid reduction as written. These issues are fixable, but they currently affect the support for the central claims.","major_comments":[{"comment":"The approximation guarantees are only for the surrogate upper-bound objectives (7) and (11), not for the true expected loss in (3). Assumption 1 gives no lower bound or tightness condition on the Δ values, so the gap between the surrogate and the true objective is uncontrolled. If the Δ are loose, the surrogate-optimal route can be essentially the travel-cheapest route while the true optimum strongly prefers a different final region, and the ratio E[π(τ*)] / min_τ E[π(τ)] can be arbitrarily large. The simulations in Section IV-C compute R := E[πbar*]/E[πbar**], so they only exercise the surrogate ratio. The abstract, Propositions 2 and 3, and the conclusion should either explicitly restrict all claims to the upper-bound surrogate, or the authors should add a theorem bounding the surrogate-to-true gap (for example, under an assumption that each Δ is within a constant factor of the true squared distance).","section":"Section II-B, Assumption 1 and Eqs. (3), (7), (11); Section IV-C"},{"comment":"The inequality after 'The first inequality holds' is false as stated. From E[F(τ*)] ≤ E[F(τ**)] one cannot conclude (A+B)/(C+D) < B/D; for example, A=1, B=1, C=2, D=100 gives (A+B)/(C+D) > B/D. The claimed 3/2 ratio is recoverable by a different argument: since F* ≤ F** and C* ≤ (3/2)C**, the ratio (F*+C*)/(F**+C**) is at most max(F*/F**, C*/C**) ≤ 3/2. The proof should be rewritten with this argument, and the strict inequality should be made non-strict where equality is possible.","section":"Appendix C, proof of Proposition 2"},{"comment":"The NP-hardness proof is not a valid reduction as written. The fact that the objective contains the SHP term Σ c_{τ_t,τ_{t+1}} does not imply that minimizing the composite objective is at least as hard as SHP, because the additional Δ-dependent terms can dominate or erase the dependence on the order. A correct reduction should specify an instance of (7) or (11) whose optimal route coincides with the optimal SHP route, e.g., by setting all Δ_{i,j} equal to a common constant so that the task-dissimilarity part is order-independent. Please provide such a construction or revise the argument.","section":"Section III-C, Proposition 1"},{"comment":"The experiments generate each traveling cost c_{i,j} uniformly in [1,10] without enforcing the triangle inequality assumed in Section II-A. For instance, c_{ab}=10 with c_{ac}=c_{cb}=1 violates c_{ab} ≤ c_{ac}+c_{cb}. Since Lemma 3 and the Christofides-style approximation rely on the metric property, the reported ratios are not a verification of the stated guarantee. Please generate metric costs (e.g., from random Euclidean points or as shortest-path distances) or explicitly label the experiments as heuristic tests outside the model assumptions.","section":"Section IV-C, simulation setup"}],"minor_comments":[{"comment":"Proposition 3 states the approximation ratio 'to the optimum of the agent's expected overall loss in (7)', but for the overparameterized case the relevant objective is Eq. (11), not Eq. (7).","section":"Section IV-B, Proposition 3"},{"comment":"The text calls x_{τ_t} an 'm × n feature vector'; it should be an 'm × n feature matrix'. Also, the output vector is n × 1, so the notation should be adjusted consistently.","section":"Section II-A"},{"comment":"The phrase 'without loss of generality' before Assumption 1 is misleading: the existence of upper bounds Δ is an additional modeling assumption, not a normalization. Please replace it with a direct statement of the assumption.","section":"Section II-B, Assumption 1"},{"comment":"The sentence 'we have Algorithm 1 returns a solution with o(3/2 + r^{1-T}) approximation ratio' should read 'with an approximation ratio of 3/2 + r^{1-T}'; the little-o notation is inappropriate here.","section":"Appendix D, proof of Proposition 3"},{"comment":"The simulation section does not report the number of random trials, confidence intervals, or the method used to compute the optimum E[πbar**]. At minimum, please state these details and specify whether the generated instances satisfy the metric assumption.","section":"Section IV-C"},{"comment":"Lemmas 1 and 2 are the analytic backbone of the paper, but the appendices only refer to Appendix D.8 and D.3 of [14]. Please state explicitly that these are restated known results and either reproduce the short derivations or give the precise theorem numbers in [14], so the paper is more self-contained.","section":"Appendix A and B"}],"recommendation":"major_revision","confidential_remarks":"The paper has a reasonable optimization core, but the current version overclaims relative to the true continual-learning loss. I would support publication after the authors reframe the contribution as surrogate upper-bound optimization, fix the proof of Proposition 2 and the NP-hardness argument, and make the simulation setup respect the metric assumption. The approximation results appear recoverable, so I do not recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is the problem: task ordering in continual learning with a metric travel cost. Previous work on task ordering in CL keeps the sequence fixed or only looks at a few patterns. Making the route itself a decision variable and proving NP-hardness by a reduction to shortest Hamiltonian path is a fair formal first step. The Christofides-style algorithm that forces the final region to be the one with the smallest total dissimilarity is a clean idea, and the overparameterized proof (Prop. 3) checks out: the ratio calculation is convoluted but the inequalities go the right way, aside from a typo that references (7) when it means (11).\n\nThe underparameterized proof (Prop. 2) has a real gap. The claim (A+B)/(C+D) < B/D when A≤C is false in general. The 3/2 ratio can still be recovered with a simpler argument: F(τ*)≤F(τ**) and C(τ*)≤1.5C_min≤1.5C(τ**), so the total ratio is bounded. But as written the proof is invalid and needs to be fixed.\n\nThe bigger caveat is that every approximation guarantee is for the upper-bound objective in (7) and (11), built on the Δ_{i,j} bounds. The paper is upfront about this in Section II, but it never quantifies how far the surrogate-optimal route can be from the true-loss optimum, and loose Δ can make the gap arbitrarily large. The simulations don't help here: they generate Δ and c directly and compute the surrogate ratio, so 'close-to-optimum' is close to the surrogate optimum, not the actual CL loss. That is not fatal to the formal claims, but the practical claim in the introduction and abstract is weaker than it appears. A referee should ask for either a gap analysis or a simulation with ground-truth parameters.\n\nAlso, Lemmas 1 and 2 are imported from [14] without derivation. That is fine for a short conference paper, but readers deserve at least a sketch.\n\nOverall: the problem is new, the algorithm is sensible, and most of the math holds up after a proof repair. It is a perfectly reasonable ICASSP-level contribution, not a branch-reshaping result. I would send it to a serious referee with the expectation of a revision. I would cite it only if I were working specifically on routing in CL, which I am not.","headline":"A novel routing-plus-forgetting CL formulation with a mostly sound approximation algorithm, but all guarantees are for the upper-bound surrogate and one proof has an invalid step.","tokens_in":10821,"tokens_out":7143,"would_cite":false,"duration_ms":57788,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q17","90C27","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that choosing the order in which an agent visits tasks in an IoT network—not just how it trains—can be optimized with provable 3/2 and 3/2+r^{1-T} approximation ratios, despite the NP-hardness of the joint task-ordering…","keywords":["continual learning","IoT networks","task ordering","approximation algorithm","catastrophic forgetting","Hamiltonian path","linear regression","NP-hardness"],"falsifier":"For a small instance with $T=5$, enumerate all $T!$ routes to compute the exact minimum of $E[\\bar\\pi]$ in (7) and (11), run Algorithm 1, and compare the ratio; any instance where the ratio exceeds $3/2$ (or $3/2 + r^{1-T}$) would refute the corresponding proposition. One could also construct true parameter vectors whose dissimilarities are far below the given $\\Delta$ bounds and check whether the algorithm's route is far from the true optimum, exposing the surrogate gap.","tokens_in":9858,"feed_emoji":"🚗","tokens_out":6857,"duration_ms":56969,"temperature":0.7,"pith_summary":"Continual learning normally treats the task sequence as fixed and asks how to train so earlier tasks are not forgotten. This paper makes the order itself a decision: an autonomous agent samples data by moving through geographically separated regions, so it can reorder tasks at a travel cost. The authors define the overall loss as expected forgetting loss plus average travel cost, derive closed-form expressions for both the underparameterized and overparameterized linear-regression settings, and show the resulting order optimization is NP-hard. They then give a polynomial-time algorithm, based on a metric-TSP 3/2-approximation with a forced final region, that achieves approximation ratios of 3/2 and 3/2 + $r^{{1-T}}$ against the optimal upper-bound route.","feed_headline":"Task routing bounds continual-learning loss at 1.5x optimum","feed_subtitle":"An NP-hard scheduling problem over IoT regions gets a polynomial-time 3/2 guarantee, with travel cost and forgetting loss combined.","key_machinery":"The argument runs through two pieces. First, closed-form expectations of the forgetting loss (Lemmas 1 and 2) convert the unknown ground-truth parameters into the known dissimilarity bounds $\\Delta_{i,j}$ and $\\Delta_{i,0}$, leaving an objective that is a weighted Hamiltonian path over regions plus order-independent constants. Second, Algorithm 1 solves that path problem by the standard metric-TSP recipe: build a minimum spanning tree, add a minimum-weight perfect matching on its odd-degree vertices, form an Eulerian circuit, and shortcut repeated vertices; a zero-cost dummy vertex forces the path to end at the region minimizing the forgetting-loss term. The $3/2$ factor comes from the classic bound on the resulting Hamiltonian path, and the forgetting-loss part is no worse than the optimum because the forced final region is the one with minimum summed dissimilarity.","core_discovery":"The central claim is that the route-planning version of continual learning reduces to a shortest Hamiltonian path problem with a last-vertex bonus, and that a shortcutting algorithm forced to end at the region with the smallest summed dissimilarity preserves a 3/2 approximation. Proposition 2 states that in the underparameterized case ($n \\geq m+2$) Algorithm 1 returns a route whose expected upper-bound loss in (7) is within a factor $3/2$ of the optimum, with $O(T^3)$ complexity. Proposition 3 states that in the overparameterized case ($m \\geq n+2$) the ratio is $3/2 + r^{1-T}$, where $r = 1 - n/m$, and that it improves to $3/2$ when $m$ is sufficiently larger than $n$. The paper reports simulations showing ratios below these bounds and substantial gains over a fixed-order continual-learning baseline.","pith_inferences":["The approximation ratios are for the upper-bound surrogate objective, not the true expected loss. A direct extension would bound the surrogate-to-true gap as a function of how much the unknown $\\Delta$ values overestimate true parameter dissimilarities; without such a bound, a loose estimate can make the recommended route far from the true optimum.","The zero-cost dummy-vertex trick for forcing a Hamiltonian path to end at a designated vertex generalizes to other route-planning problems with a last-stop bonus, such as delivery or inspection tours with a preferred final location.","The same reordering idea could transfer to curriculum selection or replay scheduling in continual learning whenever a closed-form forgetting-loss expression is available, though the travel-cost interpretation would need a replacement cost structure."],"forward_implications":["Task order becomes a tunable resource: an agent with route freedom can keep the upper-bound forgetting-plus-travel loss within a constant factor of the best possible order in polynomial time.","In the overparameterized regime the guarantee tightens to $3/2$ as the feature count grows relative to the sample count, because inter-task dissimilarity contributes less to forgetting.","For two regions the algorithm returns an exactly optimal route, and in simulations its ratios stay below the theoretical $3/2$ and beat a fixed-order continual-learning baseline by 30–50% for $T \\geq 6$.","The $O(T^3)$ running time makes the approach usable for moderate numbers of tasks or regions."],"supporting_citations":[{"why":"Supplies the autonomous-vehicle motivating example and the linear-regression setting for task data.","marker":"[13]"},{"why":"Provides the closed-form expected-forgetting-loss derivations that Lemmas 1 and 2 invoke, plus the dissimilarity upper-bound assumption.","marker":"[14]"},{"why":"Underwrites the inverse-Wishart distribution result used for the closed-form expectations and the excluded $m = n \\pm 1$ cases.","marker":"[16]"},{"why":"Establishes the NP-hardness of the shortest Hamiltonian path problem used to prove Proposition 1.","marker":"[18]"},{"why":"Gives the $3/2$ approximation bound for metric Hamiltonian paths that Algorithm 1 and Propositions 2 and 3 rely on.","marker":"[19]"}],"fun_headline_variants":["Routing tasks in IoT cuts forgetting loss to 1.5x optimum","NP-hard continual learning routing gets 3/2 approximation","Forget less by routing tasks: 1.5x optimal in IoT networks","First to route task order to bound continual learning loss","Travel-cost-aware task routing yields 3/2 loss bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantees hold only for the upper-bound objective, and they require the agent to know upper bounds $\\Delta_{i,j}$ and $\\Delta_{i,0}$ on the true dissimilarities between ground-truth model parameters; if those bounds are loose, the chosen route can be far from optimal for the agent's actual loss.","fun_headline_variants_meta":{"raw":{"variants":["Routing tasks in IoT cuts forgetting loss to 1.5x optimum","NP-hard continual learning routing gets 3/2 approximation","Forget less by routing tasks: 1.5x optimal in IoT networks","First to route task order to bound continual learning loss","Travel-cost-aware task routing yields 3/2 loss bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000759,"raw_usage":{"total_tokens":3366,"prompt_tokens":936,"completion_tokens":2430,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":2341}},"tokens_in":552,"tokens_out":2430,"duration_ms":14289,"temperature":1.0,"reasoning_tokens":2341,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:16:30.158447+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small instance with $T=5$, enumerate all $T!$ routes to compute the exact minimum of $E[\\bar\\pi]$ in (7) and (11), run Algorithm 1, and compare the ratio; any instance where the ratio exceeds $3/2$ (or $3/2 + r^{1-T}$) would refute the corresponding proposition. One could also construct true parameter vectors whose dissimilarities are far below the given $\\Delta$ bounds and check whether the algorithm's route is far from the true optimum, exposing the surrogate gap.","supporting_citations":[{"cited_title":"How catastrophic can catastrophic forgetting be in linear regr ession?","cited_arxiv_id":null,"evidence_quote":"Supplies the autonomous-vehicle motivating example and the linear-regression setting for task data."},{"cited_title":"Theory on forgett ing and generalization of continual learning,","cited_arxiv_id":null,"evidence_quote":"Provides the closed-form expected-forgetting-loss derivations that Lemmas 1 and 2 invoke, plus the dissimilarity upper-bound assumption."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Underwrites the inverse-Wishart distribution result used for the closed-form expectations and the excluded $m = n \\pm 1$ cases."},{"cited_title":"Hamiltonian paths in large clustered routing problems,","cited_arxiv_id":null,"evidence_quote":"Establishes the NP-hardness of the shortest Hamiltonian path problem used to prove Proposition 1."},{"cited_title":"A historical note on the 3/2- approximation algorithm for the metric traveling salesman problem,","cited_arxiv_id":null,"evidence_quote":"Gives the $3/2$ approximation bound for metric Hamiltonian paths that Algorithm 1 and Propositions 2 and 3 rely on."}],"review_version":1}