REVIEW 3 major objections 4 minor 1 cited by
A Projected Variable Smoothing for Weakly Convex Optimization and Supremum Functions
T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read A projected variable-smoothing algorithm reaches epsilon-approximate solutions in O(epsilon-cubed) iterations for weakly convex composite problems, and it supplies proximity formulas for supremum functions.
desk verdict Solid prox formulas for weakly convex suprema, but Algorithm 2's stopping rule tests the full gradient while the theory only bounds the projected gradient, so the O(ε^{-3}) termination guarantee is false as written; easy fix. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the Moreau envelope $g_\mu(x)=\inf_y\{g(y)+\frac{1}{2\mu}\|x-y\|^2\}$ and its proximity operator $\operatorname{prox}_{\mu g}(x)$, which smooths a weakly convex $g$ into a function with gradient Lipschitz constant $L_{\nabla h}+\|A\|^2/\mu_k$ when composed with $A$. Iterating $x_{k+1}=P_V(x_k-\gamma_k\nabla(h+g_{\mu_k}\circ A)(x_k))$ with $\mu_k=Ck^{-\alpha}$ and $\gamma_k=1/L_k$ is the projected variable smoothing step; the projection $P_V$ enforces the subspace constraint and enters the optimality residual through $N_V(x)$. For supremum functions, the load-bearing identity is Theorem 5.1, $f_\mu(x)=\sup_{c\in C}(f_c)_\mu(x)$, which allows one to compute $\operatorname{prox}_{\mu f}$ by selecting an index attaining that supremum and applying $\operatorname{prox}_{\mu f_c}$.
What would settle it
Run Algorithm 2 with $\alpha=1/3$, $C=1$, $h=0$, $g(x)=|x|$, $A=1$, and $V=H$, and check whether stopping occurs by the stated iteration bound $2\max\{\tilde C^3, C^3L_g^3\}\epsilon^{-3}$ for $\epsilon=10^{-3}$; if either residual tolerance is exceeded, the $O(\epsilon^{-3})$ complexity bound is false. Separately, for the max-dispersion instance with $R=(1\,1\,1)$ and $B$ the unit ball, record $\sup_{k\le 10^6}\|x_k\|$ under Algorithm 4; an unbounded sequence would confirm that Theorem 3.2's boundedness hypothesis is not automatic.
Extended reading notes
Core claim
On the paper's own terms, the central claim is that the composite weakly convex problem (2), minimize $h(x)+g(Ax)$ over $x$ in a closed vector subspace $V$, is solved by the projected variable smoothing iteration: set $\mu_k=Ck^{-\alpha}$, form $F_k=h+g_{\mu_k}\circ A$, and update $x_{k+1}=P_V(x_k-\gamma_k\nabla F_k(x_k))$. Theorems 3.1 and 4.1 prove that under $L_g$-Lipschitz $g$ the sequence satisfies $\min_{1\le j\le k} d(-\nabla h(x_j), A^*\partial g(\operatorname{prox}_{\mu_j}g(Ax_j))+N_V(x_j)) \le k^{(\alpha-1)/2}\tilde C$ and $\|Ax_k-\operatorname{prox}_{\mu_k}g(Ax_k)\|\le C L_g k^{-\alpha}$, so an $\epsilon$-approximate solution costs $O(\epsilon^{-2/(1-\alpha)})$ iterations, or $O(\epsilon^{-3})$ at $\alpha=1/3$. Theorem 3.2 extends the rates to non-Lipschitz $g$ in finite-dimensional codomain under a boundedness assumption on the iterates. For supremum functions $f=\sup_{c\in C} f_c$ with weakly convex data, Theorem 5.1 gives $f_\mu(x)=\sup_c(f_c)_\mu(x)$, and Theorem 5.2 identifies $\operatorname{prox}_{\mu f}(x)$ with $\operatorname{prox}_{\mu f_c}(x)$ for any $c$ attaining the supremum; Proposition 5.2 gives a closed-form prox for the maximum of quadratics, and Proposition 5.3 gives a convergent iterative prox for affine-quadratic suprema. Penalty versions of DRO, constrained LASSO, and max dispersion fit into problem (2), and the numerical section compares two subspace formulations for max dispersion.
Load-bearing premise
The load-bearing premise is that the weakly convex function $g$ is Lipschitz; for the non-Lipschitz applications the paper instead assumes the generated sequence stays bounded, and that boundedness is not verified for the DRO and max-dispersion examples.
Editorial extensions
If this is right
- For Lipschitz weakly convex composites with subspace constraints, an $\epsilon$-approximate point is guaranteed in $O(\epsilon^{-2/(1-\alpha)})$ iterations, and the user can set $\alpha=1/3$ to get the $O(\epsilon^{-3})$ rate.
- When the generated sequence stays bounded, the same rate holds without any Lipschitz assumption on $g$, expanding the class of usable objectives to functions like negative quadratics.
- The supremum-envelope identity reduces proximity evaluation for supremum functions to a maximization over the index set $C$; for the maximum of finitely many quadratic terms, the maximizer has a KKT closed form, making the prox computation explicit.
- The method is immediately applicable to penalty reformulations of DRO, constrained LASSO with weakly convex regularizers, and max dispersion, with the max-dispersion experiments indicating which of two subspace formulations converges faster.
Reading between the lines
- A natural next step is to verify the boundedness hypothesis of Theorem 3.2 numerically for Algorithms 3 and 4; if the iterates stay bounded on the reported instances, the $O(\epsilon^{-3})$ guarantee would cover the non-Lipschitz DRO and max-dispersion problems as well.
- The closed-form proximity for the maximum of quadratics should transfer to other max-type weakly convex losses, such as robust estimation or adversarial training, wherever the active index follows the same sorted-$\alpha_i$ KKT pattern.
- An implicit testable consequence is that Algorithm 4's advantage in wall-clock time over Algorithm 3 should widen with larger $N$, because Algorithm 4 uses a closed-form proximity operator while Algorithm 3 runs an inner convergent iteration for the same task.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the composite minimization problem min_{x in V} h(x) + g(Ax), where h has a Lipschitz gradient, g is weakly convex, A is a bounded linear operator, and V is a closed vector subspace. The authors propose a projected variable smoothing method that interleaves decreasing smoothing parameters with projection onto V, and they prove convergence and complexity results: under a Lipschitz assumption on g they obtain an O(epsilon^{-2/(1-alpha)}) iteration bound (O(epsilon^{-3}) for alpha=1/3) for an epsilon-approximate optimality certificate, and under a boundedness assumption on the generated sequence they obtain analogous guarantees without the Lipschitz assumption. The paper also develops tools for suprema of weakly convex functions, showing that the Moreau envelope of a supremum is the supremum of Moreau envelopes and deriving formulas and algorithms for proximity operators in two cases (quadratic and affine data). These results are applied to distributionally robust optimization, constrained LASSO, and max dispersion problems, with numerical experiments for max dispersion.
Significance. The paper extends the variable smoothing framework of Boehm and Wright to the projected setting and to suprema of weakly convex functions, and the technical results in Section 5 appear useful and correct. The explicit formulas and convergent algorithms for proximity operators of weakly convex supremum functions are a genuine contribution. The main complexity theorem, however, is not correct as written: the stopping criterion used in Algorithm 2 tests the full gradient norm while the proof controls only the projected gradient norm. This is a load-bearing flaw because Theorem 4.1 is the paper's headline guarantee. The flaw is local and repairable by changing the stopping statistic to the projected gradient norm (or the exact distance in equation (10)), and with that correction the epoch argument supports the stated O(epsilon^{-3}) bound. The non-Lipschitz applications in Sections 6 and 7 are also not covered by the stated theorems, because boundedness of the generated sequence is assumed, not verified. If the stopping criterion is corrected and the application claims are qualified appropriately, the paper would be a solid contribution to weakly convex and nonsmooth optimization.
major comments (3)
- [Section 4, Algorithm 2 and Theorem 4.1] The stopping criterion in Algorithm 2 is incompatible with the proof of Theorem 4.1. Algorithm 2 stores S_l = min ||nabla F_{k+1}(x_{k+1})|| over the epoch and stops when S_l <= epsilon, but the proof of Theorem 4.1 establishes a bound only on the projected gradient: equation (14) bounds min ||P_V nabla F_j(x_j)||, and equation (10) bounds the optimality distance by ||P_V nabla F_j(x_j)||. Since ||P_V y|| <= ||y||, a small projected gradient does not imply a small full gradient. Concretely, take H = R^3, V = ker(1,1,1), h(x) = x_1+x_2+x_3, g = 0, and A = I. Then every x in V is a critical point because nabla h(x) = (1,1,1) belongs to V^perp = N_V(x). Algorithm 1 keeps x_{k+1} = P_V(x_k - gamma_k v) = x_k, and Algorithm 2 computes S_l = ||v|| = sqrt(3) in every epoch, so it never terminates for any epsilon < sqrt(3), contradicting the claimed O(epsilon^{-2/(1-alpha)}) termination guarantee. The fix is to store and test ||P_V nabla F_{k+1}(x_{k+1})||, or the exact distance in (10), in place of the full gradient norm; with that change the epoch argument in the proof of Theorem 4.1 goes through, since (14) and (15) then apply to the iterate on which the epoch minimum is attained.
- [Sections 6.3 and 7; Theorems 3.1 and 3.2] The max dispersion application is not covered by the theoretical guarantees as presented. The function rg in (40) and g in (42) are not globally Lipschitz on R^n or R^{nN}, so Theorem 3.1 and Theorem 4.1, which both assume g is L_g-Lipschitz, do not apply. Theorem 3.2 removes the Lipschitz assumption only under the additional hypothesis that the sequence (x_k) generated by Algorithm 1 is bounded, and no boundedness proof is supplied for Algorithms 3 and 4 in Section 7. Coercivity of the penalized objective for lambda > 2 does not by itself imply boundedness of the iterates of a variable-smoothing scheme with changing objectives. Thus the numerical experiments in Section 7 demonstrate heuristic performance, but the paper does not establish the advertised convergence or O(epsilon^{-3}) complexity for the showcased non-Lipschitz problems. I recommend either proving the required boundedness for these instances or clearly stating that the complexity guarantees apply only to the Lipschitz case and that the non-Lipschitz applications are supported by the conditional Theorem 3.2 when boundedness can be verified.
- [Section 3, Theorem 3.2 and Proposition A.2] The proof of Theorem 3.2 depends on Proposition A.2, which provides a uniform bound on ||nabla g_mu(y)|| for y in a bounded set S, but the argument in Proposition A.2 uses Lipschitz continuity of g on the bounded set rS. The claim that g is Lipschitz on rS follows from weak convexity and boundedness, but the proof as written omits the verification that g is finite and continuous on rS; g is assumed lower semicontinuous and weakly convex on R^m, so it is locally Lipschitz on the interior of its domain, but the domain is not stated to be all of R^m. If g is real-valued, this is fine; if g is extended-valued, the passage from weak convexity on R^m to Lipschitzness on rS needs an explicit domain assumption or a localization argument. This point should be clarified, since Theorem 3.2 is the only result covering non-Lipschitz applications.
minor comments (4)
- [Section 2, first paragraph] There is a typo in 'the set of extended valued functions ohH'; it should read 'on H'.
- [Section 4, Algorithm 2] The initialization j_l <- 2^l is never used before being overwritten; consider initializing j_l to 2^l and documenting that the recorded index is updated only when S_l changes.
- [Section 6.3, equations (39)-(41)] The equivalence between (39) and (41) is asserted but not proved; a brief argument that x = (x, ..., x) solves (41) if and only if x solves (39) would improve readability.
- [Section 7, numerical experiments] The stopping criterion based on ||x_{k+1} - x_k|| <= 10^{-5} is not justified by the theory, which provides stopping rules based on (projected) gradient norms or optimality distances; the experiments should either use a theory-compatible stopping rule or explicitly describe the stopping rule as a heuristic.
Circularity Check
No significant circularity: the complexity proof and the supremum-function prox results reduce to prior independent theorems rather than to the paper's own conclusions.
full rationale
The central complexity result (Theorem 4.1) is proved by the epoch-summing argument adapted from [6], using descent inequalities and Lipschitz/prox estimates whose proofs are cited from [6] and not from the target theorem. The genuinely new element, projection onto the subspace V, enters through the inequality d(-z, N_V(x)) <= ||P_V z||, which is proved in the paper. No parameter is fitted and no optimality measure is defined in terms of the complexity bound being claimed. The supremum-function section reduces the weakly convex case to the convex case via Lemma 5.1 and then invokes [22, Theorem 3.1] and [22, Theorem 3.5]. These are prior published results by two of the authors, but they are not restatements of the present target: they apply to convex data functions, whereas the present theorems concern weakly convex supremum functions. The reduction via [1, Theorem 3.4] and Lemma 5.1 is an external mathematical step, so the self-citation is real evidence rather than a circular premise. There is a genuine correctness gap in Section 4: Algorithm 2 stops on the full gradient norm ||∇F_{k+1}(x_{k+1})||, whereas the proof of Theorem 4.1 bounds only the projected norm ||P_V∇F_j(x_j)||. That mismatch is a bug in the written termination argument, not a circularity, because it does not make the claimed result equivalent to its inputs. Similarly, Theorem 3.2 assumes boundedness of the generated sequence without verifying it in the applications; this is an unproven hypothesis, not a circular derivation. Overall, the paper does not derive its conclusions from those same conclusions, and the central claims have independent content.
Assumptions & free parameters
free parameters (3)
- alpha (smoothing exponent) =
1/3 in experiments
- C (initial smoothing scale) =
1/4 in experiments
- lambda (penalty weight) =
100 and 200 in experiments
assumptions (6)
- standard math Projection onto closed subspace is linear and N_V(x)=V^perp for x in V
- domain assumption Bohm-Wright lemmas [6, Lemma 3.1-3.3, 4.1]
- domain assumption Attouch-Aze envelope relations [1, Theorem 3.4]
- domain assumption Convex supremum envelope theorems [22, Theorem 3.1 and 3.5]
- standard math KKT conditions for simplex-constrained convex problem (21)
- standard math Krasnoselskii-Mann convergence [3, Theorem 5.15]
Cite this review
Pith. "Pith review of A Projected Variable Smoothing for Weakly Convex Optimization and Supremum Functions." pith.science (2026). https://pith.science/paper/GYUZV3Z5
@misc{pith2026250200525,
author = {Pith},
title = {Pith review of: A Projected Variable Smoothing for Weakly Convex Optimization and Supremum Functions},
year = {2026},
howpublished = {\url{https://pith.science/paper/GYUZV3Z5}},
note = {Machine review of arXiv:2502.00525}
}
abstract
In this paper, we address two main topics. First, we study the problem of minimizing the sum of a smooth function and the composition of a weakly convex function with a linear operator on a closed vector subspace. For this problem, we propose a projected variable smoothing algorithm and establish a complexity bound of $\mathcal{O}(\epsilon^{-3})$ to achieve an $\epsilon$-approximate solution. Second, we investigate the Moreau envelope and the proximity operator of functions defined as the supremum of weakly convex functions, and we compute the proximity operator in two important cases. In addition, we apply the proposed algorithm for solving a distributionally robust optimization problem, the LASSO with linear constraints, and the max dispersion problem. We illustrate numerical results for the max dispersion problem.
Forward citations
Cited by 1 Pith paper
-
A Proximal Variable Smoothing for Minimization of Nonlinearly Composite Nonsmooth Function -- Finite-Max Minimization and MIMO Applications
A proximal variable smoothing method with backtracking stepsizes finds stationary points for nonlinearly composite nonsmooth optimization with O(epsilon^-3) iteration complexity.
Reference graph
Works this paper leans on
-
[22]
P. P´ erez-Aros and E. Vilches. Moreau envelope of supremum functions with applications to infinite and stochastic programming. SIAM J. Optim. , 31(3):1635–1657, 2021
work page 2021
-
[6]
A. B¨ ohm and S.J. Wright. Variable smoothing for weakly convex composite functions. J. Optim. Theory Appl. , 188:628–649, 2021
work page 2021
-
[1]
H. Attouch and D. Az´ e. Approximation and regularization of arbitrary functions in Hilbert spaces by the Lasry-Lions method. Ann. Inst. H. Poincar´ e C Anal. Non Lin´ eaire, 10(3):289–312, 1993
work page 1993
- [2]
-
[3]
H. H. Bauschke and Patrick L. Combettes. Convex analysis and monotone operator theory in Hilbert spaces . CMS Books Math./Ouvrages Math. SMC. Springer, second edition, 2017
work page 2017
-
[4]
A.E. Beaton and J.W. Tukey. The fitting of power series, meaning polynomials, illus- trated on band-spectroscopic data. Technometrics, 16(2):147–185, 1974
work page 1974
-
[5]
A. Beck. First-order methods in optimization , volume 25 of MOS-SIAM Ser. Optim. SIAM, Philadelphia, PA., 2017
work page 2017
-
[7]
L. Brice˜ no-Arias, J. Deride, S. L´ opez-Rivera, and F.J. Silva. A primal-dual partial inverse algorithm for constrained monotone inclusions: Applications to stochastic pro- gramming and mean field games. Appl. Math. Optim. , 87(2):21, 2023
work page 2023
Show all 29 references
-
[8]
Brice˜ no-Arias
L. Brice˜ no-Arias. Forward douglas rachford splitting and forward-partial inverse method for solving monotone inclusions. Optimization, 64(5):1239–1261, 2015
2015
-
[9]
Chambolle and P.L
A. Chambolle and P.L. Lions. Image recovery via total variation minimization and related problems. Numer. Math. , 76:167–188, 1997
1997
-
[10]
X. Chen, T. K. Pong, and R. J-B. Wets. Two-stage stochastic variational inequalities: an ERM-solution procedure. Math. Program., 165(1, Ser. B):71–111, 2017
2017
-
[11]
L. Condat. A primal–dual splitting method for convex optimization involving lips- chitzian, proximable and linear composite terms. J. Optim. Theory Appl. , 158(2):460– 479, 2013
2013
-
[12]
Cui and J.-S
Y. Cui and J.-S. Pang. Modern nonconvex nondifferentiable optimization , volume 29 of MOS-SIAM Ser. Optim. SIAM, Philadelphia, PA., 2022
2022
-
[13]
Dasarathy and L.J
B. Dasarathy and L.J. White. A maxmin location problem. Oper. Res., 28(6):1385– 1401, 1980
1980
-
[14]
de Oliveira
W. de Oliveira. Risk-averse stochastic programming and distributionally robust opti- mization via operator splitting. Set-Valued Var. Anal., 29(4):861–891, 2021. 20 Sergio L´ opez-Rivera, Pedro P´ erez-Aros and Emilio Vilches
2021
-
[15]
Duchi, S
J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the l 1-ball for learning in high dimensions. In Proceedings of the 25th international conference on Machine learning , pages 272–279, 2008
2008
-
[16]
Fan and R
J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle properties. J. Amer. Statist. Assoc. , 96(456):1348–1360, 2001
2001
-
[17]
Haines, J
S. Haines, J. Loeppky, P. Tseng, and X. Wang. Convex relaxations of the weighted maxmin dispersion problem. SIAM J. Optim. , 23(4):2264–2294, 2013
2013
-
[18]
Jeyakumar and G
V. Jeyakumar and G. Li. Exact second-order cone programming relaxations for some nonconvex minimax quadratic optimization problems. SIAM J. Optim. , 28(1):760–787, 2018
2018
-
[19]
Johnson, L.M
M.E. Johnson, L.M. Moore, and D. Ylvisaker. Minimax and maximin distance designs. Journal of statistical planning and inference , 26(2):131–148, 1990
1990
-
[20]
Luenberger and Y
D.G. Luenberger and Y. Ye. Linear and nonlinear programming , volume 2. Springer, 1984
1984
-
[21]
B. Mercier. In´ equations variationnelles de la m´ ecanique, volume 1 of Publications Math´ ematiques d’Orsay. Universit´ e de Paris-Sud, D´ epartement de Math´ ematiques, Or- say, 1980
1980
-
[23]
Rockafellar
R.T. Rockafellar. Convex analysis , volume 11. Princeton university press, 1997
1997
-
[24]
Shapiro, D
A. Shapiro, D. Dentcheva, and A. Ruszczynski. Lectures on Stochastic Programming: Modeling and Theory . Society for Industrial and Applied Mathematics, Philadelphia, PA, third edition, 2021
2021
-
[25]
W. Shi, G. Wahba, S. Wright, K. Lee, R. Klein, and B. Klein. Lasso-patternsearch algorithm with application to ophthalmalogy data. University of Wisconsin , 2006
2006
-
[26]
Sun and Y
S. Sun and Y. Yu. Least squares estimation of weakly convex functions. In K. Chaudhuri and M. Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics , volume 89 of Proceedings of Machine Learning Research, pages 2...
2019
-
[27]
Sun, A.J
X.A. Sun, A.J. Conejo, et al. Robust optimization in electric energy systems . Springer, 2021
2021
-
[28]
Tibshirani and J
R.J. Tibshirani and J. Taylor. The solution path of the generalized lasso. Ann. Statist., 39(3):1335–1371, 2011
2011
-
[29]
C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty. Ann. Statist., 2010. A Appendix A.1 Penalty Method This section is based in [20, Section 21.1]. Consider the following optimization problem min xPVXB fpxq, (43) where f : RnÑ R is lower semicontinuo...
2010
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.