- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper proposes Hom-PALM, a proximal augmented Lagrangian framework for optimization with convex inequality constraints and potentially nonlinear equality constraints. It uses a homeomorphic reparameterization of the inequality-feasible region by the unit ball, replacing expensive projections onto the original feasible set with simple ball projections, while handling equality constraints through augmented Lagrangian or penalty updates. Its main algorithmic contribution is Hom-APG, which combines regularization and extrapolation in the original coordinates with inner optimization in the transformed coordinates to exploit hidden convexity. Under stated regularity assumptions, the paper develops equivalence and optimality results for the reformulation and claims complexity bounds matching optimal or best-known rates across several convex and nonconvex settings. Empirical validation includes synthetic convex QCQPs and constrained PCA on the Stiefel manifold using DIGITS and LFW data. Comparisons with projection-based, penalty, augmented Lagrangian, and retraction-based methods assess objective values, constraint violations, and runtime. The reported results suggest competitive solution quality and feasibility, with runtime advantages on the tested instances.
Critical strengths
- Hom-PALM combines homeomorphic treatment of convex inequalities with augmented Lagrangian handling of equalities. Particularly interesting is Hom-APG’s separation of regularization and extrapolation in the original coordinates from inner optimization over the ball. This provides a concrete mechanism for exploiting hidden convexity while avoiding expensive projections onto the original inequality-feasible region. The design addresses a meaningful limitation of existing reparameterization methods and is the paper’s strongest conceptual contribution.
- The experiments cover convex QCQPs and constrained PCA with nonlinear orthogonality constraints, evaluating objective quality and constraint violations against runtime. Comparisons include both general optimization methods and specialized retraction methods. The reported results provide initial evidence that the proposed decomposition can offer practical computational benefits while maintaining solution quality and feasibility, giving the framework value beyond its theoretical motivation.
Critical weaknesses
-
The proposed mapping is not adequately covered by the theoretical assumptions. The convergence analysis requires a globally differentiable homeomorphism with a nonsingular, Lipschitz-continuous Jacobian. However, the proposed gauge map, after subtracting the interior reference point, is positively homogeneous of degree one; differentiability at the origin would therefore force it to be linear. The general gauge construction consequently fails these assumptions even for smooth, non-spherical feasible regions. Although the paper acknowledges regularity limitations and discusses smoothing, it does not establish a suitable construction or quantify how approximation error and derivative constants affect the claimed complexity. This leaves a consequential gap between the conditional theory and the advertised applicability to general convex inequalities.
-
The central accelerated complexity guarantee has unresolved proof gaps. Proposition E.3 asserts geometric contraction for step sizes including , although projected gradient descent can oscillate at that endpoint even for a strongly convex quadratic under the identity mapping. More substantially, Theorem 3 applies an unconstrained Catalyst warm-start formula to an objective containing the feasible-set indicator. The resulting initialization can leave the feasible region and need not define a feasible starting point in the mapped domain. These issues undermine the inner convergence and work bounds used to establish the overall accelerated complexity. Corrected step sizes and alternative feasible warm starts may repair the analysis, but preserving the stated complexity requires a revised proof. Since acceleration is a principal theoretical contribution, this uncertainty materially affects my recommendation.
Questions for authors
- Regularity of the proposed gauge mapping (Appendix C.2). Which concrete mapping satisfies the differentiability, nonsingular-Jacobian, and Lipschitz-Jacobian assumptions for the problem classes covered by the claimed guarantees? For the proposed gauge construction, is positively homogeneous of degree one. Differentiability at zero would imply , forcing to be linear. Thus, the general gauge map fails the stated assumptions even for smooth, non-spherical feasible regions. How does the analysis cover the mapping actually used? If smoothing is intended, can the authors quantify its approximation error, its effect on feasibility, and the dependence of the derivative constants—and therefore the final complexity on the smoothing accuracy?
- Step sizes and contraction in Proposition E.3 (p. 41). How should the stated linear-convergence result be corrected? It permits and gives a contraction factor independent of the chosen . Consider , , and f(z)=\tfrac12 z_1^2+z_2^2. Here . With and , the iterates alternate between and , contradicting the claimed contraction. Moreover, arbitrarily small positive step sizes cannot share the stated fixed contraction factor. Can the authors provide the corrected step-size range and contraction factor, including their dependence on the mapping constants, and propagate these changes through Theorem 3 and the subsequent complexity bounds?
- Feasibility of the Catalyst warm start in Theorem 3 (p. 42). How is the initialization z_{k,0}=\Psi^{-1}!\left(x_k+ \frac{\lambda_{\rm reg}}{\lambda_{\rm reg}+\mu_f}(y_k-y_{k-1})\right) guaranteed to belong to ? The argument invokes a smooth, unconstrained warm-start formula, whereas the objective here contains . The extrapolated point can leave , even when , so it need not yield a feasible inner initialization. The composite variant in the cited Catalyst analysis involves a proximal step, which becomes a projection onto . Can the authors specify a feasible initialization that preserves the projection-free implementation and prove the required inner-iteration bound uniformly over the outer iterations?
- Normalization of the proximal parameter in Theorems 6–7 (pp. 46–47). Are the proximal coefficients in Eqs. (51)–(52) inverted relative to the cited result? Melo et al. use
In Algorithm 6’s normalization, this corresponds to a proximal coefficient , whereas Eq. (51) specifies . This affects strong convexity: with , equality , , and , the stated coefficient is , leaving curvature along at the origin. What are the correct parameters, and should Theorem 7 use the transformed weak-convexity constant ? Do the corrected parameters preserve the claimed complexity? 5. Applicability of the cited nonconvex ALM result to the stated algorithm (Theorems 6–7). Can the authors give an explicit correspondence between their algorithm and the algorithm analyzed by Melo et al.? The cited method keeps the penalty fixed during a sequence of primal–dual iterations, obtains a suitably refined approximate stationary point, and doubles the penalty when the feasibility test fails. Eqs. (51)–(52), however, prescribe at every iteration. Where are the required stopping criteria and refinement steps incorporated? If instead indexes penalty stages, please specify the nested iteration structure and justify its total inner complexity. 6. Boundary derivatives and the transfer of optimality conditions (Eq. (15), p. 31; Lemmas D.14, D.15, and D.17). What justifies the identities and ? Agreement of constraint values on the boundary does not imply agreement of derivatives. For example, take and g(x)=\sqrt{1+|x|^2}-\sqrt2, which defines the unit ball. On its boundary, , and its Hessian is not . Consequently, the multiplier identification and subsequent Hessian identities do not follow as written. Can the authors provide corrected multiplier and second-order arguments, with the necessary constraint qualifications, and identify which landscape conclusions remain valid? 7. Exact versus inexact trajectory equivalence in Lemma E.4 (p. 44). Is this lemma intended only for exact subproblem solves? Algorithm 1 permits approximate inner solutions, while Lemma E.4 asserts that every mapped iterate is an exact minimizer of the corresponding PALM subproblem. For the finite inner solves used in the complexity analysis, can the authors state the appropriate inexact correspondence, specify how the required errors or residuals transfer under , and identify the convergence theorem that applies to that inexact sequence? 8. Applicability of Assumption 5 to the Stiefel experiments (Eq. (65), p. 52). Have the authors verified the global regularity condition for the experimental feasible sets? For , one has and . If the box and group-budget constraints permit X=0, the right-hand side of Eq. (65) is zero while its left-hand side is positive. Do the actual experimental bounds exclude zero, and does the condition hold throughout the resulting set? If these experiments lie outside the theorem’s assumptions, can the authors clarify the scope of the theoretical guarantee?
6 comments
Part II
Question 1
Regularity of the proposed gauge mapping (Appendix C.2). Which concrete mapping satisfies the differentiability, nonsingular-Jacobian, and Lipschitz-Jacobian assumptions … If smoothing is intended, can the authors quantify … complexity … on the smoothing accuracy?
Response. Refer to the response to Weakness 1.
Question 2
Step sizes and contraction in Proposition E.3 (p. 41) … With and , the iterates alternate … Can the authors provide the corrected step-size range … and propagate these changes through Theorem 3 …?
Response. Thank you for the careful counterexample. The issue is not a failure of the Hom-APG/PALM argument itself, but a proof typo inherited from prior work: when adapting the Hom-PGD contraction proof from [1] into our appendix, we mistakenly kept the step-size range and the contraction factor formula from that manuscript. On the ball with a proximal term, the valid range is with (the missing factor in is the same slip). This removes the non-contractive regime behind the – oscillation at (see also Weakness 2).
Downstream bounds. After correcting Prop. E.3, the per-step contraction changes by at most a constant (e.g. a factor of two in when ). The Hom-APG proof in Appendix E (Thm. 3) and the Hom-PALM total-complexity statements keep the same asymptotic -orders; only absolute constants in the / expressions are updated (blue in the revision).
References. [1] C. Liu, E. Liang, M. Chen. Fast projection-free approach (without optimization oracle) for optimization over compact convex set. Advances in Neural Information Processing Systems, 2025.
Question 3
Feasibility of the Catalyst warm start in Theorem 3 (p. 42). How is the initialization guaranteed to belong to ? …
Response. Same as Weakness 2 (2). The warm-start point need not lie in beforehand: we use when needed. Hom-PGD (Alg. 4) projects onto at every step, so is always well posed. Extrapolation in Catalyst may leave in -space; the inner solve remains a ball-constrained problem in .
Question 4
Normalization of the proximal parameter in Theorems 6–7 (pp. 46–47). Are the proximal coefficients in Eqs. (51)–(52) inverted relative to the cited result? …
Response. (1) Typo. Thank you—the proximal coefficients in Eqs. (51)–(52) were inverted. We corrected Appendix E, Thms. 6–7 to and , matching Melo et al. [1].
(2) Why in Thm. 7. Hom-PALM runs in , but we map iterates to and cite PALM$(\theta)$ in -space; schedules use the original-space weak-convexity constant ( on the trajectory).
(3) Complexity. Corrected coefficients restore strong convexity of the ACG subproblems under [1]’s assumptions. The outer rate remains ; only hidden constants change.
References. [1] J. G. Melo, R. D. C. Monteiro, H. Wang. A proximal augmented Lagrangian method for linearly constrained nonconvex composite optimization problems. Journal of Optimization Theory and Applications, 202(1):388–420, 2024.
Part III
Question 5
- Applicability of the cited nonconvex ALM result to the stated algorithm (Theorems 6--7). Can the authors give an explicit correspondence between their algorithm and the algorithm analyzed by Melo et al.? … Where are the required stopping criteria and refinement steps incorporated?
Response. (1) Correspondence with Melo et al. [1]. The reviewer's reading is correct. Our Thms. 6--7 are not " at every outer iteration"; we mis-stated the schedule. The correct template is Melo's static + dynamic -IPAAL: (i) static stage—fix , run PALM$(\theta)(\theta)$ with , each primal step solved by ACG until [1, Eq. (32)] (Alg. 7) plus refinement, and stop the stage when ; (ii) dynamic outer loop—if (feasibility in [1, Eq. (3)]), set and repeat; otherwise output (with for our Def. E.6 / approximate stationarity in Appendix E). Mapping: Melo , , static outer our PALM primal--dual steps, ACG inner loop. Hom-PALM only replaces by in ACG. We revised Appendix E, Thms. 6--7 accordingly (blue).
Inner and total complexity. Per-stage outer/ACG bounds and the doubling penalty count are taken from [1, Thms. 4--6]; we do not re-prove them. The total ACG-iteration complexity remains (sharp version under Slater).
(2) Scope. The nonconvex linear-equality results are an extension of the homeomorphic PALM framework. Our primary theory and experiments concern the convex setting (Hom-APG / Hom-PALM with proved accelerated rates).
References. [1] J. G. Melo, R. D. C. Monteiro, and H. Wang. A proximal augmented Lagrangian method for linearly constrained nonconvex composite optimization problems. Journal of Optimization Theory and Applications, 202(1):388--420, 2024.
Question 6
- Boundary derivatives and the transfer of optimality conditions (Eq. (15), p. 31; Lemmas D.14, D.15, and D.17). What justifies the identities and ? Agreement of constraint values on the boundary does not imply agreement of derivatives. For example, take and , which defines the unit ball. On its boundary, , and its Hessian is not . Consequently, the multiplier identification and subsequent Hessian identities do not follow as written. Can the authors provide corrected multiplier and second-order arguments, with the necessary constraint qualifications, and identify which landscape conclusions remain valid?
Response. You are correct: the global identities , , and were not justified.
Revised KKT material (blue in the revision). See Appendix D: the KKT systems in - and -space (Appendix D, Eqs. KKT of P / KKT of H) and subsection "Relationships of KKT Stationary Points"—Lemma D.14; revised Lemma D.15 (, on $
tial\mathcal B$); Lemmas D.16 and D.18 (forward direction); Remark D.19.
Summary of fixes. (i) No pointwise ; active constraints use the normal cone of . (ii) Multipliers transfer through and the -- formula above, not . (iii) Second-order conditions use the chain-rule Hessian identity and Lemma D.14(iii). First-order KKT equivalence (under strict complementarity) and the forward second-order/non-degeneracy statements used for Hom-PGD remain valid in the revision.
Part I
We are grateful to Reviewer J6q6 for the deep technical review: gauge vs. global C1 assumptions, Prop. E.3 step sizes, Catalyst warm starts, Melo Thms. 6–7, KKT boundary transfers, Lemma E.4 vs. inexact Hom-PALM, and Assumption 5 on Stiefel data. These points improved appendix statements and clarified experimental scope.
Weakness 1
Response. We thank the reviewer for this careful reading. Your understanding is largely correct, and we agree that our earlier draft did not state the scope of the guarantees and the smoothing trade-off with sufficient explicitness. In particular, a degree-one positively homogeneous gauge cannot be differentiable at 0 unless it is linear, so Prop. 3.2’s raw map is not an admissible Ψ in the literal Sec. 4 statements; our rates are conditional on a smooth surrogate while reported iterates still use the exact gauge.
(1) What the theorems assume (and do not claim). All complexity statements in Sec. 4 ("Theoretical Guarantees and Complexity") are conditional: they apply to a homeomorphism Ψ that is invertible on Rn with a nonsingular Jacobian JΨ that is globally Lipschitz. The raw gauge map in Prop. 3.2 does not satisfy this globally (it is twice differentiable only almost everywhere; Prop. B.4 in Appendix B). We therefore do not claim that the printed ϵ-order bounds hold verbatim for the nonsmooth raw gauge on polyhedral sets without further qualification.
(2) A concrete way out, with quantified trade-off (Appendix E.5). Following Liu et al. [Hom-PGD, 2025], we analyze log-sum-exp smoothing with parameter w>0, defining a C2 surrogate Ψw and pullback hw=f∘Ψw used in inner gradients. Appendix E.5 records explicitly:
(3) Theory vs. practice. Proved acceleration rates are for the smoothed inner model at fixed w, not a blanket transfer to the raw nonsmooth gauge. Experiments use a hybrid pipeline—exact Ψ for x and feasibility, smoothed gradients for inner Hom-APG—with a small fixed w (Appendix F).
(4) Where this is explicit in the revision (blue). Sec. 4 General Assumptions; Appendix E.5; Sec. 6 (Limitations), third item.
Weakness 2
Response. (1) Step size (Prop. E.3). The valid constant step-size range is α∈(0,1/Lh], with contraction factor σ=1−αμfκ1/2. The earlier range (0,2/Lh] came from a typo in the Hom-PGD proof in [1] (including the oscillatory example at α=1 when 2/Lh≥1). We have corrected Prop. E.3 in Appendix E and carried the factor 1/2 through the Hom-APG complexity proof (blue in the revision).
(2) Warm start (Thm. 3 / Hom-APG). The Catalyst formula zk,0=Ψ−1(⋯) is a suggested initializer. The inner subproblem is minz∈BQk(z), solved by Hom-PGD (Alg. 4), which projects onto B every step. If Ψ−1(⋅)∈/B (e.g., extrapolation leaves C in x-space), we set zk,0=ΠB(Ψ−1(⋯))—O(n), same order as one ball projection. Feasibility of the warm start is therefore not required; Catalyst/inexact-inner analysis is unchanged up to constants. We will state this projection explicitly next to the warm-start line.
References. [1] C. Liu, E. Liang, M. Chen. Fast projection-free approach (without optimization oracle) for optimization over compact convex set. Advances in Neural Information Processing Systems, 2025.