Time-varying graphical LASSO (TVGL) aims to infer a sequence of graphs from time series data and has been widely used in many statistical inference problems. The existing algorithms usually suffer from high computational cost when solving large-scale TVGL problems. In this paper, we develop an efficient and scalable hierarchical block coordinate descent (HBCD) method for solving TVGL with smooth temporal difference prior. The proposed HBCD method contains both outer-loop and inner-loop BCD iterations. The outer loops seperate the original TVGL problem into a sequence of subproblems, which are variants of the static graphical LASSO problems. Then, we propose an efficient BCD method to solve the inner-loop subproblems. We provide theoretical analysis that indicates the linear convergence of our proposed method. Furthermore, numerical experiments on both synthetic and real datasets show that our method significantly outperforms the state-of-the-art algorithm in terms of both the required iterations and CPU time to reach the target precision.

Decentralized optimization aims to cooperatively solve a global finite-sum loss function, where each agent only possesses knowledge of its own local function. Real-world applications introduce challenges such as unstable channels and differential privacy concerns, necessitating the development of more robust algorithms. This paper proposes a framework that explores second-order information using two approaches: global Newton tracking and local Newton preconditioning. Furthermore, we adapt a generic convergence result for gradient tracking methods to demonstrate the almost sure convergence property of both schemes under specific conditions. To validate the effectiveness of the proposed algorithm, numerical experiments are conducted on synthetic and real datasets, showcasing its robustness and superior accuracy compared to existing first-order methods.

The maximal coding rate reduction (MCR$^2$) objective for learning structured and compact deep representations is drawing increasing attention, especially after its recent usage in the derivation of fully explainable and highly effective deep network architectures. However, it lacks a complete theoretical justification: only the properties of its global optima are known, and its global landscape has not been studied. In this work, we give a complete characterization of the properties of all its local and global optima as well as other types of critical points. Specifically, we show that each (local or global) maximizer of the MCR$^2$ problem corresponds to a low-dimensional, discriminative, and diverse representation, and furthermore, each critical point of the objective is either a local maximizer or a strict saddle point. Such a favorable landscape makes MCR$^2$ a natural choice of objective for learning diverse and discriminative representations via first-order optimization. To further verify our theoretical findings, we illustrate these properties with extensive experiments on both synthetic and real data sets.

We study the problem of symmetric positive semi-definite low-rank matrix completion (MC) with deterministic entry-dependent sampling. In particular, we consider rectified linear unit (ReLU) sampling, where only positive entries are observed, as well as a generalization to threshold-based sampling. We first empirically demonstrate that the landscape of this MC problem is not globally benign: Gradient descent (GD) with random initialization will generally converge to stationary points that are not globally optimal. Nevertheless, we prove that when the matrix factor with a small rank satisfies mild assumptions, the nonconvex objective function is geodesically strongly convex on the quotient manifold in a neighborhood of a planted low-rank matrix. Moreover, we show that our assumptions are satisfied by a matrix factor with i.i.d. Gaussian entries. Finally, we develop a tailor-designed initialization for GD to solve our studied formulation, which empirically always achieves convergence to the global minima. We also conduct extensive experiments and compare MC methods, investigating convergence and completion performance with respect to initialization, noise level, dimension, and rank.

In this paper we develop a simple scheme for a coupled matrix factorization problem arising in the topic of hyperspectral super-resolution (HSR). HSR considers the problem of recovering a super-resolution image from a multispectral image and a hyperspectral image, which have lower spectral and spatial resolutions, respectively, and it is a motivated topic in the domain of remote sensing. The challenge with coupled factorization (COFAC) is that we are required to simultaneously factorize two data matrices, with their factors being interrelated. We adopt a separable COFAC strategy, in which we first factorize one data matrix, and then use the retrieved factors and the coupled factor relationship to help us factorize another matrix; the merit is that it may lead to simple COFAC schemes. Our scheme is based on the simplex-structured factorization model, which is commonly used in HSR, and a sparse factor assumption. In particular, we leverage the coupled factor structure to exploit sparsity in an easy way; we solve simple constrained least squares problems, and we sidestep the need to do sparse optimization. Numerical results show that our proposed scheme works reasonably on both semi-real data and synthetic data, and it runs much faster than some state-of-the-art COFAC schemes.

This work presents ReSync, a Riemannian subgradient-based algorithm for solving the robust rotation synchronization problem, which arises in various engineering applications. ReSync solves a least-unsquared minimization formulation over the rotation group, which is nonsmooth and nonconvex, and aims at recovering the underlying rotations directly. We provide strong theoretical guarantees for ReSync under the random corruption setting. Specifically, we first show that the initialization procedure of ReSync yields a proper initial point that lies in a local region around the ground-truth rotations. We next establish the weak sharpness property of the aforementioned formulation and then utilize this property to derive the local linear convergence of ReSync to the ground-truth rotations. By combining these guarantees, we conclude that ReSync converges linearly to the ground-truth rotations under appropriate conditions. Experiment results demonstrate the effectiveness of ReSync.

The K-subspaces (KSS) method is a generalization of the K-means method for subspace clustering. In this work, we present local convergence analysis and a recovery guarantee for KSS, assuming data are generated by the semi-random union of subspaces model, where $N$ points are randomly sampled from $K \ge 2$ overlapping subspaces. We show that if the initial assignment of the KSS method lies within a neighborhood of a true clustering, it converges at a superlinear rate and finds the correct clustering within $\Theta(\log\log N)$ iterations with high probability. Moreover, we propose a thresholding inner-product based spectral method for initialization and prove that it produces a point in this neighborhood. We also present numerical results of the studied method to support our theoretical developments.

In this paper, we study the problem of exact community recovery in the symmetric stochastic block model, where a graph of $n$ vertices is randomly generated by partitioning the vertices into $K \ge 2$ equal-sized communities and then connecting each pair of vertices with probability that depends on their community memberships. Although the maximum-likelihood formulation of this problem is discrete and non-convex, we propose to tackle it directly using projected power iterations with an initialization that satisfies a partial recovery condition. Such an initialization can be obtained by a host of existing methods. We show that in the logarithmic degree regime of the considered problem, the proposed method can exactly recover the underlying communities at the information-theoretic limit. Moreover, with a qualified initialization, it runs in $\mO(n\log^2n/\log\log n)$ time, which is competitive with existing state-of-the-art methods. We also present numerical results of the proposed method to support and complement our theoretical development.

Stochastic gradient descent (SGD) usually samples training data based on the uniform distribution, which may not be a good choice because of the high variance of its stochastic gradient. Thus, importance sampling methods are considered in the literature to improve the performance. Most previous work on SGD-based methods with importance sampling requires the knowledge of Lipschitz constants of all component gradients, which are in general difficult to estimate. In this paper, we study an adaptive importance sampling method for common SGD-based methods by exploiting the local first-order information without knowing any Lipschitz constants. In particular, we periodically changes the sampling distribution by only utilizing the gradient norms in the past few iterations. We prove that our adaptive importance sampling non-asymptotically reduces the variance of the stochastic gradients in SGD, and thus better convergence bounds than that for vanilla SGD can be obtained. We extend this sampling method to several other widely used stochastic gradient algorithms including SGD with momentum and ADAM. Experiments on common convex learning problems and deep neural networks illustrate notably enhanced performance using the adaptive sampling strategy.

In this paper, we consider the large-scale case of the robust beamforming problem with interference temperature constraints. Previous semidefinite relaxation (SDR) method becomes impracticable because of its expensive computational cost. Even successive convex approximation (SCA) method, the state-of-the-art method, cannot tackle this problem efficiently. Thus, we are motivated to design two efficient first-order methods, multi-block alternating direction method of multipliers (ADMM) and linear programming-assisted subgradient descent (LPA-SD), to solve it. Numerical results demonstrate the potential of our proposed methods in terms of both computational efficiency and solution quality.

In this paper, we consider a ℓ1-PCA problem under the large-scale data sample scenario, which has extensive applications in science and engineering. Previous algorithms for the problem either are not scalable or do not have good convergence guarantees. Our contribution is threefold. First, we develop a novel accelerated version of the proximal alternating maximization method to solve the ℓ1-PCA problem. Second, by exploiting the Kurdyka-Łojasiewicz property of the problem, we show that our proposed method enjoys global convergence to a critical point, which improves upon existing convergence guarantees of other first-order methods for the ℓ1-PCA problem. Third, we demonstrate via numerical experiments on both real-world and synthetic datasets that our proposed method is scalable and more efficient and accurate than other methods in the literature.

This paper describes a novel small-scale turtle-inspired Amphibious Spherical Robot (ASRobot) to accomplish exploration tasks in the restricted environment, such as amphibious areas and narrow underwater cave. A Legged, Multi-Vectored Water-Jet Composite Propulsion Mechanism (LMVWCPM) is designed with four legs, one of which contains three connecting rod parts, one water-jet thruster and three joints driven by digital servos. Using this mechanism, the robot is able to walk like amphibious turtles on various terrains and swim flexibly in submarine environment. A simplified kinematic model is established to analyze crawling gaits. With simulation of the crawling gait, the driving torques of different joints contributed to the choice of servos and the size of links of legs. Then we also modeled the robot in water and proposed several underwater locomotion. In order to assess the performance of the proposed robot, a series of experiments were carried out in the lab pool and on flat ground using the prototype robot. Experiments results verified the effectiveness of LMVWCPM and the amphibious control approaches.

A fundamental class of matrix optimization problems that arise in many areas of science and engineering is that of quadratic optimization with orthogonality constraints. Such problems can be solved using line-search methods on the Stiefel manifold, which are known to converge globally under mild conditions. To determine the convergence rates of these methods, we give an explicit estimate of the exponent in a Lojasiewicz inequality for the (non-convex) set of critical points of the aforementioned class of problems. This not only allows us to establish the linear convergence of a large class of line-search methods but also answers an important and intriguing problem in mathematical analysis and numerical optimization. A key step in our proof is to establish a local error bound for the set of critical points, which may be of independent interest.