The multiplicative weights update method: a meta-algorithm and applications
From MaRDI portal
Publication:2913806
DOI10.4086/TOC.2012.V008A006zbMATH Open1283.68414OpenAlexW2150865801MaRDI QIDQ2913806FDOQ2913806
Authors: Elad Hazan, Satyen Kale, Sanjeev Arora 
Publication date: 27 September 2012
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2012.v008a006
Recommendations
Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms (68W40) Applications of game theory (91A80) Nonnumerical algorithms (68W05)
Cites Work
Cited In (only showing first 100 items - show all)
- On the convergence time of a natural dynamics for linear programming
- On the convergence time of a natural dynamics for linear programming
- Better bin packing approximations via discrepancy theory
- Sex with no regrets: how sexual reproduction uses a no regret learning algorithm for evolutionary advantage
- Replicator dynamics: old and new
- Linear coupling: an ultimate unification of gradient and mirror descent
- Active learning for cost-sensitive classification
- Fast approximation of matroid packing and covering
- Dynamic pricing with multiple products and partially specified demand distribution
- On learning algorithms for Nash equilibria
- An SDP primal-dual algorithm for approximating the Lovász-theta function
- Deciding probabilistic automata weak bisimulation: theory and practice
- On incremental approximate saddle-point computation in zero-sum matrix games
- Learning in games with continuous action sets and unknown payoff functions
- In pursuit of the dynamic optimality conjecture
- A multiplicative weights update algorithm for MINLP
- Sublinear time algorithms for approximate semidefinite programming
- A poly-log competitive posted-price algorithm for online metrical matching on a spider
- Exponential weight approachability, applications to calibration and regret minimization
- Costly circuits, submodular schedules and approximate Carathéodory theorems
- Semi-iterative minimum cross-entropy algorithms for rare-events, counting, combinatorial and integer programming
- Approximation and online algorithms for multidimensional bin packing: a survey
- Constrained no-regret learning
- Mirror descent algorithms for minimizing interacting free energy
- Correlation clustering in data streams
- Committee polyhedral separability: complexity and polynomial approximation
- Dynamics of Bayesian updating with dependent data and misspecified models
- Multi-Finger Binary Search Trees
- Online learning of Nash equilibria in congestion games
- On the convergence of mirror descent beyond stochastic convex programming
- A Laplacian approach to \(\ell_1\)-norm minimization
- Solving MIPs via scaling-based augmentation
- Near-optimal algorithms for online matrix prediction
- Title not available (Why is that?)
- Oracle-based robust optimization via online learning
- Clarkson's algorithm for violator spaces
- Title not available (Why is that?)
- Partitioning well-clustered graphs: spectral clustering works!
- Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Title not available (Why is that?)
- Efficient semidefinite branch-and-cut for MAP-MRF inference
- Autobidding with constraints
- Parallel approximation of min-max problems
- Convergence time of power-control dynamics
- Epsilon-net method for optimizations over separable states
- Title not available (Why is that?)
- Mutation, Sexual Reproduction and Survival in Dynamic Environments
- Log-domain interior-point methods for convex quadratic programming
- Near-linear algorithms for geometric hitting sets and set covers
- From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory
- Optimal partition trees
- Predictive spreadsheet autocompletion with constraints
- Towards more practical linear programming-based techniques for algorithmic mechanism design
- Towards more practical linear programming-based techniques for algorithmic mechanism design
- A note on fractional coloring and the integrality gap of LP for maximum weight independent set
- Solving zero-sum games using best-response oracles with applications to search games
- Bounding the inefficiency of outcomes in generalized second price auctions
- Q-learning for Markov decision processes with a satisfiability criterion
- Algorithms, games, and evolution
- New error measures and methods for realizing protein graphs from distance data
- Packing trees in communication networks
- Dynamic resource allocation in the cloud with near-optimal efficiency
- Linear programming in the semi-streaming model with application to the maximum matching problem
- A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
- A natural adaptive process for collective decision-making
- Near-optimal distributed maximum flow
- Efficient primal-dual graph algorithms for MapReduce
- An improved deterministic algorithm for the online min-sum set cover problem
- No-regret learning for repeated non-cooperative games with lossy bandits
- Bandit-based task assignment for heterogeneous crowdsourcing
- A unifying learning framework for building artificial game-playing agents
- Efficient use of quantum linear system algorithms in inexact infeasible IPMs for linear optimization
- A stochastic variant of replicator dynamics in zero-sum games and its invariant measures
- Online learning of quantum states
- Efficient Kirszbraun extension with applications to regression
- Inferring Sparse Preference Lists from Partial Information
- Finding Sparse Solutions for Packing and Covering Semidefinite Programs
- Privacy and truthful equilibrium selection for aggregative games
- A practitioner’s guide to quantum algorithms for optimisation problems
- Dual space preconditioning for gradient descent
- Optimal anytime regret with two experts
- The complexity of the distributed constraint satisfaction problem
- Multi-scale online learning: theory and applications to online auctions and pricing
- The power of vertex sparsifiers in dynamic graph algorithms
- Family of chaotic maps from game theory
- Learning equilibria of a stochastic game on Gaussian interference channels with incomplete information
- Online max-min fair allocation
- SVM via saddle point optimization: new bounds and distributed algorithms
- Hedge algorithm and dual averaging schemes
- Resonator Networks, 2: Factorization Performance and Capacity Compared to Optimization-Based Methods
- Optimistic optimisation of composite objective with exponentiated update
- Asymmetric replicator dynamics on Polish spaces: invariance, stability, and convergence
- The evolutionary dynamics of soft-max policy gradient in multi-agent settings
- Fractional set cover in the streaming model
- Geometric distinguishability measures limit quantum channel estimation and discrimination
- Distributed dense subgraph detection and low outdegree orientation
- An \(\alpha \)-regret analysis of adversarial bilateral trade
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
- Solving maxmin optimization problems via population games
This page was built for publication: The multiplicative weights update method: a meta-algorithm and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913806)
