Pith. sign in

REVIEW 2 major objections 5 minor 32 references

Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict Solid new counterexample on non-computable coordinate-descent steps, but the second negative result overclaims because reachability ignores direct evaluation at the limit coordinate. read the letter →

arxiv 2501.13038 v1 pith:SD4TGJNC submitted 2025-01-22 math.OC cs.CC

Holger Boche , Volker Pohl , H. Vincent Poor This is my paper · ORCID
classification math.OCcs.CC MSC 90C2590C0668W4003D80
keywords convexoptimizationblockcoordinatedescentGauss-SeidelmethodcomputableanalysisTuringmachineeffectiveconvergencenon-computableminimizerperformanceguarantees
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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).

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [§5, Definition 7; Corollary 5.2] 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.
  2. [§7, Summary and discussion; abstract] 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.
minor comments (5)
  1. [§4.1, Eq. (14) and §4.2] 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].
  2. [Theorem 5.1 statement] 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.
  3. [Proof of Theorem 4.3] 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).
  4. [Proof of Theorem 5.1] 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).
  5. [Theorem 5.1] 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).

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the counterexamples are explicitly constructed and the central noncomputability arguments do not reduce to their own assumptions.

full rationale

Walking the derivation chain: Theorem 4.1 constructs f1 explicitly as a piecewise-linear function and computes MIN1(x2) directly; the noncomputability of every assignment G1,alpha then follows from Lemma 2.1, the classical fact that the sign function is not Banach-Mazur computable. The proof of Lemma 2.1 cites the authors' [8] for the computable-alpha case, but this is an external, parameter-free result of computable analysis, not a consequence of the present theorems, so the self-citation is not circular. Theorem 5.1 likewise builds f2 from an explicit auxiliary function g* with a chosen noncomputable xi*, and derives the one-sided limits of G1 by calculus; no fitted parameters or predictions are involved. The second negative claim relies on Definition 7, which defines reachability via one-sided limits and excludes the direct value G1(0); the skeptic is right that this is a substantive correctness problem for Corollary 5.2, since G1(0)=0 would give an effective convergent sequence to a computable minimizer. That objection concerns the truth of the theorem, not circularity: the claimed conclusion is not equivalent to the inputs by construction, nor is it derived by renaming or by a self-citation chain. Overall, the derivation is self-contained and the circularity burden is low.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central results rest only on standard computable-analysis facts and explicitly constructed example functions. No new ontological entities are introduced. The free parameters alpha and xi* are arbitrary construction choices, not fitted to data. The main non-standard ingredient is the non-computability of sign-like functions, which is a known theorem cited to the authors' prior work.

free parameters (2)
  • alpha in f2
    Positive real weight in the definition of f2 (Eq. (16)). The theorem holds for every alpha > 0, so this is a construction parameter, not a fitted value.
  • xi* in g*
    Non-computable number in (0,1) used to define g* (Appendix A). Its existence is standard, and the result holds for any such xi*, so it is a construction choice, not a data fit.
assumptions (4)
  • domain assumption The sign function G_alpha is not Banach-Mazur computable (Lemma 2.1)
    Standard result in computable analysis; proof sketched via [8, Theorem 2] for the computable-alpha case.
  • domain assumption The unique minimizer of a computable continuous function is computable
    Used for f2's G1(x2) for x2 != 0; standard result from Pour-El and Richards [23, Chapter 6].
  • domain assumption Non-computable reals exist and can be limits of decreasing rational sequences
    Standard in computability theory; used to construct xi* in Appendix A.
  • domain assumption The function g* defined by the infinite series (21) is computable continuous
    Proved in Lemma A.1; used in Theorem 5.1 for the construction of f2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees." pith.science (2026). https://pith.science/paper/SD4TGJNC

@misc{pith2026250113038,
  author       = {Pith},
  title        = {Pith review of: Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SD4TGJNC}},
  note         = {Machine review of arXiv:2501.13038}
}
read the original abstract

This paper studies the effective convergence of iterative methods for solving convex minimization problems using block Gauss--Seidel algorithms. It investigates whether it is always possible to algorithmically terminate the iteration in such a way that the outcome of the iterative algorithm satisfies any predefined error bound. It is shown that the answer is generally negative. Specifically, it is shown that even if a computable continuous function which is convex in each variable possesses computable minimizers, a block Gauss--Seidel iterative method might not be able to effectively compute any of these minimizers. This means that it is impossible to algorithmically terminate the iteration such that a given performance guarantee is satisfied. The paper discusses two reasons for this behavior. First, it might happen that certain steps in the Gauss--Seidel iteration cannot be effectively implemented on a digital computer. Second, all computable minimizers of the problem may not be reachable by the Gauss--Seidel method. Simple and concrete examples for both behaviors are provided.

Figures

Figures reproduced from arXiv: 2501.13038 by the authors.

Figure 1
Figure 1. Illustration of the function f1 constructed in the proof of Theorem 4.1. The plot on the right shows the function f1(x1, x2) (solid line) and f1(x1, −x2) (dotted line) for fixed x2 = 0 (blue), x2 = ±1.0 (red), and x2 = ±3.0 (green). All functions in A1(f1) are step functions and so Lemma 2.1 implies that every G1,α, α ∈ [−1, 1] is not a Borel–Turing computable functions. This finally proves Property 5). □ Proof of C… view at source ↗
Figure 2
Figure 2. Illustration of the function f2 defined in (16) with α = 0.1 and using a g∗ based on ξ∗ = 1/2 and with the sequence ξn = ξ∗+2−n (cf. Appendix A). The plot on the right shows the function f2(x1, x2) (solid line) and f2(x1, −x2) (dotted line) for fixed x2 = 0 (blue), x2 = ±1.0 (red), and x2 = ±2.0 (green). gives finally G1(x2) > ξ∗ > 0 for x2 < 0 G1(x2) ∈ [−ξ∗, ξ∗] for x = 0 G1(x2) < −ξ∗ < 0 for x2 > 0 . (18) So we ha… view at source ↗
Figure 3
Figure 3. Illustration of the function g∗ defined in (21) for ξ∗ = 1/20 (blue), ξ∗ = 1/2 (red), and ξ∗ = 0.95 (green). In all three cases, the sequence ξn = ξ∗ + 2−n, n ∈ N was used to produce these plots. For every n ∈ N, we define a continuously differentiable function gn ∈ C1 (R) by gn(x) =    (x + ξn) 2 : x < −ξn 0 : −ξn ≤ x ≤ ξn (x − ξn) 2 : x > ξn . Therewith, we define finally the function g∗(x) = P∞ n=1 2 −n gn(x),… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 30 canonical work pages

  1. [1]

    Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless chan- nels, IEEE Trans

    S. Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless chan- nels, IEEE Trans. Inf. Theory, 18 (1972), pp. 14–20

    work page 1972

  2. [2]

    A vigad and V

    J. A vigad and V. Brattka , Computability and analysis: The legacy of Alan Turing , in Turing’s Legacy: Developments from Turing’s Ideas in Logic, Lecture Notes in Logic, Bd. 42, Cambridge University Press, New York, 2014, pp. 1–47

    work page 2014

  3. [3]

    Beck and L

    A. Beck and L. Tetruashvili, On the convergence of block coordinate descent type methods, SIAM J. Optim., 23 (2013), pp. 2037–2060

    work page 2013

  4. [4]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization, MPS-SIAM Se- ries on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, USA, 2001

    work page 2001

  5. [5]

    Benidis, Y

    K. Benidis, Y. Feng, and D. P. Palomar , Optimization methods for financial index track- ing: From theory to practice, Foundations and Trends in Signal Processing, 3 (2018), pp. 171– 279

    work page 2018

  6. [6]

    D. P. Bertsekas, Convex Optimization Algorithms , Athena Scientific, Nashua, USA, 2015

    work page 2015

  7. [7]

    R. E. Blahut, Computation of channel capacity and rate-distortion functions , IEEE Trans. Inf. Theory, 18 (1972), pp. 460–473

    work page 1972

  8. [8]

    Boche, R

    H. Boche, R. F. Schaefer, and H. V. Poor, Algorithmic computability and approximability of capacity-achieving input distributions, IEEE Trans. Inf. Theory, 69 (2023), pp. 5449–5462

    work page 2023

Show all 32 references
  1. [9]

    Boyd and L

    S. Boyd and L. V andenberghe, Convex Optimization , Cambridge University Press, Cam- bridge, 20004

  2. [10]

    E. J. Cand `es and B. Recht , Exact matrix completion via convex optimization , Found. Comput. Math., 9 (2009), pp. 717–772

    2009

  3. [11]

    E. J. Cand `es and T. Tao , Decoding by linear programming , IEEE Trans. Inf. Theory, 51 (2005), pp. 4203–4215

    2005

  4. [12]

    D. E. Comer, D. Gries, M. C. Mulder, A. Tucker, A. J. Turner, P. R. Young, and P. J. Denning , Computing as a discipline , Commun. ACM, 32 (1989), pp. 9–23. 24 H. BOCHE, V. POHL, AND H. V. POOR

    1989

  5. [13]

    Csisz ´ar, On the computation of rate-distortion functions , IEEE Trans

    I. Csisz ´ar, On the computation of rate-distortion functions , IEEE Trans. Inf. Theory, 20 (1974), pp. 122–124

    1974

  6. [14]

    De Santis, S

    M. De Santis, S. Lucidi, and F. Rinaldi , A fast active set block coordinate descent algo- rithm for ℓ1-regularized least squares, SIAM J. Optim., 26 (2016), pp. 781–809

    2016

  7. [15]

    H. M. Friedman , The computational complexity of maximization and integration , Adv. Math., 53 (1984), pp. 80–98

    1984

  8. [16]

    Grippo and M

    L. Grippo and M. Sciandrone , On the convergence of the block nonlinear Gauss–Seidel method under convex constraints , Oper. Res. Lett., 26 (2000), pp. 127–136

    2000

  9. [17]

    Ko, Complexity Theory of Real Functions , Birkh¨ auser, Basel, 1991

    K.-I. Ko, Complexity Theory of Real Functions , Birkh¨ auser, Basel, 1991

    1991

  10. [18]

    Y. Lee, H. Boche, and G. Kutyniok, Computability of optimizers, IEEE Trans. Inf. Theory, 70 (2024), pp. 2967–2983

    2024

  11. [19]

    Y. Lee, H. Boche, and G. Kutyniok , Computability of optimizers for AI and data science , in Handbook of Numerical Analysis, Elsevier B.V., New York, 2024, pp. 1–54

    2024

  12. [20]

    Liu, T.-H

    Y.-F. Liu, T.-H. Chang, M. Hong, Z. Wu, A. M.-C. So, E. A. Jorswieck, and W. Yu , A survey of recent advances in optimization methods for wireless communications , pre-print, (2024). arXiv:2401.12025

    2024 arXiv

  13. [21]

    Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J

    Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22 (2012), pp. 341–362

    2012

  14. [22]

    D. P. Palomar and Y. C. Eldar , eds., Convex Optimization in Signal Processing and Communications, Cambridge University Press, Cambridge, UK, 2009

    2009

  15. [23]

    M. B. Pour-El and J. I. Richards, Computability in Analysis and Physics, Springer-Verlag, Berlin, 1989

    1989

  16. [24]

    M. J. D. Powell , On search directions for minimization algorithms , Math. Program., 4 (1973), pp. 193–201

    1973

  17. [25]

    Razaviyayn, M

    M. Razaviyayn, M. Hong, and Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization , SIAM J. Optim., 23 (2013), pp. 1126– 1153

    2013

  18. [26]

    Specker, Der Satz vom Maximum in der rekursiven Analysis , in Ernst Specker Selecta, G

    E. Specker, Der Satz vom Maximum in der rekursiven Analysis , in Ernst Specker Selecta, G. J¨ ager, H. L¨ auchli, B. Scarpellini, and V. Strassen, eds., Birkh¨ auser, Basel, 1990, pp. 148– 159

    1990

  19. [27]

    A. M. Turing , On computable numbers, with an application to the Entscheidungsproblem , Proc. London Math. Soc., s2-42 (1937), pp. 230–265

    1937

  20. [28]

    A. M. Turing , On computable numbers, with an application to the Entscheidungsproblem. A correction, Proc. London Math. Soc., s2-43 (1938), pp. 544–546

    1938

  21. [29]

    Weihrauch, Computable Analysis, Springer-Verlag, Berlin, 2000

    K. Weihrauch, Computable Analysis, Springer-Verlag, Berlin, 2000

    2000

  22. [30]

    S. J. Wright , Coordinate descent algorithms, Math. Program., 151 (2015), pp. 3–34

    2015

  23. [31]

    Xu , Hybrid Jacobian and Gauss–Seidel proximal block coordinate update methods for linearly constrained convex programming, SIAM J

    Y. Xu , Hybrid Jacobian and Gauss–Seidel proximal block coordinate update methods for linearly constrained convex programming, SIAM J. Optim., 28 (2018), pp. 646–670

    2018

  24. [32]

    Xu and W

    Y. Xu and W. Yin, A block coordinate descent method for regularized multiconvex optimiza- tion with applications to nonnegative tensor factorization and completion , SIAM J. Imaging Sci., 6 (2013), pp. 1758–1789. Holger Boche, Technische Universit¨at M¨unchen, Lehrstuhl f¨ur T...

    2013

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.