Distributed optimization with applications to sensor networks and machine learning

Srivastava, Kunal

Permalink

https://hdl.handle.net/2142/29504 Copy

Description

Title

Distributed optimization with applications to sensor networks and machine learning

Author(s)

Srivastava, Kunal

Issue Date

2012-02-01T00:49:42Z

Director of Research (if dissertation) or Advisor (if thesis)

• Nedich, Angelia
• Stipanović, Dušan M.

Doctoral Committee Chair(s)

Nedich, Angelia

Committee Member(s)

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

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Systems & Entrepreneurial Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Distributed Optimization
• Consensus Algorithms
• Machine Learning

Abstract

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.

Graduation Semester

2011-12

Permalink

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

Copyright and License Information

Copyright 2011 Kunal Srivastava

Owning Collections