Bin Gao

Bin Gao, Renfeng Peng, Ya-xiang Yuan

Provably finding stationary points on bounded-rank tensors turns out to be an open problem [E. Levin, J. Kileel, and N. Boumal, Math. Program., 199 (2023), pp. 831--864] due to the inherent non-smoothness of the set of bounded-rank tensors. In contrast with bounded-rank matrices, tensors where some but not all modes are of full rank render essential difficulties in developing provable first-order methods. We resolve this problem by proposing two first-order methods with guaranteed convergence to stationary points. Specifically, we revisit the variational geometry of bounded-rank tensors and explicitly characterize its normal cones. Moreover, we propose gradient-related approximate projection methods that are provable to find stationary points, where the decisive ingredients are gradient-related vectors from tangent cones, line search along approximate projections, and rank-decreasing mechanisms near rank-deficient points. Numerical experiments on tensor completion validate that the proposed methods converge to stationary points across various rank parameters.

Simon Vary, Pierre Ablin, Bin Gao et al.

Optimization over the set of matrices $X$ that satisfy $X^\top B X = I_p$, referred to as the generalized Stiefel manifold, appears in many applications involving sampled covariance matrices such as the canonical correlation analysis (CCA), independent component analysis (ICA), and the generalized eigenvalue problem (GEVP). Solving these problems is typically done by iterative methods that require a fully formed $B$. We propose a cheap stochastic iterative method that solves the optimization problem while having access only to random estimates of $B$. Our method does not enforce the constraint in every iteration; instead, it produces iterations that converge to critical points on the generalized Stiefel manifold defined in expectation. The method has lower per-iteration cost, requires only matrix multiplications, and has the same convergence rates as its Riemannian optimization counterparts that require the full matrix $B$. Experiments demonstrate its effectiveness in various machine learning applications involving generalized orthogonality constraints, including CCA, ICA, and the GEVP.

Yan Yang, Bin Gao, Ya-xiang Yuan

Bilevel optimization, with broad applications in machine learning, has an intricate hierarchical structure. Gradient-based methods have emerged as a common approach to large-scale bilevel problems. However, the computation of the hyper-gradient, which involves a Hessian inverse vector product, confines the efficiency and is regarded as a bottleneck. To circumvent the inverse, we construct a sequence of low-dimensional approximate Krylov subspaces with the aid of the Lanczos process. As a result, the constructed subspace is able to dynamically and incrementally approximate the Hessian inverse vector product with less effort and thus leads to a favorable estimate of the hyper-gradient. Moreover, we propose a provable subspace-based framework for bilevel problems where one central step is to solve a small-size tridiagonal linear system. To the best of our knowledge, this is the first time that subspace techniques are incorporated into bilevel optimization. This successful trial not only enjoys $\mathcal{O}(ε^{-1})$ convergence rate but also demonstrates efficiency in a synthetic problem and two deep learning tasks.

Shuyu Dong, Bin Gao, Yu Guan et al.

We propose new Riemannian preconditioned algorithms for low-rank tensor completion via the polyadic decomposition of a tensor. These algorithms exploit a non-Euclidean metric on the product space of the factor matrices of the low-rank tensor in the polyadic decomposition form. This new metric is designed using an approximation of the diagonal blocks of the Hessian of the tensor completion cost function, thus has a preconditioning effect on these algorithms. We prove that the proposed Riemannian gradient descent algorithm globally converges to a stationary point of the tensor completion problem, with convergence rate estimates using the $Ł$ojasiewicz property. Numerical results on synthetic and real-world data suggest that the proposed algorithms are more efficient in memory and time compared to state-of-the-art algorithms. Moreover, the proposed algorithms display a greater tolerance for overestimated rank parameters in terms of the tensor recovery performance, thus enable a flexible choice of the rank parameter.