{"id":"5348adc7-abe8-4f71-ac86-77e05fbe7a86","arxiv_id":"2501.11135","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A concave-regularized relaxed binary mask, pruned by threshold and rewound, finds sparse trainable subnetworks with accuracy comparable to or better than iterative magnitude pruning.","lead":"The authors propose a new way to find 'winning tickets': sparse subnetworks inside a neural network that can be retrained alone without losing accuracy. Their method relaxes the network mask to continuous values and pushes it toward zero with a concave penalty, and they test it on several image classifiers.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 2 (Section IV-B) is incomplete and the displayed bound is algebraically wrong: combining the proof's own inequalities gives a different quadratic bound, and the stated denominator makes the bound larger, not smaller, than Theorem 1.","rationale":"The reader's weakest_assumption field centers on Assumption 2, and I agree that the strong-convexity assumption is a serious gap between the theory and the neural-network experiments. However, the more immediately load-bearing issue is that Theorem 2's proof does not deliver the claimed bound even if Assumption 2 is granted: the proof stops after an upper bound and never solves the resulting inequality, and the displayed formula is not a valid consequence. Because the paper's theoretical contribution is precisely the claim that a strictly concave regularizer gives a provably smaller error bound than ℓ1, this invalidates the abstract's theoretical claim as written. The corrected algebra from the proof's own inequalities still suggests that a strictly smaller upper bound may be provable, so the idea is salvageable rather than hopeless. For that reason I would keep the reader's CONDITIONAL verdict and require the authors to provide a corrected proof or explicitly downgrade Theorem 2 to a conjecture, together with code and error bars for the experiments. The experimental overclaim in Section V-F is also concerning: the row at 22.10% unpruned differs from the baseline by only +0.04, and several competitors achieve comparable accuracies with larger unpruned ratios, so 'greatly outperforms' is not supported; this is secondary to the theorem issue. Minor typo noted: Section V-A calls the log regularizer 'strictly convex' when it is strictly concave; this does not affect the main argument.","tokens_in":15042,"tokens_out":8448,"duration_ms":75333,"concrete_test":"Independently re-derive Theorem 2 from Eqs. (15) and (16) together with Assumption 2 and Eq. (6), solving the resulting quadratic inequality; if the stated formula 4λ√k/(γ−ϕ) is not obtained, the theorem as written is false. As a numerical check, take d=1, k=1, L(m)=γ/2(m−1)², em=1, R(m) the normalized log regularizer with ε=0.1, and γ=1; for λ=0.01, 0.1, and 1, compute m⋆=argmin_{m∈[0,1]} L(m)+λR(m), form a=|m⋆−1|, and test whether a ≤ 4λ/(γ−ϕ(m⋆)) and whether the corrected quadratic bound holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV-B's Theorem 2 is the paper's advertised justification for preferring log over ℓ1. Its proof stops after Eq. (16); the claimed bound never follows. Combining (16) with Assumption 2 and ∥∇L(em)∥∞≤λ yields (γ/2)∥h∥₂² ≤ 2λ∥h_S∥₁ − λϕ(m⋆) ≤ 2λ√k∥h∥₂ − λϕ(m⋆), i.e., (γ/2)a² + λϕ ≤ 2λ√k a with a=∥h∥₂. The correct consequence is a ≤ (2λ√k + sqrt(4λ²k − 2γλϕ))/γ, not 4λ√k/(γ−ϕ). The written denominator has incompatible units (γ is not dimensionless while ϕ is dimensionless), can be zero or negative, and for any ϕ>0 it is smaller than γ, making the claimed bound larger, not smaller, than Theorem 1's bound. Thus the statement that a strictly concave regularizer beats ℓ1 is not established. This is independent of Assumption 2: even in the strongly convex setting, the algebra in the proof is missing. Separately, Assumption 2 is not satisfied by the neural-network losses used in Section V, so the theorem does not cover the experiments; the empirical comparison also lacks error bars and code. The proof gap is the more load-bearing issue because it undermines the paper's central theoretical contribution as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a method for finding lottery-ticket subnetworks by optimizing a relaxed binary mask with sparsity-promoting regularization, specifically ℓ1 and a strictly concave logarithmic regularizer. The mask is trained jointly with the weights in a projected-gradient framework, then pruned by thresholding, with an outer loop analogous to iterative magnitude pruning. The authors provide a theoretical analysis in a strongly convex setting (Section IV), claiming in Theorem 2 that replacing ℓ1 with a strictly concave regularizer yields a smaller error bound than the ℓ1 bound of Theorem 1. They support the approach with experiments on CIFAR-10, CIFAR-100, and Tiny ImageNet across three architectures, comparing against IMP and several dense-to-sparse pruning baselines. The central theoretical claim, however, is not established by the proof as written.","tokens_in":15416,"tokens_out":4650,"duration_ms":43889,"significance":"If correct, the theoretical result would give a principled reason to prefer concave regularizers such as the logarithmic penalty for mask-based lottery-ticket search, and the experimental results suggest the method is competitive with or better than IMP at high sparsity. The paper is also one of the first to apply continuous concave regularization to the relaxed-mask formulation of the lottery ticket problem, which is a worthwhile direction. The experimental coverage is broad: nine architecture/dataset combinations and a comparison to many pruning baselines. The strengths are the clear problem formulation and the extensive empirical study. However, the advertised theoretical justification for log over ℓ1 is not supported by the proof in Section IV-B, and the strong convexity assumption used in the theorems does not hold for the deep networks tested. The paper would be of interest after the theoretical derivation is corrected and the scope of the claims is clarified.","major_comments":[{"comment":"The proof of Theorem 2 stops after Eq. (16) and does not derive the displayed bound (14). Combining Eq. (16) with Assumption 2 and the gradient bound ∥∇L(êm)∥∞ ≤ λ gives (γ/2)∥h∥₂² ≤ 2λ√k∥h∥₂ − λϕ(m⋆), whose correct consequence is ∥h∥₂ ≤ (2λ√k + sqrt(4λ²k − 2γλϕ(m⋆)))/γ, not 4λ√k/(γ − ϕ(m⋆)). The written denominator mixes a dimensionless quantity ϕ(m⋆) with a curvature parameter γ, can be zero or negative, and for any ϕ(m⋆) > 0 it makes the bound larger, not smaller, than Theorem 1's bound. The stated conclusion that a strictly concave regularizer improves the error bound is therefore not established by the presented proof.","section":"Section IV-B, Theorem 2"},{"comment":"Even if the proof's algebraic gap were filled, the comparison in Theorem 2 is not supported: the claimed denominator γ − ϕ(m⋆) is dimensionally inconsistent and does not follow from the quadratic inequality that the proof's ingredients imply. The authors should either provide a complete derivation of a correct bound and compare it carefully with Theorem 1, or state a weaker and rigorously proven result. As written, the claim that the log regularizer yields a 'smaller error bound ... of ϕ(m⋆)' is misleading.","section":"Section IV-B, after Eq. (16)"},{"comment":"Assumption 2 requires strong convexity of L(m) with respect to the mask at the points m⋆ and êm, but the neural network losses used in Section V are non-convex and do not satisfy this assumption. Consequently Theorems 1 and 2 do not apply to the experimental setting. The paper explicitly says the analysis is 'in the convex framework,' but the introduction and conclusion present the theory as substantiating the method's effectiveness for neural networks. The authors should clearly state that the theoretical results are only motivational for the deep-network experiments, not guarantees, and should discuss what the convex analysis can and cannot establish for the non-convex problem.","section":"Section IV, Assumption 2"},{"comment":"The joint optimization step in Algorithm 1 is not analyzed for convergence to a stationary point of the non-convex problem (2), yet the introduction claims the approach 'guarantees to find an optimal sparse mask' in the convex case. For the non-convex case used in the experiments, no convergence or local-optimality result is provided. Since the algorithm is central to the empirical claims, a brief discussion of its convergence properties, or a softening of the guarantee language, is needed.","section":"Algorithm 1 and Section V"}],"minor_comments":[{"comment":"The text states that rϵ(mi) is 'strictly convex'; it should be 'strictly concave' to be consistent with Assumption 1 and the rest of the paper.","section":"Section V-A"},{"comment":"The caption references '(a)' and '(c)' but the figure only has panels (a) and (b); the caption should be corrected to refer to panel (b).","section":"Figure 4 caption"},{"comment":"The notation '±' in Eq. (16) is nonstandard and ambiguous; the proof should be written without it, using explicit expressions for ∥hS∥1 and ∥hSc∥1.","section":"Equation (16)"},{"comment":"The experimental results are averaged over three seeds, but the figures do not show error bars or confidence intervals. Adding variability information would strengthen the comparison with IMP and the two regularizers.","section":"Section V-D and Figures 5–9"},{"comment":"No code or detailed hyperparameter search is reported; the paper relies on the public open_lth framework but does not provide the code for the proposed mask-regularization method. Sharing code would improve reproducibility.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The proof gap in Theorem 2 is the most serious issue. The correct algebra from the proof's own ingredients appears to yield a bound with denominator γ rather than γ−ϕ(m⋆), so the conclusion that the concave regularizer improves the bound may be salvageable, but the current statement is wrong and must be corrected. I recommend major revision rather than rejection because the experimental study is substantial and the underlying idea is promising, but the theoretical contribution as written is not sound. Please ask the authors also to reconcile Assumption 2 with the deep-network experiments and to add error bars to the empirical comparisons."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nHere's my read of arXiv:2501.11135. The paper proposes using ℓ1 or log-concave regularizers on a relaxed binary mask for lottery ticket search, alternating between training weights and optimizing the mask, then pruning by threshold. The empirical setup is thorough: nine dataset/architecture combinations, an ablation study on threshold vs. percentage pruning, a comparison against sigmoid reparameterization, and training times. The results show that on ResNet-20 at high sparsity, the log regularizer gives a few points of accuracy over IMP, which is genuinely useful. The illustrative MNIST example is clean and makes the mechanism easy to see.\n\nThe main soft spot is the theory. Theorem 2, which is supposed to prove that a strictly concave regularizer (log) achieves a smaller error bound than ℓ1, stops mid-proof. The proof reaches Eq. (16) and then simply asserts the bound ∥h∥₂ ≤ 4λ√k/(γ−ϕ(m⋆)). That inequality does not follow from the preceding lines. If you combine (16) with Assumption 2 and the gradient bound, you get a quadratic inequality in ∥h∥₂ whose solution is a ≤ (2λ√k + sqrt(4λ²k − 2γλϕ))/γ, not the stated fraction. The denominator γ−ϕ(m⋆) is also dimensionally suspect since γ is a curvature and ϕ is a dimensionless nonnegative function of m⋆. So the claim that log beats ℓ1 is unsupported as written. The paper even defines ϕ(m⋆) in the proof, so the reader can't reproduce the bound. This is not a minor omission; it is the paper's advertised theoretical contribution.\n\nA second issue is Assumption 2, strong convexity of the loss with respect to the mask at the two points m⋆ and êm. Neural network losses don't satisfy that. The authors acknowledge this is a convex-framework analysis, but then they use the theorems to interpret the experiments, which is a stretch. The theory, even if fixed, only covers a logistic-regression-style setting.\n\nThe empirical claims also overshoot. The abstract says the method improves on state-of-the-art algorithms, and Section V-F says our method greatly outperforms competing methods. But Table II shows that on CIFAR-10/ResNet-56, the method is competitive at ~20% unpruned but loses 5 points at below 2% unpruned, and several existing pruning methods achieve similar accuracy at higher unpruned rates. The comparison is also against dense-to-sparse methods, which is a different setup. There are no error bars (only means over 3 runs) and no code release, so the variability is unknown.\n\nWho is this for? Someone working on lottery ticket search or sparse training might want to try the threshold-based mask pruning method; the ablations are informative. A theory-minded reader will be disappointed.\n\nRecommendation: this deserves a serious referee, but not as-is. The authors need to either correct Theorem 2 or explicitly demote it to a conjecture, remove the overclaims, add error bars, and release code. If they do that, the empirical part could be a solid incremental contribution. I'd send it to review with a request for major revision.","headline":"The empirical recipe is plausible and the experiments are extensive, but the advertised proof that log beats ℓ1 (Theorem 2) is not actually proven, and the paper overclaims against state-of-the-art pruning methods.","tokens_in":15914,"tokens_out":2774,"would_cite":false,"duration_ms":25112,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"A concave regularizer on a relaxed mask finds better lottery tickets.","keywords":["lottery ticket hypothesis","neural network pruning","concave regularization","sparse optimization","relaxed binary mask","iterative magnitude pruning","matching tickets"],"falsifier":"Run the mask-recovery experiment of Section IV-C with a loss that violates Assumption 2, for example a small neural network trained with the same 'lambda' and initialization, and measure '||'m*' - 'e_m'||'_2 for log versus '1 regularization: the theory predicts the log error bound to be strictly smaller whenever m* is non-binary, so observing no gap, or a gap that changes sign across sparsity levels, would falsify the claimed mechanism.","tokens_in":14807,"feed_emoji":"🎰","tokens_out":5327,"duration_ms":51996,"temperature":0.7,"pith_summary":"The paper proposes a new way to play the lottery: instead of pruning a fixed percentage of weights by magnitude, it relaxes the binary mask that selects weights into a continuous variable in [0,1]^d and penalizes it with a concave sparsity-promoting regularizer, such as the logarithmic penalty. The claim is that this soft, threshold-based pruning finds subnetworks that train in isolation as well as iterative magnitude pruning (IMP) at moderate sparsities and better at high sparsities, across CIFAR-10, CIFAR-100, and Tiny ImageNet with ResNet-20, VGG-11, and WideResNet-20. The paper also proves, in a convex setting, that a strictly concave regularizer yields a strictly smaller error bound than '1 for recovering the unknown optimal mask. If correct, this gives practitioners a simple, principled alternative to magnitude pruning for sparse trainable networks.","feed_headline":"Concave masks beat magnitude pruning at high sparsity","feed_subtitle":"A relaxed binary mask with logarithmic regularization matches standard pruning at moderate sparsity and beats it where pruning is hardest.","key_machinery":"The machinery is the relaxed binary mask m in [0,1]^d combined with a separable concave regularizer R(m) = 'sum'_i r(m_i), with the logarithmic choice r_'epsilon'(m_i) = log((m_i+'epsilon')/'epsilon')/log((1+'epsilon')/'epsilon'). The mask encodes the network topology, and its concavity makes the penalty lie above the '1 norm on the interior of the cube, so any non-binary recovered mask pays a strictly higher penalty under log than under '1. This extra penalty 'phi'(m*) is exactly what shrinks the error bound in Theorem 2. Training uses projected gradient descent on the cube, which sidesteps the nondifferentiability of '1 at zero, and a small threshold '$\\alpha$' converts the relaxed mask into hard zero-one decisions.","core_discovery":"The central discovery is that concavity of the mask regularizer, not just sparsity of the solution, is what improves ticket search. Given a fixed trained weight vector '$\\theta$' and an unknown optimal binary mask 'e_m', minimizing L(m'odot''$\\theta$')+'$\\lambda$'R(m) over m in [0,1]^d recovers 'e_m' with error bounded by 4'$\\lambda$''sqrt'('k'/'gamma') under '1, and by 4'$\\lambda$''sqrt'('k')/('gamma' - 'phi'(m')) under any strictly concave R satisfying Assumption 1, where 'phi'(m*) = R(m*) - '||'m*'||'_1 > 0 whenever the recovered mask is not already binary. Thus the logarithmic regularizer provably tightens the recovery bound in the convex regime. The paper claims this advantage carries over to full lottery-ticket training, where the method matches IMP at matching sparsities and outperforms it at extreme sparsities, and to dense-to-sparse pruning, where it retains baseline accuracy with about 77% of weights removed.","pith_inferences":["My inference: if the concavity advantage is real and not an artifact of threshold choice, combining the relaxed-mask regularizer with rewinding to an early training iterate could further stabilize high-sparsity tickets; the paper only tests rewinding to the initial weights.","My inference: the threshold 'alpha' is left unmodeled by the theory; a natural test is whether the reported gains persist as 'alpha' tends to zero or whether they depend on a carefully tuned threshold.","My inference: the projected-gradient training itself may do part of the sparsification work; comparing against an otherwise identical method that uses a convex regularizer or no regularizer on the mask would separate the concavity effect.","My inference: because the log regularizer's advantage 'phi'(m*) vanishes as m* approaches a binary vector, the largest relative gains over '1 should appear in early pruning rounds when masks are still soft; experiments could check this directly."],"forward_implications":["At matching sparsities the proposed method matches IMP accuracy on all nine dataset and architecture combinations; at extreme sparsities it outperforms IMP, most clearly on ResNet-20.","Strictly concave regularization (log) can improve on '1 mask regularization, which the paper attributes to the strictly smaller error bound of Theorem 2.","Threshold-based pruning of the relaxed mask beats fixed-percentage pruning of mask magnitudes in the ablation study.","On CIFAR-10 with ResNet-56, the method prunes over 77% of parameters while keeping accuracy at or above the dense baseline, surpassing the dense-to-sparse baselines listed in Table II.","The method produces sparse models that can be trained in isolation after rewinding, not only sparse models for inference."],"supporting_citations":[{"why":"Defines the lottery ticket hypothesis and the iterative magnitude pruning baseline that the proposed method aims to beat.","marker":"[4]"},{"why":"Introduces matching tickets and rewinding to an early iteration, the retraining strategy that Algorithm 1 uses.","marker":"[11]"},{"why":"Provides the continuous sparsification baseline based on '0 regularization that the proposed concave mask regularization is compared against.","marker":"[12]"},{"why":"Establishes '1 as the convex surrogate of '0, motivating the choice of regularizer family.","marker":"[22]"},{"why":"Supplies the logarithmic concave regularizer and evidence that concave penalties enhance sparsity.","marker":"[23]"},{"why":"Grounds the fixed-weight mask-only analysis in Section IV, where only the mask is optimized while weights are held fixed.","marker":"[34]"}],"fun_headline_variants":["Concave masks sharpen lottery ticket search","Logarithmic masks beat magnitude pruning at high sparsity","Concave masks find winning tickets where pruning fails","Better than IMP: concave regularizers for lottery tickets","Concave masks win at extreme sparsity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The error bounds require the loss to be strongly convex in the mask at the optimal and estimated masks (Assumption 2), which neural-network losses are not, so the theoretical guarantee only covers the convex logistic-regression setting and the experiments rely on the method's empirical behavior.","fun_headline_variants_meta":{"raw":{"variants":["Concave masks sharpen lottery ticket search","Logarithmic masks beat magnitude pruning at high sparsity","Concave masks find winning tickets where pruning fails","Better than IMP: concave regularizers for lottery tickets","Concave masks win at extreme sparsity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00095,"raw_usage":{"total_tokens":4063,"prompt_tokens":965,"completion_tokens":3098,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":3027}},"tokens_in":581,"tokens_out":3098,"duration_ms":23516,"temperature":1.0,"reasoning_tokens":3027,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:36:23.825629+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the mask-recovery experiment of Section IV-C with a loss that violates Assumption 2, for example a small neural network trained with the same 'lambda' and initialization, and measure '||'m*' - 'e_m'||'_2 for log versus '1 regularization: the theory predicts the log error bound to be strictly smaller whenever m* is non-binary, so observing no gap, or a gap that changes sign across sparsity levels, would falsify the claimed mechanism.","supporting_citations":[{"cited_title":"The lottery ticket hypothesis: Finding sparse, trainable neural networks","cited_arxiv_id":null,"evidence_quote":"Defines the lottery ticket hypothesis and the iterative magnitude pruning baseline that the proposed method aims to beat."},{"cited_title":"Linear mode connectivity and the lottery ticket hypothesis,","cited_arxiv_id":null,"evidence_quote":"Introduces matching tickets and rewinding to an early iteration, the retraining strategy that Algorithm 1 uses."},{"cited_title":"Winning the lottery with continuous sparsification,","cited_arxiv_id":null,"evidence_quote":"Provides the continuous sparsification baseline based on '0 regularization that the proposed concave mask regularization is compared against."},{"cited_title":"Regression shrinkage and selection via the Lasso,","cited_arxiv_id":null,"evidence_quote":"Establishes '1 as the convex surrogate of '0, motivating the choice of regularizer family."},{"cited_title":"Enhancing sparsity by reweighted ℓ1 minimization,","cited_arxiv_id":null,"evidence_quote":"Supplies the logarithmic concave regularizer and evidence that concave penalties enhance sparsity."},{"cited_title":"What’s hidden in a randomly weighted neural network?","cited_arxiv_id":null,"evidence_quote":"Grounds the fixed-weight mask-only analysis in Section IV, where only the mask is optimized while weights are held fixed."}],"review_version":1}