Pith. sign in

REVIEW 2 major objections 6 minor 25 references

Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints

T0 review · 2 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read The Stochastic Halfspace Approximation Method projects each iterate onto a random linear halfspace approximation of one nonsmooth constraint, and its unified analysis yields O(1/√k) rates for convex objectives and O(1/k) for strongly…

desk verdict A genuine but incremental extension of stochastic halfspace methods; the optimality rates are sound, but the advertised feasibility rates rest on a linear regularity assumption that can fail, and the numerics overstate the case. read the letter →

arxiv 2412.02338 v1 pith:O7NLHPRI submitted 2024-12-03 math.OC

Nitesh Kumar Singh , Ion Necoara This is my paper · ORCID
classification math.OC MSC 90C2590C1565K05
keywords convexoptimizationnonsmoothfunctionalconstraintsstochasticgradientmethodhalfspaceapproximationrandomprojectionlinearregularityconvergenceratesstrongly
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 proposes SHAM, a stochastic algorithm for minimizing a smooth convex function over a set defined by many nonsmooth convex constraints. At each step SHAM takes a gradient step, projects the result onto the simple set Y, then projects onto a halfspace that linearizes one randomly chosen constraint at any point on the segment between the current iterate and the projected point. The central claim is a unified convergence analysis: for any such choice of linearization point, the averaged iterates have expected optimality gap and expected squared feasibility violation of order O(1/√k) when f is convex, and O(1/k) when f is strongly convex. If correct, these are the best known rates for stochastic subgradient methods, and one analysis covers infinitely many algorithmic variants, including the two extremes where the halfspace is built at the current iterate or at the projected point. The practical interest is that per iteration only one constraint is touched, so the method scales to problems with very many constraints and no easy full projections.

What carries the argument

The load-bearing object is the random halfspace L(h_j; \tilde x; Δ) = { y : h_j(\tilde x) + ⟨Δ, y-\tilde x⟩ ≤ 0 }, the linearization of a single constraint at \tilde x_k, together with the relaxed projection z_k = v_k - β (l_{h_j}(v_k;\tilde x_k))_+ / ‖Δ‖^2 Δ. The chain that carries the argument is: Lemma 2.4 converts the linear-regularity inequality dist(x,X) ≤ c max_j [h_j(x)]_+ into a bound on dist(x,X) in terms of the distance from x to the best linearization halfspace; Lemma 4.2 turns the expected squared distance from v_k to the random halfspace into a bound on $dist^{2}$(\tilde x_k, X); Lemma 4.4 feeds this into the main recurrence, which couples the contraction of ‖x_k - \bar x_k‖^2, the optimality gap f(x_{k+1}) - f(\bar x_k), and the feasibility term $dist^{2}$(x_{k+1}, X). The parameter γ controls where the halfspace is anchored and enters only through the constant $B^{2}$, so the proof handles all γ ∈ [0,1] simultaneously.

What would settle it

Compute the linear-regularity ratio for the feasible set X = {(x,y): $x^{4}$ - y ≤ 0, y ≤ 0} on Y = [-1,1]^2, whose only feasible point is (0,0). At (t,0), max_j [h_j]_+ = $t^{4}$ while dist((t,0),X) = |t|, so the ratio |t|/$t^{4}$ = 1/|t|^3 is unbounded and no finite c satisfies (6); all other assumptions (bounded subgradients, smooth convex objective) can be met. Running SHAM on this two-constraint problem with the stated α_k and β and checking whether E[$dist^{2}$(\hat x_k,X)] still decays as O(1/√k) would show whether linear regularity is a proof artifact or a genuine requirement.

Watch

Extended reading notes

Core claim

SHAM is the update x_{k+1} = Proj_Y((1-β)v_k + β Proj_{L_{j_k}}(v_k)), where v_k = Proj_Y(x_k - α_k ∇f(x_k)) and L_{j_k} is the halfspace { y : h_{j_k}(\tilde x_k) + ⟨Δ, y - \tilde x_k⟩ ≤ 0 } with \tilde x_k = γ v_k + (1-γ)x_k and Δ ∈ ∂h_{j_k}(\tilde x_k). The paper proves, under bounded subgradients, linear regularity, and a positive uniform sampling probability, that the expected squared distance to the optimal set obeys the recurrence (19). Summing this recurrence yields, for the weighted averages \hat x_k, E[f(\hat x_k)-f(\hat x^*_k)] = O(1/√k) and E[$dist^{2}$(\hat x_k, X)] = O(1/√k) in the convex case, and O(1/k) for both criteria in the strongly convex case, with explicit constants depending on c, B_h, ρ, m, L_f, and μ. The novelty is that the linearization point \tilde x_k may be any convex combination of x_k and v_k, so the result unifies and extends earlier algorithms that fixed \tilde x_k = v_k.

Load-bearing premise

The load-bearing premise is that the distance to the feasible set can be bounded by a fixed constant times the largest constraint violation (Assumption 2.3); if this linear regularity fails, the chain from halfspace errors to feasibility distances breaks and the stated rates do not follow.

Editorial extensions

If this is right

  • Both extremes γ=0 (\tilde x_k = x_k) and γ=1 (\tilde x_k = v_k) carry the same worst-case rates, so a practitioner can choose the cheaper or more stable anchor without sacrificing the O(1/√k) or O(1/k) guarantee.
  • For a strongly convex objective, the switching stepsize \alpha_k = min(1/L_f, 2/(μ(k+1))) is fully specified after k0 = floor(2L_f/μ - 1), so the algorithm needs no stepsize tuning beyond the Lipschitz and strong-convexity constants.
  • The per-iteration cost is one gradient evaluation, one projection onto Y, and one halfspace projection for a single constraint, independent of m; the feasibility guarantee is nevertheless for the full constraint set X = Y ∩ ⋂_j X_j.
  • Feasibility violation at the average point is controlled by the same sum that bounds the optimality gap, so both quality measures improve in lockstep at the same rate.
  • Under the α_k = α_0/√k choice the logarithmic factor disappears from the leading term, giving clean O(1/√k) rates for convex f.

Reading between the lines

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

  • The unified treatment of γ ∈ [0,1] suggests an intermediate γ might be tuned to balance the cheaper anchor \tilde x_k = x_k against the more robust anchor \tilde x_k = v_k observed in the numerical experiments; the theory does not single out an optimal γ.
  • Because c appears squared in the feasibility rate, constraint sets with a large linear-regularity constant will require many more iterations; estimating c (or a Slater constant) before running the algorithm could guide the choice of β and the stopping criterion.
  • The rates hold for weighted average points, not the last iterate; deriving last-iterate or high-probability guarantees would require additional machinery and is not addressed.
  • For finite-sum objectives, pairing the halfspace projection with variance-reduced gradient estimators (as in the reference [25] does for a similar method) may remove the logarithmic factor, but SHAM's analysis does not cover variance reduction.
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

2 major / 6 minor

Summary. The paper considers problem (1): minimize a smooth convex or strongly convex objective f over a simple set Y subject to convex, possibly nonsmooth functional constraints h_j(x) <= 0. It introduces Stochastic Halfspace Approximation Method (SHAM), Algorithm 1, in which each iteration performs a gradient step on f, projects onto Y, and then moves the iterate toward the projection of v_k onto a random halfspace approximation of one constraint. The linearization point is chosen as tilde x_k = gamma v_k + (1-gamma) x_k for gamma in [0,1], which unifies several previously studied and new strategies. Section IV proves a general recurrence (Theorem 4.5) and then derives rates O(1/sqrt(k)) for convex f and O(1/k) for strongly convex f, for both optimality gap and squared feasibility violation at weighted average points. Section V reports CPU-time comparisons with CVX on SOC-constrained quadratic problems.

Significance. If the results are correct, the main contribution is a unified convergence analysis for infinitely many halfspace linearization strategies, including the previously studied tilde x_k = v_k and the new tilde x_k = x_k, with state-of-the-art rates and no fitted constants in the proof. The derivation is first-principles given the explicit Assumptions 2.1-2.3 and 3.1, and the main recurrence (19) is internally consistent. The numerical experiments illustrate the algorithm on nontrivial second-order cone problems. The principal caveat is that the feasibility rates are proved only under the linear regularity condition (6), a restriction that is not advertised in the abstract or introduction.

major comments (2)
  1. [Section II, Assumption 2.3; Lemmas 2.4 and 4.2; Theorems 4.6-4.8] The feasibility-rate claims are conditional on the linear regularity assumption (6), and this restriction should be stated in the abstract and introduction. Equation (6) is used in Lemma 2.4 to convert halfspace-projection distance into dist(x,X), and that lemma enters Lemma 4.2, Lemma 4.4, and hence the main recurrence (19). The assumption is not implied by the other assumptions: take Y=[-1,1], h(x)=x^2, and X={0}; then dist(x,X)=|x| while max_j[h_j(x)]_+ = x^2, so no finite c satisfies (6). The sufficient conditions mentioned in the text (nonempty interior or polyhedrality) do not cover this example. As written, the paper's title and abstract suggest the rates hold for the general class of convex nonsmooth functional constraints, but the proof does not establish that. Please either qualify the claims or discuss whether a weaker error-bound condition can replace (6).
  2. [Appendix, proof of Lemma 4.2] The key inequality E[||tilde x_k - Pi_{L_{j_k}}(tilde x_k)||^2 | F[k]] >= (rho/m) min_Delta dist^2(tilde x_k, L(h_j; tilde x_k; Delta)) is imported without proof from Lemma 4 of [25]. This step is load-bearing: it is exactly how Lemma 2.4 is combined with Assumption 3.1 to produce the expected halfspace-projection bound used in the recurrence (19). The paper claims 'distinct proofs under basic assumptions,' so the needed lemma should be stated and proved in the appendix. Under Assumption 2.2 it can be proved directly from dist(x, L(h;x;g)) = (h(x))_+/||g|| for g != 0, and the derivation should be included for self-containedness.
minor comments (6)
  1. [Equation (1)] The notation x in Y in R^n should read x in Y subseteq R^n; the current expression 'x in Y in R^n' appears to be a typo.
  2. [Lemma 4.4] Lemma 4.4 is stated as holding 'under the assumption of Lemma 4.2 with beta in (0,2)', but Lemma 4.2 contains no beta; the beta condition belongs to Lemma 4.3. Please correct the cross-reference.
  3. [Theorem 4.8 and abstract] The displayed feasibility bound in Theorem 4.8 is O(1/(k^2 + k k0 + k0^2)), which is O(1/k^2) asymptotically, while the text after the theorem and the abstract state the strongly convex rates as O(1/k). The stronger statement should be presented consistently.
  4. [Section V, Table I] The sentence that SHAM 'consistently outperforms CVX by a factor ranging from 3 to 10' is not supported by the first row of Table I, where CVX times (2.4 and 1.9 seconds) are below the SHAM averages (about 11-13 seconds). Please qualify the claim as applying to larger instances or revise the wording.
  5. [Section IV-A, Choice (1)] The bound sum_{t=1}^{k+1} alpha_t^2 <= alpha_0^2/ln(3) for alpha_t = alpha_0/(sqrt(t+2) ln(t+2)) appears too strong; the infinite sum is numerically larger than 1/ln(3). Since only the order O(alpha_0^2) is needed for the stated rate, this does not change the conclusion, but the inequality should be corrected.
  6. [Theorems 4.6 and 4.8] The rate constants involve c^2, B_h^2, and 1/rho, which are generally unknown; a brief discussion of the practical meaning of these constants for finite k would be helpful for users of the algorithm.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence rates are derived from explicitly stated assumptions, and the cited lemmas are proved in the appendix or borrowed from external work, not from the paper's own conclusions.

full rationale

The derivation chain is self-contained given Assumptions 2.1–2.3 and 3.1. The main recurrence (19) is obtained by summing the descent inequality from Lemma 4.1, the halfspace projection bound from Lemma 4.2, the feasibility contraction from Lemma 4.3, and the conditional expectation bound from Lemma 4.4; each of these lemmas is proved in the appendix. Lemma 2.4, which converts the linear regularity condition (Assumption 2.3) into a bound involving distances to halfspaces, is proved directly from (6) and the bounded subgradient condition (Assumption 2.2), with the proof noting that it follows similarly to Proposition 1(ii) of the external reference [25]. Lemma 4.2 similarly follows from Lemma 4 of [25], which is not authored by the present authors. No fitted constants are introduced and then renamed as predictions: the constants c, B_h, ρ, m, L_f, and μ are assumption parameters, and the rates in Theorems 4.6 and 4.8 are explicit consequences of summing (19) with the chosen stepsize sequences. The self-citations to [9], [11], [12], [13], and [19] are contextual comparisons or standard projection inequalities, and none is used as the sole justification for a central claim. The skeptical concern that Assumption 2.3 can fail for tangential constraints such as h(x)=x^2 is a legitimate scope limitation, but it is a correctness/assumption caveat, not circularity: the theorem explicitly conditions on (6), and no step of the proof reduces the claimed rate to the assumption by definition.

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

The central claim rests on standard convex-analysis assumptions and one critical error-bound condition (Assumption 2.3), plus a cited lemma from [25]. No fitted parameters or invented entities are introduced; the rates depend only on problem data and user-chosen algorithm constants beta, gamma, and step sizes.

assumptions (6)
  • domain assumption f is Lf-smooth and mu-strongly convex (Assumption 2.1).
    Used in Lemma 4.1 and Theorem 4.5 to establish the descent property for the objective.
  • domain assumption Constraint functions hj are convex and have bounded subgradients: ||Delta|| <= Bh (Assumption 2.2).
    Used in Lemma 2.4 and in the rates to control the halfspace projection steps.
  • domain assumption Linear regularity / error bound: dist(x,X) <= c max_j [hj(x)]_+ for all x in Y (Assumption 2.3).
    Critical in Lemma 2.4 to connect constraint violation to distance to the feasible set; can fail for general convex constraint sets.
  • domain assumption Sampling distribution satisfies P(j_k = j | F_k) >= rho/m for all j (Assumption 3.1).
    Needed to lower-bound the expected progress from sampling a constraint in Lemma 4.2 and Theorem 4.5.
  • domain assumption Gradient norms are bounded along iterates: ||grad f(x_k)|| <= Bf (equation 14).
    Used to control the stepsize terms in the recurrence; guaranteed when Y is bounded, which is assumed in the numerics.
  • domain assumption Lemma 4 of [25], which lower-bounds the expected squared distance to a sampled halfspace.
    Invoked without proof in Lemma 4.2; it is an external established result that the paper relies on.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints." pith.science (2026). https://pith.science/paper/O7NLHPRI

@misc{pith2026241202338,
  author       = {Pith},
  title        = {Pith review of: Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O7NLHPRI}},
  note         = {Machine review of arXiv:2412.02338}
}
abstract

In this work, we consider convex optimization problems with smooth objective function and nonsmooth functional constraints. We propose a new stochastic gradient algorithm, called Stochastic Halfspace Approximation Method (SHAM), to solve this problem, where at each iteration we first take a gradient step for the objective function and then we perform a projection step onto one halfspace approximation of a randomly chosen constraint. We propose various strategies to create this stochastic halfspace approximation and we provide a unified convergence analysis that yields new convergence rates for SHAM algorithm in both optimality and feasibility criteria evaluated at some average point. In particular, we derive convergence rates of order $\mathcal{O} (1/\sqrt{k})$, when the objective function is only convex, and $\mathcal{O} (1/k)$ when the objective function is strongly convex. The efficiency of SHAM is illustrated through detailed numerical simulations.

Figures

Figures reproduced from arXiv: 2412.02338 by the authors.

Figure 1
Figure 1. Behaviour of SHAM in terms of optimality (left) and feasibility (right) running two times (top and bottom) on the same problem with n = 100, m = 100, µ = 0, and two choices for x˜k. TABLE I PERFORMANCE OF SHAM VERSUS CVX. Data-size SHAM CVX x˜k = xk x˜k = vk µ = 0 µ > 0 µ = 0 µ > 0 µ = 0 µ > 0 n = 102 m = 102 8.4 11.3 13.8 4.5 11.6 18.4 11.2 12.3 13.2 4.7 10.8 17.7 2.4 1.9 n = 102 m = 103 75.3 86.4 102.4 75.3 105.9 … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 24 canonical work pages

  1. [11]

    Necoara and N.K

    I. Necoara and N.K. Singh, ”Stochastic subgradient for comp osite convex optimization with functional constraints,” Journal of Machine Learning Research, vol. 23, no. 265, 1–35, 2022

    work page 2022

  2. [19]

    Singh, I

    N.K. Singh, I. Necoara and V . Kungurtsev, ”Mini-batch stoch astic subgradient for functional constrained optimization,” Optimization, 1–27, 2023, doi: 10.1080/02331934.2023.2189015

    arXiv 2023

  3. [25]

    Y ang, F

    Z. Y ang, F. Xia, K. Tu and M. Y ue, ”V ariance reduced random relaxed projection method for constrained finite-sum minim ization problems”, IEEE Transactions on Signal Processing , vol. 54, 2188- 2203, 2024

    work page 2024

  4. [1]

    Berthier, J

    E. Berthier, J. Carpentier, A. Rudi and F. Bach, ”Infinite-Di mensional Sums-of-Squares for Optimal Control”, Conference on Decision and Control, 577-582, 2022

    work page 2022

  5. [2]

    Bhattacharyya, L.R

    C. Bhattacharyya, L.R. Grate, M.I. Jordan, L. El Ghaoui and S . Mian, ”Robust sparse hyperplane classifiers: application t o uncertain molecular profiling data,” Journal of Computational Biology, vol. 11, no. 6, 1073-1089, 2004

    work page 2004

  6. [3]

    S. Boyd, C. Crusius and A. Hansson, ”Control applications of nonlinear convex programming,” Journal of Process Control , vol. 8, no. 5-6, 313-324, 1998

    work page 1998

  7. [4]

    D. Boob, Q. Deng and G. Lan, ”Stochastic first-order methods for convex and nonconvex functional constrained optimizat ion”, Mathematical Programming, vol. 197, 215–279, 2023

    work page 2023

  8. [5]

    Gower, L

    R. Gower, L. Nicolas, Q. Xun, S. Alibek, S. Egor and P . Richtar ik, ”SGD: general analysis and improved rates,” International Confer- ence on Machine Learning , 5200-5209, 2019

    work page 2019

Show all 25 references
  1. [6]

    Grant and S

    M. Grant and S. Boyd, ”CVX: Matlab software for disciplined convex programming, version 2.0 beta,” http://cvxr .com/cvx, 2013

    2013

  2. [7]

    M.S. Lobo, L. V andenberghe, S. Boyd and H. Lebret, ”Applicat ions of second-order cone programming,” Linear Algebra and its Appli- cations, vol. 284, 193-228, 1998

    1998

  3. [8]

    Lewis and J.S

    A. Lewis and J.S. Pang, Error bounds for convex inequality systems , Generalized Convexity, Generalized Monotonicity (J.-P . C rouzeix, J.-E.Martinez-Legaz, and M. V olle, eds.), 75–110, Cambrid ge Uni- versity Press, 1998

    1998

  4. [9]

    Nedich, ”Random algorithms for convex minimization prob lems,” Mathematical Programming, vol

    A. Nedich, ”Random algorithms for convex minimization prob lems,” Mathematical Programming, vol. 129, no. 2, 225–273, 2011

    2011

  5. [10]

    Necoara, ”General convergence analysis of stochastic fir st order methods for composite optimization,” Journal of Optimization The- ory and Applications , vol

    I. Necoara, ”General convergence analysis of stochastic fir st order methods for composite optimization,” Journal of Optimization The- ory and Applications , vol. 189, 66-95, 2021

    2021

  6. [12]

    Necoara and A

    I. Necoara and A. Nedich, ”Minibatch stochastic subgradien t-based projection algorithms for feasibility problems with conve x inequal- ities,” Computational Optimization and Applications , vol. 80, 121- 152, 2021

    2021

  7. [13]

    Nedelcu, I

    V . Nedelcu, I. Necoara and Q. Tran Dinh, ”Computational comp lex- ity of inexact gradient augmented Lagrangian methods: appl ication to constrained MPC”, SIAM Journal of Control and Optimization , vol. 52, no. 5, 3109–3134, 2014

    2014

  8. [14]

    Nesterov, ”Lectures on Convex Optimization,” Springer Opti- mization and Its Applications , vol

    Y u. Nesterov, ”Lectures on Convex Optimization,” Springer Opti- mization and Its Applications , vol. 137, 2018

    2018

  9. [15]

    Polyak, ”Minimization of unsmooth functionals,” USSR Com- putational Mathematics and Mathematical Physics , vol

    B.T. Polyak, ”Minimization of unsmooth functionals,” USSR Com- putational Mathematics and Mathematical Physics , vol. 9, no. 3, 14-29, 1969

    1969

  10. [16]

    Polyak, ”Random algorithms for solving convex inequal ities,” Studies in Computational Mathematics , vol

    B.T. Polyak, ”Random algorithms for solving convex inequal ities,” Studies in Computational Mathematics , vol. 8, 409-422, 2001

    2001

  11. [17]

    Rockafellar and S.P

    R.T. Rockafellar and S.P . Uryasev, ”Optimization of condit ional value-at-risk,” Journal of Risk , vol. 2, 21-41, 2000

    2000

  12. [18]

    Sidiropoulos, T.N

    N.D. Sidiropoulos, T.N. Davidson and Z.-Q. Luo, ”Transmit b eam- forming for physical-layer multicasting,” IEEE Transactions on Signal Processing, vol. 54, no. 6, 2239–2251, 2006

    2006

  13. [20]

    Tibshirani, ”The solution path of the generalized lasso, ” Phd Thesis, Stanford University, 2011

    R. Tibshirani, ”The solution path of the generalized lasso, ” Phd Thesis, Stanford University, 2011

    2011

  14. [21]

    V apnik, ”Statistical learning theory,” John Wiley, 1998

    V . V apnik, ”Statistical learning theory,” John Wiley, 1998

    1998

  15. [22]

    Wang and D.P

    M. Wang and D.P . Bertsekas, ”Stochastic first-order methods with random constraint projection,” SIAM Journal on Optimization , vol. 26, no. 1, 681–717, 2016

    2016

  16. [23]

    Wei, ”Tutorials on advanced optimization methods,” arXiv:2007.13545, 2020

    W. Wei, ”Tutorials on advanced optimization methods,” arXiv:2007.13545, 2020

    2007 arXiv

  17. [24]

    Xu, ”Primal-dual stochastic gradient method for convex p rograms with many functional constraints,” SIAM Journal on Optimization , vol

    Y . Xu, ”Primal-dual stochastic gradient method for convex p rograms with many functional constraints,” SIAM Journal on Optimization , vol. 30, no. 2, 1664–1692, 2020

    2020

Pith tools

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