Source-linked AI summary
Non-Convex Distributed Optimization
Tatiana Tatarenko, Behrouz Touri
TL;DR
The paper studies distributed minimization of a sum of non-convex local functions over time-varying networks. It analyzes deterministic and perturbed push-sum dynamics, proving convergence to critical points and, under additional conditions, almost-sure convergence toward local minima. The paper also reports an O(1/t) convergence rate for the noised procedure.
Problem
Distributed optimization needs methods for non-convex sums over time-varying networks, where agents access only local functions and communicate locally.
Method
The paper combines push-sum consensus with local gradient descent and adds random perturbations to the update process.
Results
The deterministic dynamics converge to critical points, while the perturbed dynamics converge almost surely to local minima under the stated assumptions.
Takeaways & Limitations
Perturbations address the inability of deterministic gradient dynamics to distinguish local minima from local maxima and support local-minimum search.
Takeaways & Limitations
Without second-order derivative assumptions, the procedure can converge to a local minimum or a saddle point; the local-minimum guarantee also requires the stated assumptions and absence of saddle points.
Abstract
from arXiv · showhide
We study distributed non-convex optimization on a time-varying multi-agent network. Each node has access to its own smooth local cost function, and the collective goal is to minimize the sum of these functions. We generalize the results obtained previously to the case of non-convex functions. Under some additional technical assumptions on the gradients we prove the convergence of the distributed push-sum algorithm to some critical point of the objective function. By utilizing perturbations on the update process, we show the almost sure convergence of the perturbed dynamics to a local minimum of the global objective function. Our analysis shows that this noised procedure converges at a rate of $O(1/t)$.
1 Introduction
The paper addresses distributed non-convex optimization over time-varying networks, extending push-sum analysis beyond convex objectives. Perturbations are used to steer the dynamics toward local minima, while the deterministic method converges to critical points.
- Motivation: Distributed agents optimize a global objective using only local communication and local cost information.Applications include sensor control, signal processing, power control, routing, machine learning, opinion dynamics, and spectrum coordination.
- Motivation: Prior theory largely focused on sums of convex functions, despite applications requiring non-convex optimization.Non-convex resource allocation with non-elastic traffic is identified as one such application.
- Related work: Existing local-minimum guarantees required time-invariant communication, favorable initialization, and sufficiently small step sizes.The paper contrasts these restrictions with more general time-varying network settings.
- Approach: Push-sum combines consensus dynamics with local gradient descent and avoids requiring double-stochastic communication matrices.The paper studies its perturbed form over time-varying communication networks.
- Contributions: The paper proves convergence to critical points and shows that perturbations steer every node to a local minimum from any initial state.The analysis also studies the convergence rate of the stochastic procedure.
- Scope: Without second-order derivative assumptions, the procedure may converge to either a local minimum or a saddle point.This qualifies the deterministic or unperturbed convergence behavior.
2 Distributed Optimization Problem
The distributed problem uses a time-varying directed network in which each agent knows only its own local function. Agents seek to minimize the global sum under gradient and connectivity assumptions.
- Network model: At each time t, agent i communicates only with out-neighbors in a directed graph G(t).The graph has vertex set [n] and a time-varying edge set.
- Network model: The graph sequence is S-strongly connected when the union over every S-time interval is strongly connected.This assumption is used to ensure sufficient information mixing among agents.
- Network model: Each node knows its current out-degree and treats itself as both an in-neighbor and an out-neighbor.The notation distinguishes time-varying in- and out-neighborhoods and the out-degree d_i(t).
- Optimization objective: The agents’ goal is to solve the stated minimization problem distributively.The local function F_i is available only to agent i.
- Assumptions: Each local gradient is uniformly bounded by a finite constant α.The paper also assumes a solution exists and that the critical-point set has finitely many connected components.
3 Preliminaries
The preliminaries formulate stochastic recursive approximation and establish how push-sum perturbations track the network average. These results provide the basis for convergence analysis of deterministic and noisy distributed optimization.
- Stochastic approximation: The analysis models the dynamics as a d-dimensional non-autonomous nonlinear stochastic process.The process framework supports the later treatment of perturbed distributed optimization.
- Stochastic approximation: The recursive approximation has the form X(t + 1) = X(t) − a(t + 1)˜f(t, X(t)) − a(t + 1)W(t + 1).Here a(t) is a positive step size, while the drift includes f and q and W is a Markov noise sequence.
- Stochastic approximation: A Lyapunov-style generating operator measures the conditional change in V along the stochastic process.For deterministic dynamics, it reduces to the corresponding difference equation.
- Stochastic approximation: Under the theorem’s assumptions, the stochastic process converges almost surely to a zero of f or the boundary of a connected component of the zero set.The conditions include a finite connected-component structure and Lyapunov-type drift requirements.
- Push-sum preliminaries: Push-sum maintains vector states z_i(t), x_i(t), and w_i(t), a scalar y_i(t), and additive perturbations e_i(t).The perturbation can be deterministic or include independent zero-mean random vectors with bounded variance.
- Push-sum preliminaries: If the perturbations vanish asymptotically, every z_i(t) tracks the average state almost surely.This tracking result connects push-sum dynamics to the average gradient-descent behavior.
4 Main Results
The paper analyzes deterministic and perturbed push-sum methods for distributed non-convex optimization over S-strongly connected time-varying graphs. The deterministic process converges to critical points, while perturbations exclude non-minimizing critical points under additional assumptions.
- Deterministic Procedure: The deterministic push-sum process combines consensus updates with local gradient descent for distributed optimization.Each agent maintains vector and scalar variables, and the update uses local gradients evaluated at the agent states.
- Deterministic Procedure: Under Lipschitz gradients, coercivity, and square-summable step sizes, the average and agent states converge to a critical point or a connected-component boundary.The result assumes an S-strongly connected graph sequence and requires Σ a(t)^2 < ∞.
- Deterministic Procedure: Because gradients cannot distinguish critical-point types, the deterministic process does not by itself guarantee convergence to a local minimum.The paper identifies this as an inherent limitation of gradient-based optimization.
- Perturbed Procedure: Adding noise turns the perturbed push-sum dynamics into a Markov chain and enables exploration of unstable directions near non-local minima.The perturbation is motivated by simulated annealing and is applied to the local optimization step.
- Perturbed Procedure: Under Assumptions 1–5 and a suitable non-increasing step-size sequence, the perturbed states converge almost surely to local minima or a connected-component boundary from any initial states.The result applies to S-strongly connected graph sequences and uses a condition excluding non-minimizing critical points.
- Convergence Rate: When the objective has finitely many critical points and additional gradient assumptions hold, the perturbed process converges to the local-minimum set for sufficiently small constant step size.The theorem states that there exists α > 0 such that any 0 < a ≤ α yields convergence of the average and agent states to the local-minimum set.
5 Proof of the Main Results
The proofs establish convergence of deterministic and perturbed push-sum dynamics using stochastic-approximation arguments, Lipschitz gradients, Lyapunov functions, and connectivity assumptions. The perturbed process avoids non-minimizing critical points almost surely, while the deterministic process may converge to any critical point.
- Convergence analysis: The analysis uses Lipschitz gradients, step-size conditions, and S-strong connectivity to control consensus and perturbation errors.The proofs introduce a sequence c(t) bounding the error and require summability of a(t+1)c(t).
- Assumptions: The theorem assumes finitely many connected components of the critical-point and local-minimum sets, although this restriction is stated to simplify notation.The result can be generalized to finitely many connected components.
- Convergence analysis: A Lyapunov function V(x)=F(x)+C supplies the stochastic-approximation argument for convergence toward critical-point components.The constant C ensures positivity, while coercivity gives V(x)→∞ as ∥x∥→∞.
- Critical points: The deterministic process guarantees convergence to a zero of ∇F but cannot distinguish local minima, saddle points, and local maxima.The proof concludes convergence of the agents to the limiting average state under the stated assumptions.
- Perturbed dynamics: The perturbed process converges to critical points and, under the Markov-process avoidance result, assigns zero probability to convergence at non-minimizing points.The argument excludes the set of critical points that are not local minima, independently of the initial state.
- Perturbed dynamics: The local-minimum result assumes structural conditions near non-minimizing points and uses positive-definite matrices to establish their avoidance.The proof applies a theorem for Markov processes with i.i.d. random perturbations and local stability conditions.
6 Simulation Results
The simulation applies the perturbed push-sum algorithm to a three-agent, time-varying network optimizing a non-convex objective. From two initial conditions, the agents converge to the global or a local minimum rather than remaining at a nearby local maximum.
- Simulation setup: The example distributes three local functions across three agents and studies their sum over a randomly varying communication graph.The graph sequence is 4-strongly connected, and each agent knows only its own function.
- Simulation setup: The objective has no local minima outside z∈[-6,6], and the perturbed algorithm is applied under the stated assumptions.The construction extends the objective to satisfy the paper’s assumptions on the whole real line.
- Observed convergence: The algorithm converges almost surely to one of the local minima, z = -2.49 or z = 2.62.The two minima are the possible limiting points identified for the simulation.
- Observed convergence: From zero initial estimates, the agents converge to the global minimum z = 2.62.This trajectory is shown in Figures 2–4 for the three agent states.
- Observed convergence: From initial estimates near the local maximum z = -1.12, the agents instead converge to the local minimum z = -2.49.The second initialization uses x1(0) = -1, x2(0) = -1.2, and x3(0) = -1.1.
7 Discussions and Concluding Remarks
The deterministic push-sum procedure reaches critical points, while its stochastic perturbation reaches local minima almost surely under stated conditions. The analysis also identifies a path toward global-minimum methods and payoff-based extensions.
- The deterministic push-sum algorithm converges to a critical point of the global objective under assumptions on the objective’s gradient.
- The stochastic distributed procedure converges almost surely to a local minimum, or to a critical-set boundary, when saddle points are absent.
- The deterministic gradient procedure cannot distinguish between local maxima and local optima.
- Future work may modify the algorithm to approach global minima and develop a payoff-based version for optimal wind farm control.