Privacy-Preserving Distributed Online Mirror Descent for Nonconvex Optimization
Yingjie Zhou, Tao Li · 2025
Read Privacy-Preserving Distributed Online Mirror Descent for Nonconvex Optimization by Yingjie Zhou, Tao Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-04222.txt.
Introduction
Teams that split a math task across many nodes may also need to keep each node's data private. Yingjie Zhou and Tao Li build a private, split solving method for rough tasks in work from twenty twenty-five. Past work stuck to smooth tasks, which are easier. Their method bends each step through a mirror map and adds tuned noise for privacy.
Proofs show that on a well-linked web of nodes, the right step size keeps privacy at each time tick. When the local costs are smooth enough, the total miss over time grows slower than time itself, a sound rate. Test runs on fake data backed the claims. The work widens private split solving to the rough tasks that real teams meet.
Catalog record
| CREATOR | Yingjie Zhou, Tao Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-04222
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Privacy-Preserving Distributed Online Mirror Descent for Nonconvex Optimization Yingjie Zhou, Tao Li Abstract We investigate the distributed online nonconvex optimization problem with differential privacy over time-varying networks. Each node minimizes the sum of several nonconvex functions while preserving the node’s differential privacy. We propose a privacy-preserving distributed online mirror descent algorithm for nonconvex optimization, which uses the mirror descent to update decision variables and the Laplace differential privacy mechanism to protect privacy. Unlike the existing works, the proposed algorithm allows the cost functions to be nonconvex, which is more applicable. Based upon these, we prove that if the communication network is B B -strongly connected and the constraint set is compact, then by choosing the step size properly, the algorithm guarantees ϵ \epsilon -differential privacy at each time. Furthermore, we prove that if the local cost functions are β \beta -smooth, then the regret over time horizon T T grows sublinearly while preserving differential privacy, with an upper bound O ( T ) O(\sqrt{T}) . Finally, the effectiveness of the algorithm is demonstrated through numerical simulations. Journal: Systems & Control Letters 1 Introduction In distributed optimization, each node is aware of its local cost function. Nodes exchange information with their neighboring nodes through a communication network and collaborate to optimize the global cost function. This collaboration results in convergence towards the global optimal solution, where the global cost function is the sum of the local cost functions of all nodes. In numerous practical scenarios, each node’s local cost function varies over time which leads to distributed online optimization problems. Distributed online optimization problems have wide applications in signal processing ( [ 1 ] ), economic dispatch ( [ 2 ] ), and sensor networks ( [ 3 ] ) et al. The regret is commonly used to evaluate the performance of a distributed online optimization algorithm. If the regret grows sublinearly, then the algorithm is effective. The existing works show that if the cost function is convex, then the best regret bound achieved by an algorithm is O(\sqrt{T}) , and if the cost function is strongly convex, then the best regret bound is O(\ln(T)) , where T denotes the time horizon ( [ 4 , 5 ] ). In recent years, distributed online optimization problems have been extensively studied ( [ 6 , 7 , 8 , 9 ] ). The algorithms above are designed based on the Euclidean distance. Such algorithms often face challenges in computing projections for complex cost functions and constraint sets, e.g. problems with simplex constraints. Beck et al. ( [ 10 ] ) proposed the mirror descent algorithm based on the Bregman distance instead of the Euclidean distance, which effectively improves the computational efficiency. The mirror descent algorithm is highly effective for handling large-scale optimization problems ( [ 11 ] ), and numerous studies have focused on extending this algorithm to distributed settings ( [ 12 , 13 ] ). In distributed algorithms, each node possesses a data set containing its private information. By collecting the information exchanged between nodes, attackers could potentially deduce the data sets of the nodes, leading to privacy leakage. To protect private information, an effective approach is the differential privacy mechanism proposed by Dwork et al. ( [ 14 ] ). The fundamental principle of the differential privacy mechanism is to add a certain level of noises to the communication, thereby ensuring that attackers can only obtain limited privacy information from their observations. Recently, extensive works have been proposed for distributed online convex optimization problems with differential privacy ( [ 15 , 16 , 17 , 18 , 19 , 20 , 21 ] ). Yuan et al. ( [ 15 ] ) proposed a privacy-preserving distributed online optimization algorithm based on the mirror descent. For a fixed graph, they proved that if the cost function is strongly convex, then the regret bound of the algorithm is the same as that without differential privacy, which is O(\ln{(T)}) . Zhao et al. ( [ 16 ] ) proposed a distributed online optimization algorithm with differential privacy based on one-point residual feedback. They proved that, even if the gradient information of the cost function is unknown, the algorithm can still achieve differential privacy and the regret of the algorithm grows sublinearly. For constrained optimization problems, Lü et al. ( [ 17 ] ) introduced an efficient privacy-preserving distributed online dual averaging algorithm by using the gradient rescaling strategy. Li et al. ( [ 18 ] ) proposed a framework for differentially private distributed optimization. For time-varying communication graphs, they obtained the regrets bounds O(\sqrt{T}) and O(\ln{(T)}) for convex and strongly convex cost functions, respectively. Zhu et al. ( [ 19 ] ) proposed a differentially private distributed stochastic subgradient online convex optimization algorithm based on weight balancing over time-varying directed networks. They demonstrated that the algorithm ensures \epsilon -differential privacy and provided the regret bound of the algorithm. The aforementioned privacy-preserving distributed online optimization algorithms all address the cases of convex cost functions. However, in practical applications, many problems involve nonconvex cost functions. For example, in machine learning, the cost function may be nonconvex due to sparsity and low-rank constraints ( [ 22 ] ). In wireless communication, energy efficiency problems may also involve nonconvex cost functions due to constraints on node transmission power ( [ 23 ] ). Since the cost function is nonconvex, finding a global minimizer is challenging. Therefore, the regret for convex optimization cannot be used to measure the performance of nonconvex online algorithms. For nonconvex optimization, the goal is usually to find a point that satisfies the first-order optimality condition ( [ 24 , 25 , 26 , 27 ] ). They used the regret based on the first-order optimality condition to evaluate the performance of the algorithm. Under appropriate assumptions, they proved that the regret grows sublinearly. The privacy-preserving distributed online nonconvex optimization problems have wide applications in practical engineering fields, such as distributed target tracking. Up to now, the studies on privacy-preserving distributed nonconvex optimization have been restricted to offline settings ( [ 28 , 29 ] ). In [ 28 ] , a new algorithm for decentralized nonconvex optimization was proposed, which can enable both rigorous differential privacy and convergence. Compared with the existing works, the main challenges for privacy-preserving distributed online nonconvex optimization are as follows. The first challenge is ensuring the convergence of the algorithm with the differential privacy mechanism. Existing works on distributed online nonconvex optimization do not incorporate privacy protection, and adding noises to decision variables may lead to divergence for differential privacy in distributed online optimization algorithms. The second challenge is improving the computational efficiency of online algorithms. For online optimizations, computational resources are limited, and the immediate decision-making is required. Compared with [ 28 ] , which addressed unconstrained optimization problems, we focus on optimization problems with set constraints, making the solution process more difficult and the computational cost higher. The algorithm in [ 28 ] is based on the gradient descent. For constrained optimization problems, directly incorporating Euclidean projection into the algorithm given in [ 28 ] may lead to high computational costs. Motivated by selecting Bregman projections based on different constraint conditions can improve computational