Pith. sign in

REVIEW 3 major objections 4 minor 64 references

Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Iterative hard thresholding with an extra convex constraint converges globally in objective value, at rate $O(\kappa \log 1/\epsilon)$, when the constraint is support-preserving; the same proof removes the zeroth-order system error of…

desk verdict Real technique and a real zeroth-order advance, but the central theorems as printed are false because they omit the condition wbar in Gamma; with that hypothesis added, the paper is conditionally acceptable. read the letter →

arxiv 2506.08558 v2 pith:NTCX2ZTD submitted 2025-06-10 math.OC cs.LG

William de Vazelhes , Xiao-Tong Yuan , Bin Gu This is my paper
classification math.OCcs.LG MSC 90C2690C30
keywords iterativehardthresholdingsupport-preservingsettwo-stepprojectionthree-pointlemmarestrictedstrongconvexityzeroth-orderoptimizationstochasticsparse
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

Many sparse-optimization problems come with extra convex constraints—budget limits in portfolios, norm bounds in non-negative matrix factorization—and iterative hard thresholding (IHT) had no global sub-optimality guarantees for that mixed setting. This paper proposes a two-step projection that first hard-thresholds a gradient iterate to $k$ nonzero coordinates and then projects onto the convex set, and proves that the iterates converge in objective value to within $(1+2\rho)R(\bar{w})+\epsilon$ in $O(\kappa_s \log(1/\epsilon))$ iterations, provided the convex set is support-preserving. The same guarantee is extended to stochastic and zeroth-order versions, and the zeroth-order result removes a non-vanishing system error present in earlier work. The engine is a new three-point lemma for the non-convex two-step projection, which lets the proof telescope under restricted strong convexity and smoothness.

What carries the argument

The machinery is the two-step projection $\bar{\Pi}_\Gamma^k(w)=\Pi_\Gamma(H_k(w))$: first keep the $k$ largest-magnitude coordinates (the hard-thresholding operator $H_k$), then take the Euclidean projection onto the convex set $\Gamma$. When $\Gamma$ is $k$-support-preserving, meaning the projection of any $k$-sparse vector never creates nonzeros outside its support, this two-step output lies in $B_0(k)\cap\Gamma$. The load-bearing identity is Lemma 3.6, the constrained $\ell_0$ three-point inequality $$\|\bar{\Pi}_\Gamma^k(w)-w\|^2 \le \|w-\bar{w}\|^2 - \|\bar{\Pi}_\Gamma^k(w)-\bar{w}\|^2 + \sqrt{\$\beta$}\|H_k(w)-\bar{w}\|^2, \quad \$\beta$=\bar{k}/k,$$ which extends the convex three-point lemma through the relative-concavity coefficient $\sqrt{\bar{k}/k}$ of hard thresholding and is what makes the telescoping convergence proof work.

What would settle it

Run the deterministic algorithm on an RSC/RSS quadratic in dimension at least 3 with $k=1$ and $\Gamma$ the standard simplex $\{z: z\ge 0, \sum_i z_i=1\}$. After one gradient step, hard-thresholding can select a single negative coordinate, and the simplex projection then assigns positive mass to several coordinates that $H_1$ had zeroed, so the two-step iterate leaves $B_0(1)$; if such an iterate appears under the theorem's parameter regime, the claimed guarantee cannot hold as stated.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.7: suppose $R$ is $(\nu_s,s)$-restricted strongly convex and $(L_s,s)$-restricted smooth with $s=2k$, $\Gamma$ is $k$-support-preserving, and $\bar{w}$ is any $\bar{k}$-sparse point in $\Gamma$. For any $\rho\in(0,1/2]$ and $k\ge 4(1-\rho)^2 L_s^2/(\rho^2\nu_s^2)\bar{k}$, Algorithm 1 with step size $1/L_s$ satisfies $\min_{t\le T}R(w_t)\le(1+2\rho)R(\bar{w})+\epsilon$ after $T=O(\kappa_s\log(1/\epsilon))$ iterations, with $\kappa_s=L_s/\nu_s$. Theorem 4.3 proves the stochastic analogue with exponentially growing batch sizes, and Theorem 4.8 proves the zeroth-order analogue with exponentially growing numbers of random directions. In the zeroth-order case the paper claims the first convergence-in-risk guarantee without system error for a hard-thresholding algorithm, even when no extra constraint is present, improving on the result from (de Vazelhes et al., 2022).

Load-bearing premise

The analysis collapses if the extra constraint ever turns a zero coordinate into a nonzero one when a sparse vector is projected onto it—the key inequality needs those supports to stay disjoint—and the theorem statements also silently require the reference point $\bar{w}$ to lie in $\Gamma$.

Editorial extensions

If this is right

  • Deterministic IHT-2SP reaches $\min_{t\le T}R(w_t)\le(1+2\rho)R(\bar{w})+\epsilon$ in $O(\kappa_s\log(1/\epsilon))$ iterations whenever $k\ge 4(1-\rho)^2L_s^2/(\rho^2\nu_s^2)\bar{k}$, so no closed-form projection onto the mixed constraint is needed.
  • The stochastic variant matches the same rate with exponentially increasing batch sizes; the number of gradient calls to reach $\epsilon$ is $O(\kappa_s/(\nu_s\epsilon))$.
  • The zeroth-order variant delivers a convergence-in-risk bound without system error, with query complexity that is dimension-independent when the random directions sample the full space.
  • A small $\rho$ gives a tighter factor $(1+2\rho)$ but demands a larger sparsity relaxation $k\propto 1/\rho^2$; this explicit trade-off is the paper's mechanism for balancing sub-optimality against iterate sparsity.
  • For sign-free sets such as $\ell_p$ balls, the two-step projection equals the Euclidean projection onto the mixed constraint, so the theorems also globalize the guarantees of projected gradient descent in this mixed setting.

Reading between the lines

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

  • The support-preserving condition silently excludes many natural constraints—for example the standard probability simplex, whose projection can turn zero coordinates positive—so the theorems should not be read as covering them; a support-expansion allowance would be needed.
  • The same three-point proof is likely to transfer to other non-convex projection operators such as group-sparse or low-rank hard thresholding, where comparable relative-concavity coefficients exist; that is the paper's own suggested but undeveloped direction.
  • A direct experiment can isolate the role of the assumption: on a non-support-preserving constraint, the two-step iterate may leave $B_0(k)\cap\Gamma$, and the objective gap should visibly fail to follow the predicted $(1+2\rho)R(\bar{w})+\epsilon$ envelope.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies sparse optimization with an additional convex 'support-preserving' constraint set Γ, proposing an iterative hard-thresholding algorithm whose projection step first hard-thresholds to k-sparsity and then projects onto Γ. The main theoretical contribution is a constrained three-point lemma (Lemma 3.6) and its use in proving global objective-value guarantees for deterministic, stochastic, and zeroth-order variants under restricted strong convexity/smoothness assumptions. The headline results are Theorems 3.7, 4.3, and 4.8, which give bounds of the form R(ŵ) ≤ (1+2ρ)R(w̄)+ε with sparsity level k = O(κ²k̄/ρ²), and, in the zeroth-order case, a claimed removal of the non-vanishing system error present in de Vazelhes et al. (2022).

Significance. If the theorem statements are corrected, the paper makes a genuinely useful contribution: it provides a proof framework that unifies and simplifies existing IHT analyses, extends global sub-optimality guarantees to a natural class of mixed ℓ0-plus-convex constraints, and improves the zeroth-order IHT literature by eliminating a non-vanishing system error. The core three-point lemma (Lemma 3.6) is a real technical innovation, and the proofs are well structured and largely self-contained, importing known relative-concavity and zeroth-order estimator results from the literature rather than introducing fitted constants. The paper also ships reproducible code and useful experimental illustrations, and its Table 1 gives a clear comparison with prior work. The main caveat is that the theorem statements, as printed, omit a required feasibility hypothesis, and one 'without loss of generality' assertion is not valid for the multiplicative bound being proved; both issues are fixable without changing the proof strategy.

major comments (3)
  1. [Theorem 3.7 and Theorems 4.3, 4.8] As stated, Theorem 3.7 asserts a bound for 'an arbitrary k̄-sparse vector w̄', but the proof (Lemma 3.6, and the non-expansiveness step in App. E.2.2, Eq. (12)) requires w̄ ∈ Γ. Without this hypothesis the theorem is false. For example, take R(w)=‖w−e₁‖², Γ={0}, k̄=1, k=4, ρ=0.5, L_s=ν_s=2. Γ is support-preserving, R is non-negative and satisfies (2,8)-RSC/RSS, Algorithm 1 projects every iterate onto {0}, so R(w_t)=1 for all t, while w̄=e₁ is 1-sparse with R(w̄)=0. The printed bound min_{t≤T} R(w_t) ≤ ε for arbitrarily small ε is therefore false, and the 'further' global-minimizer claim fails identically since e₁ is a global minimizer of R over B0(4). The fix is to state all bounds for w̄ ∈ Γ ∩ B0(k̄), exactly as Table 1 does; under that intended reading the proof is coherent. The same missing hypothesis appears in Theorems 4.3 and 4.8, whose proofs use Lemma 3.6 and the same non-expansiveness argument.
  2. [Theorems 3.7, 4.3, 4.8 and proofs (App. E.2.2, F.2.3, F.4.3)] The phrase 'R is non-negative (without loss of generality)' is not a valid WLOG reduction for the multiplicative bound R(w_t) ≤ (1+2ρ)R(w̄)+ε. If one shifts R to R+c, the right-hand side becomes (1+2ρ)(R(w̄)+c)+ε, which is not equivalent to the original target inequality; the residual 2ρc does not vanish when translating back. Non-negativity is used only to drop the term ρR(v_t) in the proofs, so it should be stated as an explicit assumption on the original R (or the proof should be modified to handle a lower-bound assumption directly).
  3. [Theorem 3.7, 'Further' claim] The 'further' claim in Theorem 3.7 (and its analogues in Theorems 4.3 and 4.8) assumes that w̄ is a global minimizer of R over B0(k) while w̄ was introduced as an arbitrary k̄-sparse vector. This is internally inconsistent: an arbitrary vector cannot be assumed to be a global minimizer. The intended meaning is presumably 'if the comparator w̄ in the preceding bound happens to be a global minimizer over B0(k)', but as written the statement invites the counterexample above, where e₁ is a global minimizer and the claimed conclusion fails. This should be reworded and the hypothesis w̄ ∈ Γ should be carried through.
minor comments (4)
  1. [Appendix A] The notation list in Appendix A states that ∥·∥ denotes the ℓ0 pseudo-norm, while Section 2 defines ∥·∥ as the ℓ2 norm; this is inconsistent and should be corrected.
  2. [Theorem 4.8 and Appendix F.4.3] Theorem 4.8 lists 'Assumption 2.3' among its hypotheses, but there is no Assumption 2.3 in the paper; the intended reference is Definition 2.3 (support-preserving set).
  3. [Lemma 3.6 proof (App. E.1.4)] The proof of Lemma 3.6 would be easier to follow if it explicitly stated that v_k−w is zero on supp(v_k) and that Π_Γ(v_k)−v_k is supported inside supp(v_k); the current sentence 'which imply that ... have disjoint supporting sets' is correct but terse.
  4. [Section H.3] In the multiclass logistic regression experiment description, the text reads 'We set set all other hyperparameters'; this is a typo and should be 'We set all other hyperparameters'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity (score 0): Lemmas 3.2/3.6 are derived from the external relative-concavity result of Liu & Foygel Barber (2020), and the self-cited ZO estimator bounds are independent evidence, so the guarantees do not reduce to their inputs. Non-circular correctness flag: Theorems 3.7/4.3/4.8 omit the w̄∈Γ hypothesis their proofs require; as printed, Theorem 3.7 is false.

full rationale

The derivation chain is self-contained given independently checkable inputs. Lemma 3.2 (the unconstrained ℓ0 three-point lemma) is proven in App. E.1.2 from the external relative-concavity bound of Liu & Foygel Barber (2020) (Lemma E.2, γ_{k,β}(H_k) = √β/2), and its tightness is shown by explicit example (Lemma 3.3). The central new tool, Lemma 3.6, is derived rather than assumed: App. E.1.4 combines Lemma 3.2 with the standard three-point lemma for the convex projection onto Γ, using Definition 2.3 only to conclude that supp(Π̄^k_Γ(w)−v_k) ⊆ supp(v_k) and supp(v_k−w) ⊆ supp(v_k)^c so that the cross-term vanishes; the algebra is explicit. Theorems 3.7, 4.3, and 4.8 then follow from RSS/RSC inequalities and telescoping sums, with ρ a free theorem parameter, so the claimed (1+2ρ)-suboptimality versus sparsity-relaxation trade-off is a consequence of the bound, not a fitted input. The only self-citation, (de Vazelhes et al., 2022), supplies Proposition F.5 and Lemma F.6 — parameter-free bias and second-moment bounds on the ZO gradient estimator whose stated assumptions do not include any convergence conclusion; the claimed removal of the non-vanishing system error via exponentially increasing q_t is new telescoping analysis built on those lemmas, so per the rules this citation is real, independent evidence and does not raise the score. No uniqueness-theorem import, no ansatz-via-citation, and no renaming of known results occurs: Theorems 3.4 and 4.2 are explicitly labeled equivalent to (Jain et al., 2014) and (Zhou et al., 2018) and are re-proven inside the paper. Flagged explicitly, located, and weighed (these are soundness defects, not circular reductions): Lemma 3.6 assumes 'w̄∈Γ', and the proof of Theorem 3.7 uses 'w̄∈Γ and the non-expansiveness of projection over convex sets', yet Theorems 3.7, 4.3, and 4.8 are printed with only 'w̄ be an arbitrary k̄-sparse vector'; since Γ={0} is support-preserving and R(w)=∥w−e_1∥² is RSC/RSS, Algorithm 1 stays at 0 (R=1) while w̄=e_1 is 1-sparse with R(w̄)=0, so the printed theorem is false unless w̄∈Γ∩B_0(k̄) is added (as Table 1 states). Similarly, 'R is non-negative (without loss of generality)' is invalid for the multiplicative bound because a constant shift c changes the right-hand side by 2ρc. These gaps should be fixed at revision but do not affect the circularity verdict.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central theorems rest on RSC/RSS, support-preservation, feasible comparators, a cited relative-concavity lemma, and nonnegativity of R. No invented entities or fitted constants appear, but the feasibility and sparsity conditions of the comparator are under-specified in the theorem statements.

free parameters (1)
  • rho (sparsity/sub-optimality trade-off)
    User-chosen in (0,0.5] or (0,1); the sparsity relaxation k scales as 1/rho^2 while the optimality slack is (1+2rho)R(wbar). Not fitted to data, but every main bound depends on it.
assumptions (5)
  • domain assumption R satisfies (nu_s, s)-RSC and (L_s, s)-RSS (or RSS'), Assumptions 2.1, 2.2, and 4.5.
    All convergence theorems are conditional on these restricted curvature and smoothness constants; they drive the telescoping arguments.
  • domain assumption Gamma is k-support-preserving (Definition 2.3).
    Used in Lemma 3.6 to guarantee supp(Pi_Gamma(H_k(w))) is a subset of supp(H_k(w)), giving orthogonality and feasibility. Fails for many natural sets such as the probability simplex when starting points can have negative coordinates.
  • domain assumption Comparator wbar lies in Gamma.
    The theorem statements in the main text omit this, but the proofs use wbar in Gamma for the convex three-point lemma and for non-expansiveness of Pi_Gamma. Without it the bound is not meaningful.
  • standard math The relative concavity coefficient of the hard-thresholding operator is sqrt(beta)/2 (Lemma E.2 from Liu and Foygel Barber 2020).
    External lemma, cited but not proven in the paper; it underpins Lemma 3.2 and therefore all subsequent three-point inequalities.
  • ad hoc to paper R is non-negative (stated 'without loss of generality').
    Used to lower-bound R(v_t) by 0 when converting the combination bound to min R(w_t). Adding a constant does not preserve the multiplicative bound (1+2rho)R(wbar), so this is not actually WLOG.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees." pith.science (2026). https://pith.science/paper/NTCX2ZTD

@misc{pith2026250608558,
  author       = {Pith},
  title        = {Pith review of: Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NTCX2ZTD}},
  note         = {Machine review of arXiv:2506.08558}
}
abstract

In sparse optimization, enforcing hard constraints using the $\ell_0$ pseudo-norm offers advantages like controlled sparsity compared to convex relaxations. However, many real-world applications demand not only sparsity constraints but also some extra constraints. While prior algorithms have been developed to address this complex scenario with mixed combinatorial and convex constraints, they typically require the closed form projection onto the mixed constraints which might not exist, and/or only provide local guarantees of convergence which is different from the global guarantees commonly sought in sparse optimization. To fill this gap, in this paper, we study the problem of sparse optimization with extra support-preserving constraints commonly encountered in the literature. We present a new variant of iterative hard-thresholding algorithm equipped with a two-step consecutive projection operator customized for these mixed constraints, serving as a simple alternative to the Euclidean projection onto the mixed constraint. By introducing a novel trade-off between sparsity relaxation and sub-optimality, we provide global guarantees in objective value for the output of our algorithm, in the deterministic, stochastic, and zeroth-order settings, under the conventional restricted strong-convexity/smoothness assumptions. As a fundamental contribution in proof techniques, we develop a novel extension of the classic three-point lemma to the considered two-step non-convex projection operator, which allows us to analyze the convergence in objective value in an elegant way that has not been possible with existing techniques. In the zeroth-order case, such technique also improves upon the state-of-the-art result from de Vazelhes et. al. (2022), even in the case without additional constraints, by allowing us to remove a non-vanishing system error present in their work.

Figures

Figures reproduced from arXiv: 2506.08558 by the authors.

Figure 1
Figure 1. Support-preserving set and two-step projection (d = 2, k = 1). cussions about 2SP vs EP). The 2SP procedure, which we denote by Π¯ k Γ , is as follows: we first project w onto B0(k) through the hard-thresholding operator Hk, to obtain a k￾sparse vector vk = Hk(w). Then, we project vk onto Γ , to obtain a final vector wS = ΠΓ(vk), where S = supp(vk). Note that consequently, the obtained wS is not necessarily the EP o… view at source ↗
Figure 2
Figure 2. Illustration of Theorem 3.4 (i.e. Γ = R d ). 54 [PITH_FULL_IMAGE:figures/full_fig_p054_2.png] view at source ↗
Figure 3
Figure 3. λ = 0.1 [PITH_FULL_IMAGE:figures/full_fig_p055_3.png] view at source ↗
Figures from the paper (10 more)
Figure 5
Figure 5. Figure 5: λ = 1 [PITH_FULL_IMAGE:figures/full_fig_p055_5.png]
Figure 9
Figure 9. Figure 9 [PITH_FULL_IMAGE:figures/full_fig_p057_9.png]
Figure 10
Figure 10. Figure 10: CSI300 [PITH_FULL_IMAGE:figures/full_fig_p057_10.png]
Figure 13
Figure 13. Figure 13 [PITH_FULL_IMAGE:figures/full_fig_p059_13.png]
Figure 17
Figure 17. Figure 17 [PITH_FULL_IMAGE:figures/full_fig_p059_17.png]
Figure 21
Figure 21. Figure 21 [PITH_FULL_IMAGE:figures/full_fig_p059_21.png]
Figure 25
Figure 25. Figure 25 [PITH_FULL_IMAGE:figures/full_fig_p060_25.png]
Figure 28
Figure 28. Figure 28: #IZO [PITH_FULL_IMAGE:figures/full_fig_p060_28.png]
Figure 31
Figure 31. Figure 31: #IZO [PITH_FULL_IMAGE:figures/full_fig_p061_31.png]
Figure 35
Figure 35. Figure 35 [PITH_FULL_IMAGE:figures/full_fig_p061_35.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

64 extracted references · 58 canonical work pages

  1. [1]

    Agarwal, A., Negahban, S., and Wainwright, M. J. Fast global convergence rates of gradient methods for high-dimensional statistical recovery. Advances in Neural Information Processing Systems, 23, 2010

    work page 2010

  2. [2]

    and Stich, S

    Ajalloeian, A. and Stich, S. U. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008.00051, 2020

    arXiv 2008

  3. [3]

    Attouch, H., Bolte, J., and Svaiter, B. F. Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward--backward splitting, and regularized gauss--seidel methods. Mathematical Programming, 137: 0 91--129, 2013

    work page 2013

  4. [4]

    and Sviridenko, M

    Axiotis, K. and Sviridenko, M. Sparse convex optimization via adaptively regularized hard thresholding. The Journal of Machine Learning Research, 22 0 (1): 0 5421--5467, 2021

    work page 2021

  5. [5]

    and Sviridenko, M

    Axiotis, K. and Sviridenko, M. Iterative hard thresholding with adaptive regularization: Sparser solutions without sacrificing runtime. In International Conference on Machine Learning, pp.\ 1175--1197, 2022

    work page 2022

  6. [6]

    and Ghadimi, S

    Balasubramanian, K. and Ghadimi, S. Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates. Advances in Neural Information Processing Systems, 31, 2018

    work page 2018

  7. [7]

    H., Bolte, J., and Teboulle, M

    Bauschke, H. H., Bolte, J., and Teboulle, M. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42 0 (2): 0 330--348, 2017

    work page 2017

  8. [8]

    H., Bolte, J., Chen, J., Teboulle, M., and Wang, X

    Bauschke, H. H., Bolte, J., Chen, J., Teboulle, M., and Wang, X. On linear convergence of non-euclidean gradient methods without strong convexity and lipschitz gradient continuity. Journal of Optimization Theory and Applications, 182: 0 1068--1087, 2019

    work page 2019

Show all 64 references
  1. [9]

    and Hallak, N

    Beck, A. and Hallak, N. On the minimization over sparse symmetric sets: Projections, optimality conditions, and algorithms. Mathematics of Operations Research, 41: 0 196--223, 2016

    2016

  2. [10]

    S., Cao, L., Choromanski, K., and Scheinberg, K

    Berahas, A. S., Cao, L., Choromanski, K., and Scheinberg, K. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, pp.\ 1--54, 2021

    2021

  3. [11]

    Multinomial logistic regression algorithm

    B \"o hning, D. Multinomial logistic regression algorithm. Annals of the Institute of Statistical Mathematics, 44: 0 197--200, 1992

    1992

  4. [12]

    Proximal alternating linearized minimization for nonconvex and nonsmooth problems

    Bolte, J., Sabach, S., and Teboulle, M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146: 0 459--494, 2014

    2014

  5. [13]

    I., Csetnek, E

    Bo t , R. I., Csetnek, E. R., and L \'a szl \'o , S. C. An inertial forward--backward algorithm for the minimization of the sum of two nonconvex functions. EURO Journal on Computational Optimization, 4: 0 3--25, 2016

    2016

  6. [14]

    Sparse and stable markowitz portfolios

    Brodie, J., Daubechies, I., De Mol, C., Giannone, D., and Loris, I. Sparse and stable markowitz portfolios. Proceedings of the National Academy of Sciences, 106: 0 12267--12272, 2009

    2009

  7. [15]

    Bubeck, S. et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8: 0 231--357, 2015

    2015

  8. [16]

    A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization

    Cai, H., Lou, Y., McKenzie, D., and Yin, W. A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization. In International Conference on Machine Learning, pp.\ 1193--1203, 2021

    2021

  9. [17]

    Zeroth-order regularized optimization (zoro): Approximately sparse gradients and adaptive sampling

    Cai, H., Mckenzie, D., Yin, W., and Zhang, Z. Zeroth-order regularized optimization (zoro): Approximately sparse gradients and adaptive sampling. SIAM Journal on Optimization, 2022

    2022

  10. [18]

    and Lin, C.-J

    Chang, C.-C. and Lin, C.-J. LIBSVM : A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2: 0 1--27, 2011

    2011

  11. [19]

    and Shen, J

    Damadi, S. and Shen, J. Gradient properties of hard thresholding operator. arXiv preprint arXiv:2209.08247, 2022

    2022 arXiv

  12. [20]

    and Themelis, A

    De Marchi, A. and Themelis, A. An interior proximal gradient method for nonconvex optimization. arXiv preprint arXiv:2208.00799, 2022

    2022 arXiv

  13. [21]

    Zeroth-order hard-thresholding: Gradient error vs

    de Vazelhes, W., Zhang, H., Wu, H., Yuan, X., and Gu, B. Zeroth-order hard-thresholding: Gradient error vs. expansivity. Advances in Neural Information Processing Systems, 35: 0 22589--22601, 2022

    2022

  14. [22]

    J., and Uppal, R

    DeMiguel, V., Garlappi, L., Nogales, F. J., and Uppal, R. A generalized approach to portfolio optimization: Improving performance by constraining portfolio norms. Management Science, 55: 0 798--812, 2009

    2009

  15. [23]

    and Rauhut, H

    Foucart, S. and Rauhut, H. An invitation to compressive sensing. In A Mathematical Introduction to Compressive Sensing, pp.\ 1--39. Springer, 2013

    2013

  16. [24]

    and Ha, W

    Foygel Barber, R. and Ha, W. Gradient descent with non-convex constraints: local concavity determines convergence. Information and Inference: A Journal of the IMA, 7: 0 755--806, 2018

    2018

  17. [25]

    Splitting methods with variable metric for kurdyka ojasiewicz functions and general convergence rates

    Frankel, P., Garrigos, G., and Peypouquet, J. Splitting methods with variable metric for kurdyka ojasiewicz functions and general convergence rates. Journal of Optimization Theory and Applications, 165: 0 874--900, sep 2014

    2014

  18. [26]

    Gradientless descent: High-dimensional zeroth-order optimization

    Golovin, D., Karro, J., Kochanski, G., Lee, C., Song, X., and Zhang, Q. Gradientless descent: High-dimensional zeroth-order optimization. In International Conference on Learning Representations, 2019

    2019

  19. [27]

    K., Arablouei, R., and Werner, S

    Gratton, C., Venkategowda, N. K., Arablouei, R., and Werner, S. Privacy-preserved distributed learning with zeroth-order optimization. IEEE Transactions on Information Forensics and Security, 17: 0 265--279, 2021

    2021

  20. [28]

    Inexact proximal gradient methods for non-convex and non-smooth optimization

    Gu, B., Wang, D., Huo, Z., and Huang, H. Inexact proximal gradient methods for non-convex and non-smooth optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018

    2018

  21. [29]

    Hoyer, P. O. Non-negative sparse coding. In Proceedings of the 12th IEEE workshop on neural networks for signal processing, pp.\ 557--565. IEEE, 2002

    2002

  22. [30]

    On iterative hard thresholding methods for high-dimensional m-estimation

    Jain, P., Tewari, A., and Kar, P. On iterative hard thresholding methods for high-dimensional m-estimation. Advances in Neural Information Processing Systems, 27, 2014

    2014

  23. [31]

    G., Nowak, R

    Jamieson, K. G., Nowak, R. D., and Recht, B. Query complexity of derivative-free optimization. arXiv preprint arXiv:1209.2434, 2012

    2012 arXiv

  24. [32]

    Sparse projections onto the simplex

    Kyrillidis, A., Becker, S., Cevher, V., and Koch, C. Sparse projections onto the simplex. In International Conference on Machine Learning, pp.\ 235--243, 2013

    2013

  25. [33]

    and Lin, Z

    Li, H. and Lin, Z. Accelerated proximal gradient methods for nonconvex programming. Advances in Neural Information Processing Systems, 28, 2015

    2015

  26. [34]

    Nonconvex sparse learning via stochastic optimization with progressive variance reduction

    Li, X., Arora, R., Liu, H., Haupt, J., and Zhao, T. Nonconvex sparse learning via stochastic optimization with progressive variance reduction. arXiv preprint arXiv:1605.02711, 2016

    2016 arXiv

  27. [35]

    and Foygel Barber, R

    Liu, H. and Foygel Barber, R. Between hard and soft thresholding: optimal iterative thresholding algorithms. Information and Inference: A Journal of the IMA, 9: 0 899--933, 2020

    2020

  28. [36]

    and Yang, Y

    Liu, H. and Yang, Y. A dimension-insensitive algorithm for stochastic zeroth-order optimization. arXiv preprint arXiv:2104.11283, 2021

    2021 arXiv

  29. [37]

    Zeroth-order stochastic variance reduction for nonconvex optimization

    Liu, S., Kailkhura, B., Chen, P.-Y., Ting, P., Chang, S., and Amini, L. Zeroth-order stochastic variance reduction for nonconvex optimization. arXiv preprint arXiv:1805.10367, 2018

    2018 arXiv

  30. [38]

    O., and Varshney, P

    Liu, S., Chen, P.-Y., Kailkhura, B., Zhang, G., Hero III, A. O., and Varshney, P. K. A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37: 0 43--54, 2020

    2020

  31. [39]

    and Wainwright, M

    Loh, P.-L. and Wainwright, M. J. Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima. Advances in Neural Information Processing Systems, 26, 2013

    2013

  32. [40]

    Optimization over sparse symmetric sets via a nonmonotone projected gradient method

    Lu, Z. Optimization over sparse symmetric sets via a nonmonotone projected gradient method. arXiv preprint arXiv:1509.08581, 2015

    2015 arXiv

  33. [41]

    Metel, M. R. Sparse training with lipschitz continuous loss functions and a weighted group l0-norm constraint. Journal of Machine Learning Research, 24: 0 1--44, 2023

    2023

  34. [42]

    Random reshuffling: Simple analysis with vast improvements

    Mishchenko, K., Khaled, A., and Richt \'a rik, P. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33: 0 17309--17320, 2020

    2020

  35. [43]

    J., and Ravikumar, P

    Negahban, S., Yu, B., Wainwright, M. J., and Ravikumar, P. A unified framework for high-dimensional analysis of m -estimators with decomposable regularizers. Advances in Neural Information Processing Systems, 22, 2009

    2009

  36. [44]

    Introductory lectures on convex optimization: A basic course, volume 87

    Nesterov, Y. Introductory lectures on convex optimization: A basic course, volume 87. Springer, 2003

    2003

  37. [45]

    and Spokoiny, V

    Nesterov, Y. and Spokoiny, V. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, pp.\ 527--566, 2017

    2017

  38. [46]

    Nesterov, Y. et al. Lectures on convex optimization, volume 137. Springer, 2018

    2018

  39. [47]

    Linear convergence of stochastic iterative greedy algorithms with sparse constraints

    Nguyen, N., Needell, D., and Woolf, T. Linear convergence of stochastic iterative greedy algorithms with sparse constraints. IEEE Transactions on Information Theory, 63: 0 6869--6895, 2017

    2017

  40. [48]

    Zeroth-order random subspace algorithm for non-smooth convex optimization

    Nozawa, R., Poirion, P.-L., and Takeda, A. Zeroth-order random subspace algorithm for non-smooth convex optimization. arXiv preprint arXiv:2401.13944, 2024

    2024 arXiv

  41. [49]

    A convergent iterative hard thresholding for nonnegative sparsity optimization

    Pan, L., Zhou, S., Xiu, N., and Qi, H.-D. A convergent iterative hard thresholding for nonnegative sparsity optimization. Pacific Journal of Optimization, 13: 0 325--353, 2017

    2017

  42. [50]

    Ac/dc: Alternating compressed/decompressed training of deep neural networks

    Peste, A., Iofinova, E., Vladu, A., and Alistarh, D. Ac/dc: Alternating compressed/decompressed training of deep neural networks. Advances in Neural Information Processing Systems, 34: 0 8557--8570, 2021

    2021

  43. [51]

    and Li, P

    Shen, J. and Li, P. A tight bound of hard thresholding. Journal of Machine Learning Research, 18: 0 7650--7691, 2017

    2017

  44. [52]

    Sparse stochastic zeroth-order optimization with an application to bandit structured prediction

    Sokolov, A., Hitschler, J., Ohta, M., and Riezler, S. Sparse stochastic zeroth-order optimization with an application to bandit structured prediction. arXiv preprint arXiv:1806.04458, 2018

    2018 arXiv

  45. [53]

    Simultaneous pursuit of out-of-sample performance and sparsity in index tracking portfolios

    Takeda, A., Niranjan, M., Gotoh, J.-y., and Kawahara, Y. Simultaneous pursuit of out-of-sample performance and sparsity in index tracking portfolios. Computational Management Science, 10: 0 21--49, 2013

    2013

  46. [54]

    J., Jordan, M

    Wainwright, M. J., Jordan, M. I., et al. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1: 0 1--305, 2008

    2008

  47. [55]

    Stochastic zeroth-order optimization in high dimensions

    Wang, Y., Du, S., Balakrishnan, S., and Singh, A. Stochastic zeroth-order optimization in high dimensions. In International Conference on Artificial Intelligence and Statistics, pp.\ 1356--1365, 2018

    2018

  48. [56]

    Non-asymptotic analysis of stochastic methods for non-smooth non-convex regularized problems

    Xu, Y., Jin, R., and Yang, T. Non-asymptotic analysis of stochastic methods for non-smooth non-convex regularized problems. Advances in Neural Information Processing Systems, 32, 2019 a

    2019

  49. [57]

    Stochastic optimization for dc functions and non-smooth non-convex regularizers with non-asymptotic convergence

    Xu, Y., Qi, Q., Lin, Q., Jin, R., and Yang, T. Stochastic optimization for dc functions and non-smooth non-convex regularizers with non-asymptotic convergence. In International Conference on Machine Learning, pp.\ 6942--6951, 2019 b

    2019

  50. [58]

    and Li, P

    Yang, Y. and Li, P. Projective proximal gradient descent for a class of nonconvex nonsmooth optimization problems: Fast convergence without kurdyka-lojasiewicz (kl) property. arXiv preprint arXiv:2304.10499, 2023

    2023 arXiv

  51. [59]

    and Yu, J

    Yang, Y. and Yu, J. Fast proximal gradient descent for a class of non-convex and non-smooth sparse learning problems. In Uncertainty in Artificial Intelligence, pp.\ 1253--1262, 2020

    2020

  52. [60]

    Gradient hard thresholding pursuit

    Yuan, X.-T., Li, P., and Zhang, T. Gradient hard thresholding pursuit. Journal of Machine Learning Research, 18: 0 6027--6069, 2017

    2017

  53. [61]

    Zeroth-order optimization with weak dimension dependency

    Yue, P., Yang, L., Fang, C., and Lin, Z. Zeroth-order optimization with weak dimension dependency. In The Thirty Sixth Annual Conference on Learning Theory, pp.\ 4429--4472. PMLR, 2023

    2023

  54. [62]

    Desirable companion for vertical federated learning: New zeroth-order gradient based algorithm

    Zhang, Q., Gu, B., Dang, Z., Deng, C., and Huang, H. Desirable companion for vertical federated learning: New zeroth-order gradient based algorithm. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp.\ 2598--2607, 2021

    2021

  55. [63]

    Efficient stochastic gradient hard thresholding

    Zhou, P., Yuan, X., and Feng, J. Efficient stochastic gradient hard thresholding. Advances in Neural Information Processing Systems, 31, 2018

    2018

  56. [64]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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