{"id":"76e1a5c1-8a6e-4b5a-8a88-e73d4fdd30f3","arxiv_id":"2412.08023","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"An ALM with semismooth Newton-CG and an adaptive sieving strategy solves large-scale support matrix machines with per-iteration cost driven by active samples and solution rank.","lead":"Support matrix machines classify matrix-shaped data with a low-rank penalty, but become slow when the sample count is huge. This paper builds a fast augmented Lagrangian solver that exploits the sparse set of active samples and tests it on datasets with up to a million samples.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Per-Newton-iteration residual formation costs O(npq) and is omitted from the Section 4 complexity analysis, so the advertised O(pq max{|J1|,|alpha|}) per-iteration bound is not established for the full algorithm.","rationale":"The reader's weakest assumption focuses on the size of J1 and alpha, which is the condition for the CG matvec to be cheap. My stress test finds a more fundamental gap: the complexity analysis in Section 4 and Table 1 stops at the CG matvec and never accounts for the residual formation required at the start of every Newton iteration and every line-search trial. Equation (17) defines the residual via A^*Pi_S(omega), and omega itself is formed by an O(npq) application of A to the current W (eq. 11). Since W changes each Newton iteration, one cannot amortize this away without an incremental scheme that is not described. Additionally, Pi_S(omega) is supported on all samples with omega_j > 0, i.e., all support matrices, not just J1, so the residual cost scales with |SM|, which Figure 1 shows can be a large fraction of n. Thus the advertised O(pq max{|J1|,|alpha|}) per-iteration cost is not the cost of an iteration of the proposed method; it is only the cost of one CG application within the iteration. The 422.7x speedup statement is also confounded by the warm-starting from isPADMM described in Section 6.2, but that is secondary. The contribution list also contains a reversed inequality (says reduce from O(pq max{|J1|,|alpha|}) to O(npq)), consistent with a possible mix-up of the direction of the improvement. These issues are addressable by a revised complexity accounting and a timing breakdown, so the conditional verdict stands, but the paper should be asked to provide this evidence.","tokens_in":38278,"tokens_out":10746,"duration_ms":109745,"concrete_test":"Add instrumentation to the MATLAB implementation to time three components separately on the (n,p,q)=(10^6,50,100), tau=10, C=0.1 synthetic problem: (a) one evaluation of omega = -lambda - sigma(AW + b y - e_n), (b) one evaluation of A^*Pi_S(omega) for the current residual, and (c) one CG application of eV from (32). If (a)+(b) contributes more than, say, 30% of total wall-clock time and scales roughly linearly in n while (c) scales with |J1| and |alpha|, then the paper's per-iteration complexity claim holds only for the CG matvec and the full iteration remains O(npq)-dominated. Report these timings and the measured |SM| for each test instance so the gap between active and total support matrices is quantified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central complexity claim (Section 1, Table 1) states that the primary per-iteration cost is reduced from O(npq) to O(pq max{|J1|,|alpha|}) by exploiting active support matrices J1 and solution rank |alpha|. Table 1, however, only counts the cost of applying the operator eV in (32) to a direction within the CG loop. It does not include the cost of forming the semismooth Newton residual grad phi_k in (17), which requires computing omega = -lambda_k - sigma_k(AW + b y - e_n) for all n samples (definition (11)) and then A^*Pi_S(omega). Computing AW alone costs O(npq) whenever W changes, which it does at every Newton step and at every line-search trial in Algorithm 2. Moreover, Pi_S(omega) is nonzero for every support matrix (omega_j > 0), not merely for active support matrices in J1, so A^*Pi_S(omega) costs O(|SM|*pq), with |SM| potentially O(n) (Figure 1 shows support-matrix fractions up to 86%). Thus the full per-Newton-iteration cost is at least O(npq) unless an incremental update of AW with reduced cost is described, and no such update is present. The advertised asymptotic improvement therefore applies only to the CG matvec, not to the overall algorithm, and the 422.7x speedup claim over F-ADMM cannot be attributed to the reduced per-iteration complexity without a timing breakdown.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops an augmented Lagrangian method with a semismooth Newton-CG inner solver (ALM-SNCG) for the support matrix machine (model (1)). It exploits two structural properties at KKT points: sample sparsity, expressed through the active support-matrix index set J1, and low rank of the regression matrix W, expressed through the index set α. These are used to reduce the cost of the Hessian-vector product in the Newton linear system from O(npq) to O(pq max{|J1|, |α|}). The paper also proposes an adaptive sieving (AS) strategy for generating solution paths over a grid of C values and proves its finite termination. Numerical experiments on synthetic data with up to one million samples and on four real datasets report substantial speedups over F-ADMM and isPADMM, including an average speedup of 422.7x over F-ADMM on real data.","tokens_in":38579,"tokens_out":9669,"duration_ms":103498,"significance":"If the advertised complexity and convergence results are taken at face value, the paper is a useful step toward making SMM tractable at large sample sizes. The extension of adaptive sieving to sample sparsity is nontrivial, and the experimental scope (up to one million samples) is impressive. The paper also provides concrete KKT-residual stopping criteria and convergence-rate statements, and it includes proofs for the quadratic-growth condition and the finite termination of the AS strategy. However, the advertised per-iteration complexity covers only one Hessian-vector product, not the complete Newton iteration, and the numerical comparison with F-ADMM and isPADMM is weakened by an unexplained warm-start procedure for ALM-SNCG. The contribution is therefore conditionally significant: the algorithmic ideas are sound, but the end-to-end complexity and the fairness of the speedup comparisons need to be established.","major_comments":[{"comment":"The complexity analysis counts only the cost of applying the operator eV in (32) to a direction H inside the CG loop. It does not count the cost of forming the residual grad phi_k in (17) at each Newton step and at each line-search trial. Forming grad phi_k requires the vector omega = -lambda_k - sigma_k(AW + b y - e_n) for all n samples (definition (11)) and the adjoint application A^* Pi_S(omega). For a new W, AW costs O(npq), and Pi_S(omega) is supported on all support matrices, not only on J1; Figure 1 reports support-matrix fractions up to 86%. No incremental update of AW is described. Therefore the paper does not establish an O(pq max{|J1|, |alpha|}) cost per iteration of Algorithm 2; it establishes that cost only for a single CG matvec. The speedup claims in Section 6.2.2 need a full per-iteration complexity analysis or a profiling/timing breakdown that separates residual formation, line search, and CG matvec costs.","section":"Section 4, Table 1; Eq. (17)"},{"comment":"The description of the experimental setup states that ALM-SNCG is initialized with a lower-accuracy starting point obtained from isPADMM, using up to four iterations on synthetic data and up to ten on real data, while the other methods start from the origin. The wall-clock time spent in those initial isPADMM iterations is not reported, and the paper does not state whether it is included in the ALM-SNCG times. If it is not included, the speedup ratios in Tables 4 and 5 are not a like-for-like comparison. Please report the warm-start overhead explicitly, run all methods from the same starting point, or present cumulative times that include the cost of generating the warm start.","section":"Section 6.2"},{"comment":"The superlinear convergence of the inner SNCG method is conditional on the nonemptiness of the index set J1 at the limit, which is equivalent to constraint nondegeneracy. The numerical sections report values of |J1| but do not state whether this condition holds in the tested configurations. Since the advertised high efficiency is partly attributed to the fast local convergence of SNCG, the manuscript should either verify the condition for the reported instances or provide a fallback convergence statement for cases where J1 is empty or very small.","section":"Section 3.2, Theorem 2, Proposition 2"}],"minor_comments":[{"comment":"The sentence claiming to reduce the cost 'from O(pq max{|J1|, |alpha|}) to O(npq)' reverses the direction; it should read 'from O(npq) to O(pq max{|J1|, |alpha|})'.","section":"Section 1, contribution 2"},{"comment":"There are typos: 'Tabel' in Table 2, and 'exibited' and 'achive' in the text around Tables 4 and 5.","section":"Table 2 and Tables 4-5"},{"comment":"The symbol I is used both for the identity matrix and for the matrix I := U [I_p 0] V^T; please use a different symbol, such as \\bar{I}, to avoid confusion.","section":"Proposition 1, Eq. (14)"},{"comment":"The constant beta is defined with an unspecified parameter gamma >= 1; please state the role of gamma or give a precise reference for this constant.","section":"Theorem 1"},{"comment":"The caption uses NSM without defining it; please define support matrices, active support matrices, and non-support matrices in the caption or in the surrounding text.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of math.OC and builds on established ALM and semismooth Newton machinery. The main risks are the incomplete end-to-end complexity accounting and the warm-start setup in the numerical comparisons. I do not see circular reasoning or inappropriate citation behavior; the self-citations to adaptive sieving papers are relevant and properly credited. A profiling table that separates CG matvec, residual formation, line search, and warm-start costs would substantially strengthen the paper and would allow the speedup claims to be evaluated fairly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nQuick take: this is a solid algorithmic paper with strong numerical results, but its central complexity claim is overstated. The claim that per-iteration cost is O(pq max{|J1|,|α|}) only covers the CG matvec. Forming the semismooth Newton residual in (17) requires computing AW for all n samples each time W changes, which costs O(npq). Table 1 and the contribution list ignore this. Unless the authors supply an incremental AW update or restrict the claim to the CG operator, the advertised asymptotic speedup is not established. This is the main thing to fix.\n\nWhat's genuinely new: applying ALM-SNCG to SMM with the sparsity-exploiting operator is a reasonable extension, and the adaptive sieving strategy for sample sparsity (with finite convergence proof) is a nice contribution. The experiments are large-scale and show real speedups, though giving ALM-SNCG a warm start from isPADMM without clear accounting of the warm-up time weakens the comparison. No error bars, no code.\n\nThe stress-test note is correct. The paper's own expression (17) for ∇φk requires A^* Π_S(ω), and Π_S(ω) is nonzero on all support matrices, which can be a large fraction of n (their Figure 1 shows up to 86%). So the O(npq) term is real. This doesn't necessarily sink the empirical results—the algorithm may still be fast in practice because Newton iterations are few—but the theoretical selling point needs rework.\n\nThe convergence theorems are quoted from prior work, which is fine, but Theorem 2's reliance on nonempty J1 means the fast rate can fail. That's a known caveat, not a flaw.\n\nWho is this for: people solving large-scale SMM for EEG/image classification. They will care about the speedups. But they should read the complexity claim with caution.\n\nRecommendation: send to peer review, but require a substantial revision that either fixes the complexity analysis (e.g., includes residual formation cost, or gives an incremental update) or clearly reframes the contribution as empirical. Also clarify the warm-start cost. As is, I would not cite the complexity claim.","headline":"A useful algorithmic extension with impressive experiments, but the advertised per-iteration complexity omits the O(npq) residual formation, so the main theoretical claim needs correction.","tokens_in":39114,"tokens_out":3082,"would_cite":false,"duration_ms":31566,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C06","90C25","90C90"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims an augmented Lagrangian with semismooth Newton-CG solves large-scale support matrix machines by exploiting sample sparsity and low-rank solutions, reducing per-iteration cost from $O(npq)$ to $O(pq\\max\\{|J_1|, |\\alpha|\\})$.","keywords":["support matrix machine","sample sparsity","low-rank regularization","adaptive sieving","augmented Lagrangian method","semismooth Newton method","nuclear norm","large-scale classification"],"falsifier":"Choose a dataset in which a large fraction of training matrices lie exactly on the optimal margin and take $\\tau$ small enough that many singular values of $-A^*\\lambda$ exceed $\\tau$; then measure the time per CG iteration as $n$ grows. If the cost scales like $npq$ rather than $\\max\\{|J_1|,|\\alpha|\\}pq$, the advertised complexity reduction is not holding in that regime.","tokens_in":38076,"feed_emoji":"🧮","tokens_out":9180,"duration_ms":83838,"temperature":0.7,"pith_summary":"This paper tries to establish that the support matrix machine---a classifier for matrix-shaped data with Frobenius and nuclear-norm regularization plus hinge loss---can be solved when $n$ is hundreds of thousands to a million, not just small-sample problems. The proposed method is an augmented Lagrangian outer loop whose subproblems are solved by a semismooth Newton-CG inner solver, and the central claim is that the inner linear algebra costs $O(pq\\max\\{|J_1|, |\\alpha|\\})$ per iteration instead of $O(npq)$, where $J_1$ is the active-support-matrix set and $|\\alpha|$ is the rank of the solution matrix $W$. The paper also develops an adaptive sieving strategy that reuses active samples from one grid value of $C$ to warm-start the next, with finite termination. If the claim is correct, cross-validation over $C$ and other model-selection tasks become feasible on large matrix datasets.","feed_headline":"Support matrix machine scales to a million samples","feed_subtitle":"By exploiting active support matrices and low-rank solutions, the solver is hundreds of times faster than ADMM baselines on real data.","key_machinery":"The machinery is the pair of index sets $J_1$ and $\\alpha$, together with the generalized Jacobians of the two proximal or projection maps. $J_1$ collects training samples whose dual slack is strictly inside $(0,C)$---the active support matrices---and $\\alpha$ collects singular values of the projection input that exceed $\\tau$, so $|\\alpha|$ equals the rank of the optimal $W$. Choosing $M\\in\\partial\\Pi_S$ supported on $J_1$ and $G\\in\\partial\\Pi_{\\mathcal{B}_2^\\tau}$ with the sparse structure induced by $\\alpha$ makes the Newton operator $\\tilde V$ act only on $|J_1|$ samples and an $|\\alpha|$-dimensional spectral block; the augmented Lagrangian outer loop and the adaptive sieving strategy then reduce the number and size of the subproblems solved.","core_discovery":"At a KKT point of the SMM model, the dual variable satisfies $\\lambda\\in[0,C]^n$ and the regression matrix has the form $W=-\\sum_{j=1}^n \\lambda_j y_j X_j-\\Lambda$, so only samples with positive dual weight contribute to $W$; samples with $0<(-\\lambda)_j<C$ are the active support matrices and lie on the margin. In parallel, the optimality relation $W=\\mathrm{Prox}_{\\tau\\|\\cdot\\|_*}(-A^*\\lambda)$ shows that the rank of $W$ equals the number of singular values of $-A^*\\lambda$ exceeding $\\tau$, denoted $|\\alpha|$. The paper's discovery is that these two sets are exactly the sparsity needed by the semismooth Newton-CG solver: the generalized-Jacobian factor $M$ is supported on $J_1$, and the spectral-ball factor $G$ has a block-sparse structure indexed by $\\alpha$, so the dominant matrix-vector products in the Newton system cost $O(|J_1|pq)$ and $O(|\\alpha|pq)$ instead of $O(npq)$. Under a strict-complementarity condition the ALM iterates converge R-superlinearly, and the SNCG inner loop converges superlinearly when $J_1$ is nonempty.","pith_inferences":["Editorial inference: tracking $|J_1|/n$ and $|\\alpha|/p$ online would let a user detect when the $O(pq\\max\\{|J_1|,|\\alpha|\\})$ promise is about to fail, since the paper's own cost analysis makes the dependence explicit.","Editorial inference: the adaptive sieving idea should transfer to the convex SMM variants listed in the paper, but the transfer is an extrapolation until experiments are run.","Editorial inference: combining the sample sieve with a feature or subspace sieve is the natural next step, and a concrete test is whether the two reductions compound on high-resolution image datasets where $pq$ is large."],"forward_implications":["ALM-SNCG solves SMM instances with $n$ up to $10^6$ and $pq$ in the tens of thousands, where F-ADMM runs out of memory or cannot reach the requested accuracy within two hours.","On the four real datasets tested, ALM-SNCG is on average 422.7 times faster than F-ADMM at medium accuracy and 477.2 times faster at high accuracy.","Adaptive sieving generates a $C$-grid solution path with average speedups of 2.69 and 3.07 over warm-started ALM on synthetic data, and 1.50 and 1.92 on MNIST.","The same algorithm framework carries over to convex SMM variants such as multiclass, weighted, transfer, and pinball SMMs, because the active-sample and low-rank structure is inherited from the same KKT system."],"supporting_citations":[{"why":"introduces the SMM model (1) and the F-ADMM solver that the paper uses as its main baseline.","marker":"[40]"},{"why":"provides the fast ADMM with restart that underlies F-ADMM, the method ALM-SNCG is compared against.","marker":"[15]"},{"why":"supplies the R-superlinear convergence theory for inexact augmented Lagrangian methods that Theorem 1 is derived from.","marker":"[9]"},{"why":"supplies the superlinear convergence framework for the semismooth Newton-CG method used for the ALM subproblems.","marker":"[69]"},{"why":"gives the generalized Jacobian of the metric projection onto the spectral-norm ball, whose sparse structure is exploited in computing $G d_W$.","marker":"[21]"},{"why":"characterizes the proximal mapping of the nuclear norm, which identifies the rank of the solution matrix $W$.","marker":"[39]"},{"why":"introduces the adaptive sieving dimension-reduction strategy whose idea is extended from solution sparsity to sample sparsity.","marker":"[67]"}],"fun_headline_variants":["SMM solver exploits sparsity and low rank for speed","Adaptive sieving speeds up support matrix machine","Low-rank & sparse structure accelerate SMM solver","SMM scales to million samples via adaptive sieving"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The speed and superlinear convergence depend on the active support set and the solution rank being genuinely small; if a dataset produces many active support matrices or a high-rank solution, the per-iteration cost climbs back toward $O(npq)$ and the reported gains shrink.","fun_headline_variants_meta":{"raw":{"variants":["SMM solver exploits sparsity and low rank for speed","Adaptive sieving speeds up support matrix machine","Low-rank & sparse structure accelerate SMM solver","SMM scales to million samples via adaptive sieving"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00093,"raw_usage":{"total_tokens":4032,"prompt_tokens":1043,"completion_tokens":2989,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":659,"completion_tokens_details":{"reasoning_tokens":2927}},"tokens_in":659,"tokens_out":2989,"duration_ms":19199,"temperature":1.0,"reasoning_tokens":2927,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:18:20.661776+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Choose a dataset in which a large fraction of training matrices lie exactly on the optimal margin and take $\\tau$ small enough that many singular values of $-A^*\\lambda$ exceed $\\tau$; then measure the time per CG iteration as $n$ grows. If the cost scales like $npq$ rather than $\\max\\{|J_1|,|\\alpha|\\}pq$, the advertised complexity reduction is not holding in that regime.","supporting_citations":[{"cited_title":"In: International Conference on Machine Learning, pp","cited_arxiv_id":null,"evidence_quote":"introduces the SMM model (1) and the F-ADMM solver that the paper uses as its main baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the fast ADMM with restart that underlies F-ADMM, the method ALM-SNCG is compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the R-superlinear convergence theory for inexact augmented Lagrangian methods that Theorem 1 is derived from."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the superlinear convergence framework for the semismooth Newton-CG method used for the ALM subproblems."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the generalized Jacobian of the metric projection onto the spectral-norm ball, whose sparse structure is exploited in computing $G d_W$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"characterizes the proximal mapping of the nuclear norm, which identifies the rank of the solution matrix $W$."}],"review_version":1}