3. N. Mastronarde and M.
van der Schaar, “Energy-efficient Delay-critical Communication in Unknown
Wireless Environments,” IEEE COMSOC MMTC E-Letter,
vol. 7, no. 8, pp. 8-11, Nov. 2012.
2.
J. Park and M. van der Schaar,
"A Note on the Intervention Framework". [Link]
1. F. Fu and M. van der Schaar, "Separation Principles for
Multimedia Delivery over Energy Efficient Networks," IEEE ComSoc MMTC
E-letter, Sept. 2010. [Link]
Theses
Onur Atan (Graduation Date: Sep 2018),
Title: Structured Learning and Decision-Making for Medical Informatics [Link] [Slides]
Abstract:
Clinicians are routinely faced with the practical challenge of integrating high-dimensional data in order to make the most appropriate clinical decision from a large set of possible actions for a given patient. Current clinical decisions continue to rely on clinical practice guidelines, which are aimed at a representative patient rather than an individual patient who may display other characteristics. Unfortunately, if it were necessary to learn everything from the limited medical data, the problem would be completely intractable because of the high-dimensional feature space and large number of medical decisions. My thesis aims to design and analyze algorithms that learn and exploit the structure in the medical data - for instance, structures among the features (relevance relations) or decisions (correlations). The proposed algorithms have much in common with the works in online and counterfactual learning literature but unique challenges in the medical informatics lead to numerous key differences from existing state of the art literature in Machine Learning (ML) and require key innovations to deal with large number of features and treatments, heterogeneity of the patients, sequential decision-making, and so on.
Yuanzhang Xiao (Graduation Date: May 2014),
Title: Optimal Sequential Resource Sharing and Exchange in Multi-Agent Systems [Link] [Slides]
Abstract:
Central to the design of many engineering systems and social networks is to solve the underlying resource sharing and exchange problems, in which multiple decentralized agents make sequential decisions over time to optimize some long-term performance metrics. It is challenging for the decentralized agents to make optimal sequential decisions because of the complicated coupling among the agents and across time. In this dissertation, we mainly focus on three important classes of multi-agent sequential resource sharing and exchange problems and derive optimal solutions to them.
First, we study multi-agent resource sharing with imperfect monitoring, in which self-interested agents have imperfect monitoring of the resource usage and inflict strong negative externality (i.e. strong interference and congestion) among
each other. Despite of the imperfect monitoring, the strong negative externality, and the self-interested agents, we propose an optimal, distributed, easy-to-implement resource sharing policy that achieves Pareto optimal outcomes at the
equilibrium. A key feature of the optimal resource sharing policy is that it is nonstationary, namely it makes decisions based on the history of past (imperfect) monitoring of the resource usages. The applications of our proposed design in
wireless spectrum sharing problems enable us to improve the spectrum e fficiency by up to 200% and achieve up to 90% energy saving, compared to state-of-the-art (stationary) spectrum sharing policies.
Second, we study multi-agent resource sharing with decentralized information, in which each agent has a private, independently and stochastically changing state (whose transition may depend on the agent's action), and the agents' actions are coupled through resource sharing constraints. Despite of the decentralized information (i.e. private states), we propose distributed resource sharing policies that achieve the social optimum, and apply the proposed policies to demand-side management in smart grids, and joint resource allocation and packet scheduling in wireless video transmissions. The proposed policies demonstrate significant performance gains over existing myopic policies that do not take into account the
state dynamics and the policies based on Lyapunov optimization that were proposed for single-agent problems.
Finally, we study multi-agent resource exchange with imperfect monitoring, in which self-interested, anonymous agents exchange services (e.g. task solving in crowdsourcing platforms, file sharing in peer-to-peer networks, answering in
question-and-answer forums). Due to the anonymity of the agents and the lack of fixed partners, free-riding is prevalent, and can be addressed by rating protocols. We propose the first rating protocol that can achieve the social optimum at the
equilibrium under imperfect monitoring of the service quality. A key feature of the optimal rating protocol is again that it is nonstationary, namely it recommends desirable behaviors based on the history of past rating distributions of the agents.
Yu
Zhang (Graduation Date: May 2013),
Title: System and Incentive Design in Socio-technical
Networks [Link] [Slides]
Abstract:
Socio-technical networks (e.g. social networking services, peer-to-peer systems, etc.)
provide a popular, cost-effective and scalable framework for sharing user-generated resources
or services. Achieving resource sharing efficiency in socio-technical networks is a challenging
problem, because the information available about the various resources is decentralized and it
is changing dynamically; the agents may be heterogeneous and have different learning abilities;
the agents may make proactive decisions on link formation; and most importantly, the agents may
be self-interested, i.e. they take actions which maximize their individual utilities rather than
the collective social welfare and thus choose to free-ride rather than share their resources..
The overarching goal of my dissertation is to develop a rigorous and unified paradigm for the
joint design of efficient incentive mechanisms and resource management schemes in socio-technical
networks. It can be generally divided into two parts.
The first part focuses on the efficient resource sharing in socio-technical networks. Existing
distributed network optimization techniques that enable efficient resource allocation when agents
are obedient or cooperative are no longer suitable in socio-technical networks which are formed by
self-interested agents. The strategic interactions of such self-interested agents lead in numerous
socio-technical networks to (Nash) equilibria that are highly inefficient from a social perspective.
To achieve social efficiency, incentives need to be provided to agents such that they find in their
own self-interest to cooperate and thus act in a socially-optimal way. I propose a general methodology
for the design and analysis of rating protocols and associated multi-agent learning algorithms to
sustain cooperation in socio-technical networks. Under a rating protocol, an agent is rated based on
its behavior. The rating affects the agent's rewards received in the network, which are typically
determined according to a differential resource management scheme: compliant agents receive higher
ratings and are rewarded by gaining more access to resources compared to non-compliant agents. This
preferential treatment thus provides an incentive for agents to cooperate. I rigorously formalize
and study the design of rating protocols to optimize the social resource sharing efficiency while
encompassing various unique features of socio-technical networks, including the anonymity of agents,
asymmetry of interests between different parties in the network, imperfect monitoring, dynamics in the
agent population, and white-washing effects (i.e., an individual agent creating multiple identities in
the network).
Different from the first part where the underlying network topology is exogenously determined, the second
part of my dissertation augments the proposed rating protocols by investigating the endogenous formation
of network topologies by the strategic, self-interested agents who produce, disseminate or collect resources.
I propose a novel game-theoretic framework to model and analyze the trade-offs (of each individual agent)
between the costs and benefits of producing resources personally and forming links to acquire and disseminate
resources. A central point of my analysis, which departs from the existing literature on social network formation,
is the assumption that the strategic agents are heterogeneous and that agents value this heterogeneity.
The heterogeneity of agents and the ability of agents to strategically produce, disseminate or collect resources
have striking consequences on the endogenously emerging topology, which provide important guidelines for the design
of effective incentive mechanisms and resource management schemes in endogenous socio-technical networks. I first
show that the network topology that emerges (at equilibrium) necessarily displays a core-periphery type: hub agents
(at the core of the network) produce most of the resources and also create and maintain links to the agents at the
periphery, while spoke agents (at the periphery of the network) derive most of their resources from hub agents,
producing little of it themselves. As the population becomes larger, the number of hub agents and the total amount
of resources produced grow in proportion to the total population. I then show that the networks that emerge at
equilibrium are frequently minimally connected and have short network diameters. These ``scale-free'' conclusions had
been conjectured for many networks, such as the ``small-world'' phenomenon in the World-Wide-Web, but not derived in
any formal framework, and are in stark contradiction to the ``law of the few'' that had been established in previous
work, under the assumption that agents solely benefit by forming links for resource acquisition, while resources are
homogeneous and part of the endowment of agents, rather than heterogeneous and produced.
Brian
Foo (Graduation Date: May 2008),
Title: Towards a Systematic Approach for Modeling and Optimizing Distributed
and Dynamic Multimedia Systems [Link] [Slides]
Abstract:
Recent advances in low-power, multi-core and distributed computing technologies
have opened up exciting research opportunities, as well as unique challenges,
for modeling, designing, and optimizing multimedia systems and applications.
First, multimedia applications are highly dynamic, with source characteristics
and workloads that can change significantly within milliseconds. Hence, systems
need to be able to optimally adapt their scheduling, resource allocation, and
resource adaptation strategies on-the-fly to meet the multimedia applications'
time-varying resource demands within the delay constraints specified by each
application. Second, systems often need to support multiple concurrent
multimedia applications and thus, (Pareto) efficient and fair resource
management solutions for dividing processing resources among the competing
applications need to be designed. Finally, some applications require
distributed computing resources or processing elements, which are located
across different autonomous sites. These different sites can collaborate in
order to jointly process the multimedia data by exchanging information about
their specific system implementations, algorithms and processing capabilities.
However, exchanging this information among these autonomous entities may result
in unacceptable delays or transmission overheads. Moreover, they may even
refuse to share this information due to proprietary or legal restrictions.
Thus, information-decentralization can present a major obstacle for optimizing
the performance of delay-sensitive multimedia applications that require
coordination and cooperation between distributed, autonomous sites.
This dissertation addresses the above challenges by providing a systematic
framework for modeling and optimizing multimedia systems in dynamic,
resource-constrained, and informationally-distributed environments. In
particular, we propose a stochastic modeling approach to capture the
dynamically changing utilities and workload variations inherent in multimedia
applications. This approach enables us to determine analytical solutions for
optimizing the performance of applications on resource-constrained systems.
Furthermore, the problem of information-decentralization can be addressed in
our framework by systematically decomposing the joint multi-applications and
multi-site optimization problems, and designing corresponding mechanisms for
exchanging model parameters, which characterize the utilities, constraints and
features of the autonomous entities. This systematic decomposition enables
entities to autonomously coordinate and collaborate under informational and
delay constraints. Finally, to optimize the performance of the multimedia
applications or systems in these distributed environments, we deploy
multi-agent learning strategies, which enable individual sites or applications
to model the behaviors of its competitors or peers and, based on this, select
their optimal parameters, configurations, and algorithms in an autonomous
manner. Summarizing, our framework proposes a unified approach combining
stochastic modeling, systematic information exchange mechanisms, and
interactive learning solutions for optimizing the performance of a wide range
of multimedia systems.
A unique and distinguishing feature of our approach is the extent of multimedia
algorithms and systems domain specific knowledge used in developing the
proposed framework for modeling, and optimizing the interacting system
components and applications. This is in contrast to existing distributed
optimization or game theoretic approaches, which use simplistic utility -
resource functions, and often ignore the dynamics and constraints experienced
in actual multimedia systems. Instead, our developed modeling and optimization
framework is directly shaped by the specific characteristics, constraints and
requirements of multimedia systems. Specifically, the proposed framework
provides pragmatic implementation solutions for (i) the optimization of dynamic
voltage scaling algorithms for multimedia applications, (ii) energy-aware resource
management for multiple multimedia tasks, and (iii) resource-constrained
adaptation for cascaded classifier topologies in distributed stream mining
systems.
Hyunggon
Park (Graduation Date: Nov. 2008),
Title: Distributed and Dynamic Resource Management Strategies for Multimedia
Networks using Cooperative Game Theoretic Approaches [Link] [Slides]
Abstract:
This thesis proposes a distributed and dynamic multi-user resource management
framework, which enables heterogeneous multimedia users that repeatedly
interact in a dynamically varying network environment to strategically maximize
their own utilities, given their private information. For this, we rely on
cooperative game-theoretic concepts. For instance, we model the bilateral
interactions among users as resource reciprocation games. Using our
formulation, the resource reciprocation among the various peers in a
peer-to-peer network is modeled as a stochastic game. Within this game,
the peers can autonomously determine their optimal strategies for resource
reciprocation using a Markov Decision Process (MDP) formulation. Unlike
existing myopic solutions for resource reciprocation such as Tit-For-Tat, the
optimal strategies determined based on MDP enable the peers to make foresighted
decisions about resource reciprocation, such that they can explicitly consider
both their immediate and future expected utilities. In the resource
reciprocation games, the participating users need to mutually agree on a
particular resource division. For this, we propose a methodology for designing
utility-aware resource division solutions which are able to fulfill desired
fairness axioms in terms of multimedia performance. We also show how the
proposed resource management framework can also be successfully deployed in
cognitive radio networks, wireless multimedia broadcasting, distributed stream
mining systems, etc.
Hsien-Po
Shiang (Graduation
Date: Mar. 2009),
Title: Designing Autonomic Wireless Multi-Hop Networks for Delay-Sensitive
Applications [Link] [Slides]
Abstract:
Emerging multi-hop wireless networks provide a low-cost and flexible infrastructure
that can be simultaneously utilized by multiple users for a variety of
applications, including delay-sensitive applications, such as multimedia
streaming, mission-critical applications, etc. However, this wireless
infrastructure is often unreliable and provides dynamically varying resources
with only limited QoS support. To improve the performance of the
delay-sensitive applications and to support timely reaction to the network
dynamics, the multi-hop network needs to be composed of autonomic nodes
(agents), which can adapt, make their own transmission decisions and negotiate
their wireless resources based on their available local information. Current
wireless networking research has focused on coping with the environment
disturbances, such as variations (uncertainties) of the wireless channel (e.g.
fading) or source (e.g. multimedia traffic) characteristics, while neglecting
the coupling dynamics among nodes, due to the shared nature of the wireless
spectrum. However, characterizing and learning the neighboring nodes' actions
and the evolution of these actions over time is vital in order to construct an
efficient and robust solution for delay-sensitive applications.
Hence, we propose and analyze various interactive learning schemes for these agents
to learn the network dynamics and, based on this knowledge, foresightedly adapt
their cross-layer transmission decisions such that they can efficiently utilize
the shared, time-varying network resources. We show that the foresighted
decision making significantly improves the agents' utilities under a variety of
dynamic network scenarios (e.g. multimedia streaming over WLAN,
energy-efficient transmission in mobile ad hoc networks, joint route/channel
selection in multi-hop cognitive radio networks) and various network topologies
as compared to existing state-of-the-art solutions. In conclusion, our research
adds a new, "cognitive", dimension to existing multi-hop wireless
networks that enables the autonomic nodes to dynamically forecast the expected
response to network dynamics of neighboring nodes and evaluate how specific
forms of explicit and implicit signaling impact the performance of
delay-sensitive applications.
Yi
Su (Graduation Date: May 2010),
Title: Informationally Efficient Multi-User Communication [Link] [Slides]
Abstract:
The rapid increase in the demand for data rate over wired and wireless
communication networks has led to a rethinking of the traditional network
architecture and design principles. In fact, communication systems are
inherently informationally decentralized competitive environments, where
multiple devices executing a variety of applications and services need to
locally adapt their transmission strategies based on their available
information and compete for scarce networking resources. The concepts and
techniques that have dominated multi-user communication research in recent
years are not well suited for these informationally decentralized environments.
Specifically, most existing research has focused on two extreme multi-user
interaction scenarios, the complete information scenario with a common
system-wide objective (e.g. Pareto optimality) and the private information
scenario with conflicting objectives (e.g. Nash equilibrium (NE)).
The objective of this dissertation is to characterize users' optimal strategies
to improve their performance subject to varying degrees of informational
constraints. We mainly focus on fully distributed solutions without any
real-time information exchange between different users. In particular, we
investigate three key problems in information-constrained multi-user
communication systems. First, when will a distributed algorithm (e.g. best
response dynamics) converge to a NE? And how fast? Second, if information is
constrained and no real-time information exchange between users is allowed, how
to improve an inefficient NE without message passing? Last, assuming no
real-time information exchange between users, can we still achieve Pareto
optimality? We propose and analyze two new classes of games named additively
coupled sum constrained games and linearly coupled games, in which we
individually address these three questions. In particular, we provide
sufficient conditions under which a unique NE exists and best response dynamics
linearly converges to the NE. We also provide conjectural equilibrium based
solutions that can substantially improve the performance of inefficient NE and
fully recover Pareto optimality without any real-time information exchange
between users. The proposed game models apply to a variety of realistic
applications in multi-user communication systems, including multi-channel power
control, flow control, and wireless random access.
Fangwen
Fu (Graduation Date: May 2010),
Title: A Unified Framework for Delay-Sensitive Communications [Link] [Slides]
Abstract:
Delay-sensitive communications (e.g. multimedia transmission) are booming over
a variety of wireless networks. Current solutions often lead to an
unsatisfactory experience for delay-sensitive applications since they ignore
the stringent delay requirements and the heterogeneous features (e.g.
importance, delay deadlines and dependencies) of the delaysensitive data. This
problem is becoming increasingly more serious when multiple delaysensitive
applications coexist in wireless networks and share the scarce network
resources. In this dissertation, we develop a unified foresighted optimization
framework which explicitly considers both the heterogeneity of the
delay-sensitive data and the dynamics of the wireless networks in order to
optimize the long-term utilities of the delay-sensitive applications.
In the proposed unified framework, we establish three separation principles
which are theoretically important for designing delay-sensitive communication
systems. First, by introducing the post-decision states, we separate the
foresighted decisions from the underlying network dynamics, which enables us to
explore the structures of the optimal solutions and design low-complexity algorithms.
Second, in order to explicitly consider the heterogeneity of the multimedia
traffic, we prioritize the delay-sensitive data (expressed as direct acyclic
graphs) and separate the multi-data unit foresighted decision into multiple
single-data unit foresighted decisions, which can subsequently be performed
from the high priority to the low priority. Third, when multiple
delay-sensitive applications coexist in the wireless network, by introducing a
resource price and relaxing the network resource constraints imposed in the
future transmission, we separate the multi-user foresighted decision into
multiple single-user foresighted decision, thereby significantly reducing the
computation and communication complexity. Implementing the above framework in practice
requires statistical knowledge of the network dynamics, which is often
unavailable before transmission time. To overcome this obstacle, we propose
novel structure-aware online learning algorithms derived from the above three
separation principles. The proposed online learning algorithms have low
complexity and fast convergence, and achieve ?-optimal
solutions, which can significantly improve the delay-sensitive communication
performance in the unknown environments.
Nicholas
Mastronarde
(Graduation Date: June 2011),
Title: Online Learning for Energy-Efficient Multimedia Systems [Link][Slides]
Abstract:
Designing energy-efficient resource management strategies for multimedia
applications is a challenging problem because of their stringent delay constraints,
mixed priorities, intense resource requirements, and sophisticated source
coding dependency structures. In my dissertation research, I aim to develop a
rigorous, formal, and unified modeling framework for supporting such
applications in a large class of resource management scenarios including
energy-efficient point-to-point wireless communication, cooperative multi-user
wireless video transmission, and energy-efficient cross-layer system
optimization.
The foundation of my approach is modeling multimedia systems as stochastic and
dynamic systems. Unlike traditional resource management solutions, in which the
goal is to optimize the immediate utility (i.e. myopic optimization), the goal
in the proposed framework is to optimize the trajectory of the system's
underlying stochastic process by accounting for how decisions at the current
time impact the future utility (i.e. dynamic optimization). To achieve this, I
model system and network resource management problems as Markov decision
processes (MDPs). Then, to address the fact that the statistics of the system's
underlying stochastic process are typically unknown a priori, I adopt and often
extend reinforcement learning techniques from artificial intelligence to enable
devices to learn their experienced dynamics online, at run-time, in order to
optimize their long-term performance.
Shaolei Ren (Graduation Date: June 2012),
Title: Strategic Pricing and Resource Allocation: Framework and Applications
[Link][Slides]
Abstract:
Enabled by ubiquitous broadband connectivity and seamless wireless connections,
we have witnessed in the past few years the emergence of a plethora of wireless
applications, ranging from data communications and social networking to the
more recently wireless cloud computing. The growing tension between the
exploding demand for such wireless applications and the increasingly scarce
network resources (e.g., spectrum, power) has urged a rethinking of the service
providers' pricing strategies and network resource management techniques to
cope with potential threats of quality-of-service degradation and revenue
decreases. Specifically, it has become of paramount importance for service
providers to strategically redesign their pricing policies and to understand
how various pricing policies will affect the service demand, competition in the
market, as well as the network resource management.
In this dissertation, I propose a novel framework to optimize a service
provider's pricing policy as well as its network resource allocation decision
for profit maximization, in the presence of self-interested participating users
that strategically respond to the charged price to maximize their own benefits.
Applicable to both static and stochastic environments, the proposed framework
explicitly takes into account user heterogeneity, which is observed in a wide
range of applications. Based on the framework, I investigate the problem of
optimizing pricing and resource allocation for the service provider's profit
maximization in various contexts, including cooperative relay networks,
communications markets, online user-generated content platforms, and mobile
cloud computing systems.
Personal use of
this material is permitted. However, permission to reprint/republish this
material for advertising or promotional purposes or for creating new collective
works for resale or redistribution to servers or lists, or to reuse any
copyrighted component of this work in other works must be obtained from the
copyright holder.
ML-AIM Machine Learning and Artificial Intelligence for Medicine