{"id":"a7fd9948-e847-49e9-810a-2d0af035b934","arxiv_id":"2505.11752","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"Coordinate permutation is claimed to guarantee coverage of the global optimum in nonsmooth nonconvex optimization, but the proof assumes the coverage property it concludes and the convergence-rate result is a tautological norm fact.","lead":"This paper claims that randomly permuting the coordinates of an optimizer's iterates helps it escape local optima and provably approach the global optimum on nonsmooth nonconvex problems. The theoretical proofs do not support the claim, and the experiments lack code and error bars needed for reproduction.","discovery_kind":"incremental","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.3's global-cover conclusion is assumed, not proved; permutation only reorders existing coordinate values, and a two-coordinate stuck-optimizer counterexample refutes the claimed guarantee.","rationale":"The reader's weakest assumption is exactly the coverage assertion in Theorem 4.3's proof, and my independent reading finds the same point. I add a concrete counterexample: because permutation preserves the multiset of coordinate values and cannot manufacture values the optimizer has never produced, the finite union of cubes around permuted iterates has no mechanism to cover the domain; the proof's invocation of Lemma 4.1 supplies no such mechanism. The two-coordinate example with a zero-gradient local minimum shows the claimed universal guarantee is false, not just underived. Secondary issues (Lemma 3.1's contraction claim, Theorem 4.5's norm-based convergence-rate argument, and the non-reproducible experimental section) support rejection but are not needed for the decision. The final verdict should remain REJECT, so no adjustment to the reader's verdict is needed.","tokens_in":15488,"tokens_out":12677,"duration_ms":136163,"concrete_test":"Analytical check: on I=[-2,2]^2 define f(x,y)=min((x-1)^2+1,(x+1)^2)+(y-1)^2 and initialize at (1,1). Verify that ∇f(1,1)=(0,0), so gradient descent (and any descent method using only zero gradients) keeps x_t=y_t=1 for all t, and that every permutation sends (1,1) to (1,1). Then for any fixed radius δ with 0<δ<1, the distance from every center (1,1) to the global cube B((-1,1),δ) exceeds δ, so B((-1,1),δ) is not covered for any T. This settles that Theorem 4.3's coverage claim is false rather than merely unproved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central positive claim is Theorem 4.3, whose proof (Eq. (2) and Appendix B, Eq. (B8)) asserts that for sufficiently large T and D the union of cubes centered at permuted iterates covers the whole domain I. This is the theorem's conclusion, and it is not derived. Lemma 4.1 is quoted as if any finite family of closed cubes automatically covers a compact set; the lemma is stated without the cover hypothesis and is false as a general claim. More fundamentally, a coordinate permutation only reorders the D values already present in the current iterate. If the unrandomized optimizer never visits some part of I, no permuted iterate visits it either, so \"T,D large\" cannot force coverage. This is not merely a missing argument: the theorem is false as stated. Take D=2, I=[-2,2]^2, f(x,y)=g(x)+(y-1)^2 with g(x)=min((x-1)^2+1,(x+1)^2). On I, f is Lipschitz, nonsmooth, and nonconvex; g has a stable local minimum at x=1 (zero gradient) and a global minimum at x=-1. Start from I0=(1,1). Gradient descent leaves (1,1) fixed because both partial derivatives vanish, and every permutation of (1,1) is (1,1). Hence all iterates remain (1,1), and the union of cubes of any fixed radius δ<1 never meets B((-1,1),δ). Theorem 4.3's coverage guarantee therefore fails in a concrete instance.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies permutation randomization as a wrapper around gradient-based optimizers for nonsmooth nonconvex Lipschitz objectives. It claims (Theorem 4.3) that, with sufficiently many iterations and sufficiently high dimension, the union of cubes centered at permuted iterates covers the domain, and hence approximates a closed cube around the global optimum; it also claims (Theorem 4.5) that permutation randomization preserves the underlying optimizer's convergence rate. The authors support the theoretical claims with experiments comparing a 'randomized ADAM' against ADAM, ADMM, and SVRG on deep matrix factorization, deep belief networks, noisy objectives, and logistic regression.","tokens_in":15763,"tokens_out":3484,"duration_ms":36101,"significance":"If the central theorem were correct, the result would be remarkable: it would imply that a purely combinatorial coordinate permutation, applied to any gradient-based method, turns a local method into a global optimizer for all Lipschitz nonsmooth nonconvex functions, in contrast to known lower bounds for deterministic nonsmooth nonconvex optimization. The paper also provides pseudo-code and experiments on public data. However, the proof of the main theorem is circular, and the theorem is false as stated; a simple two-dimensional counterexample shows that permutation randomization cannot escape a fixed point whose coordinate set contains only the starting values. The contraction lemma underpinning the negative result is asserted without proof, and several auxiliary statements are mathematically incorrect. The central claims are therefore not established.","major_comments":[{"comment":"The proof of the main global-coverage claim assumes the conclusion. In Eq. (2) and Appendix B (B8), the authors state that when T and D are sufficiently large, the union of cubes centered at the permuted iterates covers the whole domain I, and they cite Lemma 4.1 (Heine-Borel) for this step. But a union of finitely many cubes covers I only if the iterates happen to visit a set of points whose cubes cover I; this is precisely the statement to be proved. No argument is given to show that permutation randomization forces the iterates to visit such a set. The proof is therefore circular.","section":"Theorem 4.3, Eq. (2) and Appendix B, Eqs. (B1), (B8)"},{"comment":"The claimed guarantee is false as stated. Take D=2, I=[-2,2]^2, and f(x,y)=g(x)+(y-1)^2 with g(x)=min((x-1)^2+1,(x+1)^2). The function is Lipschitz, nonsmooth, and nonconvex on I. Starting at (1,1), gradient descent has zero partial derivative in both coordinates, so every unrandomized iterate is (1,1); every permutation of (1,1) is (1,1). The global minimizer is (-1,1), and for any fixed radius delta<1, no cube centered at (1,1) covers B((-1,1),delta). Thus Theorem 4.3's conclusion fails despite arbitrarily large T (and D=2). Permutation randomization only reorders coordinate values that already appear in the iterate; it cannot create new coordinate values or visit unvisited regions.","section":"Theorem 4.3, counterexample"},{"comment":"Lemma 3.1 asserts that any gradient-based optimizer without randomization satisfies G(f(I_t)) = I_{t+1} subset of I_t for all t, i.e., nested contraction of the iterate set. This is not a property of gradient-based optimizers in general: gradient descent with a poorly chosen step size can increase the norm of the iterate or oscillate. The 'proof by contradiction' assumes that if the set ever expanded, iterates would diverge to infinity, which conflates set-theoretic expansion with norm growth of a sequence. The lemma is used to prove Theorem 3.2, so the claimed limitation of non-randomized optimizers is not established.","section":"Lemma 3.1 and Appendix A"},{"comment":"Both lemmas are mathematically incorrect as stated. Lemma 4.1 claims that for a closed bounded set Gamma and a closed set G = {g_i}_{i=1}^K, the union of finitely many closed sets g_i covers Gamma; this is false without a covering assumption (e.g., take two disjoint closed intervals in [0,2]). Lemma 4.2's statement of the Vitali covering theorem is also not a standard formulation: finitely many disjoint closed sets with small outer measure of the complement do not constitute a Vitali covering in the usual sense, and the countable/measure-theoretic conditions are missing. Since these lemmas are the cited justification for the covering step in Theorem 4.3, the proof collapses.","section":"Lemma 4.1 and Lemma 4.2"},{"comment":"The convergence-rate preservation result is not proven. In Appendix B, Eq. (B17) states ||G(f(X)-f(Y))|| <= c||G(f(X)-f(Y))|| with 0<c<1, which is trivially false unless the left side is zero; the intended contraction inequality should involve ||f(X)-f(Y)|| on the right. The subsequent argument only shows that the operator norm of R is 1, which does not imply that the composed iteration preserves a specific convergence rate. Theorem 4.6's statement and proof are incomprehensible: the set equality involves unbound variables and 'Cauchy Theorem' is invoked without a clear statement; the final bound 1/sqrt(T) <= 2|f(x_{i,gbest},delta)| appears without derivation from the preceding lines. These results do not constitute a valid proof.","section":"Theorem 4.5 and Theorem 4.6, Appendix B"}],"minor_comments":[{"comment":"The notation \\(x,y \\subseteq \\mathbb{R}^D\\) is incorrect; x and y should be elements, not subsets. Also, \\(\\|f(x)-f(y)\\|\\le L\\|x-y\\|\\) with f scalar-valued typically uses absolute values, and the L should be assumed nonnegative.","section":"Definition 2.1"},{"comment":"Assumption 2.1 is nearly vacuous: every point is the center of some cube of positive radius. It does not constrain the iterates or the covering property, so it cannot support the theorem's coverage conclusion.","section":"Assumption 2.1"},{"comment":"The terminology 'closed interval' is used for what is a finite set of D points, and notations like \\(G_t \\cdot f(I_0)\\) are used inconsistently (an operator acting on a function value rather than on an iterate). This makes the definitions hard to parse.","section":"Definition 2.4 and 2.5"},{"comment":"The pseudo-code for randomized ADAM updates the second moment as \\(V_t \\leftarrow \\beta_1 V_{t-1} + (1-\\beta_1) g_t\\), which should involve \\(\\beta_2\\) and \\((1-\\beta_2)\\) in standard ADAM. As written, the second moment estimate uses the wrong decay factor.","section":"Table 3 (Appendix C)"},{"comment":"The statement that 'deterministic, dimension-free, first-order optimizers cannot outperform randomized methods' mischaracterizes Jordan et al. (2023), which gives lower bounds on deterministic methods; it does not establish that randomized methods achieve dimension-free global convergence on nonsmooth nonconvex problems.","section":"Introduction and Related Work"},{"comment":"The experiments show lower reconstruction loss on specific datasets but do not measure whether the optimizer approximates a global optimum or covers the domain; thus the empirical results do not corroborate Theorem 4.3, which is the paper's central claim.","section":"Section 5"}],"recommendation":"reject","confidential_remarks":"The paper's central theorem is both unproven and false as stated, and the counterexample in the report is decisive. The coverage assumption in Eq. (B8) is the conclusion itself, and permutation randomization cannot force new coordinate values. Additionally, the presentation of the auxiliary lemmas and convergence-rate arguments falls far below the standard for a serious journal. I see no repair within the manuscript's scope that would preserve the claimed guarantees."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the bottom line: the central theorem is not proven; it assumes the conclusion. As stated, it is false. The paper should not be accepted.\n\nWhat is actually new here is the attempt to answer an open question from Jordan et al. 2023 about the role of randomization in nonsmooth nonconvex optimization. That is a good question, and testing a coordinate-permutation wrapper on ADAM against ADAM, SVRG, and ADMM is a reasonable thing to try. The reported loss curves suggest the heuristic can help in some settings, and the observation that a permutation operator has norm 1 is true. That is where the credit ends.\n\nThe core problem is Theorem 4.3. Its proof asserts that when T and D are large, the union of cubes centered at permuted iterates covers the domain I, and then concludes that the cube around the global optimum is covered. That coverage is exactly the theorem's content, not a derived consequence. Permuting coordinates only reorders the values already present in the iterate. If the optimizer never visits a region, no permutation visits it. A concrete counterexample kills the theorem: take D=2, f(x,y)=g(x)+(y-1)^2 where g has a stable local minimum at x=1 and a global minimum at x=-1. Starting at (1,1), gradient descent stays at (1,1) forever, and every permutation of (1,1) is still (1,1), so the iterates never approach the global optimum. So the claimed guarantee fails in a simple instance.\n\nOther issues are proportionate to this one. Lemma 3.1 asserts that all gradient-based optimizers contract the initial set, which is not generally true. Lemma 4.1 is a garbled statement of Heine-Borel and is false as written: a finite family of closed sets does not cover a compact set without a cover hypothesis. Theorem 4.6 is nearly unreadable and ends with an unsupported 1/sqrt(T) bound. On the empirical side, there is no code, no seeds, no error bars on the loss curves, a hand-picked trigger threshold, and a typo in the pseudo-code (the second moment update uses beta1 instead of beta2). Independent verification is not possible.\n\nThe citation pattern is also weak: the paper does not engage with existing shuffle/permutation heuristics in optimization, which matters less than the math problems but is still a gap.\n\nWho is this paper for? Only a reader interested in a practical shuffling heuristic might get something out of the experiments, but the theory should not be cited. This paper deserves a desk reject, not a serious referee. If it comes back, the authors would need to state an achievable coverage condition and drop the global-optimum claim.","headline":"The central theorem assumes the conclusion and is false as stated; the paper is not salvageable in its current form, though the empirical question it asks is a real one.","tokens_in":16355,"tokens_out":2231,"would_cite":false,"duration_ms":23361,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Permutation randomization lets gradient-based optimizers approximate the global optimum on nonsmooth nonconvex objectives while preserving their convergence rate.","keywords":["permutation randomization","gradient-based optimization","nonsmooth nonconvex","Lipschitz continuous","global optimum","convergence rate","randomized ADAM","operator norm"],"falsifier":"Run a two-dimensional nonsmooth nonconvex Lipschitz function whose global minimizer has a coordinate value that never appears in any coordinate of any iterate of the deterministic optimizer; since permutation only reorders existing coordinate values, that minimizer can never be covered, and observing that the randomized optimizer cannot approach it would refute the coverage claim of Theorem 4.3.","tokens_in":15169,"feed_emoji":"🔀","tokens_out":10023,"duration_ms":91324,"temperature":0.7,"pith_summary":"The paper tries to establish that a simple coordinate-permutation randomization can make gradient-based optimizers global optimizers for nonsmooth nonconvex Lipschitz objectives. The mechanism is coverage: after enough iterations and in high enough dimension, the closed cubes around the permuted iterates cover the whole domain, hence a closed cube around the global optimum; the permutation has operator norm one, so the underlying optimizer's convergence rate is preserved. If correct, this gives a dimension-free theoretical role for randomization in a setting where deterministic first-order methods face known limitations. The authors demonstrate the idea by adding permutation to ADAM and reporting lower reconstruction loss than ADAM, ADMM, and SVRG on deep matrix factorization, a deep belief network, and noisy objectives.","feed_headline":"A coordinate shuffle turns gradient optimizers into global optimizers","feed_subtitle":"Paper proves shuffling coordinates preserves the optimizer's convergence rate while escaping local traps.","key_machinery":"The load-bearing object is the permutation randomization operator $R:\\mathbb{R}^D\\to\\mathbb{R}^D$, which reorders all coordinates of the current point; because it is a finite-dimensional isometry, $\\|R\\|=1$. $R$ is interleaved with a gradient-based optimizer operator $G$, so the iterate is $R_t G_t f(I_0)$. The argument uses the contraction and shrinkage property of $G$ to explain why plain optimizers stall, and Heine-Borel and Vitali covering theorems to argue that the union of cubes around randomized iterates fills $I$. The norm-one property is what prevents $R$ from slowing the base optimizer.","core_discovery":"The central claim is Theorem 4.3: given a Lipschitz continuous nonsmooth nonconvex $f:\\mathbb{R}^D\\to\\mathbb{R}$, interleaving a gradient-based optimizer $G$ with a permutation operator $R$ that reorders coordinates produces iterates $\\hat{x}_{i,t}$ whose closed cubes $B(\\hat{x}_{i,t},\\delta_{i,t})$ cover the domain $I$ when $T$ and $D$ are sufficiently large, and therefore cover the closed cubes around the global optimum. The proof splits into overlapping cubes, handled by the Heine-Borel theorem, and non-overlapping cubes, handled by the Vitali covering theorem. Theorem 4.5 claims the permutation has operator norm $\\|R\\|=1$, so the convergence rate of the included optimizer is unchanged; Theorem 4.6 states the upper bound $\\frac{1}{\\sqrt{T}}\\le 2\\,|\\psi(B(x_{\\mathrm{gbest}},\\delta))|$ for a one-dimensional $\\psi$. The paper's experiments corroborate the claim by showing randomized ADAM keeps updating late in training and outperforms ADAM, ADMM, and SVRG on the chosen tasks.","pith_inferences":["The proof of coverage is combinatorial rather than dynamical: permutation never creates new coordinate magnitudes, it only rearranges existing ones, so the real engine of Theorem 4.3 is the assumption that the visited coordinate values are dense enough in the domain; a natural test is to measure visited-cube volume directly and see whether sparse permutation triggering preserves the guarantee.","If the norm-one argument is the reason convergence is preserved, then any measure-preserving coordinate transformation, such as cyclic shifts or sign flips, should behave like permutation; this is an untested prediction of the paper's reasoning.","The algorithms in the experiments trigger permutation only when $\\|g_t-g_{t-1}\\|<\\epsilon$, while the theorems consider permutation at every step, so closing that gap would decide whether the practical algorithm is fully covered by Theorem 4.3."],"forward_implications":["If Theorem 4.3 holds, any gradient-based optimizer augmented with coordinate permutation can approach a closed cube around the global optimum on Lipschitz nonsmooth nonconvex problems, given enough iterations.","Because $\\|R\\|=1$, the random permutation adds no asymptotic slowdown: the randomized optimizer inherits the base optimizer's convergence rate.","Permutation can be applied only when the gradient difference is small, and the experiments indicate this lets the optimizer escape stationary points and keep updating late in training.","The empirical results imply that randomized ADAM is a practical replacement for ADAM on deep stacked architectures and noisy objectives, with better reconstruction accuracy and lower runtime than SVRG."],"supporting_citations":[{"why":"Defines the open question the paper answers: the role of randomization in nonsmooth nonconvex optimization, and supplies the deterministic lower-bound context.","marker":"Jordan et al., 2023"},{"why":"Provides the Heine-Borel and Vitali covering theorems used to prove that the union of permuted cubes covers the domain in Theorem 4.3.","marker":"Royden, 1968"},{"why":"Supplies the functional-analysis notions of operators, contraction, and operator norm used in Lemma 4.4 and Theorem 4.5.","marker":"Rudin, 1973"},{"why":"Defines the generalized-gradient and Clarke stationary-point framework that plain optimizers are said to get stuck at.","marker":"Clarke, 1974, 1975, 1981, 1990"},{"why":"ADAM is the representative optimizer that the paper augments with permutation and uses as an experimental baseline.","marker":"Kingma and Ba, 2014"},{"why":"Shows that randomization with a shrinking norm benefits local search but can interfere with convergence, motivating the norm-one permutation operator.","marker":"Burke et al., 2020"}],"fun_headline_variants":["Coordinate shuffling turns local optimizers into global ones","Permutation randomization: escape local traps, keep convergence rate","Shuffle coordinates to make gradient descent global","Random coordinate order unlocks global convergence in nonsmooth nonconvex optimization","Permutation trick preserves convergence rate while escaping local minima"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's key step is assuming that, once the iteration count and dimension are large enough, the small boxes around the points the optimizer has visited cover the entire search space; this coverage is asserted rather than derived, and a permutation only reorders coordinate values the optimizer has already produced.","fun_headline_variants_meta":{"raw":{"variants":["Coordinate shuffling turns local optimizers into global ones","Permutation randomization: escape local traps, keep convergence rate","Shuffle coordinates to make gradient descent global","Random coordinate order unlocks global convergence in nonsmooth nonconvex optimization","Permutation trick preserves convergence rate while escaping local minima"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000177,"raw_usage":{"total_tokens":1315,"prompt_tokens":988,"completion_tokens":327,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":249}},"tokens_in":604,"tokens_out":327,"duration_ms":3537,"temperature":1.0,"reasoning_tokens":249,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:48:14.326023+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a two-dimensional nonsmooth nonconvex Lipschitz function whose global minimizer has a coordinate value that never appears in any coordinate of any iterate of the deterministic optimizer; since permutation only reorders existing coordinate values, that minimizer can never be covered, and observing that the randomized optimizer cannot approach it would refute the coverage claim of Theorem 4.3.","supporting_citations":[],"review_version":1}