{"id":"2c7b6782-cb26-45aa-962a-a5b09aba1ff1","arxiv_id":"2501.13038","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For some computable functions convex in each variable, block Gauss-Seidel coordinate descent has no Turing-computable argmin step and no effective stopping rule, so performance guarantees are impossible.","lead":"Coordinate descent often can't be made into a reliable computer algorithm: even for simple functions that are convex in each variable, the step that minimizes one coordinate at a time can be mathematically impossible to compute, so no guaranteed stopping error exists. The paper proves this with two explicit two-variable functions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Second negative result invalid: reachability definition (Def. 7) excludes G1(0), so f2's coordinate descent can choose computable G1(0)=0 and converge effectively; Theorem 4.1 remains sound.","rationale":"The paper's central theorem, Theorem 4.1, is solid: the explicitly constructed f1 is convex in each variable, has a computable global minimizer set intersected with the x1-axis, and every assignment function G1 is a step function with an arbitrary value at 0. Lemma 2.1 then correctly rules out computability of all such step functions. This alone establishes that the exact coordinate-descent step cannot be implemented on a Turing machine, giving a valid negative answer to the paper's main question. The second construction, however, is overclaimed. Definition 7's reachability notion deliberately ignores the value G1(bx2), but the actual iteration (11) uses exactly this value once the second coordinate reaches 0. For f2, G1(0) can be chosen to be any point in [−ξ*, ξ*], including the computable point 0. With that choice the iteration converges in two steps to (0, 0), a computable global minimizer, and the approximation error is exactly zero thereafter. Thus Corollary 5.2 and the corresponding summary statements are false. This warrants a conditional verdict: the main impossibility result stands, but the authors must correct the reachability discussion, Corollary 5.2, and Section 7. The same correction does not affect Theorem 4.1, so no stronger sanction is needed.","tokens_in":21242,"tokens_out":23705,"duration_ms":238662,"concrete_test":"Analytic check: for the f2 of Theorem 5.1, choose the assignment function G1 ∈ A1(f2) defined by G1(0) = 0 and G1(x2) equal to the unique minimizer of f2(·, x2) for x2 ≠ 0, and G2(x1) = 0. Compute the coordinate-descent iterates from an initial point with x2(0) = 1: x1(1) = G1(1) < −ξ*, x2(1) = 0, x1(2) = 0, x2(2) = 0, and x(k) = (0, 0) for all k ≥ 2. This is an exact Gauss–Seidel sequence, since every step chooses an element of the corresponding argmin set, and it converges effectively to the computable global minimizer (0, 0), directly disproving Corollary 5.2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definition 7 defines reachability along coordinate x2 exclusively through one-sided limits of (G1(x2), x2) as x2 → bx2 with x2 ≠ bx2. For f2 in Theorem 5.1 this yields only (−ξ*, 0) and (ξ*, 0), both noncomputable. But Algorithm 1's update (11) evaluates G1 directly at the current coordinate, including bx2 = 0. For f2, MIN1(0) = [−ξ*, ξ*], so an assignment function with G1(0) = 0 is a legitimate element of A1(f2). Starting from any initial x2(0), one obtains x(1) = (G1(x2(0)), 0), then x(2) = (G1(0), 0) = (0, 0), and the sequence is constant thereafter. Since (0, 0) is a computable global minimizer, this convergence is effective. Therefore Corollary 5.2 is false, and the summary's claim that the iteration 'always converges to non-computable minimizers' fails. The flaw is consequential for the paper's second negative reason, but Theorem 4.1's noncomputable-assignment argument is independent and remains valid.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies whether block Gauss–Seidel (coordinate descent) methods for minimizing computable continuous functions that are convex in each variable can be implemented on Turing machines with effective control of the final error. The authors construct two explicit functions on a rectangle. Theorem 4.1 gives a computable, piecewise linear, coordinatewise convex function f1, with infinitely many computable global minimizers, such that every assignment function G1 in A1(f1) (the first-coordinate argmin map) is not Turing computable. Theorem 5.1 gives a C^1 function f2 whose global minimizers form an interval [-xi*, xi*] x {0} with xi* noncomputable; the authors claim that the only minimizers reachable along the second coordinate are the noncomputable endpoints, and infer (Corollary 5.2) that convergence of any sequence to a global minimizer cannot be effective. The paper concludes that iterative coordinate-wise optimization under performance guarantees is generally impossible.","tokens_in":21452,"tokens_out":13095,"duration_ms":124252,"significance":"Theorem 4.1 is a significant result in computable analysis: it provides a very simple, explicit optimization problem with computable data and computable global minimizers for which the block Gauss–Seidel iteration cannot even be implemented on a Turing machine, because the argmin map is noncomputable. This cleanly answers Question 2 in the negative and gives a concrete, falsifiable counterexample to the common heuristic that local coordinate-wise steps are computationally easier than joint optimization. The second negative claim (Corollary 5.2 and Section 7) is not established and is in fact false as stated; the paper's solid contribution is the noncomputable-assignment result, not the reachability-based argument.","major_comments":[{"comment":"Corollary 5.2 is false as stated. For the function f2 of Theorem 5.1, the proof (Eq. (18)) shows that MIN1(0) = [-xi*, xi*], so an assignment function G1 in A1(f2) with G1(0) = 0 is legitimate. Taking the unique G2(x1) = 0, Algorithm 1 with update rule (11) produces, from any initialization, x(1) = (G1(x(0)_2), 0) and x(2) = (G1(0), 0) = (0,0), and the sequence is constant thereafter. Since (0,0) is a computable global minimizer of f2, this sequence converges effectively, contradicting the corollary's assertion that no sequence converging to a global minimizer of f2 can be effective. The source of the error is Definition 7: it defines reachability only through one-sided limits of (G1(x2), x2) as x2 tends to bx2 with x2 different from bx2, but Algorithm 1 evaluates G1 directly at the current coordinate (line 4), including bx2 = 0. The reachability notion therefore does not match the algorithm's actual update rule.","section":"§5, Definition 7; Corollary 5.2"},{"comment":"The paper's advertised second reason for negative results — that the iteration always converges to non-computable minimizers even though computable minimizers exist — is not established. As the previous comment shows, for f2 there exists an allowed assignment function for which the algorithm converges effectively to the computable minimizer (0,0). Moreover, the argmin map G1 in Theorem 5.1 is discontinuous at x2 = 0 (with one-sided limits -xi* and xi*), so every G1 in A1(f2) is non-Borel-Turing-computable irrespective of the value G1(0); consequently Theorem 5.1 does not provide an example in which the argmin steps are effectively implementable while convergence is ineffective. The two failure modes discussed in Section 7 are therefore not separated, and the claim in Section 7 that 'the iterative algorithm converges for any arbitrary initialization vector to a non-computable minimizer' is false for the constructed f2.","section":"§7, Summary and discussion; abstract"}],"minor_comments":[{"comment":"In the proof of Theorem 4.1 and in Section 4.2, the range of alpha in the definition of G1,alpha is written as alpha in [-1, -1]; this should be alpha in [-1, 1].","section":"§4.1, Eq. (14) and §4.2"},{"comment":"In the statement of Theorem 5.1, the codomain of f2 is written as C; it should be R, and the domain should be R^2.","section":"Theorem 5.1 statement"},{"comment":"In the proof of Theorem 4.3, the second case is written as 'a < 0'; since the theorem assumes a > 0, this should be 'a < 1' (the same typo appears in the discussion of the second case).","section":"Proof of Theorem 4.3"},{"comment":"In the line after Eq. (18) in the proof of Theorem 5.1, the displayed set 'G1 1 (0)' should be 'G-1(0)' (the subscript minus sign is missing).","section":"Proof of Theorem 5.1"},{"comment":"The statement of Theorem 5.1 asserts a,b > 0 arbitrary; as written, if a < xi* the interval [-xi*, xi*] of global minimizers is not contained in R and property (5) becomes vacuous. The authors should state a >= 1 or specify that xi* is chosen with xi* < min(a,1).","section":"Theorem 5.1"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a correct and elegant negative result (Theorem 4.1), but the second part (Theorem 5.1, Corollary 5.2, Section 7) contains a false corollary and unsubstantiated claims. I would ask the authors to remove or fundamentally revise the reachability-based second result, and to adjust the abstract and summary accordingly. The paper would then be a solid contribution, though with a narrower conclusion than currently claimed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the main construction (Theorem 4.1) is a clean, explicit counterexample: a computable continuous function, convex in each coordinate, whose coordinate-descent assignment map is a step function but every choice is Turing non-computable. That is a real result and it directly answers Question 2. Second, the paper's second negative claim (Corollary 5.2 and Section 7) is overclaimed. The reachability definition in Def. 7 deliberately ignores G1(bx2), but Algorithm 1 evaluates G1 at the current coordinate. For f2, MIN1(0) contains computable points such as 0, so a valid assignment function with G1(0)=0 makes the iteration converge in one step to the computable minimizer (0,0). Therefore Corollary 5.2 is false as stated, and the summary's statement that the method 'always converges to non-computable minimizers' does not hold.\n\nWhere the paper earns credit: the examples are simple and concrete, the proof of Theorem 4.1 is self-contained, and the non-computability of the step function is standard and clearly handled. The construction of f2 with non-computable one-sided limits is also interesting; the analysis of the limit behavior seems sound. The problem is the interpretation, not the calculus.\n\nSoft spots, in order: (1) Corollary 5.2 is false and should be replaced with a carefully quantified statement about which assignment functions produce effective convergence. (2) Definition 7's notion of reachability should be reconciled with the actual update rule (11); as written, it excludes direct evaluation at the limit coordinate, which is something the iteration can do. (3) Minor typos: in the proof of Theorem 4.1, 'α ∈ [−1, −1]' should be '[−1, 1]'; in Theorem 4.3, case 'a < 0' should presumably be 'a < 1'.\n\nAudience: people working in computable analysis and optimization theory. The paper is worth a serious referee because Theorem 4.1 alone is a valuable impossibility result. But the second negative result needs to be rewritten or substantially qualified before publication. If I were the editor, I would send it out with the expectation of a major revision.","headline":"Solid new counterexample on non-computable coordinate-descent steps, but the second negative result overclaims because reachability ignores direct evaluation at the limit coordinate.","tokens_in":22029,"tokens_out":6523,"would_cite":false,"duration_ms":62388,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C06","68W40","03D80"],"pacs":[],"model":"deepseek-v4-flash","headline":"On a fixed computable, coordinatewise-convex, continuous function, every block Gauss-Seidel step can be Turing-noncomputable, or every convergent trajectory can be forced to land on non-computable minimizers.","keywords":["convex optimization","block coordinate descent","Gauss-Seidel method","computable analysis","Turing machine","effective convergence","non-computable minimizer","performance guarantees"],"falsifier":"Run the two-coordinate Gauss–Seidel recurrence for $f_2$ from a starting point with $x_2 \\neq 0$, and at the step where $x_2$ becomes $0$ choose $G_1(0)=0$. The iterates then become constant at the computable global minimizer $(0,0)$, giving effective convergence. This would contradict Corollary 5.2 under a notion of reachability that permits direct use of the assignment value at the reached coordinate; it does not affect Theorem 4.1, where every assignment function is non-computable.","tokens_in":20979,"feed_emoji":"🧮","tokens_out":12090,"duration_ms":112196,"temperature":0.7,"pith_summary":"The paper asks whether iterative block Gauss–Seidel (coordinate descent) methods can be run on a digital computer in a way that always stops with a guaranteed error bound. It answers no, even for functions that look benign: computable, continuous, convex in each variable separately, and with infinitely many computable global minimizers. Two concrete two-variable functions are exhibited. For the first, every possible first-coordinate argmin step is a step function that no Turing machine can compute, so even the first iteration cannot be implemented. For the second, every sequence the method produces converges to non-computable minimizers, so no algorithmic stopping rule can certify closeness to a computable minimizer. The paper concludes that the failure is inherent to the local coordinate-wise strategy, not to the underlying optimization problem.","feed_headline":"Coordinate descent can be impossible on any digital computer","feed_subtitle":"Two explicit two-variable functions show that no effective stopping rule can be guaranteed, even when computable minimizers exist.","key_machinery":"The load-bearing object is the assignment function $G_\\ell$ of Definition 6, the map that selects one minimizer of the one-coordinate problem for each fixed value of the other coordinates; Algorithm 1 iterates by composing these maps. For $f_1$, $G_1$ is a sign-like step function, and Lemma 2.1 supplies the fact that such step functions are not Banach–Mazur computable, which is what makes the first update non-implementable. For $f_2$, the machinery shifts to Definition 7, reachability along a coordinate, which looks only at one-sided limits of $G_1(x_2)$ as $x_2 \\to 0$; this notion converts the non-computability of $\\xi^*$ into the statement that the only minimizers the iteration can land on are not computable.","core_discovery":"The central discovery is that the coordinate-wise update is not merely hard to analyze; it can be algorithmically unrealizable even when the objective is computable and coordinatewise convex. Theorem 4.1 constructs $f_1$ on $[-a,a]\\times[-b,b]$ whose global minimizer set is $[-1,1]\\times\\{0\\}$, but whose first-coordinate assignment function is $G_1(x_2)=1$ for $x_2<0$, $G_1(0)=\\alpha$, and $G_1(x_2)=-1$ for $x_2>0$; because every such step function is non-computable, the first argmin step has no Turing implementation and no computable approximation within a fixed tolerance. Theorem 5.1 constructs a $C^1$ function $f_2$ whose minimizer set is $[-\\xi^*,\\xi^*]\\times\\{0\\}$ for a non-computable $\\xi^*$, and whose argmin map has one-sided limits $-\\xi^*$ and $\\xi^*$; therefore every coordinate-descent trajectory converges to a non-computable minimizer. Together these two examples establish that both reasons offered in the abstract occur, and they answer negatively both Question 1 (effective convergence) and Question 2 (effective implementability of each step).","pith_inferences":["The second negative result is narrower than it may appear: it holds under the one-sided-limit notion of reachability, not for every run of coordinate descent. A run that reaches $x_2=0$ and selects a computable value of $G_1(0)$ can converge effectively to a computable minimizer; what is impossible is a guarantee that the method will land on such a minimizer.","Theorem 4.1 is not affected by that subtlety, because there every assignment function is non-computable. The two theorems thus separate distinct obstructions: non-computability of the argmin operator versus non-reachability of computable minimizers.","A natural extension is to adapt the $f_2$ construction to prescribed non-computable limits and to ask whether randomization, different blockings, or inexact inner solves can evade the reachability obstruction.","The same discontinuity-of-argmin technique may transfer to other iterative methods whose updates are argmin maps, turning approximation-error questions into computability questions in those settings as well."],"forward_implications":["For $f_1$, no Turing machine computes the first coordinate update, and even an approximation of that update within a fixed positive tolerance is impossible (Theorem 4.3).","For $f_2$, any sequence of local minimizers produced by coordinate-wise optimization that converges to a global minimizer converges non-effectively, so no algorithm can stop with a guaranteed error bound (Corollary 5.2).","Both functions have computable global minimizers, so joint global optimization can approximate one effectively; the obstruction is intrinsic to the coordinate-wise strategy (Section 7).","The negative behavior extends to block Gauss–Seidel methods with at least two blocks, to unconstrained problems, and to smooth functions of arbitrary differentiability class (Section 6, Remarks 6 and 10)."],"supporting_citations":[{"why":"Supplies the distinction between Borel–Turing and Banach–Mazur computability used in Definitions 4 and Lemma 2.1.","marker":"[2]"},{"why":"Gives the convergence theory for block coordinate descent methods that the iterative procedure in Algorithm 1 is an instance of.","marker":"[3]"},{"why":"Provides the construction used in Lemma 2.1 to prove that sign-like step functions are not Banach–Mazur computable.","marker":"[8]"},{"why":"Shows that under convex constraints block nonlinear Gauss–Seidel iterates converge to critical points; this is the procedure whose first step Theorem 4.1 proves noncomputable.","marker":"[16]"},{"why":"Establishes the computable-analysis foundations: minimum values are computable, unique minimizers are computable, and non-unique minimizer sets can contain non-computable points.","marker":"[23]"},{"why":"Provides a block coordinate descent convergence theorem that Theorem 4.1 shows cannot be effectively implemented for $f_1$.","marker":"[32]"}],"fun_headline_variants":["No effective stopping rule for coordinate descent even on computable functions","Gauss-Seidel steps can be non-computable, killing performance guarantees","Some convex problems make coordinate descent impossible to implement","Block Gauss-Seidel may have no computable iteration path","Guaranteed convergence is unattainable for some descent methods"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Corollary 5.2 rests on Definition 7, which counts a minimizer as reachable only through one-sided limits of the argmin map and ignores the value $G_1(0)$ that the map takes exactly at the reached coordinate; if direct evaluation at that coordinate is allowed, the coordinate-descent sequence can choose a computable minimizer there.","fun_headline_variants_meta":{"raw":{"variants":["No effective stopping rule for coordinate descent even on computable functions","Gauss-Seidel steps can be non-computable, killing performance guarantees","Some convex problems make coordinate descent impossible to implement","Block Gauss-Seidel may have no computable iteration path","Guaranteed convergence is unattainable for some descent methods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001103,"raw_usage":{"total_tokens":4620,"prompt_tokens":987,"completion_tokens":3633,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":3547}},"tokens_in":603,"tokens_out":3633,"duration_ms":26239,"temperature":1.0,"reasoning_tokens":3547,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:31:24.448060+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the two-coordinate Gauss–Seidel recurrence for $f_2$ from a starting point with $x_2 \\neq 0$, and at the step where $x_2$ becomes $0$ choose $G_1(0)=0$. The iterates then become constant at the computable global minimizer $(0,0)$, giving effective convergence. This would contradict Corollary 5.2 under a notion of reachability that permits direct use of the assignment value at the reached coordinate; it does not affect Theorem 4.1, where every assignment function is non-computable.","supporting_citations":[{"cited_title":"A vigad and V","cited_arxiv_id":null,"evidence_quote":"Supplies the distinction between Borel–Turing and Banach–Mazur computability used in Definitions 4 and Lemma 2.1."},{"cited_title":"Beck and L","cited_arxiv_id":null,"evidence_quote":"Gives the convergence theory for block coordinate descent methods that the iterative procedure in Algorithm 1 is an instance of."},{"cited_title":"Boche, R","cited_arxiv_id":null,"evidence_quote":"Provides the construction used in Lemma 2.1 to prove that sign-like step functions are not Banach–Mazur computable."},{"cited_title":"Grippo and M","cited_arxiv_id":null,"evidence_quote":"Shows that under convex constraints block nonlinear Gauss–Seidel iterates converge to critical points; this is the procedure whose first step Theorem 4.1 proves noncomputable."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the computable-analysis foundations: minimum values are computable, unique minimizers are computable, and non-unique minimizer sets can contain non-computable points."},{"cited_title":"Xu and W","cited_arxiv_id":null,"evidence_quote":"Provides a block coordinate descent convergence theorem that Theorem 4.1 shows cannot be effectively implemented for $f_1$."}],"review_version":1}