Distributed optimization with applications to sensor networks and machine learning

This dissertation deals with developing optimization algorithms which can be distributed over a network of computational nodes. Specifically we develop distributed algorithms for the special class when the optimization problem of interest has a separable structure. In this case the objective function can be written as a sum of local convex objective functions. Each computational node has knowledge of its own local objective function and its local constraint set and needs to cooperatively solve the optimization problem under this information constraint. Furthermore we consider the case when the communication topology of the nodes is dynamic in nature. Recently, there has been a lot of interest in the so called ``consensus'' algorithms which has been shown to be remarkable robust to dynamic communication topology. Our algorithms leverage the robustness properties of consensus algorithm to compute the optimal solution in a distributed manner. We propose algorithms which have guaranteed convergence behavior in the presence of various forms of perturbations like communication noise, stochastic subgradient errors and stochastic communication topologies. This enables our algorithms to be useful in a wide class of application areas in sensor networks and machine learning. Specifically the consideration of stochastic subgradient errors enable our algorithms to be useful in an online setting, when the algorithm operates on streaming data. We adapt our algorithms for the binary classification problem in the support vector machine setting and show the behavior over a sample data set. We further develop distributed algorithms for the min-max problem in a network. This formulation doesn't readily fit the separable structure of the objective function discussed earlier. We develop an exact penalty based approach and an approach based on primal-dual iterative schemes. We show the applicability of the algorithms on a power allocation problem in cellular networks.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Systems & Entrepreneurial Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2012

Author dc:creator

• Srivastava, Kunal

Contributors dc:contributor

• Nedich, Angelia
• Stipanović, Dušan M.
• Kumar, P.R.
• Sreenivas, Ramavarapu S.

• Distributed Optimization
• Consensus Algorithms
• Machine Learning

Statement dc:rights

• Copyright 2011 Kunal Srivastava

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/29504

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/29504