Ying Cui

Yangchen Li, Ying Cui, Vincent Lau

The optimal implementation of federated learning (FL) in practical edge computing systems has been an outstanding problem. In this paper, we propose an optimization-based quantized FL algorithm, which can appropriately fit a general edge computing system with uniform or nonuniform computing and communication resources at the workers. Specifically, we first present a new random quantization scheme and analyze its properties. Then, we propose a general quantized FL algorithm, namely GQFedWAvg. Specifically, GQFedWAvg applies the proposed quantization scheme to quantize wisely chosen model update-related vectors and adopts a generalized mini-batch stochastic gradient descent (SGD) method with the weighted average local model updates in global model aggregation. Besides, GQFedWAvg has several adjustable algorithm parameters to flexibly adapt to the computing and communication resources at the server and workers. We also analyze the convergence of GQFedWAvg. Next, we optimize the algorithm parameters of GQFedWAvg to minimize the convergence error under the time and energy constraints. We successfully tackle the challenging non-convex problem using general inner approximation (GIA) and multiple delicate tricks. Finally, we interpret GQFedWAvg's function principle and show its considerable gains over existing FL algorithms using numerical results.

Jake Roth, Ying Cui

The \emph{top-$k$-sum} operator computes the sum of the largest $k$ components of a given vector. The Euclidean projection onto the top-$k$-sum sublevel set serves as a crucial subroutine in iterative methods to solve composite superquantile optimization problems. In this paper, we introduce a solver that implements two finite-termination algorithms to compute this projection. Both algorithms have $O(n)$ complexity of floating point operations when applied to a sorted $n$-dimensional input vector, where the absorbed constant is \emph{independent of $k$}. This stands in contrast to an existing grid-search-inspired method that has $O(k(n-k))$ complexity, a partition-based method with $O(n+D\log D)$ complexity, where $D\leq n$ is the number of distinct elements in the input vector, and a semismooth Newon method with a finite termination property but unspecified floating point complexity. The improvement of our methods over the first method is significant when $k$ is linearly dependent on $n$, which is frequently encountered in practical superquantile optimization applications. In instances where the input vector is unsorted, an additional cost is incurred to (partially) sort the vector, whereas a full sort of the input vector seems unavoidable for the other two methods. To reduce this cost, we further derive a rigorous procedure that leverages approximate sorting to compute the projection, which is particularly useful when solving a sequence of similar projection problems. Numerical results show that our methods solve problems of scale $n=10^7$ and $k=10^4$ within $0.05$ seconds, whereas the most competitive alternative, the semismooth Newton-based method, takes about $1$ second. The existing grid-search method and Gurobi's QP solver can take from minutes to hours.

Bowen Tan, Ying Cui

Fast and accurate device activity detection is the critical challenge in grant-free access for supporting massive machine-type communications (mMTC) and ultra-reliable low-latency communications (URLLC) in 5G and beyond. The state-of-the-art methods have unsatisfactory error rates or computation times. To address these outstanding issues, we propose new maximum likelihood estimation (MLE) and maximum a posterior estimation (MAPE) based device activity detection methods for known and unknown pathloss that achieve superior error rate and computation time tradeoffs using optimization and deep learning techniques. Specifically, we investigate four non-convex optimization problems for MLE and MAPE in the two pathloss cases, with one MAPE problem being formulated for the first time. For each non-convex problem, we develop an innovative parallel iterative algorithm using the parallel successive convex approximation (PSCA) method. Each PSCA-based algorithm allows parallel computations, uses up to the objective function's second-order information, converges to the problem's stationary points, and has a low per-iteration computational complexity compared to the state-of-the-art algorithms. Then, for each PSCA-based iterative algorithm, we present a deep unrolling neural network implementation, called PSCA-Net, to further reduce the computation time. Each PSCA-Net elegantly marries the underlying PSCA-based algorithm's parallel computation mechanism with the parallelizable neural network architecture and effectively optimizes its step sizes based on vast data samples to speed up the convergence. Numerical results demonstrate that the proposed methods can significantly reduce the error rate and computation time compared to the state-of-the-art methods, revealing their significant values for grant-free access.

Yangchen Li, Ying Cui, Vincent Lau

Optimal algorithm design for federated learning (FL) remains an open problem. This paper explores the full potential of FL in practical edge computing systems where workers may have different computation and communication capabilities, and quantized intermediate model updates are sent between the server and workers. First, we present a general quantized parallel mini-batch stochastic gradient descent (SGD) algorithm for FL, namely GenQSGD, which is parameterized by the number of global iterations, the numbers of local iterations at all workers, and the mini-batch size. We also analyze its convergence error for any choice of the algorithm parameters. Then, we optimize the algorithm parameters to minimize the energy cost under the time constraint and convergence error constraint. The optimization problem is a challenging non-convex problem with non-differentiable constraint functions. We propose an iterative algorithm to obtain a KKT point using advanced optimization techniques. Numerical results demonstrate the significant gains of GenQSGD over existing FL algorithms and reveal the importance of optimally designing FL algorithms.

Chengjun Guo, Ying Cui, Zhi Liu et al.

In this paper, we study the optimal transmission of a multi-quality tiled 360 virtual reality (VR) video from a multi-antenna server (e.g., access point or base station) to multiple single-antenna users in a multiple-input multiple-output (MIMO)-orthogonal frequency division multiple access (OFDMA) system. We minimize the total transmission power with respect to the subcarrier allocation constraints, rate allocation constraints, and successful transmission constraints, by optimizing the beamforming vector and subcarrier, transmission power and rate allocation. The formulated resource allocation problem is a challenging mixed discrete-continuous optimization problem. We obtain an asymptotically optimal solution in the case of a large antenna array, and a suboptimal solution in the general case. As far as we know, this is the first work providing optimization-based design for 360 VR video transmission in MIMO-OFDMA systems. Finally, by numerical results, we show that the proposed solutions achieve significant improvement in performance compared to the existing solutions.

Ying Cui, Yangchen Li, Chencheng Ye

Federated learning (FL) has become a hot research area in enabling the collaborative training of machine learning models among multiple clients that hold sensitive local data. Nevertheless, unconstrained federated optimization has been studied mainly using stochastic gradient descent (SGD), which may converge slowly, and constrained federated optimization, which is more challenging, has not been investigated so far. This paper investigates sample-based and feature-based federated optimization, respectively, and considers both unconstrained and constrained nonconvex problems for each of them. First, we propose FL algorithms using stochastic successive convex approximation (SSCA) and mini-batch techniques. These algorithms can adequately exploit the structures of the objective and constraint functions and incrementally utilize samples. We show that the proposed FL algorithms converge to stationary points and Karush-Kuhn-Tucker (KKT) points of the respective unconstrained and constrained nonconvex problems, respectively. Next, we provide algorithm examples with appealing computational complexity and communication load per communication round. We show that the proposed algorithm examples for unconstrained federated optimization are identical to FL algorithms via momentum SGD and provide an analytical connection between SSCA and momentum SGD. Finally, numerical experiments demonstrate the inherent advantages of the proposed algorithms in convergence speeds, communication and computation costs, and model specifications.

Chencheng Ye, Ying Cui

In this paper, we investigate unconstrained and constrained sample-based federated optimization, respectively. For each problem, we propose a privacy preserving algorithm using stochastic successive convex approximation (SSCA) techniques, and show that it can converge to a Karush-Kuhn-Tucker (KKT) point. To the best of our knowledge, SSCA has not been used for solving federated optimization, and federated optimization with nonconvex constraints has not been investigated. Next, we customize the two proposed SSCA-based algorithms to two application examples, and provide closed-form solutions for the respective approximate convex problems at each iteration of SSCA. Finally, numerical experiments demonstrate inherent advantages of the proposed algorithms in terms of convergence speed, communication cost and model specification.

Ying Cui, Shuaichao Li, Wanqing Zhang

In this paper, we investigate jointly sparse signal recovery and jointly sparse support recovery in Multiple Measurement Vector (MMV) models for complex signals, which arise in many applications in communications and signal processing. Recent key applications include channel estimation and device activity detection in MIMO-based grant-free random access which is proposed to support massive machine-type communications (mMTC) for Internet of Things (IoT). Utilizing techniques in compressive sensing, optimization and deep learning, we propose two model-driven approaches, based on the standard auto-encoder structure for real numbers. One is to jointly design the common measurement matrix and jointly sparse signal recovery method, and the other aims to jointly design the common measurement matrix and jointly sparse support recovery method. The proposed model-driven approaches can effectively utilize features of sparsity patterns in designing common measurement matrices and adjusting model-driven decoders, and can greatly benefit from the underlying state-of-the-art recovery methods with theoretical guarantee. Hence, the obtained common measurement matrices and recovery methods can significantly outperform the underlying advanced recovery methods. We conduct extensive numerical results on channel estimation and device activity detection in MIMO-based grant-free random access. The numerical results show that the proposed approaches provide pilot sequences and channel estimation or device activity detection methods which can achieve higher estimation or detection accuracy with shorter computation time than existing ones. Furthermore, the numerical results explain how such gains are achieved via the proposed approaches.