arxiv: 2605.08684 · v1 · submitted 2026-05-09 · 🧮 math.OC

Recognition: 2 theorem links

· Lean Theorem

On the Stationary Duality of Structural Composite Cardinality Optimization

Houduo Qi, Naihua Xiu, Penghe Zhang

Pith reviewed 2026-05-12 01:18 UTC · model grok-4.3

classification 🧮 math.OC

keywords composite cardinality optimizationstationary dualitydual formulationlocal solutions correspondenceglobal solutionscardinality constraintsaffine mapping

0 comments

The pith

Stationary duality reduces composite cardinality optimization to simple counting and yields equivalent primal-dual solutions.

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

The paper establishes a dual formulation for composite cardinality optimization problems by using stationary duality to convert the composite counting process into ordinary counting of nonzero elements. This reformulation makes it possible to prove that local solutions of the original and dual problems stand in one-to-one correspondence, and that the same holds for global solutions once the dual weighted parameters are chosen suitably. The authors also supply conditions guaranteeing the existence of global solutions and check those conditions on standard test cases from the literature. A reader would care because many practical problems in statistics, signal processing, and engineering involve counting operations wrapped inside linear transformations, and a workable dual often opens the door to new computational methods.

Core claim

Through the use of the stationary duality, we reduce the composite counting to simple counting, and thereby obtain a dual formulation of CCOP. For both primal and dual problems, we investigate the sufficient conditions for the existence of global solutions. We then show that local solutions of the primal and dual problems are equivalent to their stationary points. This result further helps us establish a one-to-one correspondence between primal and dual local solutions. We also demonstrate that the correspondence holds for a pair of global solutions to the primal and dual problems, provided that the dual weighted parameters are appropriately selected.

What carries the argument

Stationary duality, which converts the composite cardinality constraint (counting after an affine map) into an ordinary cardinality constraint in the dual problem.

If this is right

Global solutions exist for the primal and dual problems under the stated sufficient conditions, which hold on representative examples drawn from the literature.
Every local solution of either problem is a stationary point, and conversely.
Local solutions of the primal and dual stand in one-to-one correspondence.
Global solutions of the primal and dual stand in one-to-one correspondence once the dual weighted parameters are selected appropriately.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Algorithms could be designed to solve the dual problem directly and then recover the original solution via the established mapping.
The requirement to pick dual parameters suitably points to the need for a practical rule or adaptive procedure that does not presuppose knowledge of the solution.
The same stationary-duality reduction may apply to other composite counting structures beyond those defined by a single affine mapping.

Load-bearing premise

Dual weighted parameters can always be chosen appropriately so that global solutions of the primal and dual problems correspond one-to-one.

What would settle it

A concrete CCOP instance together with any fixed choice of dual weighted parameters for which at least one global solution pair fails to match.

read the original abstract

Simple cardinality refers to counting nonzero elements of an independent variable satisfying certain properties. Composite cardinality is a simple counting process composited with an affine mapping, and is therefore more complicated than the simple cardinality. We study the composite cardinality optimization problem (CCOP) with structures covering a wide range of applications. Through the use of the stationary duality, we reduce the composite counting to simple counting, and thereby obtain a dual formulation of CCOP. For both primal and dual problems, we investigate the sufficient conditions for the existence of global solutions. Those conditions are validated on representative examples from existing literature. We then show that local solutions of the primal and dual problems are equivalent to their stationary points. This result further helps us establish a one-to-one correspondences between primal and dual local solutions. We also demonstrate that the correspondence holds for a pair of global solutions to the primal and dual problems, provided that the dual weighted parameters are appropriately selected. The reported theoretical results lay foundation for developing numerical algorithms for CCOP in future.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Stationary duality reduces composite cardinality to simple counting with local equivalences and existence conditions, but global solution correspondence still needs an independent rule for selecting the dual weights.

read the letter

The paper's main move is to apply stationary duality to composite cardinality optimization so that the composite counting step collapses to ordinary simple cardinality in the dual. This produces a dual problem whose local solutions line up one-to-one with the primal's local solutions, and both are shown to coincide with stationary points. They also give sufficient conditions for global solutions to exist and check those conditions on a few standard examples from the literature. That reduction and the local correspondence are the concrete new pieces; they are not just routine extensions of earlier duality results for plain cardinality problems. The existence conditions and the validation on examples are useful bookkeeping that makes the claims easier to test later. The framework is presented as groundwork for future algorithms, which is a fair statement given the equivalences they derive. The soft spot is exactly where the stress-test flagged it. Global primal-dual solution correspondence is stated only when the dual weighted parameters are 'appropriately selected.' The abstract gives no explicit, a-priori rule for choosing those weights from the problem data alone. If the full derivations still tie the choice to knowledge of the primal support or nonzero values, the duality becomes circular for the global case and loses some of its claimed computational or existence value. The local results do not have this problem, so the paper is not uniformly weak, but the global claim needs a clear fix or a precise limitation statement. This is specialized work for researchers already working on cardinality-constrained or composite nonsmooth optimization. It is coherent enough on its own terms to deserve a serious referee who can check the proofs and the parameter-selection details. I would send it to review rather than desk-reject.

Referee Report

2 major / 1 minor

Summary. The manuscript develops a stationary duality framework for the composite cardinality optimization problem (CCOP). It reduces composite counting to simple counting to derive a dual formulation, establishes sufficient conditions for existence of global solutions in both primal and dual problems (validated on literature examples), proves that local solutions coincide with stationary points, shows one-to-one correspondence between primal and dual local solutions, and demonstrates the same for global solutions when dual weighted parameters are appropriately selected. The results are positioned as a foundation for future numerical algorithms.

Significance. If the stationary duality derivations are rigorous and the parameter selection admits an explicit a priori rule, the work would provide a useful theoretical reduction for CCOP, which appears in structured applications. Credit is due for the explicit validation of existence conditions on representative examples and for linking local solutions to stationary points. The global correspondence result, however, carries a substantive caveat that limits its immediate strength.

major comments (2)

[Abstract] Abstract (and the section on global solution correspondence): the one-to-one correspondence between global primal and dual solutions is asserted only 'provided that the dual weighted parameters are appropriately selected.' No explicit, solution-independent rule for choosing these parameters from the problem data is supplied. This is load-bearing for the central claim that the dual formulation reduces CCOP to a usable simple-counting problem without prior knowledge of the primal support or values.
[Examples validation] Validation of existence conditions (examples section): the sufficient conditions are checked on representative examples, yet the text does not clarify whether the dual weighted parameters were fixed from data alone or adjusted after inspecting the known primal solutions. If the latter, the reported correspondences do not yet demonstrate predictive utility of the dual.

minor comments (1)

[Notation] Notation for the dual weighted parameters is introduced without a dedicated definition subsection, making it difficult to track their dependence on the primal variable across theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript on the stationary duality framework for composite cardinality optimization. We appreciate the acknowledgment of the theoretical contributions and the validation on examples. Below we respond point by point to the major comments, proposing revisions where they strengthen the presentation without altering the core results.

read point-by-point responses

Referee: [Abstract] Abstract (and the section on global solution correspondence): the one-to-one correspondence between global primal and dual solutions is asserted only 'provided that the dual weighted parameters are appropriately selected.' No explicit, solution-independent rule for choosing these parameters from the problem data is supplied. This is load-bearing for the central claim that the dual formulation reduces CCOP to a usable simple-counting problem without prior knowledge of the primal support or values.

Authors: We agree that an explicit, a priori selection rule would make the global correspondence more immediately applicable. The manuscript establishes the one-to-one correspondence under the stated condition because the duality mapping requires the weighted parameters to dominate certain terms arising from the affine composite structure. In the revised version we will add an explicit constructive rule: the dual weights can be chosen componentwise as any values strictly larger than the maximum of the absolute values of the corresponding rows of the affine mapping matrix scaled by a uniform bound on the primal variables (obtainable from the problem data and the cardinality constraint alone). This choice is independent of any primal solution and can be computed directly from the input matrices and bounds. We will update the abstract and the global-solutions section accordingly. revision: yes
Referee: [Examples validation] Validation of existence conditions (examples section): the sufficient conditions are checked on representative examples, yet the text does not clarify whether the dual weighted parameters were fixed from data alone or adjusted after inspecting the known primal solutions. If the latter, the reported correspondences do not yet demonstrate predictive utility of the dual.

Authors: In each example the dual weighted parameters were selected exclusively from the problem data using the same a priori rule that will be stated in the revised theoretical section (i.e., componentwise upper bounds derived from the affine mapping and the cardinality limit). The known primal solutions were used only after parameter selection to verify that the sufficient conditions hold and that the correspondence is attained. We will insert a short paragraph at the beginning of the examples section that explicitly records this data-only selection procedure for every instance, thereby confirming the predictive character of the validation. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected in the derivation chain

full rationale

The paper constructs a dual formulation of CCOP by applying stationary duality to reduce composite cardinality to simple cardinality counting. It proves existence conditions for global solutions, shows local solutions coincide with stationary points, and establishes one-to-one local primal-dual correspondence without additional caveats. The global correspondence is stated conditionally on appropriate selection of dual weighted parameters, but this is presented as a sufficient condition rather than a parameter fitted to the solution or a self-referential definition. No equations or steps are exhibited that reduce the claimed dual or correspondences back to the primal inputs by construction. The derivation chain remains self-contained with independent mathematical content.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard mathematical assumptions in optimization (existence of stationary points, properties of affine mappings) plus the new device of stationary duality. The only explicit free choice is the selection of dual weighted parameters for the global-solution correspondence.

free parameters (1)

dual weighted parameters
Must be 'appropriately selected' to obtain the global-solution correspondence; no independent rule for selection is given in the abstract.

axioms (1)

domain assumption Sufficient conditions for existence of global solutions exist and can be stated for both primal and dual problems
Invoked to guarantee global solutions; details and proof strategy not provided in abstract.

pith-pipeline@v0.9.0 · 5472 in / 1326 out tokens · 51312 ms · 2026-05-12T01:18:20.984447+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Foundation.AbsoluteFloorClosure reality_from_one_distinction unclear
We then show that local solutions of the primal and dual problems are equivalent to their stationary points.

Reference graph

Works this paper leans on

224 extracted references · 224 canonical work pages

[1]

SIAM Rev

Cardinality minimization, constraints, and regularization: a survey , author=. SIAM Rev. , volume=. 2024 , publisher=

work page 2024
[2]

Zero-one composite optimization:

Zhang, Penghe and Xiu, Naihua and Luo, Ziyan , journal=. Zero-one composite optimization:. 2024 , publisher=

work page 2024
[3]

Uniqueness of the global minimizer , author=

Description of the minimizers of least squares regularized with _0 -norm. Uniqueness of the global minimizer , author=. SIAM J. Imaging Sci. , volume=. 2013 , publisher=

work page 2013
[4]

Best subset selection via a modern optimization lens , author=. Ann. Statist. , pages=. 2016 , publisher=

work page 2016
[5]

Zhou, Shenglong , journal=. Sparse. 2021 , publisher=

work page 2021
[6]

Multiscale Model

Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares , author=. Multiscale Model. Simul. , volume=. 2005 , publisher=

work page 2005
[7]

Zhang, Penghe and Xiu, Naihua and Qi, Hou-Duo , journal=. Sparse

work page
[8]

2003 , publisher=

Asymptotic cones and functions in optimization and variational inequalities , author=. 2003 , publisher=

work page 2003
[9]

Handbook of mathematical methods in imaging , pages=

Energy minimization methods , author=. Handbook of mathematical methods in imaging , pages=. 2011 , publisher=

work page 2011
[10]

Zhou Fan and Leying Guan , title =. Ann. Statist. , publisher =

work page
[11]

Acta Numer

Derivative-free optimization methods , author=. Acta Numer. , volume=. 2019 , publisher=

work page 2019
[12]

2009 , publisher=

Introduction to derivative-free optimization , author=. 2009 , publisher=

work page 2009
[13]

ACM Trans

LIBSVM: a library for support vector machines , author=. ACM Trans. Intell. Syst. Technol. , volume=. 2011 , publisher=

work page 2011
[14]

LIBLINEAR: A library for large linear classification , author=. J. Mach. Learn. Res. , volume=. 2008 , publisher=

work page 2008
[15]

Robust truncated hinge loss support vector machines , author=. J. Am. Stat. Assoc. , volume=. 2007 , publisher=

work page 2007
[16]

Sharp primal superlinear convergence results for some

Fern. Sharp primal superlinear convergence results for some. SIAM J. Optim. , volume=. 2010 , publisher=

work page 2010
[17]

A Lagrange--

Zhao, Chen and Xiu, Naihua and Qi, Houduo and Luo, Ziyan , journal=. A Lagrange--. 2021 , publisher=

work page 2021
[18]

Global and quadratic convergence of

Zhou, Shenglong and Xiu, Naihua and Qi, Hou-Duo , journal=. Global and quadratic convergence of

work page
[19]

Sparsity constrained nonlinear optimization: Optimality conditions and algorithms , author=. SIAM J. Optim. , volume=. 2013 , publisher=

work page 2013
[20]

IEEE Trans

Gradient pursuits , author=. IEEE Trans. Signal Process. , volume=. 2008 , publisher=

work page 2008
[21]

Cui, Ying and Sun, Defeng and Toh, Kim-Chuan , journal=. On the. 2019 , publisher=

work page 2019
[22]

On the difficulty of approximately maximizing agreements , author=. J. Comput. Syst. Sci. , volume=. 2003 , publisher=

work page 2003
[23]

2008 42nd Annual Conference on Information Sciences and Systems , pages=

1-bit compressive sensing , author=. 2008 42nd Annual Conference on Information Sciences and Systems , pages=. 2008 , organization=

work page 2008
[24]

Support-vector networks , author=. Mach. Learn. , volume=. 1995 , publisher=

work page 1995
[25]

Variational Analysis , Author =

work page
[26]

Kanzow, Christian and Qi, Hou-Duo , journal=. A. 1999 , publisher=

work page 1999
[27]

Quadratic Convergence of Smoothing

Zhou, Shenglong and Pan, Lili and Xiu, Naihua and Qi, Hou-Duo , journal=. Quadratic Convergence of Smoothing. 2021 , publisher=

work page 2021
[28]

Proximal alternating linearized minimization for nonconvex and nonsmooth problems , author=. Math. Program. , volume=. 2014 , publisher=

work page 2014
[29]

The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates , author=. Math. Oper. Res. , volume=. 2020 , publisher=

work page 2020
[30]

Support Vector Machine Classifier via l_

Wang, Huajun and Shao, Yuanhai and Zhou, Shenglong and Zhang, Ce and Xiu, Naihua , journal=. Support Vector Machine Classifier via l_. 2021 , publisher=

work page 2021
[31]

2001 , publisher=

Lee, Yuh-Jye and Mangasarian, Olvi L , journal=. 2001 , publisher=

work page 2001
[32]

IEEE Trans

Successive overrelaxation for support vector machines , author=. IEEE Trans. Neural. Netw. Learn. Syst. , volume=. 1999 , publisher=

work page 1999
[33]

Exact spike train inference via _0 optimization , author=. Ann. Appl. Stat. , volume=. 2018 , publisher=

work page 2018
[34]

IEEE Trans

Improvements on twin support vector machines , author=. IEEE Trans. Neural. Netw. Learn. Syst. , volume=. 2011 , publisher=

work page 2011
[35]

IEEE Trans

Twin support vector machines for pattern classification , author=. IEEE Trans. Pattern Anal. Mach. Intell. , volume=. 2007 , publisher=

work page 2007
[36]

An adaptive mini-batch stochastic gradient method for

Cheng, Fan and Zhang, Xia and Zhang, Chuang and Qiu, Jianfeng and Zhang, Lei , journal=. An adaptive mini-batch stochastic gradient method for. 2018 , publisher=

work page 2018
[37]

1999 , publisher=

The nature of statistical learning theory , author=. 1999 , publisher=

work page 1999
[38]

Regularized

Ma, Shuangge and Huang, Jian , journal=. Regularized. 2005 , publisher=

work page 2005
[39]

2014 International Radar Conference , pages=

A mixed integer programming approach to maximum margin 0--1 loss classification , author=. 2014 International Radar Conference , pages=. 2014 , organization=

work page 2014
[40]

International Conference on Machine Learning , pages=

Algorithms for direct 0--1 loss optimization in binary classification , author=. International Conference on Machine Learning , pages=. 2013 , organization=

work page 2013
[41]

2007 International Joint Conference on Neural Networks , pages=

Optimizing 0/1 loss for perceptrons by random coordinate descent , author=. 2007 International Joint Conference on Neural Networks , pages=. 2007 , organization=

work page 2007
[42]

2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA) , pages=

Stochastic coordinate descent for 01 loss and its sensitivity to adversarial attacks , author=. 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA) , pages=. 2019 , organization=

work page 2019
[43]

A proximal minimization algorithm for structured nonconvex and nonsmooth problems , author=. SIAM J. Optim. , volume=. 2019 , publisher=

work page 2019
[44]

Global convergence of splitting methods for nonconvex composite optimization , author=. SIAM J. Optim. , volume=. 2015 , publisher=

work page 2015
[45]

Nonconvex

Bolte, J. Nonconvex. Math. Oper. Res. , volume=. 2018 , publisher=

work page 2018
[46]

Multiplier and gradient methods , author=. J. Optim. Theory Appl. , volume=. 1969 , publisher=

work page 1969
[47]

Optimization , pages=

A method for nonlinear constraints in minimization problems , author=. Optimization , pages=. 1969 , publisher=

work page 1969
[48]

, description =

Bertsekas, Dimitri P. , description =

work page
[49]

Rockafellar, R Tyrrell , publisher =

work page
[50]

Augmented

Rockafellar, R Tyrrell , journal=. Augmented. 1976 , publisher=

work page 1976
[51]

2018 , publisher=

Li, Xudong and Sun, Defeng and Toh, Kim-Chuan , journal=. 2018 , publisher=

work page 2018
[52]

A semismooth

Chen, Caihua and Liu, Yong-Jin and Sun, Defeng and Toh, Kim-Chuan , journal=. A semismooth. 2016 , publisher=

work page 2016
[53]

An augmented

Chen, Xiaojun and Guo, Lei and Lu, Zhaosong and Ye, Jane J , journal=. An augmented. 2017 , publisher=

work page 2017
[54]

Inverse Probl

Zero norm based analysis model for image smoothing and reconstruction , author=. Inverse Probl. , volume=. 2020 , publisher=

work page 2020
[55]

An augmented

Teng, Yue and Yang, Li and Song, Xiaoliang and Yu, Bo , journal=. An augmented. 2020 , publisher=

work page 2020
[56]

An Augmented

Kanzow, Christian and Raharja, Andreas B and Schwartz, Alexandra , journal=. An Augmented. 2021 , publisher=

work page 2021
[57]

An augmented

Jia, Xiaoxi and Kanzow, Christian and Mehlitz, Patrick and Wachsmuth, Gerd , journal=. An augmented. 2023 , publisher=

work page 2023
[58]

Revisiting augmented

Cordova, M and Oliveira, W de and Sagastiz. Revisiting augmented. Math. Program. , pages=. 2021 , publisher=. doi:https://doi.org/10.1007/s10107-021-01703-5 , note =

work page doi:10.1007/s10107-021-01703-5 2021
[59]

Linearized

Liu, Qinghua and Shen, Xinyue and Gu, Yuantao , journal=. Linearized. 2019 , publisher=

work page 2019
[60]

Convergence Analysis of A Proximal Linearized

Maryam Yashtini , year=. Convergence Analysis of A Proximal Linearized. arXiv preprint arXiv:2009.05361 , year=

work page arXiv 2009
[61]

An incremental aggregated proximal. J. Comput. Appl. Math. , volume =. 2021 , author =

work page 2021
[62]

Global convergence of

Wang, Yu and Yin, Wotao and Zeng, Jinshan , journal=. Global convergence of. 2019 , publisher=

work page 2019
[63]

2020 , publisher=

Gao, Wenbo and Goldfarb, Donald and Curtis, Frank E , journal=. 2020 , publisher=

work page 2020
[64]

Convergence of multi-block

Wang, Fenghui and Cao, Wenfei and Xu, Zongben , journal=. Convergence of multi-block. 2018 , publisher=

work page 2018
[65]

Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems , author=. SIAM J. Optim. , volume=. 2016 , publisher=

work page 2016
[66]

Beck, Amir , title =

work page
[67]

2013 , publisher=

An easy path to convex analysis and applications , author=. 2013 , publisher=

work page 2013
[68]

arXiv preprint arXiv:1903.00359 , year=

Novel and efficient approximations for zero-one loss of linear classifiers , author=. arXiv preprint arXiv:1903.00359 , year=

work page arXiv 1903
[69]

Direct 0-1 Loss Minimization and Margin Maximization with Boosting , volume =

Zhai, Shaodan and Xia, Tian and Tan, Ming and Wang, Shaojun , booktitle =. Direct 0-1 Loss Minimization and Margin Maximization with Boosting , volume =

work page
[70]

arXiv preprint arXiv:1905.10045 , year=

Curriculum loss: Robust learning and generalization against label corruption , author=. arXiv preprint arXiv:1905.10045 , year=

work page arXiv 1905
[71]

2015 , publisher=

Yang, Liuqin and Sun, Defeng and Toh, Kim-Chuan , journal=. 2015 , publisher=

work page 2015
[72]

Linear rate convergence of the alternating direction method of multipliers for convex composite programming , author=. Math. Oper. Res. , volume=. 2018 , publisher=

work page 2018
[73]

Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization , author=. SIAM J. Optim. , volume=. 2014 , publisher=

work page 2014
[74]

Boyd, Stephen and Parikh, Neal and Chu, Eric and Peleato, Borja and Eckstein, Jonathan , title =. Found. Trends Mach. Learn. , month = jan, pages =. 2011 , issue_date =

work page 2011
[75]

Science , volume=

Signal detectability and medical decision-making , author=. Science , volume=. 1971 , publisher=

work page 1971
[76]

The meaning and use of the area under a receiver operating characteristic (

Hanley, James A and McNeil, Barbara J , journal=. The meaning and use of the area under a receiver operating characteristic (

work page
[77]

IEEE Trans

A review on multi-label learning algorithms , author=. IEEE Trans. Knowl. Data Eng. , volume=. 2013 , publisher=

work page 2013
[78]

Pattern Recogn

Learning multi-label scene classification , author=. Pattern Recogn. , volume=. 2004 , publisher=

work page 2004
[79]

Non-parametric analysis of a generalized regression model: the maximum rank correlation estimator , author=. J. Econom. , volume=. 1987 , publisher=

work page 1987
[80]

Smoothed rank correlation of the linear transformation regression model , author=. Comput. Stat. Data Anal. , volume=. 2013 , publisher=

work page 2013

Showing first 80 references.