BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Department of Electrical & Computer Engineering - ECPv6.16.2//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Department of Electrical & Computer Engineering
X-ORIGINAL-URL:https://ece.northeastern.edu
X-WR-CALDESC:Events for Department of Electrical & Computer Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20210314T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20211107T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20220313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20221106T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20230312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20220216T133000
DTEND;TZID=America/New_York:20220216T143000
DTSTAMP:20260612T050753
CREATED:20220214T210524Z
LAST-MODIFIED:20220214T210524Z
UID:5459-1645018200-1645021800@ece.northeastern.edu
SUMMARY:ECE PhD Proposal Review: Yuanyuan Li
DESCRIPTION:PhD Proposal Review: Submodularity in Cache Networks \nYuanyuan Li \nLocation: Zoom Link \nAbstract: As information-based demand surges\, distributed network services\, e.g.\, cache networks\, play an important role to mitigate network traffic. Cache networks are a natural abstraction for many applications\, including information-centric networks\, content delivery networks\, cloud computing\, and edge/wireless IoT. How to allocate resources (routing\, placing items in caches\, flow control\, etc.) in cache networks is a crucial problem\, as resources (storage space\, and bandwidths) are usually limited. Resource allocation in networks has been traditionally approached through classic convex optimization. However\, simple problems becomes combinotorial in cache networks\, which leads to NP-hardness. Enlightened by several works studying cache networks\, we identify a useful property\, submodularity\, which is the key to approximation algorithms solving those NP hard resource allocation problem in cache networks.\nLeveraging submodularity\, we study a cache network\, in which intermediate nodes equipped with caches can serve content requests\, from different angles.\nFirst\, we model this network as a universally stable queuing system\, in which packets carrying identical responses are consolidated before being forwarded downstream. We refer to resulting queues as M/M/1c or counting queues\, as consolidated packets carry a counter indicating the packet’s multiplicity. Cache networks comprising such queues are hard to analyze; we propose two approximations: one via M/M/∞ queues\, and one based on M/M/1c queues under the assumption of Poisson arrivals. We show that\, in both cases\, the problem of jointly determining (a) content placements and (b) service rates admits a poly-time\, 1-1/e approximation algorithm. We also show that our analysis\, with respect to both algorithms and associated guarantees\, extends to (a) counting queues over items\, rather than responses\, as well as to (b) queuing at nodes and edges\, as opposed to just edges.\nSecond\, we refer to the cost reduction enabled by caching as the caching gain\, and the product of the caching gain of a content request and its request rate as caching gain rate. We aim to study \emph{fair} content allocation strategies through a utility-driven framework\, where each request achieves a utility of its caching gain rate\, and consider a family of α-fair utility functions to capture different degrees of fairness. The resulting problem is an NP-hard problem with a non-decreasing submodular objective function. Submodularity allows us to devise a deterministic allocation strategy with an optimality guarantee factor arbitrarily close to 1-1/e. When 0 < α ≤ 1\, we further propose a randomized strategy that attains an improved optimality guarantee\, (1-1/e)^(1-α)\, in expectation.\nThird\, We study a cache network under arbitrary adversarial request arrivals. We propose a distributed online policy based on the online tabular greedy algorithm. Our distributed policy achieves sublinear (1-1/e)-regret\, also in the case when update costs cannot be neglected.\nFinally\, we propose an experimental design network paradigm\, wherein learner nodes train possibly different Bayesian linear regression models via consuming data streams generated by data source nodes over a network. We formulate this problem as a social welfare optimization problem in which the global objective is defined as the sum of experimental design objectives of individual learners\, and the decision variables are the data transmission strategies subject to network constraints. We first show that\, assuming Poisson data streams\, the global objective is a continuous DR-submodular function. We then propose a Frank-Wolfe type algorithm that outputs a solution within a 1-1/e factor from the optimal. Our algorithm contains a novel gradient estimation component which is carefully designed based on Poisson tail bounds and sampling.
URL:https://ece.northeastern.edu/event/ece-phd-proposal-review-yuanyuan-li/
END:VEVENT
END:VCALENDAR