Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 9 of 9 for “"Multiplicative weights update"”.

  1. Low-stretch trees for network visualization

    … querying. In addition, we explore the use of the multiplicative weights update method to compute a distribution over low-stretch trees in order to achieve low stretch for all edges in expectation, rather than on average. We present the results of using this distribution in place of a single …

    ubc Repository record for Low-stretch trees for network visualization (opens in a new tab) Download PDF for Low-stretch trees for network visualization (opens in a new tab)

  2. Online learning in the presence of strategic adversary

    … show that a special case of AFTRL, the Accurate Multiplicative Weights Update (AMWU), can achieve last round convergence to the Nash equilibrium in self-play settings. In the third and final main chapter, we extend our results to the challenging setting of Online Markov Decision Processes …

    soton Download PDF for Online learning in the presence of strategic adversary (opens in a new tab)

  3. A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming

    … thus refine certain uses of Ellipsoid and Multiplicative-Weights Update methods. We prove our algorithms and analyses to be optimal in several aspects. Extensive experimental work is provided on the special case of maximum cut and fractional cut-covering problems. We present several …

    waterloo Repository record for A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming (opens in a new tab)

  4. Efficient Algorithms for Optimal Transport in Geometric Settings

    … time. We then couple this algorithm with the multiplicative weights update (MWU) method to obtain a near-linear time approximation algorithm for the 1-Wasserstein barycenter problem in Euclidean space. We additionally design a different near-linear time, MWU-based approximation algorithm for …

    duke Repository record for Efficient Algorithms for Optimal Transport in Geometric Settings (opens in a new tab)

  5. Bin packing, number balancing, and rescaling linear programs

    … programming. Our algorithm is based on the multiplicative weights update (MWU) method, which is a general framework that is currently of great interest in theoretical computer science. An algorithm for linear programming based on MWU was known previously, but was not polynomial time -- we …

    washington Repository record for Bin packing, number balancing, and rescaling linear programs (opens in a new tab)

  6. Quantum Online Learning

    … a projective version of the symmetric cone multiplicative weights update algorithm that achieves sublinear regret when learning states of generalized probabilistic theories. We consider the task of detecting changes in sequences of unknown quantum states with a constraint of no false …

    vt Repository record for Quantum Online Learning (opens in a new tab)

  7. Strategic resource coordination for detecting illegal activity

    … guarantees: a Column Generation and a Multiplicative Weights Update (MWU) algorithm with approximate best responses. Each iteration of our MWU algorithm requires computing a projection under the unnormalized relative entropy, for which we provide a closed-form solution and a linear-time …

    gatech Repository record for Strategic resource coordination for detecting illegal activity (opens in a new tab)

  8. Study on the effect of misinformation in multi-agent systems

    … are publicly announced, thus allowing agents to update their information. Consequently, agents may re-evaluate their behaviour in the next time step. We call this process Adaptation Procedure, and we provide various results regarding its properties. Further, we present a complete analysis of the …

    greece Repository record for Study on the effect of misinformation in multi-agent systems (opens in a new tab)

  9. Quantum Information and Variants of Interactive Proof Systems

    … an algorithmic technique known as the matrix multiplicative weights update method to solve a semidefinite program that characterizes the success probability of the quantum prover. (2) We show that polynomially many logarithmic-size unentangled quantum proofs are no more powerful than a …

    waterloo Repository record for Quantum Information and Variants of Interactive Proof Systems (opens in a new tab)