Motion planning for large-scale robotic swarms presents significant challenges in terms of scalability and safety assurance in cluttered environments. To address these issues, this manuscript proposes a Closed-loop hierarchical Risk-aware swarm mOtion planner using Conditional ValuE at Risk (C-ROVER) that enables safe and efficient navigation for swarm robotic systems. The hierarchical structure of C-ROVER comprises a macroscopic planning stage that models the swarm state with Gaussian Mixture Models (GMMs) and generates trajectories for the swarm GMM, followed by a microscopic control stage that computes individual robot control using distributed model predictive control to track the GMM trajectories while achieving robot-level collision avoidance. Robot positions are periodically used to update the swarm GMM, closing the hierarchical planning and control loop. To achieve collision risk-awareness between the swarm and environmental obstacles at the macroscopic stage, C-ROVER leverages the stochastic Signed Distance Function to characterize the distance between the swarm GMM and obstacles, which is proven to follow a GMM. Then C-ROVER proposes an analytical expression of Conditional Value-at-Risk (CVaR) of a GMM to enable the swarm collision risk mitigation. Furthermore, C-ROVER designs a novel risk-aware space discretization approach to enhance the ability to navigate constrained spaces. To achieve efficient online motion planning, C-ROVER develops a convergent sequential convex programming approach for macroscopic planning, leveraging the concavity of CVaR constraints. C-ROVER has been evaluated through various simulations and real-world experiments, demonstrating its capability to ensure safe, scalable, and real-time swarm navigation in cluttered scenarios.

Due to the communication bottleneck in distributed and decentralized federated learning applications, algorithms using compressed communication have attracted significant attention. The Error Feedback (EF) is a widely-studied compression framework for convergence with biased compressors such as top-k sparsification. Although various improvements have been obtained in recent years, the theoretical guarantee for EF-type framework is still limited. Previous works either 1) rely on strong assumptions such as bounded gradient/dissimilarity assumptions, thus can not deal with arbitrary data heterogeneity and also slow the convergence speed, or 2) can not enjoy linear speedup in the number of clients. In this work, we propose a new EFSkip framework which removes the strong assumptions to allow arbitrary data heterogeneity and enjoys linear speedup for significantly improving upon previous results. In particular, EFSkip achieves a substantially lower computational complexity compared to the previous EF21, i.e., EFSkip enjoys the linear speedup in the number of clients (reducing the result linearly using more clients). We also show that EFSkip enjoys linear speedup and achieves faster convergence for nonconvex problems satisfying Polyak-Lojasiewicz (PL) condition. We believe that the new EFSkip framework will have a large impact on the communication- and computation-efficient distributed and decentralized federated learning.

Motivated by the settings where sensing the entire tensor is infeasible, this paper proposes a novel tensor compressed sensing model, where measurements are only obtained from sensing each lateral slice via mutually independent matrices. Leveraging the low tubal rank structure, we reparameterize the unknown tensor ?* using two compact tensor factors and formulate the recovery problem as a nonconvex minimization problem. To solve the problem, we first propose an alternating minimization algorithm, termed Alt-PGD-Min, that iteratively optimizes the two factors using a projected gradient descent and an exact minimization step, respectively. Despite nonconvexity, we prove that Alt-PGD-Min achieves ϵ-accuracy recovery with ?(?²log1/?) iteration complexity and ?(?⁶rn₃logn₃(?²r(n₁+n₂)+n₁log1/ε)) sample complexity, where ? denotes tensor condition number of ?*. To further accelerate the convergence, especially when the tensor is ill-conditioned with large ?, we prove Alt-ScalePGD-Min that preconditions the gradient update using an approximate Hessian that can be computed efficiently. We show that Alt-ScalePGD-Min achieves ? independent iteration complexity ?(log1/ε) and improves the sample complexity to ?(?⁴rn₃log n₃(?⁴ r(n₁ + n₂)+n₁log 1/ε)). Experiments validate the effectiveness of the proposed methods.

Decentralized federated learning (DFL) can greatly reduce communication costs due to its decentralized communication structure compared to traditional centralized federated learning (FL). Existing works on FL with partial client participation often considered idealized scenarios (such as all clients participate in a round with the same probability), or required using clients' past gradient/model information which can be too costly to implement, or focused on centralized FL. In this paper, we study lightweight decentralized federated learning that does not use any client's past gradient/model information. We first present a novel sample-path-based cyclic convergence analysis for lightweight DFL with arbitrary client participation for the non-convex objectives case. The cyclic convergence analysis bounds clients' local model drifts due to partial participation over multiple rounds within a cycle and the cyclic consensus error via a per-cycle descent approach, while capturing the effect of client participation through a single unified term. By analyzing this term, we propose Cyclic Decentralized Federated Learning (CDFL), which enables general cyclic client participation by requiring only that each client performs the same total number of local updates per cycle. Our results show that CDFL achieves a convergence rate that matches existing benchmarks. We further propose a cyclic control framework that is both training-round and energy efficient to adaptively select participating clients and determine their number of local updates. Numerical experiments using real-world datasets verify our theoretical results and demonstrate the effectiveness of CDFL and the adaptive cyclic control framework.

In this paper, we propose a novel tube-wise local tensor compressed sensing (CS) model, where sensing operators are independently applied to each tube of a third-order tensor. To recover the low-rank ground truth tensor, we minimize a non-convex objective via Burer–Monteiro factorization and solve it using gradient descent with spectral initialization. We prove that this approach achieves exact recovery with a linear convergence rate. Notably, our method attains provably lower sample complexity than existing TCS methods. Our proof leverages the leave-one-out technique to show that gradient descent generates iterates implicitly biased towards solutions with bounded incoherence, which ensures contraction of optimization error in consecutive iterates. Empirical results validate the effectiveness of GD in solving the proposed local TCS model.

We study sparse linear regression over a network of agents, modeled as an undirected graph without a center node. The estimation of the $s$-sparse parameter is formulated as a constrained LASSO problem wherein each agent owns a subset of the $N$ total observations. We analyze the convergence rate and statistical guarantees of a distributed projected gradient tracking-based algorithm under high-dimensional scaling, allowing the ambient dimension $d$ to grow with (and possibly exceed) the sample size $N$. Our theory shows that, under standard notions of restricted strong convexity and smoothness of the average loss functions, suitable conditions on the network connectivity and algorithm tuning, the distributed algorithm converges globally at a linear rate to an estimate that is within the centralized statistical precision of the model, $O(s\log d/N)$. When $s\log d/N=o(1)$, a condition necessary for statistical consistency, an $\varepsilon$-optimal solution is attained after ${O}(\kappa \log (1/\varepsilon))$ gradient computations and $O(\kappa/(1-\rho) \log (1/\varepsilon))$ communication rounds, where $\kappa$ is the restricted condition number of the loss function and $\rho$ measures the network connectivity. The computation cost matches that of the centralized projected gradient algorithm despite having data distributed; whereas the communication rounds reduce as the network connectivity improves. Overall, our study reveals interesting connections between statistical efficiency, network connectivity and topology, and convergence rate in the high dimensional setting.

This paper considers solving a class of nonconvex-strongly-convex distributed stochastic bilevel optimization (DSBO) problems with personalized inner-level objectives. Most existing algorithms require computational loops for hypergradient estimation, leading to computational inefficiency. Moreover, the impact of data heterogeneity on convergence in bilevel problems is not explicitly characterized yet. To address these issues, we propose LoPA, a loopless personalized distributed algorithm that leverages a tracking mechanism for iterative approximation of inner-level solutions and Hessian-inverse matrices without relying on extra computation loops. Our theoretical analysis explicitly characterizes the heterogeneity across nodes (denoted by $b$), and establishes a sublinear rate of $\mathcal{O}( {\frac{1}{{{{\left( {1 - \rho } \right)}}K}}\!+ \!\frac{{(\frac{b}{\sqrt{m}})^{\frac{2}{3}} }}{{\left( {1 - \rho } \right)^{\frac{2}{3}} K^{\frac{2}{3}} }} \!+ \!\frac{1}{\sqrt{ K }}( {\sigma _{\operatorname{p} }} + \frac{1}{\sqrt{m}}{\sigma _{\operatorname{c} }} ) } )$ without the boundedness of local hypergradients, where ${\sigma _{\operatorname{p} }}$ and ${\sigma _{\operatorname{c} }}$ represent the gradient sampling variances associated with the inner- and outer-level variables, respectively. We also integrate LoPA with a gradient tracking scheme to eliminate the impact of data heterogeneity, yielding an improved rate of ${{\mathcal{O}}}(\frac{{1}}{{ (1-\rho)^2K }} \!+\! \frac{1}{{\sqrt{K}}}( \sigma_{\rm{p}} \!+\! \frac{1}{\sqrt{m}}\sigma_{\rm{c}} ) )$. The computational complexity of LoPA is of ${{\mathcal{O}}}({\epsilon^{-2}})$ to an $\epsilon$-stationary point, matching the communication complexity due to the loopless structure, which outperforms existing counterparts for DSBO. Numerical experiments validate the effectiveness of the proposed algorithm.

We consider learning a sparse model from linear measurements taken by a network of agents. Different from existing decentralized methods designed based on the LASSO regression with explicit $\ell_1$ norm regularization, we exploit the implicit regularization of decentralized optimization method applied to an over-parameterized nonconvex least squares formulation without penalization. Our first result shows that despite nonconvexity, if the network connectivity is good, the well-known decentralized gradient descent algorithm (DGD) with small initialization and early stopping can compute the statistically optimal solution. Sufficient conditions on the initialization scale, choice of step size, network connectivity, and stopping time are further provided to achieve convergence. Our result recovers the convergence rate of gradient descent in the centralized setting, showing its tightness. Based on the analysis of DGD, we further propose a communication-efficient version, termed T-DGD, by truncating the iterates before transmission. In the high signal-to-noise ratio (SNR) regime, we show that T-DGD achieves comparable statistical accuracy to DGD, while the communication cost is logarithmic in the number of parameters. Numerical results are provided to validate the effectiveness of DGD and T-DGD for sparse learning through implicit regularization.

We study sparse linear regression over a network of agents, modeled as an undirected graph (with no centralized node). The estimation problem is formulated as the minimization of the sum of the local LASSO loss functions plus a quadratic penalty of the consensus constraint—the latter being instrumental to obtain distributed solution methods. While penalty-based consensus methods have been extensively studied in the optimization literature, their statistical and computational guarantees in the high dimensional setting remain unclear. This work provides an answer to this open problem. Our contribution is two-fold. First, we establish statistical consistency of the estimator: under a suitable choice of the penalty parameter, the optimal solution of the penalized problem achieves near optimal minimax rate $O(s \log d/N)$ in $\ell_2$-loss, where $s$ is the sparsity value, $d$ is the ambient dimension, and $N$ is the total sample size in the network—this matches centralized sample rates. Second, we show that the proximal-gradient algorithm applied to the penalized problem, which naturally leads to distributed implementations, converges linearly up to a tolerance of the order of the centralized statistical error---the rate scales as $O(d)$, revealing an unavoidable speed-accuracy dilemma. Numerical results demonstrate the tightness of the derived sample rate and convergence rate scalings.

We study linear regression from data distributed over a network of agents (with no server node) by means of LASSO estimation, in high-dimension, which allows the ambient dimension to grow faster than the sample size. While there is a vast literature of distributed algorithms applicable to the problem, statistical and computational guarantees of most of them remain unclear in high dimension. This paper provides a first statistical study of the Distributed Gradient Descent (DGD) in the Adapt-Then-Combine (ATC) form. Our theory shows that, under standard notions of restricted strong convexity and smoothness of the loss functions–which hold with high probability for standard data generation models–suitable conditions on the network connectivity and algorithm tuning, DGD-ATC converges globally at a linear rate to an estimate that is within thecentralizedstatistical precision of the model. In the worst-case scenario, the total number of communications to statistical optimality grows logarithmically with the ambient dimension, which improves on the communication complexity of DGD in the Combine-Then-Adapt (CTA) form, scaling linearly with the dimension. This reveals that mixing gradient information among agents, as DGD-ATC does, is critical in high-dimensions to obtain favorable rate scalings.

We develop a general framework unifying several gradient-based stochastic optimization methods for empirical risk minimization problems both in centralized and distributed scenarios. The framework hinges on the introduction of an augmented graph consisting of nodes modeling the samples and edges modeling both the inter-device communication and intra-device stochastic gradient computation. By designing properly the topology of the augmented graph, we are able to recover as special cases the renowned Local-SGD and DSGD algorithms, and provide a unified perspective for variance-reduction (VR) and gradient-tracking (GT) methods such as SAGA, Local-SVRG and GT-SAGA. We also provide a unified convergence analysis for smooth and (strongly) convex objectives relying on a proper structured Lyapunov function, and the obtained rate can recover the best known results for many existing algorithms. The rate results further reveal that VR and GT methods can effectively eliminate data heterogeneity within and across devices, respectively, enabling the exact convergence of the algorithm to the optimal solution. Numerical experiments confirm the findings in this paper.

This paper proposes a novel family of primal-dual-based distributed algorithms for smooth, convex, multi-agent optimization over networks that uses only gradient information and gossip communications. The algorithms can also employ acceleration on the computation and communications. We provide a unified analysis of their convergence rate, measured in terms of the Bregman distance associated to the saddle point reformation of the distributed optimization problem. When acceleration is employed, the rate is shown to be optimal, in the sense that it matches (under the proposed metric) existing complexity lower bounds of distributed algorithms applicable to such a class of problem and using only gradient information and gossip communications. Preliminary numerical results on distributed least-square regression problems show that the proposed algorithm compares favorably on existing distributed schemes.

In this paper, intelligent reflecting surfaces (IRSs) are employed to enhance the physical layer security in a challenging radio environment. In particular, a multi-antenna access point (AP) has to serve multiple single-antenna legitimate users, which do not have line-of-sight communication links, in the presence of multiple multi-antenna potential eavesdroppers whose channel state information (CSI) is not perfectly known. Artificial noise (AN) is transmitted from the AP to deliberately impair the eavesdropping channels for security provisioning. We investigate the joint design of the beamformers and AN covariance matrix at the AP and the phase shifters at the IRSs for maximization of the system sum-rate while limiting the maximum information leakage to the potential eavesdroppers. To this end, we formulate a robust non-convex optimization problem taking into account the impact of the imperfect CSI of the eavesdropping channels. To address the non-convexity of the optimization problem, an efficient algorithm is developed by capitalizing on alternating optimization, a penalty-based approach, successive convex approximation, and semidefinite relaxation. Simulation results show that IRSs can significantly improve the system secrecy performance compared to conventional architectures without IRS. Furthermore, our results unveil that, for physical layer security, uniformly distributing the reflecting elements among multiple IRSs is preferable over deploying them at a single IRS.

This paper studies Dictionary Learning problems wherein the learning task is distributed over a multi-agent network, modeled as a time-varying directed graph. This formulation is relevant, for instance, in Big Data scenarios where massive amounts of data are collected/stored in different locations (e.g., sensors, clouds) and aggregating and/or processing all data in a fusion center might be inefficient or unfeasible, due to resource limitations, communication overheads or privacy issues. We develop a unified decentralized algorithmic framework for this class of nonconvex problems, which is proved to converge to stationary solutions at a sublinear rate. The new method hinges on Successive Convex Approximation techniques, coupled with a decentralized tracking mechanism aiming at locally estimating the gradient of the smooth part of the sum-utility. To the best of our knowledge, this is the first provably convergent decentralized algorithm for Dictionary Learning and, more generally, bi-convex problems over (time-varying) (di)graphs.

The paper studies a general class of distributed dictionary learning (DL) problems where the learning task is distributed over a multi-agent network with (possibly) time-varying (non-symmetric) connectivity. This setting is relevant, for instance, in scenarios where massive amounts of data are not collocated but collected/stored in different spatial locations. We develop a unified distributed algorithmic framework for this class of non-convex problems and establish its asymptotic convergence. The new method hinges on Successive Convex Approximation (SCA) techniques while leveraging a novel broadcast protocol to disseminate information and distribute the computation over the network, which neither requires the double-stochasticity of the consensus matrices nor the knowledge of the graph sequence to implement. To the best of our knowledge, this is the first distributed scheme with provable convergence for DL (and more generally bi-convex) problems, over (time-varying) digraphs.

We consider a non-convex constrained Lagrangian formulation of a fundamental bi-criteria optimization problem for variable selection in statistical learning; the two criteria are a smooth (possibly) non-convex loss function, measuring the fitness of the model to data, and the latter function is a difference-of-convex (DC) regularization, employed to promote some extra structure on the solution, like sparsity. This general class of nonconvex problems arises in many big-data applications, from statistical machine learning to physical sciences and engineering. We develop the first unified distributed algorithmic framework for these problems and establish its asymptotic convergence to d-stationary solutions. Two key features of the method are: i) it can be implemented on arbitrary networks (digraphs) with (possibly) time-varying connectivity; and ii) it does not require the restrictive assumption that the (sub)gradient of the objective function is bounded, which enlarges significantly the class of statistical learning problems that can be solved with convergence guarantees.

The problem of estimating sparse eigenvectors of a symmetric matrix attracts a lot of attention in many applications, especially those with high dimensional data set. While classical eigenvectors can be obtained as the solution of a maximization problem, existing approaches formulated this problem by adding a penalty term into the objective function that encourages a sparse solution. Nevertheless, the resulting methods achieve sparsity at a sacrifice of the orthogonality property. In this paper, we develop a new method to estimate dominant sparse eigenvectors without trading off their orthogonality. The problem is highly non-convex and too hard to handle. We apply the minorization-maximization (MM) framework where we iteratively maximize a tight lower bound (surrogate function) of the objective function over the Stiefel manifold. The inner maximization problem turns out to be the rectangular Procrustes problem, which has a closed-form solution. Numerical experiments show that the propose method matches or outperforms existing algorithms in terms of recovery probability and explained variance.

In this paper, we consider the robust covariance estimation problem in the non-Gaussian set-up. In particular, Tyler's M-estimator is adopted for samples drawn from a heavy-tailed elliptical distribution. For some applications, the covariance matrix naturally possesses certain structure. Therefore, incorporating the prior structure information in the estimation procedure is beneficial to improving estimation accuracy. The problem is formulated as a constrained minimization of the Tyler's cost function, where the structure is characterized by the constraint set. A numerical algorithm based on majorization-minimization is derived for general structures that can be characterized as a convex set, where a sequence of convex programming is solved. For the set of matrices that can be decomposed as the sum of rank one positive semidefinite matrices, which has a wide range of applications, the algorithm is modified with much lower complexity. Simulation results demonstrate that the proposed structure-constrained Tyler's estimator achieves smaller estimation error than the unconstrained case.