Fast Projection-Free Approach (without Optimization Oracle) for Optimization over Compact Convex Set
Authors: Chenghao Liu
Enming Liang
Minghua Chen
Venue: NeurIPS 2025 spotlight ()
Keywords: projection-free
homeomorphism
gauge mapping
constrained optimization
convex set
Primary area: optimization
TL;DR: A novel projection-free framework for solving (non-)convex optimization over general compact convex set without expensive per-iteration optimization oracles.

Abstract: Projection-free first-order methods, e.g., the celebrated Frank-Wolfe (FW) algorithms, have emerged as powerful tools for optimization over simple convex sets such as polyhedra, because of their scalability, fast convergence, and iteration-wise feasibility without costly projections. 
However, extending these methods effectively to general compact convex sets remains challenging and largely open, as FW methods rely on expensive linear optimization oracles (LOO), while penalty-based methods often struggle with poor feasibility. 
We tackle this open challenge by presenting **Hom-PGD**, a novel projection-free method without expensive (optimization) oracles. 
Our method constructs a homeomorphism between the convex constraint set and a unit ball, transforming the original problem into an equivalent ball-constrained formulation, thus enabling efficient gradient-based optimization while preserving the original problem structure. 
We prove that Hom-PGD attains *optimal* convergence rates matching gradient descent with constant step-size to find an $\epsilon$-approximate (stationary) solution: $\mathcal{O}(\log (1/\epsilon))$ for strongly convex objectives, $\mathcal{O}(\epsilon^{-1})$ for convex objectives, 
and $\mathcal{O}(\epsilon^{-2})$ for non-convex objectives. 
Meanwhile, Hom-PGD enjoys a low per-iteration complexity of $\mathcal{O}(n^2)$, without expensive oracles like LOO or projection, where $n$ is the input size. 
Our framework further extends to certain non-convex sets, broadening its applicability in practical optimization scenarios with complex constraints. Extensive numerical experiments demonstrate that Hom-PGD achieves comparable convergence rates to state-of-the-art projection-free methods, while significantly reducing per-iteration runtime  (up to 5 orders of magnitude faster) and thus the total problem-solving time.

Fast Projection-Free Approach (without Optimization Oracle) for Optimization over Compact Convex Set
Chenghao Liu', Enming Liangl*, Minghua Chen DDeaartment of Data Science, City University of Hong Kong School of Data Science, The Chinese University of Hong Kong, Shenzhen
Abstract
Projection-free first-order methods, e.g., the celebrated Frank- (FW) algo- rithms, have emerged as powerful tools for optimization over simple convex sets such as polyhedra, because of their scalability, fast convergence, and iteration-wise feasibility without costly projections. However, extending these methods effec- tively to general compact convex sets remains challenging and largely open, as FW methods rely on expensive linear optimization oracles (LOO), while penalty-based methods often struggle with poor feasibility. We tackle this open challenge by presenting Hom-PGD, a novel projection-free method without expensive (opti- mization) oracles. Our method constructs homeomorphism between the convex constraint set and a unit ball, transforming the original problem into an equivalent ball-constrained formulation, thus enabling efficient gradient-based optimization while preserving the original problem structure. We prove that Hom-PGD attains optimal convergence rates matching gradient descent with constant step-size find an e-approximate (stationary) solution: O (loog(//e) for strongly convex ob- jectives, O(e-1) ) for convex objectives, and O(e 2) for non-convex objectives. Mcanwhile, Hom-PGD enjoys low per-iteration complexity of (n²), without expensive oracles like LOO or projection, where is the input size. Our framework further extends to certain non-convex sets, broadening its applicability in practical optimization scenarios with complex constraints. Extensive numerical experiments demonstrate that Hom-PGD achieves comparable convergence rates to state-of-the art projection- free methods, while significantly reducing per-iteration runtime (up to 5 orders of magnitude faster) and thus the total problem-solving time.
Introduction
We consider constrained optimization where the objective smooth, possibly non-convex, and the constrained set is compact convex. Although popular second-orde methods, such as interior-pont methods [PW00 Wri97] and cutting plane methods 15), achieve linear convergence rates, their per-iteration computational complexity scales super-linearly with the problem size, typically on the order of On²²) due to solving a linear system. Consequently, these methods become impractical for large-scale problems. Alternative approaches, such projection- based gradient descent (PGD) first-order methods (see, e.g., [Bec17] ZPL22 [L22)), provide a computational benefit for simple convex sets where orthogonal projections can be performed efficiently, such as Euclidean balls and boxes. Despite their slower convergence rate of O /e) in the convex smooth setting and ( /e2) in the non-convex smooth setting, these methods are favorable in practice due their relatively low per-iteration cost. However, the projection operation, i.e., solving a convex problem with a quadratic objective over constraints, is computationally expensive except for simple constraint sets.
"Corresponding authors: Enming Liang (enming.cityu@@ wmail//mmmmmmmmmmmmmm/mm and Minghua Chen (minghut@cuuk.edu..c
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Summary of existing projection free methods for solving optimization problems.
Reference
Settings:
Key Assumption
Algorithm
Step-size X
Per-iteration
Convergence Rate
Obj.
Ctr.
Complexity
Hadamard Purameterizaatio Pertubed PGD
LMY23
NC
Simplex
Constant
O(x))
O(e
SC (Obj Ctr Set)
O(E
002
S (Obj Ctr Set)
Sub Alg. for the RD(41
Implicit and Diminishing
Q00
Ole 0.5
SC & S (Obj + Cir Set)
Olloge e )
C
Upper Radial Ohj
Accelerate Suh GD Alg. for the RD
Implicit or Vanishing
MO
Ofe 0.5)
MHSY25
DC
C
Frank-Wolfe
Diminishing
LOO
O(e²)
Theorem 1
C
C ND Minimizer
O(e '
Hom-PGD
Theorem
SC
C
(Sec.
Constant
MO
Ollog -1) O(
Theorem
Abbreviations: "convex", "non choooncoovee",.... DC "difference of convex", SCC= "strongly convex", "Smooth". Ohj-
"objective", Ctr= "constraint", GD = "gradient deseent", ND "non-dogenerate" RD= "radial dual". LOO "lincar optimization
oracle", -00= "quadratic optimization oracle", MO "membership oracle".
Step-size: (i) vanishing step size: depends (ii) diminishing step decreases poly(1 /K) with the numher of iterations K, (ii) constant step-size: is independent of both and K, and (iv) implicit step-size: has implicit parameters such as smoothness and optimal objective.
Convergence Rate: numher of iterations for finding e-approximate stationary point for non-convex opeimizations
approximate optimum for convex optimizations.
The radial dual (RD) convex constrained problem unconstraine min-max problem Gr124a Gri24h
To circumvent these issues, projection-frue free methods based the Frank- Wolfe (FW) algorithm [FW+ have been widely studied (e.g.. TTWZ22/ Mha22 MHSY25). These methods employ linear optimization oracle (LOO) each iteration instead of projections, with the former often being performed efficiently [CP2T]. However, LOO can still be computationally expensive over complex constrained sets: therefore, FW methods are confined scenarios where the LOO is efficient. Moreover, they exhibit oscillatory behavior near the solution, resulting in slow convergence [RZ24]] FG16]. Beyond FW methods, penalty-based approaches [Ber76 SCB 97 LMX22 struggle with ill-conditioning as penalty parameters increase and perform poorly, particularly when dealing with complex constraints. Recent advances explore projection-
strategies leveraging techniques such as reparameterizatioo [LMY23] TT24 CV25) and radial dual reformulation [Gri24a| Gri24b]. These methods highlight recent efforts to address the limitations of classical projection-fre methods, but remain restricted to structured constraint sets and may suffer from practical drawbacks, such as impractical siep choices (see Table [ Please refer to Appendix A for a detailed discussion of related work to reduce the per-iteration cost and accelerate convergence for solving convex- constrained optimization. Despite the success of existing projection- free methods, the research gap still remains:
Can we design projection-free approach for optimization over general compact convex set with desirable properties, including fast convergence and cheap per-iteration cost?
In this paper, we propose novel projection-free framework that positively answers this question. Concretely, we make the following contributions:
>> In Sec. 3 we design the novel projection-free method, termed as Hom-PGD, that re-parameterizes the optimization over convex compact sets to equivalent ball-constrained optimization. By solving the equivalent problem with gradient descent with closed-form projection and mapping the converged solution back, we obtain the solution to the original constrained problem.
> In Sec. 4 we establish convergence and complexity analysis for Hom-PGD: O(1/e) in the convex setting, Tlg 1/e) in the strongly convex setting, and 0 in the non-convex setting, where established convergence rates are optimal under unaccelerated settings. Moreover, the per-iteration complexity of Hom-PGD is cheap O(n²) without linear/quadratic optimization oracles. We also extend our framework to optimization over certain non-convex sets in Sec. 5
*Optimal convergence rate means it matches the lower bound on iteration complexity. (i) The optimal convergence is ( 2) in the non-convex smooth setting (CDHS20); (ii) For constant step-size, the optimal convergence rate for GD is Ollog 1/c) in the strongly convex smooth setting and ((1/c) in the convex smooth setting; e.g. [P23].

---

>> In Sec. 6 through extensive numerical experiments over convex and non-convex problems, including applications to max-cut SDP problems, we demonstrate Hom-PGD outperforms existing first-order approaches in computational efficiency, which achieve similar convergence rate but significantly lower per-iteration cost (up to 3-5 orders of magnitude).
To the best of our knowledge, the proposed Hom-PGD is the first projection-free, first-order frame- work capable of solving optimization over general convex compact sets while achieving the optimal convergence rate under unaccelerated settings without expensive optimization oracles.
2 Problem Statement
We consider the following continuous convex constrained optimization problem:
min fxx), s.t. E K,
(P)
where x E R is the decision variable, s()) is the objective function, and the constraint set K. C TR is compact and convex. For ease of amalysis and without loss of generality, we assume the constraint
set IC is defined by incqualitie as = {x E R" g(x) S 0} with g = (g .m)) where gi 1 R are functions.
Open Issues: Although convex optimization has been extensively studied, existing methods face significant limitations when dealing with complex constraints. As discussed in Sec. [ projection- based approaches incur high computational costs beyond simple sets, while projection-free methods such as FW and primal-dual approaches are largely restricted to structured convex sets. For example, when solving semidefinite programming (SDP), the LOO required by FW involves solving an SDP itself, defeating its purpose as low-cost alternative. These challenges underscore the need for projection- free algorithms that preserve fast convergence and maintain computational efficiency across broader convex programs.
3 Homeomorphic Optimization Approach
Motivated by recent advances in low-complexity schemes and reparameterization techniques for solving constrained optimization problems [LCL23 [MY23 PP23 LCL24 RSW24 LC25], we propose novel approach that transforms the original constrained problem via a homeomorphic mapping between the convex constraint set K. and the unit ball B. This transformation preserves the essential problem structure while replacing the potentially complex constraint set with the geomet- rically simple unit ball, thereby enabling efficient gradient-based optimization without expensive projection operations.
Definition 3.1 (Homeomorphic constrained optimization). Given a homeomorphism sb : B K. define the transformed optimization problem with objective function lı(z) (ʃ o (z)) and
constraint set - (XC) as:
min l((), s.t. 2 E B
(H)
Homeomorphism (or homeomorphic mapping) is bi-continuous bijection from two topological spaces, guaranteeing the topological equivalence. It is classic result that any compact convex set is homeomorphic to a unit ball 1es 1re13], i.e., there exists a homeomorphism ab such that B = 2b (KC) and K = (B). Thus, we can transform any optimization problem P over a compact convex set into ball-constrained program H In practice, this transformation relies on an explicit homeomorphic mapping, which we will discuss how to obtain in Sec. 3.2
The transformed problem H has a non-conver objective function ht(-) due to the non-linear mapping ub even though the original objective is convex, but it features a simple constraint set as a unit ball, leading closed-form projection. Moreover, under the homeomorphic transformation, the original problem and its homeomorphic counterpart are equivalent, i.e.. there exists bijective correspondence between their optimal solution sets P and H*, where P {x x arg min (P) and similarly for H Specifically, for any x E P there exists unique z E H* such that x = (z). and vice versa. Thus, we can solve the transformed problem H without expensive projection obtain the corresponding optimal solution of the original problem P
Remark:
Linear equality constraints can be removed without loss of generality, see Appendix B.l for discussions.
3

---

PGD
Hom-PGD
min f(x) S...E
ON h(2) (()(x)) V (KC)
min h(z) s.t. Z B
Homeomorphic Mapping v/
B
K
(z)
Optimal paint
Reration trajectory
Figure 1: Hom-PGD Framework: Hom-PGD conducts the standard PGD algorithm in the trans- formed space by a homeomorphic mapping (b()), where the transformed constraint set is a simple unit ball, and the transformed objective function l(-) is non-convex but structured.
3.1 Algorithm Overview
illustrated Fig. [ PGD in the original space suffers from expensive projection operations during iteration over the constraint boundary. To solve prob- lem P without expensive projection, we transform problen em Piints into ball-constrained optimization H by homeomorphic mapping 1b. Then apply regular PGD to efficiently solve the homeomorphic optimiza- tion H with flosed-form projection, thereby termed projection-free" methods. Finally, we map the ob- tained solution back the original space to recover the corresponding solution for the original problem. We call the combination of homeomorphic transformation and regular PGD Hom-PGD, shown in
Algorithm Hom-PGD
Input: initial point Zu, problem H with tb and maximum iteration number K for k 0 to K do
Compute stepsize OKky
Update: 2g++1 TT (2x Ork Vh(2z))
end for
Output: XK +<<<>>
Alg. [
Next, we discuss how to construct an explicit ai for a general compact convex set X.
3.2 Construction of Homeomorphism
We introduce explicit-form homeomorphic mapping between convex set K. and unit ball B as follows, termed Gauge mapping [T22 [LC25]:
Definition 3.2 (Gauge mapping). Let 7x(x, x*) = inf{X > 0 / E X(K x")} be the
Gauge/Minkowski function (BM08) given an interior point x E inl(KC). The gauge mapping ab B + K. is defined between unit ball and compact convex set:
2 7K (2,
7x x", x
(z)
x, Vz B;
+ (x)
(x x)), E (I)
X x
First, gauge mapping &b establishes a homeomorphism between any compact convex set and the unit ball, ensur- ing that K. = (B) and B = +/ (KC). Intuitively, this mapping transforms the unit ball by first translating it to align with an interior point of the convex set, then scaling points radially outward from this interior point until the ball's boundary conforms to the convex set's boundary (illustrated in Fig. 2 Moreover, the gauge mapping has closed-form expressions for common convex sets (linear, quadratic, second-orde -oder cone, and linear matrix inequality constraints) and can be efficiently computed via bisection methods for general convex constraints. For comprehensive property and computation of gauge mapping, we refer readers to Appendix B
2x
0+
B
K
Figure 2: Gauge mapping illustration.
'The term "projection "ereettioo-free" specifically refers to avoiding expensive projections onto original complex constraint sets, usage that aligns with standard conventions the literature (LMY23 LBHH23

---

Leveraging this explicit homeomorphic gauge mapping き we transform problem to problem H and apply Hom-PGD (Alg. [ to solve without expensive projection. However, the gauge mapping s/ depends on the choice of interior point x" (shown in Def. 3.2 Different choices of x yield distinct gauge mappings that alter the landscape of the transformed problem H and affect the convergence behavior of Hom-PGID As we will establish rigorously in Sec. gauge mappings with smaller Lipschitz constants favor faster convergence Hom-PGD, Thus, we proceed to analyze the Lipschitz properties of the gauge mapping as:
Proposition 3.3 (Bi-Lipschitz constants of the gauge mapping). Let K C. R" be a compact convex set and let x" E in) be an interior point. Define the inner and outer radii with respect to
:= sup 2 0: B(x", r) Ck), To : in 2 0: C B(x", ,r))
such that B(x²,n) S S B(x", Then the Lipschitz constant (denoted as T(-)) of gauge mapping sp associated with IC satisfies the following bounds:
1 L( S 2/ri- K1
Forward Lipschitz: K2 L(() 2 +r//r, Inverse Lipschitz:
Therefore, reduce the Lipschitz constant of the gauge mapping and boost the convergence of Hom-PGD, we can select "central" interior point with large inner radius ri small outer radius To. In practice, we may solve convex problem by minimizing the constraint residual find a "central" interior point approximately following [HH22 (refer to Appendix B for details).
4 Performance Analysis
In this section, we present a comprehensive performance analysis for Hom-PGD, including the landscape analysis, convergence rate, and run-time complexity.
General Assumptions (with details in Appendix C.2): )): The objective and constrained functions ga
in P are continuously differentiable and smooth. The homeomorphic mapping vb is invertible with
non-singular Jacobian matrix and is (K1, K2) biiisshitpss continuous. Additionally, the Jacobian matrix of 2p (denoted as Jub exists and is Lipschitz continuous.
We remark that theoretical results hold for any homeomorphism satisfying these assumptions, and we construct a specific homeomorphism, the gauge mapping, in practice. Moreover, gauge mapping meets these assumptions (with details in Appendix B.3
4.1 Landscape Analysis
First, under general assumptions, the composite function f o sb in problem inherits favorable properties as follows (more properties of h are included Lemma D.I}.
Lemma 4.1. Denote Ls.0, Lr, K2; Lop as the Lipschitz constant of f, V 1b Jw respectively. Then Ln.0 = 5,0k2 Lipschitz continuous and h is L -mooohh with Ln, = RRL, + L
Next, recall that point x" is said to be stationary point of problem minxeK f(x) with convex set KC, if V fx(") (x) 2 0 for any K. It is well-known that any stationary point is global optimum for convex constrained optimization problem. A natural question arises: does this property also hold for the non-convex optimization problem H under convex problem PP For unconstrained cases, this property does hold, as the function h is invex with the property that every stationary point of invex function is a global optimum [Mar85]. For the constrained case, provide the following formal statement where the proof is deferred to Appendix [D.6]
Proposition 4.2 (Global Optimality of H). Suppose problem P is a convex optimization. If 2 is
stationary point of problem H and LICO (Def. D.3) holds at z then x" = <b(z") is stationary point of problem P (thus a global optimum). Hence, z" a global optimum.
We remark that the LICQ assumption is mild in our setting. For problem HH. the only constraint is ||z||² < 1, so LICQ holds at any boundary point where the constraint is active. Moreover, since there are no equality constraints, LICQ trivially holds at any interior point. Moreover, we derive that there a one-to-one correspondence for KKT points and non-degenerate stationary points between P and
H
The relevant definitions, formal statements, and proofs are provided in Appendix D.5
5

---

4.2 Convergence Analysis
In this section, we provide theoretical convergence analysis of Hom-PGD (Alg. D for solving problem H Our main result demonstrates that: Hom-PGD achieves the same convergence rate as the standard PGD for the (non-)conved problem under mild regularity conditions, despite operating on the non-convex formulation H
Before moving on, recall some basic definitions. An e-stationary point x" for problem P defined
by |G((x)) < where the gradient mapping G(x) == G1/a (x) 1 [x 1Ix (x
- a (x))].
Note that in the definition, we omit the dependence of the function G on K. and
4.2.1 (Strongly) Convex Objective f
The following theorem provides the convergence analysis of Hom-PGD for convex optimization P
Theorem 1. Suppose the strict complementary slackness condition (Def. D.4) holds for both problem P and H and the problem P convex with non non-degenerate minimizer x'. Let {zz} be the sequence generated by Hom-PGD with step-size a E (0, L,, For sufficient small e > 0, {zx 1K contains z' such that h(z') ht* E.
1==1
with K = E(
Proof Intuition. Under the invertible mapping, z" = <b(x") is also a non-degenerate point from Lemma D.10 Consequently, it satisfies local strong convexity local PL. condition, meaning that h(z) - h' < ((())) (2) holds within a sufficiently small ball centered at z" .. As a result, it follows from Theorem 3 that PGD only requires O(1/e) complexity to find a (ote)--ttii point z' such that h(z') Tu(z), < (Ee). The idea is motivated by [LMY23] which applies specific Hadamard parameterization to transform simplex-constrained optimization to sphere-constrained optimization. We extend their results to a general homeomorphic mapping き and proof details can be found in Appendix E.1
the objective in is strongly convex, we will have a faster (i.e., linear) convergence rate as: Theorem 2. Suppose problem is convex with st-stoyyyly convex objective f. Let {zk]=20 be generated by Hom-PGD with proper constant step-size a E (0, 2. With K = (1s log 1/c) where K = Ln)(u)))) ), we have h(zk) - h(z") S e, and ||z z" c.
Proof Intuition. If f is a strongly convex function over a convex set, it satisfies a generalized PL condition. The homeomorphic mapping preserves this generalized PL condition such that the linear convergence can be established for H Details can be found in Appendix E.2
Remark. (i) The convergence rates derived in Theorem and 2 match the lower bounds in the
unacclerated convex and strongly convex settings (referring e.g., [AP23]) (ii) Theorem [ and Theorem 2 demonstrate that the Hom-PGD algorithm not only maintains projection-free properties over the unit ball, reducing per-iteration computational complexity; but also achieves the same convergence rates as standard PGD when applied to the original convex optimization problem P which is non-trivial since Hom-PGD operates the non-convex objective in problem H
4.2.2 Non-convex Objective f
For non-convex objective f. classical result (e.g., Theorem 9.15 [Bc|14] can be leveraged to show that Hom-PGD algorithms can converge to an e-stationary point with ((1/e) iterations.
Theorem Consider problem mingez h(z) with convex set Z. Suppose h is non-convex and differentiable with Lip-schctitzz continuous gradient. Then the sequence {z with K =
(LL/E²) generated by Hom-PGD algorithm with a constant step-size a E (0, 2 c-stationary point z', Lee, [|G(z')] < 6 éfor some z' (2 k
L contains an
Remark. (i) The convergence rate in Theorem 3 matches the optimal rate for smooth non-convex optimization problems [CDS220. (ii) While Theorem 3 also applies to (strongly) convex objectives, it yields slower convergence than standard PGD in these cases, as it fails to exploit the convex structure of problem and the hidden convexity of problem [HH233 This highlights the significance of
A minimizer of an optimization problem is non-degenerate if the Hessian of the Lagrangian function is positive definite in the critical cone of the minimizer. See Appendix D.4 for details.

---

our results in Theorems 1 and where Hom-PGD achieves the same convergence rates of standard PGD while avoiding expensive projection in the transformed domain. (ii) For non-convex objectives satisfying regularity conditions such as the KI. property or ermor bound conditions, linear convergence rates as in Theorem can also be achieved. See Remark H.5 for further discussion.
In these sections, we establish convergence results for Hom-PGD across different problem classes (Theorems 2 3). The convergence rates depend on the Lipschitz constants of the constructed gauge mapping, specifically: (i) the forward Lipschitz constant K2, which relates to the parameter Ln established in Lemma a.1 and appears in Theorems I and B and (ii) the inverse Lipschitz constant 1/K1, which appears in Theorem 2 As demonstrated in Prop. 3.3 the choice of interior point directly influences the Lipschitz constants of the gauge mapping y.. Consequently, different interior points modify the Hom-PGI convergence rate by constant factors while preserving the fundamental convergence order.
Additionally, our theoretical analysis assumes access to exact gradients and gauge mappings, which is consistent with standard practice in the optimization literature (c.g., [LBGH23). However, for general convex sets, the gauge mapping is numerically approximated using the bisection algorithm (Alg. 2 to compute both its value and gradient within specified error tolerance each iteration. This numerical approximation introduces an additional (ō) term in the optimality gap of convergence results DGN14]. Since 8 can be chosen arbitrarily small, this additional error term remains negligible and does not affect the fundamental convergence guarantees of our algorithm.
4.3 Complexity Analysis
In this subsection, we analyze the total run-time complexity of Hom-PGD, including initialization complexity, per-iteration complexity, and last-step complexity.
Oracles. We list specific oracles in Hom-PGD besides general ones (e.g., zeroth-order oracle for explicit function evaluation).
Membership oracle: Given x R" this oracle Mx I(x E KC) R" + {0, 1} returns 1 if and only if x E K. This oracle performs only feasibility checking without requiring the solution of optimization subproblems. For common convex sets including polyhedra and second-order cones, the membership oracle can be implemented with computational complexity not exceeding ((n²) Mha22], with significantly lower computational burden than LOO or projection practice.
Interior point oracle: This oracle returns an interior point of K. by solving convex feasibility problem. This requirement, common in projection-free frameworks [Mha22 Gri24a Gri24b can
be addressed using first-order methods with Ón 2 complexity or interior-poine methods with (1:5.5) complexity, Notably, this oracle is only called once for the entire optimization algorithm.
Basic operations in Hom-PGD (with details in Appendix B.4]. Hom-PGD requires computing the gradient of / = f o vp per iteration and transforming the final solution via the gauge mapping.
Computing gauge mapping ab: Ön). To compute the gauge mapping in the general case, one may evaluate the gauge function (xc. x²) plus O(n) operations for the scalar-vector product in Def. 3.2
) to an accuracy e with Ollog I/c) membership oracle calls,
Computing gradient of h: (n²). Numerical differentiation techniques (fiite/automatic dif- ferentiation [BF97 BPRSI8 LBGH23)) can be applied, e.g., computing each component V,h (i = 1, 2, ... n) requires (1)) zeroth-order oracle calls of f and Ó(n) cost for evaluating sb. yielding a total complexity of Ö
Total run-time complexity of Hom-PGD.
Initialization complexity (IC): One interior point oracle call to obtain interior point of K.
Per-iteration complexity (PiC): Each iteration cost Ö(n)), comprising gradient computation (z Ō(n²) and unit ball projection O(n).
Last-step complexity (LsC)): costs Ö(n) for computing &b to map the converged solution z back to the original space via x" ab(z").
Number of iterations (#I): Convergence rate varies from different settings, referring to Sec. 4.2
'Here Ō(-) hides polynomial logarithmic factors.
7

---

In conclusion, the total complexity of Hom-PGD equals to IC + #1 Pic LsC O(n #I). This complexity is significantly lower than that of second-order methods, which typically incur Onn²) per-iteration cost, thereby highlighting the scalability of Hom-PGI) to high-dimensional problems. Moreover, our method achieves an optimal convergence rate under the first-order setting, ensuring both efficiency and theoretical soundness.
Discussions
5.1 Beyond Vanilla Gradient Methods
Mirror gradient methods: Mírror descent methods use a mirror map to transform points into dual space, where optimization steps are performed. Essentially, these methods can be viewed as generalized projection methods [BT03]. For example, with quadratic mirror map, it becomes standard PGD; with a negative entropy mirror map, it recovers exponential gradient descent for simplex-cou constrained problems. However, for general convex constraints, mirror descent often lacks explicit mirror maps and suffers from high projection complexity, despite having convergence rates comparable ours [7ec
Advanced gradient methods. One may note that we can replace the unaccelerated gradient methods with any advanced optimizers, such momentum-based
Nesterov-acceleratee methods, or the Adam optimizer popular in deep learning [KB14]. Despite their potential for accelerating optimization of the non-convex landscape problem H analyzing the convergence behavior by utilizing the hidden convexity structure remains challenging, which opens directions for future research. We also conduct illustrative experiments comparing vanilla gradient descent and Adam Section 6.4
Second-order methods. We may also consider second-order methods with projection to optimize problem H However, significant challenges arise from both computational and theoretical perspec- tives. From a computational standpoint, evaluating the Hessian of the composite objective h = f o zb requires computing third-order tensor of the gauge mapping, which is both computationally pensive and memory intensive. From a convergence perspective, analyzing convergence over the non-convex landscape to global optimum becomes substantially more difficult.
5.2 Extension to Non-Convex Constraints
Star-shaped set. Our framework can naturally extend to optimization over non-convex sets where an explicit homeomorphism vp exists such that (B3) K. For star-shaped sets, all points are visible from a star center x" [O] allowing the construction of gauge mapping that bijectively maps standard ball to the set. Such star-shaped constrained problems arise in machine learning tasks such as en-constrained adversarial attacks in neural networks [EBMA2I] Applying Hom-PGD to such problems maintains the (11e²) convergence rate for finding an e-stationary point per Theorem
hall-homeomorphic set. Our framework may also extend to non-convex sets that are homeomorphic unit ball. However, determining if non-convex set is hall-homeemorphic requires examining its topological properties, which is challenging. While a homeomorphism exists for such sets, there is generally explicit form for the homeomorphism. Learning-ben based methods for approximating such homeomorphisms [LCL23 LCL24) present promising directions for future research.
General non-convex set. For more general non-convex sets that may not be ball- hall-homeomorphic (c.g., disconnected sets), our framework remains applicable but without optimality guarantees. Given an interior point x" in K, Similar to constraint restriction methods [LNDT19), the optimality gap depends on the Hausdorff' distance between K. and X.
define X' the largest contained star-shaped set with center x".
Empirical Study
In this section, we conduct simulations to demonstrate the effectiveness of Hom-PGD on both convex and non-convex constrained optimization problems. The detailed problem formulations, experimental settings, algorithm hyperparameters, and supplementary experiment results are in Appendix
Baselines: (i) PGD: Regular projected gradient descent applied to problem P where the projection operation called at each iteration. (ii) FW: Frank Wolfe methods, which solve an update direction with linearized objective and update the decision variables. (iii) ALM: Augmented Lagrangian

---

optimelity cap 16 PIPP
optimaltty gap
PGD
20
FW
ALM
AUM
15
Nem-PFDD
Fom PG3
20
10P
10
10
10
0.0
0.6
num of fteretion
running time (s)
(a) convergence rate
(b) running time (S)
(c) PGD iteration
(d) Hom-PGD iteration
20"
optii alll gop 14 -f UP
100
oppamaltt 946
FGD
20m
20
rum of ttration
running Eime (5)
(h) Hom-PGD iteration Figure 3: Performance for optimization over polyhedron (a-d) and star-shaped set (e-h). respectively.
(e) convergence rale
(1) rumning time (s)
(g) PGD iteration
All methods are executed with the same initial points and terminated by a maximum number of
iterations (10*). Complete results are in Appendix G.1 (Fig.
methods for problem P that alternately update primal and dual coefficients for the unconstrained formulation to problem (iv) RD: Radial-Dual framework, which applies radial-dual to formulate the constrained problem into unconstrained min-mas optimization. (v) Hom-PGD: Projected gradient descent applied to the transformed problem shown in Sec.
6.1 Illustrative Examples: Optimization over Polyhedron and Star-shaped Set
We examine a two-dimensional illustrative optimization problem involving quadratic optimization both (convex) polyhedron and (non-convex) star-shaped set to demonstrate our method's efficiency. As shown in Fig. 3 Hom-PGD outperforms other first-order algorithms in both settings. The iteration trajectories Hom-PGD avoids complex projections while effectively performing gradient descent in a structured landscape of problem to the optimum, even though is non-convex.
the transformed space reveal the mechanism behind this efficiency:
6.2 Solving Second-order Cone Programming (SOCP)
We next evaluate the performance of algorithms on SOCP, which encompasses fundamental convex programs (LP, QP, convex QCQP) and has widespread applications in portfolio optimization [BB V04) and optimal power flow problems [Low [4a]. Problem instances are randomly generated following the CVXPY documents. As shown in Fig. 4 our method not only converges rapidly to the target error tolerance but also demonstrates significantly lower per-iteration costs (up to 3-5 orders of magnitude) compared to projection- based Frank- Wolfe methods, since Hom-PGD does need complex optimization oracles such as projection or LOO during iterations. Further, we also use commercial solver, MOSEK, which typically applies primal-dual interior point methods solve convex programs. Notably, the solver costs 5424 seconds to solve the 1000-dim instance, while Hom-PGD takes less than 600 seconds reach 10-3 objective optimality gap.
Solving Max-Cut Semi-Definite Programming (SDP)
We further evaluate our method on the more challenging max-cut SDP problem. While max-cut an NP-hard combinatorial problem, SDP relaxation with randomized rounding achieves an expected approximation ratio of 0.878 GW95). We generate random Erdös-Rény graphs test instances [HSS08]. Since the optimum of the max-cut SDP is typically low-rank, the gauge mapping encounters non-differentiabiliy at these solutions. To address this practical issue, we apply the smoothing techniques described in Appendix B.3.2 As shown in Figure 5 our approach demonstrates efficient optimization even high-dimensional decision spaces (50² variables) with positive semi-definite cone constraints. Notably, Hom-PGD exhibits slower convergence rate on SDP with linear objectives

---

101
221
100
18P
10P
192
HSD
207
optnaityy
(iii) The gauge mapping Hom ACD
12
Home PGO
107
19
200
400
582
200
300
300
PCD
1mm-PD
RamvEG
(a) (n,, m) = (100, 1000)
(b) (n, m) = (1000, 2500)
Figure 4: Performance over SOCP: n is the number of decision variables and m is the number of constraints. All methods are executed with the same initial points and terminated by maximum iterations (109) or running time (600 seconds). Complete results are in Appendix G.2 (Fig. 12
10
(0-1
10
to?
PGD
10
PGD
10
Pom
Pom/PCD
10
200
800
200
600 PG0 AUMkgAMMt
rurking time 50
K40 ALMISAAIMOP iem-PD
rurniing time DM)
(a) 30
50
Figure 5: Performance over SDP: there are = O(22) decision variables where N is the graph size. All methods are executed with the same initial points and terminated by maximum of iterations (10%) or running time (600 seconds). Complete results are in Appendix G.3 (Fig. 15 19
compared to SOCP with quadratic objectives. This behavior aligns with our theoretical analysis in Theorems D and 2 where strongly convex (quadratic) objectives yield faster convergence rates than SDP formulation [BM03
convex (linear) objectives. The ALM methods solve the
with log-rank (log .) and Barvinok- Barvinok-Pataki (bp)-rank (v2N) Bar95 Par98 BVB20). Despite the scalability of this low-rank formulation. it incurs violation on additional equality constraint and high iteration cost for each inner minimization. However, the per-iteration complexity of our method still outperforms other approaches, resulting in comparable convergence in terms of total running time.
6.4 Scalability Tests and Ablation Study
We first evaluate the scalability of gauge mapping computation across various constraints and dimensions Fig. []] demonstrating efficiency (less than 0. seconds) up 3000-dimensional constraints. Our ablation study further examines critical framework components: (i) interior point selection (Fig. 20.. confirming that central points (smaller Lipschitz) accelerate convergence as
predicted by our theory analysis in Sec. 4.2 and (ii) gradient method variants (Fig. 21). revealing
that advanced optimization techniques (e.g., Adam (KB14) further enhance performance for solving non-convex problem H suggesting promising directions for future research.
7 Conclusion and Limitations
In this work, we propose Hom-PGD, projection-free method that transforms constrained opti- mization over general convex (and certain non-convex) into ball-constrained problem via homeomorphism. Hom-PGID achieves optimal convergence rates with O(n²) per-iteration com- plexity without expensive projections or oracles. Numerical results show competitive convergence with significantly lower iteration costs. Despite its efficiency, there are several limitations to be addressed in future work: (i) Extending Hom-PGD more general non-convex sets is non-trivial, as discussed in Sec. [5] (ii) From the convergence theory perspective, while Hom-PGD achieves optimal convergence rates under unaccelerated settings, it remains an open question whether acceleration techniques (e.g., Nesterov-style methods) can be incorporated to attain optimal accelerated rates. The challenge stems from the non-convexity of the transformed problem used in this work serves as a simple and explicit homeomorphism but may not be the optimal choice terms of conditioning or convergence behavior. Exploring alternative homeomorphisms tailored to specific problem structures could further improve performance.
10

---

Acknowledments
This work is supported in part by a General Research Fund from Research Grants Council, Hong Kong (Project No. 11214825), a Collaborative Research Fund from Research Grants Council, Hong Kong (Project No. C1049-24G), an InnoHK initiative, The Government of the HKSAR, Laboratory for Al-Powered Financial Technologies, a Shenzhen-Hong Kong-Macau Science & Technology Project (Category C, Project No. SGDX202205001 1203026), and Start-up Research Grant from The Chinese University of Hong Kong. Shenzhen (Project No. UDF01004086). The authors would also like to thank the anonymous reviewers for their helpful comments.
References
[AFP23] Ademir Alves Aguiar, Orizon Pereira Ferreira, and Leandro Prudente. Inexact gradient projection method with relative emror tolerance. Computational Optimization and Applications, 84(2):363-395, 2023.
[AP23] Jason Altschuler and Pablo Parrilo. Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule. Journal of the ACM, 2023.
15] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ Machine Learning, 8(3-4):2313377, 2015.
[Bar95] Alexander I. Barvinok. Problems of distance geometry and convex properties of quadratic maps. Discrete & Computational Geometry, 13:189-202. 202, 1995.
[BBV04] Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[Bec14] Amir Beck. Introduction to nonlinear optimization: Theory, algorithms, and applica- tions with MATLAB. SIAM, 2014.
[Bec17] Amir Beck. First-order methods in optimization. SIAM, 2017.
[Ber76] Dimitri P Bertsekas. On penalty and multiplier methods for constrained minimization. SIAM Journal on Control and Optimization, 14(2):216 6-5,, 1976.
[BF97] Richard L Burden and J Douglas Faires. Numerical analysis, brooks, 1997.
[BM03] Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical programming, 95(2):399-357, 2003.
[BM08] Franco Blanchini and Stefano Miani. Sei-theoretic methods control, volume 78. Springer, 2008.
[BMR03] Emnesto G Birgin, José Mario Martínez, and Marcos Raydan. Inexact spectral projected gradient methods convex sets. IMA Journal of Numerical Analysis, 23(4):539-559, 2003.
[Bou23] Nicolas Boumal. An introduction to optimization smooth manifolds. Cambridge University Press, 2023.
[BPRS18] Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jef- frey Mark Siskind. Automatic differentiation in machine learning: survey. Journal of machine learning research, 18(153):1 2018.
[BPTW19] Gábor Braun, Sebastian Pokutta, Dan Tu, and Stephen Wright. Blended conditonal gradients. In International conference on machine learning, pages 735-743. PMLR, 2019.
[Bre13] Glen E Bredon. Topology and geometry, volume 139. Springer Science Business Media, 2013.

---

[BRTW22] Bubacarr Bah, Holger Rauhut, UIrich Terstiege, and Michael Westdickenberg. Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers. Information and Inference: A Journal of the IMA, 11(1):307-353, 2022.
[BRZ24] Immanuel M Bomze, Francesco Rinaldi, and Damiano Zeffiro. Frank-wolfe and friends: journey into projection-free first-order optimization methods. Annals of Operations Research, 343(2):607- 2024.
[BTO3] Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters. 31(3):167-175, 2003.
[BBB20] Nicolas Boumal, Vladislav Voroninski, and Afonso Bandeira. Deterministic guaran- tees for burer-monteiro factorizations of smooth semidefinite programs. Communica- lions on Pure and Applied Mathematicx, 73(3):881 2020.
[BZK18] Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Deep woafk for neural network optimization. arXiv preprint arXiv:1811.0759/ 2018.
[CDHS20] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points Mathematical Programming, 184(1):11-120, 2020.
[CHHY22] Xin Chen, Niao He, Yifan Hu, and Zikun Ye. Efficient algorithms for minimizing compositions of convex functions and random functions and its applications in network revenue management. arXiv preprint 2xXi:2205.007744.. 2022.
[Cif21] Diego Cifuentes. On the moneerrro method for general semidefinite programs. Optimization Letters, 15(6):2299 2309, 2021.
[CJJ+20] Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with ball optimization oracle. Advances in Neural Information Processing Systems, 33:19052-19063, 2020.
[CP11] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40:120-10 145, 2011.
[CP20] Cyrille Combettes and Sebastian Pokutta. Boosting foank-wolfe by chasing gradients. In International conference machine learning, pages 2111-2121. PMLR, 2020.
[CP21] Cyrille W Combettes and Sebastian Pokutta. Complexity of linear minimization and projection on some sets. Operations Research Letters, 49(4))565-571, 2021.
[CV25] James Chok and Geoffrey M Vasil. Optimization over probability simplex. Journal of Machine Learning Research, 26(73):1-35, 2025.
[DFF56] George Bernard Dantzig, Lester R Ford, and Delbert Ray Fulkerson. A primal-dual algorithm for linear programs. Linear inequalities and related systems, 38:171-182, 1956.
[DGN14] Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1):37-75, 2014.
[DKP*24] Osear Davis, Samuel Kessler, Mircea Petrache, Ismail IIkan Ceylan, Michael Bronstein, and Avishek Joey Bose. Fisher flow matching for generative modeling over discrete data. arXiv preprint arXiv:2405.14666. 2024.
[DP19] Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178:503-558, 2019.
[DR70] Vladimir Fedorovich Demianov and Aleksandr Moiseevich Rubinov. Approximate methods in optimization problems. (No Title), 1970.
12

---

[Dun79] Joseph C Dunn. Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals. SIAM Journal on Control and Optimization, 17(2):187-211, 1979.
[BBMA21] Ecenaz Erdemir, Jeffrey Bickford, Luca Melis, and Sergul Aydore. Adversarial ro- bustness with non- non-uniform perturbations. Advances in Neural Information Processing Systems, 34:19147-19155 2021.
[Eva18] LawrenceCraig Evans. Measure theory and fine properties of functions. Routledge, 2018.
[FFK98] Francisco Facchinei, Andreas Fischer, and Christian Kanzow. Regularity properties of semismooth reformulation of variational inequalities. SIAM Journal on Optimization, 8(3):850-86) 1998.
[FG16] Robert M Freund and Paul Grigas. New analysis and results for the frank-wolfe method. Mathematical Programming. 155(1):199-230, 2016.
[HH223 Ilyas Fatkhullin, Niao He, and Yifan Hu. Stochastic optimization under hidden convexity. arXiv preprint arXiv:2401 2000:2000.0008, 2023.
[FLP22] Orizon Pereira Ferreira, Max Lemes, and Leandro F Prudente. On the inexact scaled gradient projection method. Computational Optimization and Applications, pages 1-35, 2022.
[6W+ Marguerite Frank, Philip Wolfe, al. algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-100, 1956.
[2e Stefan Geschke. Convex open subsets of are homeomorphic to n-dimensional open balls. Preprint, http://relaunch. hcm. uni-bonn. pdf, 2012.
[GH15] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method strongly- convex sets. In International Conference on Machine Learning, pages 541-549. PMLR, 2015.
[GH16] Dan Garber and Flad Hazan. A linearly convergent variant of the conditional gradient al- gorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3): 149:):1993111 1528, 2016.
[GLRR25] Kaja Gruntkowska, Hanmin Li, Aadi Rane, and Peter Richtárik. The ball-proximal (=" broximal")) point method: new algorithm, convergence theory, and applications. arXiv preprint arXiv:2502.02002 2025.
[GLS81] Martin Grötschel, Lászłó Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981.
[GM86] Jacques Guélat and Patrice Marcotte, Some comments on wolfe's 'away step'. Mathe- matical Programming, 3501):100-119, 10-,19, 1986.
[Gri24a] Benjamin Grimmer. Radial duality part i: foundations. Mathematical Programming, 205(1):33-68, 2024.
[Gri24b] Benjamin Grimmer. Radial duality part ii: applications and algorithms. Mathematical Programming, 205(1):69-10) 105,, 2024.
[GW95] Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 115--115,, 1995.
[HHZ17] Mingyi Hong. Davood Hajinezhad, and Ming-Min Zhao. Prox-pda: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks. International Conference on Machine Learning, pages 1529-1538. PMIR, 2017.
13

---

[HL17] Mingyi Hong and Zhi-Quan Luo. On the linear convergence of the alternating direction method of multipliers. Mathematical Programminng. 162(1):165-199 2017.
[HLB20] Wooseok Ha, Haoyang Liu, and Rina Foygel Barber. An equivalence between critical points for rank constraints versus low-rank factorizations. SIAM Journal on Optimiza- tion, 30(4):2927-294 2955, 2020.
[HP90] Patrick T Harker and Jong-Shi Pang. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Mathematical programming. 48(1):161-220, 1990.
[HSS08] Aric Hagherg, Pieter J Swart, and Daniel A Schult. Exploring network structure, dynam- ics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008.
[JFFF14] Armand Joulin, Kevin Tang, and Li Fei-Fei. Efficient image and video co-localization with foank-wolfe algorithm. In European conference on computer vision, pages 253-268. Springer, 2014.
[KB14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1xXiv:/412.69880 2014.
[KLLJS21] Thomas Kerdreux, Lewis Liu, Simon Jacoste-Julien, and Damien Scieur. Affine invariant analysis of traak-wolfi, strongly convex sets. In International conference on machine learning, pages 5398-5408. PMLR, 2021.
[KNS16] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradiess methods under the tojaak--ojssiewicz condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pages 795-811. Springer, 2016.
[Koj89] M Kojima, A primal-dual interior point algo-rithm for linear programming. Progress in mathematical programming: Interior point and related methods/Springer- Verlag, 1989.
[KS15] Aritra Konar and Nicholas D Sidiropoulos. Hidden convexity in qeqp with toeplitz- hermitian quadratics. IEEE Signal Processing Letters, 22(10): 1623--67623 2015.
[Lan13] Guanghui Lan. The complexity of large-scale convex programming under a linear optimization oracle. arXiv preprint arXiv: 1309,55300 2013.
[LBGH23] Zhou Lu, Nataly Brukhim, Paula Gradu, and Elad Hazan. Projection-free adaptive regret with membership oracles. In International Conference on Algorithmic Learning Theory, pages 1055-1073. PMLR, 2023.
[LC25] Enming Liang and Minghua. Chen. Efficient bisection projection to ensure neural- network solution feasibility for optimization over general set. In International Confer- ence on Machine Learning. PMLR, 2025.
[LCL.23] Enming Liang, Minghua Chen, and Steven H. Low. Low complexity homeomorphic projection ensure neural-network solution feasibility for optimization over (non- )convex set. In International Conference on Machine Learning. PMLR, 2023.
[I.CI.24] Enming Liang, Minghua Chen, and Steven H. Low. Homeomorphic projection to ensure neural-network solution feasibility for constrained optimization. Journal of Machine Learning Rsearch, 2024.
[Lee10] John Lee. Introduction to topological manifolds, volume 202. Springer Science & Business Media, 2010.
[LG23] Ning Liu and Benjamin Grimmer. Gauges and accelerated optimization over smooth and/or strongly convex sets. arXiv preprint arXiv:2303.0500 2023.
[LKB24] Fitan Levin, Joe Kileel, and Nicolas Boumal. The effect of smooth parametrizations on noncomvex optimization landscapes. Mathematical Programming, pages 2024.
14

---

[LL12] John M Lee and John M Lee. Smooth manifolds. Springer, 2012.
[LLC25] Xinpeng Li, Enming Liang, and Minghua Chen. Gauge flow matching for efficient constrained generative modeling over general convex set. In ICLR 2025 Workshop on Deep Generative Model in Machine Learning: Theory. Principle and Efficacy, 2025.
[LMX22] Qihang Lin, Runchao Ma, and Yangyang Xu. Complexity of an inexact proximal- point penalty method for constrained smooth non-convex optimization. Computational optimization and applications, 82(1):175-224, 2022.
[LMY23] Qiuwei Li, Daniel McKenzie, and Wotao Yin. From the simplex to the sphere: faster constrained optimization using the hadamard parametrization. Information and Infer- ence: Journal of the IMA, 12(3) 2023.
[LNDT19] Dongchan Lee, Hung D Nguyen, Krishnamurthy Dvijotham, and Konstantin Turitsyn. Convex restriction of power flow feasibility sets. IEEE Transactions on Control of Network Systems, 6(3):1235-1244 2019.
[Low14a] Steven H Low. Convex relaxation of optimal power flow flow-part i: Formulations and equivalence. IEEE Transactions on Control of Network Systems, 1(1):15-27, 2014.
[4b] Steven H Low. Convex relaxation of optimal power flow part ii: Exactness. IEEE Transactions Control of Network Systems, 1(2):177-189, 2014.
[LP66] Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 6(5):1-50, 1966.
[LT92] Zhi-Quan Luo and Paul Tseng. On the convergence of the coordinate descent method for convex differentiable minimization. Journal of Optimization Theory and Applications, 72(1):7-35, 1992.
[LT93a] Zhi-Quan Luo and Paul Tseng. Error bounds and convergence analysis of feasible descent methods: a general approach. Annals of Operations Research, 46(1):157-178, 1993.
[LT93b] Zhi-Quan Luo and Paul Tseng. On the convergence rate of dual ascent methods for linearly constrained convex minimization. Mathematics of Operations Research, 18(4):846-86) 867, 1993.
[Mar85] D H. Martin, The essence of invexity. Journal of optimization Theory and Applications, 47:65-76 1985.
[Mch92] Sanjay Mehrotra. On the implementation of a primal-dual interior point method. SIAM Journal on optimization, 2(4):575-601, 1992.
[Mha22] Zakaria Mhammedi. Efficient projection-free online convex optimization with member- ship oracle. In Conference on Learning Theory, pages 5314-5390. PMLR, 2022.
[MHK20] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization submodular maximization. Journal of machine learning research, 21(105):1-45 2020.
[MHSY25] Hoomaan Maskan, Yikun Hou, Suvrit Sra, and Alp Yurtsever. Revisiting frank-wolfe for structured nonconvex optimization. arXiv preprint 25X0:225033.821,, 2025.
[MMBS14] Bamdev Mishra, Gilles Meyer, Silvere Bonnabel, and Rodolphe Sepulchre. Fixed-rank matrix factorizations and riemannian low-rank optimization. Computational Statistics, 29:591-621, 2014.
[MZWG16] Cun Mu, Yuqian Zhang, John Wright, and Donald Goldfarb. Scalable robust matrix recovery: Frank-wolfe meets proximal methods. SIAM Journal Scientific Computing, 3865):33211-33317, 2016.
IN+ 18] Yurüi Nesterov et al. Lectures convex optimization, volume 137. Springer, 2018.
15

---

[Nes05] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical program- ming. 103(1):127-152, 2005.
[NFSA14] Ricardo Nanculef, Emanuele Frandi, Claudio Sartori, and Héctor Allende. A novel frank-wolfe algorithm. analysis and applications to large-scale sym training. Informa- tion Sciences, 285:66-99, 2014.
[NW99] Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
[Pn997] Jong-Shi Pang. Error bounds in mathematical programming. Mathematical Program- ming, 79(1):299-333 1997.
[Pat98] Gábor Pataki. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Mathematics of operations research, 23(2):339- 358, 1998.
[Pen23] Javier F Pena. Affine invariant convergence rates of the conditional gradient method. SIAM Journal on Optimization, 33(4):2654-2674, 2023.
[PI21] Andrei Patrascu and Paul Irofti. Computational complexity of inexact proximal point algorithm for convex optimization under holderian growth. arXiv preprint arXiv:2108. 04488, 2021.
[PNI8] Andrei Patraseu and Ion Necoara. On the convergence of inexact projection primal first-order methods for convex minimization. IEEE Transactions Automatic Control, 63(10)33317-3329 2018.
[PP23] Clarice Poon and Gabriel Peyré. Smooth over-parametterized solvers for non-smooth structured optimization. Mathematical programming, 201(1):897-952, 2023.
[PW00] Florian A Potra and Stephen Wright. Interior-point methods. Journal of computational and applied mathematics, (24(1-2):28112)) -302 2000.
[RSW24] Akshay Ramachandran, Kevin Shu, and Alex L Wang. Hidden convexity, optimization, and algorithms on rotation matrices. Mathematics of Operations Research, 2024.
[RW09] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
ISCB+97) 97] Alice Smith, David W Coit, Thomas Baeck, David Fogel, and Zbigniew Michalewiez. Penalty functions. Handbook of evolutionary computation, 97(1):C5, 1997.
[SG24] Thabo Samakhoana and Benjamin Grimmer. Scalable projection-free optimization methods via multiradial duality theory. arXiv preprint arXiv:2403.13688 2024.
[SRB11] Mark Schmidt, Nicolas Roux, and Francis Bach. Convergence rates of inexact proximal- gradient methods for convex optimization. Advances in neural information processing systems, 24, 2011.
[THH23] Jesus Tordesillas, Jonathan P How, and Marco Hutter. Rayen: Imposition of hard convex constraints on neural networks. arXiv preprint arXiv:2307.08336 2023.
[THZK21] Kenya Tajima, Yoshihiro Hirohashi, Esmeraldo Ronnie Rey Zara, and Tsuyoshi Kato. Frank-wolfe algorithm for learning svm-type multi-category classifiers. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 432-440. SIAM, 2021.
[Tob86] Roger Tobin. Sensitivity analysis for variational inequalities. Journal of optimization theory and applications, 48(1): 1986.
[TT24] Tianyun Tang and Kim-Chuan Toh. Optimization over convex polyhedra via hadamard parametrizations. Mathematical Programming, pages 1-41, 2024.
16

---

[TZ22] Daniel Tabas and Baosen Zhang. Computationally efficient safe reinforcement learning for power systems. In 2022 American Control Conference (ACC), pages 3303-3310. IEEE, 2022.
[WKP23] Elias Wirth, Thomas Kerdreux, and Sebastian Pokutta. Acceleration of frank-wolfe algo- rithms with open-loop step-sizes. In International Conference on Artificial Intelligence and Statistics, pages 77-100. PMLR, 2023.
[WL06] Changyu Wang and Qian Liu. Convergence properties of inexact projected gradient methods. Optimization, 55(3):301-310, 2006.
[Wol70] Philip Wolfe. Convergence theory in nonlinear programming. Integer and nonlinear programming, pages 1-36, 1970.
[WPP24] Elias Wirth, Javier Pena, and Sebastian Pokutta. Fast convergence of frank- wolfe algorithms on polytopes. arXiv preprint (xXi::2406//8889 2024.
[WPP25] Elias Wirth, Javier Pena, and Sebastian Pokutta. Accelerated infine-ivvariant conver- gence rates of the frank-wolfe algorithm with open-loop step-sizes. Mathematical Programming, pages 1 1-45, 2025.
[Wri97] Stephen Wright. Primal-dual interior-point methods. SIAM, 1997.
[Yc94] Yinyu Ye. Combining binary search and newton s method compute real roots for class of real functions. Journal of Complexity, 10(3):271-288 1994.
[Ye01] Yinyu Ye. Quadratic programming over an ellipsoid. In Encyclopedia of Optimization, pages 2112-2116. Springer, 2001.
[ZL20] Jiawei Zhang and Zhi-Quan Luo. A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal on Optimization, 20(3):2272-3303 2020.
[ZL22] Jiawei Zhang and Zhi-Quan Luo. A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization. SIAM Journal Optimization, 32(3):2319-2366 2022.
[ZPL22] Jiawei Zhang, Wenqiang Pu, and Zhi-Quan Luo. On the iteration complexity of smoothed proximal alm for nonconvex optimization problem with convex constraints. arXiv preprint arXiv:2207.0632 2022.
[ZWWY20] Fan Zhang, Hao Wang, Jiashan Wang, and Kai Yang. Inexact primal-dual gradient projection methods for nonlinear optimization on convex set. Optimization, (91))2333 2365, 2020.
17

---

Contents
Related Work
19
A.1 Classical Methods
19
A.2
Recent Advances
19
A.3
Ball-Constrained Optimization
20
B
Homeomorphism of Convex set via Gauge Mapping
21
Handling Constraint Set with Equality
................................
21
B.2
Gauge Mapping for Convex Set
................................
21
B.3
Properties of Gauge Mapping
22
B.4
Computation of Gauge Mapping
24
B.5
Gauge Mapping in Hom-PGD
25
Preliminaries for Technical Proof
27
C.1
Basic Concepts
27
C.2
Basic Assumptions and Notations
................................
28
C.3
Basic Facts
29
Landscape Analysis
29
D.I
Action of Homeomorphism
Constrained Set
................................
30
D.2
Properties of Function / fo 2/
30
D.3
Stationary Points and KKT Points
................................
D.4
KKT Conditions of Problem F
33
D.5
Relationships of KKT Points between Problem and
34
D.6
Global Optimality Property of Optimization Problem
36
Convergence Analysis
37
E.1
Proof of Theorem 1] Convex Case
37
E.2 Proof of Theorem 2 Strongly Convex Case
39
Experiments Setting
42
F
Problem Formulations and Instance Generation
42
2
Baseline Algorithms and Hyper-Paranee Para-aaaaeeerss
43
Supplementary Experiments Results
45
G.1
Illustrative Examples
45
G.2
Second-order Cone Programming
46
G.3
Max-Cus Semidefinite Programming
46
G.4
Ablation Study
48
18

---

A
Related Work
We discuss related work on methods for reducing computational costs and achieving speedups in constrained optimization, organized into three parts: (i) classical projection and projection-free methods, (ii) recent advances, and (iii) work related to ball-constrained optimization.
A.1 Classical Methods
In convex optimization, three classical approaches have been widely studied: Frank-Wolf methods [FW+56], which avoids projection through linear minimization oracles over constrained sets; primal- dual methods (DFF56). which address primarily linear constraints through simultaneous updates to primal and dual variables; and penalty methods [Ber76], which incorporate constraints into the objective function using penalty functions (SCB NCB++7] 97]. Each approach has its limitations.
Frank-Woul methods. Frank-Wolfe (FW) methods are first-order optimization algorithms that offer several attractive properties: they easy to implement, projection- free,
[Lan KLLJS21 [Pen23] land their iterates naturally form sparse convex combinations of extreme points in the feasible region, making them particularly valuable for various machine learning applications
14 JTFF14 BZK18 MHK20 THZK21. Convergence analysis of classic FW methods GM86) However, FW methods face two key limitations: they require an efficient linear minimization oracle [CP21]. and they often exhibit slower convergence rates [BRZ24 [6 Specifically, under the Wolfe's 's lower bound setting [Wo170), the
have been widely studied PL66 DR70
D9n
FW algorithm cannot achieve convergence rates better than (0e-1+)) for any > 0. Overcoming this fundamental barrier requires either algorithmic modifications or additional strong assumptions
GHIS
BPT 6H16
CP20 [KP23 WPP25). For advanced convergence analysis, one could
refer
23
WPP24
MHS
Penalty methods. Penalty methods struggle with ill-conditioning as penalty parameters increase and perform badly, especially for complex constraints. Primal-dual methods primarily used to handle linear constraints (Koj89] MMh922, [PIT], and their second-order variants face scalability issues due to high computational complexity.
First-order primal-dual methods. First-order primal-dual methods iteratively update primal and dual variables using inexact gradient steps (see, e.g., [HHZI CPIT)). However, analyzing the
convergence of such methods remains a challenging problem. particularly for nonconvex objectives
[2L22]. Most existing convergence results focus on problems with linear constraints [L93bb] CPII].
A widely used technique to address this challenge is error-boumt analysis [LT93a Pan97], which
has been effective in establishing convergence rates for first-order methods in the convex setting
LT92 HL177. However, these results typically provide only local convergence guarantees ensurrng convergence only when iterates are sufficiently close to the solution set-and and depend on an error- bound constant that is often unknown or difficult to estimate. Recent work (ZL20) ZL22 ZPL22] introduces the smooth augmented Lagrangian primal-dual algorithm for constrained optimization. While this method achieves an optimal convergence rate matching the lower bound of optimization complexity for nonconvex objectives, incurs additional projection complexity in each iteration.
A.2 Recent Advances
To reduce the cost and accelerate the convergence for solving (non-)convex optimization over convex sets, recent novel projection-free methods and other advanced techniques involve inexact projection, radial dual formulation, re-parameterizing optimization problems, and uncovering hidden convexity.
Inexact projection. In many cases, the projection operator lacks analytic solution or is com- putationally expensive to compute exactly, motivating the analysis of inexact projected methods. For convex optimization, such methods achieve the same convergence rate as PGD if the cumula- tive projection error is bounded [SRBI]] PN18), with new results derived under specific settings For nonconvex objectives with convex constraints, their convergence has been analyzed in BMROS WL06 ZWWY Recent advances further generalize inexact projection operators to broader settings
PI21.
AFP23
Radial duality. Beyond classical projection-free methods, recent advancements have introduced novel approaches based on gauge and radial duality theory. Radial duality theory for nonnegative
19

---

demonstrates that constrained optimization problems can be reformulated as unconstrained problems using the gauge of their constraints. This framework has led to the development of new families of projection- methods with optimal convergence guarantees [G23]] as well as relaxed conditions [SG24] that enable more efficient line search operators for the reformulated unconstrained problems.
optimization problems [Gri24a Gri24b]
Reparameterization. Reparameterization optimization problems aim mitigate challenging prop- erties, such as non-smoothness or non-convexity, via invertible transformations while preserving equivalent optima. Parameterization widely used optimization and learning tasks, including semi- demindefinite programming [Cir2]] low-rank optimization [MMBS14 HLB20), and risk minimiza- tion [BRTW22]. Recent advancements include parameterizing simplex (LMY23) and polyhedron TT24 optimization via Hadamard transformation to reduce projection complexity, smooth over- parameterization to accelerate non-smooth optimization algorithms [PP23], parameterizing discrete data as continuous for generative learning [DKP+24), and analyzing the optimization landscape under parameterization transformations in non-convex settings [KK22]
Hidden convexity. Hidden convexity refers to transformations that reveal the convex structure of non- convex or functions, which has been exploited in problems such as rotation matrix optimization [RSW24), non-linear least squares [DP19], revenue management and inventory control [CHH)22]] and quadratically constrained quadratic programming (QCQP) with Toepliz-Hermitian [KS13]. For non-convex stochastic optimization with hidden structure. projected gradient- based algorithms can achieve the same convergence rate in convex optimization for both strongly convex [FHH23 and convex objectives [CHHY22 under certain assumptions. Furthermore, QCQP, which generally NP-hard, can solved in polynomial time when hidden convexity is present [KS15).
Hermitian quadraties
A.3 Ball-Constraieed Optimization
To improve algorithmic performance and reduce the computational cost of constrained optimization, recent work has explored the use of ball-constrained optimization. The idea dates back to the ellipsoid method [GLS8I]. which iteratively encloses the feasible region in shrinking ellipsoids that contain the optimal solution. Despite theoretical appeal and linear convergence. the ellipsoid method suffers from high computational complexity as O (n²)), making it impractical for large-scale problems. More recently, [CJJ=20 GLRR25] studied acceleration techniques using ball-optimization oracles for specific problem settings. Inherently, ball-constrained optimization exhibits favorable properties; for example, solving quadratic problems over ball using combination of bisection and Newton's 's method can achieve convergence rate of Olog tog(1/e) Ye94,, YeO1, which matches the fast rate of Newton's 's method for unconstrained problems [BV These developments highlight the potential of call-constrained techniques in designing efficient and scalable optimization algorithms.
20

---

B Homeomorphism of Convex set via Gauge Mapping
In this section, we provide the omitted details in Sec. and Sec.
B.1 Handling Constraint Set with Equality
We first explain how to apply our framework to handle constraints with linear equality constraints as mentioned in Sec. Consider the constrained set as follows
K fx qxx) 91 (x) I O, Im ( S 0}
where q(-)
(mea) with qi 12" I are linear/affine functions. Note that the rank of Jq is constant for all x, i.e.,
(g1. -2.-
rank
=T, E.
Then fq(x) = 0} of dimension n by the Constant-Rank Level Set Theorem LL12 In other words, we can use a subset of decision variables x E R and reconstruct full decision variable X2] E R" via the equality constraint, where X2 = & (xi) and q ([x,, & (x1))) 0. Such
reconstruction process ensures the feasibility of the equality constraint. Then the constraint K. can be reformulated as
K xx1 E R" 9) | ((x1)) S 50,... (x1,
((x1)) 9 50
follows from the reconstruction that
(x1. Φ (x2)) K EK"
Thus, can assume the constrained set has no inequalities without loss of generality.
B.2 Gauge Mapping for Convex Set
We first recall the definitions of gauge function//aaping. Definition B.1 (Gauge/Minkowski function (BM08)) Let C C R" a compact convex set with
non-empty interior. The gauge/Minkowski function ne R" int(C)) + Rz0 is defined as
cc(x, x²) inf x X(C -x"),
where x int(C).
Building upon this foundation, we define the gauge mapping between two compact convex sets: Definition B.2 (Gauge mapping ( Let 2, C C IR. be compact convex sets with interior points z E int(2) (2) and x" E inL(C), respectively. Then
the gauge mapping ub Z C defined
(z) 72(z 2², 2²) 2²)
2") + x" Z,
7c(2 n,, x²)
2) and the inverse gauge mapping 2b 1 C + 2 is given by:
s (x) 7x(x x², x²)
(x xx +2", XEC.
22 (x x 2²)
have the following remarks based on the definition.
In essence, the gauge mapping scales the boundary of convex set from interior point to another convex set and with translation to its interior point.
When Z is a unit ball, the gauge mapping in Def. B.2 is simplified as Def.
|||||
7c(x x² x*)
(bx))
xx) z + x", Vz E B,
(x)
(x x"), Vx C. x
||x
21

---

B.3 Properties of Gauge Mapping
The gauge function satisfies the following properties.
Proposition B.3 (Basic properties of gauge function), Let be a compact and convex set. For all x, R and a 2 0, gauge function xc((;x²) given interior point x² int((C) satisfies:
Non-negativity: v0(xx x*) 2 0.
Positive homogeneity: (e(o,, x²) (x,,
Subadditivvit:: 7c(x y.x) I ve(x, x*) + x").
Convexity.
Differentiability: Gauge function twice differentiable almost everywhere.
Upper/lower bounds: (xc x*) [|/x|//ro: /x])
Lipschitz continuous: |// x*) re xI +, || yll-
Proof. We show them one by in the following.
1)2) The definition can directly derive non-negativity and positive homogeneity.
3YTo show subadditivity, let
2 = %e (x,x*) and = rc (y,x")
By the definition of the gauge function, there exist points u, v E C - x" such that u and
y X Now, consider the sum:x + = u + v, Write this sum as
A
x + = (Au + Xyy
(xx
Ax
+x
u
dr + X
Since C- x convex (as translation of the convex set C the convex combination
A
Xy
A A ut
v VEC-
Ae Ag
Thus, x x E (Az + A,) - x)) which implies by the definition of % that "ce (x + y, xxx S
d + Xy. Since Ay and X can be arbitrarily approximated by sequences converging 90 (x,x²) and ne x²) (if the infimum is not attained exactly), we conclude 7/ (x + x²) S 70 (x, x9) ie xy,
4) Convexity is induced by Positive homogeneity and Subadditivity.
5) Differentiability is from the fact that Convex functions over compact set are twice differentiable almost everywhere [Eval8].
6) By the definition of gauge function (Def. B.5
we have:
|x|
No xxx dx(x", x [|x E [[]x|]/ro> [|x]/r]]]
7) By the subadditivity, we have: vo (x, (x,x²) 7e (c.yx)) I ve(x - y,x²) + ve(y,x)) 7e(y.")) -c((x v.x²) s ||x yl//n
Similarly, we have:
xc(y,x") - (x(x x²) S 7cly - x,xx) < ||x - yll/n
Thus, have
- x0)| S =|x yll- _ r
1
Based on the non-negativity, positive homogeneity, and subadditivity, the gauge function generalizes the concept of norm. For set C that is symmetric about the origin, the gauge function 7c(x, 0) defines norm. In particular, when C = B, = {x E I |x||, S 1] the unit ball of the p-norm, we have yB, (x, 0) |x||p
22

---

B.3.1 Proof of Proposition 3.3: Bi-Lipschitz Constants of Gauge Mapping
Next, we prove Proposition 3.3 constant depending on rj and To.
stating that the gauge mapping is bi-Lipschitz continuous with
Proof of Proposition 3.3
We begin with the forward gauge mapping from the 2-norm ball B to C as
2 IC (z, x²)
(z)
z + xx, Vz E B
Differentiating (z) with respect (using the product and quotient rules) yields
zz
2
(Va7c(2,x)) T.
J 7c x*)
(z, x |z]
7C (z, x2)
Taking the operator norm and applying the triangle inequality gives
J
||
||2||
||2|
V Vxro(2,x))
7/ (2)
xx(
x))2
r
To
ri
where in the last inequality we have used the facts that (i) for B one has | < 1, (ii) the gauge function satisfies (2,))x)) E [||z|//ro /z/l/r] and (ii) Vc x")] is bounded by 1/r--
In summary, we obtain
|
s 2r
which proves that the forward Lipschitz constant of ap satisfies
Lip(tb S 2ro + Ti
Next, consider the inverse gauge mapping from C to the 2-norm ball as
Tc(x x", x²)
(x xx), Vx C.
||x x
Differentiating with respect to x gives
xxxx")(x-XX
(x) V-c(x x", x")
x ||x x²1
)
Tc(x x2, x²)
xx x x
x - x²1
Taking norms and again using the triangle inequality leads
7 rc(x x", x0)
1 (x=x")(6 (x-xx) x
x
| s
Vxc(x Vxc(x-xx)
- x², x²) |xx x² 1
x x
Using the bound (e - x²,x" x²) E [||x - x term has norm at most 1/1[x x² I1),, have
//// ||x
x
x2|l/r] and the projection matrix related
| (x)
1
2
ri
r n
Thus, the inverse Lipschitz constant is bounded by
Lip(æb
1) <
This completes the proof.
23

---

B.3.2 Smoothing Technique for Gauge Mapping
Moreover, we have the following property for gauge mapping as corollary from Proposition B.3
Corollary B.4. The gauge mapping up defined in Def. B.2 is twice differentiable almost everywhere.
This corollary follows directly from Proposition B.3 and aligns with our general assumptions (see Appendix C.2p. However, the existence of a mero-me set of non-differentiable points creates sap between our theoretical requirements and the current formulation. For instance, in max-cut SDP problems, low-rank optimal solutions lead to con-differentiable points the PSD cone constraint boundary due to eigenvalue multiplicity at the maximum eigenvalue, causing convergence behavior to oscillate around the optimum. While these points may have no practical impact on most engineering problems, mathematical rigor demands that we address this discrepancy.
To bridge this gap, introduce smoothing technique. Recall that the gauge mapping sb from the unit ball B to a convex set computed (see Appendix B.4) as:
(b()) Ke (x"; z z/|lz|)
2 x²
where ke is the inverse distance function (Def. B.5
In practice, most constraints encounter listed in Table 2 The non-smoothness of Kg (and thus +)) arises from the use of the max operator (including the ReLU operator [-]*) when handling multiple constraints. We define K, (x",, v) such that ke, (x", v) [x,(x", v)] in Table 2 Hence, each K; is smooth. We then express ke(xx, v = max (x,,x), v), 0} and, letting #m++1 = 0, we 15a5m
simplify this as
kc v) max (x:(x,.)) isis
with loss of generality. In the following, for convenience, we fix x" and write (v) instead of ky (x(",, v).
We smooth ke using the log-sum-exp approximation (also called Nesterov smoothing) with parameter n 0 following [Gri24h] Nes05):
(i((V)
(y = log
cxp
with the corresponding gradient
m
exp (ka (v)/n)
Ki Σ X Vn((v) where
A;
ΣØ= exp (Ki (v)/n)
By replacing the objective = f o ab with h, = o 1b,, where (b, ",,'""///<>> 2 x", we
obtain a twice-differentiable homeomorphism. The smoothing introduces optimality gap of O [Nes05] Gri24b) (here the hidden constant is dependent on the Lipschitz constant of f), which can be made arbitrarily small by choosing 7) sufficiently small.
B.4 Computation of Gauge Mapping
For computational purposes, we introduce a point-to-boundary distance function and its inverse. Definition B.5
distance [THH23], ). Let C C R be compact convex set and |||| = 13, we define the interior interior-point-to-
x" E iC) For any unit vector V E 5--1 {u E R"
boundary distance function de int(C)) Sn-1 + R>o along direction v as
de(x", v) sup A 2 0 x CV
The inverse distance function re: iCt(C) x s--1 + Rgo is defined as ke(x", v) == 1/de(x,, (ddex",vv) v).
We then have the following rules for computing the gauge mapping with the help of the point-to- boundary distance function.
24

---

This distance function relates to the gauge function as:
||]| TC (x, x²) = ko(x"; x/||>||) ||x|| dx(x", , x/ x/||x||
Further, considering the positive homogeneity, we have:
1
(x /e(x/||>| ,xxl/x/xxx))))))))) x") = ke(x" focxxxxx/00 x/|xx) de(x², x/||x|1)
The gauge mapping between B and C. can be simplified as:
(x) = de(x" z/ ||2ll
2 + x², Vn EB
(x) dc(x²; (x x X x E
Therefore, compute the inverse distance function to obtain the gauge mapping. In practice, we can compute the inverse distance function (x("", as follows.
Closed-form for common constrained set. For various common constraint types, Table 2 provides closed-form expressions of the inverse distance function and Fig. [6 show the actual computational cost for Most matrix calculations can be computed and stored offline before being applied online given v.
Bisection- algorithm for general constrained set When the inverse distance function lacks
closed-fome expression, we employ efficient bisection algorithm detailed in Alg. 2 This algorithm supports batch processing, enabling efficient parallel computation for multiple inputs simultaneously.
10-2
Linear
SOC
Gauge computation (s)
Quadratic
LMI
10-1
500
1000
1500
2000
2500 3000
Constraint dimension n
Figure 6: Illustration of gauge function calculation time as constraint dimension varies.
B.5 Gauge Mapping in Hom-PGD
Optimizing the interior point in Hom-PGD. As shown in Sec. one can select a central interior point with large inner radius or smaller outer radius To to reduce the Lipschitz constant of the gauge mapping &b thereby boosting the convergence rate of Hom-PGI Here, we introduce two types of interior points which maximize r; and minimize To respectively, below.
Chebyshev center: maximizes the minimum distance from the point to the boundary set large inner radius ri:
arg max min ||x - y!l.
xeK. yEaK.
Min-max center: minimizes the maximum distance from the point to the boundary of the set for a smaller outer radius To:
x arg min max ||x -y
XEX YEOK
25

---

Table 2: Closed-form Expressions for Inverse Distance Functions THH22
Inverse Distance Function Ke(x", v)
Constrained Set
Formulation
Linear
fx aaxxx x S b}
(,a
Quadratic
{x x Qx a x b}
(1/root (Aq, Bq: Cq))
Second Order Cone
{x ||
pll S +
(1/roo((As, Bs, Cs))
Linear Matrix Incquality
fx: Σ F, Fu 0}
(eig (L (-S)
Intersections
C M Ci
max Isism
{Ne, (x", v)}
Notation: x.
R Q E 87. R=xm E R Fo.... Fn mm X R (.)
max(-,0) 0).
3 rooo(22, 22, m2) -22 123 132-511
22,
denotes the rosts for quadratic equation.
281
Aq v BQ 2x
Qv +av. =x=x²= Qx a
As
(A vv) (a 2)2
BS 2 +p) v) 2(a aaxx" b)(a v). Cs (ATx*
(A p)-
+02
= Din1 F,
(ig > denotes the eigenvalues satisfying det(X A1) = U. Note that only the maximum eigenvalue necdle.. Thus, power iteration methods can be upplied to compute it eefficiently
L E.,,
Note that all v-independent terms can be computed only once and stored for use.
Algorithm 2 Bisection Algorithm for Inverse Shinttt-BBouddry Distance
Input: A compact convex set an interior point x" C, and unit vector v.
a, and an
2: while lai - aal 2 10 do
3: if 0s. C then
4: increase lower bound: Oi <
5: double upper bound: ag t am
6: else
7: bisection: am = (ar + a2)/2
8: if x amm C then
9: increase lower bound: ag f O.m
10: else
11: decrease upper bound: an < am
12: end if
13:
end if
14:
end while
Output: inverse distance: (x(x", v) = 1/am
According to the definitions, the Chebyshev center maximizes ri and the min-max center minimizes To- For certain convex sets, one can efficiently compute these centers. For instance, for a polyhedron, one can find the Chebyshev center by solving an LP (see e.g., (BV044). However, for general convex sets, computing the Chebyshev center entails solving convex optimization problem that may be very hard due to the infinitely many constraints where each corresponding to a boundary point of the set.
In practice, we may minimize the constraint residual to find approximate central interior point following [TH223 Concretely, we solve the following convex program to obtain an interior point x E K. := (g(x) 0).
(x", c) = arg max
s.t. g(x) S -cl,
E E>
Note that in the main experiments, we set 10-3 as constant solve this convex feasibility problem to obtain an interior point (which may close to the boundary). In the ablation study, we solve this residual maximization problem to obtain "central" interior point for comparison.
26

---

Computation of basic operations in Hom-PGD. We now summarize the practical methods used to compute the key operations Hom-PGD, including the gauge function/mapping and the gradient of h o/:
Computing the gauge function ",
x²): Compute the inverse distance function k)((x,,) via Algorithm or using the closed form when available.
Computing the gauge mapping sb: Derived from Definition B given (x(x,))).
Computing the gradient of h f th: Approximated using numerical differentiation methods. If has a closed-form, the gradient can be computed using automatic differentiation methods (see e.g.. (BPRSI8), For general cases, we adopt the finite difference method for computing the gradient of the gauge function in [LGGH23] i.e., for 1.2....,
v,h(x) h(x Xe;) h(x)
A
given proper small number À 0 where denotes the standard basis over R".
Next, we summarize the complexity for computing the above basic operations.
Proposition B.6. With the zeroth-order oracle of f and the membership oracle, the computational complexity of the basic operations in Hom-PGD) is as follows.
(i) Computing gauge function "ic"-x"" an error costs Olog 1/e).
(ii) Computing gauge mapping (x) costs Ö(n).
(iii) Computing the gradient of h = f a up costs O(?)).
Proof. We show them one by in the following.
(i) This a classical result of the Iisection-based algorithm. Using Oloo 1/e) number of calls to the membership oracle, can get Ebie -aproxximaee solution the gauge function (+((=x)). One could refer to, c.g., [CL23 LBGH23 Mha22] for detailed proof.
(ii) From Def. B.2 computing 2b requires (1) complexity to evaluate x²) and (n)) complexity to compute the vector product de -x) . z.
(iii) From the finite difference method described above, computing each partial derivative V.h requires evaluating h, which involves a zeroth-order oracle call to f and a computation of the gauge mapping sb. Therefore, computing each V,h(xx) (i = 1,2....,77 costs Ö(n), leading to a total of Ō(n²) to compute the gradient mapping Vh.
C Preliminaries for Technical Proof
In this section, summarize the related basic concepts, notations, assumptions, and fundamental propositions and lemmas.
C.1 Basic Concepts
We list the basic concepts used in this paper below.
Indicator function. For a set X C IR", the indicator function dx R2" > IR is defined as
if X, if & X.
6x(x) 8o
Distance between a point and set. For a closed set X' E IR" and any E RR"", the distance between x and A' is defined dist(x, X') infyex ||x yl]. Orthogonal projection. For closed set X, the orthogonal projection of point R onto X' is defined as IT (x) = arg minyex |yl-
Function convexity. For a differentiable function f : C IR it is said to convex if one of the following holds:
27

---

1) Jensen's s inequality. For f with 0 S 0 S 1, we have f(0x f)y) + for all y, X.
X. 3) monotone gradient. (Vf(()) - Vf(y)) -)) forall x, X.
first-order condition. f(y) 2 f(x) (V
L-Smoothness. A differentiable function f X _ _= + R said be L-smooth if one of the
following holds:
1) zeroth-order condition. f(Ax + (1 A)y) Af(x) + -)f(y) 1 Alll - -xl2.. for all x, y E X, [0. 1].
2) first-order condition. f(y) - fxx + [Vf(x), y - + / lly - x11 for all x, E X.
3) Lipschitz gradient. (}V fx)() - -xll for all x,
u-Strong convexity. A differentiable function f X' -F= R is said be μ-strongly convex holds if one of the following holds:
1) zeroth-order condition. f(Ax + (1- - Aly) & Af(x) + - -))-(f(())))))))))) 5x(1 A)lly - x|1?
for all x, X [0. 1].
2) first-order condition. f(y) 2 fxx) + y + f - 2 for all x, E X.
3) strictly monotone gradient. (V V
x|2 - 3 for all x, X.
Stationary point. Consider program {minx f(x), s.t., E ) where f is differentiable and X
is a convex set. Let a > 0. Then point x" is called a stationary point for the program
1xx a (x)) = x,
equivalently (see c.g. [Bcc14)
(Vf 0, X
Jacobian matrix. Suppose f R" + RD is function such that each of its first-order partial derivatives exists on R". Then the Jacobian matrix of f, denoted Jr E RRx", defined as 0
Jr
)ig-
02y
A Hessian a function f: RD - R is defined as v = ( 8. 02,02, )iy E R if its second-orded partial derivatives exist. Moreover, for mapping f R.. -> R. with existed second-order partial derivatives of each component fi = 1,2, ... .m). The Hessian of f is defined as H(f) = (V ,',., Jm).
C.2 Basic Assumptions and Notations
In the following, we make assumptions throughout the paper.
Assumptions on I and constraints gi (i = 1,2, mm) in problem
P
1) f is L,.o-iipscht continuous, i.e., llf(x)) - f(y)ll s Ly,ol|x -yl for any x, y.
2) problem Pis differentiable and smmoohh
3) f > >oo where f == minxek fx).
Each gi L-ipschiz continuous, differentiable, and Ly. -mooth.
Assumptions on the homeomorphic mapping &b IR. + R":
1) /b is differentiable with non- singuln Jacobian (-),
2) 2b is (K1, -ii--ii--iishhhiiii continuous for K2 2 Ki > 0, i.e.
81 xiIlu- - v/l < [[ <b(v)] & K2 v/|- Then the Jacobian matrix, (-) and - (-) will satisfy
1
[ S K2, Vz, (x)-(())] 5 Ki
Vx.
3) ub has Lap-Lipsehitz continuous Jacobian matrix, i.e., [| - (v)]l < Lællu l 1a--vll vll. Vu, vb has continuous Hessian, i.c..
(z) = (V v2zb,))
exists and is continuous.
In addition, summarize the commonly used notations in this paper in Table
28

---

Table 3: Summary of Notations. The notations shown in the table is for problem P and we use the
same type notations for problem
Notation
Definition
12-norm || ll2
B
unit ball centered at 0 Lipschitz constant of f Ly-smooth property of f Hy-strong convexity bi-Lipschitz constant of vb distortion of tb, i.c., K2/Ki Lipschitz constant of J the interior, boundary of IC
Lg.0
Lf
As
f
K1,
Lo
(IC),O.
C,3 Basic Facts
In this section, we list the fundamental facts we will use in this paper.
Proposition C.1 (Global optimality condition, see e.g., (BBV04 Bec17)). For convex constrained optimization (minx (x), s.f. E } x" is global optimum if and only if x" is stationary point of the problem, i..,
[x(x'),x-x* 0.
Proposition C.2 (Properties of orthogonal projection, see e.g., Bec14 ). The projection operator
1l over closed and convex set C satisfies the following properties.
1) Optimality condition: Vy C, (x [x), Ie((x)) 0.
2) Non-Expon Von-Expansiveness: [|I]c(x) - Iyc s |x-xll
3) Monotonicity; (Ilc(x) (yc(y), x y) 2 0.
We have the following lemma related to ab to help with the computation.
Lemma C.3. Suppose Jup is Ls Lipschitz, iee, ( Ju (z) S Lap Iu z|| for any u and z.
Then, we have
Vu, z. (vb(u) <p(()= - (z) 2))1u S L /| u - z|/2
2
One can refer to Lemma 1.2.3 N 18 for the proof.
Next, we list the following rules for basic computation:
Jacobian equivalence: J (x) 1 (z) for (bxx).
Chain rule for computing gradient of ub:
Vh(z) = J (z) vf((((z) [ Vf(().
Chain rule for computing gradient of f:
Vf(x) = J (x) Vh(z) = (x) (22TToe Vh((z).
Chain rule for computing Hessian of h = f fo ab:
df 0x:
(hh(2) - = S(
(bb (zb(
D
Landscape Analysis
In this section, we provide landscape analysis to understand important relationships between problem and H
29

---

10
10
05
05
-10
-15
-15
-25
-1.
-0.5
0.0
0.5
10
15
-15
-10
-05
9.
0.5
1.0
15
Figure Illustration of the action of homeomorphism on polyhedron. The left figure is the polyhedral constraints of problem P for some Under the homeomorphic mapping 4b. the constrained set transformed a ball (right figure). Each constraint inequality {Z, S 0} (colored differently) is non-convex in general.
Each color of line represents a constraint incquality {a, x S b
D.1 Action of Homeomorphism on Constrained Set
Recall that the constrained set is K. = fx E I
(x) S 0) with g = (91.92, .9m) where 9:
1,2, ... m) is convex function. For problem
B - -= = {z E IR" (z) E K} {z E R" G(z) = g(bb(z)) S 0}
where G2 might be non-convex even for convex 9:- However, B is assumed to be convex (actually a ball set) in this paper. One refer Fig. for illustration.
Moreover, we assume there are no redundant inequalities in K., i.e., there is no J: such that can be represented as the positive linear combination of other inequalities. In this case, any feasible point satisfying gi (x) = 0 for some is on the boundary of the set Moreover, we have
fx K Øj
gh (x) + n fx E (x(x) = (x) + 0 =
any & + j. Note (z Gi(z) < 0, 1,2, : {z ||z|2 S 13. Moreover, (2) < 0, 1,2..... m) also has no redundant constraints by the non-singularity of the Jacobian of db and similarly,
B | Gy(z) Gz(z) 0) N (z e B Gz(z) = 0}
for any * k. Hence if satisfies Gz(z) for some i, it lies the boundary of B. Clearly, we have
Gz(z) |||||
z' B, G,(z)) 0.
(2)
and
VG,(2) =2, 2z, (G 2I, at B.B,G.(2) 0.
(3)
where I, is the identity matrix of n by n.
D.2 Properties of Function f = fo
Lemma D.1 (Properties of = ab). Under the general assumptions C.2 = fo sb has the following properties.
1) h is La,0 Lg Lipschitz continuous.
2) La-smooth with L2 x²L + LIg.
3) If f convex, then h en-welkly convex with C, T.g.OT.p.
4) If J is stsslnnggly convex. Then h satisfies the quadratic growth condition with my the ball set B, i.e.,
KrKs
2 on
h(z)) h- mn mmllz- 121 Vz B.
(4)
30

---

Proof. We prove them one by one in the following.
1) We can directly derive from basic definitions:
|| (u) - h (v)ll s ( (u)) - / (x) (v))
S L 1b (v)ll
- 5 u vll.
2) From sy-smoots of f. we have
[[x vf(y)]l S 5 yll-
(5)
Then we derive with x - (2), v = byy).
[Vh(z) 4h (v)l
Ju(Z) Vf(x) Jo (v) vz(}
(U(E) (V/(x) v.(()) + (J Joh (v)) 4 [
[[J(()) T. (Vf(x) Vf(y)) + (J - M (v)) [,(r)) KeLes [1/b()) - ab (v)l + L. 1|z vll
I (mīL. + L (,0)) I|z - vll-
Let Ln, -RgLs + Lab We have the conclusion.
3) One hope show 11)) + - 11 is convex function, i.e.,
h(v) + l | 2 h(z)
la |2 + (Vh(2) + +,2.v v- 2), Vz, v.
2
2
This is equivalent to show
h(v) + En | 21122((z) + (Vh(z), v- -2)), 42.
2
We drive with x = (b()) = =bv as follows,
(Vh(z), v z) (V)x(z) f(x), v - 2)
( - z))
(V)(x), (Vv) + (b22) + [+( 2)) + (Vf(x), +(v) - (b()))
$ [[V](())]| ||v(v) (bzz) (z(z)(v z)ll V x)
S 1 ||2 v/I + f(y) - f(x)
= 5 | - v1I² + +(() h(z)
where the first inequality is from triangular inequality and the second inequality is from Lemma C.3 and the convexity of f.
4) Note that optimality implies stationarity. By the strong convexity of f. for any x E K. and x" K we have
f(x) 2 f (x*) (x*)
H1 2
||x x* 12.
Here the last inequality is from the global optimality condition
C.I
With (z), we have
(z) 2 h((z)) + 15 [1b(()) 31("))12 2 h(z²) + 13 K2 Iz - 1/2
2
2
31

---

D.3 Stationary Points and KKT Points
Recall that the stationary point x* of defined by the variational inequality:
(Vf x- x*) 2 0, K.
(6)
Besides, a tuple (x, X) is said to satisfy the Karush-Kuhn-Tucker (KKT) condition of problem Pi the following holds
m
Vs(x) + (x) = =0
gi(x) S 0, i= ,......... A 2 0, >xgi(x) = =0 i= 1,2,
where À is the dual variable corresponding to inequality constraints. Definition D.2 (KKT stationary point). A point x" is said be KKT stationary point of if there exists X such that (x", X*) satisfies KKT condition 7
Actually, these two definitions are equivalent under mild conditions, which will be discussed later. Before moving on, introduce related definitions.
Definition D.3 (Constraints qualification). Let be feasible for a problem with constraint set x 9i (x) v 0, 4 (x) = 0, for = 1,2, ",,.,,,,,, ,,, and j = 1,2, ... ,P}
and put A(x) (x) 0}. We say that
1) the linear independence constraint qualification (LICQ) holds at & (and write LICQ(x) ) the gradients
(x) A(x)) (ąj(x)( ......p)
linearly independent.
2) the Baaggasarian-Frommoyo constraint qualification (MFCQ) holds at & (and write MFCQ(x)) ) the gradients
(gy( = ......p)
are linearly independent and there exists a vector d E IR such that (x) d 0(i A(x)),
(x) d O(j ...,..,7>>
Definition D.4 (Strict complementary slackness). It is said that the strict complementary slackness condition holds for problem P if
X for 9x
and for problem
1/ for ||z'|| =
Definition D.5 (Slater's condition). It is said that the Slater's condition holds for problem with constrained set K. := (x) I 0, = 2, ... m.. there exists Xo such that for all 1,2....,. m.
(xp) < O.
established that the variational inequality and the KKT system 7 coincide with strong relationship if certain constraints qualification holds. One could refer to [HP90 FFK98 Tob86) for detailed discussion. We summarize the conclusion the following proposition.
Proposition D.6. We have the following relationship between and (7).
1) x" is solution of the variational inequality 6 and certain constraint qualification (e.g.. LICO, MFCQ. see Def. D.3 holds x", then there exists X" such that the tuple (x", X²) satisfy the KKT system 7
2) Suppose and gs (i- 1,2, m. are convex and Slater's condition D.5 is satisfied. xf is solution of the variational inequality ( then there exists X* such that the tuple (x" x²) satisfy the KKT system (7).
3) 1f (x", (*) satisfies the KKT system and g is convex, then x* satisfy the variational inequalities
Proof. One can refer e.g. Bec17 1 for item (2).
Tob86 HP90 for item (1) and (3) and refer to e.g. Theorem 3.78
D
32

---

D.4 KKT Conditions of Problem and H
We first introduce the following definition.
The normal cone Ns(x) closed and convex set 'C' at x E defined as
Nx (x) {y (y,z x) for any z E KC}.
The tangent cone (x(x) of a closed and convex set K. at E K. is defined as
Tx(x) = cl YE > 0 s.t x + Xy E K}
where cl(-) denotes the closure of a set.
The critical cone Cx(x) of a closed and convex set K x E K. with related a objective function f is defined as
Cx(x) {d Tx(x): Vf(x) 0}
To define the second-order KKT condition for the optimization problems, we first recall that the critical cone of problem P can be written [NW99]
gi (x*) d for all i Axx)) with X 0, Vg (x*)
d E Cx (x")
d 2 0, for all i (x*) with XØ = 0.
Here X is the Lagrangian multiplier of inequality constraints 9a and A(xx) is the index of active constraints. Moreover, if strict complementary slackness holds, the critical cone is simplified as
Cx (x*) = (d IR." Vgi (x*) d 0, for all i E A (x")).
Then, write KKT Suppose strict complementary slackness holds for problem and H
conditions for problem P] and H in the following.
First-order KKT conditions on x". The Lagrangian of P
(r(x, = f(x) + (x).
The first-order KKT conditions of P are: there exists A such that
vf(x)) +
(xx =
(8a)
xxxx) < 0, i= 1,2, m 2 O, (xx(x)) = 0, i= 1,2, m.
(8b)
(8c)
Second-order KKT conditions on It adds the following condition
TV2CC(x' ; 20 0
(9)
for any w satisfying w (xx)x") = with E A(x*). First-order KKT conditions on zz. The Lagrangian of is
Cu(z,v) h(z) + v x[|z| - 1).
The first-order KKT conditions of H aree there exists v² such that
Vh(z²) + 22 = 0,
(10a)
||>0|| < 1, 1 2 0, ||
(10b)
0.
(10c)
Second-order KKT condition on z". will add the following condition.
d CH' x" ,'' 2 2
(11)
for any E Cz(z"). Here recall that
Cs(2²) ( 2t = 0},
R"
zf int(B),
if 0B.
33

---

D.5 Relationships of KKT Points between Problem P and H
Lemma D.7. We have that x" is KKT stationary point of P if and only if is also KKT stationary
point of H
Proof. 1) First, we assume that z" is KKT stationary point of By assumption, there exists X such that the KKT condition holds (8) holds. Then we have
(z") [V(2))'[[x") +
(x Vxi(x") = 0,
)i((b(z") < i= 1,2, ; A 2 0, {īgo(ab(z")) = 0, i= 1,2, . m.
This is equivalent to
Vh(z') + Vz)))z) = 0.
(12a)
Gi(z") < 0, i= 1,2, m X 220, 0, X7Gi(2") = 0, i= 1, 1,2,
(12b)
(12c)
Let V" = Eiz M. According to the eq. 2 eq. 12a is actually
Vh(z") + 2v x²
By assumption, eq. (1b) is equivalent to
|z v 1.
Note that if (z") < 0 for all then A = 0 and thus v O. In this case, 1| 1|-_1] 1) 0. Ifz makes at least one G;(z") ) = O, then we have | = 1. In this case, we also have v² ([|2* 2 = 0.
Hence, eq. (2ch implies
2 0, v (| 1 - =. In conclusion, there exists n,, v² such that the KKT condition holds.
2) Now, we assume z",v* satisfy KKT condition problem H i.e.,
Vh(z") + 2v"z" 0,
||20||2 < 1, v/ 2 1² "1|z" 1) 0.
If iB) then (z)) < for all and 0. In this case, there exists X such that the KKT condition (10) of problem P holds at x* =bb(z") X
from strict complementary slackness. Denote A = {d: G. (z") 0}. Note we define A; = 0 if A and
0B, then there exists least one i 21,2. m} such that Gz(z") = 0 and
X; = >/ A|A]. Then have z", X such that eq. holds which implies x* xb(z" A make the
KKT condition of problem PhoP hold.
Lemma D.8. Suppose strict complementary slackness condition holds for both problem P and
Then x" is second-ord order KKT stationary point of P if and only if z = =b-²((²)) is also second-order KKT stationary point of H
H
Proof. From Lemma D.7 there exists X and D² such that (x" x*) holds for first-order KKT condition of P if and only if (z* v*) holds for first-order KKT condition of H Hence, suffices to show the equivalence of condition and 9
Let's first suppose x" is second-order KKT stationary point, i.e., eq. holds.
Note
V2Cu(z', v²h(z") + 2 In.
34

---

where In is identity matrix of size n x n. We just need to show d' VLH(z", .d 2 0 for any E Cz(z"). Recall that
of
f(>b(z²)) = J1ylz")== v ()) +
Σ
0x, (bb(zz) (2bz')))'',,E7"
==1
and
dgi
V²G((z)) (
90((b(zz)) ()( +
(2b i i= 1.2,
, ,
From eq.
note that
GzGxzz") 2I,, wk A(x') Gx(z') 03.
From Lemma D.7 v² = E. Then we have
m
2 FL((z, (21(2z))
Gv''((z"")
(13a)
= v' f(b((z))))) f((b(2))) + Σ Jo(z") (, v (1(((z))))) (x (2')(()))))
(13b)
0f (zb(2 )) (z') +
0g: () (z'")z
(13c)
0x:
8x:
From first-order KKT stationarity of i.c.,
Vf((") +
i Vxx(x) = 0,
We have
0f 0xk
m
0g: (x") O.
(x")
OxH
Hence for any d Cs(z"), we have the second term (3c) is equal to 0.
Now we note it's trivial that Ck(x*) = CB(z*) = R" if e int(KC) where x (0zz). Hence in this case if d E Cs(2"), we will have (z(2)) E Cx(x*)
x E OC, then A(x*) + 0. For d E Cg(z"), i.e. d z² = 0, we have
(Jo(2")d) T (xx)x" = d (a(zz))Voitt = =d G, 2d ====0 for E A(x"), or Jo(")d Cx(x").
So ford E Cz(z"), we have the following holds about the first term of V V2Luizz,,u v²).
m
(Je (2) V2 (ub (z")) Ju (x") d + (Jap d2)
Σ x (ab (2")) (b())))
Ju (z")
where the last '2' is from the assumption that x" is the second-order KKT stationary point of P Hence, we have d Lu(z""" =n)d 2 0 for any d E Cs(z*), i.e. zt vo "x*) is also second-order KKT stationary point.
2) Let's suppose zt is second-order KKT stationary point and show that x" is a second-order KKT stationary point.
If 1 E int( the proof is trivial because v" = 0 according to the similar analysis. So we assume
z" E 05. Define A(z") (i Gz(z") 0). and X 0 for i & A(z"), X v² A((x)) for
i E A(z*).
Note for any E Cx(x*), we have
0 w (xx(x") w J [eT))"((''') -J (z")w) z², for ie A(x") A(z").
35

---

Hence J (z") (2" w E Cb(z"). Then for any w E Cx(x"),
w xx ,'
m
-w -w'v2/(x' Σ
1 V gi("")
(JT
+ (1
(z')w
Of 8x
m
Ogi
(ab
(1b(2 [)( (z") ( (z")
Ox
= -J (z") ww)
LH(z", 1/
(z ww
where the sum of last term of the second '=' is exactly and the last "2' is from the assumption that z a second-order KKT stationary point.
Definition D.9 (Non-degenerate KKT stationary point). A second-order KKT point x" of P is said to be non-degenerate there exists A such that
d V2 >'
for all 0 * d E Cx(x"). Here the Lagrangian function is
C(x, A) f(x) + m
(x).
Lemma D.10. Suppose strict complementary slackness holds for problem and H Then x* non-degenerate KKT point of optimization if and only if z satisfying x ub(2") is also non-degenerate KKT point of problem
Proof. 1) Suppose x" is non-degenerate KKT stationary point. Note that for d Cg(2²), ). have Ja (z") d Cx(x*) from the proof of Lemma D.8 Moreover, from (z*)") * we have (z ) + if and only if d o O. Then the conclusion trivial from eq. (13) in the proof of Lemma D.8
2) Now, suppose z' is non-degenerate KKT stationary point. It follows from the proof of Lemma D.8 that for any E Cx(("", we have J=1 (z")w Cs(2*). Hence, the conclusion is also trivial from the proof of item (2) of Lemma D.8.
D.6 Global Optimality Property of Optimization Problem
H
Proposition
4.2
Suppose problem is corvex optimization. Then the following holds.
Ifxx is stationary point (thus global optimum) in problem then z" optimum in problem and (Vh(z"),
2/ (x*) is global
z²) 2 0.
2) z is stationary point of problem H and LICQ holds z", then x" is stationary point of problem P (thus a global optimum). Hence, z" is global optimum.
Proof. 1) Due the global optimality of x", we have
f(x") < f fxx), K. Hence with the homeomorphism 1a and (z), have f(b(zz)) < f(b(z)), Vz B,
36

---

that is
h(z²) 2 h(z). Vz
Therefore, (Vh(z"), 2 16=x" x²) 2 referring to Prop. C.I
2) By assumption, LICQ holds at z Hence by Proposition D.6 there exists a tuple (z" 1/*) such that the KKT condition of problem H holds. It follows from Lemma D.7 there exists A such that (x*, X²) also satisfy the KKT condition of problem P Then it follows from the convexity of
( 99m) that x" is global optimum of P From the above conclusion (item (1)), x is also a global optimum.
E Convergence Analysis
In this section, we will provide omitted details in Section 4.2
E.1 Proof of Theorem I Convex Case
Define for any z, T(z) Tg--1 (z) {d d 0} and denote Projz(d) ProiT(e)())
(d z)z. We define
grad h(z) (Vh(2)))(z)
and
hess (z)) Proj, (V2h(z)) vh(z) In) Projz.
Moreover, we define (z) Vh(z) if (B) and (z) grad l(z)) if z E AB. Similarly, define Vzg( = V2h(z) if iBt(()) and Vigh(z) = hess M(z) if E AB.
With these notations, the definition of the second-order KKT stationary point z for H is equivalent the following (see e.g. (LMY23)
VB h(zz) = 0, (igh 2 0,
where min eig(-) represents the minimum eigenvalue. Moreover, z" is non-degenerate if in addition min eig( (Zgh(2") > 0.
We first give some help lemmas in the following.
Lemma E.1 (Local PL condition). Suppose h is twice continuously differentiable.
If aB is a non-degenerate minimizer for H there exists 5 == 5(z") and = r(2") such that
PL inequality holds locally, i.e.,
h(z) - h-(z(()) S 27
Igrad h(z)]
for any z E B(z", (8) AB.
2) 2f E iB) is a non non-degenerate minimizer for there exists ō = ó(2") and T = T(z") such that PL inequality holds the ball B(z", ,8), i.e.,
h(z) - h(zz)((=))))))))z)))) < 2T [Vh(z)]]
for any z E B(z", 8).
Proof. For item (1), x is on the boundary of B. We can consider h 0B = S, - R. Because z" a non-degenerate minimizer, by continuity there exists ball B(x", 5) and upon z E B(z" 5) 0B we have hess h((z) is positive definite, i.e., h is r-strongly convex over the ball. Hence PI. inequality holds over E B(z", .6 n ØB (refer to e.g. Lemma 11.28 [Bou23]. i.c..
h(Z)) - h(22)) <
Igrad h(z)]
2T
for any z E B(z", 5) AB.
It's easy to show item (2). Actually, by continuity there exists ball B(x", 8) upon which (²)(2)) is positive definite, i.e., r-strongly convex over the ball. Hence PI. inequality holds over the ball (refer e.g. [KNS16)).
37

---

Definition E.2 (Approximate stationary point), A point x" is called e-stationary point for problem minxek. fxx with convex set K. if the gradient norm mapping
1 xx lx aVf(x))
G(x) = Gi/a
satisfies ||G(x)]| S for proper > 0.
Lemma E.3. Suppose and zz = ll -ae--aVhie aVh(zz)) (ell(z)).oo for some a > 0 are both on the boundary of B. the gradient norm mapping
G(z) = G1/a (2)
1z =²]
satisfies [|G())]| S then |grad h(z)ll & (c)).
Proof. From properties of the orthogonal projection
2 have
<Vh(zz) 2 juz
for some μ 2 0, or
Vh(z) G(z) apG(() + - c1 G(z) ozz
where e = aa
0 (for small enough and c2 p1/a. We have then grad lzz) Vh(z) (Vh(z), 2) Gz)((z) - ((z) z)2.
Thus,
Igrad h(z)]l & 2eelllGaa G(z)) s s(().
Lemma E.4. Suppose h is twice continuously differentiable and z is unique minimizer (stationary point) for Then for any O, there exists an eg > O such that z is an 68 stationary point can imply I x² 8.
Proof. We suppose there does not exist such es > 0. Then for any == 1/k, we can find an stationary point žę such that ||z, 2" 2 8. As B is compact, may assume Z B. Then a stationary point by continuity of the gradient norm mapping:
[|G(z)] || |G lim zx)ll lim [[G(z)]]
S lim EK
10000
k-+00
This contradicts |
xz 2
Theorem I Suppose the strict complementary slackness condition holds for both problem and H and we suppose the problem Piis convex and has non-degenerate minimizer x". Let {zz} be the sequence generated by Hom-PGD PGD with step-size a E (0, 2. For sufficient small 0, {z ) k=1
with = O(Ln/e) contains z' such that
h(z') h" S.
Proof. From Lemma D.10 z² is also a non-degenerate stationary point.
1) We first assume x² E 0B.
By Lemma
E.1 there exists and 8* such that for any z E B(z", 8*) n aB, h(z)) - h(z")
2 grad 122))12
Moreover, we assume this 5* is small enough to satisfy the condition that for any E B(z", .8*). z a Vh(z) is outside the ball, which implies z lg(z - ad(2)) E 0B. This 8 exists by the continuity of Vh and note Vh(2*) = uzz for some fı" > O (where '>' is from strict complementary slackness condition). Hence if PGD can find an approximate stationary point z' B(z", 8*) ), we can assume z' E OB.
38

---

From Lemma E. there exists eg- > 0 such that if z is an eg- stationary point then z E B (z", 6*).
So, suppose
0 is small enough that eve 68- where
0 is fixed constant determined later.
By Theorem
PGD finds evE-stationary point z' E aB, within K O ([=/(v3)) (1/4))
iterations, i.c., G(z') I cve. From Lemma E.3
we can choose proper such that |[rad h(z')l -
V2T*e.
As evV Eg. we know z' is also 6X- -tattiony point within B (z* 88))
1 1 2r Igrad (z))l (V2T*c)² Sc.
h (z') - h (z²) S
27
2) The case when z E iB) is similar.
By Lemma
E.1 there exists -² and 8* such that for any E B ,8),
1 h(z) - h(2") < 2 |Vb(2)]13
From Lemma E.4 there exists eg- 0 such that if z is an cş- stationary point then E B (z", 6).
Similarly, suppose
0 is small enough that evfe < 6g* where e
a fixed constant determined
later. By Theorem 3 PGD finds eVE-stationary point z', within K = O (1/(v))² = O (1/c)
iterations, i.e., ||G(z)) Il < ev... Because z" is in the interior of B, hence when z' is close enough
to x² (Ō is sufficient small), the gradient norm mapping G(z') is exactly Vh(z'). So we can choose
proper such that Vh(z')]l & V2
As eVV= < Eg- we know z' is also an stationary point within B (z", 88)) Then we have
1
1
(z') h (z*) s 2r
Igrad (z')1² s 27 (v2T=c)² Se.
E.2 Proof of Theorem 2 Strongly Convex Case
In this section, we show Theorem Actually, Theorem 2 a corollary of the following theorem.
Theorem 4. Suppose f is f stronnyyyy convex and K. is conver set. Then the updating sequence {z&} ) by Hom-PGI algorithm with constant step size E (0, 2.1, converges global optimum point 2t linearly, i.e.,
2 k (h (zo) h (z²))
h (zx) - h (z") S K (2o) h (z")) dist (zx, B²)
118111
where
MS81 La
10.
Proof. By strong convexity f. and convexity of Kc, one can show that f satisfy proximal PL condition over K. (see e.g. Appendix G (KNS16) i.e.
(x. 2 (xx( f(x*))
where
Dbe (x, Ai -22 min
(Vf(x), - x) + + x|12
BEK
39

---

Next, we show that h = f sb also satisfies the proximal-PP condition over B. We derive with x x= {z)) (u) as follows
(Vh(z), u 2) + 11, u - 2|1²
2
(Jw(2) v u u2 L :.o (V (z) 2))
||u - /212
2
T I.3.01.
1|u - =z12
2
(V/(b(())) (u) (z) Jo (z) 2)) (VI((((Z))) (u)) (b(2)) + L || z|1
1.,0 || z||² + (x)())) y -x) x)} 1.
2 ||u z||²
(V)((x), x) 2 u ub
(y) ||r) - +/- -x)'l
2
<(VS(x), x) +
ly x-2
2x1
where
the 2-nd line from the chain rule of the gradient,
the 3-rd line is from property of inner product, i... for vector a, b and matrix A, (ATa, aa,,, b) = (a. Ab),
the 4-th line is based on simple caculation,
the 5-th line is from Lemma C.3 and the transformation y = (u)),
the 6-th line is from the inverse transformation xb
and the last line from the bi-Lipschitz property of 4b.
Briefly, we get
-x) (Vh(z), u - z) + L5,0 I z/1² (Vf(x). x) + 211,0 Iyy x|1
(14)
2
2xy
Next, we assume C1 == 2 2 Hy without loss of generality. This because if c1 < Hgg we
have
(Vh(z), u- z) + 2
L
Iu z|| (Vf(x). x) P f -
or
(Vh(z), u- z) + L
Lap
y 212 2 2 min (Vf(xx) -x) + 11 |yy - x1|
2 min uEB
I
2
yek
2
2 2 fr) = 2 (l((z) -())))))))
That is, if Hy, we directly get the conclusion that h satisfy proximal PL condition over B: Dog (z, I h) 2 y (h (z)
(z")).
In the following, we assume 01 2 My. By Lemma I in [KNS16), for any convex set KC and differ- entiable function Dāe (x, f; is monotone increasing in μr, i.e., D&g M1; f) 2 Dōg (x. p2: f) given μ2 2 #1 > O. Hence, we have
Dāx (x, c1:f) 2 Dor (f:ff 2f -f).
Then it following from Eq. 14h that
Leg.oio Doo (z, I, T.p h)
Dac (x,c1;))
1
Do (xs
22 (f(x) -)").
2
6
Ci
9
Hence we have satisfy proximal PL condition over B:
D5n (z, L. h) 2 f. 11 (h(z) - h(z²)) = 185hi (T(z) h(2²)). (15)
c1
2
40

---

Finally, we show the linear convergence rate of the projected gradient descent algorithm. We derive
2k+1 =
[T (2 V (zt))
arg min u
(ZR aVh (2x))11²
arg min wEB
(Vh (zx) u - z₁} + ||u - Z
arg min uEB
(Vh (Z&) 7k) I 2x:11 s
where the 2-nd line is from the definition of orthogonal projection II, the 3-rd and last line is from simple calculation.
This implies
Das (z, 2. :1) - (Vh(ze), 2k+1 zx)+ 1122++1------- 2x 2x112
La (h(zz),2244 2x.1 zx)+
Zk+ 2n 2|
a
2
(16)
where the last inequality is from selection stepsize a (0, E. and recall La = 23L.0,11 Tup f.0 from Prop. D.1
Then the iterative of PGD satisfies,
(Vh(zz); 1K+1 2x.) + La
h(2411) S h((x))
12++ Zū
S h(2x)
a
Dou (Zk;
:1)
2
2
a
S h((z))
2 Dog (Zk, f,0
0p1811 (h(z)) h(zz)))
< h(Zz)
2
where
the 1-st line from the L -moothhesss of h,
the 2-nd line is from Eq. (16).
the 3-rd line is from monotone increasing property of Dog (z, h) and the choice of a E (0, T and the last line from the proximal PL condition Eq. (5) of h.
Take
p4 (h((z) h(zz)))
h(zx-1) h(z²) S
Ln
Then we rewrite
h(zk) - hi(2)) < o (h(2o) - h((z))),
where a= =1- 1881
Ith
From quadratic growth condition D.I
we have
2 o (h(zu) - 1222)))
dist(Zk, 18),
(h(zx) - h(z")) <
1g111
Let o (h(zo) 1((2²)) e. We have
log 1/e 0 0(1-0)-
K = o x
-- log 1/e)
Tog 1/a
where the last '=' holds when is closed to 1.
Remark E.5. It follows directly from the proof that the assumption of strong convexity can be relaxed. suffices for the objective to satisfy the proximal-PI, condition over the conver constraint set IC in order to achieve the convergence rate of Olog 1/e). Moreover, there exist many alternative and equivalent assumptions for the proximal-PI. condition. We list some commonly used equivalent assumptions below, where the proof of the equivalence can be referred to, e.g, [KNS6
41

---

Proximal enror bounds (Proximal-EB): There exists e > such that
x - xx- - prox 8x L
where XIC- is the orthogonal projection of x onto the optimal solution set K and prox,(x) arg min, { {g( + ||u x|²} Moreover, note that for À > 0, we have proX 1lc.
Kurdyka- (KL) condition: There exists j 0 such that
min || 2p (F(x) FF) (EFF(x)
where F(x) = f(x) + (x) and 0F(x) is the Frechet subdifferential RW09.. this case,
0F(x) [V/(x) + & E 00x
where (x) can be simlified as (x), with Nx(x)) {y (y, x) 0, E K} for x E IC and Nx(x) = 0 for x & K. Note that KL condition can imply PL condition ([V
(f f")) but the converse does not hold in general.
F Experiments Setting
F1 Problem Formulations and Instance Generation
Optimization over polyhedron: We first consider two-dimensional optimization convex polyhedron to illustrate the effectiveness of our methods. The problem is defined as:
min LSXSU
wa - 1)² s.t. a, x S b,. i= 1....,. 7ijn
(17)
where E IR2 is the decision variable, w; is the positive coefficients, and L, U E R represent the lower and upper bounds on the variables. a, E IR² and b; E represents the coefficients in nin linear constraints. The homeomorphic counterparts derived by closed-form gauge mapping as discussed in B.4
Optimization over star-shaped set: We then consider a two-dimensional optimization over non-convex star-shaped set to illustrate the effectiveness of our methods. The problem and its homcomorphic counterpart are defined as:
min Σ wi(x; - 1)2
min E wi(2; Ta,n (z) 1)2
(18)
s.t. ||x Tann(x (x)
s.t.
||z| I
<b()) [z] P (2), 22 (z))
(x) (21/ /T (x),,()),,)))) 22/T a (x)];
(19)
where z, x R² and Fo.n non-linear function with parameters a > and n Z+, defined as P. (a x2]) = sin(n (relan(22/a1)) Under the homeomorphic mapping th. the non- convex-constrained optimization problem can be transformed into ball-constrained non-convex optimization. We then compared different iterative algorithms over this problem.
Second-order cone programming: We then consider convex second-order cone programming (SOCP), which encompasses linear programming (LP), quadratic programming (QP), and convex quadratically constrained quadratic programming (QCQP) problems. This formulation has wide applications in portfolio optimization and optimal power flow problems [Low14a) Low144)
1 xxxx+xxx LSXSU
min
||, + h; S of + di, i= 1,..., Tsooc s.L.
(00)
where X E R" the decision variable, Q E Rexn symmetric positive semidefinite matrix, RR is a vector of linear cost coefficients, and L, U E RM represent the lower and upper bounds on the variables. For the second-order cone constraints, G; E mR x and h, RR define the affine function inside the norm, while 1 and d, R define the affine function on the right-hand side.
42

---

The parameter nsoe represents the number of recond-order cone constraints in the problem. The total number of constraints also includes the upper/lower bound on the decision variables.
Max-cut semidefinite programming: We consider an important class of SDP in the max-cut problem. Given graph G {N,&) E with node set E VV and edge set (i, E the max-cut SDP problem is formulated as:
Σ (1 Itj)/2
(21)
ISX1I
(RJ)EE
s.t.
Zi = 1,
i= 1
(22)
X 0,
(23)
where X > 0 indicates that X is positive semidefinite. Define the upper triangle off-diagonal
elements in X as y E NNN2 then the SDP can be equivalently reformulated in Linear Matrix Inequality (LMI))based form as:
max -1ys1
Σ (1 - 12
(24)
s.t.
Σ Uk A 0.
(25)
where A& is a symmetric matrix with positions corresponding to the k-th off-diagonal entry, and zeros elsewhere. Given such an LMI- based formulation, as discussed in B.4 Note that a "central" interior point for such a PSD cone is naturally the zero vector y 0.
the diagonal and with in the (i,j) and ()
construct the homeomorphic counterpart based closed gauge mapping
also consider solving the well-known Burer-Monteiro (BM) factorization- semidefinite program via augmented Lagrangian methods [BB03]. Let X VVT, where V Rx and is the selected rank, then we have the following low-rank SDP:
max VVT
Σ (1 r2j)/2
(26)
(L,EEE
8.L.
TH = 1, ,,
(27)
1 -15 X <
(28)
In our experiments, we consider both log-rank (r log(N) and Barvinok-Pataki (bp)-rank (r 22N factorization-bant SDP methods [Bar95 Pa BVB20]
F.2
Baseline Algorithms and Hyper-Parameters
We implement the baselines as follows:
PGD:
X [xx an (x(x))
(29)
where Th denotes the orthogonal projection onto the feasible set K., ag > is the step size at iteration k and (xx) the gradient of the objective function at point X The quadratic projection problem is solved via MOSEK for convex problems and by ALM for non-convex problems.
FW:
arg min V fxxx). s). sek
(30)
X (1 o)xx, 0gSkk
(31)
where ag E [0, 1] is the step size at iteration k. The linear minimization problem is solved via MOSEK for convex problems and ALM for non-convex problems.
ALM:
X arg (f XTg(x) + Pk 1" 1))
(32)
x
43

---

A++1 = Ax + P g(x++1)]++
(33)
where X is the Lagrange multipliers, g(x) represents the constraint functions, and Pk > 0 the dual step size. The inner unconstrained optimization problem is solved by gradient descent.
RD:
Ya+1 = Yk Or max (y&), (x(()))
(34)
where f is the radial dual of the objective function and "/c is the gauge function [Gri24b). The solution mapped to the original space after convergence as x" = y" (y") via radial dual.
Hom-PGD:
2k+1 (z Ork (((b(()))))
(35)
where 1i denotes the projection onto unit ball B, and r/ is the homeomorphism. The solution is mapped to the original space after convergence as x = <b(z))
MOSEK: commercial interior-point optimizer that solves conic optimization problems efficiently using highly optimized primal-dual interior-point methods with medictor-corrector techniques and sparse linear algebra. Note that we use an Academic license for MOSEK.
Gradient calculation: For simple quadratic objective functions, gradients calculated via closed- form formulations. Other non-trivial gradient calculations across various algorithms are im- plemented using auto-differentiation in PyTorch. We note that replacing auto-difierentiation with closed-form gradient implementations could further improve the computational efficiency of the algorithms.
Step-size: Theoretically, different algorithms employ their own step size selection strategies, such as explicit dependence on smoothness and convexity parameters, or implicit step sizes that depend on the optimal objective value Gri244] For practical implementation, we initialize a fixed step size (e.g., 10-3) and decay it by a factor of 0.999 if the objective value does not decrease, which helps identify a sufficient step size for convergence. Although more sophisticated backtracking line search methods adaptive step size schemes could accelerate convergence, we do not implement these for sake of fair comparison.
Computational Environment: We conduct our experiments across two computational platforms to accommodate different problem scales. For small-scale illustrative examples, we execute algorithm comparisons on a MacBook Pro 2023. For larger-scale SOCP and SDP experiments, we implement all algorithms Py PoTch and execute them on an Ubuntu server equipped with an NVIDIA A800 GPU and an AMD EPYC 7763 64-Core Processor.
44

---

G Supplementary Experiments Results
G.1 Illustrative Examples
POD
Fel
30%
3871
D011
20"4
Hom
autmmaity
10
12-
ALM
227
10
11
133
num Remaoon
rurning time 03)
num of Rtestton
P50
AUN
nD
Pom
(a) convergence rate
running time (S)
(c) constraint violation
(d) per-iter, time (s)
Figure Convergence performance for optimization over polyhedron.
(a) Hom-PGD
(b) Hom-PGD
(c) PGD
(d) FW
(c) ALM
(f) RD
Figure 9: Iteration trajectory for optimization over polyhedron. Hom-PGD (a) and RD (f) are also mapped to the original space visualize their trajectories.
1044
32"4
10-1
20-2
optrratty
FSD
K0
80
num Barabon
Funn ng Eime (s)
num of bertien
940
AM
8D
(a) convergence rate
(b) running time (s)
(c) constraint violation
(d) per-iter. time (s)
Figure 10: Convergence performance for optimization over a star-shaped set.
(a) Hom-PGD (b) Hom-PGD
(c) PGD
(d) FW
(e) ALM
(1 RD
Figure 11: Iteration trajectory for optimization over star-shaped set. Hom-PGD (a) and RD (f) are also mapped the original space visualize their trajectories.
45

---

G.2
Second-order Cone Programming
12-11
2011
1074
Hoo
KD
FGD
10
AMM
1071
12-1
10-4
Hgm AG0
107
100
203
300
400
500
000
(a) convergence rate
(h) running time (8)
(c) constraint violation
(d) per-iter. time (8)
Figure 12: Convergence performance SOCP with (n, m) (100, 1000).
10
FSO
10
Ham-FCD
PI
1200
10
107
30
100
200
300
930
200
60
22"h
107
2.3
2.55
300
10a
10
(a) convergence rate
running time
(c) constraint violation
(d) per-iter. time (s)
Figure 13: Convergence performance over SOCP with (n, m) (500, 1500).
101
12-11
10F
-291
PGD
Hom
PED
AMM
F2
Hoy-PPO0
107
JUF
11f
100
203
300
400
200
600
110
101
202
(a) convergence rate
running time
(c) constraint violation
(d) per-iter. time (s)
Figure 14: Convergence performance over SOCP with (n, m) (1000, 2500).
G.3 Max-Cut Semidefinite Programming
FSD
30-1
Hom-AGG
Han-
4LM og
la
223
Hom-PCD
367
102
200
600
500
30"1
200
600
900
(a) convergence rate
(b) running time (s)
(c) constraint violation
(d) per-iter. time (s)
Figure 15: Convergence performance over SDP with n 10a.
46

---

PSO ALl-igg
ALX1122
ALX-22
20-1
23
19
32"
127
(um Reratio
rurving Sime (5)
runniing time 60
150 AJH ALMop
RD hom
(a) convergence rate
running time (s)
(c) constraint violation
(d) per-iter, time (s)
Figure 16: Convergence performance over SDP with n = 20
3011
ALM-33
22-1
38-1
FSD
ALM--83
30-1
Hom
RD
gop
PED
22"
Hom HOD
107
30F
2000
610
200
(a) convergence rate
(b) running time (8)
(c) constraint violation
(d) per-iter. time (s)
Figure 17: Convergence performance over SDP with n 30
1.7
ALM-o2g
ALM-00
20"1
optinalty
optimaityy
KLM-30
10
(1m Rorabin
rurning Sime bx)
ninming Sime 6s)
150 A. ALMop
RD rommao
(a) convergence rate
(b) running time (s)
(c) constraint violation
(d) per-iter. time (s)
Figure 18: Convergence performance over SDP with n = 20
12
38-1
10-1
20:14
CLM (03
910
307
222
10
200
400
800
30-1
200
600
900
(a) convergence rate
(b) running time (s)
(c) constraint violation
(d) per-iter. time (s)
Figure 19: Convergence performance over SDP with n 50
47

---

G.4 Ablation Study
opt mallyy gap 14- 6-F -FIFF
10-2
10"1
10-1
central ip
10
10'
num of iteration
Convergence comparison.
(b) Near-Boundary IP
"Central" IP
Figure 20: Effect of interior point (IP) selection convergence behavior: Gauge mapping with a near-boundary IP results in larger Bi-Lipschitz constants, which distorts the landscape of the transformed problem H consequently reducing convergence speed in practice.
optimaiiyy gap I6 WIF
10a
adam
10-1
10
10-3
10
10
10
10a
10a
num of iteration
(a) Convergence comparison.
(b) Gradient descent
(c) Adam KB14
Figure 21: Comparison of gradient methods: We evaluate Hom-PGD under Gauge mapping with a near-boundary IP. In this non-convex landscape, standard gradient descent exhibits slower convergence, while the Adam optimizer demonstrates superior performance due its momentum acceleration and adaptive step size adjustment.
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the abstract part and the introduction part (Sec. 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Sec.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
49

---

Justification:
See Sec. 4and Appendix C
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Sec. 6 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
50

---

Answer:
[No]
Justification: does not include code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ lttipp.cc/pullic/guiice gwwcc//gwuee//eee /Code//mmdeeubiii corbbbisssioww awiionooliccoo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Sec. 6 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Sec. and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
51

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Sec. 6 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpss: wwt.rripsscppppbubp httprriss..ccpp....tttccccccci.o
Answer:
[Yes]
Justification: conforms with the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
52

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
53

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
54

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- standad components.
Please refer to our LLM policy hattps://neurips: 200p://ccccccoooeeeeee///00///// for what should or should not be described.
55


Reviews:
[{"review_id": "0p7eAOM2Od", "reviewer": "Reviewer_4NvD", "summary": "This paper presents a new, simple approach to solving a constrained convex optimization problem. The idea is to compute a homeomorphism from the convex constraint set to the unit ball, and solve the “homeomorphic constrained optimization” problem. To do so, they consider standard projected gradient descent (PGD) in the homeomorphic optimization problem. They provide convergence analysis, complexity analysis, and experiments. They suggest a specific example of a homeomorphism (the gauge/Minkowski function), and provide details about how to efficiently compute/approximate it.", "questions": "I do not really have additional questions beyond the ones I listed above. Some questions that I'm curious about, but are not relevant to how I score the paper, nor do they necessarily need a response: \n\n1. If we only care about the convergence rate in terms of iterations of projected gradient descent, do you think there would be any advantage in recomputing the gauge map centered at a point $\\mathbf{x}^\\circ$ close to the iterates? Or, is it better to just choose $\\mathbf{x}^\\circ$ to be some sort of centroid of $\\mathcal{K}$?\n\n2. You mentioned this approach builds upon [LMY23], which focuses on optimization on the probability simplex. In the case the objective is the simplex, another approach to deal with constraints is to run mirror descent (where the dual space is now unconstrained). The cost here is computing the mirror map versus the gauge map. Do you have a sense for which approach would be favorable?\n\n3. How amenable do you think this homeomorphism approach is to second-order methods?", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths.**\nThis paper was really a pleasure to read, and introduces a very natural approach to solving constrained convex problems. The theory seems pretty complete. The experiments looked convincing, with quite significant speed-ups in terms of wall-clock time. \n\n**Weaknesses.**\nI do not see any significant weaknesses in this paper. Perhaps it would be nice to include a Hom-PGD pseudocode block somewhere, say in the appendix, and also consider having Equation 35 in the main paper. I think perhaps the minor questions I would have are:\n\n1. The theory assumes that the homeomorphism is twice-differentiable, while the gauge function is only twice-differentiable almost everywhere. While the iterates will almost surely never land on a point at which $\\psi$ is not smooth, does this pose a problem in the analysis when specialized to the gauge homeomorphism?\n\n2. The theoretical analysis assumes access to exact gradients and evaluations of the homeomorphism, while in the algorithm, the gradients and gauge map are approximated. It may be reasonable to provide bounds on how accurately these need to be approximated in order to achieve a target approximation error. However, computing such a bound seems like it would be fairly tedious but not necessarily enlightening.", "was_revised": true, "final_justification": "The paper is a great contribution.", "rebuttal": "### Dear Reviewer 4NvD,\n\nWe appreciate your time and effort in reviewing our paper, and for your encouraging and insightful review. We greatly appreciate your recognition of our paper's clarity, theoretical completeness, and significant experimental results. We have addressed your questions one by one as follows.\n\n### Comments/Questions in *Weakness* part\n\n---\n\n> **C1: The theory assumes that the homeomorphism is twice-differentiable, while the gauge function is only twice-differentiable almost everywhere. While the iterates will almost surely never land on a point at which $\\gamma$ is not smooth, does this pose a problem in the analysis when specialized to the gauge homeomorphism?**\n\n---\n\nThanks for the insightful question. We underscore that while the gauge function is twice differentiable almost everywhere (and iterates almost surely avoid the non-smooth points in practice), the assumption that the homeomorphism is twice differentiable is indeed required in theory.\n\nTo bridge the gap, we can employ a classical smoothing technique to satisfy this assumption [1][2]. \n- The non-smoothness arises from the maximum operator $\\max \\{\\cdot\\}$ when handling multiple constraints (see Table 2 in Appendix B.4). \n- Specifically, the gauge mapping $\\psi$ can be defined by the inverse distance function $\\kappa$, i.e, $\\psi(z)=\\kappa(x^\\circ,z/|z|)\\cdot z +x^\\circ$ (see Appendx B.4). \n- For multiple constraints (Table 2), $\\kappa(\\cdot)$ can be written in the form $\\kappa(x^\\circ, \\cdot)=\\max_i{\\kappa_i }$ where $\\kappa_i$ is the individual inverse distance function for each constraint. \n\nWe smooth this using the log-sum-exp approximation with parameter $\\eta > 0$:\n\n$$\n\\kappa_\\eta(x) = \\eta \\log \\left(\\sum_{i=0}^n \\exp\\left(\\frac{\\kappa_i(x)}{\\eta}\\right)\\right),\n$$\n\nwith the corresponding gradient\n\n$$\n\\nabla \\kappa_\\eta(x)=\\sum_{i} \\lambda_i \\nabla \\kappa_i(x) \\quad \\text{where} \\quad \\lambda_i=\\frac{\\exp\\left(\\kappa_i(x)/\\eta\\right)}{\\sum_j \\exp\\left(\\kappa_j(x)/\\eta\\right)}.\n$$\n\nBy replacing the objective $h=f\\circ\\psi$ with $h=f\\circ\\psi_\\eta$ where $\\psi_{\\eta}(\\cdot)=\\kappa_\\eta(x^\\circ,\\cdot)\\cdot z+x^\\circ$, we obtain a twice-differentiable homeomorphism. The smoothing introduces an optimality gap of $\\mathcal{O}(\\eta)$ (here the hidden constant is dependent on the Lipschitz constant of $f$), which can be made arbitrarily small by choosing $\\eta$ sufficiently small.\n\nIn practice, this smoothing has a minor impact. Our new experiments show that Hom-PGD with the original gauge map and its smoothed version ($\\eta=10^{-5}$) produce a similar convergence curve with respect to the optimality gap, but the smooth version costs a little bit more per-iteration computation time than the original gauge map.\n\n|            | Mean (s) | Std (s)         |\n|------------|----------|-----------------|\n| Original   | 0.0061   | 0.0033        |\n| Smoothed   | 0.0080   | 0.0086       |\n\n*Table: Comparison between Hom-PGD with gauge map and its smoothed version ($\\eta=10^{-5}$) in 100-dim SOCP.*\n\nWe will include this discussion and supporting experimental results in the final version. Thank you for highlighting this important theoretical consideration.\n\nRef:\n- [1] Beck A, Teboulle M. Smoothing and first order methods: A unified framework[J]. SIAM Journal on Optimization, 2012, 22(2): 557-580.\n- [2] Grimmer B. Radial duality part II: applications and algorithms[J]. Mathematical Programming, 2024, 205(1): 69-105.\n\n---\n\n> **C2: The theoretical analysis assumes access to exact gradients and evaluations of the homeomorphism, while in the algorithm, the gradients and gauge map are approximated. It may be reasonable to provide bounds on how accurately these need to be approximated in order to achieve a target approximation error. However, computing such a bound seems like it would be fairly tedious but not necessarily enlightening.**\n\n---\n\nWe appreciate the reviewer's insightful observation regarding the gap between theoretical assumptions and practical implementation.\n\n- Our theoretical analysis follows standard conventions in the optimization literature (e.g., [3]), assuming access to exact gradients and gauge mappings. This provides foundational insights, even though practical algorithms may rely on approximations.\nIn more general cases where approximations are required, the incurred error is typically logarithmic (via bisection methods) and negligible in practice.\n\n- Nevertheless, we acknowledge that deriving explicit bounds on the accuracy of the gradient and gauge map approximations with respect to the final solution error is indeed an interesting direction, which has been studied in, e.g., [4]. \nTypically, the optimality gap is augmented by an additional term of order \\(\\mathcal{O}(\\delta)\\), where \\(\\delta\\) represents the error of the (gradient or gauge mapping) oracle at each iteration. \n\nWe will add these discussions to the final version of our paper. \n\nRef:\n- [3] Lu Z, Brukhim N, Gradu P, et al. Projection-free adaptive regret with membership oracles[C]//International Conference on Algorithmic Learning Theory. PMLR, 2023: 1055-1073.\n- [4] Devolder O, Glineur F, Nesterov Y. First-order methods of smooth convex optimization with inexact oracle[J]. Mathematical Programming, 2014, 146(1): 37-75.\n\n---\n\n> **C3: Perhaps it would be nice to include a Hom-PGD pseudocode block somewhere, say in the appendix, and also consider having Equation 35 in the main paper.**\n\n---\n\nThank you for the suggestion. We will add it to the main body in the final version. \n\n### Questions\n\n---\n\n> **Q1: If we only care about the convergence rate in terms of iterations of projected gradient descent, do you think there would be any advantage in recomputing the gauge map centered at a point $x^\\circ$ close to the iterates? Or, is it better to just choose $x^\\circ$ to be some sort of centroid of $\\mathcal{K}$?**\n\n---\n\n\n\nThanks for the insightful questions. We would like to clarify that it is not necessary—nor beneficial from a convergence standpoint—to continuously update $x^\\circ$ during optimization.\n\n- From our theoretical analysis (Theorems 1, 2, and 3), the convergence rate depends primarily on the bi-Lipschitz constant of the gauge mapping, which is determined by the choice of the interior point $x^\\circ$. Importantly, this dependency is independent of the current iterations. \n\n- Moreover, adaptively changing $x^\\circ$ during the iterations could alter the gauge mapping at each step, effectively modifying the landscape of the optimization problem. This could destabilize the algorithm and even prevent convergence, as the optimization landscape would no longer be consistent across iterations.\n\n- In practice, recomputing the gauge map centered at a different point in each iteration is computationally expensive and may introduce additional errors. \n\nTherefore, choosing $x^\\circ$ as a fixed central point (such as the centroid of $\\mathcal{K}$) is preferable both theoretically and practically.\n\n---\n\n> **Q2: You mentioned this approach builds upon [LMY23], which focuses on optimization on the probability simplex. In the case the objective is the simplex, another approach to deal with constraints is to run mirror descent (where the dual space is now unconstrained). The cost here is computing the mirror map versus the gauge map. Do you have a sense for which approach would be favorable?**\n\n---\n\nThanks for the interesting questions.\n\n- For optimization on the probability simplex specifically, both our gauge-based approach and mirror descent achieve comparable convergence rates. Mirror descent with entropic regularization is indeed well-established and efficient for this domain.\n- From a practical standpoint, our method may require tuning additional hyperparameters (e.g., the interior point $x^\\circ$), while mirror descent for the simplex is more straightforward to implement with the standard entropic mirror map.\n\nHowever, the key advantage of our approach is its generality: it provides a unified framework that seamlessly extends to arbitrary compact convex sets without requiring problem-specific design. In contrast, mirror descent requires carefully crafted mirror maps for each domain, which may not always be available or computationally tractable. For instance, finding appropriate mirror maps for complex constraint sets (e.g., PSD cones with additional linear constraints) can be challenging, whereas our gauge-based approach handles these naturally.\n\nThus, while mirror descent may be preferable for the simplex alone, our method offers broader applicability as a general-purpose constrained optimization framework.\n\n---\n\n> **Q3: How amenable do you think this homeomorphism approach is to second-order methods?**\n\n---\n\nThanks for the insightful questions.\n\n- **Computational Complexity:** Second-order methods would require computing the Hessian of the composite objective $f\\circ\\psi$. Since the Hessian of the gauge map $\\psi$ is a third-order tensor, this becomes both computationally intensive and memory-prohibitive. In contrast, our first-order approach only requires gradients, making it significantly more efficient.\n\n- **Convergence Behavior:**  We also remark that the composite objective $f\\circ\\psi$ is generally non-convex. Despite the well-established faster convergence behavior of second-order methods for convex problems, analyzing the convergence over a non-convex landscape to the global optimum is more challenging and would likely require additional smooth assumptions beyond the standard analysis used for second-order methods.\n\nWhile extending our framework to second-order methods is theoretically possible, these computational and analytical challenges suggest that first-order methods are more practical for this setting. We view second-order extensions as an intriguing direction for future research, particularly for special cases where the gauge mapping structure might simplify the Hessian computation."}, {"review_id": "zvg7UiqLGG", "reviewer": "Reviewer_w43j", "summary": "In this paper, the authors propose **Hom-PGD**, a new projection-free first-order method for solving convex optimization problems over general compact convex sets. Hom-PGD reparameterizes the original problem into an equivalent optimization problem constrained to a Euclidean ball, applies standard PGD to solve the reparameterized problem, and then maps the solution back to the original domain. The method achieves optimal convergence rates in the unaccelerated setting and maintains a low per-iteration complexity of $\\mathcal{O}(n^2)$.", "questions": "See the Weaknesses section.\n\nOne minor question: Hom-PGD still requires projection onto a ball. Given this, it is unclear whether \"projection-free\" is the most appropriate term to describe the method.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper presents a thorough literature review of projection-free methods and clearly communicates the theoretical results. Overall, it is well-written, demonstrating both quality and clarity.\n\n2. The proposed algorithm is the first projection-free, first-order framework capable of solving optimization problems over general compact convex sets. It achieves the optimal convergence rate in the unaccelerated setting without relying on expensive oracles, highlighting its significance and originality.\n\n**Weaknesses**\n\n1. The LICQ assumption in Proposition 5.2 appears to be somewhat strong and may limit the applicability of the proposed algorithm. Is it possible to relax this assumption by adopting a weaker constraint qualification?\n\n2. Similarly, the strict complementary slackness assumption in Theorem 1 could be restrictive. Can this assumption be relaxed?\n\n3. In line 261, the authors claim that the proposed algorithm has significantly lower complexity compared to second-order methods. However, is this always the case for first-order methods? It may be beneficial to include a section comparing the overall computational cost with both other first-order and second-order methods.", "was_revised": true, "final_justification": "The authors provided detailed rebuttal and addressed my concerns and questions. Therefore, I raised my score.", "rebuttal": "### Dear Reviewer w43j,\n\nThank you for the time and effort in giving our paper a thorough review. We are very happy to receive your comments and suggestions. For your concerns and questions, we address them one by one as follows.\n\n---\n\n> **Q1: The LICQ assumption in Proposition 5.2 appears to be somewhat strong and may limit the applicability of the proposed algorithm. Is it possible to relax this assumption by adopting a weaker constraint qualification?**\n\n---\n\n\nThank you for the thoughtful question.\n\nWe acknowledge that the Linear Independence Constraint Qualification (LICQ) can be strong in general. However, it is a standard assumption widely adopted in the optimization literature to ensure the validity of KKT conditions and local optimality results.\n\n- In our specific setting, the LICQ assumption is not restrictive. For problem $\\mathcal{H}$, the only constraint is $||z||^2 - 1 \\leq 0$, which defines the unit Euclidean ball. By definition, LICQ holds at any boundary point $z^*$ where the constraint is active, as the gradient of the constraint is non-zero. Therefore, LICQ is automatically satisfied in our case.\n\n- More generally, the LICQ assumption can indeed be relaxed. In Appendix D, we show that our results hold under the weaker Mangasarian-Fromovitz Constraint Qualification (MFCQ) (see Definition D.3 and Proposition D.6). Here, one should note LICQ can imply MFCQ thereby MFCQ is a weaker condition. Additionally, other constraint qualifications like Slater's condition may be appropriate in convex settings (if problem H is also convex). Exploring weaker or alternative constraint qualifications for broader applicability is a valuable direction for future work.\n\nWe will update the paper to clarify these points in the final version.\n\n---\n\n> **Q2: Similarly, the strict complementary slackness assumption in Theorem 1 could be restrictive. Can this assumption be relaxed?**\n\n---\n\n\nThank you for raising this important point.\n\nWhile the strict complementary slackness assumption can be strong in general, it is a standard condition commonly used in the optimization literature to ensure uniqueness and stability of KKT multipliers. Its use allows for cleaner theoretical analysis and has precedent in many related works.\n\nRelaxing this assumption within our current proof framework is non-trivial, as it plays a key role in the analysis of KKT conditions and directional optimality. Addressing this would require more delicate treatment of degenerate cases and potentially different analytical tools. We view this as an interesting open problem and a promising direction for future work.\n\nWe will revise the paper to clarify the role of this assumption and discuss its potential relaxation in the final version.\n\n---\n\n> **Q3: In line 261, the authors claim that the proposed algorithm has significantly lower complexity compared to second-order methods. However, is this always the case for first-order methods? It may be beneficial to include a section comparing the overall computational cost with both other first-order and second-order methods.**\n\n---\n\n  \nThanks for the insightful question. While first-order methods generally have lower per-iteration complexity than second-order methods (avoiding expensive Hessian computations), a more nuanced analysis would indeed be valuable.\n\n-  In our submitted manuscript (lines 306–308), we indeed compare the run-time complexity with a second-order method empirically in a 1000-dim SOCP.  \n- Specifically, we compare our methods to a commercial solver, MOSEK (which uses highly optimized second-order interior point methods).\n- MOSEK costs 5424 seconds to solve the 1000-dim instance, while Hom-PGD takes less than 600 seconds to reach a similar optimality gap.\n\nWe agree that a more comprehensive comparison of different problems would further strengthen the paper. We will include a new table in the final version that provides comprehensive run-time complexity for both first-order and second-order baselines.\n\n---\n\n> **Q4: Hom-PGD still requires projection onto a ball. Given this, it is unclear whether \"projection-free\" is the most appropriate term to describe the method.**\n\n---\nThanks for the insightful question.\n\nWhile Hom-PGD involves projection onto a Euclidean ball, this operation has a closed form and is trivial. The term \"projection-free\" specifically refers to avoiding expensive projections onto original complex constraint sets—a usage that aligns with standard conventions in the literature, e.g., [1,2].\n\nWe will clarify this in the revised version to prevent any misunderstanding.\n\n- [1] Li Q, McKenzie D, Yin W. *From the simplex to the sphere: faster constrained optimization using the Hadamard parametrization*. Information and Inference: A Journal of the IMA, 2023, 12(3): 1898-1937.\n- [2] Lu Z, Brukhim N, Gradu P, et al. *Projection-free adaptive regret with membership oracles*. In *International Conference on Algorithmic Learning Theory*. PMLR, 2023: 1055-1073."}, {"review_id": "MyrgIlvdya", "reviewer": "Reviewer_HSQR", "summary": "The paper investigates projection-free first-order methods for optimization over a compact and convex set. The key contribution of the paper is to propose an approach, Hom-PGD, which contrary to the popular Frank-Wolfe algorithm does not require a linear minimization oracle (LOO). The main insight is to transform the convex set into a ball, and then solve the transformed problem. The approach achieves optimal convergence rates while enjoying low per-iteration complexity. The experiments show a speed up of 3-6 orders of magnitude in the per-iteration runtime for some problem.", "questions": "- Which sets are best handled by the proposed approach versus existing algorithms, and which sets admit a closed-form gauge mapping? \n- Does the speed up demonstrated in the experiments hold even for complicated sets that do not admit a closed-form gauge mapping?\n- The behavior of the ALM approach in Figure 4 seems unexpected. Is the large optimality gap due to the suboptimality gap in the SDP relaxation? Otherwise, I would expect Burer Monteiro to converge fairly quickly?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is very clear and easy to follow. Abstract and introduction provide compelling problem statement and motivations.\n- The idea is elegant in its simplicity: transform the convex set into a ball and optimize over the unit ball instead!Proposition 5.2 shows that while this transformation might break convexity, stationary points of the nonconvex problem can be mapped to global optima of the original problem.\n- The convergence analysis is comprehensive (e.g., it covers the convex, strongly convex and non-convex case) and reports optimal convergence rates.\n- The experiments show impressive results, with a 4-6 orders of magnitude per-iteration runtime reduction compared to baselines.\n\nWeaknesses:\n- In general, the paper remains vague about which sets are best handled by the proposed approach versus existing algorithms, and which sets admit a closed-form gauge mapping. This prevents the reader from fully understanding the impact of the proposed method. \n- The experiments would benefit from adding a breakdown of the runtime for the initialization and the last-step computation for Hom-PGD.\n- A main concern is that the experiments do not clarify if the considered problem instances admit a closed-form gauge mapping. In other words, does the speed up demonstrated in the experiments hold even for complicated sets that do not admit a closed-form gauge mapping?\n- The behavior of the ALM approach in Figure 4 seems unexpected. Is the large optimality gap due to the suboptimality gap in the SDP relaxation? Otherwise, I would expect Burer Monteiro to converge fairly quickly?\n\nMinor weaknesses:\n- Line 31: “Despite their slower convergence rate, …”: this sentence is not grammatically correct as written.\n- Right after stating problem (P), it would be useful to provide an example of problems where existing methods do not perform well. This would help the reader visualize the type of constraints that make the problem challenging.\n- Line 90: The paper structure feels a bit redundant and could be merged into the overview of contributions at the end of Section 1.\n- Footnote 2 on page 3 should refer to Appendix B.1 instead of B.2 I think.", "was_revised": true, "final_justification": "The paper presents a strong and interesting contribution. The proposed idea is elegant and effective and the authors have addressed my remaining concerns.", "rebuttal": "### Dear Reviewer HSQR,\n\nThank you for your time and effort in reviewing our paper, and for your encouraging and insightful review. We have addressed your questions as follows one by one. \n\n**We note that the comments in the Weakness section cover the questions.** Therefore, we list the comments in Weakness section and give the responses in the following.\n\n---\n\n> **C1: In general, the paper remains vague about which sets are best handled by the proposed approach versus existing algorithms, and which sets admit a closed-form gauge mapping. This prevents the reader from fully understanding the impact of the proposed method.**\n\n---\n\n\n\nThank you for the insightful comment.  We agree that clarifying which constraint sets are best suited for our approach is important for understanding its practical impact. \n\nOur approach is particularly effective for constraint sets that admit closed-form gauge mappings, which encompasses a broad class of important convex optimization problems, including: QP, SOCP, and SDP. Besides, it also works for general compact convex sets with bisection-induced gauge mapping.  \n- We provide a comprehensive treatment of these cases in Appendix B.4, with specific examples and closed-form expressions summarized in Table 2. (Due to space limitations, this discussion was placed in the appendix.)\n\nThe key advantage of our method over existing algorithms lies in its ability to handle **general compact convex** constraint sets where projection oracles or linear minimization oracles are computationally expensive or unavailable. While we briefly mentioned this in the introduction, we agree it deserves more prominent placement.\n\nWe appreciate the reviewer's guidance in improving the clarity and impact of our presentation.\n\n---\n\n> **C2: The experiments would benefit from adding a breakdown of the runtime for the initialization and the last-step computation for Hom-PGD.**\n\n---\n\n\nThank you for the suggestion.\n\nWe thank the reviewer for this constructive suggestion. While the initialization (*interior point computation*) and final-step (*gauge map computation*) computation costs are minor compared to the total iteration cost, we agree that providing this breakdown would enhance transparency and completeness of our experimental analysis. \n\n- For example, as shown in the table, the initialization and final-step computations together account for less than 0.1% of the total runtime, confirming that the computational overhead of our method is minimal. \n\n| Problem     | initialization     | total iteration     | final-step     |\n|-------------|-----------|-----------|----------|\n| SOCP        | 0.060%    | 99.93%    | 0.0003%  |\n| MaxCut-SDP  | 0 (explicit interior point) | 99.99% | 0.0002%  |\n||\n\n*Table: Percentage of initialization/iteration/last-step running time for 50-dim SOCP and 50×50 MAX-CUT SDP*\n\nWe will also include these breakdown tables alongside our main experimental results for problems of different dimensions in the final version of our paper to enhance the completeness. Thanks for your suggestion.\n\n\n---\n\n> **C3: A main concern is that the experiments do not clarify if the considered problem instances admit a closed-form gauge mapping. In other words, does the speed up demonstrated in the experiments hold even for complicated sets that do not admit a closed-form gauge mapping?**\n\n---\n\n \nThank you for raising this important point.\n\n- All problem instances in our experiments (SOCP and SDP) do admit **closed-form** gauge mappings. We selected these problems because they represent widely-used convex optimization classes with significant practical importance in systems processing and machine learning applications. Specifically, SDP is one of the most general convex program classes that still admits efficient closed-form gauge mappings.\n\n- While in the **general convex** case, the gauge map can be efficiently computed via bisection (see *Appendix B.4* for details) and our theoretical results guarantee that the proposed method remains applicable, we agree that it is valuable to evaluate performance in such scenarios.\n   - For example, we test polynomial constraints using the sum-of-squares formulation (common in robotic control): for such $m$ polynomial inequalities with $n$ variables and degree $d$ (with total terms of $\\binom{n+d/2}{d/2}^2$), the gauge function computation via bisection (tolerance of $10^{-5}$) on a MacBook Pro 2023 costs is presented in the follow table:\n\n| $m$ | $n$   | $d$  | $\\binom{n+d/2}{d/2}^2$ | Gauge calculation (s) |\n|-----|-------|------|-------------------------|------------------------|\n| 10  | 10    | 4    | 4,356                   | 0.0250                 |\n| 10  | 50    | 4    | 1,758,276               | 0.4919                 |\n| 10  | 100   | 4    | 26,532,801              | 5.5915                 |\n||\n\nWe will further include additional experiments on such polynomial-constrained optimization problem instances without closed-form gauge mappings in the revised version to further support the generality and robustness of our approach.\n\n\n---\n\n> **C4: The behavior of the ALM approach in Figure 4 seems unexpected. Is the large optimality gap due to the suboptimality gap in the SDP relaxation? Otherwise, I would expect Burer Monteiro to converge fairly quickly?**\n\n---\n\n\nThank you for the insightful comment.\n\nThe large optimality gap is indeed due to the non-convexity introduced by the Burer-Monteiro (BM) reformulation, not the SDP relaxation itself. \n- When the rank parameter is small (e.g., $\\log(d)$ in our experiments following the initialization setting of [1]), the BM approach can converge to poor local minima, which explains the behavior observed in Figure 4. While BM can converge quickly to a local minimum, the quality of this solution depends critically on the rank parameter choice.  \n\nWe will also explore adjusting the rank parameter to improve the performance and fairness of this comparison.\n\n- It's worth noting the fundamental difference between these approaches: BM methods solve a non-convex reformulation and provide optimality guarantees only in over-parameterized settings, while our method operates on a reparameterized problem via a homeomorphic mapping, guaranteeing global optimality. We include BM as a baseline because it represents the current state-of-the-art for large-scale SDP solving, making it an important reference point despite these fundamental differences.\n\n\n[1] Han, Qiushi, Zhenwei Lin, Hanwen Liu, Caihua Chen, Qi Deng, Dongdong Ge, and Yinyu Ye. \"Accelerating low-rank factorization-based semidefinite programming algorithms on GPU.\" arXiv preprint arXiv:2407.15049 (2024).\n\n---\n\n### Minor Comments\n\n---\n\n> **C5: Line 31: \"Despite their slower convergence rate, ...\": this sentence is not grammatically correct as written.**\n\n---\n\n\nThank you for pointing this out. We will revise the sentence to correct the grammar in the final version of the paper.\n\n---\n\n> **C6: Right after stating problem (P), it would be useful to provide an example of problems where existing methods do not perform well. This would help the reader visualize the type of constraints that make the problem challenging.**\n\n---\n\n\nThank you for the suggestion. We agree that providing a concrete example early on helps clarify the motivation. Initially, we included a toy example in Figure 1 that illustrates how existing general methods can struggle with general constrained problems due to the high cost of the projection operator. To improve clarity and flow, we will provide an illustrative example where existing methods do not perform well closer to the statement of problem (P) in the revised version.\n\n---\n\n> **C7: Line 90: The paper structure feels a bit redundant and could be merged into the overview of contributions at the end of Section 1.**\n\n---\n\n\nThank you for the helpful suggestion.\n\nWe agree that the structure summary in Line 90 may be redundant. In the revised version, we will merge it into the overview of contributions at the end of Section 1 to improve clarity and reduce repetition.\n\n---\n\n> **C8: Footnote 2 on page 3 should refer to Appendix B.1 instead of B.2 I think.**\n\n---\n\n\nThank you for pointing this out. We will revise it in the final version of the paper."}, {"review_id": "X4QLrNtZ7i", "reviewer": "Reviewer_ERsh", "summary": "This paper proposes a novel method for solving constrained convex optimization problems. The main idea is to construct a homeomorphism between the original problem and a transformed problem with a unit ball constraint. The transformed problem can be solved without using expensive LOO step or complicated projection steps in PGD. The paper provides convergence guarantees for the proposed method in both convex and non-convex settings.", "questions": "- Why is the proposed method called \"projection-free\"? The transformed problem still involves a constraint (even though it is a unit ball with closed closed-form solution) and requires projection.\n\n- In Figure 1, why is the initial point located outside the constrained set?\n\n- The paper only evaluates toy examples. Could the method also be applied to practical settings such as adversarial attacks in neural networks, especially with some non-ball constraints? Can the author discuss under which setting the proposed method might be useful for deep learning or neural network training?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- The method is novel and effective. The homeomorphism and Gauge Mapping is well constructed and the connection between the Global Optimality of the original problem and the stationary point of transformed problem is good. (Proposition 5.2)\n\n- The paper presents strong theoretical results to support the proposed method and shows that it can achieve the same optimal convergence rate as raw gradient descent.\n\n- The empirical results are promising, showing faster convergence compared to LOO and projected gradient descent.\n\n- The paper is well-written and well-structured, I do not find any typos, the visualization is good\n\n\n# Weaknesses:\n- Very minor problem: line 34 could be clarified. Specifically, the case “O(1/epsilon) in the convex setting” requires the gradient to be Lipschitz continuous, and the “O(1/epsilon^2) in the non-convex setting” seems to need additional assumption, i.e., gradient Lipschitz continuity.\n-- Section 4.2 is more important than the theoretical analysis in Section 4.5 in my view because it discuss with the construction of the homeomorphism, which is crucial for practical implementation. However, Algorithm 1, Table 2, and some revalant discussion are deferred to the appendix. It would improve the paper to move them into the main body.\n- The paper claims that a key benefit over FW (or LOO) is avoiding expensive linear minimization. It would be useful to include concrete examples of problems where this is indeed costly, to enhance the paper’s self-consistency. Additionally, the limitation section can be improved by considering the following question.: Are there any case where FW (or LOO) is more efficient than the proposed method? For instance, when the algorithm is slow, or when the closed-form expression in Table 2 is hard to derive while LOO is is easily to solve?", "was_revised": true, "final_justification": "The detailed rebuttal has solved my concerns, and I will update the score.", "rebuttal": "### Dear Reviewer ERsh, \n\nThank you for your time and effort in reviewing our paper, and for your encouraging and insightful review. We have addressed your questions as follows one by one.\n\n### Comments/Questions in *Weakness* section\n---\n\n> **C1: Very minor problem: line 34 could be clarified. Specifically, the case \"O(1/epsilon) in the convex setting\" requires the gradient to be Lipschitz continuous, and the \"O(1/epsilon$^2$) in the non-convex setting\" seems to need additional assumptions, i.e., gradient Lipschitz continuity.**\n\n---\n\n\nWe thank the reviewer for this careful observation. You are correct that these complexity results require the gradient Lipschitz continuity assumption.\n\nIn the revised version, we will modify line 34 to explicitly state those conditions. Thank you for helping us improve the precision of our presentation.\n\n---\n\n> **C2: Section 4.2 is more important than the theoretical analysis in Section 4.5 in my view because it discuss with the construction of the homeomorphism, which is crucial for practical implementation. However, Algorithm 1, Table 2, and some relevant discussion are deferred to the appendix. It would improve the paper to move them into the main body.**\n\n---\n\n\nThank you for the helpful suggestion. We agree that the construction of the homeomorphism in Section 4.2 is central to the practical implementation and deserves more prominence. Due to space constraints, we initially placed Algorithm 1, Table 2, and the associated discussion in the appendix. However, since the final version allows for an additional page, we will move these elements into the main body to improve clarity and accessibility.\n\n---\n\n> **C3: The paper claims that a key benefit over FW (or LOO) is avoiding expensive linear minimization. It would be useful to include concrete examples of problems where this is indeed costly, to enhance the paper's self-consistency. Additionally, the limitation section can be improved by considering the following question: Are there any case where FW (or LOO) is more efficient than the proposed method? For instance, when the algorithm is slow, or when the closed-form expression in Table 2 is hard to derive while LOO is easily to solve?**\n\n---\n\n\n\nThank you for this insightful comment and the suggestions for improving the limitations discussion.\n\nRegarding the cost of linear minimization, a concrete example is semidefinite programming (SDP). In this case, the linear optimization oracle (LOO) required by Frank-Wolfe (FW) corresponds to solving an SDP itself, which defeats the purpose of using FW as a low-cost alternative. Therefore, FW is not applicable in such settings.\n\n- This limitation is also reflected in our experimental benchmarks, where all tasks involve constraint sets for which LOO is expensive or impractical. To enhance the paper's self-consistency, we will include a small toy example in the introduction that highlights a case where linear minimization is prohibitively expensive.\n\nRegarding the reviewer's follow-up question on when FW (or LOO-based methods) might be more efficient than our approach, we offer the following considerations:\n\n- **Computational Cost:** Our method relies only on a *membership oracle* (one just needs to check whether a point is feasible), which is generally cheaper than a *linear optimization oracle* (one needs to solve a linear optimization over the feasible set) for general convex sets. \n    - Intuitively, solving the LOO at least requires evaluating the constraint/objective function, and the membership oracle only needs to evaluate the constraint to check feasibility.\n\n- **Convergence Behavior:** Under standard assumptions (e.g., smoothness and convexity), the convergence rates of FW and our method are comparable, even though there are slightly different conditions for the two settings. \n\nTherefore, our proposed method has a lower run-time cost than FW methods overall.\n\nWe will revise the limitations section to include this discussion in the final version of our paper.\n\n---\n\n### Questions\n\n---\n\n> **Q1: Why is the proposed method called \"projection-free\"? The transformed problem still involves a constraint (even though it is a unit ball with closed closed-form solution) and requires projection.**\n\n---\n\n \nThe term \"projection-free\" specifically refers to avoiding expensive projections onto original complex constraint sets. Hence while in our work, we use the term \"projection-free\" due to the closed and trivial projection operator, which is a usage that aligns with standard conventions in the literature e.g.:\n\n- Li Q, McKenzie D, Yin W. *From the simplex to the sphere: faster constrained optimization using the Hadamard parametrization*. Information and Inference: A Journal of the IMA, 2023, 12(3): 1898–1937.\n- Lu Z, Brukhim N, Gradu P, et al. Projection-free adaptive regret with membership oracles[C]//International Conference on Algorithmic Learning Theory. PMLR, 2023: 1055-1073.\n\nWe will clarify this in the revised version to prevent any misunderstanding.\n\n---\n\n> **Q2: In Figure 1, why is the initial point located outside the constrained set?**\n\n---\n\n \nFor the PGD algorithm, the initial point is randomly generated and does not need to be feasible because the projection operator will make each iteration point feasible. In Fig. 1, we randomly generate an initial point, which is located outside coincidentally.\n\n---\n\n> **Q3: The paper only evaluates toy examples. Could the method also be applied to practical settings such as adversarial attacks in neural networks, especially with some non-ball constraints? Can the author discuss under which setting the proposed method might be useful for deep learning or neural network training?**\n\n---\n\n\n\nWe thank the reviewer for this excellent suggestion to connect our work to deep learning applications.\n\nWhile our experiments include large-scale SOCP and SDP problems with practical importance, we agree that demonstrating applications in deep learning would strengthen the paper's impact. Our method is indeed applicable for adversarial robustness and constrained neural network training.\n\n- **Adversarial Attack**: Standard PGD-based attacks use simple $\\ell_2$ or $\\ell_\\infty$ ball constraints where projection is trivial. However, recent work has shown that more sophisticated constraint sets (e.g., non-uniform bounds) can be more effective. For these cases, projection becomes computationally expensive, making our approach advantageous.\n\n    - For instance, when perturbations are constrained to non-uniform balls [1], Hom-PGD can efficiently handle these constraints via gauge mapping. \n    - We include experiments comparing standard PGD, Non-orthogonal PGD [1], and Hom-PGD on MNIST with various non-ball perturbation constraints:\n\n\n|               | $\\|Wv\\|_{0.5} \\le 1$ | $\\|Wv\\|_4 \\le 0.1$ |\n|---------------|----------------------|--------------------|\n| PGD           | N/A (non-convex)     | N/A (polynomial)   |\n| Non-orthogonal-PGD | 0%, 0.0032s      | 12.7%, 0.0030s     |\n| Hom-PGD       | 0.1%, 0.0034s        | 12.2%, 0.0033s     |\n\n*Table: Attack success rate and per-iteration cost of PGD, Non-orthogonal-PGD, and Hom-PGD for trained CNN under 1,000 input samples with Non-uniform Perturbations [1] in MNIST dataset*\n\n\n\n\n\n- **Constrained NN Policy**: Our method also applies to safety-critical applications where neural network outputs must satisfy convex constraints [2]. By transforming the output space via gauge mapping, we can train networks with guaranteed constraint satisfaction while maintaining efficient gradient updates.\n\nWe will add those discussions to Sections 5 and 6 in the final version, including deep learning applications with experimental validation, demonstrating the practical relevance of our approach beyond traditional convex optimization problems.\n\n**Reference:**\n\n- [1] Erdemir E, Bickford J, Melis L, et al. *Adversarial robustness with non-uniform perturbations*. NeurIPS 2021.\n- [2] Tabas D and Zhang B. Computationally efficient safe reinforcement learning for power562systems. ACC 2022"}]

Author rebuttal:

Meta-review: This paper introduces Hom-PGD, a projection-free first-order method for optimizing over general compact convex sets without expensive linear minimization oracles. It leverages a homeomorphism between the constraint set and a unit ball to transform the original optimization problem into a ball-constrained formulation. The algorithm achieves optimal convergence rates matching gradient descent in (strongly) convex or non-convex settings. The paper received four detailed reviews, in which it is unanimously agreed that the proposed framework is novel and theoretically sound, and the demonstrated empirical speed-ups over baselines are impressive. Reviewers also raised  minor concerns regarding assumptions, terminology, and experimental transparency, which were effectively addressed in rebuttals. 

Overall, based on the reviews, authors responses and discussions, it was assessed that this submission makes a sufficiently novel and significant contribution to the field of constrained optimization. The meta reviewer thus would be happy to recommend the paper for acceptance. Congratulations for the nice piece of work!
Decision: Accept (spotlight)