{"id":"8986dbdd-e7a1-41af-8749-5626fdbb33fd","arxiv_id":"1908.01402","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A convergence-guaranteed Bregman proximal alternating linearized minimization framework for multi-block nonconvex nonsmooth problems, with closed-form updates for penalized orthogonal nonnegative matrix factorization.","lead":"This paper introduces two multi-block optimization algorithms that use Bregman distances to minimize nonconvex, nonsmooth functions and proves that the sequences they generate converge to critical points. It applies the framework to orthogonal nonnegative matrix factorization with closed-form update steps and reports preliminary numerical results.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Penalty route is not faithful: rank-deficient partial isometries V satisfying VV^T V = V are stationary for every penalty λ, so convergence to critical points of (4.6) does not imply a solution of ONMF (4.2).","rationale":"I read the paper as making two distinct contributions: a general multi-block Bregman proximal alternating framework with convergence and rate results, and an application to penalized orthogonal NMF with closed-form updates. I did not find a fatal flaw in the core convergence proofs of Sections 3: the sufficient decrease, subgradient lower bound, subsequential convergence, KL-based global convergence, and rate arguments are structurally sound, modulo minor typos and loose constants. The load-bearing weakness is in the ONMF application. The reader's weakest assumption identified the penalty route as heuristic; I agree, and I can sharpen it with an explicit failure mechanism. The penalty term λ/2‖I − VV^T‖^2 has gradient 2λ(VV^T V − V), which vanishes for any partial isometry V, not only for full orthogonal matrices. Consequently there exist stationary points of (4.6) with ‖I − VV^T‖ arbitrarily large, for every λ>0, and these points are even fixed points of the BPALM iteration. This decisively shows that convergence to a critical point of the penalized problem carries no guarantee of orthogonality. The numerical section itself supports the concern: in Table 1, larger initial λ improves Oerror only for A-BPALM1, while BPALM and A-BPALM2 show worse fidelity errors. The paper is still a solid theoretical contribution for the penalized formulation; the ONMF claim needs to be reworded or supplemented with an explicit penalty-approximation result. Hence I concur with the reader's CONDITIONAL verdict, and my stress-test does not move it.","tokens_in":27857,"tokens_out":34352,"duration_ms":337011,"concrete_test":"Analytical check: fix r = 2, let w ∈ R^{1×n} with ‖w‖ = 1, let u ∈ R^{m×1}, and set X = u w^T. Define U0 = [u, 0] ∈ R^{m×2} and V0 = [w; 0] ∈ R^{2×n}. (a) Verify that ∇_U f(U0, V0) = 0 and ∇_V f(U0, V0) = 0 for f in (4.6), while V0V0^T = diag(1,0). (b) Run BPALM (Algorithm 1) from (U0, V0) with any λ>0; since the subproblems (4.7) and (4.8) are strictly convex and have (U0, V0) as their unique minimizer, the iterates remain at (U0, V0). If confirmed, the algorithm provably converges to a critical point of (4.6) that violates the orthogonality constraint of (4.2), showing that the claimed convergence guarantee is not a guarantee for ONMF as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The ONMF application rests on the penalized problem (4.6) and the heuristic continuation in Algorithm 3, but no theorem relates critical points of (4.6) to feasible points of the original problem (4.2). This is not merely a missing detail: the penalty has spurious stationary points for every λ>0. The V-gradient of the penalty term is 2λ(VV^T V − V), which vanishes whenever VV^T V = V, i.e. for any partial isometry, including V = [w; 0] with ww^T = 1. Take X = u w^T and U0 = [u, 0]. Then ∇_U f(U0, V0) = 0 and ∇_V f(U0, V0) = 0, so (U0, V0) is a critical point of (4.6) for every λ>0, yet V0V0^T = diag(1, 0), so V0 is not feasible for (4.2). A direct check of the closed-form subproblems (4.7)–(4.8) shows (U0, V0) is also a fixed point of the BPALM updates, since each subproblem is strictly convex and has (U0, V0) as its unique minimizer. Thus the stated convergence guarantees are fully compatible with a terminal point that is not an ONMF solution. The abstract's claim that the framework gives convergence guarantees for ONMF is therefore an overclaim: the proven statement concerns the penalized formulation only, and Algorithm 3 has no convergence guarantee for the outer continuation loop.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces two multi-block proximal alternating linearized minimization algorithms, BPALM and A-BPALM, for minimizing f + sum_i g_i where f is (L_1,...,L_N)-smooth relative to a multi-block Bregman kernel h. The authors prove a sufficient decrease condition, summability of Bregman gaps, a subgradient lower bound, subsequential convergence to critical points, and global convergence with rates under a KL/Łojasiewicz-type assumption. They then instantiate the framework for the penalized orthogonal nonnegative matrix factorization (ONMF) formulation (4.6), derive closed-form block updates, and report numerical experiments on a synthetic data set and the Hubble telescope data set.","tokens_in":28212,"tokens_out":10026,"duration_ms":81501,"significance":"If the convergence results are correct, the multi-block relative smoothness framework is a useful generalization of PALM and B-PALM, and the closed-form updates for the penalized ONMF problem are practically valuable. The theoretical sections are largely a parameter-free derivation from stated assumptions: the relative smoothness constants in (4.5) are analytic bounds, and the KL-based arguments follow a standard template. The authors also make the code publicly available. However, the advertised application-level guarantee for ONMF is not supported by the theorems, which address only the penalized objective, and one key step in the subgradient lower bound needs repair. The core algorithmic idea is promising, but the manuscript currently overstates its scope.","major_comments":[{"comment":"The convergence guarantees proved in Section 3 apply to the penalized problem (4.6), not to the orthogonal NMF problem (4.2), and no theorem in the paper relates critical points of (4.6) to feasible points of (4.2). This is not a minor omission: the penalty has spurious stationary points for every λ>0, since the V-gradient of (λ/2)||I − VV^T||_F^2 is 2λ(VV^T V − V), which vanishes for any partial isometry V. For example, take nonnegative unit vectors u and w, set X = u w^T, U0 = [u, 0], V0 = [w; 0]; then (U0, V0) is a critical point of (4.6) for every λ>0 (both block gradients vanish), yet V0 V0^T = diag(1,0) ≠ I, so it is not feasible for (4.2). The same point is also a fixed point of the BPALM updates (4.7)–(4.8), since each subproblem is strictly convex and uniquely minimized there. Consequently the abstract's claim that BPALM and A-BPALM give rigorous convergence theory for ONMF is an overclaim; only the penalized formulation is covered. Algorithm 3's continuation over λ has no convergence analysis, and Table 1 shows that increasing the initial penalty can worsen Ferror, so the heuristic status of the route to (4.2) should be acknowledged and the claims reframed.","section":"§4.1, Eqs. (4.2), (4.6), and Algorithm 3"},{"comment":"The vector G^{k+1}_i is defined using ∇_i f(x^{k,i}), but for i < N the point x^{k,i} differs from x^{k+1} in blocks i+1,...,N, so the claimed inclusion (G^{k+1}_1,...,G^{k+1}_N) ∈ ∂ϕ(x^{k+1}) is not established and is in general false. This is load-bearing because Theorem 3.4 and the subsequent KL-based results use this inclusion to pass to the limit and conclude 0 ∈ ∂ϕ(x*). The gap is repairable: replacing ∇_i f(x^{k,i}) by ∇_i f(x^{k+1}) yields a true subgradient, and the extra term ∇_i f(x^{k+1}) − ∇_i f(x^{k,i}) can be controlled by the same Lipschitz/block-displacement argument; but as written the proof is incomplete.","section":"§3, Proposition 3.3, Eq. (3.6)"}],"minor_comments":[{"comment":"The sentence 'The unconstrained version of the ONMF problem (4.2) is given by (4.6)' is misleading: (4.6) still contains nonnegativity constraints via indicator functions and a penalty term, so it is a penalized formulation rather than an unconstrained problem.","section":"§4.1"},{"comment":"In the definition of τ2, the triple-bar norm '|||·|||' should be the Frobenius norm; please correct the notation.","section":"§4.2, Theorem 4.2, Eq. (4.9)"},{"comment":"The caption says 'the smallest number of Ferror and Ferror are displayed in bold' but should refer to Ferror and Oerror; moreover, the bold entries do not always appear to be the smallest in their columns (for example, the BPALM row with λ=1 has Ferror 6.75e-2, which is not the minimum).","section":"§4.2, Table 1"},{"comment":"The text refers to 'A-BPALM1 and A-BPALM1' when describing the two adaptive variants; the second should be A-BPALM2.","section":"§4.2"},{"comment":"In the displayed inequality for i=1,...,N−1, the summation index i is reused both as a fixed block index and as a summation index; using separate indices would improve clarity.","section":"§3, Proposition 3.3 proof"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's claimed priority as 'the first algorithms with rigorous convergence theory for ONMF' is contestable given the gap between the penalized problem (4.6) and the original problem (4.2); even after reframing, the novelty statement should be softened. The proof gap in Proposition 3.3 appears repairable, but the authors need to fix it before the theoretical results can be relied upon. The numerical contribution is preliminary but the public code is a positive element."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing. First, the multi-block Bregman proximal alternating linearized minimization framework is a genuine extension of PALM and B-PALM: it handles N>2 blocks, nonsmooth nonconvex block-separable terms, and product-separable kernels, with convergence and rates under the usual KL assumption. The proofs follow the standard template and I did not find a load-bearing error. Second, the ONMF application overreaches. The convergence guarantees are for the penalized problem (4.6), and that problem has spurious stationary points for every λ>0. Take V = [w; 0] with ww^T = 1, U = [u, 0], X = u w^T. Then ∇_V of the penalty is 2λ(VV^T V − V) = 0 because V is a partial isometry, and ∇_U is zero too, so (U,V) is a critical point of (4.6) even though VV^T ≠ I. The paper's claim to be the first with rigorous convergence guarantees for ONMF is therefore not accurate; 'penalized ONMF' would be defensible.\n\nWhat the paper does well: the relative-smoothness analysis is carefully laid out, Proposition 4.1 gives explicit L1,L2 for the ONMF kernel, and the closed-form subproblem solutions are neat and useful. The adaptive backtracking variant is a reasonable addition. I would trust the main theorems.\n\nSoft spots, in order of importance. The penalty/continuation gap is the big one; no theorem connects critical points of (4.6) to feasible points of (4.2), and Algorithm 3 is heuristic. Table 1 even shows that larger λ can worsen reconstruction for BPALM and A-BPALM2, so the route is not empirically reliable either. The numerical section is preliminary by the authors' own admission—no baselines, no error bars, one synthetic plus one real dataset—so it should not carry the paper's claims. Minor: Theorem 4.2's notation around the Cardano solution has a typo (the double norm bars), but the formula is recoverable.\n\nWho is this for? Optimization researchers working on Bregman proximal methods will get real value from the multi-block analysis. The ONMF part needs reframing before it can be cited as a convergence result for ONMF. I would send this to referees: the theory deserves scrutiny and the application claims need to be corrected.","headline":"Solid multi-block Bregman PALM theory, but the ONMF application overclaims because the penalized problem has spurious stationary points that are not orthogonal factorizations.","tokens_in":28821,"tokens_out":2608,"would_cite":true,"duration_ms":25695,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two Bregman proximal alternating linearized algorithms are proven to converge to critical points for nonconvex nonsmooth multi-block problems, and applied with closed-form updates to penalized orthogonal nonnegative matrix factorization.","keywords":["Bregman proximal alternating linearized minimization","multi-block relative smoothness","Kurdyka-Łojasiewicz inequality","orthogonal nonnegative matrix factorization","nonconvex nonsmooth optimization","closed-form updates","convergence rates"],"falsifier":"Exhibit a bounded sequence generated by Algorithm 1 that satisfies all assumptions of Theorem 3.4 but whose cluster set contains a point $x^\\star$ with $0\\notin\\partial\\phi(x^\\star)$; for instance, engineer two-block nonconvex terms $g_i$ with flat regions to create a spurious accumulation point, and check the subgradient residual (3.6) along the orbit. Alternatively, enumerate exact solutions of the hard ONMF problem (4.2) for a small random matrix and check whether continuation applied to (4.6) returns a KKT point of the hard problem; failure would falsify the paper's implied penalty route.","tokens_in":27644,"feed_emoji":"🧮","tokens_out":11351,"duration_ms":109957,"temperature":0.7,"pith_summary":"The paper introduces two block-coordinate algorithms, BPALM and its adaptive variant A-BPALM, for minimizing an objective made of a smooth nonconvex function $f$ plus block-separable nonsmooth nonconvex terms $g_i$. The central claim is that, under a multi-block relative smoothness condition that replaces Lipschitz-gradient knowledge with a Bregman distance, every bounded sequence generated by either algorithm has cluster points that are critical points; under the Kurdyka-Łojasiewicz inequality the whole sequence converges, with rates governed by the Łojasiewicz exponent. This matters because the framework is shown to cover orthogonal nonnegative matrix factorization: with a product-separable Bregman kernel the block subproblems admit closed-form solutions, giving what the authors describe as the first convergence-guaranteed algorithms for ONMF. The paper thus offers both a general convergence certificate for alternating Bregman methods and a concrete factorization problem where the certificate is actually used.","feed_headline":"Bregman alternating algorithms converge on nonconvex ONMF","feed_subtitle":"Two methods reach critical points without Lipschitz constants, with closed-form updates for orthogonal NMF.","key_machinery":"The central object is the multi-block Bregman proximal alternating linearized mapping\n$$$T_i^{{h/\\gamma_i}}$(x)=\\arg\\min_{z\\in\\mathbb{R}^{n_i}}\\left\\{\\langle\\nabla_i f(x),\\,z-x_i\\rangle+\\frac{1}{\\gamma_i}D_h(x+U_i(z-x_i),x)+g_i(z)\\right\\},$$\nwhere $D_h$ is the Bregman distance of a multi-block kernel $h$ and $U_i$ selects the $i$-th block. The structural assumption doing the heavy lifting is multi-block relative smoothness: $f$ is $(L_1,\\ldots,L_N)$-smooth relative to $h$ if $L_i h(x+U_i(z-x_i))-f(x+U_i(z-x_i))$ is convex in $z$ for every $x$ and $i$. This gives a blockwise majorization, the multi-block descent lemma, that makes the function decrease at every subproblem solve, and it replaces the usual Lipschitz moduli of partial gradients with kernel-dependent constants $L_i$. The same inequality, together with the optimality conditions of $T_i^{h/\\gamma_i}$, yields the subgradient lower bound on iterate gaps that all subsequential and KL-based global convergence results rely on.","core_discovery":"On its own terms, the paper's discovery is a convergence theorem for the Bregman proximal alternating linearized minimization scheme applied to problem (1.1). For a multi-block kernel $h$, the objective component $f$ is called $(L_1,\\ldots,L_N)$-smooth relative to $h$ when each blockwise function $\\varphi_i^x(z)=L_i h(x+U_i(z-x_i))-f(x+U_i(z-x_i))$ is convex; this yields a blockwise descent inequality without any Lipschitz constant for $\\nabla_i f$. With step sizes $\\gamma_i<1/L_i$, each block update decreases $\\phi$ by a positive multiple of the block Bregman distance, and the optimality conditions of the subproblem provide a subgradient of $\\phi$ at the new point whose norm is bounded by the iterate gap. Theorem 3.4 then gives subsequential convergence to critical points of bounded sequences, Theorem 3.8 gives global convergence and finite length under the Kurdyka-Łojasiewicz property, and Theorem 3.11 gives finite, linear, or sublinear rates depending on the Łojasiewicz exponent. For penalized ONMF, the kernel $h(U,V)=(\\beta_1/2\\|U\\|_F^2+1)(\\alpha_2/4\\|V\\|_F^4+\\beta_2/2\\|V\\|_F^2+1)$ makes the objective multi-block relatively smooth, and the $U$- and $V$-subproblems are solved in closed form, the latter through the root of a scalar cubic.","pith_inferences":["The paper stops at the penalized ONMF objective; establishing a homotopy between stationary points of (4.6) and critical points of the exact problem (4.2) would turn the continuation procedure in Algorithm 3 from a heuristic into a certified method.","The multi-block relative smoothness setting is not tied to the ONMF kernel; it should transfer to other block factorization models, such as sparse NMF or nonnegative tensor factorization, once a sum- or product-separable kernel satisfying the blockwise convexity inequalities is identified.","The closed-form $V$-update uses Cardano's formula for a scalar cubic; a numerically guarded root solve of the same cubic would improve stability at scale without changing the convergence guarantees."],"forward_implications":["Every bounded BPALM orbit has all its cluster points in the critical set of the composite objective, so stationarity can be certified without knowing partial-gradient Lipschitz constants.","Under the Kurdyka-Łojasiewicz property the whole sequence converges to a single critical point and the successive-iterate gaps are summable.","The Łojasiewicz exponent controls the speed: finite termination for $\\theta=0$, linear convergence for $\\theta\\in(0,1/2]$, and sublinear convergence for $\\theta\\in(1/2,1)$.","For penalized ONMF, both block updates are closed-form operations, so each sweep of BPALM or A-BPALM is deterministic and cheap, which is what makes large-scale use plausible.","The adaptive backtracking variant A-BPALM inherits the subsequential and global convergence results while bounding the number of extra oracle calls per sweep."],"supporting_citations":[{"why":"Supplies the relative-smoothness descent lemma that the paper extends from one block to many.","marker":"[11]"},{"why":"Introduces relative smoothness and the Bregman-kernel formalism that Definition 2.4 generalizes.","marker":"[43]"},{"why":"Provides the proximal alternating linearized template and the Kurdyka-Łojasiewicz convergence machinery BPALM builds on.","marker":"[21]"},{"why":"Supplies subdifferential calculus and KL-based convergence arguments for nonsmooth nonconvex composite minimization.","marker":"[5]"},{"why":"Gives the N=2 B-PALM special case that BPALM covers when N=2 and g1=g2=0.","marker":"[40]"},{"why":"Shows the C-PALM algorithm recovered when the kernel is the squared Euclidean norm.","marker":"[53]"},{"why":"Formulates ONMF as a clustering problem and supplies the SVD-based initialization used in the numerical experiments.","marker":"[49]"},{"why":"Defines h-prox-boundedness and the Bregman forward-backward mapping properties used in Proposition 2.7.","marker":"[2]"},{"why":"Supplies the Hubble telescope spectral data set used in the numerical comparison.","marker":"[47]"}],"fun_headline_variants":["Bregman alternating method converges on nonconvex ONMF","Closed-form Bregman updates for orthogonal NMF convergence","No Lipschitz constants needed: Bregman alternating for ONMF","Multi-block Bregman alternating minimization reaches critical points","BPALM and A-BPALM: Bregman alternating with ONMF closed forms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that solving the penalized problem (4.6) with an increasing penalty parameter $\\lambda$ is a faithful route to the original orthogonal NMF problem (4.2); the paper does not prove a stationary-point correspondence between the two problems, and its own Table 1 shows that larger initial $\\lambda$ can worsen reconstruction error.","fun_headline_variants_meta":{"raw":{"variants":["Bregman alternating method converges on nonconvex ONMF","Closed-form Bregman updates for orthogonal NMF convergence","No Lipschitz constants needed: Bregman alternating for ONMF","Multi-block Bregman alternating minimization reaches critical points","BPALM and A-BPALM: Bregman alternating with ONMF closed forms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001009,"raw_usage":{"total_tokens":4302,"prompt_tokens":1020,"completion_tokens":3282,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":636,"completion_tokens_details":{"reasoning_tokens":3190}},"tokens_in":636,"tokens_out":3282,"duration_ms":25480,"temperature":1.0,"reasoning_tokens":3190,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:15:32.852049+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a bounded sequence generated by Algorithm 1 that satisfies all assumptions of Theorem 3.4 but whose cluster set contains a point $x^\\star$ with $0\\notin\\partial\\phi(x^\\star)$; for instance, engineer two-block nonconvex terms $g_i$ with flat regions to create a spurious accumulation point, and check the subgradient residual (3.6) along the orbit. Alternatively, enumerate exact solutions of the hard ONMF problem (4.2) for a small random matrix and check whether continuation applied to (4.6) returns a KKT point of the hard problem; failure would falsify the paper's implied penalty route.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the relative-smoothness descent lemma that the paper extends from one block to many."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces relative smoothness and the Bregman-kernel formalism that Definition 2.4 generalizes."},{"cited_title":"B olte, S","cited_arxiv_id":null,"evidence_quote":"Provides the proximal alternating linearized template and the Kurdyka-Łojasiewicz convergence machinery BPALM builds on."},{"cited_title":"A ttouch, J","cited_arxiv_id":null,"evidence_quote":"Supplies subdifferential calculus and KL-based convergence arguments for nonsmooth nonconvex composite minimization."},{"cited_title":"S hefi and M","cited_arxiv_id":null,"evidence_quote":"Shows the C-PALM algorithm recovered when the kernel is the squared Euclidean norm."},{"cited_title":"P ompili, N","cited_arxiv_id":null,"evidence_quote":"Formulates ONMF as a clustering problem and supplies the SVD-based initialization used in the numerical experiments."},{"cited_title":"A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima","cited_arxiv_id":"1905.11904","evidence_quote":"Defines h-prox-boundedness and the Bregman forward-backward mapping properties used in Proposition 2.7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Hubble telescope spectral data set used in the numerical comparison."}],"review_version":1}