SILO



The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group

3M

with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Using a New Nonconvex Singular Value Regularizer in Multivariate Linear Regression | Traffic-Redundancy Aware Network Design

Hongbo Dong | Sid Barman, Post-doc in WID and graduate student in CS

Date and Time: Feb 08, 2012 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building

Abstract:

*** Hongbo's talk:
Title: Using a New Nonconvex Singular Value Regularizer in Multivariate Linear Regression.
Abstract:
We introduce the weighted singlar value penalization, which uses a nonconvex nonseparable
regularizer. We show that in spite of the nonconvexity, one optimization problem with this regularizer is efficiently solvable. Applied to Multivariate Linear Regression, we develop a new estimator for simultaneous dimension reduction and coefficient estimation. We prove the rank consistency and establish prediction and estimation performance bounds for our estimator. Advantages of our estimator are demonstrated by extensive simulation studies and an application in genetics. I will also discuss a variant of our optimization result that is applicable to sparse optimization.

*** Sid's talk
Title: Traffic-Redundancy Aware Network Design

Abstract:
We consider network design problems for information networks where routers can replicate data but
cannot alter it. This functionality allows the network to eliminate data-redundancy in traffic, thereby
saving on routing costs. We consider two problems within this framework and design approximation
algorithms.
The first problem we study is the traffic-redundancy aware network design (RAND) problem. We
are given a weighted graph over a single server and many clients. The server owns a number of different
data packets and each client desires a subset of the packets; the client demand sets form a laminar set
system. Our goal is to connect every client to the source via a single path, such that the collective cost
of the resulting network is minimized. Here the transportation cost over an edge is its weight times
times the number of distinct packets that it carries.
The second problem is a facility location problem that we call RAFL. Here the goal is to find an
assignment from clients to facilities such that the total cost of routing packets from the facilities to
clients (along unshared paths), plus the total cost of producing one copy of each desired packet at
each facility is minimized.
We present a constant factor approximation for the RAFL and an O(log P) approximation for
RAND, where P is the total number of distinct packets. We remark that P is always at most the
number of different demand sets desired or the number of clients, and is generally much smaller.

This is joint work with Shuchi Chawla.