Tara Javidi - US grants

The use of wireless technology has the potential to significantly reduce the cost and enhance the growth of broadband data access, which is currently dominated by the cost of installation and maintenance of wired networks. A significant challenge in wireless networks is the issue of cross-layer design, which this research addresses by modeling broadband wireless networks as a complex system of interacting economies with two parts, wireless bandwidth (local), and the network core link-capacities (end-to-end). Media access control (MAC) provides a bandwidth multiplexing scheme, while at the transport layer, congestion/rate control determine the demand, hence the buffer and capacity allocation. In other words, the optimal design of broadband wireless networks can be viewed as the problem of scalable yet optimal utilization/sharing of various resources among autonomous users. Economists have been studying similar problems in various contexts such as air pollution, traffic management, etc. It is known, for example, that in all of these scenarios a centralization of decisions is not always possible or desirable. At the same time, unregulated access can result in over-utilization (which is suboptimal) due to each user's incentive to deviate from the common good (known as "tragedy of the commons"). Similarly, addressing the fundamental trade-offs between fairness, optimal allocation, and decentralization is essential in a cross-layer design of broadband wireless networks. This research provides a novel methodology that addresses such issues across various layers of protocol stack, and integrates these interdisciplinary studies into the academic curriculum.

The focus of this project is integrated design and analysis of communication networks in service of coordinated control of multi-vehicle systems. Consider a set of vehicles, equipped with local controllers and wireless radios, that is set to arrange itself, to stabilize, and to control its collective motion. To achieve globally desirable formation behavior, the controller on a given vehicle must respond to the motion and state of others.

In fact, there exists a complicated coupling among system components: network architecture, communications protocols, and controller design. The integrated design of these components is the objective of this project. The fundamental challenge in designing networked control systems is that the tasks of communication and control, in general, cannot be considered decoupled from each other without loss of optimality. However, modular solutions can potentially provide significant insights into the nature of efficient solutions. This project addresses the problem of integrated communications and control from a practically viable perspective by decomposing the problem into modular tasks. The introduced degree of modularity, despite its sub-optimality, enables practical and efficient solutions as well as insights into the inherent trade-offs. Because the questions that arise lie at the intersection between communications and controls research, the components of the project bring together expertise in decentralized control, networking, and signal processing through the following specific tasks: 1) Nonlinear coordinated control over dynamic graphs, 2) Crosslayer optimization of wireless networks in service of coordinated control, 3) Physical layer solutions to decentralized communication and control, and 4) Experimental performance evaluation on a 3D autonomous underwater vehicle test-bed at the University of Washington.

The PI and Co-PIs propose to organize a joint conference of two Workshops: the
Workshop on Algorithms and Models for the Web-Graph (WAW 2007) and the Workshop on Internet & Network Economics (WINE 2007) at San Diego December 11-14, 2007.
The main theme of WINE focuses on the algorithmic game theory including various aspects of computational complexity and applications such as auctions, pricing, collaboration, competition, security and other Internet related economical issues in general. In the past three years, there has been a great deal of development in understanding the computational complexity of Nash equilibrium and large scale economical games. WINE workshops have played a vital role in this and have been an impetus to the developments of algorithmic game theory and numerous applications.

WAW focuses on mathematical modeling and analysis of the dynamics of the webgraph and related large complex social networks as well as algorithmic applications in declustering, information retrieval and data mining. The series of WAW workshops have contributed to the rapid developments on the graph-theoretical and algorithmic aspects of the new science of networks.

Controlling Uncertainty: On the Sequential Refinement of Belief
This research focuses on a variety of information acquisition and sensing applications in which a
decision maker, by carefully controlling a sequence of actions with uncertain outcomes,
dynamically refines his belief about a phenomenon of interest in a speedy, accurate, and efficient
manner. The model includes a class of applications in communications, design of experiments,
cognitive science, and sensor management. In particular, the following three problems are
tackled.
? Active Sequential Hypothesis Testing: There are a set of hypotheses, one of which is true. A
decision maker is asked to identify the correct hypothesis by sequentially employing either one
of available sensing actions. Actions costs differently and produce statistically distinct
observations. Given a penalty for error in declaration, the work investigates the optimal
selection of sensing actions.
? Feedback Schemes for Joint Source-Channel Coding with Bandwidth Expansion: A message is
to be conveyed to a receiver over a noisy memoryless channel with feedback. The expected
distortion between the message and the receiver?s construction is sought to be minimized over
the choice of causal encoding functions as well as the decoding function.
? Joint Source-Channel Coding over a Multiple Access Channel with Feedback: Multiple
transmitters convey messages to a common receiver over a noisy memoryless multiple access
channel with perfect output feedback.
These problems boil down to the sequential control of a dynamical system whose system is the
conditional distribution of the unknown (true hypothesis, message, etc) and whose dynamics is
dictated by the Bayes? rule. In particular, the optimal choice of actions, i.e. refinement in the
conditional distribution and reduction of uncertainty, is investigated.

Learning and inference in distributed settings is an important from both a scientific and engineering perspective. A typical instance of the problem is a network of individual sensors or agents attempting to infer a global distribution that governs their local observations. By passing messages the agents can individually make inference about a global phenomenon. This research investigates communication and networking paradigms that can enable a network of individual agents to collaboratively estimate distributions over high dimensional spaces, even when individual observations are severely limited in accuracy, space, or time.

In particular, the investigators study how individual decision makers can integrate two kinds of information: local observations and messages from their neighbors in the network. Both observation and messaging can be thought of as sampling : individuals sample their own environment and sample the opinions of their neighbors. Central to the approach is that the agents generate simple messages at random from an internal estimate of the global distribution of interest. The first major goal of this project is to develop a mathematical framework and analysis techniques to understand if and when this limited form of learning and communication is sufficient for an individual to estimate and learn distributions and/or global parameters governing the observations of all nodes. The technical approach is a blend of analysis techniques ranging from stochastic approximation, randomized algorithms, and statistical physics.

Applications for this work range from mathematical modeling of messages and opinion formation in social networks, communication protocols for distributed optimization, and estimation of parameters in data networks. The work will cover several related problems : estimating high-dimensional histograms of data held in the network, parametric estimation using a mix of Bayesian and non-Bayesian techniques, and estimation of more complex generative models. The final part of the work is to apply these methods to peer-peer networks and social network modeling. The broader impact of this work is to further develop the interdisciplinary field of network science, which impacts both quantitative social sciences and engineering. The PIs will develop educational materials and organize research activities to help bring together different research communities interested in networks and social learning.

This research focuses on the problem of information acquisition in the context of spectrum sensing and utilization where a (set of) decision maker(s), by carefully controlling a sequence of actions with uncertain outcomes, dynamically refines his/her belief about stochastically time-varying parameters of interest such as spectrum availability and quality, in order to communicate over that spectrum as efficiently as possible.

The research represents a new theoretical framework for stochastic learning and decision-making in such settings termed Information Acquisition and Utilization Problems (IAUP). Motivated by a synthesis of the researchers' prior works on adaptive sampling, active hypothesis testing, and restless multi-armed bandits, this framework is particularly apt for problems of spectrum sensing and access for several reasons. First, unlike more general stochastic control frameworks such as partially observable Markov decision problems (POMDP's), the IAUP is a purely informational problem in that the actions of the decision maker change only its information state, but not the state of the underlying environment (spectrum quality). Second, in an IAUP there is a conceptual distinction between two kinds of actions: those taken to obtain/refine the information state, and those taken to utilize the current information state, potentially allowing for tractable solutions in many cases where a separation theorem can be proved between these two sets. Finally, an IAUP can explicitly capture the tradeoff between the cost of spectrum sensing and the accuracy and completeness of the information that can be obtained.

This project deals with theory and efficient algorithms for statistical decision problems that are radically different from those that have been studied to date in two key aspects: First, the decision-maker may choose among a large class of observation channels (features) of varying complexity and quality; and second, the total cost of computational resources that can be used prior to arriving at a decision is limited. Computer vision is a paradigmatic source of such feature-rich decision problems, requiring the use of multiple heterogeneous feature types, integration of diverse sources of contextual information, and possibly even human interaction.

This project entails the development of a rigorous mathematical framework for feature-rich decision problems in accordance with three specific aims: (1) structural characterization of features as stochastic belief-refining filters; (2) universal cost-sensitive criteria for numerical comparison of features in terms of expected information gains; and (3) optimal value-of-information criteria for sequential feature selection that take into account both feature extraction costs and terminal decision losses. As corollaries, this research investigates connections to asymptotic information-theoretic characterizations of optimal feature selection rules and decisions. The fourth specific aim of the project is the development of practical algorithms for two challenging computer vision problems: active visual search and fine-grained categorization. This component of the project leverages theoretical aims (1) and (2) to develop practical cost- and loss-sensitive feature compression techniques. Theoretical aim (3) targets algorithms that function as autonomous decision-making agents. Faced with an inference task on an image, they apply cost-sensitive non-myopic value- of-information criteria to decide at each time step whether to extract a new feature from the image or to stop and declare an answer.

This project focuses on the problem of information acquisition, state estimation and control in the context of cyber physical systems. In our underlying model, a (set of) decision maker(s), by controlling a sequence of actions with uncertain outcomes, dynamically refines the belief about stochastically time-varying parameters of interest. These parameters are then used to control the physical system efficiently and robustly. Here the cyber system collects, processes, and acquires information about the underlying physical system of interest, which is used for its control. The proposed work will develop a new theoretical framework for stochastic learning, decision-making, and control in stochastically-varying cyber physical systems.

In order to obtain analytical insights into the structure of efficient design, we first consider the case where the actions of the cyber system only affect the estimate of the underlying physical system. This class of problems arises in the context of (distributed) sensing/tracking of a physical system in isolation from cyber system control of the physical system's state. Joint state estimation and control for cyber-physical systems will then be considered. Here the most natural first step is to obtain sufficient conditions and/or special classes of systems where a separated approach to the information acquisition and efficient control is (near) optimal. To demonstrate its utility in practice, our theoretical framework will be applied in the specific context of energy efficient control of data centers and robust control of the smart grid under limited sensing.

The intellectual merit of this work will be to develop a theoretical framework for the design of cyber-physical systems including information acquisition, state estimation, and control. In addition, separation theorems for the optimality of separate state estimation and control will be explored.

In terms of broader impacts, significant performance improvement of control systems closed over communication networks will impact a wide range of applications for societal benefit, including smart buildings, intelligent transportation systems, energy-efficient data centers, and the future smart-grid. The PIs plan to disseminate the research results widely through conferences and journals, as well as by organizing specialized workshops and conference sessions related to cyber physical systems. The proposed project will train Ph.D. students as well as enrich the curriculum taught by the PIs in communications, stochastic control, and networks. The PIs have a strong track record in diversity and outreach activities, which for this project will include exposure and involvement of high school and undergraduate students, including under-represented minorities and women.

Claude Shannon?s ?A Mathematical Theory of Communication? is the landmark event that paved the way for the development of modern communication systems. Shannon analyzed the fundamental redundancy that must be added to data in order to achieve reliable communication in the presence of noise. Since then his vision has guided the practical design of virtually all aspects of modern communication systems such as forward error correction, spectrally-efficient communication, multiuser and inter-symbol interference, multiple-antenna systems, opportunistic communication, and joint compression/transmission. However, while feedback is present in virtually all modern communication systems, the field of information theory has had relatively little impact on how feedback is employed in practice. The proposed work will advance knowledge by developing a more complete understanding of how feedback should be employed in communication systems and what quantitative improvements in delay, complexity, and transmitted power one can expect from its effective use, under realistic delay constraints such as those found in high-speed wireless data. In summary, the successful completion of the project is expected to contribute new mathematical tools, designs, viewpoints, and models to the field of information theory.

The goal of this research is to bring the insight, design guidance, and performance bounds for which information theory is known to bear on the design of systems with feedback. By providing new design principles and feedback codes, this research has the potential not only to advance basic science but also to improve the efficiency and reliability of our communications infrastructure, including consumer technology such as WiFi and smartphones. Given the proliferation of personal communication devices, such improvements would augment the efficiency with which crucial resources such as energy and radio frequency bandwidth are currently utilized.

The goal of this project is to develop interactive learning frameworks and methods that can learn predictors based on complex, imperfect feedback adaptively solicited in an on-line fashion from human annotators. Such predictors can significantly benefit the practice of machine learning by making it more accessible in domains where annotations are expensive. Currently, beyond a handful of heuristic studies, the only well-understood interactive learning setting is active binary classification, where a single annotator interactively provides labels to a learning algorithm. The main challenge in exploiting richer feedback is that human responses are inherently inconsistent and imperfect. This project will overcome this challenge by assuming that the responses come from unknown probability distributions with some mild yet realistic properties, which will be exploited to provide methods that can learn reliably from complex feedback.

Specifically, this project will introduce a general framework for interactive learning from imperfect, complex feedback, and develop methods for three common cases: (1) Active Learning with Abstention Feedback, where annotators can either provide a label or declare I Don't Know (2) Active Learning for Multiclass Classification, where the goal is to learn a classifier for a large number of classes and (3) Active Learning with Feedback from Multiple Annotators, where the goal is to combine feedback from many labelers with varying amounts of expertise subject to a budget. These problems will be approached through two main tools -- adaptive hypothesis testing and surrogate loss minimization. Combining these approaches will lead to principled algorithms for building accurate machine learning predictors with low annotation cost, which in turn, will benefit the practice of machine learning in domains where annotated data is expensive.

This award is a planning grant for the Spectrum Innovation Initiative: National Center for Wireless Spectrum Research (SII-Center). The focus of a spectrum research SII-Center goes beyond 5G, IoT, and other existing or forthcoming systems and technologies to chart out a trajectory to ensure United States leadership in future wireless technologies, systems, and applications in science and engineering through the efficient use and sharing of the radio spectrum. This project aims to catalyze the activities of a multi-disciplinary academic team and stakeholders towards collaborative long-term research, education, workforce development and establishing the definitive center of spectrum engineering, policy and science. The SII-Center is envisioned as the corner stone of trans-disciplinary effort, amalgamating efforts of academics, industry, government, policy, standard bodies and scientific and civic communities. The center will transform wireless communications anytime, anywhere, providing use and utilization of spectrum ubiquitously and seamlessly across networks, devices and communities, addressing the critical need of closing the digital divide, providing reliable and secure access to information for all. The broader impact of this effort will directly contribute to the United States reclaiming its rightful place as the global leader in wireless communications and information processing in the internet of everything era.

The comprehensive research vision of the center is to establish the next and last generation of wireless connectivity by an integrative system design that will build on optimal use of wireless resources throughout the spectrum, from hardware to system design, software and policy, ensuring coexistence requirements of communities who are primary users of the spectrum. The project will seek to (i) refine the research vision by engaging industry, government, research labs, and communities with use requirements such as remote sensing and radio astronomy; (ii) formulate research partnerships towards executing the vision; (iii) prepare a comprehensive white paper which will not only contribute to the center proposal, but importantly, will be a stand alone guide for government, learned societies, communities, industry and academia on the last generation of wireless, i.e., a holistic system design making optimum and seamless spectrum utilization an innate component from the outset. The center vision includes inter-disciplinary curricula and workforce development for spectrum science and engineering.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Improved optimizations of energy-efficiency, safety, robustness, and other criteria in engineered systems offer the promise of incalculable societal benefits. However, challenges of scale and complexity keep many real-world optimization needs beyond our reach. The mission of The National Artificial Intelligence (AI) Institute for Learning-enabled Optimization at Scale (TILOS) is to make impossible optimizations possible, at scale and in practice. The institute (a partnership of University of California, San Diego, Massachusetts Institute of Technology, National University, University of Pennsylvania, University of Texas at Austin and Yale University) will pioneer learning-enabled optimizations that transform chip design, robotics, communication networks, and other use domains that are vital to our nation’s health, prosperity and welfare. In TILOS, research, education, outreach and translation are holistically driven by what makes the nexus of AI/ML and optimization uniquely challenging at the leading edge of practice. Industry partners will interact closely with TILOS on both foundational research and its use-domain application. TILOS will build an openly accessible program of continuing education with long-term, lifelong learning and skills renewal as its central tenet. This institute will also broaden participation, building on the visible successes at its partner institutions that have reached underserved demographics from K-12 onward. Through these efforts, TILOS will discover, educate, and translate into real-world practice a new nexus of AI, optimization, and use.

TILOS is organized around multiple virtuous cycles that unify AI and optimization, use domains, and the translation of AI-optimization breakthroughs into practice. A first virtuous cycle of AI and optimization, where each enables and amplifies the other, is at the heart of TILOS. Foundational research will pursue five main pillars: (i) bridging discrete and continuous optimization; (ii) distributed, parallel, and federated optimization; (iii) optimization on manifolds; (iv) dynamic decisions under uncertainty; and (v) nonconvex optimization in deep learning. A second virtuous cycle of challenges, inspirations and data-enabled validations connects the foundational research in AI-optimization with use-domain expertise. The initial use-domain foci bring diverse optimization challenges but inspire shared solutions with commonalities such as physical embeddedness, hierarchical-system context, underlying graphical models, safety and robustness as first-class concerns, and the bridging of human-guided and autonomous systems. A third virtuous cycle is one of translation and ever-tighter connections to the leading edge of practice. TILOS will leverage industry partnerships to accelerate impact via open standards, data sets and “data virtual reality”, and open source that democratize access to research enablement. Roadmaps of optimization formulations and progress metrics will draw researchers together and toward shared research goals. A fourth virtuous cycle with industry and the institutional partners spans both workforce development and the broadening of participation. Workforce development will identify and teach the skills and mindsets needed at the nexus of learning, optimization and practice, so as to provide skills renewal for the existing workforce as well as onramps for underserved demographics such as veterans or those seeing a career change. Broadening of participation will be pursued via the institute’s partnerships with community organizations and middle and high school educators, via tiers of engagement that span exposure, experience and environment.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.