This paper is concerned with the computation of the capacity region of a continuous, Gaussian vector broadcast channel (BC) with covariance matrix constraints. Since the decision variables of the corresponding optimization problem are Gaussian distributed, they can be characterized by a finite number of parameters. Consequently, we develop new Blahut-Arimoto (BA)-type algorithms that can compute the capacity without discretizing the channel. First, by exploiting projection and an approximation of the Lagrange multiplier, which are introduced to handle certain positive semidefinite constraints in the optimization formulation, we develop the Gaussian BA algorithm with projection (GBA-P). Then, we demonstrate that one of the subproblems arising from the alternating updates admits a closed-form solution. Based on this result, we propose the Gaussian BA algorithm with alternating updates (GBA-A) and establish its convergence guarantee. Furthermore, we extend the GBA-P algorithm to compute the capacity region of the Gaussian vector BC with both private and common messages. All the proposed algorithms are parameter-free. Lastly, we present numerical results to demonstrate the effectiveness of the proposed algorithms.

Nonconvex-concave (NC-C) finite-sum minimax problems have broad applications in decentralized optimization and various machine learning tasks. However, the nonsmooth nature of NC-C problems makes it challenging to design effective variance reduction techniques. Existing vanilla stochastic algorithms using uniform samples for gradient estimation often exhibit slow convergence rates and require bounded variance assumptions. In this paper, we develop a novel probabilistic variance reduction updating scheme and propose a single-loop algorithm called the probabilistic variance-reduced smoothed gradient descent-ascent (PVR-SGDA) algorithm. The proposed algorithm achieves an iteration complexity of ${\mathcal{O}}\left({{\varepsilon ^{ - 4}}}\right)$, surpassing the best-known rates of stochastic algorithms for NC-C minimax problems and matching the performance of the best deterministic algorithms in this context. Finally, we demonstrate the effectiveness of the proposed algorithm through numerical simulations.

Learning the graph topology of a complex network is challenging due to limited data availability and imprecise data models. A common remedy in existing works is to incorporate priors such as sparsity or modularity which highlight on the structural property of graph topology. We depart from these approaches to develop priors that are directly inspired by complex network dynamics. Focusing on social networks with actions modeled by equilibriums of linear quadratic games, we postulate that the social network topologies are optimized with respect to a social welfare function. Utilizing this prior knowledge, we propose a network games induced regularizer to assist graph learning. We then formulate the graph topology learning problem as a bilevel program. We develop a two-timescale gradient algorithm to tackle the latter. We draw theoretical insights on the optimal graph structure of the bilevel program and show that they agree with the topology in several manmade networks. Empirically, we demonstrate the proposed formulation gives rise to reliable estimate of graph topology.

Chonghe Jiang, Bao Nguyen, Anthony Man-Cho So, Viet Anh Nguyen. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

Solving bilevel optimization (BLO) problems to global optimality is generally intractable. A common surrogate is to compute a hyper-stationary point—a stationary point of the hyper-objective function obtained by minimizing or maximizing the upper-level objective over the lower-level solution set. Existing methods, however, either provide weak notions of stationarity or require restrictive assumptions to guarantee the smoothness of hyper-objective functions. In this paper, we eliminate these impractical assumptions and show that strong (Clarke) hyper-stationarity remains computable even when the hyper-objective is nonsmooth. Our key ingredient is a new structural property, called set smoothness, which captures the variational dependence of the lower-level solution set on the upper-level variable. We prove that this property holds for a broad class of BLO problems and ensures weak convexity (resp. concavity) of pessimistic (resp. optimistic) hyper-objective functions. Building on this foundation, we show that a zeroth-order algorithm that computes approximate Clarke hyper-stationary points with non-asymptotic convergence guarantees. To the best of our knowledge, this is the first computational guarantee for Clarke-type stationarity in nonsmooth BLO. Beyond this specific application, the set smoothness property emerges as a structural concept of independent interest, with potential to inform the analysis of broader classes of optimization and variational problems.

We study the basic computational problem of detecting approximate stationary points for continuous piecewise affine (PA) functions. Our contributions span multiple aspects, including complexity, regularity, and algorithms. Specifically, we show that testing first-order approximate stationarity concepts, as defined by commonly used generalized subdifferentials, is computationally intractable unless P = NP. To facilitate computability, we consider a polynomial-time solvable relaxation by abusing the convex subdifferential sum rule and establish a tight characterization of its exactness. Furthermore, addressing an open issue motivated by the need to terminate the subgradient method in finite time, we introduce the first oracle-polynomial-time algorithm to detect so-called near-approximate stationary points for PA functions.

This paper proposes a Generalized Power Method (GPM) to simultaneously solve the joint problem of community detection and group synchronization in a direct non-convex manner, in contrast to the existing method of semidefinite programming (SDP). Under a natural extension of stochastic block model (SBM), our theoretical analysis proves that the proposed algorithm is able to exactly recover the ground truth in $O(n\log^2 n)$ time for problems of size $n$, sharply outperforming the $O(n^{3.5})$ runtime of SDP. Moreover, we give a lower bound of model parameters as a sufficient condition for the exact recovery of GPM. The new bound breaches the information-theoretic limit for pure community detection under SBM, thus demonstrating the superiority of our simultaneous optimization algorithm over any two-stage method that performs the two tasks in succession. We also conduct numerical experiments on GPM and SDP to corroborate our theoretical analysis.

Hyperparameter tuning is an important task of machine learning, which can be formulated as a bilevel program (BLP). However, most existing algorithms are not applicable for BLP with non-smooth lower-level problems. To address this, we propose a single-level reformulation of the BLP based on lower-level duality without involving any implicit value function. To solve the reformulation, we propose a majorization minimization algorithm that marjorizes the constraint in each iteration. Furthermore, we show that the subproblems of the proposed algorithm for several widely-used hyperparameter turning models can be reformulated into conic programs that can be efficiently solved by the off-the-shelf solvers. We theoretically prove the convergence of the proposed algorithm and demonstrate its superiority through numerical experiments.

Fair principal component analysis (FPCA), a ubiquitous dimensionality reduction technique in signal processing and machine learning, aims to find a low-dimensional representation for a high-dimensional dataset in view of fairness. The FPCA problem involves optimizing a non-convex and non-smooth function over the Stiefel manifold. The state-of-the-art methods for solving the problem are subgradient methods and semidefinite relaxation-based methods. However, these two types of methods have their obvious limitations and thus are only suitable for efficiently solving the FPCA problem in special scenarios. This paper aims at developing efficient algorithms for solving the FPCA problem in general, especially large-scale, settings. In this paper, we first transform FPCA into a smooth non-convex linear minimax optimization problem over the Stiefel manifold. To solve the above general problem, we propose an efficient alternating Riemannian/projected gradient descent ascent (ARPGDA) algorithm, which performs a Riemannian gradient descent step and an ordinary projected gradient ascent step at each iteration. We prove that ARPGDA can find an ε-stationary point of the above problem within ${\mathcal{O}}\left( {{\varepsilon ^{ - 3}}} \right)$ iterations. Simulation results show that, compared with the state-of-the-art methods, our proposed ARPGDA algorithm can achieve a better performance in terms of solution quality and speed for solving the FPCA problems.

Many machine learning tasks, such as principal component analysis and low-rank matrix completion, give rise to manifold optimization problems. Although there is a large body of work studying the design and analysis of algorithms for manifold optimization in the centralized setting, there are currently very few works addressing the federated setting. In this paper, we consider nonconvex federated learning over a compact smooth submanifold in the setting of heterogeneous client data. We propose an algorithm that leverages stochastic Riemannian gradients and a manifold projection operator to improve computational efficiency, uses local updates to improve communication efficiency, and avoids client drift. Theoretically, we show that our proposed algorithm converges sub-linearly to a neighborhood of a first-order optimal solution by using a novel analysis that jointly exploits the manifold structure and properties of the loss functions. Numerical experiments demonstrate that our algorithm has significantly smaller computational and communication overhead than existing methods.

Mathematical optimization is now widely regarded as an indispensable modeling and solution tool for the design of wireless communications systems. While optimization has played a significant role in the revolutionary progress in wireless communication and networking technologies from 1G to 5G and onto the future 6G, the innovations in wireless technologies have also substantially transformed the nature of the underlying mathematical optimization problems upon which the system designs are based and have sparked significant innovations in the development of methodologies to understand, to analyze, and to solve those problems. In this paper, we provide a comprehensive survey of recent advances in mathematical optimization theory and algorithms for wireless communication system design. We begin by illustrating common features of mathematical optimization problems arising in wireless communication system design. We discuss various scenarios and use cases and their associated mathematical structures from an optimization perspective. We then provide an overview of recently developed optimization techniques in areas ranging from nonconvex optimization, global optimization, and integer programming, to distributed optimization and learning-based optimization. The key to successful solution of mathematical optimization problems is in carefully choosing or developing suitable algorithms (or neural network architectures) that can exploit the underlying problem structure. We conclude the paper by identifying several open research challenges and outlining future research directions.

Fine-tuning pre-trained models has been ubiquitously proven to be effective in a wide range of NLP tasks. However, fine-tuning the whole model is parameter inefficient as it always yields an entirely new model for each task. Currently, many research works propose to only fine-tune a small portion of the parameters while keeping most of the parameters shared across different tasks. These methods achieve surprisingly good performance and are shown to be more stable than their corresponding fully fine-tuned counterparts. However, such kind of methods is still not well understood. Some natural questions arise: How does the parameter sparsity lead to promising performance? Why is the model more stable than the fully fine-tuned models? How to choose the tunable parameters? In this paper, we first categorize the existing methods into random approaches, rule-based approaches, and projection-based approaches based on how they choose which parameters to tune. Then, we show that all of the methods are actually sparse fine-tuned models and conduct a novel theoretical analysis of them. We indicate that the sparsity is actually imposing a regularization on the original model by controlling the upper bound of the stability. Such stability leads to better generalization capability which has been empirically observed in a lot of recent research works. Despite the effectiveness of sparsity grounded by our theory, it still remains an open problem of how to choose the tunable parameters. Currently, the random and rule-based methods do not utilize task-specific data information while the projection-based approaches suffer from the projection discontinuity problem. To better choose the tunable parameters, we propose a novel Second-order Approximation Method (SAM) which approximates the original problem with an analytically solvable optimization function. The tunable parameters are determined by directly optimizing the approximation function. We conduct extensive experiments on several tasks. The experimental results show that our proposed SAM model outperforms many strong baseline models and it also verifies our theoretical analysis. The source code of this paper can be obtained from https://github.com/fuzihaofzh/AnalyzeParameterEff\/icientFinetune .

This paper investigates the problem of exact community recovery in the symmetric $d$-uniform $(d \geq 2)$ hypergraph stochastic block model ($d$-HSBM). In this model, a $d$-uniform hypergraph with $n$ nodes is generated by first partitioning the $n$ nodes into $K\geq 2$ equal-sized disjoint communities and then generating hyperedges with a probability that depends on the community memberships of $d$ nodes. Despite the non-convex and discrete nature of the maximum likelihood estimation problem, we develop a simple yet efficient iterative method, called the projected tensor power method, to tackle it. As long as the initialization satisfies a partial recovery condition in the logarithmic degree regime of the problem, we show that our proposed method can exactly recover the hidden community structure down to the information-theoretic limit with high probability. Moreover, our proposed method exhibits a competitive time complexity of $\mathcal{O}(n\log^2n/\log\log n)$ when the aforementioned initialization condition is met. We also conduct numerical experiments to validate our theoretical findings.

Gromov-Wasserstein (GW) distance is a powerful tool for comparing and aligning probability distributions supported on different metric spaces. Recently, GW has become the main modeling technique for aligning heterogeneous data for a wide range of graph learning tasks. However, the GW distance is known to be highly sensitive to outliers, which can result in large inaccuracies if the outliers are given the same weight as other samples in the objective function. To mitigate this issue, we introduce a new and robust version of the GW distance called RGW. RGW features optimistically perturbed marginal constraints within a Kullback-Leibler divergence-based ambiguity set. To make the benefits of RGW more accessible in practice, we develop a computationally efficient and theoretically provable procedure using Bregman proximal alternating linearized minimization algorithm. Through extensive experimentation, we validate our theoretical results and demonstrate the effectiveness of RGW on real-world graph learning tasks, such as subgraph matching and partial shape correspondence.

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.

Graph learning from signals is a core task in graph signal processing (GSP). A significant subclass of graph signals called the stationary graph signals that broadens the concept of stationarity of data defined on regular domains to signals on graphs is gaining increasing popularity in the GSP community. The most commonly used model to learn graphs from these stationary signals is SpecT, which forms the foundation for nearly all the subsequent, more advanced models. Despite its strengths, the practical formulation of the model, known as rSpecT, has been identified to be susceptible to the choice of hyperparameters. More critically, it may suffer from infeasibility as an optimization problem. In this paper, we introduce the first condition that ensures the infeasibility of rSpecT and design a novel model called LogSpecT, along with its practical formulation rLogSpecT to overcome this issue. Contrary to rSpecT, our novel practical model rLogSpecT is always feasible. Furthermore, we provide recovery guarantees of rLogSpecT from modern optimization tools related to epi-convergence, which could be of independent interest and significant for various learning problems. To demonstrate the practical advantages of rLogSpecT, a highly efficient algorithm based on the linearized alternating direction method of multipliers (L-ADMM) that allows closed-form solutions for each subproblem is proposed with convergence guarantees. Extensive numerical results on both synthetic and real networks not only corroborate the stability of our proposed methods, but also highlight their comparable and even superior performance than existing models.

Nonconvex-nonconcave minimax optimization has received intense attention over the last decade due to its broad applications in machine learning. Most existing algorithms rely on one-sided information, such as the convexity (resp. concavity) of the primal (resp. dual) functions, or other specific structures, such as the Polyak-Łojasiewicz (PŁ) and Kurdyka-Łojasiewicz (KŁ) conditions. However, verifying these regularity conditions is challenging in practice. To meet this challenge, we propose a novel universally applicable single-loop algorithm, the doubly smoothed gradient descent ascent method (DS-GDA), which naturally balances the primal and dual updates. That is, DS-GDA with the same hyperparameters is able to uniformly solve nonconvex-concave, convex-nonconcave, and nonconvex-nonconcave problems with one-sided KŁ properties, achieving convergence with $\mathcal{O}(\epsilon^{-4})$ complexity. Sharper (even optimal) iteration complexity can be obtained when the KŁ exponent is known. Specifically, under the one-sided KŁ condition with exponent $\theta\in(0,1)$, DS-GDA converges with an iteration complexity of $\mathcal{O}(\epsilon^{-2\max\\{2\theta,1\\}})$. They all match the corresponding best results in the literature. Moreover, we show that DS-GDA is practically applicable to general nonconvex-nonconcave problems even without any regularity conditions, such as the PŁ condition, KŁ condition, or weak Minty variational inequalities condition. For various challenging nonconvex-nonconcave examples in the literature, including *Forsaken*, *Bilinearly-coupled minimax*, *Sixth-order polynomial*, and *PolarGame*, the proposed DS-GDA can all get rid of limit cycles. To the best of our knowledge, this is the first first-order algorithm to achieve convergence on all of these formidable problems.

Given the network and the time-triggered flow requests of a Time Sensitive Network (TSN), configuring the gate control lists (GCL) of IEEE 802.1Qbv for the ports of each node can be formed as a Job Shop Scheduling Problem, which is NP-hard. At present, most of the existing heuristic solutions for such problems consider scenarios where all given traffic flows can be scheduled. In order to solve the undetermined flow scheduling problem in scenarios no matter whether the flows can be scheduled or not, we propose to maximize the remaining time in conjunction with optimizing the network utilization instead of only minimizing the flowspan. Though the new problem is still NP-hard, it is a unified framework capable of covering general scenarios. On the basis of the new framework, we propose a novel Mixed initial population Genetic Algorithm (MGA) to solve the problem. Extensive simulation evaluation shows that MGA performs better and faster in different network scenarios while other methods prevails only in specific scenarios. This feature makes the method attractive in realistic TSN scheduling applications for in most cases it is hard for users to properly classifying the problem.

This paper is concerned with the algorithmic aspects of sharper stationarity of a nonconvex, nonsmooth, Clarke irregular machine learning model. We study the SVM problem with a $\rho$-margin loss function, which is the margin theory generalization bound of SVM introduced in the learning theory textbook by Mohri et al. [2018], and has been extensively studied in operations research, statistics, and machine learning communities. However, due to its nonconvex, nonsmooth, and irregular nature, none of the existing optimization methods can efficiently compute a d(irectional)-stationary point, which turns out to be also a local minimum, for the $\rho$-margin loss SVM problem. After a detailed discussion of various nonsmooth stationarity notions, we propose a highly efficient nonconvex semi-proximal ADMM-based scheme that provably computes d-stationary points and enjoys a local linear convergence rate. We report concrete examples to demonstrate the necessity of our assumptions. Numerical results verify the effectiveness of the new algorithm and complement our theoretical results.

Signed graphs encode similarity and dissimilarity relationships among different entities with positive and negative edges. In this paper, we study the problem of community recovery over signed graphs generated by the signed stochastic block model (SSBM) with two equal-sized communities. Our approach is based on the maximum likelihood estimation (MLE) of the SSBM. Unlike many existing approaches, our formulation reveals that the positive and negative edges of a signed graph should be treated unequally. We then propose a simple two-stage iterative algorithm for solving the regularized MLE. It is shown that in the logarithmic degree regime, the proposed algorithm can exactly recover the underlying communities in nearly-linear time at the information-theoretic limit. Numerical results on both synthetic and real data are reported to validate and complement our theoretical developments and demonstrate the efficacy of the proposed method.

In convex optimization, the problem of finding near-stationary points has not been adequately studied yet, unlike other optimality measures such as the function value. Even in the deterministic case, the optimal method (OGM-G, due to Kim and Fessler (2021)) has just been discovered recently. In this work, we conduct a systematic study of algorithmic techniques for finding near-stationary points of convex finite-sums. Our main contributions are several algorithmic discoveries: (1) we discover a memory-saving variant of OGM-G based on the performance estimation problem approach (Drori and Teboulle, 2014); (2) we design a new accelerated SVRG variant that can simultaneously achieve fast rates for minimizing both the gradient norm and function value; (3) we propose an adaptively regularized accelerated SVRG variant, which does not require the knowledge of some unknown initial constants and achieves near-optimal complexities. We put an emphasis on the simplicity and practicality of the new schemes, which could facilitate future work.

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.

We report a practical finite-time algorithmic scheme to compute approximately stationary points for nonconvex nonsmooth Lipschitz functions. In particular, we are interested in two kinds of approximate stationarity notions for nonconvex nonsmooth problems, i.e., Goldstein approximate stationarity (GAS) and near-approximate stationarity (NAS). For GAS, our scheme removes the unrealistic subgradient selection oracle assumption in (Zhang et al., 2020, Assumption 1) and computes GAS with the same finite-time complexity. For NAS, Davis & Drusvyatskiy (2019) showed that $\rho$-weakly convex functions admit finite-time computation, while Tian & So (2021) provided the matching impossibility results of dimension-free finite-time complexity for first-order methods. Complement to these developments, in this paper, we isolate a new class of functions that could be Clarke irregular (and thus not weakly convex anymore) and show that our new algorithmic scheme can compute NAS points for functions in that class within finite time. To demonstrate the wide applicability of our new theoretical framework, we show that $\rho$-margin SVM, $1$-layer, and $2$-layer ReLU neural networks, all being Clarke irregular, satisfy our new conditions.

Simplex identification via split augmented Lagrangian (SISAL) is a popularly used algorithm in blind unmixing of hyperspectral images. Developed by José M. Bioucas-Dias in 2009, the algorithm is fundamentally relevant to tackling simplex-structured matrix factorization and, by extension, nonnegative matrix factorization, which have many applications under their umbrellas. In this article, we revisit SISAL and provide new meanings to this quintessential algorithm. The formulation of SISAL was motivated from a geometric perspective, with no noise. We show that SISAL can be explained as an approximation scheme from a probabilistic simplex component analysis framework, which is statistical and is principally more powerful in accommodating the presence of noise. The algorithm for SISAL was designed based on a successive convex approximation method, with a focus on practical utility. It was not known, by analyses, whether the SISAL algorithm has any kind of guarantee of convergence to a stationary point. By establishing associations between the SISAL algorithm and a line search--based proximal gradient method, we confirm that SISAL can indeed guarantee convergence to a stationary point. Our re-explanation of SISAL also reveals new formulations and algorithms. The performance of these new possibilities is demonstrated by numerical experiments.

Text generation tasks, including translation, summarization, language models, and etc. see rapid growth during recent years. Despite the remarkable achievements, the repetition problem has been observed in nearly all text generation models undermining the generation performance extensively. To solve the repetition problem, many methods have been proposed, but there is no existing theoretical analysis to show why this problem happens and how it is resolved. In this paper, we propose a new framework for theoretical analysis for the repetition problem. We first define the Average Repetition Probability (ARP) to characterize the repetition problem quantitatively. Then, we conduct an extensive analysis of the Markov generation model and derive several upper bounds of the average repetition probability with intuitive understanding. We show that most of the existing methods are essentially minimizing the upper bounds explicitly or implicitly. Grounded on our theory, we show that the repetition problem is, unfortunately, caused by the traits of our language itself. One major reason is attributed to the fact that there exist too many words predicting the same word as the subsequent word with high probability. Consequently, it is easy to go back to that word and form repetitions and we dub it as the high inflow problem. Furthermore, we extend our analysis to broader generation models by deriving a concentration bound of the average repetition probability for a general generation model. Finally, based on the theoretical upper bounds, we propose a novel rebalanced encoding approach to alleviate the high inflow problem and thus reducing the upper bound. The experimental results show that our theoretical framework is applicable in general generation models and our proposed rebalanced encoding approach alleviates the repetition problem significantly in both the translation task and the language modeling task. The source code of this paper can be obtained from https://github.com/fuzihaofzh/repetition-problem-nlg.

In this paper, we study the cardinality constrained mean-variance-skewness-kurtosis (MVSKC) model for sparse high-order portfolio optimization. The MVSKC model is computationally challenging, as the objective function is non-convex and the cardinality constraint is discontinuous. Since the cardinality constraint has the difference-of-convex (DC) property, we transform it into a penalty term and then propose three algorithms, namely the proximal difference-of-convex algorithm (pDCA), pDCA with extrapolation (pDCAe), and the successive convex approximation (SCA), to handle the resulting penalized mean-variance-skewness-kurtosis (PM-VSK) formulation. Moreover, we establish theoretical convergence results for pDCA and SCA. Numerical experiments on a real dataset demonstrate the superiority of our proposed methods in obtaining better objective values and sparser solutions efficiently.

We consider the problem of identifying the graph topology from a set of smooth graph signals. A well-known approach to this problem is minimizing the Dirichlet energy accompanied with some Frobenius norm regularization. Recent works have incorporated the logarithmic barrier on the node degrees to improve the overall graph connectivity without compromising graph sparsity, which is shown to be quite effective in enhancing the quality of the learned graphs. Although a primal-dual algorithm has been proposed in the literature to solve this type of graph learning formulations, it lacks a rigorous convergence analysis and appears to have a slow empirical performance. In this paper, we cast the graph learning formulation as a nonsmooth, strictly convex optimization problem and develop an efficient alternating direction method of multipliers to solve it. We show that our algorithm converges to the global minimum with arbitrary initialization. We conduct extensive experiments on various synthetic and real-world graphs, the results of which show that our method exhibits sharp linear convergence and is substantially faster than the commonly adopted primal-dual method.

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.

The recent success of single-agent reinforcement learning (RL) in Internet of Things (IoT) systems motivates the study of multiagent RL (MARL), which is more challenging but more useful in large-scale IoT. In this article, we consider a voting-based MARL problem, in which the agents vote to make group decisions and the goal is to maximize the globally averaged returns. To this end, we formulate the MARL problem based on the linear programming form of the policy optimization problem and propose a primal-dual algorithm to obtain the optimal solution. We also propose a voting mechanism through which the distributed learning achieves the same sublinear convergence rate as centralized learning. In other words, the distributed decision making does not slow down the process of achieving global consensus on optimality. Finally, we verify the convergence of our proposed algorithm with numerical simulations and conduct case studies in practical multiagent IoT systems.

Graph learning is one of the most important tasks in machine learning, statistics and signal processing. In this paper, we focus on the problem of learning the generalized graph Lapla-cian (GGL) and propose an efficient algorithm to solve it. We first fully exploit the sparsity structure hidden in the objective function by utilizing soft-thresholding technique to transform the GGL problem into an equivalent problem. Moreover, we propose a fast proximal point algorithm (PPA) to solve the transformed GGL problem and establish the linear convergence rate of our algorithm. Extensive numerical experiments on both synthetic data and real data demonstrate that the soft-thresholding technique accelerates our PPA method and PPA can outperform the current state-of-the-art method in terms of speed.

Variable selection is one of the most important tasks in statistics and machine learning. To incorporate more prior information about the regression coefficients, various constrained Lasso models have been proposed in the literature. Compared with the classic (unconstrained) Lasso model, the algorithmic aspects of constrained Lasso models are much less explored. In this paper, we demonstrate how the recently developed semis-mooth Newton-based augmented Lagrangian framework can be extended to solve a linear equality-constrained Lasso model. A key technical challenge that is not present in prior works is the lack of strong convexity in our dual problem, which we overcome by adopting a regularization strategy. We show that under mild assumptions, our proposed method will converge superlinearly. Moreover, extensive numerical experiments on both synthetic and real-world data show that our method can be substantially faster than existing first-order methods while achieving a better solution accuracy.

Learning community structures in graphs that are randomly generated by stochastic block models (SBMs) has received much attention lately. In this paper, we focus on the problem of exactly recovering the communities in a binary symmetric SBM, where a graph of $n$ vertices is partitioned into two equal-sized communities and the vertices are connected with probability $p = \alpha\log(n)/n$ within communities and $q = \beta\log(n)/n$ across communities for some $\alpha>\beta>0$. We propose a two-stage iterative algorithm for solving this problem, which employs the power method with a random starting point in the first-stage and turns to a generalized power method that can identify the communities in a finite number of iterations in the second-stage. It is shown that for any fixed $\alpha$ and $\beta$ such that $\sqrt{\alpha} - \sqrt{\beta} > \sqrt{2}$, which is known to be the information-theoretical limit for exact recovery, the proposed algorithm exactly identifies the underlying communities in $\tilde{O}(n)$ running time with probability tending to one as $n\rightarrow\infty$. We also present numerical results of the proposed algorithm 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.

Wasserstein \textbf{D}istributionally \textbf{R}obust \textbf{O}ptimization (DRO) is concerned with finding decisions that perform well on data that are drawn from the worst probability distribution within a Wasserstein ball centered at a certain nominal distribution. In recent years, it has been shown that various DRO formulations of learning models admit tractable convex reformulations. However, most existing works propose to solve these convex reformulations by general-purpose solvers, which are not well-suited for tackling large-scale problems. In this paper, we focus on a family of Wasserstein distributionally robust support vector machine (DRSVM) problems and propose two novel epigraphical projection-based incremental algorithms to solve them. The updates in each iteration of these algorithms can be computed in a highly efficient manner. Moreover, we show that the DRSVM problems considered in this paper satisfy a Hölderian growth condition with explicitly determined growth exponents. Consequently, we are able to establish the convergence rates of the proposed incremental algorithms. Our numerical results indicate that the proposed methods are orders of magnitude faster than the state-of-the-art, and the performance gap grows considerably as the problem size increases.

We propose a new methodology to design first-order methods for unconstrained strongly convex problems. Specifically, instead of tackling the original objective directly, we construct a shifted objective function that has the same minimizer as the original objective and encodes both the smoothness and strong convexity of the original objective in an interpolation condition. We then propose an algorithmic template for tackling the shifted objective, which can exploit such a condition. Following this template, we derive several new accelerated schemes for problems that are equipped with various first-order oracles and show that the interpolation condition allows us to vastly simplify and tighten the analysis of the derived methods. In particular, all the derived methods have faster worst-case convergence rates than their existing counterparts. Experiments on machine learning tasks are conducted to evaluate the new methods.

The problem of geolocating an unknown high-frequency emitter based on the quasi-parabolic ionosphere model with time-difference of arrival measurements of the refracted radio rays is of fundamental importance in various military and civilian applications. Such a problem admits a maximum-likelihood (ML) formulation, which is nonlinear and non-convex. By elucidating the geometry of the feasible set of the ML formulation, we develop a first-order algorithm, which we call Generalized Projected Gradient Descent, to solve it. We prove that every limit point of the iterates generated by our proposed algorithm is a critical point of the ML formulation. Simulation results show that our proposed algorithm can more reliably and accurately geolocate the emitter than a state-of-the-art method in various settings.

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.

Wasserstein distance-based distributionally robust optimization (DRO) has received much attention lately due to its ability to provide a robustness interpretation of various learning models. Moreover, many of the DRO problems that arise in the learning context admits exact convex reformulations and hence can be tackled by off-the-shelf solvers. Nevertheless, the use of such solvers severely limits the applicability of DRO in large-scale learning problems, as they often rely on general purpose interior-point algorithms. On the other hand, there are very few works that attempt to develop fast iterative methods to solve these DRO problems, which typically possess complicated structures. In this paper, we take a first step towards resolving the above difficulty by developing a first-order algorithmic framework for tackling a class of Wasserstein distance-based distributionally robust logistic regression (DRLR) problem. Specifically, we propose a novel linearized proximal ADMM to solve the DRLR problem, whose objective is convex but consists of a smooth term plus two non-separable non-smooth terms. We prove that our method enjoys a sublinear convergence rate. Furthermore, we conduct three different experiments to show its superb performance on both synthetic and real-world datasets. In particular, our method can achieve the same accuracy up to 800+ times faster than the standard off-the-shelf solver.

Anonymous communication is desirable for personal, financial, and political reasons. Despite the abundance of frameworks and constructions, anonymity definitions are usually either not well defined or too complicated to use. In between are ad-hoc definitions for specific protocols which sometimes only provide weakened anonymity guarantees. This paper addresses this situation from the perspectives of syntax, security definition, and construction. We propose simple yet expressive syntax and security definition for anonymous communication. Our syntax covers protocols with different operational characteristics. We give a hierarchy of anonymity definitions, starting from the strongest possible to several relaxations. We also propose a modular construction from any key-private public-key encryption scheme, and a new primitive-oblivious forwarding protocols, of which we give two constructions. The first is a generic construction from any random walk over graphs, while the second is optimized for the probability of successful delivery, with experimental validation for our optimization. Anonymity is guaranteed even when the adversary can observe and control all traffic in the network and corrupt most nodes, in contrast to some efficient yet not-so-anonymous protocols. We hope this work suggests an easier way to design and analyze efficient anonymous communication protocols in the future.

We consider the problem of unknown emitter geolocation using the time difference of arrival (TDOA) of the path rays through the ionosphere by multiple coordinated distant receivers. We formulate the geolocation in the sense of maximum likelihood with the exact ray expressions for the quasi-parabolic (QP) ionosphere, which is a highly nonlinear and non-convex optimization problem. By carefully studying the characteristic of the group path ray, we propose an efficient procedure to approach the optimal solution of the geolocation. Simulation results show that the geolocation error approaches the associated Cramer-Rao bound when the knowledge of the ionosphere is available. We also performed Monte Carlo runs to evaluate the performance of the geolocation when the knowledge of the ionosphere is not exactly known, e.g., the QP model parameters are perturbed. Simulation results show that the geolocation performance under the perturbation within a given certain range is acceptable.

Classifying binary imbalanced streaming data is a significant task in both machine learning and data mining. Previously, online area under the receiver operating characteristic (ROC) curve (AUC) maximization has been proposed to seek a linear classifier. However, it is not well suited for handling nonlinearity and heterogeneity of the data. In this paper, we propose the kernelized online imbalanced learning (KOIL) algorithm, which produces a nonlinear classifier for the data by maximizing the AUC score while minimizing a functional regularizer. We address four major challenges that arise from our approach. First, to control the number of support vectors without sacrificing the model performance, we introduce two buffers with fixed budgets to capture the global information on the decision boundary by storing the corresponding learned support vectors. Second, to restrict the fluctuation of the learned decision function and achieve smooth updating, we confine the influence on a new support vector to its -nearest opposite support vectors. Third, to avoid information loss, we propose an effective compensation scheme after the replacement is conducted when either buffer is full. With such a compensation scheme, the performance of the learned model is comparable to the one learned with infinite budgets. Fourth, to determine good kernels for data similarity representation, we exploit the multiple kernel learning framework to automatically learn a set of kernels. Extensive experiments on both synthetic and real-world benchmark data sets demonstrate the efficacy of our proposed approach.

Unlike dimensionality reduction (DR) tools for single-view data, e.g., principal component analysis (PCA), canonical correlation analysis (CCA) and generalized CCA (GCCA) are able to integrate information from multiple feature spaces of data. This is critical in multi-modal data fusion and analytics, where samples from a single view may not be enough for meaningful DR. In this work, we focus on a popular formulation of GCCA, namely, MAX-VAR GCCA. The classic MAX-VAR problem is optimally solvable via eigen-decomposition, but this solution has serious scalability issues. In addition, how to impose regularizers on the sought canonical components was unclear - while structure-promoting regularizers are often desired in practice. We propose an algorithm that can easily handle datasets whose sample and feature dimensions are both large by exploiting data sparsity. The algorithm is also flexible in incorporating regularizers on the canonical components. Convergence properties of the proposed algorithm are carefully analyzed. Numerical experiments are presented to showcase its effectiveness.

In this work, we consider the robust beamforming design for secondary downlink multicasting channels, where primary users are present with norm-bounded channel errors. In particular, the max-min-fair formulation is considered and the resulting design problem is a quadratically constrained quadratic program (QCQP) with a set of semi-infinite constraints, which is NP-hard in general. As a remedy, we apply the semidefinite relaxation (SDR) technique and S-lemma to approximate the problem into a tractable form. The key contribution of this paper is to study the approximation quality. Our analytical results show that, the SDR solution achieves an objective value that is at least Ω(1/MN log J) times the optimal objective value, where M is the number of secondary users, J is the number of primary users, and N is the number of antennas at the secondary base station. This is a fundamentally new result for SDR applied to robust QCQPs. Practically, it provides a performance guarantee for the robust beamforming design. All these results are verified by our numerical simulations.

We consider the degree distribution design of the low-density parity-check (LDPC) code ensembles for symmetric Gaussian multiple-access channels (GMAC). To characterize the probability density function (PDF) of the message passing in the process of joint decoding, we propose a new scheme to construct the associated Gaussian mixture (GM) distribution, where each GM component is assigned according to the corresponding signal group transmitted by the users. By tracking the variation of the GM components in the iterative decoding process, more accurate mutual information can be obtained for the extrinsic information transfer (EXIT) chart analysis. Simulation results show that the performance of our proposed LDPC codes is better than that of the existing methods.

In this paper, we consider a device-to-device (D2D) network underlying a cellular system wherein the densely deployed D2D user devices can act as wireless relays for a distant transceiver pair. We aim to devise a beamforming strategy for the relays that maximizes the data rate of the distant transceiver while satisfying interference constraints at the cellular receivers. Towards that end, we first formulate a beamforming problem whose solution is robust against the channel uncertainties in the relay-destination hop. Motivated by practical observations, we assume that the random channels in this hop follow unimodal distributions and propose a novel unimodal distributionally robust model to capture the channel uncertainties. Then, we extend the formulation so that it can also guard against the channel uncertainty in the source-relay hop under the worst case robust model. The resulting robust beamforming problem is generally non-convex and intractable. Therefore, we design an iterative algorithm, which is based on solving semidefinite programs, to find an approximate solution to it. Simulation results show that under mild conditions, our robust model significantly improves the throughput of D2D relay transmissions when compared with the conventional robust models that merely rely on the channels' moment information. It also outperforms the Bernstein-type inequality-based convex approximation, which assumes that the channel follows a Gaussian distribution.

Motivated by the observation that energy harvesting (EH) from radio-frequency (RF) signal is subject to fluctuations, multiple EH-enabled relays are employed to collaboratively enhance data communications in a device-to-device (D2D) network underlying a cellular system. Each relay is equipped with a single antenna and unable to harvest energy and transmit data simultaneously. Thus, the D2D user equipment (DUE) needs to optimally schedule the channel time for the relays' EH and data transmissions, which depends on their EH capabilities and channel conditions. Considering that the relays' channel estimations are usually unreliable, we formulate a robust throughput maximization problem to optimize the relays' EH time and transmit power, subject to a probabilistic interference constraint at the cellular user equipment (CUE). We show that the proposed problem, though non-convex, can be tackled by exploiting its monotonicity structure. Specifically, we design a successive approximation algorithm that involves solving a sequence of semi-definite programs (SDPs) and show numerically that it always achieves the global optimum. This validates our analysis and demonstrates the efficacy of the proposed algorithm.

In this paper, we consider the robust beamforming design in a device-to-device (D2D) two-hop one-way relay network. Specifically, we study the amplify-and-forward (AF) scheme in the scenario where both the transmitter-to-relays link and relays-to-receiver link are subject to estimation errors. Assuming that those errors lie in a ball with bounded radius, the resulting design problem can be formulated as a semi-infinite program (SIP) that involves high-degree polynomial inequality constraints, which is difficult to deal with in general. In this paper, we employ the semidefinite relaxation (SDR) technique and tools from polynomial optimization to construct a safe approximation of the aforementioned SIP. Furthermore, we propose an alternating algorithm to tackle the safe approximation. To the best of our knowledge, our work is the first to provide an efficient algorithmic approach to the aforementioned robust beamforming design problem. In addition, our numerical results show that the proposed robust beamforming design is more reliable than the non-robust counterpart, and it can achieve better signal-to-noise ratios (SNRs) than the existing linear approximation approach, which ignores error terms with degree higher than one.

We consider the problem of geolocating two unknown co-channel emitters by a cluster of formation-flying satellites using both time difference of arrival (TDOA) and frequency difference of arrival (FDOA) measurements. As the association between the TDOA/FDOA measurements obtained by each pair of satellites and the corresponding emitters is typically not known, the emitter-measurement association and the emitters' locations need to be jointly estimated. In this paper, we first formulate the joint estimation problem as a mixed integer nonlinear optimization problem. Then, we propose a semidefinite relaxation-based approach to tackle the problem and demonstrate its efficacy via simulations.

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.

We consider a wireless network with densely deployed user devices (e.g., a device-to-device or wireless sensor network) underlaying a cellular system, in which some user devices act as relays to facilitate data transmissions between a distant transceiver pair under imperfect channel information. Motivated by the observation that most of the channel distributions are unimodal, we formulate a novel distributionally robust beamforming problem, in which the random channel coefficient follows a class of unimodal distribution with known first- and second-order moments. Our design objective is to maximize the worst-case signal-to-noise ratio (SNR) at the dedicated user device while satisfying a probabilistic interference constraint at the cellular user equipment (CUE). Though such a unimodal distributionally robust (UDR) beamforming problem is non-convex, we show that an approximate solution can be computed efficiently using semidefinite programming. Our simulation results show that under mild conditions, the UDR model yields significant beamforming performance improvement over conventional robust models that merely rely on first- and second-order moments of the channel distribution.

This letter studies a robust design problem for far-field line-of-sight (LOS) propagation channels where phase errors are present. Compared with the commonly used additive error model, the phase error model is more suitable for capturing the uncertainty in an LOS propagation channel, as the dominant source of uncertainty lies in the phase. We consider a multiple-input single-output multicast scenario, in which our goal is to design a beamformer that minimizes the transmit power while satisfying probabilistic signal-to-noise ratio constraints. In particular, the probabilistic constraints give rise to a new computational challenge, as they involve random trigonometric forms. In this study, we propose to first approximate the random trigonometric form by its second-order Taylor expansion and then tackle the resulting random quadratic form using a Bernstein-type inequality. It follows that an approximately optimal beamformer can be obtained using the standard semidefinite relaxation technique. Such a design approach is applicable to both independent and correlated phase errors. In the simulations, we first show that if a nonrobust design (i.e., one that does not take phase errors into account) is used; then, the whole system may collapse. We then show that our proposed method is less conservative than the existing robust design based on Gaussian approximation and thus requires a lower power budget.

In this paper, we consider a two-hop one-way relay network for multigroup multicast transmission between long-distance users, in which the relay is equipped with multiple antennas, while the transmitters and receivers are all with a single antenna. Assuming that the perfect channel state information is available, we study amplify-and-forward (AF) schemes that aim at optimizing the max-min-fair (MMF) rate. We begin by considering the classic beamformed AF (BF-AF) scheme, whose corresponding MMF design problem can be formulated as a rank-constrained fractional semidefinite program (SDP). We show that the gap between the BF-AF rate and the SDR rate associated with an optimal SDP solution is sensitive to the number of users as well as the number of power constraints in the relay system. This reveals that the BF-AF scheme may not be well suited for large-scale systems. We, therefore, propose the stochastic beamformed AF (SBF-AF) schemes, which differ from the BF-AF scheme in that time-varying AF weights are used. We prove that the MMF rates of the proposed SBF-AF schemes are at most 0.8317 bits/s/Hz less than the SDR rate, irrespective of the number of users or power constraints. Thus, SBF-AF can outperform BF-AF especially in large-scale systems. Finally, we present numerical results to demonstrate the viability of our proposed schemes.

Online learning from imbalanced streaming data to capture the nonlinearity and heterogeneity of the data is significant in machine learning and data mining. To tackle this problem, we propose a kernelized online imbalanced learning (KOIL) algorithm to directly maximize the area under the ROC curve (AUC). We address two more challenges: 1) How to control the number of support vectors without sacrificing model performance; and 2) how to restrict the fluctuation of the learned decision function to attain smooth updating. To this end, we introduce two buffers with fixed budgets (buffer sizes) for positive class and negative class, respectively, to store the learned support vectors, which can allow us to capture the global information of the decision boundary. When determining the weight of a new support vector, we confine its influence only to its $k$-nearest opposite support vectors. This can restrict the effect of new instances and prevent the harm of outliers. More importantly, we design a sophisticated scheme to compensate the model after replacement is conducted when either buffer is full. With this compensation, the learned model approaches the one learned with infinite budgets. We present both theoretical analysis and extensive experimental comparison to demonstrate the effectiveness of our proposed KOIL.

In this paper, we consider a cloud relay network (C-RN) which provides reliable communication between long-distance users. Specifically, we study the amplify-and-forward (AF) schemes in C-RNs. In our scenario setting, with the cloud processor units fully coordinating in the network, the C-RN can be treated as an MIMO relay system. We therefore propose the beamformed (BF) Alamouti AF scheme to provide multigroup multicast information delivery in this network. By applying an Alamouti space-time code structure, the relays adopt two rank-one weights to AF the received signals in two time slots. Then, one more degree of freedom is available compared to the traditional BF AF scheme, and a new fractional semidefinite relaxation (SDR) is obtained from a max-min-fair quality-of-service (QoS) perspective. We prove that the Gaussian randomization algorithm based on the new fractional SDR has the same approximation quality-i.e., on the order of √M-as the traditional rank-two SDR approximation in multigroup multicast networks without relays, where M is the number of users served in the network. This result is verified by our numerical experiments.

Recently, \ell_1,p-regularization has been widely used to induce structured sparsity in the solutions to various optimization problems. Motivated by the desire to analyze the convergence rate of first-order methods, we show that for a large class of \ell_1,p-regularized problems, an error bound condition is satisfied when p∈[1,2] or p=∞but fails to hold for any p∈(2,∞). Based on this result, we show that many first-order methods enjoy an asymptotic linear rate of convergence when applied to \ell_1,p-regularized linear or logistic regression with p∈[1,2] or p=∞. By contrast, numerical experiments suggest that for the same class of problems with p∈(2,∞), the aforementioned methods may not converge linearly.

This letter considers multi-input single-output (MISO) downlink multicasting with finite-alphabet inputs when perfect channel state information is known at the transmitter. Two advanced transmit schemes, namely the beamformed (BF) Alamouti scheme and the stochastic beamforming (SBF) scheme, for maximizing the finite-alphabet-constrained multicast rate are studied. We show that the transmit optimization for these two schemes can be formulated as an SNR-based max-min-fair (MMF) problem with Gaussian inputs, which can be handled via the semidefinite relaxation (SDR) technique. Apart from transmit optimization, we analyzed the rate performance of the two schemes. Our analytical results show that for BF Alamouti, the multicast rate degrades with the number of users M at a rate of √M, which is better than the traditional transmit beamforming scheme. For SBF, the multicast rate degradation is less sensitive to the increase in the number of users and outperforms BF Alamouti for large M. All the results were verified by numerical simulations.

We investigate latent aspect mining problem that aims at automatically discovering aspect information from a collection of review texts in a domain in an unsupervised manner. One goal is to discover a set of aspects which are previously unknown for the domain, and predict the user's ratings on each aspect for each review. Another goal is to detect key terms for each aspect. Existing works on predicting aspect ratings fail to handle the aspect sparsity problem in the review texts leading to unreliable prediction. We propose a new generative model to tackle the latent aspect mining problem in an unsupervised manner. By considering the user and item side information of review texts, we introduce two latent variables, namely, user intrinsic aspect interest and item intrinsic aspect quality facilitating better modeling of aspect generation leading to improvement on the accuracy and reliability of predicted aspect ratings. Furthermore, we provide an analytical investigation on the Maximum A Posterior (MAP) optimization problem used in our proposed model and develop a new block coordinate gradient descent algorithm to efficiently solve the optimization with closed-form updating formulas. We also study its convergence analysis. Experimental results on the two real-world product review corpora demonstrate that our proposed model outperforms existing state-of-the-art models.

Consider a wireless scenario in which a multi-antenna transmitter wants to send a confidential message to a single-antenna information receiver (IR) while transferring wireless energy to a number of multi-antenna energy receivers (ERs). In order to keep the ERs from retrieving the confidential message, an artificial noise (AN)-aided physical-layer secrecy approach is employed at the transmitter. The AN has dual purpose: First, it can interfere with the ERs' information receptions and thus help improve security. Secondly, it provides wireless energy for the ERs to harvest. Assuming imperfect channel state information at the transmitter, we jointly optimize the co-variances of confidential information and AN such that the secrecy rate at the IR is maximized, while each ER receives a prescribed amount of wireless energy. Although this secrecy-rate maximization problem is non-convex, we show that it can be handled by solving a sequence of convex optimization problems. Numerical results are provided to demonstrate the efficacy of the proposed design.

This paper considers robust transmit beamforming for multiuser multi-input single-output (MISO) downlink transmission, where imperfect channel state information (CSI) is assumed at the base station (BS). The imperfect CSI is captured by a moment-based random error model, in which the BS knows only the mean and covariance of each CSI error, but not the exact distribution. Under this error model, we formulate a distributionally robust beamforming (DRB) problem, in which the total transmit power at the BS is to be minimized, while each user's SINR outage probability, evaluated w.r.t. any distribution with the given mean and covariance, is kept below a given threshold. The DRB problem is a semi-infinite chance-constrained problem. By employing recent results in distributionally robust optimization, we show that the DRB problem admits an explicit conic reformulation, which can be conveniently turned into a convex optimization problem after semidefinite relaxation (SDR). We also consider the case where the mean and covariance are not perfectly known. We show that the resulting DRB problem still admits a conic reformulation and can be approximately solved using SDR. The robustness of the proposed designs are demonstrated by numerical simulations.

In this paper, we consider an outage-based robust beamforming problem in two-way relay networks under the imperfect channel state information (CSI) scenario. Specficially, our goal is to minimize the relay transmit power while keeping the probability of each user's signal-to-interference-plus-noise ratio (SINR) outage as caused by the imperfect CSI below a given threshold. Assuming that the CSI errors follow a complex Gaussian distribution, the probabilistic SINR constraints involve quartic polynomials of complex Gaussian random variables, which, to the best of our knowledge, have not been treated from a computational perspective before. Using moment inequalities for Gaussian polynomials and the semidefinite relaxation technique, we propose a new tractable approximation approach for tackling such constraints. Simulation results show that the proposed method outperforms the existing robust approaches when the CSI errors are large.

Recently, simultaneous wireless information and power transfer (SWIPT) has received considerable attention. In this paper, we consider a multicast SWIPT system, where a multi-antenna transmitter broadcasts common information to a group of single-antenna information receivers (IRs) and at the same time provides certain amount of energy transfer to a group of single-antenna energy receivers (ERs). Assuming imperfect channel state information (CSI) at the transmitter, two transmit schemes are proposed to maximize the IRs' outage-constrained multicast rate subject to a minimum provision of average energy transfer to ERs. In the first transmit scheme, we consider transmit beamforming and develop a safe approximation approach to obtain a conservative beamforming solution for maximizing the outage-constrained multicast rate. To further improve the performance of transmit beamforming, in the second transmit scheme, we consider a stochastic beamforming (SBF) approach, which allows the beamformer to randomly change over time according to some prescribed distribution. By doing so, the SBF scheme is able to fully exploit the temporal degree of freedom to achieve more balanced outage-constrained achievable rates among IRs. Simulation results demonstrated that the SBF scheme is generally better than the transmit beamforming scheme.

Consider a multi-input multi-output (MIMO) channel wiretapped by multiple multi-antenna eavesdroppers. Assuming imperfect eavesdroppers' channel state information (CSI) at the transmitter, an outage-constrained secrecy rate maximization (OC-SRM) problem is considered. Specifically, we aim to design the transmit covariance matrix such that the outage secrecy rate is maximized for a given outage probability. The OC-SRM problem is challenging, and as a compromise, we resort to a recently developed Bernstein-type inequality approach to obtain a safe (conservative) approximate solution for OC-SRM. The merit of the proposed safe design lies in its tractability. In particular, a safe solution can be efficiently computed by alternately solving two convex conic optimization problems. The efficacy of the proposed design is demonstrated by simulations.

In this paper, we consider transmit design in multiple-input single-output (MISO) multi-group multicast (MM) cognitive radio (CR) systems. Previously, semidefinite relaxation (SDR)-based transmit beamforming has been very successful in transmit design. However, recent research shows that further performance gain is possible by suitably modifying the transmit structure. Here, we propose a transmit beamformed Alamouti space-time code scheme for MM-CR systems, whose corresponding transmit design problem can be reformulated as a rank-2 constrained fractional semidefinite program. We then develop an SDR framework for this scheme and study its signal-to-interference-and-noise ratio (SINR) performance via both theoretical analysis and simulations. Specifically, we show that the worst-case approximation accuracy of the proposed scheme scales on the order of √MSlog MP, where MP(resp. MS) is the number of primary (resp. secondary) users in the CR network. This unifies and generalizes a number of results in the literature and is, to the best of our knowledge, the first provable bound on the performance of a beamforming scheme in a general MM-CR system. Finally, simulation results show that our proposed scheme indeed has a better performance in both MM and MM-CR scenarios than the traditional beamforming scheme.

The successful deployment and operation of location-aware networks, which have recently found many applications, depends crucially on the accurate localization of the nodes. Currently, a powerful approach to localization is that of convex relaxation. In a typical application of this approach, the localization problem is first formulated as a rank-constrained semidefinite program (SDP), where the rank corresponds to the target dimension in which the nodes should be localized. Then, the non-convex rank constraint is either dropped or replaced by a convex surrogate, thus resulting in a convex optimization problem. In this paper, we explore the use of a non-convex surrogate of the rank function, namely the so-called Schatten quasi- norm, in network localization. Although the resulting optimization problem is non-convex, we show, for the first time, that a first- order critical point can be approximated to arbitrary accuracy in polynomial time by an interior-point algorithm. Moreover, we show that such a first-order point is already sufficient for recovering the node locations in the target dimension if the input instance satisfies certain established uniqueness properties in the literature. Finally, our simulation results show that in many cases, the proposed algorithm can achieve more accurate localization results than standard SDP relaxations of the problem.

Motivated by various applications in machine learning, the problem of minimizing a convex smooth loss function with trace norm regularization has received much attention lately. Currently, a popular method for solving such problem is the proximal gradient method (PGM), which is known to have a sublinear rate of convergence. In this paper, we show that for a large class of loss functions, the convergence rate of the PGM is in fact linear. Our result is established without any strong convexity assumption on the loss function. A key ingredient in our proof is a new Lipschitzian error bound for the aforementioned trace norm-regularized problem, which may be of independent interest.

Being the predominant air interface of next-generation wireless standards, orthogonal frequency division multiple access (OFDMA) is well known for its flexibility in allocating subcarriers to different mobile users according to their different fast channel variations. Numerous research studies have demonstrated that OFDMA can bring substantial capacity gain when the subcarriers are optimally allocated. Nonetheless, practical systems can hardly afford optimal subcarrier allocation, because frequent re-optimization performed at the same timescale as fast fading variation would lead to excessively high computational and signaling costs. As a result, most practical systems settle for low-complexity schemes that operate far from the optimum, thus making them unable to enjoy the large capacity gain predicted by theoretical studies. To address this problem, we propose a novel alternative, termed the slow adaptive OFDMA, to drastically reduce the computational and signaling costs. The proposed scheme adapts subcarrier allocation at a much slower timescale than that of channel fading variation, yet achieves similar system capacity and quality of service (QoS) levels as the optimal fast adaptive OFDMA. Moreover, it possesses several attractive features. First, neither prediction of channel state information nor specification of channel fading distribution is needed for subcarrier allocation. As such, the algorithm is robust against any mismatch between actual channel state/distributional information and the one assumed. Secondly, although the optimization problem arising from our proposed scheme is non-convex in general, based on recent advances in chance-constrained optimization, we show that it can be approximated by a certain linear program with provable performance guarantees. In particular, we only need to handle an optimization problem that has the same structure as the fast adaptive OFDMA problem, yet we are able to enjoy lower computational and signaling costs. Last but not the least, instead of relying on standard but abstract linear program solvers such as the interior-point method to solve the aforementioned linear program, we can exploit its special structure and design a provably efficient algorithm for it. The proposed algorithm not only has a transparent engineering interpretation but is also easy to implement at the base stations of practical systems.

In physical-layer multicasting over a multiuser MISO downlink channel, transmit beamforming using semidefinite relaxation (SDR) has been a popular approach. In this paper, we propose a rank-2 transmit beamformed Alamouti space-time code scheme, which may be seen as a generalization of the previous SDR-based beamforming framework. The beamforming problem arising from the proposed scheme is a rank-2 constrained semidefinite program (SDP).We deal with it using the SDR technique, but this time using rank-2 approximation rather than rank-1 approximation in the previous transmit beamforming. An analysis on the worst-case approximation accuracy of the rank-2 SDR approximation is provided, which reveals that the approximation accuracy degrades at a rate of √M, where M is the number of users served. This improves upon the case of transmit beamforming, where the worst-case approximation accuracy degrades at the higher rate of M. Simulation results further show that the proposed scheme performs better than the transmit beamforming scheme.

We propose a novel stochastic process that is with probability $\alpha_i$ being absorbed at current state $i$, and with probability $1-\alpha_i$ follows a random edge out of it. We analyze its properties and show its potential for exploring graph structures. We prove that under proper absorption rates, a random walk starting from a set $\mathcal{S}$ of low conductance will be mostly absorbed in $\mathcal{S}$. Moreover, the absorption probabilities vary slowly inside $\mathcal{S}$, while dropping sharply outside $\mathcal{S}$, thus implementing the desirable cluster assumption for graph-based learning. Remarkably, the partially absorbing process unifies many popular models arising in a variety of contexts, provides new insights into them, and makes it possible for transferring findings from one paradigm to another. Simulation results demonstrate its promising applications in graph-based learning.

This paper considers the problem of low complexity implementation of high-performance semidefinite relaxation (SDR) MIMO detection methods. Currently, most SDR MIMO detectors are implemented using interior-point methods. Although such implementations have worst-case polynomial complexity (approximately cubic in the problem size), they can be quite computationally costly in practice. Here we depart from the interior-point method framework and investigate the use of other low per-iteration-complexity techniques for SDR MIMO detection. Specifically, we employ the row by-row (RBR) method, which is a particular version of block coordinate descent, to solve the semidefinite programs that arise in the SDR MIMO context with an emphasis on the QPSK scenario. In each iteration of the RBR method, only matrix-vector multiplications are needed, and hence it can be implemented in a very efficient manner. Our simulation results show that the RBR method can indeed offer a significant speedup in runtime, while providing bit error rate performance on par with the interior-point methods.

Recently, robust transmit beamforming has drawn considerable attention because it can provide guaranteed receiver performance in the presence of channel state information (CSI) errors. Assuming complex Gaussian distributed CSI errors, this paper investigates the robust beamforming design problem that minimizes the transmission power subject to probabilistic signal-to-interference-plus-noise ratio (SINR) constraints. The probabilistic SINR constraints in general have no closed-form expression and are difficult to handle. Based on a Bernstein-type inequality for quadratic forms of complex Gaussian random variables, we propose a conservative formulation to the robust single-cell beamforming design problem. The semidefinite relaxation technique can be applied to efficiently handle the proposed conservative formulation. Simulation results show that, in comparison with existing methods, the proposed method is more power efficient and is able to support higher target SINR values for receivers.

In cognitive radio (CR) networks with multiple-input multiple-output (MIMO) links, secondary users (SUs) can exploit "spectrum holes" in the space domain to access the spectrum allocated to a primary system. However, they need to suppress the interference caused to primary users (PUs), as the secondary system should be transparent to the primary system. In this paper, we study the optimal secondary-link beamforming pattern that balances between the SU's throughput and the interference it causes to PUs. In particular, we aim to maximize the throughput of the SU, while keeping the interference temperature at the primary receivers below a certain threshold. Unlike traditional MIMO systems, SUs may not have the luxury of knowing the channel state information (CSI) on the links to PUs. This presents a key challenge for a secondary transmitter to steer interference away from primary receivers. In this paper, we consider three scenarios, namely when the secondary transmitter has complete, partial, or no knowledge about the channels to the primary receivers. In particular, when complete CSI is not available, the interference-temperature constraints are to be satisfied with high probability, thus resulting in chance constraints that are typically hard to deal with. Our contribution is fourfold. First, by analyzing the distributional characteristics of MIMO channels, we propose a unified homogeneous quadratically constrained quadratic program (QCQP) formulation that can be applied to all three scenarios, in which different levels of CSI knowledge give rise to either deterministic or probabilistic interference-temperature constraints. The homogeneous QCQP formulation, though non-convex, is amenable to semidefinite programming (SDP) relaxation methods. Secondly, we show that the SDP relaxation admits no gap when the number of primary links is no larger than two. A polynomial-time algorithm is presented to compute the optimal solution to the QCQP problem efficiently. Thirdly, we propose a randomized polynomial-time algorithm for constructing a near-optimal solution to the QCQP problem when there are more than two primary links. Finally, we show that when the secondary transmitter has no CSI on the links to primary receivers, the optimal solution to the QCQP problem can be found by a simple matrix eigenvalue-eigenvector computation, which can be done much more efficiently than solving the QCQP directly.

A fundamental problem in wireless ad-hoc and sensor networks is that of determining the positions of nodes. Often, such a problem is complicated by the presence of nodes whose positions cannot be uniquely determined. Most existing work uses the notion of global rigidity from rigidity theory to address the non-uniqueness issue. However, such a notion is not entirely satisfactory, as it has been shown that even if a network localization instance is known to be globally rigid, the problem of determining the node positions is still intractable in general. In this paper, we propose to use the notion of universal rigidity to bridge such disconnect. Although the notion of universal rigidity is more restrictive than that of global rigidity, it captures a large class of networks and is much more relevant to the efficient solvability of the network localization problem. Specifically, we show that both the problem of deciding whether a given network localization instance is universally rigid and the problem of determining the node positions of a universally rigid instance can be solved efficiently using semidefinite programming (SDP). Then, we give various constructions of universally rigid instances. In particular, we show that trilateration graphs are generically universally rigid, thus demonstrating not only the richness of the class of universally rigid instances, but also the fact that trilateration graphs possess much stronger geometric properties than previously known. Finally, we apply our results to design a novel edge sparsification heuristic that can reduce the size of the input network while provably preserving its original localization properties. One of the applications of such heuristic is to speed up existing convex optimization-based localization algorithms. Simulation results show that our speedup approach compares very favorably with existing ones, both in terms of accuracy and computation time.

Due to their computational efficiency and strong empirical performance, semidefinite relaxation (SDR)-based algorithms have gained much attention in multiple-input multiple-output (MIMO) detection. In the case of a binary phase-shift keying (BPSK) constellation, the theoretical performance of the SDR approach is relatively well-understood. However, little is known about the case of quadrature amplitude modulation (QAM) constellations, although simulation results suggest that the SDR approach should work well in the low signal-to-noise ratio (SNR) region. In this paper we make a first step towards explaining such phenomenon by showing that in the case of QAM constellations, several commonly used SDR-based algorithms will provide a constant factor approximation to the optimal log-likelihood value in the low SNR region with exponentially high probability. Our result gives some theoretical justification for using SDR-based algorithms for the MIMO detection of QAM signals, at least in the low SNR region.

Kernel learning is a powerful framework for nonlinear data modeling. Using the kernel trick, a number of problems have been formulated as semidefinite programs (SDPs). These include Maximum Variance Unfolding (MVU) (Weinberger et al., 2004) in nonlinear dimensionality reduction, and Pairwise Constraint Propagation (PCP) (Li et al., 2008) in constrained clustering. Although in theory SDPs can be efficiently solved, the high computational complexity incurred in numerically processing the huge linear matrix inequality constraints has rendered the SDP approach unscalable. In this paper, we show that a large class of kernel learning problems can be reformulated as semidefinite-quadratic-linear programs (SQLPs), which only contain a simple positive semidefinite constraint, a second-order cone constraint and a number of linear constraints. These constraints are much easier to process numerically, and the gain in speedup over previous approaches is at least of the order $m^{2.5}$, where m is the matrix dimension. Experimental results are also presented to show the superb computational efficiency of our approach.

In this paper we consider the problem of approximating a class of quadratic optimization problems that contain orthogonality constraints, i.e. constraints of the form XTX = I, where X ∊ ℝm×n is the optimization variable. This class of problems, which we denote by (Qp–Oc), is quite general and captures several well–studied problems in the literature as special cases. In a recent work, Nemirovski [17] gave the first non–trivial approximation algorithm for (Qp–Oc). His algorithm is based on semidefinite programming and has an approximation guarantee of O ((m + n)1/3). We improve upon this result by providing the first logarithmic approximation guarantee for (Qp–Oc). Specifically, we show that (Qp–Oc) can be approximated to within a factor of O(ln(max{m, n})). The main technical tool used in the analysis is the so–called non–commutative Khintchine inequality, which allows us to prove a concentration inequality for the spectral norm of a Rademacher sum of matrices. As a by–product, we resolve in the affirmative a conjecture of Nemirovski concerning the typical spectral norm of a sum of certain random matrices. The aforementioned concentration inequality also has ramifications in the design of so–called safe tractable approximations of chance constrained optimization problems. In particular, we use it to simplify and improve a recent result of Ben–Tal and Nemirovski [4] concerning certain chance constrained linear matrix inequality systems.

Many applications of wireless sensor networks require collaboration among sensor nodes to achieve a common task. Moreover, this is often dynamic in nature. For instance, in multi-object tracking, sensor nodes that are tracking various moving objects must share information in order to improve the tracking quality. Thus, it is important to have a protocol that maintains group connectivity in such a setting. In this paper, we study the problem of maintaining communication paths among a group of moving agents that have interacted with one another. As its solution, we propose a data structure called the distributed collaboration graph (DCG), which is a communication graph obtained from the agent trajectories. The DCG can be constructed in a purely distributed fashion with very little cost and can be used for group discovery and for multicasting/broadcasting among agents. We also propose a distributed protocol which maintains a communication tree among the agents within the DCG while the agents are moving. This allows us to maintain group connectivity and provides the infrastructure for routing among the moving agents.