Pith. sign in

REVIEW 3 major objections 2 minor 29 references

Computational approaches to non-convex, sparsity-inducing multi-penalty regularization

T0 review · 3 major / 2 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Infimal convolution gives linear convergence for two-penalty sparse recovery.

desk verdict The infimal-convolution reduction is a real computational contribution, but Theorem 2.11 does not prove the claimed linear convergence because its rate constant can exceed 1 under the stated conditions. read the letter →

arxiv 1908.02503 v4 pith:5JHVLDYZ submitted 2019-08-07 cs.IT math.IT

Zeljko Kereta , Johannes Maly , Valeriya Naumova This is my paper · ORCID
classification cs.ITmath.IT MSC 90C2665K0594A12
keywords multi-penaltyregularizationsparserecoveryinfimalconvolutionnon-convexoptimizationiterativethresholdinglinearconvergencecompressedsensingnoisefolding
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper deals with recovering a sparse signal from noisy linear measurements when noise enters both before and after the measurement step, a situation that calls for two separate penalties. The authors show that the resulting non-convex multi-penalty problem can be reduced to a single-penalty problem in two ways: an augmented formulation that needs a costly matrix square root and inverse, and a new infimal-convolution formulation that avoids that preprocessing. They prove that proximal-gradient iterations for either reduction converge linearly, once the iterates' support and sign pattern have stabilized, with rates that improve with sparsity and measurement count. The infimal-convolution route provides the same guarantee at $O(mn)$ cost per iteration instead of $O(m^\rho)$, making it practical for large measurement matrices.

What carries the argument

The load-bearing object is the infimal convolution $g(w)=\inf_{u\in\mathbb{R}^n}\frac{\alpha}{q}\|u\|_q^q+\frac{\beta}{2}\|w-u\|_2^2$, which merges the two penalties into one. Its proximal operator is computed through the identity $\operatorname{prox}_{\mu,\lambda M_{t,f}}(x)=\frac{t}{t+\mu\lambda}x+\frac{\mu\lambda}{t+\mu\lambda}\operatorname{prox}_{(t+\mu\lambda),f}(x)$ (Lemma 2.10), so the cost of one proximal-gradient step is dominated by the proximal map of the $\ell_q$ quasinorm, a componentwise thresholding operator. The proofs also rely on a support-and-sign stabilization lemma: because the thresholding operator has a gap near zero, consecutive iterates' supports and signs can change only finitely many times, turning a global iteration into a local contraction on the stabilized support. That contraction is what produces the explicit linear rates in Theorems 2.7 and 2.11.

What would settle it

Take a small problem where $B_\beta$ can be computed exactly, choose parameters within the allowed ranges ($0<\mu<\|A\|^{-2}$ and $\alpha$ below the stated threshold), run the infimal-convolution iteration from a random initialization, and record the relative error after the supports of the iterates stop changing; if the error does not decrease by a factor below 1 per iteration, the contraction bound in Theorem 2.11 would be contradicted.

Watch

Extended reading notes

Core claim

The central claim is that the non-convex multi-penalty problem, with $0<q\le 1$ and $p=2$, is equivalent to a single-penalty problem in which the $\ell_q$ quasinorm and the quadratic penalty on the second component are combined through an infimal convolution. The paper proves that the minimizer of the original two-penalty functional is obtained by solving this single-penalty program and then splitting the solution via the proximal operator of the $\ell_q$ term. For both the augmented and the infimal-convolution reductions, the paper establishes that once the iterates converge to a stationary point and the support and signs stabilize, the error contracts by a factor strictly below one at each step, provided the step size stays below the reciprocal of the squared spectral norm of $A$ and the regularization parameter $\alpha$ lies below a threshold that depends on the smallest nonzero entry of the limit. The infimal-convolution route achieves this at $O(mn)$ per iteration, whereas the augmented route requires an $O(m^\rho)$ preprocessing step to form $B_\beta$. If the theorems hold, multi-penalty regularization with non-convex sparsity penalties becomes as cheap to run as ordinary iterative thresholding.

Load-bearing premise

The linear-rate theorems hold only after the iterates have already converged to a stationary point and the support and sign pattern have stabilized, and the paper does not prove that this stabilization occurs from an arbitrary initialization, relying instead on Kurdyka-\L{}ojasiewicz arguments from the cited literature.

Editorial extensions

If this is right

  • The infimal-convolution formulation solves the non-convex two-penalty problem with per-iteration cost $O(mn)$, so multi-penalty recovery becomes practical for large measurement counts $m$ where the augmented formulation's $O(m^\rho)$ preprocessing is prohibitive.
  • Both reductions converge linearly once the support and signs stabilize, with the contraction factor determined by the restricted isometry constant of $A$, the sparsity level, and the smallest nonzero entry of the solution.
  • Alternating minimization, which requires solving an inner thresholding problem at every outer step, is dominated by either single-penalty formulation in terms of total proximal-operator calls.
  • The infimal-convolution reduction is not tied to the $\ell_q$ quasinorm; the same program applies to other sparsity-inducing regularizers such as SCAD, MCP, or the log-sum penalty, where the general rate analysis of [28] should carry over.
  • For $q=1$ the method is equivalent to proximal descent on the squared $\ell_2$-norm of the gradient of a Moreau-smoothed $\ell_1$ functional, pointing to a view of multi-penalty regularization as a smooth zero-finding procedure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the admissible $\alpha$ bound depends on $d_{\min}$, the smallest nonzero entry of the yet-unknown solution, a practical implementation would need to estimate $d_{\min}$ on the fly—for instance, by monitoring the stabilized support and adapting $\alpha$—since the theoretical threshold cannot be evaluated before running the algorithm.
  • The local nature of the rate (it only starts after support stabilization) suggests that the algorithm's early phase, during which the support is still changing, may dominate wall-clock time; any improvement that speeds up support identification would directly accelerate overall recovery.
  • The Moreau-envelope reinterpretation for $q=1$ hints that for $0<q<1$ the method implicitly tracks a family of smoothed quasi-norms, which could open the door to step-size rules larger than $\|A\|^{-2}$ or to second-order accelerations, though the paper does not establish these.
  • One testable extension: on large-scale problems with $m$ in the thousands, the per-iteration gap between the two formulations should grow roughly as $m^{\rho-1}$, so the infimal-convolution method should win by an increasingly wide margin as $m$ grows; this is a quantitative prediction that can be checked empirically.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 2 minor

Summary. The manuscript studies the multi-penalty regularization problem (2) with p=2 and 0<q<=1. It extends the augmented single-penalty reduction of [16] to the non-convex lq penalty and proposes a new reduction based on infimal convolution, leading to proximal-gradient algorithms (9) and (15). The paper claims linear convergence rates for both algorithms in Theorems 2.7 and 2.11, with parameter-dependent constants, and reports numerical experiments comparing alternating minimization, the augmented method, and the infimal-convolution method in terms of iteration counts and running time. The computational motivation for the infimal-convolution reduction is clear and the numerical illustrations support the qualitative efficiency claims.

Significance. The infimal-convolution reduction is an attractive way to avoid forming the matrix B_beta, and Lemma 2.10 offers a practical way to evaluate the proximal step of the Moreau envelope. The computational complexity discussion in Section 2.2.2 and the numerical comparison in Section 3 are useful and reproducible in spirit. However, the main theoretical claim for the infimal-convolution method -- linear convergence -- is not established by the proof as written, because the contraction constant in Theorem 2.11 can exceed one under the stated assumptions. The augmented-formulation theorem (Theorem 2.7) is sound once the missing positivity condition is added, but the central novelty of the paper depends on the infimal-convolution rate, which needs to be repaired or substantially qualified.

major comments (3)
  1. [Theorem 2.11 / Section A.5] The contraction constant displayed in Theorem 2.11 is not guaranteed to be smaller than 1. The proof derives two separate inequalities with coefficients rho_I/(1-T) on the support I and rho_{I^c}/(1+mu beta) on I^c, and the displayed constant is the Euclidean norm of these two coefficients. Even if each individual coefficient is below 1, their squared sum can exceed 1; for example, with beta=0.2 and mu=0.1 as in Section 3.2, and with rho_{I^c}=1, the second coefficient equals 1/1.02 and the combined constant can easily be larger than 1. Consequently, Theorem 2.11 as stated provides an upper bound with an unspecified constant rather than a linear convergence rate, and the claim in Remark 2.12 that 'we get linear convergence of (15)' is not justified by the displayed inequality.
  2. [Remark 2.12, Eq. (17)] The inequality ||Id_n - mu A^T A|| < 1 used in (17) is false when A is rank-deficient, which is the relevant compressed-sensing regime m<n. In that case the nullspace of A gives eigenvalues of Id_n - mu A^T A equal to 1, so the spectral norm is exactly 1. This invalidates the claim ||P_{I^c} - mu A_{I^c}^T A|| < 1 and leaves the second term of the Theorem 2.11 constant controlled only by 1/(1+mu beta). The linear-convergence assertion in Remark 2.12 therefore requires an explicit lower bound on beta (or a different argument controlling the cross terms), and no such bound is provided.
  3. [Theorem 2.7 and Theorem 2.11] Both theorems omit the positivity condition on the denominators. In Theorem 2.7 the denominator 1 - mu alpha (1-q)(dmin/2)^{q-2} must be positive for the displayed inequality to be meaningful; the condition alpha < alpha_star appears only in Remark 2.8(i) and is not part of the theorem statement. The same omission occurs in Theorem 2.11 for the factor 1 - alpha mu (1-q)(dmin/2)^{q-2}. Because these conditions depend on the unknown limit point through dmin, they should be stated explicitly among the assumptions, or the theorems should be formulated as conditional statements valid only when the denominators are positive.
minor comments (2)
  1. [Lemma 2.10] The statement of Lemma 2.10 uses prox_{mu,lambda M_{t,f}}(x) and then writes the result in terms of prox_{(t+mu lambda),f}(x); the argument of the proximal operator in the formula is not fully specified. Aligning the notation with the definition in (10) would improve readability and avoid ambiguity.
  2. [Remark 2.12] The same symbol alpha* is used in Remark 2.12 to denote a threshold that differs from the alpha_star defined in Remark 2.8(i). Overloading the symbol in this way is confusing; using a distinct notation for the two thresholds would clarify the conditions.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation; convergence rates are proven from KKT/RIP/support-stability facts, not from fitted data. Minor self-citations are not load-bearing.

full rationale

The central derivation chain is self-contained. Lemma 2.4 reduces the multi-penalty problem to the augmented single-penalty problem via an explicit Woodbury-identity computation in Section A.1; the citation to [16] is contextual, and the proof is reproduced. Lemma 2.9 is a direct reformulation by infimal convolution, and Lemma 2.10 is proved in Section A.4. Theorems 2.7 and 2.11 are derived from KKT conditions, support/sign stabilization lemmas, RIP bounds, and dmin-dependent estimates; the cited KL-property and support-stability facts ([4], [9], [27], [28]) are standard external lemmas from non-author works and are used as inputs, not as the desired contraction conclusions. The convergence constants are expressed in terms of design parameters and are not fit to data; the oracle-informed tuning in Section 3 is experimental validation and does not feed into the theorems. The displayed bound in Theorem 2.11 is not shown to have a contraction constant below 1, and alpha* depends on the unknown dmin, but these are quantitative/correctness caveats rather than circular reductions. The only reason for a nonzero score is the presence of minor non-load-bearing self-citations ([15], [16], [21]); none of them carries the proof burden, so the paper is not significantly circular.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The theoretical rate results do not fit parameters to data; they are local convergence statements conditioned on convergence to a stationary point and on alpha lying below a threshold set by the unknown minimum entry of the limit. The experiments add oracle-tuned parameters (alpha selected to match the true support size), which affects the empirical validation but not the derivation.

free parameters (3)
  • alpha (regularization parameter) = tuned in convergence experiments; 0.02 in runtime experiment
    Appears in the rate denominators; in Section 3.1 it is tuned so the reconstruction shares support size with the ground truth, making the empirical curves conditional on oracle knowledge.
  • beta (regularization parameter) = 0.2 in runtime experiment; varied in Figure 1a
    Controls the augmented matrix B_beta and the O(beta^{-1}) term in Theorem 2.11; chosen by hand in experiments.
  • mu (step size) = 0.1 in runtime experiment; theoretical bounds in theorems
    Step size must satisfy mu<||A||^{-2}+beta^{-1} (Theorem 2.7) or mu<||A||^{-2} (Theorem 2.11); chosen by hand in Section 3.2.
assumptions (6)
  • domain assumption The measurement matrix A satisfies the s-restricted isometry property with constant delta_s.
    Theorem 2.7 uses RIP to bound lambda_min(A_I^T A_I) below by (1-delta_s)^2; without RIP the displayed rate constant cannot be derived.
  • domain assumption The proximal-gradient iterates converge to a stationary point (u^k->u* or w^k->w*), and support and sign stabilize after finitely many steps.
    Theorems 2.7 and 2.11 assume convergence and rely on Lemmas A.3/A.4 for support and sign stability; convergence with a rate is not proven from arbitrary initialization.
  • ad hoc to paper The regularization strength satisfies alpha<alpha* (or alpha<alpha_star) so that the rate denominator is positive.
    The proofs require 1-mu*alpha*(1-q)*(dmin/2)^(q-2)>0; the theorem statements omit this, and the threshold depends on the unknown dmin and RIP constant. Remarks 2.8 and 2.12 supply it.
  • domain assumption Step sizes obey mu<||A||^{-2}+beta^{-1} for the augmented iteration and mu<||A||^{-2} for the infimal-convolution iteration.
    These bounds are needed to have ||u^{k+1}-u^k||->0 and ||w^{k+1}-w^k||->0 respectively, by [9, Corollary 2.1].
  • standard math For Lemma 2.10, f is lower semi-continuous with f(0)=min f and has a nonempty proximal operator; the set-valued case at the threshold is ignored.
    The Moreau-envelope proximal identity and the single-valued prox in (11) exclude the jump point |u|=tau_mu, where the proximal operator is set-valued.
  • domain assumption The data generation model is y=A(u*+v)+xi with Gaussian pre- and post-measurement noise.
    The multi-penalty objective (2) and all numerical experiments are rooted in this noise-folding model; the paper does not claim results for other noise models.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computational approaches to non-convex, sparsity-inducing multi-penalty regularization." pith.science (2026). https://pith.science/paper/5JHVLDYZ

@misc{pith2026190802503,
  author       = {Pith},
  title        = {Pith review of: Computational approaches to non-convex, sparsity-inducing multi-penalty regularization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5JHVLDYZ}},
  note         = {Machine review of arXiv:1908.02503}
}
read the original abstract

In this work we consider numerical efficiency and convergence rates for solvers of non-convex multi-penalty formulations when reconstructing sparse signals from noisy linear measurements. We extend an existing approach, based on reduction to an augmented single-penalty formulation, to the non-convex setting and discuss its computational intractability in large-scale applications. To circumvent this limitation, we propose an alternative single-penalty reduction based on infimal convolution that shares the benefits of the augmented approach but is computationally less dependent on the problem size. We provide linear convergence rates for both approaches, and their dependence on design parameters. Numerical experiments substantiate our theoretical findings.

Figures

Figures reproduced from arXiv: 1908.02503 by the authors.

Figure 1
Figure 1. In the left panel we consider A ∈ R 200×600 and vary the parameter β, whereas in the right panel we consider A ∈ R m×600 and vary the number of measurements m ∈ {100, 200, 300, 400}. Varying the Penalty Parameter. In the first experiment we take a Gaussian matrix A ∈ R 200×600, a 20-sparse signal u † , and vary β. Theorem 2.7 predicts that smaller values of β allow to take larger stepsizes, though the convergence co… view at source ↗
Figure 2
Figure 2. In the left panel we look at the relative error with respect to the number of times the [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 26 canonical work pages

  1. [16]

    Grasmair and V

    M. Grasmair and V. Naumova. Conditions on optimal support recovery in unmixing prob- lems by means of multi-penalty regularization.Inverse Problems, 32(10):104007, 2016

    work page 2016

  2. [1]

    Aeron, V

    S. Aeron, V. Saligrama, and M. Zhao. Information theoretic bounds for compressed sensing. IEEE Transactions on Information Theory, 56(10):5111–5130, 2010

    work page 2010

  3. [2]

    Arias-Castro and Y

    E. Arias-Castro and Y. C. Eldar. Noise folding in compressed sensing.IEEE Signal Pro- cessing Letters, 18(8):478–481, 2011

    work page 2011

  4. [3]

    Dampingnoise-foldingandenhancedsupportrecovery in compressed sensing.IEEE Transactions on Signal Processing, 63(22):5990–6002, 2015

    M.Artina, M.Fornasier, andS.Peter. Dampingnoise-foldingandenhancedsupportrecovery in compressed sensing.IEEE Transactions on Signal Processing, 63(22):5990–6002, 2015

    work page 2015

  5. [4]

    Attouch, J

    H. Attouch, J. Bolte, P. Redont, and A. Soubeyran. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka- Łojasiewicz inequality.Mathematics of Operations Research, 35(2):438–457, 2010

    work page 2010

  6. [5]

    Attouch, J

    H. Attouch, J. Bolte, and B. F. Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods.Mathematical Programming, 137(1):91–129, 2013

    work page 2013

  7. [6]

    H. H. Bauschke, P. L. Combettes, et al.Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011

    work page 2011

  8. [7]

    Beck.First-order methods in optimization

    A. Beck.First-order methods in optimization. SIAM, 2017

    2017

Show all 29 references
  1. [8]

    Bolte, T

    J. Bolte, T. P. Nguyen, J. Peypouquet, and B. W. Suter. From error bounds to the com- plexity of first-order descent methods for convex functions.Mathematical Programming, 165(2):471–507, 2017

    2017

  2. [9]

    Minimizationofnon-smooth, non-convexfunction- als by iterative thresholding.Journal of Optimization Theory and Applications, 165(1):78– 112, Apr 2015

    K.Bredies, D.A.Lorenz, andS.Reiterer. Minimizationofnon-smooth, non-convexfunction- als by iterative thresholding.Journal of Optimization Theory and Applications, 165(1):78– 112, Apr 2015

    2015

  3. [10]

    E. J. Candés, M. B. Wakin, and S. P. Boyd. Enhancing sparsity by reweightedl1 minimiza- tion. Journal of Fourier Analysis and Applications, 14(5-6):877–905, 2008

    2008

  4. [11]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.Introduction to algorithms. MIT press, 2009

    2009

  5. [12]

    Daubechies, M

    I. Daubechies, M. Defrise, and C. D. Mol. Sparsity-enforcing regularisation and ISTA revis- ited. Inverse Problems, 32(10):104001, 2016

    2016

  6. [13]

    Fan and R

    J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, 96(456):1348–1360, 2001

    2001

  7. [14]

    Foucart and H

    S. Foucart and H. Rauhut.A Mathematical Introduction to Compressive Sensing. Birkhäuser Basel, 2013

    2013

  8. [15]

    Grasmair, T

    M. Grasmair, T. Klock, and V. Naumova. Adaptive multi-penalty regularization based on a generalized lasso path.Applied and Computational Harmonic Analysis, 49(1):30–55, 2020

    2020

  9. [17]

    Laude, T

    E. Laude, T. Wu, and D. Cremers. A nonconvex proximal splitting algorithm under Moreau- Yosida regularization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 491–499, 2018. 19

    2018

  10. [18]

    Laude, T

    E. Laude, T. Wu, and D. Cremers. Optimization of inf-convolution regularized nonconvex composite problems. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 547–556, 2019

    2019

  11. [19]

    G. Li. Global error bounds for piecewise convex polynomials.Mathematical Programming, 137(1):37–64, 2013

    2013

  12. [20]

    B. S. Mordukhovich. Variational analysis and generalized differentiation I: Basic theory, volume 330. Springer Science & Business Media, 2006

    2006

  13. [21]

    Naumova and S

    V. Naumova and S. Peter. Minimization of multi-penalty functionals by alternating iterative thresholding and optimal parameter choices.Inverse Problems, 30(12):125003, 2014

    2014

  14. [22]

    Parikh and S

    N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3):127–239, 2014

    2014

  15. [23]

    R. T. Rockafellar and R. J.-B. Wets.Variational analysis, volume 317. Springer Science & Business Media, 2009

    2009

  16. [24]

    Y. Wang, J. Zeng, Z. Peng, X. Chang, and Z. Xu. Linear convergence of adaptively iterative thresholding algorithms for compressed sensing.IEEE Transactions on Signal Processing, 63(11):2957–2971, 2015

    2015

  17. [25]

    F. Wen, L. Chu, P. Liu, and R. C. Qiu. A survey on nonconvex regularization-based sparse and low-rank recovery in signal processing, statistics, and machine learning.IEEE Access, 6:69883–69906, 2018

    2018

  18. [26]

    Z. Xu, X. Chang, F. Xu, and H. Zhang. L1/2 regularization: a thresholding representa- tion theory and a fast solver. IEEE Transactions of Neural Networks Learning Systems, 23(7):1013–1027, 2012

    2012

  19. [27]

    P. Yu, G. Li, and T. K. Pong. Deducing kurdyka-lojasiewicz exponent via inf-projection. arXiv preprint arXiv:1902.03635, 2019

    1902 arXiv

  20. [28]

    J. Zeng, S. Lin, and Z. Xu. Sparse regularization: Convergence of iterative jumping thresh- olding algorithm. IEEE Transactions on Signal Processing, 64(19):5106–5118, 2016

    2016

  21. [29]

    Nearlyunbiasedvariableselectionunderminimaxconcavepenalty

    C.-H.Zhang. Nearlyunbiasedvariableselectionunderminimaxconcavepenalty. The Annals of Statistics, 38(2):894–942, 2010. 20

    2010

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.