{"id":"893ef49e-212b-4a0d-848a-96ccbd1e7e49","arxiv_id":"2304.03641","paper_version":4,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"OBCD is a feasible block coordinate descent algorithm for nonsmooth composite optimization under orthogonality constraints that updates k rows per iteration, proves completeness of the scheme, stronger global block-k stationary points, and O(1/ε) complexity to ε-block-k stationary points.","lead":"The paper introduces OBCD, a block coordinate descent method that solves nonsmooth composite optimization problems with orthogonality constraints by updating k rows at a time and globally solving the resulting small subproblems. A smart generalist might read it to learn about new feasible algorithms with stronger optimality guarantees for constrained problems common in statistical learning and data science.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Global optimality of k-row subproblems via breakpoint search is assumed without explicit verification of the search procedure's completeness","rationale":"The reader's weakest_assumption correctly isolates the single assumption on which every subsequent guarantee rests. Because the full text is now available, the concern can be stated more precisely as the lack of a completeness argument for the breakpoint enumeration itself rather than merely its existence. This moves the verdict from UNVERDICTED to CONDITIONAL pending explicit verification that the subproblem solver is globally correct.","tokens_in":1805,"tokens_out":369,"duration_ms":9222,"concrete_test":"Construct a 3-row subproblem (k=3) with a nonsmooth term whose breakpoints are known analytically; enumerate all candidate points by the paper's breakpoint procedure and compare against exhaustive grid search over the Stiefel manifold (or a high-resolution discretization); if the procedure misses a point whose objective is strictly lower, the global-optimality claim is falsified.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claims (completeness of row-wise updates, global block-k stationarity of limit points, and O(1/ε) iteration complexity to ε-block-k stationarity) all require that each block subproblem—minimize a nonsmooth composite objective subject to orthogonality on exactly k rows—is solved to global optimality. The paper states that novel breakpoint search methods achieve this, yet the argument provides no explicit proof that the breakpoint enumeration covers all candidate points or that the nonsmooth terms (e.g., ℓ1 or indicator functions) do not create additional stationary points missed by the search. If any subproblem instance admits a better feasible point than the breakpoint method returns, the descent property used in the convergence analysis fails and the complexity bound does not hold.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proposes OBCD, a block coordinate descent algorithm for nonsmooth composite optimization subject to orthogonality constraints. In each iteration, k rows (k≥2) of the matrix variable are updated by globally solving a small nonsmooth subproblem under row-wise orthogonality constraints, using novel breakpoint search methods. The central claims are: (i) the row-wise orthogonal update scheme is complete, i.e., any feasible point is reachable from any feasible initialization; (ii) limit points are global block-k stationary points, a stronger notion than standard critical points; (iii) OBCD reaches an ε-block-k stationary point in O(1/ε) iterations; (iv) non-ergodic convergence rates hold under the KL inequality; and (v) the method empirically outperforms existing approaches on statistical learning tasks.","tokens_in":1960,"tokens_out":498,"duration_ms":25438,"significance":"If the central claims hold, the work supplies a feasible, low-footprint method with explicit iteration complexity and a strictly stronger stationarity concept for a practically relevant class of orthogonality-constrained nonsmooth problems. The completeness result for the update scheme and the O(1/ε) bound to ε-block-k stationarity are notable strengths that would distinguish the contribution from standard BCD analyses.","major_comments":[{"comment":"The section describing the breakpoint search methods for the k-row subproblems: the manuscript asserts that these methods solve each nonsmooth composite subproblem to global optimality, yet supplies no explicit argument that the enumerated breakpoints cover every candidate point or that the nonsmooth terms (ℓ1, indicators, etc.) cannot introduce additional stationary points missed by the search. Because global optimality of every block update is required for the descent property, the completeness theorem, the definition of global block-k stationarity, and the O(1/ε) complexity bound all rest on this unverified claim.","section":"subproblem solver description (near the statement of the breakpoint search)"},{"comment":"Theorem establishing the O(1/ε) iteration complexity: the proof invokes that each subproblem is solved to global optimality to obtain a uniform descent amount; if the breakpoint procedure returns only a local solution on some instances, the descent lemma fails and the complexity guarantee does not hold.","section":"complexity theorem"}],"minor_comments":[],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the detailed and constructive report. The two major comments correctly identify that the current manuscript asserts global optimality of the breakpoint search procedures for the k-row subproblems but does not supply an explicit, self-contained argument that the enumerated breakpoints exhaust all candidate minimizers and that the nonsmooth terms cannot create additional stationary points outside the search. We will address this gap by adding the required proof in the revised version; the remainder of the analysis then follows as stated.","responses":[{"response":"We agree that an explicit verification is required. In the revised manuscript we will insert a dedicated subsection (immediately following the description of the breakpoint search) that proves: (i) every point at which the subdifferential of the nonsmooth composite objective can contain zero under the row-wise orthogonality constraint must coincide with one of the enumerated breakpoints or an endpoint of the feasible interval; (ii) the nonsmooth terms (ℓ1 norms and indicator functions) contribute only finitely many additional candidate points that are already captured by the breakpoint enumeration; and (iii) exhaustive evaluation at these points therefore yields the global minimizer. This argument will be written in a self-contained manner so that the descent property, completeness of the update scheme, global block-k stationarity, and complexity bound rest on a fully justified foundation.","revision_made":"yes","referee_comment":"[subproblem solver description (near the statement of the breakpoint search)] The section describing the breakpoint search methods for the k-row subproblems: the manuscript asserts that these methods solve each nonsmooth composite subproblem to global optimality, yet supplies no explicit argument that the enumerated breakpoints cover every candidate point or that the nonsmooth terms (ℓ1, indicators, etc.) cannot introduce additional stationary points missed by the search. Because global optimality of every block update is required for the descent property, the completeness theorem, the definition of global block-k stationarity, and the O(1/ε) complexity bound all rest on this unverified claim."},{"response":"The complexity proof indeed relies on a uniform descent amount that is guaranteed only when each block subproblem is solved to global optimality. Once the explicit argument requested in the first comment is added, the descent lemma holds without qualification and the O(1/ε) bound follows exactly as written. No change to the statement or proof structure of the complexity theorem itself will be needed beyond referencing the new subsection on global optimality of the subproblem solver.","revision_made":"yes","referee_comment":"[complexity theorem] Theorem establishing the O(1/ε) iteration complexity: the proof invokes that each subproblem is solved to global optimality to obtain a uniform descent amount; if the breakpoint procedure returns only a local solution on some instances, the descent lemma fails and the complexity guarantee does not hold."}],"tokens_in":1547,"tokens_out":597,"duration_ms":14859,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's main contribution is the OBCD algorithm, which does block coordinate descent by updating exactly k rows at a time while staying feasible. It proves that these updates are complete, meaning you can reach any feasible matrix from any feasible starting point. It also defines global block-k stationary points as a stronger notion than ordinary critical points and shows an O(1/ε) iteration bound to reach an ε-block-k stationary point, plus non-ergodic linear rate under the KL property. The method keeps a small per-iteration cost and the abstract reports better empirical performance than prior approaches on the tested problems. That package of results is new relative to the BCD literature cited in the abstract. The work is clearly aimed at people who need feasible methods for orthogonality-constrained nonsmooth problems in statistical learning. The formal claims are stated directly and the citation pattern looks standard. The soft spot is the subproblem solver. The entire descent property, stationarity guarantee, and complexity bound require that each k-row nonsmooth subproblem is solved to global optimality. The paper says novel breakpoint search methods handle this, but if the enumeration misses candidate points created by the nonsmooth terms, the analysis does not go through. That assumption is load-bearing and needs explicit verification in the proofs. Minor issues like implementation details for the search would be easy to fix in revision. Overall the paper shows clear thinking on the algorithmic structure and the stationarity definitions. It is worth sending to peer review so referees can check the breakpoint completeness argument and the empirical setup in detail.","headline":"OBCD adds a completeness result for k-row orthogonal updates and a stronger global block-k stationarity notion, plus O(1/ε) complexity, but everything rests on the breakpoint search actually solving the nonsmooth subproblems to global optimality.","tokens_in":2448,"tokens_out":402,"would_cite":false,"duration_ms":27453,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/AlexanderDuality.lean","rs_theorem":"alexander_duality_circle_linking","paper_passage":"We also demonstrate how novel breakpoint search methods can be used to solve the subproblems arising in OBCD... Any orthogonal matrix V ∈ St(2,2) can be expressed as V = Vrot_θ or V = Vref_θ ... min_θ ½∥V∥²_Q + ⟨V,P⟩ + h(VZ) s.t. V ∈ {Vrot_θ, Vref_θ}"},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean","rs_theorem":"reality_from_one_distinction","paper_passage":"We prove the completeness of the proposed update scheme, showing that row-wise orthogonal updates can reach any feasible point from any feasible initialization... limit points ... global block-k stationary points"}],"headline":"Block-coordinate Stiefel optimizer with breakpoint search on Givens/Jacobi rotations; no RS cost, ratio symmetry or forcing-chain structure","alignment":"orthogonal","rationale":"Paper's core machinery (row-wise BCD on St(n,r), exact solution of k-row subproblems via breakpoint enumeration on Vrot_θ / Vref_θ, block-k stationarity, O(1/ε) ergodic rate) lives entirely in numerical optimization on the orthogonal group. It invokes neither J-cost, φ-ladder, recognition cost functional equations, 8-tick periodicity, nor any parameter-free derivation of constants. The geometric primitives (Givens rotations, reflections) appear in AlexanderDuality only as a topological tool for D=3 forcing; they are not used here to derive any RS theorem. No claim contradicts an RS result (e.g., no dimension or constant assertion). Hence orthogonal to the RS framework.","tokens_in":67909,"confidence":"high","tokens_out":439,"duration_ms":8819,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"OBCD updates k rows at a time by exactly solving small nonsmooth subproblems to reach global block-k stationary points with O(1/ε) iteration complexity.","keywords":["block coordinate descent","orthogonality constraints","nonsmooth composite optimization","global block-k stationary points","iteration complexity","Kurdyka-Lojasiewicz inequality"],"falsifier":"A concrete numerical instance in which breakpoint search returns a suboptimal subproblem solution and the overall algorithm fails to produce a global block-k stationary point, or an experiment showing that more than linear-in-1/ε iterations are required to reach an ε-block-k stationary point.","tokens_in":2692,"feed_emoji":"","tokens_out":665,"duration_ms":23044,"temperature":0.7,"pith_summary":"The paper presents OBCD, a block coordinate descent method for nonsmooth composite optimization under orthogonality constraints. In each step it selects k rows of the current matrix and replaces them by the global minimizer of a small subproblem that keeps the row block orthogonal. The authors prove that such row-wise updates are complete, meaning any feasible point is reachable from any other, and that the limit points satisfy a global block-k stationarity condition stronger than ordinary criticality. They further establish an iteration complexity of O(1/ε) to produce an ε-block-k stationary point and a non-ergodic rate under the Kurdyka–Lojasiewicz inequality.","feed_headline":"OBCD reaches global block-k points in O(1/ε) iterations","feed_subtitle":"Row-wise updates solve small ortho-constrained subproblems exactly and prove completeness plus stronger stationarity than ordinary critical ","key_machinery":"The OBCD row-wise update that globally solves a small nonsmooth optimization problem under orthogonality constraints for any chosen block of k rows.","core_discovery":"The central claim is that the OBCD scheme, by globally solving the nonsmooth subproblems that arise when k rows are updated under orthogonality constraints, produces limit points that are global block-k stationary points and reaches an ε-block-k stationary point after O(1/ε) iterations.","pith_inferences":["If similar globally solvable subproblems exist for other matrix constraints, the same block-update completeness argument could apply.","The stronger stationarity notion may translate into better empirical performance on downstream statistical-learning tasks that rely on orthogonal matrices.","Breakpoint search techniques developed for the subproblems could be reused in other nonconvex composite problems that admit low-dimensional orthogonal blocks."],"forward_implications":["Row-wise orthogonal updates can reach any feasible point from any feasible initialization.","Limit points of OBCD are global block-k stationary points that satisfy stronger optimality than standard critical points.","An ε-block-k stationary point is found after O(1/ε) iterations.","Under the Kurdyka–Lojasiewicz inequality a non-ergodic convergence rate holds."],"fun_headline_variants":["OBCD reaches ε-block-k points in O(1/ε) iterations","OBCD yields global block-k stationary points in O(1/ε)","Row-wise updates give OBCD O(1/ε) block-k stationarity","Block-k points from OBCD stronger than critical points"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The small nonsmooth optimization subproblems under orthogonality constraints that arise when updating k rows can be solved to global optimality using breakpoint search methods.","fun_headline_variants_meta":{"raw":{"variants":["OBCD reaches ε-block-k points in O(1/ε) iterations","OBCD yields global block-k stationary points in O(1/ε)","Row-wise updates give OBCD O(1/ε) block-k stationarity","Block-k points from OBCD stronger than critical points"]},"model":"grok-4.3","cost_usd":0.008201,"raw_usage":{"total_tokens":3734,"prompt_tokens":692,"num_sources_used":0,"completion_tokens":76,"cost_in_usd_ticks":82012000,"prompt_tokens_details":{"text_tokens":692,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2966,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":692,"tokens_out":76,"duration_ms":19500,"temperature":1.0,"reasoning_tokens":2966,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-24T09:20:26.198368+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete numerical instance in which breakpoint search returns a suboptimal subproblem solution and the overall algorithm fails to produce a global block-k stationary point, or an experiment showing that more than linear-in-1/ε iterations are required to reach an ε-block-k stationary point.","supporting_citations":[],"review_version":1}