This paper explores the cubic-regularized Newton method within a federated learning framework while addressing two major concerns: privacy leakage and communication bottlenecks. We propose the Differentially Private Federated Cubic Regularized Newton (DP-FCRN) algorithm, which leverages second-order techniques to achieve lower iteration complexity than first-order methods. We incorporate noise perturbation during local computations to ensure privacy. Furthermore, we employ sparsification in uplink transmission, which not only reduces the communication costs but also amplifies the privacy guarantee. Specifically, this approach reduces the necessary noise intensity without compromising privacy protection. We analyze the convergence properties of our algorithm and establish the privacy guarantee. Finally, we validate the effectiveness of the proposed algorithm through experiments on a benchmark dataset.

In this work, we propose a continuous-time distributed optimization algorithm with guaranteed zero coupling constraint violation and apply it to safe distributed control in the presence of multiple control barrier functions (CBFs). The optimization problem is defined over a network that collectively minimizes a separable cost function with coupled linear constraints. An equivalent optimization problem with auxiliary decision variables and a decoupling structure is proposed. A sensitivity analysis demonstrates that the subgradient information can be computed using local information. This then leads to a subgradient algorithm for updating the auxiliary variables. A case with sparse coupling constraints is further considered, and it is shown to have better memory and communication efficiency. For the specific case of a CBF-induced time-varying quadratic program (QP), an update law is proposed that achieves finite-time convergence. Numerical results involving a static resource allocation problem and a safe coordination problem for a multiagent system demonstrate the efficiency and effectiveness of our proposed algorithms.

This work studies the distributed empirical risk minimization (ERM) problem under differential privacy (DP) constraint. Standard distributed algorithms achieve DP typically by perturbing all local subgradients with noise, leading to significantly degenerated utility. To tackle this issue, we develop a class of private distributed dual averaging (DDA) algorithms, which activates a fraction of nodes to perform optimization. Such subsampling procedure provably amplifies the DP guarantee, thereby achieving an equivalent level of DP with reduced noise. We prove that the proposed algorithms have utility loss comparable to centralized private algorithms for both general and strongly convex problems. When removing the noise, our algorithm attains the optimal O(1/t) convergence for non-smooth stochastic optimization. Finally, experimental results on two benchmark datasets are given to verify the effectiveness of the proposed algorithms.

Byzantine machine learning has garnered considerable attention in light of the unpredictable faults that can occur in large-scale distributed learning systems. The key to secure resilience against Byzantine machines in distributed learning is resilient aggregation mechanisms. Although abundant resilient aggregation rules have been proposed, they are designed in ad-hoc manners, imposing extra barriers on comparing, analyzing, and improving the rules across performance criteria. This paper studies near-optimal aggregation rules using clustering in the presence of outliers. Our outlier-robust clustering approach utilizes geometric properties of the update vectors provided by workers. Our analysis show that constant approximations to the 1-center and 1-mean clustering problems with outliers provide near-optimal resilient aggregators for metric-based criteria, which have been proven to be crucial in the homogeneous and heterogeneous cases respectively. In addition, we discuss two contradicting types of attacks under which no single aggregation rule is guaranteed to improve upon the naive average. Based on the discussion, we propose a two-phase resilient aggregation framework. We run experiments for image classification using a non-convex loss function. The proposed algorithms outperform previously known aggregation rules by a large margin with both homogeneous and heterogeneous data distributions among non-faulty workers. Code and appendix are available at https://github.com/jerry907/AAAI24-RASHB.

We propose a delay-agnostic asynchronous coordinate update algorithm (DEGAS) for computing operator fixed points, with applications to asynchronous optimization. DEGAS includes novel asynchronous variants of ADMM and block-coordinate descent as special cases. We prove that DEGAS converges with both bounded and unbounded delays under delay-free parameter conditions. We also validate by theory and experiments that DEGAS adapts well to the actual delays. The effectiveness of DEGAS is demonstrated by numerical experiments on classification problems.

Existing asynchronous distributed optimization algorithms often use diminishing step-sizes that cause slow practical convergence, or fixed step-sizes that depend on an assumed upper bound of delays. Not only is such a delay bound hard to obtain in advance, but it is also large and therefore results in unnecessarily slow convergence. This paper develops asynchronous versions of two distributed algorithms, DGD and DGD-ATC, for solving consensus optimization problems over undirected networks. In contrast to alternatives, our algorithms can converge to the fixed point set of their synchronous counterparts using step-sizes that are independent of the delays. We establish convergence guarantees under both partial and total asynchrony. The practical performance of our algorithms is demonstrated by numerical experiments.

For large-scale cyber-physical systems, the collaboration of spatially distributed sensors is often needed to perform the state estimation process. Privacy concerns naturally arise from disclosing sensitive measurement signals to a cloud estimator that predicts the system state. To solve this issue, we propose a differentially private set-based estimation protocol that preserves the privacy of the measurement signals. Compared to existing research, our approach achieves less privacy loss and utility loss using a numerically optimized truncated noise distribution. The proposed estimator is perturbed by weaker noise than the analytical approaches in the literature to guarantee the same level of privacy, therefore improving the estimation utility. Numerical and comparison experiments with truncated Laplace noise are presented to support our approach. Zonotopes, a less conservative form of set representation, are used to represent estimation sets, giving set operations a computational advantage. The privacy-preserving noise anonymizes the centers of these estimated zonotopes, concealing the precise positions of the estimated zonotopes.

This work studies the distributed nonconvex optimization problem in bandwidth-limited communication environments. We develop a communication-efficient algorithm based on the gradient-tracking based distributed optimization method, where each computation node is equipped with a new event-triggered communication scheduler. Such scheduler approves the broadcasting only when the innovation of exchanged variables exceeds the change of decision variables in two consecutive updates. Compared to the conventional scheduler with time-dependent vanishing thresholds, the proposed one adapts better to the optimization dynamics and thus leads to more significant communication reduction. Finally, we prove the convergence of the algorithm and illustrate its performance via numerical examples.

This work studies nonconvex distributed constrained optimization over stochastic communication networks. We revisit the distributed dual averaging algorithm, which is known to converge for convex problems. We start from the centralized case, for which the change of two consecutive updates is taken as the suboptimality measure. We validate the use of such a measure by showing that it is closely related to stationarity. This equips us with a handle to study the convergence of dual averaging in nonconvex optimization. We prove that the squared norm of this suboptimality measure converges at rate O(1/t). Then, for the distributed setup we show convergence to the stationary point at rate O(1/t). Finally, a numerical example is given to illustrate our theoretical results.

This article addresses the distributed optimization problem in the presence of malicious adversaries that can move within the network and induce faulty behaviors in the attacked nodes. We first investigate the vulnerabilities of a consensus-based secure distributed optimization protocol under mobile adversaries. Then, a modified resilient distributed optimization algorithm is proposed. We develop conditions on the network structure for both complete and non-complete directed graph cases, under which the proposed algorithm guarantees that the estimates by regular nodes converge to the convex combination of the minimizers of their local functions. Simulations are carried out to verify the effectiveness of our approach.