- 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 -small projected-gradient mapping (smooth case) or Moreau-envelope residual (nonsmooth case) using stochastic subgradients. For smooth nonconvex constraints, under a global infeasible-slope condition, an exact-penalty variant returns a feasible point within of an -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 -KKT witness), exact feasibility of the output, and an 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 , which is impractical as stated. The paper does not discuss how to boost this to high probability (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 written as two inequalities would violate the Slater-type margin structure. A discussion of this limitation and possible extensions is needed.
Questions for authors
- In Algorithm 1, line 6, the algorithm returns , but 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?
- Assumption 3.1 assumes a feasible point 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?
- For a nonconvex constraint set , 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)?
- In both settings (convex and nonconvex constraints), the convergence rates are the same . 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 , penalty , and curvature ) and the stronger Assumption 3.7, or is there a regime where the nonconvex setting provably costs more?
- Why do you restrict each subproblem to a ball 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?
Thank you for your very constructive comments. We will address them below.
W1. Is the success probability limited to 2/3?
No. The confidence can be raised to 1−δ in a single run. Replace the uniform output index by t∗∈argmin0≤t<T∥xt+1−xt∥. With failure budget δ/T per inner solve, Lemma A.1 and a union bound give simultaneous inner error e=O((log(K+1)+log(T/δ))/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) for e≤1.
Thus, for fixed problem parameters, T=O(ϵ−2) and K=O(ϵ−2log(2/(ϵδ))) suffice. This costs TK=O(ϵ−4[log(2/ϵ)+log(1/δ)]) stochastic objective-oracle calls and one terminal projection: project xt∗+1 for convex constraints or xt∗ 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=0, our algorithm can still work. But for general nonconvex equality g(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).
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 z: if ∥z−xJ∥≤dist(xJ,C)+η, then on the theorem's success event ∥z−y∥≤2ϵ/β+η for the same ϵ-KKT witness y. This follows by the triangle inequality since ∥xJ−y∥≤ϵ/β. 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∈B be arbitrary and write dt=dist(xt,C). The convex inner lemma already holds for any center in the ball, so dt≤e/GF for every t≥1 on the inner accuracy event. The outer descent proof uses d0=0 only when summing over steps. Keeping the first term replaces the initial gap Δf by Δf+Gfd0+ℓd02. Since the unit ball has diameter two, 2Gf+4ℓ bounds the extra term without computing d0. Both convex theorems therefore retain their stationarity measures, O(ϵ−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) outer steps suffice, and solving each strongly convex subproblem to objective error O(ϵ2) takes O(ϵ−2) calls. Their product gives the same O(ϵ−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 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 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)>0 and ∇g(x)=0, where (13) fails. We have not measured sensitivity to the radius in our experiments.