acceptodds
Under review as a conference paper at ICLR 2027

Constrained Nonconvex Stochastic Optimization with One Projection

Abstract

Constrained nonconvex optimization has seen increasing application in modern machine learning, such as safe LLM alignment/finetuning, transfer learning and rank-constrained continual learning. Projection onto a functional constraint can cost substantially more than a stochastic first-order update. We study whether this operation can be deferred until the end of nonconvex stochastic optimization. For weakly convex, possibly nonsmooth objectives and regular convex constraints, we give a penalized proximal method that uses stochastic subgradients and one projection onto the constraint set. The returned point is exactly feasible and has a small Moreau-envelope stationarity measure; for smooth objectives, the same algorithm controls the projected-gradient mapping. For smooth nonconvex constraints, we assume a global lower bound on the infeasible constraint slope which permits arbitrary, possibly infeasible initialization. An exact-penalty variant attains the same stochastic-oracle order and returns an exactly feasible point within of an -KKT point. All intermediate updates use only projections onto a simple Euclidean ball. These are oracle-complexity guarantees: the cost of the single terminal projection is separate, and no efficient projection algorithm for a general nonconvex set is assumed to follow from regularity.

Primary area:
optimization
Keywords:
stochastic optimization, constrained optimization, nonconvex optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_znDEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies stochastic optimization of nonconvex (weakly convex, possibly nonsmooth) objectives under functional constraints, with the goal of avoiding the per-iteration projections required by Projected SGD. The proposed Penalized Proximal Subgradient Method approximately solves a sequence of strongly convex penalized proximal subproblems over a simple Euclidean ball, allows all intermediate iterates to be infeasible, and performs exactly one projection onto the feasible set at the end. For convex constraints with a boundary gradient lower bound, the method returns an exactly feasible point with an ϵ\epsilon-small projected-gradient mapping (smooth case) or Moreau-envelope residual (nonsmooth case) using O~(ϵ−4)\widetilde{O}(\epsilon^{-4}) stochastic subgradients. For smooth nonconvex constraints, under a global infeasible-slope condition, an exact-penalty variant returns a feasible point within O(ϵ)O(\epsilon) of an ϵ\epsilon-KKT point at the same oracle complexity. Experiments on transfer learning and classification with abstention show large runtime savings over Projected SGD at comparable accuracy.

Critical strengths
  • Wide setting. The framework covers both convex and nonconvex functional constraints, as well as smooth and nonsmooth weakly convex objectives, within a single algorithmic template. The nonconvex-constraint result additionally permits arbitrary, possibly infeasible initialization, which is rare in this literature.
  • Complete results. For each setting the paper provides an appropriate stationarity certificate (projected-gradient mapping, Moreau-envelope residual, or nearby ϵ\epsilon-KKT witness), exact feasibility of the output, and an O~(ϵ−4)\widetilde{O}(\epsilon^{-4}) oracle complexity matching the standard rate for unconstrained weakly convex stochastic optimization — all while using a single terminal projection. The analysis is self-contained, the role of each assumption is clearly delineated, and a counterexample (Appendix C.5) justifies the global slope condition.
Critical weaknesses
  • Constant success probability. The stationarity guarantees (e.g., Theorems 3.3 and 3.5 in the convex-constrained setting) hold only with probability at least 2/32/3, which is impractical as stated. The paper does not discuss how to boost this to high probability 1−δ1-\delta (e.g., by independent restarts), what the resulting cost would be, or whether a post-hoc verification step is even available given that the stationarity measures are not computed by the algorithm.
  • Vague motivation relative to projection-free alternatives. The paper motivates the method by the fact that Projected SGD needs a projection at every iteration. However, there are well-established methods for constrained optimization that avoid projections entirely, e.g., augmented Lagrangian methods, as well as other primal-dual and penalty schemes. The paper does not compare with such methods, either theoretically or empirically — notably, the authors themselves use an augmented-Lagrangian solver to implement the terminal projection in the experiments, which makes the omission more conspicuous. How does the proposed method compare with these alternatives?
  • No equality constraints. While the paper considers nonlinear inequality-constrained programming, it does not consider (non)linear equality constraints, which are common in practice. It is unclear whether the proposed method can be applied in that setting: the error-bound and slope conditions are formulated for inequality constraints, and an equality constraint h(x)=0h(x)=0 written as two inequalities would violate the Slater-type margin structure. A discussion of this limitation and possible extensions is needed.
Questions for authors
  1. In Algorithm 1, line 6, the algorithm returns x^∈PC(xJ)\hat{x} \in \mathcal{P}_{\mathcal{C}}(x_J), but x^\hat{x} does not appear to be used anywhere afterwards. Is this the intended final output of the whole algorithm, and is the notation simply confusing, or is something else intended?
  2. Assumption 3.1 assumes a feasible point x0∈Cx_0 \in \mathcal{C} is supplied. How should one obtain such a point in practice? Does finding it require solving a feasibility problem whose cost could be comparable to the projections the method is trying to avoid?
  3. For a nonconvex constraint set C\mathcal{C}, projecting a point onto it is hard in general (possibly NP-hard). How do you compute the single terminal projection onto a nonconvex constraint in your proposed method? Theorem 3.8 assumes an exact nearest-point oracle; what should a practitioner use, and how do the guarantees degrade if the projection is only approximate (as in your own neural-network experiments)?
  4. In both settings (convex and nonconvex constraints), the convergence rates are the same O~(ϵ−4)\widetilde{O}(\epsilon^{-4}). This is not intuitive, since the nonconvex setting seems substantially harder. How should one understand this? Is the difficulty entirely absorbed into the constants (e.g., the margin σout\sigma_{\mathrm{out}}, penalty λ\lambda, and curvature β\beta) and the stronger Assumption 3.7, or is there a regime where the nonconvex setting provably costs more?
  5. Why do you restrict each subproblem to a ball B\mathcal{B} in the algorithm? Is there any intuition? Is the ball needed only for boundedness of the iterates and subgradients in the analysis, or does it play a more essential role (e.g., in the normal-cone term of condition (13))? How sensitive is the method to the choice of its radius in practice?
1 comment

Thank you for your very constructive comments. We will address them below.

W1. Is the success probability limited to 2/32/3?

No. The confidence can be raised to 1−δ1-\delta in a single run. Replace the uniform output index by t∗∈arg⁡min⁡0≤t<T∥xt+1−xt∥t_*\in\arg\min_{0\le t<T}\|x_{t+1}-x_t\|. With failure budget δ/T\delta/T per inner solve, Lemma A.1 and a union bound give simultaneous inner error e=O((log⁡(K+1)+log⁡(T/δ))/K)e=O((\log(K+1)+\log(T/\delta))/K). The smallest squared step is at most the average; the pointwise residual bounds in Appendices B and C then bound the squared stationarity residual at the selected step by O(1/T+e)O(1/T+e) for e≤1e\le 1.

Thus, for fixed problem parameters, T=O(ϵ−2)T=O(\epsilon^{-2}) and K=O(ϵ−2log⁡(2/(ϵδ)))K=O(\epsilon^{-2}\log(2/(\epsilon\delta))) suffice. This costs TK=O(ϵ−4[log⁡(2/ϵ)+log⁡(1/δ)])TK=O\left(\epsilon^{-4}\left[\log(2/\epsilon)+\log(1/\delta)\right]\right) stochastic objective-oracle calls and one terminal projection: project xt∗+1x_{t_*+1} for convex constraints or xt∗x_{t_*} for nonconvex constraints. No restart or stationarity check is needed.

W2. What does the comparison with PSGD establish relative to augmented Lagrangians?

PSGD is the comparison for the cost of enforcing feasibility after every update. Our augmented-Lagrangian solver is used only to minimize distance to the selected iterate; running it on the original training loss would be a different baseline. The reported speedup is relative to PSGD. A direct comparison with primal–dual or augmented-Lagrangian training should match final feasibility and objective quality.

W3. Does the analysis extend to equalities?

For linear equality constraint Ax−b=0Ax-b=0, our algorithm can still work. But for general nonconvex equality g(x)=0g(x)=0, current analysis does not apply.

Q1 / Q3. What is the final output, and what if one use an approximate projection?

What Line 6 returns is the final output x^∈PC(xJ)\hat x\in P_{\mathcal C}(x_J).

The theorem counts one exact nearest-point call and accounts for its cost separately. There is also a useful bound for a feasible approximate answer zz: if ∥z−xJ∥≤dist(xJ,C)+η\|z-x_J\|\leq\mathrm{dist}(x_J,\mathcal C)+\eta, then on the theorem's success event ∥z−y∥≤2ϵ/β+η\|z-y\|\leq 2\epsilon/\beta+\eta for the same ϵ\epsilon-KKT witness yy. This follows by the triangle inequality since ∥xJ−y∥≤ϵ/β\|x_J-y\|\leq\epsilon/\beta. The neural-network solver does not certify this distance tolerance; a small violation alone does not imply it.

Q2. Regarding initial feasibility assumption in convex constraint setting

Indeed the requirement for initial feasible point can be removed in convex constraint setting as well. Let x0∈Bx_0\in\mathcal B be arbitrary and write dt=dist⁡(xt,C)d_t=\operatorname{dist}(x_t,\mathcal C). The convex inner lemma already holds for any center in the ball, so dt≤e/GFd_t\le e/G_F for every t≥1t\ge1 on the inner accuracy event. The outer descent proof uses d0=0d_0=0 only when summing over steps. Keeping the first term replaces the initial gap Δf\Delta_f by Δf+Gfd0+ℓd02\Delta_f+G_f d_0+\ell d_0^2. Since the unit ball has diameter two, 2Gf+4ℓ2G_f+4\ell bounds the extra term without computing d0d_0. Both convex theorems therefore retain their stationarity measures, O~(ϵ−4)\widetilde O(\epsilon^{-4}) oracle complexity, and one final projection; no initial feasibility solve is needed.

Q4. Why do convex and nonconvex constraints give the same oracle-rate exponent?

Both bounds count stochastic objective-subgradient calls. In each setting, O(ϵ−2)O(\epsilon^{-2}) outer steps suffice, and solving each strongly convex subproblem to objective error O(ϵ2)O(\epsilon^2) takes O~(ϵ−2)\widetilde O(\epsilon^{-2}) calls. Their product gives the same O~(ϵ−4)\widetilde O(\epsilon^{-4}) dependence for fixed problem parameters. Nonconvex constraints can still cost more: a smaller infeasible slope requires a larger penalty to rule out infeasible stationary points, and stronger constraint curvature requires more proximal regularization to keep the subproblems strongly convex. The cost of computing the final projection is separate from this oracle bound.

Q5. Why use a ball?

Projecting onto the ball B\mathcal B is cheap: an inner step that leaves it is simply rescaled to its boundary. This keeps the iterates bounded while allowing them to violate the original constraint. The ball also determines which starting points Theorem 3.8 covers. At every infeasible point in the ball there must be a direction that stays in the ball and decreases the violation at a uniformly positive rate. This is why the normal cone of B\mathcal B appears in (13): at the boundary, a direction pointing out of the ball cannot be used. The radius must be large enough to contain the feasible set in its interior, but enlarging it can admit a point with g(x)>0g(x)>0 and ∇g(x)=0\nabla g(x)=0, where (13) fails. We have not measured sensitivity to the radius in our experiments.

Reviewer_GF9mOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers stochastic optimization of weakly convex, possibly nonsmooth objective functions under convex or nonconvex functional constraints. The authors propose a penalized proximal method in which each strongly convex subproblem is approximately solved using a stochastic subgradient method. Since projections onto general feasible sets can be computationally expensive, the proposed method performs only one projection onto the feasible set at the end of the algorithm. The authors establish stationarity guarantees for both convex and nonconvex constraints, with a stochastic oracle complexity of O~(ϵ−4)\widetilde{O}(\epsilon^{-4}) and a success probability of at least 2/32/3.

Critical strengths
  • The paper provides convergence analyses for both convex and nonconvex functional constraints. Although the stochastic oracle complexity does not improve upon existing rates, the proposed method achieves the same order of complexity while requiring only one projection onto the feasible set.

  • The numerical experiments demonstrate substantial reductions in computational time compared with projected SGD, mainly by avoiding expensive projections at every iteration.

Critical weaknesses

Limited theoretical novelty. The proposed method combines several well-established techniques, including one-projection methods, penalty methods, proximal-point methods, and stochastic subgradient methods. The resulting O~(ϵ−4)\widetilde{O}(\epsilon^{-4}) oracle complexity does not improve upon existing rates. Although the extension of the one-projection principle to nonconvex optimization is potentially useful, the paper does not sufficiently clarify which theoretical ingredients are genuinely new and which can be derived from existing analyses.

Insufficient comparison with existing methods. The related-work discussion does not adequately cover classical methods for nonconvex constrained optimization. Relevant examples include:

Auslender, A., Shefi, R., Teboulle, M.: A Moving Balls Approximation Method for a Class of Smooth Constrained Minimization Problems. SIAM Journal on Optimization 20, 3232–3259 (2010).

Drusvyatskiy, D., Paquette, C.: Efficiency of Minimizing Compositions of Convex Functions and Smooth Maps. Mathematical Programming 178, 503–558 (2019).

In particular, the moving balls approximation (MBA) method also handles nonconvex functional constraints through tractable subproblems, although its approach to maintaining feasibility differs from that of the proposed method. The prox-linear framework of Drusvyatskiy and Paquette is also closely related to exact-penalty formulations. A more detailed comparison with these methods and other existing penalty-based approaches is needed to establish the contribution of the proposed framework.

Restrictive assumptions for nonconvex constraints. Assumption 3.7 imposes a global infeasible-slope condition (13), requiring the constraint violation to have a uniformly nonvanishing slope throughout the infeasible region of B\mathcal B. This is a strong assumption that excludes infeasible stationary points and may rule out many practically relevant nonconvex feasible sets. As the authors themselves illustrate in Appendix C.5, even a smooth constraint defining a disconnected feasible set can violate this condition. It is unclear how broadly applicable the nonconvex convergence result is, or whether this assumption is satisfied in the numerical experiments.

Limited strength of the theoretical guarantees. The stationarity guarantees are established only with probability at least 2/32/3. Although constant-probability guarantees are common in stochastic optimization, this leaves a failure probability of up to 1/31/3, which is relatively large. The paper does not establish guarantees with an arbitrary confidence level 1−δ1-\delta, even though the inner stochastic subgradient method already admits a high-probability bound. Moreover, for nonconvex constraints, Theorem 3.8 guarantees the existence of an approximate KKT point near the output rather than a small KKT residual at the returned point itself.

Insufficient numerical comparison. The experiments mainly compare the proposed method with projected SGD. Since the primary computational advantage is the reduction in the number of expensive projections, comparisons with alternative methods that also avoid repeated projections onto the original feasible set would be more informative. For example, MBA, prox-linear methods, and existing penalty-based approaches are relevant alternatives. Without such comparisons, it is difficult to determine whether the proposed method offers a significant practical advantage beyond projected SGD.

Practical parameter selection and presentation. The theoretical parameter choices depend on problem-specific constants, including smoothness and constraint-regularity parameters, which may not be known in advance. Moreover, Assumption 3.1 requires a feasible initial point without explaining how such a point can be obtained efficiently. The presentation could also be improved: the differentiability requirements on the constraint function are not clearly stated in the Introduction, and some parameters and notation are introduced without sufficient explanation.

Questions for authors
  1. What are the genuinely new theoretical ingredients in the proposed method beyond combining existing one-projection, penalty, and proximal optimization techniques? In particular, could the authors provide a more detailed theoretical and, where appropriate, numerical comparison with the moving balls approximation method, prox-linear methods, and existing penalty-based approaches?

  2. Assumption 3.7 imposes the global infeasible-slope condition (13), which appears substantially stronger than standard constraint qualifications imposed only near the feasible boundary. Could the authors provide practically relevant classes of nonconvex constraints satisfying this assumption? In particular, is this condition satisfied by the nonconvex constraints used in the numerical experiments? Can the assumption be relaxed while retaining the convergence guarantees?

  3. The stationarity guarantees hold with probability at least 2/32/3. Since Lemma A.1 provides a high-probability bound for the inner solver, could the authors extend the main results to an arbitrary confidence level 1−δ1-\delta? For example, would selecting an outer iterate based on the smallest successive-iterate displacement, rather than uniformly at random, allow a high-probability guarantee with only logarithmic dependence on 1/δ1/\delta while preserving the one-projection property?

  4. The proposed method requires several problem-dependent parameters that may be unknown in practice. How should these parameters be selected or estimated without prior knowledge of the corresponding constants? Furthermore, Assumption 3.1 requires a feasible initial point x0∈Cx_0\in\mathcal C. How can such a point be obtained efficiently in the convex-constraint setting?

3 comments

Thank you for your very constructive comments. We will address them below.

Q1: Our Novelty and comparison with more references

Our question is whether a single final projection can recover exact feasibility without losing the O~(ϵ−4)\widetilde O(\epsilon^{-4}) stochastic-oracle rate. For convex constraints we bound the projected-gradient norm (smooth objectives) or constrained Moreau-envelope gradient (weakly convex objectives) at the returned feasible point. For nonconvex constraints, Theorem 3.8 allows an infeasible start and certifies that the returned point lies within 2ϵ/β2\epsilon/\beta of an ϵ\epsilon-KKT point.

MethodExactly feasible output?Feasible start required?
Moving balls (MBA)Yes; every iterateYes
Prox-linear on a penaltyNot guaranteedNo; only the simple domain
Stochastic exact penalty (Cui et al.)No; approximate in expectationNo
Ours (Theorem 3.8)Yes; one exact final projectionNo; any x0∈Bx_0\in\mathcal B

[Auslender, Shefi and Teboulle] keep every iterate feasible by solving over an inner approximation built from balls. Our inner steps use one fixed bounding ball, which may contain infeasible points. [Drusvyatskiy and Paquette] linearize the smooth map; applied to a penalty, their residual measures stationarity of that composite objective. [Cui et al.] allow stochastic equalities and bound E∥c(x)∥\mathbb E\|c(x)\| by ϵ\epsilon. For our deterministic inequality, the global slope condition turns a small penalty residual into a feasible KKT witness close to the final projection.

We will include this comparison table into the paper. Thanks for your suggestion and references.

Q2: High probability bound

We can provide a high probability bound. With the suggested smallest-step rule, the original stationarity guarantee holds with probability at least 1−δ1-\delta using O(ϵ−4[log⁡(2/ϵ)+log⁡(1/δ)])O(\epsilon^{-4}[\log(2/\epsilon)+\log(1/\delta)]) stochastic objective-oracle calls and one final projection, for fixed problem parameters and the same admissible ϵ\epsilon.

Two changes suffice. First, give each inner solve failure probability δ/T\delta/T. Lemma A.1 and a union bound give simultaneous inner error e=O((log⁡(K+1)+log⁡(T/δ))/K)e=O((\log(K+1)+\log(T/\delta))/K). Second, replace the uniform output index by the index tt minimizing ∥xt+1−xt∥\|x_{t+1}-x_t\|. Its squared step is at most the average bounded by outer descent. The pointwise bounds in Appendices B and C then give squared residual O(1/T+e)O(1/T+e) for e≤1e\le1. Choosing T=O(ϵ−2)T=O(\epsilon^{-2}) and K=O(ϵ−2log⁡(2/(ϵδ)))K=O(\epsilon^{-2}\log(2/(\epsilon\delta))) gives the claim. Project xt+1x_{t+1} for convex constraints or xtx_t for nonconvex constraints; neither restarts nor residual evaluations are needed.

Q3: Restrictive assumptions for nonconvex constraints

Assumption 3.7 is stronger than boundary regularity because an arbitrary start may be far from the boundary. A verifiable sufficient condition on the unit ball is x⊤∇g(x)≥c>0x^\top\nabla g(x)\ge c>0 wherever g(x)≥0g(x)\ge0, with the feasible set strictly inside the ball. For example, take g(u,v)=u2+v2+64u2v2−1/4g(u,v)=u^2+v^2+64u^2v^2-1/4. Its sublevel set is nonconvex: (1/2,0)(1/2,0) and (0,1/2)(0,1/2) are feasible, but at their midpoint g=1/8g=1/8. Writing x=(u,v)x=(u,v) gives x⊤∇g(x)=2(g(x)+1/4)+128u2v2≥1/2x^\top\nabla g(x)=2(g(x)+1/4)+128u^2v^2\ge1/2 on g≥0g\ge0. Since x⊤n≥0x^\top n\ge0 for every n∈NB(x)n\in N_{\mathcal B}(x) and ∥x∥≤1\|x\|\le1, both the boundary gradient and the infeasible slope in (13) are bounded below by 1/21/2. We have not verified this global condition for the experimental networks.

Q4: More Numerical Comparison

We compared OP with two alternatives that avoid projection onto the empirical constraints: direct subgradient descent on the maximum positive constraint violation added to the objective (Penalty SGD), and a stochastic prox-linear variant that penalizes the maximum of the two linearized constraint residuals. The latter uses minibatch subgradients of the hinge risks; it is an adaptation, not the deterministic smooth-composite algorithm. We reused the splits, initializations, thresholds and five seeds from the comparison with PSGD. All three methods used 500 updates, batch size 64, step size 0.05, penalty weight 5 and ball radius 10, without retuning. Neither baseline received a terminal feasibility repair.

DatasetMethodType I (%)Type II (%)Abstain (%)FeasibleTime (s)
NASAOP9.43 ± 0.3910.72 ± 1.857.43 ± 0.705/54.82 ± 0.36
NASAPenalty SGD9.66 ± 1.4110.67 ± 2.647.56 ± 1.382/54.54 ± 1.19
NASAProx-linear10.50 ± 0.2912.24 ± 1.874.91 ± 0.251/54.69 ± 0.30
ClimSimOP7.20 ± 0.352.64 ± 0.423.40 ± 0.605/56.05 ± 0.38
ClimSimPenalty SGD7.85 ± 1.701.70 ± 0.793.23 ± 0.853/55.14 ± 0.39
ClimSimProx-linear5.32 ± 0.407.55 ± 1.490.00 ± 0.000/56.13 ± 0.54

Type I, Type II, abstention and training time are reported as mean ± sample standard deviation across five paired seeds. Type I and II are incorrect decisions per true class on the test set; abstentions remain in the denominator. Feasible counts final models satisfying both training constraints to tolerance 10−510^{-5}. Time is training wall time in seconds, measured sequentially on the same CPU with one thread.

OP returned a feasible model in 10/10 runs, versus 5/10 for Penalty SGD and 1/10 for the prox-linear variant. The largest positive training residuals across seeds were 0.0294 and 0.0048 for the two baselines, respectively. Thus the clearest distinction at these settings is feasibility at termination; these timings do not establish a general speed advantage over penalty methods.

Q5: Practical parameter selection and presentation

We agree with you that the hyper-parameters required in our theory are hard to set. Indeed, that is a common issue in optimization theory and practice, even in the simplest GD convergence of convex function, we require stepsize to be 1/L1/L which cannot be set in practice. The parameter-free version of the algorithm is needed. This is beyond the scope of this paper and we will leave it as future work.

For Assumption 3.1, the requirement for initial feasible point can actually be removed in convex constraint setting as well. Let x0∈Bx_0\in\mathcal B be arbitrary and write dt=dist⁡(xt,C)d_t=\operatorname{dist}(x_t,\mathcal C). The convex inner lemma already holds for any center in the ball, so dt≤e/GFd_t\le e/G_F for every t≥1t\ge1 on the inner accuracy event. The outer descent proof uses d0=0d_0=0 only when summing over steps. Keeping the first term replaces the initial gap Δf\Delta_f by Δf+Gfd0+ℓd02\Delta_f+G_f d_0+\ell d_0^2. Since the unit ball has diameter two, 2Gf+4ℓ2G_f+4\ell bounds the extra term without computing d0d_0. Both convex theorems therefore retain their stationarity measures, O~(ϵ−4)\widetilde O(\epsilon^{-4}) oracle complexity, and one final projection; no initial feasibility solve is needed.

We also appreciate your suggestion on the paper presentation. Will incorporate them into the updated version. Thanks.

Thank you for the responses. The high-probability extension and the removal of the feasible-initialization requirement address my corresponding concerns. However, my main concerns regarding novelty and comparison with existing methods remain unresolved.

1. Novelty.

The response clarifies the intended output guarantees, but does not sufficiently establish the novelty of the proposed framework relative to existing one-projection, penalty, and proximal methods. It remains unclear what substantive advance the proposed method offers beyond combining these established techniques.

2. Comparison with MBA.

The response explains the structural differences between MBA and the proposed method, particularly how they maintain feasibility. However, this explanation is insufficient to assess the contribution of the proposed framework relative to MBA. A more substantive theoretical comparison on problem settings where both methods apply would help clarify the significance of these differences.

A numerical comparison with MBA is also important for evaluating the practical benefits of the proposed approach, but none has been provided. I acknowledge the additional experiments with Penalty SGD and a prox-linear variant; however, they do not address this specific concern.

Reviewer_4Ky9OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies stochastic nonconvex optimization with functional constraints and proposes a penalized proximal subgradient method that needs only one final projection onto the original feasible set. The method approximately solves a sequence of strongly convex penalized proximal subproblems. During the iterations, it only projects onto a simple Euclidean ball.

For convex constraints, the method starts from a given feasible point and provides projected-gradient mapping guarantees for smooth objectives and Moreau-envelope stationarity guarantees for weakly convex, possibly nonsmooth objectives. For smooth nonconvex constraints, under a global infeasible-slope condition and additional regularity assumptions, an exact-penalty variant allows infeasible initialization and returns an exactly feasible point within O(ε)O(\varepsilon) of an ε\varepsilon-KKT point. For fixed problem parameters, these stationarity guarantees hold with probability at least 2/32/3, using O~(ε−4)\widetilde{O}(\varepsilon^{-4}) stochastic first-order oracle calls and one exact final projection. The computational cost of this projection is counted separately.

Critical strengths
  1. The paper addresses a practically meaningful problem: reducing expensive projections while retaining convergence guarantees. It extends the one-projection strategy to stochastic optimization with nonconvex objectives and either convex or nonconvex constraints, achieving a stochastic first-order oracle complexity of O~(ε−4)\widetilde{O}(\varepsilon^{-4}) for fixed problem parameters. This retains the standard stochastic-oracle complexity order while requiring only one final projection onto the original feasible set, whose computational cost is treated separately.

  2. The paper provides a unified algorithmic framework with carefully distinguished stationarity guarantees. For convex constraints, it establishes projected-gradient mapping guarantees for smooth objectives and Moreau-envelope stationarity guarantees for nonsmooth objectives. For smooth nonconvex constraints, the global infeasible-slope condition permits arbitrary initialization within the bounding ball and guarantees an exactly feasible output that is within O(ε)O(\varepsilon) of an ε\varepsilon-KKT point with high probability. The analysis also explicitly distinguishes stationarity at the returned point from proximity to an approximately stationary point. This careful treatment of different stationarity notions is a positive aspect of the theoretical analysis.

Critical weaknesses
  1. The technical novelty is limited. The method combines existing exact-penalty and stochastic proximal methods, and keeps the standard O~(ε−4)\widetilde{O}(\varepsilon^{-4}) stochastic-oracle complexity order. For nonconvex constraints, the argument in Lemma C.2 is close to earlier exact-penalty results: a small penalty residual forces the corresponding proximal point to be feasible and gives approximate KKT conditions. Once this feasible point yy is available, the final-projection bound ∥p−y∥≤2∥x−y∥\|p-y\|\leq 2\|x-y\| for p∈PC(x)p\in P_C(x) follows from the nearest-point property and the triangle inequality. The one-projection guarantee is useful, but the added technical work appears limited.

  2. The assumption for nonconvex constraints is strong. The global infeasible-slope condition must hold at every infeasible point in the bounding ball. This limits the problems covered by the theory. Appendix C.5 explains why boundary regularity alone is not enough, but the paper does not give a concrete nonconvex example where all the required conditions can be checked. It also does not show that this condition holds for the neural-network constraints in the experiments. The practical scope of Theorem 3.8 therefore remains unclear.

  3. The experiments have several limitations. The experiments do not directly validate the theoretical guarantees. The theory assumes exact constraint values and gradients and an exact terminal projection, while the abstention experiments use stochastic constraint-gradient estimates and approximate neural-network projections. Moreover, the experiments use the last outer iterate rather than the randomly selected iterate required by the theoretical analysis. The runtime comparisons also have a fairness issue: in the abstention experiments on ClimSim and NASA, the two methods use different constraint thresholds, so they are not solving identical constrained problems. A controlled experiment under the theoretical assumptions, together with runtime comparisons using the same thresholds and explicit reporting of final empirical constraint violations, would make the results more convincing.

Questions for authors
  1. Could the authors further clarify the theoretical differences between the proposed method and related stochastic constrained optimization methods, including exact-penalty methods [1], level-constrained methods [2], and stochastic SQP [3]? In particular, a comparison of constraint qualifications, feasibility and stationarity guarantees, and stochastic-oracle complexity would help better establish the theoretical contributions of this work, while accounting for differences in problem settings. [1] Yawen Cui, Qiankun Shi, Xiao Wang, and Xiantao Xiao. An Exact Penalty Method for Stochastic Equality-Constrained Optimization. Optimization Online, 2025. [2] Digvijay Boob, Qi Deng, and Guanghui Lan. Level Constrained First Order Methods for Function Constrained Optimization. Mathematical Programming, 209:1–61, 2025. [3] Frank E. Curtis, Daniel P. Robinson, and Baoyu Zhou. Sequential Quadratic Optimization for Stochastic Optimization with Deterministic Nonlinear Inequality and Equality Constraints. SIAM Journal on Optimization, 34(4):3592–3622, 2024.

  2. Can the authors clarify the main technical contribution beyond combining existing exact penalty methods and proximally guided stochastic optimization? In particular, could Theorem 3.8 be obtained by applying an existing stochastic first-order method to the weakly convex penalized objective, followed by a standard exact-penalty stationarity argument and a single terminal projection? If not, which step requires a new analysis?

  3. Can the authors provide an example satisfying Assumption 3.7 with a genuinely nonconvex feasible set, together with verifiable regularity constants? Can the authors also clarify whether this assumption holds for the nonlinear constraints considered in the experiments?

2 comments

Thank you for your very constructive comments. We will address them below.

Q1. How do the oracle model and output compare with related methods?

MethodExactly feasible output?Feasible start required?
Cui et al.NoNo
Boob, Deng and LanYesYes (strictly feasible)
Curtis, Robinson and ZhouNoNo
Ours (Theorem 3.8)YesNo

[Cui et al.] study smooth equality-constrained problems in which both the objective and the constraints can be stochastic. Their exact-penalty method returns a stochastic ϵ\epsilon-KKT point with E∥c(x)∥≤ϵ\mathbb{E}\|c(x)\|\le\epsilon, but does not guarantee feasibility. We treat a deterministic inequality and use one exact terminal projection to guarantee g(x^)≤0g(\hat x)\le0.

[Boob, Deng and Lan] handle multiple nonconvex inequalities. Their algorithm needs to start from a strictly feasible point, they solve a tightened convex subproblem at each step so that every iterate remains strictly feasible. Our nonconvex theorem allows any starting point in the ball and imposes no feasibility requirement on intermediate iterates.

[Curtis, Robinson and Zhou] use stochastic objective gradients and exact derivatives of deterministic nonlinear equalities and inequalities. Their SQP method linearizes the constraints at each step and establishes convergence in expectation, without guaranteeing exact feasibility at a finite iteration. We allow a nonsmooth, weakly convex objective and one smooth inequality. Under our global slope condition, O~(ϵ−4)\widetilde O(\epsilon^{-4}) stochastic objective-subgradient calls and one exact projection suffice: the returned point is feasible and, with probability at least 2/32/3, lies within 2ϵ/β2\epsilon/\beta of an ϵ\epsilon-KKT point.

W1 / Q2. Novelty, Assumption and Theorem 3.8

Our contribution is a strong guarantee for the original constrained problem after a single projection: the returned point is exactly feasible and lies near an ϵ\epsilon-KKT point. This is the first result for nonconvex constraint problem with feasible solution without feasible initialization requirement. We achieve this with the help of Assumption 3.7. Assumption 3.7 imposes a slope bound throughout the infeasible region of that ball, not just near the feasible boundary. This is what lets Theorem 3.8 dispense with a feasible start: any x0∈Bx_0\in\mathcal B is allowed, and no intermediate iterate needs to be feasible.

Regarding the proposed derivation of Theorem 3.8: a stochastic convergence bound for the penalized objective can supply a small proximal residual. The additional step is to prove that this residual certifies stationarity for the original problem. Let xx be the selected iterate, yy its exact proximal point for the penalized objective, and r=β∥x−y∥r=\beta\|x-y\|. If g(y)>0g(y)>0, proximal optimality and Assumption 3.7 imply r≥λσout−Gfr\geq\lambda\sigma_{\rm out}-G_f. Thus, on the event r≤ϵ<λσout−Gfr\leq\epsilon<\lambda\sigma_{\rm out}-G_f, yy must be feasible. The same optimality condition then gives a nonnegative multiplier with exact complementarity and KKT residual at most rr at yy. Only now does the final projection enter: since yy is feasible, the nearest point x^\hat x to xx satisfies ∥x^−y∥≤2∥x−y∥≤2ϵ/β\|\hat x-y\|\leq2\|x-y\|\leq2\epsilon/\beta.

W2 / Q3. Is there a genuinely nonconvex example satisfying Assumption 3.7?

Yes. On the unit disk take g(u,v)=u2+v2+64u2v2−1/4g(u,v)=u^2+v^2+64u^2v^2-1/4. The feasible set lies in the disk of radius 1/21/2. It contains (1/2,0)(1/2,0) and (0,1/2)(0,1/2) but excludes their midpoint, where g=1/8g=1/8. Writing x=(u,v)x=(u,v), we have x⊤∇g(x)=2(g(x)+1/4)+128u2v2≥1/2x^\top\nabla g(x)=2(g(x)+1/4)+128u^2v^2\geq1/2 whenever g(x)≥0g(x)\geq0. Every n∈NB(x)n\in N_{\mathcal B}(x) satisfies x⊤n≥0x^\top n\geq0, so ∥∇g(x)+n∥≥1/2\|\nabla g(x)+n\|\geq1/2 there. This gives both slope bounds with constant 1/21/2; smoothness follows from the polynomial Hessian on a bounded neighborhood.

W3. Does the runtime advantage persist at identical thresholds?

We re-run the comparison with the same threshold choice and provide the results here:

Dataset / methodType I (%)Type II (%)R0R_0 (%)R1R_1 (%)Abstain (%)Time (s)
NASA / OP9.37 ± 0.3810.81 ± 1.839.38 ± 0.4010.81 ± 1.837.44 ± 0.574.71 ± 0.09
NASA / PSGD9.48 ± 0.569.06 ± 2.579.76 ± 0.479.06 ± 2.579.92 ± 1.841,568.59 ± 469.38
ClimSim / OP7.08 ± 0.443.02 ± 0.797.30 ± 0.393.02 ± 0.793.04 ± 0.7620.92 ± 0.73
ClimSim / PSGD7.62 ± 0.886.60 ± 1.498.81 ± 0.606.60 ± 1.492.15 ± 1.161,261.31 ± 246.63

Time is optimizer wall time, including projections and excluding data preparation and test evaluation. With one CPU thread per run and seeds running concurrently, the ratio of mean PSGD to mean OP time was 333.4× on NASA and 60.3× on ClimSim. PSGD spent 99.91% and 99.78% of training time in its 500 projector calls, respectively; OP used one terminal call.

I appreciate the authors' responses. They have addressed my concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.