Change search
Refine search result
12 1 - 50 of 55
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Bonald, Thomas
    et al.
    Telecom Paris Tech.
    Proutière, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Two-target algorithms for infinite-armed bandits with Bernoulli rewards2013In: Advances in Neural Information Processing Systems 26 (2013), Morgan Kaufmann Publishers, 2013Conference paper (Refereed)
    Abstract [en]

    We consider an infinite-armed bandit problem with Bernoulli rewards. The mean rewards are independent, uniformly distributed over [0; 1]. Rewards 0 and 1 are referred to as a success and a failure, respectively. We propose a novel algorithm where the decision to exploit any arm is based on two successive targets, namely, the total number of successes until the first failure and until the first m failures, respectively, where m is a fixed parameter. This two-target algorithm achieves a long-term average regret in 2√n for a large parameter m and a known time horizon n. This regret is optimal and strictly less than the regret achieved by the best known algorithms, which is in 2√n The results are extended to any mean-reward distribution whose support contains 1 and to unknown time horizons. Numerical experiments show the performance of the algorithm for finite time horizon.

  • 2. Bordenave, Charles
    et al.
    McDonald, David
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Asymptotic Stability Region of Slotted Aloha2012In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 58, no 9, p. 5841-5855Article in journal (Refereed)
    Abstract [en]

    We analyze the stability of standard, buffered, slotted-Aloha systems. Specifically, we consider a set of users, each equipped with an infinite buffer. Packets arrive into user i's buffer according to some stationary ergodic Markovian process of intensity lambda(i). At the beginning of each slot, if user i has packets in its buffer, it attempts to transmit a packet with fixed probability p(i) over a shared resource/channel. The transmission is successful only when no other user attempts to use the channel. The stability of such systems has been open since their very first analysis in 1979 by Tsybakov and Mikhailov. In this paper, we propose an approximate stability condition that is provably exact when the number of users grows large. We provide theoretical evidence and numerical experiments to explain why the proposed approximate stability condition is extremely accurate even for systems with a restricted number of users (even two or three).

  • 3.
    Bordenave, Charles
    et al.
    University of California, Berkeley, USA.
    McDonald, David
    University of Ottawa, Canada.
    Proutiere, Alexandre
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    Random multi-access algorithms in networks with partial interaction: A mean field analysis2007Conference paper (Refereed)
    Abstract [en]

    We consider a network with a fixed number of links whose transmitters are saturated and access a channel using a random back-off algorithm. Some of the links may be hidden in the sense that they do not interfere with all other links but rather with a subset of the links. Using mean field techniques, we analyze a variety of random back-off algorithms by explicit calculating the throughput of the links in such networks. We apply our results to analyze the performance of the exponential back-off algorithm in networks with partial interaction. The results are striking and confirm experimental results. Hidden transmitters that fail to sense collisions with other links unfairly grab too much bandwidth at the expense of transmitters that comply with the back-off rules. We believe the model can be used to develop new algorithms realizing an adequate trade-off between fairness and efficiency.

  • 4.
    Bordenave, Charles
    et al.
    CNRS & Université de Toulouse.
    McDonald, David
    University of Ottawa, Canada.
    Proutiere, Alexandre
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    Random multi-access algorithms in networks with partial interaction: A mean field analysis2010In: Networks and Heterogeneous Media, ISSN 1556-1801, E-ISSN 1556-181X, Vol. 5, no 1, p. 31-62Article in journal (Refereed)
    Abstract [en]

    We study an interacting particle system whose dynamics depends on an interacting random environment. As the number of particles grows large, the transition rate of the particles slows down (perhaps because they share a common resource of fixed capacity). The transition rate of a particle is determined by its state, by the empirical distribution of all the particles and by a rapidly varying environment. The transitions of the environment are determined by the empirical distribution of the particles. We prove the propagation of chaos on the path space of the particles and establish that the limiting trajectory of the empirical measure of the states of the particles satisfies a deterministic differential equation. This deterministic differential equation involves the time averages of the environment process.

    We apply the results on particle systems to understand the behavior of computer networks where users access a shared resource using a distributed random Medium Access Control (MAC) algorithm. MAC algorithms are used in all Local Area Network (LAN), and have been notoriously difficult to analyze. Our analysis allows us to provide simple and explicit expressions of the network performance under such algorithms.

  • 5.
    Borst, Sem
    et al.
    Alcatel-Lucent Bell Labs.
    Hegde, Nidhi
    Orange Labs.
    Proutiere, Alexandre
    Interacting queues with server selection and coordinated scheduling - Application to cellular data networks2009In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 170, no 1, p. 59-78Article in journal (Refereed)
    Abstract [en]

    We consider a system of parallel servers handling users of various classes, whose service rates depend not only on user classes, but also on the set of active servers. We investigate the stability under two types of allocation strategies: (i) server assignment where the users are assigned to servers based on rates, load, and other considerations, and (ii) coordinated scheduling where the activity states of servers are coordinated. We show how the model may be applied to evaluate the downlink capacity of wireless data networks. Specifically, we examine the potential gains in wireless capacity from the two types of resource allocation strategies.

  • 6. Borst, Sem
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Shah, Devavrat
    Special Issue on Recent Trends in the Mathematics of Wireless Communication Networks: Algorithms, Models and Methods-Part 1 Introduction2012In: Queueing systems, ISSN 0257-0130, E-ISSN 1572-9443, Vol. 72, no 1-2, p. 1-3Article in journal (Other academic)
  • 7. Bouman, N.
    et al.
    Borst, S.
    Van Leeuwaarden, J.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Backlog-based random access in wireless networks: Fluid limits and delay issues2011In: Proceedings of the 2011 23rd International Teletraffic Congress, ITC 2011, 2011, p. 39-46Conference paper (Refereed)
    Abstract [en]

    We explore the spatio-temporal congestion dynamics of wireless networks with backlog-based random-access mechanisms. While relatively simple and inherently distributed in nature, suitably designed backlog-based access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling algorithms in a wide range of scenarios. In the present paper, we show that the specific activity functions for which maximum stability has been established, may however yield excessive queue lengths and delays. The results reveal that more aggressive/persistent access schemes can improve the delay performance, while retaining the maximum stability guarantees in a rich set of scenarios. In order to gain qualitative insights and examine stability properties we will investigate fluid limits where the system dynamics are scaled in space and time. As it turns out, several distinct types of fluid limits can arise, exhibiting various degrees of randomness, depending on the structure of the network, in conjunction with the form of the activity functions. We further demonstrate that, counter to intuition, additional interference may improve the delay performance in certain cases. Simulation experiments are conducted to illustrate and validate the analytical findings.

  • 8. Chaporkar, P.
    et al.
    Proutière, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Optimal distributed scheduling in wireless networks under SINR interference model2013In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, IEEE conference proceedings, 2013, p. 1372-1379Conference paper (Refereed)
    Abstract [en]

    Radio resource sharing mechanisms are key to ensuring good performance in wireless networks. In their seminal paper [1], Tassiulas and Ephremides introduced the Maximum Weighted Scheduling algorithm, and proved its throughput-optimality. Since then, there have been extensive research efforts to devise distributed implementations of this algorithm. Recently, distributed adaptive CSMA scheduling schemes [2] have been proposed and shown to be optimal, without the need of message passing among transmitters. However their analysis relies on the assumption that interference can be accurately modelled by a simple interference graph. In this paper, we consider the more realistic and challenging SINR interference model. We present the first distributed scheduling algorithms that (i) are optimal under the SINR interference model, and (ii) that do not require any message passing. They are based on a combination of a simple and efficient power allocation strategy referred to as Power Packing and randomization techniques. These algorithms are rate-optimal in the sense that they perform as well as the best centralized scheduling schemes in scenarios where each transmitter is aware of the rate at which it should send packets to the corresponding receiver. As shown in [3], rate-optimal algorithms can be extended easily so that they reach throughput-optimality.

  • 9. Chaporkar, Prasanna
    et al.
    Magureanu, Stefan
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Optimal Distributed Scheduling in Wireless Networks Under the SINR Interference Model2016In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 24, no 4, p. 2033-2045Article in journal (Refereed)
    Abstract [en]

    In wireless networks, the design of radio resource sharing mechanisms is complicated by the complex interference constraints among the various links. In their seminal paper (IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936-1948), Tassiulas and Ephremides introduced Maximum Weighted Scheduling, a centralized resource sharing algorithm, and proved its optimality. Since then, there have been extensive research efforts to devise distributed implementations of this algorithm. Recently, distributed adaptive CSMA scheduling schemes have been proposed and shown to be optimal, without the need of message passing among transmitters. However, their analysis relies on the assumption that interference can be accurately modeled by a simple interference graph. In this paper, we consider the more realistic and challenging signal-to-interference-plus-noise ratio (SINR) interference model. We present distributed scheduling algorithms that: 1) are optimal under the SINR interference model; and 2) do not require any message passing. These algorithms are based on a combination of a simple and efficient power allocation strategy referred to as Power Packing and randomization techniques. The optimality of our algorithms is illustrated in various traffic scenarios using numerical experiments.

  • 10. Combes, R.
    et al.
    Magureanu, Stefan
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutière, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Laroche, Cyrille
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Learning to rank: Regret lower bounds and efficient algorithms2015In: Performance Evaluation Review, ISSN 0163-5999, E-ISSN 1557-9484, Vol. 43, no 1, p. 231-244Article in journal (Refereed)
    Abstract [en]

    Algorithms for learning to rank Web documents, display ads, or other types of items constitute a fundamental component of search engines and more generally of online services. In such systems, when a user makes a request or visits a web page, an ordered list of items (e.g. documents or ads) is displayed; the user scans this list in order, and clicks on the first relevant item if any. When the user clicks on an item, the reward collected by the system typically decreases with the position of the item in the displayed list. The main challenge in the design of sequential list selection algorithms stems from the fact that the probabilities with which the user clicks on the various items are unknown and need to be learned. We formulate the design of such algorithms as a stochastic bandit optimization problem. This problem differs from the classical bandit framework: (1) the type of feedback received by the system depends on the actual relevance of the various items in the displayed list (if the user clicks on the last item, we know that none of the previous items in the list are relevant); (2) there are inherent correlations between the average relevance of the items (e.g. the user may be interested in a specific topic only). We assume that items are categorized according to their topic and that users are clustered, so that users of the same cluster are interested in the same topic. We investigate several scenarios depending on the available sideinformation on the user before selecting the displayed list: (a) we first treat the case where the topic the user is interested in is known when she places a request; (b) we then study the case where the user cluster is known but the mapping between user clusters and topics is unknown. For both scenarios, we derive regret lower bounds and devise algorithms that approach these fundamental limits.

  • 11. Combes, R.
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Dynamic rate and channel selection in cognitive radio systems2015In: IEEE Journal on Selected Areas in Communications, ISSN 0733-8716, E-ISSN 1558-0008, Vol. 33, no 5, p. 910-921, article id 6914537Article in journal (Refereed)
    Abstract [en]

    In this paper, we investigate dynamic channel and rate selection in cognitive radio systems that exploit a large number of channels free from primary users. In such systems, transmitters may rapidly change the selected (channel, rate) pair to opportunistically learn and track the pair offering the highest throughput. We formulate the problem of sequential channel and rate selection as an online optimization problem and show its equivalence to a structured multiarmed-bandit problem. The structure stems from inherent properties of the achieved throughput as a function of the selected channel and rate. We derive fundamental performance limits satisfied by any channel and rate adaptation algorithm and propose algorithms that achieve (or approach) these limits. In turn, the proposed algorithms optimally exploit the inherent structure of the throughput. We illustrate the efficiency of our algorithms using both test-bed and simulation experiments, in both stationary and nonstationary radio environments. In stationary environments, the packet successful transmission probabilities at the various channel and rate pairs do not evolve over time, whereas in nonstationary environments, they may evolve. In practical scenarios, the proposed algorithms are able to track the best channel and rate quite accurately without the need for any explicit measurement of and feedback on the quality of the various channels.

  • 12. Combes, R.
    et al.
    Talebi, Mohammad Sadegh
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Lelarge, M.
    Combinatorial bandits revisited2015In: Advances in Neural Information Processing Systems, Neural Information Processing Systems, 2015, p. 2116-2124Conference paper (Refereed)
    Abstract [en]

    This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific regret lower bound, and discuss its scaling with the dimension of the decision space. We propose ESCB, an algorithm that efficiently exploits the structure of the problem and provide a finite-time analysis of its regret. ESCB has better performance guarantees than existing algorithms, and significantly outperforms these algorithms in practice. In the adversarial setting under bandit feedback, we propose COMBEXP, an algorithm with the same regret scaling as state-of-the-art algorithms, but with lower computational complexity for some combinatorial problems.

  • 13.
    Combes, Richard
    et al.
    Centrale-Supelec, L2S, France.
    Magureanu, Stefan
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Minimal Exploration in Structured Stochastic Bandits2017In: Advances in Neural Information Processing Systems, Neural information processing systems foundation , 2017, p. 1764-1772Conference paper (Refereed)
    Abstract [en]

    This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural properties. Most existing structures (e.g. linear, lipschitz, unimodal, combinatorial, dueling,...) are covered by our framework. We derive an asymptotic instance-specific regret lower bound for these problems, and develop OSSB, an algorithm whose regret matches this fundamental limit. OSSB is not based on the classical principle of " role="presentation" style="box-sizing: border-box; display: inline-block; line-height: 0; font-size: 16.38px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; position: relative;">optimism in the face of uncertainty'' or on Thompson sampling, and rather aims at matching the minimal exploration rates of sub-optimal arms as characterized in the derivation of the regret lower bound. We illustrate the efficiency of OSSB using numerical experiments in the case of the linear bandit problem and show that OSSB outperforms existing algorithms, including Thompson sampling.

  • 14.
    Combes, Richard
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Unimodal bandits: Regret lower bounds and optimal algorithms2014In: 31st International Conference on Machine Learning, ICML 2014, 2014, p. 799-807Conference paper (Refereed)
    Abstract [en]

    2014 We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investigated in (Cope, 2009; Yu&Mannor, 2011). The set of arms is either discrete, in which case arms correspond to the vertices of a finite graph whose structure represents similarity in rewards, or continuous, in which case arms belong to a bounded interval. For discrete unimodal bandits, we derive asymptotic lower bounds for the regret achieved under any algorithm, and propose OSUB, an algorithm whose regret matches this lower bound. Our algorithm optimally exploits the unimodal structure of the problem, and surprisingly, its asymptotic regret does not depend on the number of arms. We also provide a regret upper bound for OSUB in non-stationary environments where the expected rewards smoothly evolve over time. The analytical results are supported by numerical experiments showing that OSUB performs significantly better than the state-of-the-art algorithms. For continuous sets of arms, we provide a brief discussion. We show that combining an appropriate discretization of the set of arms with the UCB algorithm yields an order-optimal regret, and in practice, outperforms recently proposed algorithms designed to exploit the unimodal structure.

  • 15.
    Combes, Richard
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control. INRIA/ENS, France .
    Yun, D.
    Ok, J.
    Yi, Y.
    Optimal Rate Sampling in 802.11 systems2014In: Proceedings - IEEE INFOCOM, 2014, p. 2760-2767Conference paper (Refereed)
    Abstract [en]

    Rate Adaptation (RA) is a fundamental mechanism in 802.11 systems. It allows transmitters to adapt the coding and modulation scheme as well as the MIMO transmission mode to the radio channel conditions, and in turn, to learn and track the (mode, rate) pair providing the highest throughput. So far, the design of RA mechanisms has been mainly driven by heuristics. In contrast, in this paper, we rigorously formulate such design as an online stochastic optimisation problem. We solve this problem and present ORS (Optimal Rate Sampling), a family of (mode, rate) pair adaptation algorithms that provably learn as fast as it is possible the best pair for transmission. We study the performance of ORS algorithms in stationary radio environments where the successful packet transmission probabilities at the various (mode, rate) pairs do not vary over time, and in non-stationary environments where these probabilities evolve. We show that under ORS algorithms, the throughput loss due to the need to explore sub-optimal (mode, rate) pairs does not depend on the number of available pairs. This is a crucial advantage as evolving 802.11 standards offer an increasingly large number of (mode, rate) pairs. We illustrate the efficiency of ORS algorithms (compared to the state-of-the-art algorithms) using simulations and traces extracted from 802.11 test-beds.

  • 16. Fu, Shuangshuang
    et al.
    Shi, Guodong
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    James, Matthew R.
    Feedback policies for measurement-based quantum state manipulation2014In: Physical Review A. Atomic, Molecular, and Optical Physics, ISSN 1050-2947, E-ISSN 1094-1622, Vol. 90, no 6, article id 062328Article in journal (Refereed)
    Abstract [en]

    In this paper, we propose feedback designs for manipulating a quantum state to a target state by performing sequential measurements. In light of Belavkin's quantum feedback control theory, for a given set of (projective or nonprojective) measurements and a given time horizon, we show that finding the measurement selection policy that maximizes the probability of successful state manipulation is an optimal control problem for a controlled Markovian process. The optimal policy is Markovian and can be solved by dynamical programming. Numerical examples indicate that making use of feedback information significantly improves the success probability compared to classical scheme without taking feedback. We also consider other objective functionals including maximizing the expected fidelity with the target state as well as minimizing the expected arrival time. The connections and differences among these objectives are also discussed.

  • 17. Ganesh, Ayalvadi
    et al.
    Lilienthal, Sarah
    Manjunath, D.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Simatos, Florian
    Load balancing via random local search in closed and open systems2012In: Queueing systems, ISSN 0257-0130, E-ISSN 1572-9443, Vol. 71, no 3, p. 321-345Article in journal (Refereed)
    Abstract [en]

    In this paper, we analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach themselves to an arbitrary server, but may switch servers independently at random instants of time in an attempt to improve their service rate. This approach to load balancing contrasts with traditional approaches where clients make smart server selections upon arrival (e.g., Join-the-Shortest-Queue policy and variants thereof). Load resampling is particularly relevant in scenarios where clients cannot predict the load of a server before being actually attached to it. An important example is in wireless spectrum sharing where clients try to share a set of frequency bands in a distributed manner. We first analyze the natural Random Local Search (RLS) strategy. Under this strategy, after sampling a new server randomly, clients only switch to it if their service rate is improved. In closed systems, where the client population is fixed, we derive tight estimates of the time it takes under RLS strategy to balance the load across servers. We then study open systems where clients arrive according to a random process and leave the system upon service completion. In this scenario, we analyze how client migrations within the system interact with the system dynamics induced by client arrivals and departures. We compare the load-aware RLS strategy to a load-oblivious strategy in which clients just randomly switch server without accounting for the server loads. Surprisingly, we show that both load-oblivious and load-aware strategies stabilize the system whenever this is at all possible. We use large-system asymptotics to characterize system performance, and augment this with simulations, which suggest that the average client sojourn time under the load-oblivious strategy is not considerably reduced when clients apply smarter load-aware strategies.

  • 18. Gast, N.
    et al.
    Le Boudec, J. -Y
    Proutière, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Tomozei, D. -C
    Impact of storage on the efficiency and prices in real-time electricity markets2013In: e-Energy 2013 - Proceedings of the 4th ACM International Conference on Future Energy Systems, Association for Computing Machinery (ACM), 2013, p. 15-26Conference paper (Refereed)
    Abstract [en]

    We study the effect of energy-storage systems in dynamic real-time electricity markets. We consider that demand and renewable generation are stochastic, that real-time production is affected by ramping constraints, and that market players seek to selfishly maximize their profit. We distinguish three scenarios, depending on the owner of the storage system: (A) the supplier, (B) the consumer, or (C) a stand-alone player. In all cases, we show the existence of a competitive equilibrium when players are price-takers (they do not affect market prices). We further establish that under the equilibrium price process, players' selfish responses coincide with the social welfare-maximizing policy computed by a (hypothetical) social planner. We show that with storage the resulting price process is smoother than without. We determine empirically the storage parameters that maximize the players' revenue in the market. In the case of consumer-owned storage, or a stand-alone storage operator (scenarios B and C), we find that they do not match socially optimal parameters. We conclude that consumers and the stand-alone storage operator (but not suppliers) have an incentive to under-dimension their storage system. In addition, we determine the scaling laws of optimal storage parameters as a function of the volatility of demand and renewables. We show, in particular, that the optimal storage energy capacity scales as the volatility to the fourth power.

  • 19. Gummadi, R.
    et al.
    Key, P. B.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Optimal bidding strategies in dynamic auctions with budget constraints2011In: Allerton Conference on Communication, Control, and Computing, 2011, p. 588-Conference paper (Refereed)
    Abstract [en]

    We consider the problem of a bidder with limited budget competing in a series of second-price auctions. A motivating example is that of sponsored search auctions, where advertisers bid in a sequence of repeated generalized second price auctions. To characterize the optimal bidding strategy, we formulate the problem as a discounted Markov Decision Process, and provide explicit solutions when the bidder is involved in a large number of auctions.

  • 20. Gunawardena, D.
    et al.
    Karagiannis, T.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Santos-Neto, E.
    Vojnovic, M.
    Scoop: Decentralized and opportunistic multicasting of information streams2011In: Proceedings of the Annual International Conference on Mobile Computing and Networking, 2011, p. 169-180Conference paper (Refereed)
    Abstract [en]

    We consider the problem of delivering information streams to interested mobile users, leveraging both access to the infrastructure and device-to-device data transfers. The goal is to design practical relaying algorithms that aim at optimizing a global system objective that accounts for two important aspects: first, the user interest in content with respect to its type and delivery time; and, second, resource constraints such as storage and transmission costs. We first examine a set of real-world datasets reporting contacts between users moving in relatively restricted geographic areas (e.g. a city). These datasets provide evidence that significant performance gains can be achieved by extending the information dissemination from one to two hops, and that using longer paths only brings marginal benefits. We also show that correlation of delays through different paths is typically significant, thus asking for system design that would allow for general user mobility. We then propose a class of relaying strategies (referred to as SCOOP) that aim at optimizing a global system objective, are fully decentralized, require only locally observable states by individual devices, and allow for general user mobility. These properties characterize a practical scheme whose efficiency is evaluated using real-world mobility traces.

  • 21. Hegde, N.
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Simulation-based optimization algorithms with applications to dynamic spectrum access2012In: 2012 46th Annual Conference on Information Sciences and Systems, CISS 2012, IEEE , 2012, p. 6310766-Conference paper (Refereed)
    Abstract [en]

    Wireless systems operating on the unlicensed part of the radio spectrum (e.g. WiFi and their evolutions) must share a (potentially large) number of frequency bands or channels in a decentralized manner. This task is complicated by fading and interference, i.e., the throughput achieved on each link depends on the quality and the level of congestion of the selected channel. In this paper, we propose and analyze decentralized protocols that aim at achieving utility-optimal allocations of spectrum resources. We first address the problem of finding an optimal static channel allocation (a classical channel assignment problem). We illustrate how optimal algorithms based on simple reversible Monte Carlo Markov Chain (MCMC) methods can be designed. We also evaluate the mixing time of these algorithms. We then consider scenarios where scheduling and channel selection algorithms operate at the same time-scale and have to be designed jointly. We formulate the corresponding optimization problem and combine CSMA protocols and MCMC methods to devise optimal decentralized scheduling and channel selection algorithms. The proposed algorithms differ from existing algorithms as they mimic centralized steepest coordinate ascent methods, yielding faster convergence.

  • 22. Hegde, N.
    et al.
    Proutière, Alexandre
    Message from the program chairs2016Conference paper (Refereed)
  • 23. Hegde, Nidhi
    et al.
    Proutiere, Alexandre
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    Performance analysis of wireless multihop data networks2007In: Wireless Systems and Mobility in Next Generation Internet / [ed] GarciaVidal, J; CerdaAlabern, L, 2007, Vol. 4396, p. 1-11Conference paper (Refereed)
    Abstract [en]

    We consider wireless multihop data networks with random multi-access mechanisms at the MAC layer. In general, our aim is to study the performance as perceived by users in a dynamic setting where data flows are generated randomly by users and cease upon completion. This task comprises two major difficulties: first, the behavior of random multi-access algorithms at slot-level in a multi-hop network is even more complex than in the case of a single hop hotspot. Second, in order to study user-level performance accounting for a dynamic population of flows, one has to first characterize the so-called rate region when the population is fixed. The rate region is defined by the set of rates at which the various active users can generate packets without inducing any instabilities in the network. Since links interact with each other through interference, characterizing the rate region is as difficult as studying the behavior of a set of interacting queues. In addition, the behavior of the congestion control algorithm must be taken into account since it impacts the set of active links and thus the interference. We propose a model, based on the so-called mean field approach, that circumvents both difficulties and allows the derivation of explicit expressions for the rate region.

  • 24.
    Jeong, Jaeseong
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Leconte, M.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Cluster-aided mobility predictions2016In: Proceedings - IEEE INFOCOM, IEEE conference proceedings, 2016Conference paper (Refereed)
    Abstract [en]

    Predicting the future location of users in wireless networks has numerous applications, and can help service providers to improve the quality of service perceived by their clients. The location predictors proposed so far estimate the next location of a specific user by inspecting the past individual trajectories of this user. As a consequence, when the training data collected for a given user is limited, the resulting prediction is inaccurate. In this paper, we develop cluster-aided predictors that exploit past trajectories collected from all users to predict the next location of a given user. These predictors rely on clustering techniques and extract from the training data similarities among the mobility patterns of the various users to improve the prediction accuracy. Specifically, we present CAMP (Cluster-Aided Mobility Predictor), a cluster-aided predictor whose design is based on recent non-parametric Bayesian statistical tools. CAMP is robust and adaptive in the sense that it exploits similarities in users' mobility only if such similarities are really present in the training data. We analytically prove the consistency of the predictions provided by CAMP, and investigate its performance using two large-scale datasets. CAMP significantly outperforms existing predictors, and in particular those that only exploit individual past trajectories.

  • 25. Lelarge, Marc
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Talebi Mazraeh Shahi, Mohammad Sadegh
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Spectrum Bandit Optimization2013In: 2013 IEEE Information Theory Workshop, ITW 2013, IEEE conference proceedings, 2013, p. 6691221-Conference paper (Refereed)
    Abstract [en]

    We consider the problem of allocating radio channels to links in a wireless network. Links interact through interference, modelled as a conflict graph (i.e., two interfering links cannot be simultaneously active on the same channel). We aim at identifying the channel allocation maximizing the total network throughput over a finite time horizon. Should we know the average radio conditions on each channel and on each link, an optimal allocation would be obtained by solving an Integer Linear Program (ILP). When radio conditions are unknown a priori, we look for a sequential channel allocation policy that converges to the optimal allocation while minimizing on the way the throughput loss or regret due to the need for exploring suboptimal allocations. We formulate this problem as a generic linear bandit problem, and analyze it in a stochastic setting where radio conditions are driven by a i.i.d. stochastic process, and in an adversarial setting where radio conditions can evolve arbitrarily. We provide, in both settings, algorithms whose regret upper bounds outperform those of existing algorithms.

  • 26. Li, Bo
    et al.
    Wu, Junfeng
    Qi, Hongsheng
    Proutiere, Alexandre
    KTH, School of Electrical Engineering and Computer Science (EECS), Automatic Control.
    Shi, Guodong
    Boolean Gossip Networks2018In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 26, no 1, p. 118-130Article in journal (Refereed)
    Abstract [en]

    This paper proposes and investigates a Boolean gossip model as a simplified but non-trivial probabilistic Boolean network. With positive node interactions, in view of standard theories from Markov chains, we prove that the node states asymptotically converge to an agreement at a binary random variable, whose distribution is characterized for large-scale networks by mean-field approximation. Using combinatorial analysis, we also successfully count the number of communication classes of the positive Boolean network explicitly in terms of the topology of the underlying interaction graph, where remarkably minor variation in local structures can drastically change the number of network communication classes. With general Boolean interaction rules, emergence of absorbing network Boolean dynamics is shown to be determined by the network structure with necessary and sufficient conditions established regarding when the Boolean gossip process defines absorbing Markov chains. Particularly, it is shown that for the majority of the Boolean interaction rules, except for nine out of the total 2(16) - 1 possible nonempty sets of binary Boolean functions, whether the induced chain is absorbing has nothing to do with the topology of the underlying interaction graph, as long as connectivity is assumed. These results illustrate the possibilities of relating dynamical properties of Boolean networks to graphical properties of the underlying interactions.

  • 27.
    Liu, Jiaping
    et al.
    Department of Electrical Engineering, Princeton University, NJ.
    Proutière, Alexandre
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    Yi, Yung
    Department of Electrical Engineering, Princeton University, NJ.
    Chiang, Mung
    Department of Electrical Engineering, Princeton University, NJ.
    Poor, H. Vincent
    Department of Electrical Engineering, Princeton University, NJ.
    Flow level Stability of Data Networks with Nonconvex and Time-varying rate regions2007In: SIGMETRICS'07: PROCEEDINGS OF THE 2007 INTERNATIONAL CONFERENCE ON MEASUREMENT & MODELING OF COMPUTER SYSTEMS, Association for Computing Machinery , 2007, p. 239-250Conference paper (Refereed)
    Abstract [en]

    In this paper we characterize flow-level stochastic stability for networks with non-convex or time-varying rate regions underresource allocation based on utility maximization. Similar to prior works on flow-level stability, we consider exogenous data arrivals with finite workloads. However, to model many realistic situations, the rate region, which constrains the feasibility of resource allocation, may be either non-convex or time-varying. When the rate region is fixed but non-convex, we derive sufficient and necessary conditions for stability, which coincide when the set of allocated rate vectors has continuous contours. When the rate region is time-varying according to some stationary, ergodic process, we derive the precise stability region. In both cases,the size of the stability region depends on the resource allocation policy, in particular, on the fairness parameter in ∝-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes, independently of the value of the fairness parameter. We further investigate the tradeoff between fairness and stability when rate region is non-convex or time-varying. Numerical examples of both wired and wireless networks are provided to illustrate the new stability regions and tradeoffs proved in the paper.

  • 28.
    Magureanu, Stefan
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Combes, Richard
    Supelec, France.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control. INRIA, France.
    Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms2014Conference paper (Refereed)
    Abstract [en]

    We consider stochastic multi-armed bandit problems where the expected reward is a Lipschitzfunction of the arm, and where the set of arms is either discrete or continuous. For discrete Lipschitzbandits, we derive asymptotic problem specific lower bounds for the regret satisfied by anyalgorithm, and propose OSLB and CKL-UCB, two algorithms that efficiently exploit the Lipschitzstructure of the problem. In fact, we prove that OSLB is asymptotically optimal, as its asymptoticregret matches the lower bound. The regret analysis of our algorithms relies on a new concentrationinequality for weighted sums of KL divergences between the empirical distributions of rewards andtheir true distributions. For continuous Lipschitz bandits, we propose to first discretize the actionspace, and then apply OSLB or CKL-UCB, algorithms that provably exploit the structure efficiently.This approach is shown, through numerical experiments, to significantly outperform existing algorithmsthat directly deal with the continuous set of arms. Finally the results and algorithms areextended to contextual bandits with similarities.

  • 29.
    Magureanu, Stefan
    et al.
    KTH.
    Isaksson, M.
    Proutiere, Alexandre
    KTH.
    Zhang, B.
    Online learning of optimally diverse rankings2018In: SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery (ACM), 2018, p. 47-49Conference paper (Refereed)
    Abstract [en]

    Search engines answer users’ queries by listing relevant items (e.g. documents, songs, products, web pages, ...). These engines rely on algorithms that learn to rank items so as to present an ordered list maximizing the probability that it contains relevant item. The main challenge in the design of learning-to-rank algorithms stems from the fact that queries often have different meanings for different users. In absence of any contextual information about the query, one often has to adhere to the diversity principle, i.e., to return a list covering the various possible topics or meanings of the query. To formalize this learning-to-rank problem, we propose a natural model where (i) items are categorized into topics, (ii) users find items relevant only if they match the topic of their query, and (iii) the engine is not aware of the topic of an arriving query, nor of the frequency at which queries related to various topics arrive, nor of the topic-dependent click-through-rates of the items. For this problem, we devise LDR (Learning Diverse Rankings), an algorithm that efficiently learns the optimal list based on users’ feedback only. We show that after T queries, the regret of LDR scales as O((N - L) log(T)) where N is the number of all items. This scaling cannot be improved, i.e., LDR is order optimal.

  • 30. Massoulié, L.
    et al.
    Ohannessian, M. I.
    Proutière, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Greedy-Bayes for targeted news dissemination2015In: Performance Evaluation Review, ACM Press, 2015, Vol. 43, no 1, p. 285-296Conference paper (Refereed)
    Abstract [en]

    This work addresses user targeting for news content delivery. Specifically, we wish to disseminate a fresh news content, whose topic is yet unknown, to all interested users, while "spamming" a minimum number of uninterested users. We formulate this as an online stochastic optimization problem that extends in several ways the classical multi-armed bandit problem. We introduce Greedy-Bayes, a policy with appealing robustness properties. We establish optimal scaling of a suitably defined regret measure in various scenarios of interest. To that end we develop an original proof technique based on martingale concentration inequalities. Numerical experiments show that Greedy-Bayes improves upon Thompson sampling, the state-of-the-art algorithm for bandit problems. Our analysis further implies that low regret can only be achieved if the assessment of content relevance for one user leverages feedback from users with widely distinct tastes. This impacts the design of efficient news dissemination platforms: existing systems typically do not leverage such negative feedback and could hence be improved upon with adequate extensions.

  • 31.
    Mueller, Matias I.
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Valenzuela, Patricio Esteban
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Rojas, Cristian R.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    A stochastic multi-armed bandit approach to nonparametric H-infinity-norm estimation2017In: 2-s2.0-85046136421, Institute of Electrical and Electronics Engineers (IEEE), 2017, p. 4632-4637Conference paper (Refereed)
    Abstract [en]

    We study the problem of estimating the largest gain of an unknown linear and time-invariant filter, which is also known as the H-infinity norm of the system. By using ideas from the stochastic multi-armed bandit framework, we present a new algorithm that sequentially designs an input signal in order to estimate this quantity by means of input-output data. The algorithm is shown empirically to beat an asymptotically optimal method, known as Thompson Sampling, in the sense of its cumulative regret function. Finally, for a general class of algorithms, a lower bound on the performance of finding the H-infinity norm is derived.

  • 32.
    Owrang, Arash
    et al.
    KTH, School of Electrical Engineering (EES), Information Science and Engineering. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Malek-Mohammadi, Mohammadreza
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Jansson, Magnus
    KTH, School of Electrical Engineering (EES), Information Science and Engineering. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Consistent Change Point Detection for Piecewise Constant Signals With Normalized Fused LASSO2017In: IEEE Signal Processing Letters, ISSN 1070-9908, E-ISSN 1558-2361, Vol. 24, no 6, p. 799-803Article in journal (Refereed)
    Abstract [en]

    We consider the problem of offline change point detection from noisy piecewise constant signals. We propose normalized fused LASSO (FL), an extension of the FL, obtained by normalizing the columns of the sensing matrix of the LASSO equivalent. We analyze the performance of the proposed method, and in particular, we show that it is consistent in detecting change points as the noise variance tends to zero. Numerical experiments support our theoretical findings.

  • 33.
    Petrosyan, Vahan
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Viral Clustering: A Robust Method to Extract Structures in Heterogeneous Datasets2016Conference paper (Refereed)
    Abstract [en]

    Cluster validation constitutes one of the most challenging problems in unsupervised cluster analysis. For example, identifying the true number of clusters present in a dataset has been investigated for decades, and is still puzzling researchers today. The difficulty stems from the high variety of the dataset characteristics. Some datasets exhibit a strong structure with a few well-separated and normally distributed clusters, but most often real-world datasets contain possibly many overlapping non-gaussian clusters with heterogeneous variances and shapes. This calls for the design of robust clustering algorithms that could adapt to the structure of the data and in particular accurately guess the true number of clusters. They have recently been interesting attempts to design such algorithms, e.g. based on involved non-parametric statistical inference techniques. In this paper, we develop Viral Clustering (VC), a simple algorithm that jointly estimates the number of clusters and outputs clusters. The VC algorithm relies on two antagonist and interacting components. The first component tends to regroup neighbouring samples together, while the second component tends to spread samples in various clusters. This spreading component is performed using an analogy with the way virus spread over networks. We present extensive numerical experiments illustrating the robustness of the VC algorithm, and its superiority compared to existing algorithms.

  • 34.
    Rabi, Maben
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Stabellini, Luca
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    Proutiere, Alexandre
    Johansson, Mikael
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Networked estimation under contention-based medium access2010In: International Journal of Robust and Nonlinear Control, ISSN 1049-8923, E-ISSN 1099-1239, Vol. 20, no 2, p. 140-155Article in journal (Refereed)
    Abstract [en]

    This paper studies networked estimation over a communication channel shared by a contention-based medium access protocol. A collection of N identical and physically decoupled scalar systems are sampled without sensor noise and transmitted over a common channel, using a contention-based medium access mechanism. We first carry out a calculation of the average distortion in estimation with irregular samples. Given the rate of packet generation at sensors, we characterize the traffic characteristics of the some contention-based MAC schemes. This lets us derive the statistics of inter-arrival times which in turn allows us to compute the packet loss rates and also the statistics of delay within a sample period. Using these results, we track the estimation performance as the sample generation rate and the number of contending nodes are varied. We provide a heuristic rule-of-thumb for choosing the sampling interval which minimizes the average distortion. By combining the network traffic characterization with that of the estimation performance, we show this rule performs pretty well. Carrying along the same lines, we are able to compute the scaling limits of estimation performance with respect to the number of contending nodes.

  • 35. Radunovic, B.
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    On downlink capacity of cellular data networks with WLAN/WPAN relays2013In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 21, no 1, p. 286-296Article in journal (Refereed)
    Abstract [en]

    We consider the downlink of a cellular network supporting data traffic in which each user is equipped with the same type of IEEE 802.11-like WLAN or WPAN interface used to relay packets to further users. We are interested in the design guidelines for such networks and how much capacity improvements the additional relay layer can bring. A first objective is to provide a scheduling/relay strategy that maximizes the network capacity. Using theoretical analysis, numerical evaluation, and simulations, we find that when the number of active users is large, the capacity-achieving strategy divides the cell into two areas: one closer to the base station where the relay layer is always saturated and some nodes receive traffic through both direct and relay links, and the farther one where the relay is never saturated and the direct traffic is almost nonexistent. We also show that it is approximately optimal to use fixed relay link lengths, and we derive this length. We show that the obtained capacity is independent of the cell size (unlike in traditional cellular networks). Based on our findings, we propose simple decentralized routing and scheduling protocols. We show that in a fully saturated network our optimized protocol substantially improves performance over the protocols that use naive relay-only or direct-only policies.

  • 36. Radunovic, B.
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Gunawardena, D.
    Key, P.
    Dynamic channel, rate selection and scheduling for white spaces2011In: Proc. Conf. Emerg. Networking Exp. Technol., CoNEXT, 2011Conference paper (Refereed)
    Abstract [en]

    We investigate dynamic channel, rate selection and scheduling for wireless systems which exploit the large number of channels available in the White-space spectrum. We first present measurements of radio channel characteristics from an indoor testbed operating in the 500 to 600MHz band and comprising 11 channels. We observe significant and unpredictable (non-stationary) variations in the quality of these channels, and demonstrate the potential benefit in throughput from tracking the best channel and also from optimally adapting the transmission rate. We propose adaptive learning schemes able to efficiently track the best channel and rate for transmission, even in scenarios with non-stationary channel condition variations. We also describe a joint scheduling scheme for providing fairness in an Access Point scenario. Finally, we implement the proposed adaptive scheme in our testbed, and demonstrate that it achieves significant throughput improvement (typically from 40% to 100%) compared to traditional fixed channel selection schemes.

  • 37.
    Radunovic, Bozidar
    et al.
    Microsoft Research, Cambridge.
    Proutière, Alexandre
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    On Downlink Capacity of Cellular Data Networks with WLAN/WPAN Relays2007In: 2007 5TH INTERNATIONAL SYMPOSIUM ON MODELING AND OPTIMIZATION IN MOBILE, AD HOC AND WIRELESS NETWORKS AND WORKSHOPS, VOLS 1-2, IEEE , 2007, p. 419-425Conference paper (Refereed)
    Abstract [en]

    We consider the downlink of a cellular network supporting data traffic. In addition to the direct traffic from the base-station, each user is equipped with the same type of 802.11-like WLAN or WPAN interface that is used to relay packets to further users and hence to improve the performance of the overall network. We are interested in analyzing what are the design guidelines for such networks and how much capacity improvements can the additional relay layer bring, in comparison to cellular networks. We consider a realistic dynamic setting where users randomly initiate downloads and leave the system upon transfer completion. A first objective is to provide a scheduling/relay strategy that maximizes the network capacity, which is the traffic in bit/s/cell that the network can support. We find that, regardless of the spatial traffic distribution, when the cell approaches saturation (the number of active users is large), the capacity-achieving strategy divides the cell into two areas: one closer to the base-station where the relay layer is always saturated and some nodes receive traffic through both direct and relay links, and the further one where the relay is never saturated and the direct traffic does not exist. We further give a simple algorithm to calculate the cell capacity. The obtained capacity is shown to be independent of the cell size (unlike in traditional cellular networks), and it is 20% -60% higher than already proposed relay architectures.

  • 38. Shi, G.
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Johansson, Mikael
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Baras, John
    Johansson, Karl Henrik
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Emergent Behaviors over Signed Random Dynamical Networks: state-flipping model2015In: IEEE Transactions on Control of Network Systems, ISSN 2325-5870, Vol. 2, no 2, p. 142-153Article in journal (Refereed)
    Abstract [en]

    Recent studies from social, biological, and engineering network systems have drawn attention to the dynamics over signed networks, where each link is associated with a positive/negative sign indicating trustful/mistrustful, activator/ inhibitor, or secure/malicious interactions. We study asymptotic dynamical patterns that emerge among a set of nodes that interact in a dynamically evolving signed random network. Node interactions take place at random on a sequence of deterministic signed graphs. Each node receives positive or negative recommendations from its neighbors depending on the sign of the interaction arcs, and updates its state accordingly. Recommendations along a positive arc follow the standard consensus update. As in the work by Altafini, negative recommendations use an update where the sign of the neighbor state is flipped. Nodes may weight positive and negative recommendations differently, and random processes are introduced to model the time-varying attention that nodes pay to these recommendations. Conditions for almost sure convergence and divergence of the node states are established. We show that under this so-called state-flipping model, all links contribute to a consensus of the absolute values of the nodes, even under switching sign patterns and dynamically changing environment. A no-survivor property is established, indicating that every node state diverges almost surely if the maximum network state diverges.

  • 39. Shi, G.
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Johansson, Mikael
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Baras, John S.
    Johansson, Karl H.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Emergent behaviors over signed random dynamical networks: Relative-state-flipping model2015In: IEEE Transactions on Control of Network Systems, ISSN 2325-5870, Vol. PP, no 99, article id 7349158Article in journal (Refereed)
    Abstract [en]

    We study asymptotic dynamical patterns that emerge among a set of nodes interacting in a dynamically evolving signed random network, where positive links carry out standard consensus and negative links induce relative-state flipping. A sequence of deterministic signed graphs defines potential node interactions that take place independently. Each node receives a positive recommendation consistent with the standard consensus algorithm from its positive neighbors, and a negative recommendation defined by relative-state flipping from its negative neighbors. After receiving these recommendations, each node puts a deterministic weight to each recommendation, and then encodes these weighted recommendations in its state update through stochastic attentions defined by two Bernoulli random variables. We establish a number of conditions regarding almost sure convergence and divergence of the node states. We also propose a condition for almost sure state clustering for essentially weakly balanced graphs, with the help of several martingale convergence lemmas. Some fundamental differences on the impact of the deterministic weights and stochastic attentions to the node state evolution are highlighted between the current relative-stateflipping model and the state-flipping model considered in Shi et al., IEEE Transaction on Control of Network Systems, 2015.

  • 40. Shi, Guodong
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Automatic Control.
    Johansson, Karl Henrik
    NETWORK SYNCHRONIZATION WITH CONVEXITY2015In: SIAM Journal of Control and Optimization, ISSN 0363-0129, E-ISSN 1095-7138, Vol. 53, no 6, p. 3562-3583Article in journal (Refereed)
    Abstract [en]

    In this paper, we establish a few new synchronization conditions for complex networks with nonlinear and nonidentical self-dynamics with switching directed communication graphs. In light of the recent works on distributed subgradient methods, we impose integral convexity for the nonlinear node self-dynamics in the sense that the self-dynamics of a given node is the gradient of some concave function corresponding to that node. The node couplings are assumed to be linear but with switching directed communication graphs. Several sufficient and/or necessary conditions are established for exact or approximate synchronization over the considered complex networks. These results show when and how nonlinear node self-dynamics may cooperate with the linear diffusive coupling, which eventually leads to network synchronization conditions under relaxed connectivity requirements.

  • 41. Shi, Guodong
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Johansson, Mikael
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Baras, John S.
    Johansson, Karl H.
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    The Evolution of Beliefs over Signed Social Networks2016In: Operations Research, ISSN 0030-364X, E-ISSN 1526-5463, Vol. 64, no 3, p. 585-604Article in journal (Refereed)
    Abstract [en]

    We study the evolution of opinions (or beliefs) over a social network modeled as a signed graph. The sign attached to an edge in this graph characterizes whether the corresponding individuals or end nodes are friends (positive links) or enemies (negative links). Pairs of nodes are randomly selected to interact over time, and when two nodes interact, each of them updates its opinion based on the opinion of the other node and the sign of the corresponding link. This model generalizes the DeGroot model to account for negative links: when two adversaries interact, their opinions go in opposite directions. We provide conditions for convergence and divergence in expectation, in mean-square, and in almost sure sense and exhibit phase transition phenomena for these notions of convergence depending on the parameters of the opinion update model and on the structure of the underlying graph. We establish a no-survivor theorem, stating that the difference in opinions of any two nodes diverges whenever opinions in the network diverge as a whole. We also prove a live-or-die lemma, indicating that almost surely, the opinions either converge to an agreement or diverge. Finally, we extend our analysis to cases where opinions have hard lower and upper limits. In these cases, we study when and how opinions may become asymptotically clustered to the belief boundaries and highlight the crucial influence of (strong or weak) structural balance of the underlying network on this clustering phenomenon.

  • 42.
    Shi, Guodong
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Johansson, Mikael
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Johansson, Karl Henrik
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Randomized consensus with attractive and repulsive links2013In: 2013 IEEE 52nd Annual Conference on Decision and Control (CDC), IEEE conference proceedings, 2013, p. 2599-2604Conference paper (Refereed)
    Abstract [en]

    We study convergence properties of a randomized consensus algorithm over a graph with both attractive and repulsive links. At each time instant, a node is randomly selected to interact with a random neighbor. Depending on if the link between the two nodes belongs to a given subgraph of attractive or repulsive links, the node update follows a standard attractive weighted average or a repulsive weighted average, respectively. The repulsive update has the opposite sign of the standard consensus update. In this way, it counteracts the consensus formation and can be seen as a model of link faults or malicious attacks in a communication network, or the impact of trust and antagonism in a social network. Various probabilistic convergence and divergence conditions are established. A threshold condition for the strength of the repulsive action is given for convergence in expectation: when the repulsive weight crosses this threshold value, the algorithm transits from convergence to divergence. An explicit value of the threshold is derived for classes of attractive and repulsive graphs. The results show that a single repulsive link can sometimes drastically change the behavior of the consensus algorithm. They also explicitly show how the robustness of the consensus algorithm depends on the size and other properties of the graphs.

  • 43.
    Shi, Guodong
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Proutière, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Johansson, Karl Henrik
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Continuous-time distributed optimization of homogenous dynamics2013In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, IEEE conference proceedings, 2013, p. 520-527Conference paper (Refereed)
    Abstract [en]

    This paper makes an attempt to explore the fundamental properties of distributed methods for minimizing a sum of objective functions with each component only known to a particular node, given a certain level of node knowledge and computation capacity. The information each node receives from its neighbors can be any nonlinear function of its neighbors' states as long as the function takes value zero within the local consensus manifold. Each node also observes the gradient of its own objective function at its current state. The update dynamics of each node is a first-order integrator. The admissible control input of each node is homogeneous, given by a binary function with each variable corresponding to the neighboring term and the gradient term, respectively. The function determining the control law is assumed to be injective when the first variable is fixed to zero. It is proven that there exists a control rule which guarantees global optimal consensus if and only if the solution sets of the local objectives admit a nonempty intersection set for fixed strongly connected graphs. Then we show that for any tolerated error, we can find a simple control rule that guarantees global optimal consensus within this error for fixed, bidirectional, and connected graphs under mild conditions. For time-varying graphs, we show that optimal consensus can always be achieved by a simple control rule as long as the graph is uniformly jointly strongly connected and the nonempty intersection condition holds. The results illustrate that nonempty intersection for the local optimal solution sets is a critical condition for distributed optimization using consensus processing to connect the information over the nodes.

  • 44.
    Stabellini, Luca
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    Proutiere, Alexandre
    KTH, School of Information and Communication Technology (ICT), Communication Systems, CoS.
    Evaluating delay and energy in sensor networks with sporadic and correlated traffic2007In: 7thScandinavian Workshop on Wireless Ad-Hoc Networks (ADHOC ´07), 2007Conference paper (Refereed)
    Abstract [en]

    Wireless sensor networks are usually comprised of a set of sensors that are equipped with a wireless transmitter/ receiver and of a set of data sinks where the information gathered by sensors should be treated. The delay, from the time when events are sensed to the time when the information arrives at sinks, has to satisfy some specific requirements. These requirements depend on the underlying application targeted by the network, and typically consist in ensuring that the delay is less than a pre-defined threshold with high probability. A common issue in sensor networks is then to design distributed scheduling and routing algorithms so as to maximize the network lifetime while guaranteeing the delay requirements. This optimization problem has to account for the particular nature of traffic in sensor networks: the traffic there is (i) sporadic, in the sense that sensors do not have always packets to transmit, (ii) correlated, meaning that the sensors belonging to a common neighborhood may generate traffic simultaneously (e.g., a network sensing temperatures typically exhibits correlated traffic). In this work, we aim at providing analytical and simulation tools able to quantify the packet delays in sensor networks with sporadic and correlated traffic, for various types of distributed scheduling protocols. These tools may then be used to design protocols maximizing the lifetime of delay-constrained networks.

  • 45.
    Talebi Mazraeh Shahi, Mohammad Sadegh
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS).
    Proutiere, Alexandre
    KTH, School of Electrical Engineering and Computer Science (EECS).
    Learning proportionally fair allocations with low regret2018In: SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery (ACM), 2018, p. 50-52Conference paper (Refereed)
    Abstract [en]

    We address the problem of learning Proportionally Fair (PF) allocations in parallel server systems with unknown service rates. We provide the first algorithms, to our knowledge, for learning such allocations with sub-linear regret

  • 46.
    Talebi Mazraeh Shahi, Mohammad Sadegh
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.
    Zou, Zhenhua
    Ericsson Res, SE-16483 Stockholm, Sweden..
    Combes, Richard
    Cent Supelec L2S, Telecommun Dept, F-91192 Gif Sur Yvette, France..
    Proutiere, Alexandre
    KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.
    Johansson, Mikael
    KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.
    Stochastic Online Shortest Path Routing: The Value of Feedback2018In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 63, no 4, p. 915-930Article in journal (Refereed)
    Abstract [en]

    This paper studies online shortest path routing over multihop networks. Link costs or delays are time varying and modeled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative difference of expected delay) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decisions. For each scenario, we derive a tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. Three algorithms, with a tradeoff between computational complexity and performance, are proposed. The regret upper bounds of these algorithms improve over those of the existing algorithms. We also assess numerically the performance of the proposed algorithms and compare it to that of existing algorithms.

  • 47.
    Talebi, Mohammad Sadegh
    et al.
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    An optimal algorithm for stochastic matroid bandit optimization2016In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) , 2016, p. 548-556Conference paper (Refereed)
    Abstract [en]

    The selection of leaders in leader-follower multi-agent systems can be naturally formulated as a matroid optimization problem. In this paper, we investigate the online and stochastic version of such a problem, where in each iteration or round, we select a set of leaders and then observe a random realization of the corresponding reward, i.e., of the system performance. This problem is referred to as a stochastic matroid bandit, a variant of combinatorial multi-armed bandit problems where the underlying combinatorial structure is a matroid. We consider semi-bandit feedback and Bernoulli rewards, and derive a tight and problem-dependent lower bound on the regret of any consistent algorithm. We propose KL-OSM, a computationally efficient algorithm that exploits the matroid structure. We derive a finite-time upper bound of the regret of KL-OSM that improves the performance guarantees of existing algorithms. This upper bound actually matches our lower bound, i.e., KL-OSM is asymptotically optimal. Numerical experiments attest that KL-OSM outperforms state-of-the-art algorithms in practice, and the difference in some cases is significant. Copyright © 2016, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org).

  • 48. Yun, D.
    et al.
    Ahn, S.
    Proutiere, Alexandre
    KTH.
    Shin, J.
    Yi, Y.
    Multi-armed bandit with additional observations2018In: SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery (ACM), 2018, p. 53-55Conference paper (Refereed)
    Abstract [en]

    We study multi-armed bandit (MAB) problems with additional observations, where in each round, the decision maker selects an arm to play and can also observe rewards of additional arms (within a given budget) by paying certain costs. We propose algorithms that are asymptotic-optimal and order-optimal in their regrets under the settings of stochastic and adversarial rewards, respectively.

  • 49. Yun, S. -Y
    et al.
    Lelarge, M.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control.
    Fast and memory optimal low-rank matrix approximation2015In: Advances in Neural Information Processing Systems, Neural information processing systems foundation , 2015, p. 3177-3185Conference paper (Refereed)
    Abstract [en]

    In this paper, we revisit the problem of constructing a near-optimal rank k approximation of a matrix M ∈ [0,1]m×n under the streaming data model where the columns of M are revealed sequentially. We present SLA (Streaming Low-rank Approximation), an algorithm that is asymptotically accurate, when ksk+1(M) =o(√mn) where sk+1(M) is the (k + 1)-th largest singular value of M. This means that its average mean-square error converges to 0 as m and n grow large (i.e., || M(k)-M(k)||2 F = o(mn) with high probability, where M(k) and M(k) denote the output of SLA and the optimal rank k approximation of M, respectively). Our algorithm makes one pass on the data if the columns of M are revealed in a random order, and two passes if the columns of M arrive in an arbitrary order. To reduce its memory footprint and complexity, SLA uses random sparsification, and samples each entry of M with a small probability δ. In turn, SLA is memory optimal as its required memory space scales as k(m+n), the dimension of its output. Furthermore, SLA is computationally efficient as it runs in O(δkmn) time (a constant number of operations is made for each observed entry of M), which can be as small as O(k log(m)4n) for an appropriate choice of δ and if n ≥ m.

  • 50. Yun, S. -Y
    et al.
    Proutiere, Alexandre
    KTH, School of Electrical Engineering (EES), Automatic Control. INRIA, France.
    Community detection via random and adaptive sampling2014In: Journal of machine learning research, ISSN 1532-4435, E-ISSN 1533-7928, Vol. 35, p. 138-175Article in journal (Refereed)
    Abstract [en]

    In this paper, we consider networks consisting of a finite number of non-overlapping communities. To extract these communities, the interaction between pairs of nodes may be sampled from a large available data set, which allows a given node pair to be sampled several times. When a node pair is sampled, the observed outcome is a binary random variable, equal to 1 if nodes interact and to 0 otherwise. The outcome is more likely to be positive if nodes belong to the same communities. For a given budget of node pair samples or observations, we wish to jointly design a sampling strategy (the sequence of sampled node pairs) and a clustering algorithm that recover the hidden communities with the highest possible accuracy. We consider both non-adaptive and adaptive sampling strategies, and for both classes of strategies, we derive fundamental performance limits satisfied by any sampling and clustering algorithm. In particular, we provide necessary conditions for the existence of algorithms recovering the communities accurately as the network size grows large. We also devise simple algorithms that accurately reconstruct the communities when this is at all possible, hence proving that the proposed necessary conditions for accurate community detection are also sufficient. The classical problem of community detection in the stochastic block model can be seen as a particular instance of the problems consider here. But our framework covers more general scenarios where the sequence of sampled node pairs can be designed in an adaptive manner. The paper provides new results for the stochastic block model, and extends the analysis to the case of adaptive sampling.

12 1 - 50 of 55
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf