More Like this

1. Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold

   Wang, B. ; Ma, S. ; Xue, L. ( January 2022 , Journal of machine learning research)

   Riemannian optimization has drawn a lot of attention due to its wide applications in practice. Riemannian stochastic first-order algorithms have been studied in the literature to solve large-scale machine learning problems over Riemannian manifolds. However, most of the existing Riemannian stochastic algorithms require the objective function to be differentiable, and they do not apply to the case where the objective function is nonsmooth. In this paper, we present two Riemannian stochastic proximal gradient methods for minimizing nonsmooth function over the Stiefel manifold. The two methods, named R-ProxSGD and R-ProxSPB, are generalizations of proximal SGD and proximal SpiderBoost in Euclidean setting to the Riemannian setting. Analysis on the incremental first-order oracle (IFO) complexity of the proposed algorithms is provided. Specifically, the R-ProxSPB algorithm finds an ϵ -stationary point with O(ϵ−3) IFOs in the online case, and O(n+n‾√ϵ−2) IFOs in the finite-sum case with n being the number of summands in the objective. Experimental results on online sparse PCA and robust low-rank matrix completion show that our proposed methods significantly outperform the existing methods that use Riemannian subgradient information. 

   more » « less
2. A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis

   Jiang, Hao ; Robinson, Daniel P. ; Vidal, Rene ; You, Chong ( April 2018 , Computational optimization and applications)

   We consider the problem of subspace clustering with data that is potentially corrupted by both dense noise and sparse gross errors. In particular, we study a recently proposed low rank subspace clustering approach based on a nonconvex modeling formulation. This formulation includes a nonconvex spectral function in the objective function that makes the optimization task challenging, e.g., it is unknown whether the alternating direction method of multipliers (ADMM) framework proposed to solve the nonconvex model formulation is provably convergent. In this paper, we establish that the spectral function is differentiable and give a formula for computing the derivative. Moreover, we show that the derivative of the spectral function is Lipschitz continuous and provide an explicit value for the Lipschitz constant. These facts are then used to provide a lower bound for how the penalty parameter in the ADMM method should be chosen. As long as the penalty parameter is chosen according to this bound, we show that the ADMM algorithm computes iterates that have a limit point satisfying first-order optimality conditions. We also present a second strategy for solving the nonconvex problem that is based on proximal gradient calculations. The convergence and performance of the algorithms is verified through experiments on real data from face and digit clustering and motion segmentation. 

   more » « less
3. Benchmarking the User-Centric Clustering and Pilot Assignment Problems in Cell-Free Networks

   https://doi.org/10.1109/GLOBECOM54140.2023.10437645  

   Aboulfotouh, Ahmed ; Fadlullah, Zubair Md ; Fouda, Mostafa M ; Ismail, Muhammad ; Niyato, Dusit ( December 2023 , IEEE)

   This paper addresses the user-centric clustering and pilot assignment problems in cell-free networks, recognizing the need to solve both problems simultaneously. The motivation of this research stems from the absence of benchmarks, general formulations, and the reliance on subjectively designed objective functions and heuristic algorithms prevalent in existing literature. To tackle these challenges, we formulate stochastic non-linear binary integer programs for both the user-centric clustering and pilot assignment problems. We specifically design the pilot assignment formulation to incorporate user-centric clusters when evaluating the desirability of pilot assignments, resulting in improved efficiency. To solve the problems, the proposed methodology employs sample average approximation coupled with surrogate optimization for the user-centric clustering problem and the genetic algorithm for the pilot assignment problem. Numerical experiments demonstrate that the optimized solutions outperform baseline solutions, leading to significant gains in spectral efficiency. 

   more » « less
4. High-Order Co-Clustering via Strictly Orthogonal and Symmetric L1-Norm Nonnegative Matrix Tri-Factorization

   https://doi.org/10.24963/ijcai.2018/340  

   Liu, Kai ; Wang, Hua ( July 2018 , Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence)

   Different to traditional clustering methods that deal with one single type of data, High-Order Co- Clustering (HOCC) aims to cluster multiple types of data simultaneously by utilizing the inter- or/and intra-type relationships across different data types. In existing HOCC methods, data points routinely enter the objective functions with squared residual errors. As a result, outlying data samples can dominate the objective functions, which may lead to incorrect clustering results. Moreover, existing methods usually suffer from soft clustering, where the probabilities to different groups can be very close. In this paper, we propose an L1 -norm symmetric nonnegative matrix tri-factorization method to solve the HOCC problem. Due to the orthogonal constraints and the symmetric L1 -norm formulation in our new objective, conventional auxiliary function approach no longer works. Thus we derive the solution algorithm using the alternating direction method of multipliers. Extensive experiments have been conducted on a real world data set, in which promising empirical results, including less time consumption, strictly orthogonal membership matrix, lower local minima etc., have demonstrated the effectiveness of our proposed method.

    

   more » « less
5. Learning Strictly Orthogonal p-Order Nonnegative Laplacian Embedding via Smoothed Iterative Reweighted Method

   https://doi.org/10.24963/ijcai.2019/561  

   Yang, Haoxuan ; Liu, Kai ; Wang, Hua ; Nie, Feiping ( August 2019 , Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence)

   Laplacian Embedding (LE) is a powerful method to reveal the intrinsic geometry of high-dimensional data by using graphs. Imposing the orthogonal and nonnegative constraints onto the LE objective has proved to be effective to avoid degenerate and negative solutions, which, though, are challenging to achieve simultaneously because they are nonlinear and nonconvex. In addition, recent studies have shown that using the p-th order of the L2-norm distances in LE can find the best solution for clustering and promote the robustness of the embedding model against outliers, although this makes the optimization objective nonsmooth and difficult to efficiently solve in general. In this work, we study LE that uses the p-th order of the L2-norm distances and satisfies both orthogonal and nonnegative constraints. We introduce a novel smoothed iterative reweighted method to tackle this challenging optimization problem and rigorously analyze its convergence. We demonstrate the effectiveness and potential of our proposed method by extensive empirical studies on both synthetic and real data sets.

    

   more » « less