{"id":"ee12d56f-b05f-45b1-a170-5eab02683410","arxiv_id":"2501.19372","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A unified framework of exact and heuristic methods for minimizing sums of pointwise minima of convex functions, including a compact big-M mixed-integer formulation and relaxed alternating minimization with convergence guarantees.","lead":"This paper presents new methods for minimizing a sum of terms, where each term is the smallest of several convex functions, a problem class covering clipped losses and facility location. The authors provide exact mixed-integer formulations and a family of fast local heuristics with proven convergence to critical points.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's critical-point guarantee is vacuous unless the iterates have a cluster point; boundedness/coercivity is missing and the proof also silently assumes G* is continuous.","rationale":"The reader's weakest-assumption analysis identifies the same load-bearing concern I find: Theorem 3.3(ii) is only meaningful if the sequence {(x_k, Q_k)} has at least one cluster point, and the paper never states boundedness of X or of the iterates, nor coercivity of the convex subproblems. The proof's contradiction argument needs infinitely many iterates with G* ≥ ι near a cluster point, so without existence of a cluster point the theorem's conclusion is vacuous. The attached continuity hypothesis on G* is a second, smaller gap: G* is a difference of lower semicontinuous convex functions and need not be continuous on the boundary of the domain without extra assumptions. Both issues are addressable by adding standard assumptions (compactness, or uniform level-boundedness, plus continuity of the component functions on X), so they do not invalidate the algorithm's design or the proof strategy. A conditional verdict is therefore appropriate; the paper should state the missing hypotheses explicitly rather than leaving them implicit. My concern does not shift the reader's verdict, hence 'UNCHANGED'.","tokens_in":31639,"tokens_out":24205,"duration_ms":282230,"concrete_test":"Insert into Section 3.4 the explicit hypothesis that X is compact, or that the iterates satisfy sup_k ||x_k|| < ∞ / that ar F(·, Q) is uniformly coercive in Q, and re-run the proof of Theorem 3.3 verbatim. If the proof goes through without any further new hypothesis, the missing boundedness is exactly the load-bearing gap. To test whether the gap is merely cosmetic, also attempt to construct an admissible instance (e.g., X = R with components whose common argmin oracle is unbounded) on which Algorithm 1 with the Lemma 3.2 epsilon rule produces sup_k ||x_k|| = ∞ while satisfying monotonicity; success shows the theorem needs an explicit boundedness assumption, and failure indicates a proof of self-boundedness should be supplied.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim, Theorem 3.3(ii), states that every cluster point of the r-AM sequence {x_k} is a critical point of (SMC). The proof in Section 3.4 requires an actual cluster point of the joint sequence {(x_k, Q_k)}: it fixes such a cluster point, uses continuity of G* to transfer a positive gain at that point to infinitely many nearby iterates, and derives a contradiction with boundedness from below. None of the stated assumptions guarantee that {x_k} has a convergent subsequence. X is not assumed compact, and the convex functions are not assumed coercive or uniformly level-bounded in Q. Assumption 1 only says a deterministic argmin oracle exists for each Q; it does not prevent that oracle from selecting a divergent sequence of argminima as Q varies. If {x_k} has no cluster point, the conclusion 'every cluster point is critical' is vacuously true, but the advertised convergence to critical points is empty. A second unstated hypothesis is used in the same proof: G*(x,Q) is assumed continuous at cluster points, which requires continuity of the component functions and ar h on X, not merely closedness and convexity. Both omissions are fixable, but without them the main convergence theorem is incomplete as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the minimization of a sum of pointwise minima of convex functions (SMC), a nonsmooth nonconvex problem that includes clipped convex regression and facility location as special cases. The authors propose two complementary instruments. First, a global approach: a compact big-M mixed-integer convex program (MICP) reformulation of SMC, avoiding the many copies of the primal variable required by the perspective reformulation, plus a local variant that replaces the objective by a reduced model using only active components near a candidate point. Second, a local approach: a bi-convex reformulation (BIC-SMC) of SMC, from which a family of relaxed alternating minimization (r-AM) methods is derived; the r-AM methods differ from standard alternating minimization only in the Q-update, and include a safeguarded exploration step governed by Lemma 3.2. The central theoretical result, Theorem 3.3, states that every cluster point of the r-AM sequence is a critical point of SMC. The paper also reports numerical experiments on piecewise-linear regression and restricted facility location, where r-AM variants (SM and MM) outperform AM and DCA in most tested settings, and a procedure for certifying local optimality on neighbourhoods using the local MICP model.","tokens_in":31927,"tokens_out":4380,"duration_ms":49693,"significance":"If the convergence theorem and the local-optimality certification procedure are correct, the paper makes a useful contribution: it provides a flexible family of first-order methods for a broad class of nonsmooth nonconvex problems, with a proof that cluster points satisfy first-order necessary conditions, and it gives a practical MICP-based way to check and possibly escape from critical points. The numerical evidence that the proposed r-AM variants improve over AM and DCA on realistic benchmarks is valuable, and the authors state that code and a package are publicly available. The paper also contains clearly useful reformulation machinery (big-M bounds, local model, bi-convex model) with several examples where the bounds are computed in closed form. However, the main convergence theorem has a load-bearing gap related to existence of cluster points and an unstated continuity assumption, and the local-optimality certification counts in Section 4.3 appear to overstate what a timeout outcome alone can certify. With these points fixed, the paper would make a solid contribution to nonsmooth nonconvex optimization.","major_comments":[{"comment":"The proof of part (ii) fixes an arbitrary cluster point (x⊥, Q⊥) of the sequence {(x_k, Q_k)} and uses an infinite subsequence converging to it, but no stated assumption guarantees that such a cluster point exists. X is not assumed compact, and the component functions and main function are only assumed closed, proper and convex on Rd; Assumption 1 only requires a deterministic argmin oracle, which does not prevent the oracle from returning a divergent sequence of minimizers as Q varies. If the sequence has no cluster point, the statement 'every cluster point is critical' is vacuously true and the advertised convergence guarantee is empty. The theorem should either add an explicit boundedness or coercivity assumption ensuring that the iterates remain in a compact set, or state the conclusion conditionally on the existence of a cluster point.","section":"Theorem 3.3 (Section 3.4)"},{"comment":"The exploration rule (63) contains a division by the quantity ⟨q̂_+^{(s)} − (q*)^{(s)}, h^{(s)}(x_+)⟩, which can be zero even when q̂_+^{(s)} ≠ (q*)^{(s)}, for instance when all components of h^{(s)}(x_+) are equal. The paper's footnote only specifies the case q̂_+^{(s)} = (q*)^{(s)}, in which ε^{(s)} is set to 1; the zero-denominator case with q̂_+^{(s)} ≠ (q*)^{(s)} is left undefined. This is load-bearing because the sufficient decrease bound used in Theorem 3.3 relies on the inequality from Lemma 3.2 holding for every iteration. A complete rule for this case must be provided and the sufficient decrease inequality verified.","section":"Lemma 3.2, Eq. (63)"},{"comment":"The proof of part (ii) asserts that G*(x,Q) is continuous in (x,Q) ∈ X × Q, and uses this continuity to transfer a positive gain at the cluster point to infinitely many nearby iterates. This continuity does not follow from the stated assumptions: closedness and convexity of the extended-valued functions h̄ and h_l imply continuity only on the relative interiors of their domains, not on the whole feasible set X, and X has not been assumed compact. Either a continuity assumption on the component functions over X must be added explicitly, or the proof must justify the continuity from the problem data and the chosen topology.","section":"Theorem 3.3 proof, continuity of G*"},{"comment":"The procedure reports as 'local optimality certifications' the number of trials in which the solver did not find a point x_new with F(x_new) ≤ F(x̂) − δ_glob within the 120-second time limit. This outcome does not by itself certify local optimality of x̂: a timeout also produces that outcome without solving (45) to global optimality. The counts (e.g., 5/5 for several datasets) therefore depend on solver time limits and do not, as reported, establish that the candidates are local minimizers. The authors should record the solver termination status (proven optimal versus stopped at node limit/time limit) and count as certifications only the cases where (45) was solved to proven global optimality.","section":"Section 4.3, local optimality certification counts"},{"comment":"Proposition 1.6 is stated as applying 'verbatim' from the authors' prior work [11] (Proposition 1.4). Since the proof is not reproduced and the proposition is used as a basis for the local model in Lemma 2.3 and Corollary 2.4, it would strengthen the paper to either state the precise assumptions under which [11, Proposition 1.4] applies to the present setting (including the role of X and the continuity of the components) or give a short proof in the appendix.","section":"Proposition 1.6"}],"minor_comments":[{"comment":"The κ_k expressions in Table 1 are ambiguous; for example, 'κ_k = (3/2)^k 3/4' is not a standard notation. Please write the schedule explicitly, e.g., κ_k = (3/2)^{3k/4}, and clarify the role of k in each schedule.","section":"Table 1"},{"comment":"The statement that zero gain implies criticality is named Lemma 2.6 in the Contributions list (Section 1.2) but Proposition 2.6 in Section 2.3 and later in the proof of Theorem 3.3; the numbering should be harmonized.","section":"Section 2.3"},{"comment":"Equation (31) writes '−M(s)_l+,l ← min_u ...' with a negative sign on the left-hand side, which is confusing. Please define the sign convention explicitly and check whether the formula yields a valid upper bound M(s)_l+,l.","section":"Equation (31)"},{"comment":"The stopping criterion in Algorithm 1 uses the quantity υ − F(x_k), where υ stores F̄(x_k, Q_k) after the update, but F(x_k) is a separate function evaluation. The pseudocode should state that this evaluation is performed at each iteration and clarify the relationship between F(x_k) and the stored value υ, especially in the first iteration where υ = ∞.","section":"Algorithm 1"},{"comment":"There are several typographical slips, for example 'for for every' in equation (69), 'Baratt-Boyd' in Table 1 versus 'Barratt' in the text, and 'minimization of (45)' in Section 4.3 where the minimization problem is (44) or (45) depending on the surrounding discussion. These do not affect the mathematics but should be corrected in a final version.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper's main convergence theorem is attractive but currently has a real gap regarding the existence of cluster points and a missing continuity hypothesis for G*. Both are fixable without changing the algorithm or the overall architecture of the proof. The more serious data-integrity issue is the overcounting of local-optimality certifications in Section 4.3, where timeout outcomes are listed as certifications. If the authors report solver termination status and restrict certification claims to proven-optimal solves, the empirical claims would be sound. The heavy reliance on the authors' own paper [11] for Proposition 1.6 is acceptable as a citation, but the referee should verify that the cited result indeed covers the current setting before publication. Overall, the paper is publishable after these revisions; I recommend major revision rather than rejection because the core ideas are coherent and the numerical results appear informative once the certification counts are corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis one is worth a serious look. It extends the clipped-convex framework of Barratt et al. to problems where each term is the pointwise minimum of arbitrarily many convex functions, and it does two things well: a compact big-M mixed-integer convex reformulation that avoids the variable copies of the perspective approach, and a family of local heuristics (r-AM) that includes plain AM as a special case. The convergence theorem for r-AM is the main theoretical draw: every cluster point is critical, with an explicit O(1/K) bound on the best gain. That theorem is mostly proved and the logic is sound.\n\nThe real gap is in Theorem 3.3. The proof needs a cluster point of the iterates to run the contradiction argument, but X is not assumed compact and the components are not assumed coercive. Without a boundedness or coercivity assumption, the iterates can diverge, and then “every cluster point is critical” is vacuously true but empty. The fix is one line: add “X bounded”, “F coercive”, or explicitly state the theorem as a conditional on the existence of cluster points. The bound (66) is still valid regardless, but the advertised convergence to critical points needs the extra assumption. The continuity of G* used in the proof is not a gap, since the problem statement already assumes continuous component functions.\n\nLemma 3.2’s epsilon rule has an undefined denominator when the candidate and the AM weight have the same inner product with h, i.e. when the candidate is also a minimizer. The footnote covers the q̂ = q* case only; a clean sentence covering the zero-denominator case (set ε = 1) would finish the job. This is a minor presentation fix.\n\nThe empirical work is honest: real datasets, multiple restarts, and comparison against DCA and the Barratt-Boyd baseline. The hyperparameter schedules are tuned on the same data, which the authors admit; that is a mild weakness but not disqualifying. The local certification procedure using ρ-active sets is actually conservative rather than overstated, because a superset of the true active set gives a lower bound on F, so proving no improvement in the relaxed model does certify local optimality.\n\nWho is this for: researchers in nonconvex optimization, operations research, and machine learning who deal with piecewise-linear regression, facility location, or MICP reformulations. It deserves a serious referee. My recommendation: accept pending minor revisions, mainly adding the missing assumption in Theorem 3.3 and cleaning up the epsilon rule.","headline":"Solid extension of clipped-convex to sums of minima with a compact MICP and a useful family of local heuristics; the main convergence theorem has a missing boundedness assumption that is easy to fix.","tokens_in":32451,"tokens_out":5997,"would_cite":true,"duration_ms":63971,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C11","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Relaxed alternating minimization, applied to sums of pointwise minima of convex functions, has every accumulation point of its iterates be a critical point, and a compact big-M mixed-integer convex program gives exact global and local…","keywords":["sum of pointwise minima of convex functions","clipped convex functions","nonconvex optimization","alternating minimization","mixed-integer convex programming","big-M reformulation","local optimality certification","piecewise-linear regression"],"falsifier":"Run r-AM on a bounded, fully-active instance from Proposition 1.1 with $d=N=1$, $n_s=2$, $X=[-10,10]$, and fixed $C_k=1/2$, starting from a weight vector at a point where the gain $G^*$ is strictly positive. Evaluate the gain at every accumulation point of the resulting sequence; the theorem predicts $G^*=0$ at each one, so discovering a single cluster point with strictly positive gain would disprove Theorem 3.3.","tokens_in":31397,"feed_emoji":"🧮","tokens_out":6436,"duration_ms":64455,"temperature":0.7,"pith_summary":"The paper studies problem (SMC): minimize a convex main function plus an average of N terms, where each term is the pointwise minimum of finitely many convex component functions. This covers truncated losses, piecewise-linear regression, and restricted facility location, and the problem is NP-hard in general. The authors' central claim is that a family of relaxed alternating minimization (r-AM) heuristics, built from a bi-convex reformulation and safeguarded exploration of the weights, converges in the sense that every cluster point of its iterates is a critical point of the nonconvex problem. The same reformulations yield a compact big-M mixed-integer convex program for global solution, plus a localized version that can certify local optimality of a candidate or produce a strictly better point. A sympathetic reader would care because this gives hard nonconvex problems a local method with formal first-order guarantees and a practical route to check optimality locally.","feed_headline":"Relaxed alternating minimization provably converges to critical points","feed_subtitle":"New big-M and bi-convex reformulations make sums of pointwise minima practical to solve and certify locally.","key_machinery":"The load-bearing objects are the bi-convex reformulation (BIC-SMC), in which $F(x)=\\min_Q \\bar F(x,Q)$ over a product of simplices, and the gain $G^*(x_+,Q)=\\bar F(x_+,Q)-\\min_{\\tilde Q}\\bar F(x_+,\\tilde Q)$, which measures how much can still be gained at fixed $x$ by reoptimizing the weights. Lemma 3.2's exploration bound fixes the exploration ratios so that $\\bar F(x_+,Q)-\\bar F(x_+,Q_+)\\ge (1-C)G^*(x_+,Q)$; this single inequality creates the sufficient descent that powers the convergence proof. The third object is the big-M epigraph reformulation, where binary variables select the active component of each term and $S$-bounds $M^{(s)}_{l_+,l}$ majorize component differences; the local version restricts binary variables to the degeneracy set $I(\\hat x)$, making local optimality checks scale with the degeneracy factor, the number of component combinations active at the candidate.","core_discovery":"On its own terms, the paper's central discovery is that the nonconvex objective can be rewritten as a bi-convex function of the variable $x$ and of weight vectors $Q$ in a product of simplices: for fixed weights the problem is convex, and for fixed $x$ the optimal weights identify the active components. Classical alternating minimization (AM) is the special case that always moves all weight to an active component. The paper shows that replacing the exact weight minimization by a convex combination of AM weights and an exploration candidate, with the mixing ratio set by Lemma 3.2 so that a fixed fraction $(1-C_k)$ of the current gain is retained, preserves sufficient descent. Summing these descents yields an $O(1/((1-\\bar C)K))$ bound on the best gain and, by continuity of the gain, implies that every cluster point of $\\{x_k\\}$ is critical (Theorem 3.3). A parallel contribution is an equivalent big-M mixed-integer convex program for (SMC) that uses one set of binary selection variables per term and no extra copies of $x$, together with a localized version whose solution either certifies local optimality of a candidate or produces a strictly better point.","pith_inferences":["The convergence theorem's unstated reliance on boundedness of the iterates suggests that, for unbounded feasible sets, practitioners should add an explicit bound or safeguard; otherwise the phrase 'every cluster point is critical' is vacuous when no cluster point exists.","The numerical gap between softmin r-AM and AM grows with the number of components per term, which suggests that r-AM's benefit over AM scales with the amount of near-degeneracy in the component values rather than with problem dimension alone.","The local optimality certificate could be turned into a practical branch-and-search loop: run a local method, certify or improve on its output with the localized MICP, and repeat; this loop's performance against a global solver is a natural benchmark the paper does not run.","Because the big-M constants in the local model only need to be valid on a neighbourhood, progressively enlarging that neighbourhood gives a computable, though not guaranteed, way to distinguish local minima from mere critical points."],"forward_implications":["For any instance satisfying the stated assumptions, every r-AM method with any exploration candidate produces iterates whose cluster points are critical, so the heuristics carry first-order stationarity guarantees rather than only empirical support.","The gain bound (66) gives an explicit iteration complexity: reaching gain below $\\delta$ requires at most $(\\hat F-F^*)/((1-\\bar C)\\delta)$ iterations, each costing one convex solve and one component evaluation.","The compact big-M MICP introduces $O(N\\max_s n_s)$ binary variables and no extra copies of $x$, in contrast to the perspective reformulation of [6] that uses $N$ extra copies of the decision variable; this makes global and local mixed-integer solving more tractable.","Corollary 2.4 converts local optimality certification into a computation: solving the localized problem (45) on a neighbourhood either certifies the candidate or returns a strictly better point from which to restart local search."],"supporting_citations":[{"why":"Supplies the clipped-convex (SCC) model, its bi-convex reformulation, the perspective MICP that this paper extends, and the Baratt-Boyd inexact weight update used as a baseline candidate.","marker":"[6]"},{"why":"Provides Proposition 1.4, which guarantees that active sets at nearby points are contained in $\\rho$-active sets at the candidate and is the basis for the local model (43)-(44).","marker":"[11]"},{"why":"Gives the truncated-convex framework, range-cut applications, and the low-dimensional global method against which the proposed local methods are positioned.","marker":"[23]"},{"why":"Defines the piecewise-linear L1-regression model and its DC optimization treatment, used as the main benchmark instance in Section 4.1.","marker":"[4]"},{"why":"Provides the alternating-minimization convergence framework that motivates the bi-convex approach and contains classical AM as the $\\varepsilon=0$ special case.","marker":"[15]"},{"why":"Defines DC programming and DCA, the baseline algorithm whose critical-point concept is adopted in Definition 1.3 and whose performance is compared in the experiments.","marker":"[21]"},{"why":"Supplies the improved big-M reformulation technique that the compact MICP (40)-(41) adapts to the sum-of-pointwise-minima structure.","marker":"[35]"}],"fun_headline_variants":["Bi-convex reformulation yields convergent r-AM for SMC","New r-AM method guarantees critical points for sum of minima","Compact big-M MICP for SMC with local optimality check","Relaxed AM outperforms DC and AM on clipped convex sums","SMC solved via bi-convexity and big-M convex programs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the sequence of r-AM iterates stays bounded, or otherwise has at least one cluster point; the claim 'every cluster point is critical' is only meaningful and only proved under that condition, yet boundedness is not listed among the theorem's assumptions.","fun_headline_variants_meta":{"raw":{"variants":["Bi-convex reformulation yields convergent r-AM for SMC","New r-AM method guarantees critical points for sum of minima","Compact big-M MICP for SMC with local optimality check","Relaxed AM outperforms DC and AM on clipped convex sums","SMC solved via bi-convexity and big-M convex programs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000306,"raw_usage":{"total_tokens":1861,"prompt_tokens":1162,"completion_tokens":699,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":778,"completion_tokens_details":{"reasoning_tokens":609}},"tokens_in":778,"tokens_out":699,"duration_ms":7258,"temperature":1.0,"reasoning_tokens":609,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T20:19:08.628826+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run r-AM on a bounded, fully-active instance from Proposition 1.1 with $d=N=1$, $n_s=2$, $X=[-10,10]$, and fixed $C_k=1/2$, starting from a weight vector at a point where the gain $G^*$ is strictly positive. Evaluate the gain at every accumulation point of the resulting sequence; the theorem predicts $G^*=0$ at each one, so discovering a single cluster point with strictly positive gain would disprove Theorem 3.3.","supporting_citations":[{"cited_title":"Barratt, G","cited_arxiv_id":null,"evidence_quote":"Supplies the clipped-convex (SCC) model, its bi-convex reformulation, the perspective MICP that this paper extends, and the Baratt-Boyd inexact weight update used as a baseline candidate."},{"cited_title":"Global minimization of a minimum of a finite collection of functions","cited_arxiv_id":"2412.04625","evidence_quote":"Provides Proposition 1.4, which guarantees that active sets at nearby points are contained in $\\rho$-active sets at the candidate and is the basis for the local model (43)-(44)."},{"cited_title":"Liu and H","cited_arxiv_id":null,"evidence_quote":"Gives the truncated-convex framework, range-cut applications, and the low-dimensional global method against which the proposed local methods are positioned."},{"cited_title":"Bagirov, S","cited_arxiv_id":null,"evidence_quote":"Defines the piecewise-linear L1-regression model and its DC optimization treatment, used as the main benchmark instance in Section 4.1."},{"cited_title":"Grippo and M","cited_arxiv_id":null,"evidence_quote":"Provides the alternating-minimization convergence framework that motivates the bi-convex approach and contains classical AM as the $\\varepsilon=0$ special case."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines DC programming and DCA, the baseline algorithm whose critical-point concept is adopted in Definition 1.3 and whose performance is compared in the experiments."},{"cited_title":"Trespalacios and I","cited_arxiv_id":null,"evidence_quote":"Supplies the improved big-M reformulation technique that the compact MICP (40)-(41) adapts to the sum-of-pointwise-minima structure."}],"review_version":1}