acceptodds
Under review as a conference paper at ICLR 2027

A Projection-Free Homeomorphic Lagrangian Method for Optimization with Convex Inequality and General Equality Constraints

Abstract

Constrained optimization with convex inequality and general equality constraints arises throughout machine learning, power systems, and scientific computing. Classical first-order methods require either expensive projections onto the feasible region or optimization oracles, whereas recent projection-free reparameterization methods focus on problems without equality constraints. We propose **Hom-PALM**, a Homeomorphic Proximal Augmented Lagrangian Method that bridges this gap by reparameterizing inequality constraints onto the unit ball via a homeomorphism while handling equality constraints through an augmented Lagrangian framework in the original domain. This decomposition enables efficient ball-constrained subproblem solving while preserving the structure required for Lagrangian methods. A key challenge is that a naive combination of reparameterization with the Lagrangian framework yields suboptimal rates: each Lagrangian iteration requires solving a subproblem using an accelerated-based method; yet the homeomorphic mapping renders subproblems nonconvex with only hidden convexity, precluding standard accelerated rates. As our main technical contribution, we extend first-order acceleration to the projection-free setting without optimization oracles and integrate it within Hom-PALM, achieving **optimal** convergence rates for convex problems and best-known rates for nonconvex problems. For instance, Hom-PALM attains a rate of for nonconvex objectives with convex inequality and *nonlinear* equality constraints, matching the best-known complexity but with per-iteration cost of only without optimization oracles. We validate Hom-PALM on convex QCQP and Stiefel manifold optimization, demonstrating competitive performance.

Primary area:
optimization
Keywords:
Constrained Optimization, Homeomorphism, Projection Free, Augmented Lagrangian, Proximal Methods

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_J6q6OpenReview ↗
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
  1. 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.
  2. 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
  1. 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.

  2. The central accelerated complexity guarantee has unresolved proof gaps. Proposition E.3 asserts geometric contraction for step sizes including 2/Lh2/L_h, 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
  1. 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, T(z)=Ψ(z)−x∘T(z)=\Psi(z)-x^\circ is positively homogeneous of degree one. Differentiability at zero would imply T(z)=DT(0)zT(z)=DT(0)z, forcing TT 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?
  2. Step sizes and contraction in Proposition E.3 (p. 41). How should the stated linear-convergence result be corrected? It permits α=2/Lh\alpha=2/L_h and gives a contraction factor independent of the chosen α\alpha. Consider Ψ=id\Psi=\mathrm{id}, C=BC=B, and f(z)=\tfrac12 z_1^2+z_2^2. Here Lh=2L_h=2. With α=1\alpha=1 and z0=(0,12)z_0=(0,\tfrac12), the iterates alternate between (0,12)(0,\tfrac12) and (0,−12)(0,-\tfrac12), 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?
  3. 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 BB? The argument invokes a smooth, unconstrained warm-start formula, whereas the objective here contains ICI_C. The extrapolated point can leave CC, even when Ψ=id\Psi=\mathrm{id}, 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 CC. 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?
  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? Melo et al. use
λθLcθ(x)+12∥x−xk∥2,λθ=τθ/ℓf.\lambda_\theta \mathcal L_c^\theta(x)+\tfrac12\|x-x_k\|^2, \qquad \lambda_\theta=\tau_\theta/\ell_f.

In Algorithm 6’s normalization, this corresponds to a proximal coefficient 1/λθ=ℓf/τθ1/\lambda_\theta=\ell_f/\tau_\theta, whereas Eq. (51) specifies τθ/ℓf\tau_\theta/\ell_f. This affects strong convexity: with f(x)=−1+x22f(x)=-\sqrt{1+x_2^2}, equality x1=0x_1=0, Ψ=id\Psi=\mathrm{id}, and θ=1/2\theta=1/2, the stated coefficient is 1/881/88, leaving curvature −87/88-87/88 along x2x_2 at the origin. What are the correct parameters, and should Theorem 7 use the transformed weak-convexity constant ℓh\ell_h? 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 ρk+1=2ρk\rho_{k+1}=2\rho_k at every iteration. Where are the required stopping criteria and refinement steps incorporated? If kk 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 ∇Gi(z)=2z\nabla G_i(z)=2z and ∇2Gi(z)=2I\nabla^2G_i(z)=2I? Agreement of constraint values on the boundary does not imply agreement of derivatives. For example, take Ψ=id\Psi=\mathrm{id} and g(x)=\sqrt{1+|x|^2}-\sqrt2, which defines the unit ball. On its boundary, ∇g(z)=z/2\nabla g(z)=z/\sqrt2, and its Hessian is not 2I2I. Consequently, the multiplier identification ν=∑iλi\nu=\sum_i\lambda_i 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 Ψ\Psi, 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 ϕ(X)=X⊤X−I\phi(X)=X^\top X-I, one has ϕ(0)=−I\phi(0)=-I and Jϕ(0)=0J_\phi(0)=0. 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

We are grateful to Reviewer J6q6 for the deep technical review: gauge vs. global C1C^1 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

The proposed gauge construction is not covered by the theory as stated. ... The gap between the conditional theory and the advertised applicability on general convex inequalities is not closed in the current draft.

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\mathbf{0} unless it is linear, so Prop. 3.2’s raw map is not an admissible Ψ\Psi 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 Ψ\Psi that is invertible on Rn\mathbb{R}^n with a nonsingular Jacobian JΨ\mathrm{J}_\Psi 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 ϵ\epsilon-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>0w>0, defining a C2C^2 surrogate Ψw\Psi_w and pullback hw=f∘Ψwh_w=f\circ\Psi_w used in inner gradients. Appendix E.5 records explicitly:

  • Feasibility. Reported iterates use the exact gauge Ψ\Psi, so primal feasibility for the original problem (Eq. (1)) is unchanged by ww.
  • Approximation / stationarity. Inner steps optimize a smoothed model; gradient error relative to the exact pullback is O(w)\mathcal{O}(w).
  • Hidden constants. LΨ(w)=O(1/w)L_{\Psi}(w)=\mathcal{O}(1/w) as w→0+w\to 0^+.
  • ϵ\epsilon-orders (E.5). At fixed w>0w>0, the ϵ\epsilon-exponents in Thm. 1 / Prop. 4.1 are unchanged, but inner cost scales with LΨ(w)=O(1/w)L_{\Psi}(w)=\mathcal{O}(1/w). Coupling w=Θ(ϵ)w=\Theta(\epsilon) can worsen the total inner-work ϵ\epsilon-order in worst-case bookkeeping (e.g. extra O~(ϵ−1/2)\widetilde{\mathcal{O}}(\epsilon^{-1/2}) via MkM_k). We prove rates at fixed ww; experiments use small fixed ww.

(3) Theory vs. practice. Proved acceleration rates are for the smoothed inner model at fixed ww, not a blanket transfer to the raw nonsmooth gauge. Experiments use a hybrid pipeline—exact Ψ\Psi for xx and feasibility, smoothed gradients for inner Hom-APG—with a small fixed ww (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

Important gaps remain in the accelerated complexity proof. In Proposition E.3, the contraction proof permits step sizes that include α=2/Lh\alpha=2/L_h … Theorem 3 applies an unconstrained Catalyst warm-start formula to an objective containing a feasible-set indicator…

Response. (1) Step size (Prop. E.3). The valid constant step-size range is α∈(0,1/Lh]\alpha\in(0,1/L_h], with contraction factor σ=1−αμfκ1/2\sigma=1-\alpha\mu_f\kappa_1/2. The earlier range (0,2/Lh](0,2/L_h] came from a typo in the Hom-PGD proof in [1] (including the oscillatory example at α=1\alpha=1 when 2/Lh≥12/L_h\ge 1). We have corrected Prop. E.3 in Appendix E and carried the factor 1/21/2 through the Hom-APG complexity proof (blue in the revision).

(2) Warm start (Thm. 3 / Hom-APG). The Catalyst formula zk,0=Ψ−1(⋯ )z_{k,0}=\Psi^{-1}(\cdots) is a suggested initializer. The inner subproblem is min⁡z∈BQ~k(z)\min_{z\in\mathcal{B}}\widetilde{Q}_k(z), solved by Hom-PGD (Alg. 4), which projects onto B\mathcal{B} every step. If Ψ−1(⋅)∉B\Psi^{-1}(\cdot)\notin\mathcal{B} (e.g., extrapolation leaves C\mathcal{C} in xx-space), we set zk,0=ΠB(Ψ−1(⋯ ))z_{k,0}=\Pi_{\mathcal{B}}(\Psi^{-1}(\cdots))—O(n)\mathcal{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.

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 α=1\alpha=1 and z0=(0,1/2)z_0=(0,1/2), 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 (0,2/Lh](0,2/L_h] and the contraction factor formula from that manuscript. On the ball with a proximal term, the valid range is α∈(0,1/Lh]\alpha\in(0,1/L_h] with σ=1−αμfκ1/2\sigma=1-\alpha\mu_f\kappa_1/2 (the missing factor 1/21/2 in σ\sigma is the same slip). This removes the non-contractive regime behind the (0,12)(0,\tfrac12)–(0,−12)(0,-\tfrac12) oscillation at α=1\alpha=1 (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 1−σ1-\sigma when α=1/Lh\alpha=1/L_h). The Hom-APG proof in Appendix E (Thm. 3) and the Hom-PALM total-complexity statements keep the same asymptotic ϵ\epsilon-orders; only absolute constants in the O(⋅)\mathcal{O}(\cdot) / O~(⋅)\widetilde{\mathcal{O}}(\cdot) 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 zk,0=Ψ−1(⋯ )z_{k,0}=\Psi^{-1}(\cdots) guaranteed to belong to B\mathcal{B}? …

Response. Same as Weakness 2 (2). The warm-start point need not lie in B\mathcal{B} beforehand: we use zk,0=ΠB(Ψ−1(⋯ ))z_{k,0}=\Pi_{\mathcal{B}}(\Psi^{-1}(\cdots)) when needed. Hom-PGD (Alg. 4) projects onto B\mathcal{B} at every step, so min⁡z∈BQ~k(z)\min_{z\in\mathcal{B}}\widetilde{Q}_k(z) is always well posed. Extrapolation in Catalyst may leave C\mathcal{C} in xx-space; the inner solve remains a ball-constrained problem in zz.

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 αk=ℓf/τθ\alpha_k=\ell_f/\tau_\theta and βk=ℓf/τθ\beta_k=\ell_f/\tau_\theta, matching Melo et al. [1].

(2) Why ℓf\ell_f in Thm. 7. Hom-PALM runs in zz, but we map iterates to x=Ψ(z)x=\Psi(z) and cite PALM$(\theta)$ in xx-space; schedules use the original-space weak-convexity constant ℓf\ell_f (βk=αk\beta_k=\alpha_k on the trajectory).

(3) Complexity. Corrected coefficients restore strong convexity of the ACG subproblems under [1]’s assumptions. The outer rate remains O~(ϵ−2.5)\widetilde{\mathcal{O}}(\epsilon^{-2.5}); 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.

Question 5

  1. 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 "ρk+1=2ρk\rho_{k+1}=2\rho_k at every outer iteration"; we mis-stated the schedule. The correct template is Melo's static + dynamic θ\theta-IPAAL: (i) static stage—fix ρ\rho, run PALM$(\theta)/Hom−PALM/Hom-PALM(\theta)$ with α=β=ℓf/τθ\alpha=\beta=\ell_f/\tau_\theta, each primal step solved by ACG until [1, Eq. (32)] (Alg. 7) plus refinement, and stop the stage when ∥v^∥≤ρ^\|\hat v\|\le\hat\rho; (ii) dynamic outer loop—if ∥φ(x^)∥>η^\|\varphi(\hat x)\|>\hat\eta (feasibility in [1, Eq. (3)]), set ρ←2ρ\rho\leftarrow 2\rho and repeat; otherwise output (with ρ^=η^=ϵ\hat\rho=\hat\eta=\epsilon for our Def. E.6 / approximate stationarity in Appendix E). Mapping: Melo c↔ρc\leftrightarrow\rho, λ=τθ/m↔α=ℓf/τθ\lambda=\tau_\theta/m\leftrightarrow\alpha=\ell_f/\tau_\theta, static outer k↔k\leftrightarrow our PALM primal--dual steps, ACG ↔\leftrightarrow inner loop. Hom-PALM only replaces ΠC\Pi_{\mathcal{C}} by ΠB\Pi_{\mathcal{B}} 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 O~(ϵ−2.5)\widetilde{\mathcal{O}}(\epsilon^{-2.5}) (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

  1. Boundary derivatives and the transfer of optimality conditions (Eq. (15), p. 31; Lemmas D.14, D.15, and D.17). What justifies the identities ∇Gi(z)=2z\nabla G_i(z)=2z and ∇2Gi(z)=2I\nabla^2 G_i(z)=2I? Agreement of constraint values on the boundary does not imply agreement of derivatives. For example, take Ψ=id\Psi=\mathrm{id} and g(x)=1+∣x∣2−2g(x)=\sqrt{1+|x|^2}-\sqrt{2}, which defines the unit ball. On its boundary, ∇g(z)=z/2\nabla g(z)=z/\sqrt{2}, and its Hessian is not 2I2I. Consequently, the multiplier identification ν=∑iλi\nu=\sum_i\lambda_i 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 ∇Gi=2z\nabla G_i=2z, ∇2Gi=2I\nabla^2G_i=2I, and ν=∑iλi\nu=\sum_i\lambda_i were not justified.

Revised KKT material (blue in the revision). See Appendix D: the KKT systems in xx- and zz-space (Appendix D, Eqs. KKT of P / KKT of H) and subsection "Relationships of KKT Stationary Points"—Lemma D.14; revised Lemma D.15 (ν∗=12∑i∈Aλi∗μi\nu^*=\frac12\sum_{i\in\mathcal A}\lambda_i^*\mu_i, ∇Gi=μiz\nabla G_i=\mu_i z on $

tial\mathcal B$); Lemmas D.16 and D.18 (forward direction); Remark D.19.

Summary of fixes. (i) No pointwise ∇Gi=2z\nabla G_i=2z; active constraints use the normal cone of B\mathcal B. (ii) Multipliers transfer through Jψ⊤\mathrm J_\psi^\top and the μi\mu_i--ν∗\nu^* formula above, not ν=∑iλi\nu=\sum_i\lambda_i. (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.

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

This paper proposes a projection-free method the authors call a Homeomorphic Proximal Augmented Lagrangian Method (Hom-PALM) for solving optimization problems of the form

min⁡{f(x):g(x)≤0,ϕ(x)=0}.\min \lbrace f(x) : g(x) \leq 0, \phi (x) = 0 \rbrace.

This follows a more recent line of work that seeks to sidestep costly projection steps that are typically used to restore feasibility in first order methods. The approach in this work can be viewed as an extension of a recent paper from Liu et al. (NeurIPS, 2025) on a method called Hom-PGD, which only handles the inequality constrained problem

min⁡x∈Cf(x),C={x:g(x)≤0}\min_{x \in \mathcal{C}} f(x), \qquad \mathcal{C} = \lbrace x : g(x) \leq 0 \rbrace

by using a homeomorphism C=Ψ(B)\mathcal{C} = \Psi (\mathcal{B}) to transform it to a problem over the unit ball B\mathcal{B}.

The authors assert the following claims:

  • For strongly convex and general convex objective functions, their approach attains optimal convergence rates of O~(ϵ−1/2)\widetilde{O}(\epsilon^{-1/2}) and O~(ϵ−1)\widetilde{O}(\epsilon^{-1}), respectively.
  • For nonconvex objective functions, they claim convergence rates of O~(ϵ−2.5)\widetilde{O}(\epsilon^{-2.5}) for problems with linear equality constraints, and O~(ϵ−3.5)\widetilde{O}(\epsilon^{-3.5}) for problems with nonlinear equality constraints.

Further, it is claimed that all of these results are attained while paying O~(n2)\widetilde{O}(n^2) per-iteration cost.

Numerical results are presented on convex QCQP and nonlinear Stiefel manifold optimization.

Critical strengths

Handling general convex inequality constraints without needing to pay the cost of projecting onto the feasible set is a very natural question. If one could achieve the optimal rates at the claimed per-iteration cost, the methods in this paper would be quite interesting.

Critical weaknesses

My primary concern is that the paper is not correct as written, and that the issues with the paper invalidate the main claims. It appears that the issues could be corrected, but I am not certain that the convergence rates will be salvaged. A secondary concern is that, putting correctness aside, the contribution is more conceptual than technical, as many of the ideas are a combination of existing approaches.

There are also submission guidelines violations the AI usage statement is omitted.

W1. The convergence rates for convex optimization do not hold for problems with corners, e.g., boxes, polytopes. These are also the types of instances considered for the numerical experiments (QCQP with box constraints).

Hom-PALM calls Hom-APG on each subproblem, and Hom-APG itself uses Hom-PGD to solve its inner problems. Every gradient step in the approach for convex optimization is a Hom-PGD step.

Hom-PGD itself is projected gradient descent on the transformed objective h(x)=f(Ψ(x))h(x) = f(\Psi(x)) over the unit ball B\mathcal{B}, and the associated rates depend on the descent lemma. The challenge is that hh is only LL-smooth if the Jacobian of the change of variables is Lipschitz (see, item 3 of the assumptions on Ψ\Psi in Appendix C.2). If we denote the smoothness constant of h(x)h(x) by LhL_h, the authors assert in Lemma D.1(ii) that Lh≤κ22+LΨLf,0L_h \leq \kappa_2^2 + L_{\Psi} L_{f, 0}.

Virtually every rate in the paper depends on this parameter, see

  • Theorem 1
  • Prop E.3
  • Theorem 7
  • Theorem 9 and their proofs.

The problem is the hypothesis of Lemma D.1 fails -- ∇h\nabla h is Lipschits only if JΨJ_{\Psi} exists everywhere, and is Lipschitz. Let yy be a corner of C (i.e., C has two linearly independent outward normals at yy). A differentiable change of variables maps normal directions linearly. The ball's normal cones are single rays, and a linear map sends a ray to a ray. Therefore, the image C=Ψ(B)C = \Psi (\mathcal{B}) cannot have a 2d normal cone, which is what a corner is. In short, no admissible Ψ\Psi exists for sets with corners, and in particular, on such sets one has LΨ=∞L_{\Psi} = \infty or κ1=0\kappa_1 = 0, so cΨ=0c_{\Psi} = 0. It seems the results do not hold for such problems, which is a substantial weakening of the results, and I don't see an immediate fix.

W2. Hom-APG is just catalyst with Hom-PGD for the inner solves. The authors acknowledge this, but it makes the contribution weaker.

W3. The experiments do very little to support the claims: the baselines solve their constrained subproblems are solved using off-the-shelf solvers, and the solve times are not reported, and all QCQP instances involve a diagonal quadratic term.

Questions for authors
  1. What are the solution times for MOSEK and IPOPT?

  2. Is there any convex C\mathcal{C} with corners, for which your assumptions hold for some Ψ\Psi? If not, which of your theorems apply to your experiments.

  3. Can you quantify the practical gains from Hom-APG over Hom-PGD?

  4. Can you be more explicit about how you generate the instances for the numerical results? I could not find the exact details for all.

5 comments

We thank Reviewer XQqU for the careful review on correctness for cornered sets, technical novelty, Catalyst vs. Hom-APG, experiments, and checklist compliance. Your questions led us to separate conditional Jacobian assumptions, smoothing and hybrid implementation, and which theorems apply to which benchmarks.

Weakness 1

My primary concern is that the paper is not correct as written … W1. The convergence rates for convex optimization do not hold for problems with corners, e.g., boxes, polytopes … no admissible Ψ\Psi exists for sets with corners … Lh=∞L_h=\infty or κ1=0\kappa_1=0 …

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.

(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 Ψ\Psi that is invertible on Rn\mathbb{R}^n with a nonsingular Jacobian JΨ\mathrm{J}_\Psi 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 ϵ\epsilon-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>0w>0, defining a C2C^2 surrogate Ψw\Psi_w and pullback hw=f∘Ψwh_w=f\circ\Psi_w used in inner gradients. Appendix E.5 records explicitly:

  • Feasibility. Reported iterates use the exact gauge Ψ\Psi, so primal feasibility for the original problem (Eq. (1)) is unchanged by ww.
  • Approximation / stationarity. Inner steps optimize a smoothed model; gradient error relative to the exact pullback is O(w)\mathcal{O}(w).
  • Hidden constants. LΨ(w)=O(1/w)L_{\Psi}(w)=\mathcal{O}(1/w) as w→0+w\to 0^+.
  • ϵ\epsilon-orders (E.5). At fixed w>0w>0, the ϵ\epsilon-exponents in Thm. 1 / Prop. 4.1 are unchanged, but inner cost scales with LΨ(w)=O(1/w)L_{\Psi}(w)=\mathcal{O}(1/w). Coupling w=Θ(ϵ)w=\Theta(\epsilon) can worsen the total inner-work ϵ\epsilon-order in worst-case bookkeeping (e.g. extra O~(ϵ−1/2)\widetilde{\mathcal{O}}(\epsilon^{-1/2}) via MkM_k). We prove rates at fixed ww; experiments use small fixed ww.

(3) Theory vs. practice. Proved acceleration rates are for the smoothed inner model at fixed ww, not a blanket transfer to the raw nonsmooth gauge. Experiments use a hybrid pipeline—exact Ψ\Psi for xx and feasibility, smoothed gradients for inner Hom-APG—with a small fixed ww (Appendix F).

(4) Where this is explicit in the revision (blue). Sec. 4 General Assumptions; Appendix E.5; Sec. 6 (Limitations), third item.

References.

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.

Weakness 2

A secondary concern is that, putting correctness aside, the contribution is more conceptual than technical, as many of the ideas are a combination of existing approaches.

Response. We agree the high-level ingredients are familiar: gauge reparameterization, proximal ALM [LQ21], and Catalyst-style acceleration. Our goal is not a new outer template, but to run projection-free PALM for general convex inequalities together with equalities, with proved accelerated outer rates when the inner problem is solved to the accuracy Li–Qu [LQ21] require.

The technical gap is specific. After Ψ\Psi, each PALM primal subproblem is nonconvex in zz though convex in x=Ψ(z)x=\Psi(z) (hidden convexity). [LQ21] assume a convex inner oracle, so a naive “PALM + gauge” citation does not yield Thm. 1. Hom-APG is built for this ball landscape (regularization/extrapolation in xx-space, proximal steps on B\mathcal{B}); we prove it supplies the inner accuracy for the inexact-PALM route (Sec. 4; Appendix E, Cor. 5).

Supporting pieces beyond outer–inner coupling include landscape/KKT under Ψ\Psi (Appendix D), gauge regularity and smoothing trade-offs (Appendix B, E.5), and Melo-type extensions under nonlinear equalities (Sec. 4.2; Appendix E.4–E.5).

Weakness 3

W2. Hom-APG is just catalyst with Hom-PGD for the inner solves. The authors acknowledge this, but, if I understand correctly, this still makes the contribution weaker.

Response. Hom-APG does follow the Catalyst template [1] with Hom-PGD as the inner loop. We do not claim Catalyst as new. We claim (i) an accelerated inner solver that stays on B\mathcal{B} and avoids ΠC\Pi_{\mathcal{C}}, and (ii) a proof that this pairing fits Hom-PALM after gauge reparameterization.

Standard Catalyst analysis assumes a convex inner problem and a proximal step on C\mathcal{C}. Here the inner problem is nonconvex in zz, so our rate argument is not a direct citation of [1] (Appendix E). Hom-PGD alone does not deliver the accelerated inner rate Hom-PALM needs; Hom-APG does (Prop. 4.1). Question 3 reports an ablation (plain vs. accelerated Hom-PGD) quantifying the inner speedup.

References. [1] H. Lin, J. Mairal, Z. Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice. Journal of Machine Learning Research, 18(212):1–54, 2018.

Weakness 4

W3. The experiments do little to support the claims … baselines solve constrained subproblems using off-the-shelf solvers … solve times are not reported … all QCQP instances involve a diagonal quadratic term.

Response.

  • Solver times. Question 1 lists MOSEK (QCQP) and IPOPT (Stiefel) wall-clock for reference objectives/feasibility targets only—not identical stopping rules vs. Hom-PALM. Every method’s cumulative time appears on the same curves in Fig. 2–3 and Appendix F, so baselines are timed on equal iteration/time budgets (Sec. 6).
  • What the plots test. QCQP is a controlled convex sanity check of gauge + Hom-PALM (n=1000n=1000, mixed equalities and quadratic inequalities). Diagonal PSD objective/inequalities are for reproducible CVXPY generation (Appendix F.3, Eq. (64)), not because we claim MOSEK is slow only on diagonal instances. Stiefel adds nonlinear equalities plus side constraints (Sec. 5.2, Appendix F.4).
  • Baselines with embedded solvers. PALM/ALM baselines that call MOSEK/IPOPT on constrained subproblems mirror standard first-order + exact-inner-oracle implementations. Our claim is projection-free gauge PALM when ΠC\Pi_{\mathcal{C}} is costly—not winning on small structured QCQP vs. a dedicated interior-point code.

Weakness 5

There are also submission guidelines violations: the AI usage statement is omitted.

Response. Thank you for flagging this checklist omission. We have added the required AI usage statement to the submission form and will keep the same disclosure in the camera-ready metadata if the paper is accepted. No AI tools were used to generate or fabricate the theoretical proofs or experimental data; any assisted writing was limited to polish and was checked by the authors. We appreciate the reminder to stay fully aligned with ICLR submission guidelines.

Question 1

What are the solution times for MOSEK and IPOPT?

Response. Thank you for asking for explicit classical-solver times. Below are wall-clock seconds for MOSEK (convex QCQP) and IPOPT (nonlinear Stiefel PCA) used only to obtain reference objectives and feasibility targets (Appendix F). These are not head-to-head races against Hom-PALM on identical stopping rules; Fig. 2–3 already plot each method’s cumulative time under the same iteration/time caps (Sec. 6).

Convex QCQP (proof-of-concept, n=1000n=1000):

MOSEK is a highly tuned interior-point solver for this problem class; on our small structured QCQP instances, beating MOSEK in wall-clock is not the intended takeaway. Runtime here is driven mainly by the number of quadratic inequalities (four (n,p,m)(n,p,m) configs at n=1000n=1000; Sec. 5.1, Appendix F.3):

# eq.# quad. ineq.MOSEK (s)
10010014.00
50010015.27
10050066.93
50050067.75

Stiefel constrained PCA:

IPOPT solves the full nonlinear program (Stiefel equalities + box/group inequalities) for reference objectives. Times grow sharply with ambient dimension (Sec. 5.2, Appendix F.4):

Instancenn (flattened)kkIPOPT (s)
DIGITS19296.92
LFW (main text)2,139976.62
LFW (larger)3,565251,797.48 (~30 min)

The larger LFW row (also in the appendix figure set) already needs ~30 minutes of IPOPT for a high-accuracy reference. That scale is where repeated projections or large KKT solves are costly—the setting our motivation targets—rather than the small convex QCQP check against MOSEK.

Question 2

Is there any convex CC with corners, for which your assumptions hold for some Ψ\Psi? If not, which of your theorems apply to your experiments.

Response. **(i) For cornered convex sets (e.g. boxes in our QCQP), the raw gauge Ψ\Psi from Prop. 3.2 that does not globally satisfy the smooth, assumptions in Sec. 4. The conditional theory is therefore stated for an admissible smooth map (implemented in practice via log-sum-exp Ψw\Psi_w at fixed w>0w>0; Appendix E.5).

(ii) Theory vs. experiments. We are explicit that the printed theorems do not rigorously subsume every detail of the benchmarks (raw gauge on polyhedral facets; hybrid smoothing; Stiefel scope). Nevertheless, the empirical behavior is strong: on QCQP, Hom-PALM tracks MOSEK on objective and full constraint violation (Fig. 2); on Stiefel, it reaches near–IPOPT objectives while improving the objective–feasibility trade-off vs. retraction-based and generic ALM baselines, including at larger LFW scale (Fig. 3; Appendix F). We view this as reassuring implementation evidence, not a substitute for the conditional guarantees above.

Question 3

Can you quantify the practical gains from Hom-APG over Hom-PGD?

Response. Hom-APG in Alg. 2 is the full Catalyst-style loop around Hom-PGD. To isolate the inner benefit of acceleration on the same ball subproblem, we ran a paired ablation: plain Hom-PGD vs. accelerated Hom-PGD (β=0.9\beta=0.9), same initialization and step size, one random instance per ambient dimension (n=2n=2 and n=100n=100). The metric is relative objective gap (f(xk)−fref)/∣fref∣×100%(f(x_k)-f_{\mathrm{ref}})/|f_{\mathrm{ref}}|\times 100\% vs. a high-accuracy reference.

Iterations2D Hom-PGD2D Accel. Hom-PGD100D Hom-PGD100D Accel. Hom-PGD
10016.0662%10.5030%35.6239%32.4098%
5000.0001317%0.00001546%47.1031%19.7991%
1,0000.000005826%—31.4953%20.6355%
10,000——0.6452%0.1888%

In 2D, accelerated Hom-PGD reaches the same terminal gap earlier (979 vs. 1,138 iterations at ≈5.83×10−6%\approx 5.83\times 10^{-6}\%) and is better at every reported budget (e.g. 10.50% vs. 16.07% at 100 iterations). In 100D, acceleration wins at every row; at 10,000 iterations the gap is 0.19% vs. 0.65%. “—” means early stop once the shared target gap was met in 2D. This ablation is a lightweight proxy for the accelerated inner work inside Hom-APG; the full Alg. 2 schedule is what Prop. 4.1 and Thm. 1 analyze.

Reviewer_JL3wOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors present a new iterative method for minimization of a smooth objective function over a compact convex set CC, subject to possibly nonlinear equality constraints. The authors aim to avoid methods requiring euclidean projections on CC which may be costly, and even linear optimization over CC which can be costly as well. Instead, they employ a recently revived approach, where the set CC is first parameterized by a continuous bijection (homeomorphism) Ψ\Psi between CC and the unit ball. This make euclidean projections easy, converting them to projections on the unit ball. The homeomorphism is expressed in terms of the classical gauge function, the length of the half-line from a given interoir point of CC along a given direction to the boundary of CC. This can be computed in closed form for some convex sets (such as a polyhedron) or iteratively by binary search in general.

The authors now merge the known PALM method with this homeomorphic parameterization, which they call Hom-PALM. They prove a good asymptotic convergence rates of this method, touching prior rates for projection-based methods, under natural assumptions, both for convex and non-convex initial problem.

Experimentally, they test the method on two toy example problems: a convex QCQP with affine equality constraints, and the minimal-trace problem over a matrix with orthonormal columns (equivalent to PCA, which is solvable by SVD/eigendecomposition).

The paper includes an almost 40 pages long supplement, where the background is thoroughly revisited and the convergence theorems are proved.

Critical strengths

The reparameterization approach in optimization is interesting (though not new) and I welcome the recent interest in it.

Critical weaknesses

The presentation clarity is not optimal and I am confused my several things. If my understanding is correct, I see several major issues.

First, the presented convergence theorems assume that the homeomorphism Ψ\Psi is smooth. But it is not in general, for many interesting convex sets CC (such as a polyhedron). The authors admit this gap but not clearly and explicitly enough. They point this out in the main paper (line 237) but without suggesting a way out. The only other place where they mention it is in the supplement (line 1342), proposing that a nonsmooth homeomorphism can be smoothed, and refering to another paper (Liu et al, 2025). However, this gap is significant. Smoothing changes the initial problem to its approximation and there is always a trade-off: small smoothing leads to good approximation but slower rates (hidden constants in the asymptotic rates), large smoothing leads to faster algorithm but changes the initial problem a lot. Deriving asymptotic rates for a smooth problem and saying that nonsmooth problems can be always smoothed is not honest enough (I apologize if my understanding is incorrect).

To illustrate this on a simpler situation, take the classical rate O(ϵ−2)O(\epsilon^{-2}) of (sub)gradient descent on a convex (possibly nonsmooth) function, which improves to O(ϵ−1)O(\epsilon^{-1}) if the function is smooth. One cannot simply conclude that GD has rate O(ϵ−1)O(\epsilon^{-1}) for any convex function because a nonsmooth function can be always smoothed.

My next major objection concerns the very idea of reparameterization of the feasible set of optimization problems. Apparently, there is a recent stream of papers exploring this interesting idea in various scenarios, the present manuscript being one of them. But computing the gauge function can be also costly: in particular, its computation by binary search has only a very poor sublinear rate, and it is not clear to me what accuracy must be achieved to keep the presented convergence theory valid. If we neglected this, all projection-based methods could be easily turned to projection-free by just using reparameteriation.

In particular, it seems to me that Hom-PALM is just PALM where the oracle to minimize a function over CC is implemented via reparameterization, that is, instead of computing arg⁡min⁡x∈Cg(x)\arg\min_{x\in C} g(x) for a given function gg we compute Ψ(arg⁡min⁡z∈Bg(Ψ(z))\Psi(\arg\min_{z\in B} g(\Psi(z)). Looking at Algorithms 1 and 2, this seems to be so. In particular, Hom-APG (Alg 2) keeps only the yy variables (in the original space), so it looks like APG with the minimization just computed via reparams (this is confirmed by the first line in section 3.4). Alg 1 also seems to be in this form, for the proximal term in the original space as ∣∣Ψ(z)−Ψ(zk)∣∣2||\Psi(z)-\Psi(z_k)||^2. Th eonly difference seems to be Hom-PGD (Alg 4), where the iterations are really in the zz coordinates (ie, in the transformed space): this seems to be the only difference to ordinary PALM. Perhaps, this is just what the authors wanted to say - but in that case, this could have been said more clearly, making the exposition simpler. Moreover, if this is the case, it is not so surprising that Hom-PALM inherits the asymptotic rates of PALM.

But a remark: Algs 1 and 2 look a bit confusing to me. It seems from Section 3.3 that the primal update in Alg 1 is computed by Alg 2. But a line in Alg 2 says "Solve min⁡z∈BQ~k(z)\min_{z\in B} \tilde{Q}_k(z) via PGD." This suggests that the whole algorithm is in fact a triple-loop one.

Perhaps I am mistaken and the proofs of the achieved rates are nontrivial and more complex that those for raw PALM. A related problem is that it is not clear what is meant by "inner iterations" in, eg, Proposition 4.1: is it the number of cycles of Alg 4?

The experiments are too simple even for this (primarily) theoretical paper. Especially the second experiments seems to be nothing more PCA, which can be computed by SVD.

Minor: the functions γC,κC,dC\gamma_C, \kappa_C, d_C are very closely related, which is not enough emphasized. I suggest to use only one of them.

Questions for authors

See weaknesses.

2 comments

We sincerely thank Reviewer JL3w for the thoughtful and detailed review. Your comments on smoothness of the gauge map, computational cost of gauge evaluation, relation to PALM, nested loop structure, and experimental scope helped us clarify what our theorems assume, how smoothing enters the rates, and how Hom-PALM should be read relative to standard proximal ALM. We address each point below.

Weakness 1

First, the presented convergence theorems assume that the homeomorphism Ψ\Psi is smooth. But it is not in general, for many interesting convex sets CC (such as a polyhedron). The authors admit this gap but not clearly and explicitly enough. They point this out in the main paper (line 237) but without suggesting a way out. The only other place where they mention it is in the supplement (line 1342), proposing that a nonsmooth homeomorphism can be smoothed, and refering to another paper (Liu et al, 2025). However, this gap is significant. Smoothing changes the initial problem to its approximation and there is always a trade-off: small smoothing leads to good approximation but slower rates (hidden constants in the asymptotic rates), large smoothing leads to faster algorithm but changes the initial problem a lot. Deriving asymptotic rates for a smooth problem and saying that nonsmooth problems can be always smoothed is not honest enough (I apologize if my understanding is incorrect).

To illustrate this on a simpler situation, take the classical rate O(ϵ−2)O(\epsilon^{-2}) of (sub)gradient descent on a convex (possibly nonsmooth) function, which improves to O(ϵ−1)O(\epsilon^{-1}) if the function is smooth. One cannot simply conclude that GD has rate O(ϵ−1)O(\epsilon^{-1}) for any convex function because a nonsmooth function can be always smoothed.

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.

(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 Ψ\Psi that is invertible on Rn\mathbb{R}^n with a nonsingular Jacobian JΨ\mathrm{J}_\Psi 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 ϵ\epsilon-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>0w>0, defining a C2C^2 surrogate Ψw\Psi_w and pullback hw=f∘Ψwh_w=f\circ\Psi_w used in inner gradients. Appendix E.5 records explicitly:

  • Feasibility. Reported iterates use the exact gauge Ψ\Psi, so primal feasibility for the original problem (Eq. (1)) is unchanged by ww.
  • Approximation / stationarity. Inner steps optimize a smoothed model; gradient error relative to the exact pullback is O(w)\mathcal{O}(w).
  • Hidden constants. LΨ(w)=O(1/w)L_{\Psi}(w)=\mathcal{O}(1/w) as w→0+w\to 0^+.
  • ϵ\epsilon-orders. ** At fixed w>0w>0, the ϵ\epsilon-exponents in Thm. 1 / Prop. 4.1 are unchanged, but inner cost scales with LΨ(w)=O(1/w)L_{\Psi}(w)=\mathcal{O}(1/w). Coupling w=Θ(ϵ)w=\Theta(\epsilon) can worsen the total inner-work ϵ\epsilon-order in worst-case bookkeeping (e.g. extra O~(ϵ−1/2)\widetilde{\mathcal{O}}(\epsilon^{-1/2}) via MkM_k). We prove rates at fixed ww; experiments use small fixed ww.

(3) Theory vs. practice. Proved acceleration rates are for the smoothed inner model at fixed ww, not a blanket transfer to the raw nonsmooth gauge. Experiments use a hybrid pipeline—exact Ψ\Psi for xx and feasibility, smoothed gradients for inner Hom-APG—with a small fixed ww (Appendix F).

(4) Where this is explicit in the revision (blue). Sec. 4 General Assumptions; Appendix E.5; Sec. 6 (Limitations), third item.

References.

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.

Weakness 2

But computing the gauge function can be also costly: in particular, its computation by binary search has only a very poor sublinear rate, and it is not clear to me what accuracy must be achieved to keep the presented convergence theory valid. If we neglected this, all projection-based methods could be turned to projection-free by just using reparameterization.

Response.

  • (1) Cost. Many sets admit a closed-form gauge (Appendix B.2). Otherwise we use bisection with membership only (Alg. 3): O(log⁡(1/ε))\mathcal{O}(\log(1/\varepsilon)) calls for ε\varepsilon-accuracy. Per Hom-PGD step we report O~(n2)\tilde{\mathcal{O}}(n^2) (Sec. 4.3; Appendix B.3).
  • (2) Inexact Ψ\Psi. If Ψ\Psi and ∇Ψ\nabla\Psi are computed to tolerance δ\delta, inexact-oracle results [1] add only O(δ)\mathcal{O}(\delta) to the gap; the rate in kk is unchanged.
  • (3) Projection vs. gauge. Reparameterization trades projection on C\mathcal{C} for ball steps plus gauge work—we count both.

References. [1] O. Devolder, F. Glineur, Y. Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1):37–75, 2014.

Weakness 3

In particular, it seems to me that Hom-PALM is just PALM where the oracle to minimize a function over CC is implemented via reparameterization … The only difference seems to be Hom-PGD (Alg. 4), where the iterations are really in the zz coordinates … this could have been said more clearly, making the exposition simpler.

Response. Yes—at a high level, Hom-PALM is proximal PALM on the reformulated ball problem (Sec. 3.3): outer updates follow [LQ21], and each arg⁡min⁡x∈C\arg\min_{x\in\mathcal{C}} primal step becomes arg⁡min⁡z∈BQ~k(z)\arg\min_{z\in\mathcal{B}}\widetilde{Q}_k(z) through Ψ\Psi (Alg. 1). The novelty is the inner solve and its analysis: the AL subproblem is nonconvex in zz (hidden convexity only), so [LQ21] convex-inner-oracle proofs do not apply. Hom-PGD (Alg. 4) is the zz-gradient step; Hom-APG (Alg. 2) adds Catalyst-style regularization/extrapolation in xx-space to recover the accelerated inner rate (Prop. 4.1) needed for Thm. 1.

Weakness 4

Algs 1 and 2 look a bit confusing to me … A line in Alg. 2 says "Solve min⁡z∈BQ~k(z)\min_{z\in\mathcal{B}}\tilde{Q}_k(z) via PGD." … it is not clear what is meant by "inner iterations" in, e.g., Proposition 4.1: is it the number of cycles of Alg. 4?

Response. There are three nested levels: Alg. 1 (ALM outer) →\to Alg. 2 (Hom-APG, KK outer steps) →\to Hom-PGD (Alg. 4, TkT_k steps per Hom-APG step). In Prop. 4.1, "inner iterations" means Hom-PGD steps: s=∑i=1KTis=\sum_{i=1}^K T_i, not Hom-APG outer cycles alone (Appendix E).

Weakness 5

The experiments are too simple even for this (primarily) theoretical paper. Especially the second experiment seems to be nothing more than PCA, which can be computed by SVD.

Response. Thank you for raising the concern that the experiments may look too simple. We clarify below: (i) the scale and structure of the QCQP benchmark, and (ii) why the Stiefel/PCA task is not standard unconstrained PCA (SVD).

(1) QCQP is not a low-dimensional toy (Fig. 2). Each instance has n=1000n=1000 and thousands of constraints: (n,p,m)∈{(1000,100,2100),(1000,500,2500)}(n,p,m)\in\{(1000,100,2100),(1000,500,2500)\} with linear equalities, convex quadratic inequalities, and boxes (Appendix F.3). Feasibility is a coupled QCQP—not a single projection onto a cube. This is the convex case our main narrative targets; baselines already use expensive constrained inner solves (MOSEK/PGD/ALM/PALM under a common iteration/time budget).

(2) “PCA = SVD” misidentifies the second problem (Fig. 3). Unconstrained PCA is indeed SVD. Our experiment is constrained PCA on the Stiefel manifold: minimize −tr⁡(X⊤AX)-\operatorname{tr}(X^\top A X) with nonlinear equalities X⊤X=IX^\top X=I and additional convex inequalities (boxes / group budgets on DIGITS and LFW; up to n=2139n=2139). No one-shot SVD solves this feasible set. We include retraction-based and ALM baselines to show a different difficulty—nonlinear equalities plus side constraints—than QCQP. It is a second stress test, not a duplicate of the first.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.