Browsing by Subject "Distributed optimization"

Zeroth-Order (ZO) methods have been applied to solve black-box or simulation-based optimization prroblems. These problems arise in many important applications nowa- days, e.g., generating adversarial attacks on machine learning systems, learning to control the system with complicated physics structure or human in the loop. In these problem settings, the objective function to optimize does not have an explicit math- ematical form and therefore its gradient cannot be obtained. This invalidates all gradient-based optimization approaches. On the other hand, ZO methods approxi- mate the gradient by using the objective function values. Many existing ZO methods adopt the two-point feedback scheme to approximate the unknown gradient due to its low estimation variance and fast convergence speed. Specifically, two-point ZO method estimates the gradient at the current iterate of the algorithm by querying the objective function value twice at two distinct neighbor points around the current iterate. Such scheme becomes infeasible or difficult to implement when the objective function is time-varying, or when multiple agents collaboratively optimize a global objective function that depends on all agents’ decisions, because the value of the objective function can be queried only once at a single decision point. However, con- ventional ZO method based on one-point feedback is subject to large variance of the gradient estimation and therefore slows down the convergence.

In this dissertation, we propose a novel one-point ZO method based on the residual feedback. Specifically, the residual feedback scheme estimates the gradient using the residual between the values of the objective function at two consecutive iterates of the algorithm. When optimizing a deterministic Lipschitz function, we show that the query complexity of ZO with the proposed one-point residual feedback matches that of ZO with the existing two-point schemes. Moreover, the query complexity of the proposed algorithm can be improved when the objective function has Lipschitz gradient. Then, for stochastic bandit optimization problems, we show that ZO with one-point residual feedback achieves the same convergence rate as that of two-point scheme with uncontrollable data samples.

Next, we apply the proposed one-point residual-feedback gradient estimator to solve online optimizaiton problems, where the objective function varies over time. In the online setting, since each objective function can only be evaluated once at a single decision point, existing two-point ZO methods are not feasible and only one-point ZO methods can be used. We develop regret bounds for ZO with the proposed one- point residual feedback scheme for both convex and nonconvex online optimization problems. Specifically, for both deterministic and stochastic problems and for both Lipschitz and smooth objective functions, we show that using residual feedback can produce gradient estimates with much smaller variance compared to conventional one- point feedback methods. As a result, our regret bounds are much tighter compared to existing regret bounds for ZO with conventional one-point feedback, which suggests that ZO with residual feedback can better track the optimizer of online optimization problems. Additionally, our regret bounds rely on weaker assumptions than those used in conventional one-point feedback methods.

The proposed residual-feedback scheme is next decentralized to conduct dis- tributed policy optimization in the multi-agent reinforcement learning (MARL) prob- lems. Existing MARL algorithms often assume that every agent can observe the states and actions of all the other agents in the network. This can be impractical in large-scale problems, where sharing the state and action information with multi-hop neighbors may incur significant communication overhead. The advantage of the pro- posed zeroth-order policy optimization method is that it allows the agents to compute the local policy gradients needed to update their local policy functions using local estimates of the global accumulated rewards that depend on partial state and action information only and can be obtained using consensus. Specifically, the local ZO policy gradients relying on one-point residual-feedback significantly reduces the vari- ance of the local policy gradient estimates compared to the conventional one-point policy gradient estimates, improving, in this way, the learning performance. We show that the proposed distributed zeroth-order policy optimization method with constant stepsize converges to a neighborhood of the global optimal policy that depends on the number of consensus steps used to calculate the local estimates of the global accumulated rewards.Another challenge in the distributed ZO optimization problems is that the agents may conduct local updates in an asynchronous fashion when they do not have ac- cess to a global clock. To deal with this challenge, we propose an asynchronous zeroth-order distributed optimization method that relies on the proposed one-point residual feedback gradient estimator. We show that this estimator is unbiased under asynchronous updating, and theoretically analyze its convergence. We demonstrate the effectiveness of all proposed algorithms via extensive numerical experiments.

Distributed optimization methods allow us to decompose an optimization problem

into smaller, more manageable subproblems that are solved in parallel. For this

reason, they are widely used to solve large-scale problems arising in areas as diverse

as wireless communications, optimal control, machine learning, artificial intelligence,

computational biology, finance and statistics, to name a few. Moreover, distributed

algorithms avoid the cost and fragility associated with centralized coordination, and

provide better privacy for the autonomous decision makers. These are desirable

properties, especially in applications involving networked robotics, communication

or sensor networks, and power distribution systems.

In this thesis we propose the Accelerated Distributed Augmented Lagrangians

(ADAL) algorithm, a novel decomposition method for convex optimization prob-

lems with certain separability structure. The method is based on the augmented

Lagrangian framework and addresses problems that involve multiple agents optimiz-

ing a separable convex objective function subject to convex local constraints and

linear coupling constraints. We establish the convergence of ADAL and also show

that it has a worst-case O(1/k) convergence rate, where k denotes the number of

iterations.

Moreover, we show that ADAL converges to a local minimum of the problem

for cases with non-convex objective functions. This is the first published work that

formally establishes the convergence of a distributed augmented Lagrangian method

ivfor non-convex optimization problems. An alternative way to select the stepsizes

used in the algorithm is also discussed. These two contributions are independent

from each other, meaning that convergence of the non-convex ADAL method can

still be shown using the stepsizes from the convex case, and, similarly, convergence

of the convex ADAL method can be shown using the stepsizes proposed in the non-

convex proof.

Furthermore, we consider cases where the distributed algorithm needs to operate

in the presence of uncertainty and noise and show that the generated sequences of

primal and dual variables converge to their respective optimal sets almost surely. In

particular, we are concerned with scenarios where: i) the local computation steps

are inexact or are performed in the presence of uncertainty, and ii) the message

exchanges between agents are corrupted by noise. In this case, the proposed scheme

can be classified as a distributed stochastic approximation method. Compared to

existing literature in this area, our work is the first that utilizes the augmented

Lagrangian framework. Moreover, the method allows us to solve a richer class of

problems as compared to existing methods on distributed stochastic approximation

that consider only consensus constraints.

Extensive numerical experiments have been carried out in an effort to validate

the novelty and effectiveness of the proposed method in all the areas of the afore-

mentioned theoretical contributions. We examine problems in convex, non-convex,

and stochastic settings where uncertainties and noise affect the execution of the al-

gorithm. For the convex cases, we present applications of ADAL to certain popular

network optimization problems, as well as to a two-stage stochastic optimization

problem. The simulation results suggest that the proposed method outperforms

the state-of-the-art distributed augmented Lagrangian methods that are known in

the literature. For the non-convex cases, we perform simulations on certain simple

non-convex problems to establish that ADAL indeed converges to non-trivial local

vsolutions of the problems; in comparison, the straightforward implementation of the

other distributed augmented Lagrangian methods on the same problems does not

lead to convergence. For the stochastic setting, we present simulation results of

ADAL applied on network optimization problems and examine the effect that noise

and uncertainties have in the convergence behavior of the method.

As an extended and more involved application, we also consider the problem

of relay cooperative beamforming in wireless communications systems. Specifically,

we study the scenario of a multi-cluster network, in which each cluster contains

multiple single-antenna source destination pairs that communicate simultaneously

over the same channel. The communications are supported by cooperating amplify-

and-forward relays, which perform beamforming. Since the emerging problem is non-

convex, we propose an approximate convex reformulation. Based on ADAL, we also

discuss two different ways to obtain a distributed solution that allows for autonomous

computation of the optimal beamforming decisions by each cluster, while taking into

account intra- and inter-cluster interference effects.

Our goal in this thesis is to advance the state-of-the-art in distributed optimization by proposing methods that combine fast convergence, wide applicability, ease

of implementation, low computational complexity, and are robust with respect to

delays, uncertainty in the problem parameters, noise corruption in the message ex-

changes, and inexact computations.