Linear Convergence of a Frank-Wolfe-type Method over the Spectrahedron without Strict Complementarity

We consider smooth convex minimization over the spectrahedron using Frank-Wolfe-type methods based only on extreme-eigenvector computations. In our recent work [8] we presented the first ambient-dimension-independent linear convergence rate under quadratic growth. However, the method makes an additional strong strict complementarity assumption, it is randomized, its linear rate holds only after a burn-in phase and in expectation, and it requires the objective smoothness constant. We show that these limitations can be removed. Assuming quadratic growth and that all optimal solutions have the same rank, but without assuming strict complementarity, we give a deterministic and parameter-free Frank-Wolfe-type method with a global ambient-dimension-independent linear convergence rate.

We consider the problem

min f (X),

X∈S n

S n:= X ∈ Sn X ⪰ 0, Tr(X) = 1.

(1)

Throughout, Sn denotes the space of real n × n symmetric matrices and Sn+ its positive-semidefinite cone. The set S n is known as the spectrahedron in Sn. For A ∈ Sn, we order the eigenvalues as λ1 (A) ≥ · · · ≥ λn (A). We use ⟨A, B⟩:= Tr(AB) for the trace inner product, and A† denotes the Moore–Penrose pseudoinverse of A. Throughout, ∥·∥ denotes an arbitrary unitarily invariant matrix norm and ∥·∥∗ its corresponding dual norm with respect to the trace inner product. We use ∥·∥2 for the Euclidean norm of column vectors and the spectral norm of matrices, and ∥·∥F for the Frobenius norm of matrices. We assume that f is convex and β-smooth over S n with respect to this primal-dual norm pair, i.e.,

∥∇f (X) − ∇f (Y)∥∗ ≤ β∥X − Y∥

∀X, Y ∈ S n.

(2)

In particular, the following standard inequality holds:

f (Y) ≤ f (X) + ⟨Y − X, ∇f (X)⟩ + β/2 ∥Y − X∥2.

(3)

Let X ∗:= argminX∈S n f (X) denote the optimal set and let f ∗ denote the optimal value. For our linear convergence result we make the following two assumptions.

Assumption 1 (quadratic growth). There exists a scalar α > 0 such that for any X ∈ S n,

min ∥X − X∗ ∥2 ≤ 2/α (f (X) − f ∗).

(4)

Assumption 2 (common rank of optimal solutions). There exists an integer r∗ ∈ 1,..., n such that rank(X∗) = r∗ for all X∗ ∈ X ∗. Accordingly we define λ∗r∗:= minX∗ ∈X ∗ λr∗ (X∗).

For more discussion of Assumption 2 and its implications see Lemma 1 in the sequel and the text following it.

Define also the quantities:

e:= supX∈S n ∥∇f (X) − λn (∇f (X))I∥,

G

2

F

.

κr∗:= sup A∈Sn, A̸=0 ∥A∥

∥A∥

D:= supX,Y∈S n ∥X − Y∥,

rank(A)≤2r∗

Problem (1) has numerous applications in various fields including statistics, machine learning, discrete optimization, and more. It is in particular interesting in the context of the Frank-Wolfe optimization method [4, 15, 12], since the Frank-Wolfe linear optimization step over S n amounts to computing a unit eigenvector corresponding to the smallest eigenvalue of the current gradient [13, 10]. This can be considerably cheaper than the projection step used by standard projection-based first-order methods as projection onto S n requires, in general, a full eigendecomposition of an n × n symmetric matrix, which in practical implementations takes O(n3) time. Moreover, Frank-Wolfe applies rank-one updates, which often allow efficient low-rank implementations. Its main drawback however, is its worst-case convergence rate. Standard Frank-Wolfe satisfies f (Xt) − f ∗ = O (βD2 /t), where t is the iteration counter, and this dependence on 1/t is worst-case tight even under quadratic growth (see for instance a typical lower bound in [11]). Thus, faster rates require exploiting additional structure, and a dependence on the rank r∗ of optimal solutions is natural in this setting. Indeed Problem (1) has received significant interest in recent years, in particular in the context of Frank-Wolfe-type methods, see for instance [13, 10, 6, 5, 1, 7, 3, 2]. We refer the interested reader to our very recent work [8] for a more in-depth discussion of related works.

Our recent work [8] proposed a Frank-Wolfe-type method for this problem that combines the standard Frank-Wolfe step with an away step specialized to the spectrahedron and also a specialized randomized pairwise step. The method requires only three leading-eigenvector computations per iteration and, under quadratic growth and strict complementarity, converges linearly in expectation after a finite burn-in phase, with both the burn-in and the linear rate independent of the ambient dimension. However, the method is randomized, its linear rate holds only in expectation and only after the burn-in phase, it requires knowledge of the smoothness parameter β, and its analysis relies on strict complementarity, which is a non-trivial assumption.

In this paper we remove all of these limitations. We present a deterministic and parameter-free Frank-Wolfe-type method which requires only three extreme-eigenvector computations per iteration and simple line-searches. Without Assumptions 1 and 2, it retains the standard O(βD2 /t) Frank-Wolfe rate. Under these assumptions it converges globally at a linear rate, without a burn-in phase and without strict complementarity. In particular, for some universal numerical constant c > 0,

f (Xt) − f ∗ ≤ (f (X1) − f ∗) exp (−c(t − 1) min 1, αλ∗r∗ / (r∗ κ2∗ βD2 + G e)).

Thus, up to universal constants, the contraction rate has no explicit dependence on the ambient dimension n. In particular, in case ∥·∥ is either the Frobenius norm or the Nuclear norm (sum of singular values), we simply have κr∗ = 1.

While our method builds on our recent work [8], a key ingredient is a new deterministic pairwise step which rotates a rank-one component supported by the current iterate in a descent direction, which is quite different than the randomized pairwise step introduced in [8]. This yields first-order progress in situations in which both the Frank-Wolfe and away steps may provide only insufficient progress. Together with a new geometric argument based on quadratic growth rather than a gradient eigengap, this is what allows us to obtain the global deterministic linear rate.

The algorithm is given as Algorithm 1. Fix an iteration t and write ∇t:= ∇f (Xt), e t:= ∇t − λn (∇t)I ⪰ 0. ∇ Since all matrices in S n have unit trace, for any X, Y ∈ S n, ⟨∇ e t, Y − X⟩ = ⟨∇t, Y − X⟩. Thus, the shift by λn (∇t)I does not change any directional derivative between feasible points. We let vt,+ be a unit eigenvector corresponding to λn (∇t). Additionally, we compute vt,− ∈ argmax v∈Im(Xt):∥v∥2 =1 v⊤ ∇ e t v, as well as ut ∈ argmax u∈Im(Xt):∥u∥2 =1 u⊤ ∇ e 2t u / (u⊤ X†t u).

We define the following three quantities (certificates) used by the algorithm:

at:= ⟨∇ e t, Xt ⟩2,

bt:= (vt,−⊤ ∇ e t vt,− − ⟨∇ e t, Xt ⟩)2,

ct:= (ut⊤ ∇ e 2t ut − (ut⊤ ∇ e t ut)2) / (ut⊤ X†t ut).

These will correspond to the possible decrement in function value on iteration t.

The algorithm uses the vectors vt,+, vt,−, ut to construct three possible update steps as we now detail.

Frank-Wolfe step: As in our previous work [8], the Frank-Wolfe step moves from Xt towards the extreme point vt,+ vt,+⊤, exactly as in the standard Frank-Wolfe method over the spectrahedron. By definition, the quantity ⟨∇ e t, Xt ⟩ = ⟨∇t, Xt − vt,+ vt,+⊤ ⟩ is precisely the Frank-Wolfe gap at Xt.

Away and Drop steps: We use the same away steps introduced in our previous work [8]. The away step decreases the weight of the rank-one matrix vt,− vt,−⊤, where vt,− is chosen according to (6). For the nondegenerate case rank(Xt) > 1, we set st:= (vt,−⊤ X†t vt,−)−1 − 1. This is the maximal scaling for the parametrization used below. Indeed, for θ ∈ [0, 1], setting η:= θst /(1+θst) gives Xt + θst (Xt − vt,− vt,−⊤) = 1/(1−η) (Xt − ηvt,− vt,−⊤), and the rank is reduced by one when θ = 1. We refer to such a step as a drop step.

Pairwise step: As in our previous work [8] we also consider a specialized pairwise step, however one that is very different from the (randomized) step suggested in [8]. The pairwise step first removes the maximal feasible weight in the direction ut u⊤ t and then places the same weight on a nearby rank-one matrix. In the nondegenerate case (I − ut u⊤ t)∇ e t ut ̸= 0 set γt:= u⊤ t X†t ut, pt:= (I − ut u⊤ t)∇ e t ut / ∥(I − ut u⊤ t)∇ e t ut∥2, vt (θ):= (ut − θpt) / √(1 + θ2). Note that pt ⊥ ut and therefore ∥vt (θ)∥2 = 1, i.e., vt (θ) is a rotation of ut.

Line-search and choice of step: We perform step-size search for each of the three steps. For each step we define a step-size function

ΦFW t (θ):= Xt + θ(vt,+ vt,+⊤ − Xt),

ΦA t (θ):= Xt + θst (Xt − vt,− vt,−⊤),

ΦPt (θ):= Xt + γt (vt (θ)vt (θ)⊤ − ut u⊤ t), θ ∈ [0, 1].

Their corresponding Armijo coefficients are

δtFW:= 1/2 ⟨∇ e t, Xt ⟩,

δtA:= st/2 (vt,−⊤ ∇ e t vt,− − ⟨∇ e t, Xt ⟩),

δtP:= γt ∥(I − ut u⊤ t)∇ e t ut∥2.

Let Θ:= 0 ∪ 2−j: j = 0, 1,.... For each nondegenerate case i ∈ FW, A, P, the Armijo search returns the largest θ ∈ Θ satisfying f (Φit (θ)) ≤ f (Xt) − θδti.

We use the following conventions in the two degenerate cases. If rank(Xt) = 1 an away-step is not possible. Also, if δtA = 0, an away-step is not sensible. In these cases we simply set ΦA t (θ) ≡ Xt, δtA = 0, and the away search returns θtA = 0 and XA t = Xt. If (I − ut u⊤ t)∇ e t ut = 0, then the vector pt in the pairwise step is undefined and we set ΦPt (θ) ≡ Xt and δtP = 0.

If max at, bt, ct = 0, the method terminates. Otherwise, the three Armijo searches are performed. If the away search accepts the full step, the algorithm takes this step and the iteration is called a drop iteration. Otherwise, the algorithm takes the point with the smallest objective value among the three Armijo points. Such an iteration is called a non-drop iteration.

The main convergence result is stated in Theorem 1:

Theorem 1. Let (Xt)t≥1 be the sequence produced by Algorithm 1. Without Assumptions 1 and 2, for every t ≥ 2,

ht ≤ 8βD2 / (t+7).

If, in addition, Assumptions 1 and 2 hold, define

ρ:= min 1/2, (√2 − 1)αλ∗r∗ / (2560r∗ κ2r∗ (βD2 + G e)).

Then, on every iteration t which is not a drop iteration,

ht+1 ≤ (1 − ρ)ht.

Finally, for every t ≥ 1,

ht ≤ h1 (1 − ρ)⌈(t−1)/2⌉.

The sublinear rate (15) is of the same order as the standard Frank-Wolfe, i.e., Θ(βD2 /t). For the Frobenius norm, ∥·∥ = ∥·∥∗ = ∥·∥F, D = 2 and κr∗ = 1, so the denominator in the second term of (16) is simply r∗ (β + G e). If the primal norm is the nuclear norm, so that ∥·∥∗ = ∥·∥2 is the spectral norm, then D = 2 and again κr∗ = 1, yielding again r∗ (2β + G e) in the corresponding denominator.

The proof of Theorem 1 is structured as follows:

• Lemma 4 gives a standard argument that the objective decrease for the FW or away steps is proportional to the quantities at and bt (defined in (8)), respectively.

• Lemma 5 develops the same type of objective decrease argument, with respect to the certificate ct (defined in (8)), for the pairwise step. In particular, the proof guides the reader as to why we define the pairwise step as we do.

• Lemma 7 is the central lemma that establishes that indeed one of the three certificates (in case of a non-drop-step) must result in sufficient objective decrease, i.e., max at, bt, ct = omega(ht).

• Finally, the proof of Theorem 1 combines the above ingredients to yield the linear convergence rate. The sublinear rate follows from standard arguments and mostly mirrors the standard Frank-Wolfe analysis.

The paper also includes a detailed section on implementation details, showing how to maintain a thin factorization Xt = Ut St U⊤ t with Ut ∈ Rn×rt, U⊤ t Ut = I, St ≻ 0, Wt:= S−1 t ≻ 0, requiring O(nrt) memory instead of the worst-case O(n2). It describes how to compute the vectors vt,+, vt,−, ut efficiently, and how to update the maintained representation for each type of step (Frank-Wolfe, away/drop, pairwise) using Sherman–Morrison and block-inverse formulas.

The paper also includes a section demonstrating why the pairwise step is needed, giving a concrete example with n = 3 where neither the Frank-Wolfe step nor the away step can provide a decrease of order ε, while the pairwise step resolves this issue.

Based on the paper, here are the specific improvements you can make to AI systems:

1. Deterministic, parameter-free optimization for low-rank matrix problems

• Improvement: Replace randomized Frank-Wolfe methods (which require strict complementarity, burn-in phases, and knowledge of the smoothness constant β) with the deterministic Algorithm 1 that uses only three extreme-eigenvector computations per iteration and simple line-searches.

• What the improved AI system can do: Solve convex optimization problems over the spectrahedron (e.g., matrix completion, sparse PCA, portfolio optimization) with a guaranteed global linear convergence rate that is independent of ambient dimension, without needing to tune β or rely on probabilistic guarantees.

2. Robust convergence under weaker assumptions

• Improvement: The method works under only quadratic growth (Assumption 1) and common rank of optimal solutions (Assumption 2), removing the strict complementarity requirement.

• What the improved AI system can do: Handle optimization problems where optimal solutions have degenerate gradients or multiple optimal points with the same rank, which previously caused randomized methods to fail or stall. This makes the system applicable to a wider class of real-world problems.

3. Elimination of burn-in phase and expectation-based guarantees

• Improvement: The linear rate holds from the first iteration (no burn-in) and is deterministic (not just in expectation).

• What the improved AI system can do: Provide reliable, worst-case performance guarantees for every run, making it suitable for safety-critical applications (e.g., control, robotics) where probabilistic convergence is unacceptable.

4. Parameter-free operation via Armijo line-search

• Improvement: The method uses adaptive step sizes via Armijo search, eliminating the need to know β.

• What the improved AI system can do: Automatically adapt to unknown problem smoothness, reducing manual hyperparameter tuning and making the system more plug-and-play for new tasks.

5. Memory-efficient implementation for large-scale problems

• Improvement: The paper provides a thin factorization (X t = U t S t U t T) requiring O(n·r t) memory instead of O(n2), with efficient updates via Sherman-Morrison formulas.

• What the improved AI system can do: Scale to very high-dimensional problems (e.g., n = 106) where storing full matrices is infeasible, enabling applications in large-scale machine learning and signal processing.

6. New deterministic pairwise step for escaping poor local progress

• Improvement: The pairwise step rotates a rank-one component in a descent direction, providing first-order progress when both Frank-Wolfe and away steps fail (demonstrated with a concrete n=3 example).

• What the improved AI system can do: Avoid stagnation in optimization landscapes where standard Frank-Wolfe variants get stuck, leading to faster convergence on ill-conditioned or degenerate problems.

7. Sublinear rate guarantee without assumptions

• Improvement: Even without Assumptions 1 and 2, the method retains the standard O(βD2/t) Frank-Wolfe rate.

• What the improved AI system can do: Gracefully degrade to classical performance when problem structure is unknown, ensuring no worse performance than standard methods in the worst case.

8. Unified convergence analysis framework

• Improvement: The proof structure (Lemmas 4, 5, 7) provides a template for analyzing similar Frank-Wolfe variants with multiple step types.

• What the improved AI system can do: Enable researchers to more easily design and verify new optimization algorithms with provable guarantees, accelerating AI research.

9. Practical implementation guidance

• Improvement: The paper details how to compute vt,+, vt,−, ut efficiently and update the factorization for each step type.

• What the improved AI system can do: Directly implement the algorithm in production systems (e.g., recommender systems, sensor networks) with clear computational recipes, reducing engineering overhead.

10. Improved worst-case performance for rank-constrained problems

• Improvement: The linear rate depends on r* (rank of optimal solutions) rather than n (ambient dimension), and κ r* = 1 for Frobenius and nuclear norms.

• What the improved AI system can do: Achieve dimension-independent convergence for problems with low-rank solutions (common in collaborative filtering, phase retrieval), making it exponentially faster than standard methods in high dimensions.