6 citations · 18 across the 13 of their papers we have counts for
7 papers · 1 filter
Stiefel optimization is NP-hard
Zehua Lai, Lek-Heng Lim, Tianyun Tang
We show that linearly constrained linear optimization over a Stiefel or Grassmann manifold is NP-hard in general. We show that the same is true for unconstrained quadratic optimiza…
Euclidean distance degree in manifold optimization
Zehua Lai, Lek-Heng Lim, Ke Ye
We determine the Euclidean distance degrees of the three most common manifolds arising in manifold optimization: flag, Grassmann, and Stiefel manifolds. For the Grassmannian, we wi…
Grassmannian optimization is NP-hard
Zehua Lai, Lek-Heng Lim, Ke Ye
We show that unconstrained quadratic optimization over a Grassmannian is NP-hard. Our results cover all scenarios: (i) when and are both allowed to…
Simpler flag optimization
Zehua Lai, Lek-Heng Lim, Ke Ye
We study the geometry of flag manifolds under different embeddings into a product of Grassmannians. We show that differential geometric objects and operations -- tangent vector, me…
Stochastic Steffensen method
Minda Zhao, Zehua Lai, Lek-Heng Lim
Is it possible for a first-order method, i.e., only first derivatives allowed, to be quadratically convergent? For univariate loss functions, the answer is yes -- the Steffensen me…
Simpler Grassmannian optimization
Zehua Lai, Lek-Heng Lim, Ke Ye
There are two widely used models for the Grassmannian , as the set of equivalence classes of orthogonal matrices $\operatorname{O}(n)/(\operatorname{O}(k) \…
Recht-Ré Noncommutative Arithmetic-Geometric Mean Conjecture is False
Zehua Lai, Lek-Heng Lim
Stochastic optimization algorithms have become indispensable in modern machine learning. An unresolved foundational question in this area is the difference between with-replacement…