The Multiplicative Weights Update Method

The Multiplicative Weights Update Method

A Combinatorial, Primal-Dual Approach to Semidefinite Programs Satyen Kale Microsoft Research Joint work with Sanjeev Arora Princeton University The Ubiquity of Semidefinite Programming Max Cut [GW95] Balanced Partitioning [ARV04] dx(t)/dt = Ax(t) Control Theory SDP (a :b) (:a c) (a b) (:c b) 1 0 0 0 1 1 0 1 Constraint Satisfaction [ACMM05]

Graph Coloring [KMS98, ACC06] Algorithms for SDP Ellipsoid method [GLS81]: O(n8) iterations Interior point methods [NN90, A95]: O(m(n3 + m)) time Combinatorial, Primal-Dual algorithms A1 X b1 Am X bm i wi(Ai X bi) 0 Lagrangian Relaxation [KL95], [AHK05]: Reduction to eigenvectors poly(1/) dependence on , limits applicability (e.g. Sparsest Cut) Primal-Dual algorithms for LP: Multicommodity Flows Unit capacities

Objective: Maximize total flow, while respecting edge capacities Primal-Dual algorithms for LP: Multicommodity Flows 11 + 1 1 1 1 Edge weights we = 1 Repeat until some e reaches capacity: Find shortest path p Route 2/log(m) flow on p Update w for all e 2 p as e 1 1

1 1 1 1 1 1 we we (1 + ) 1 Output flow. Thm [GK98]: Stops in (m) rounds with (1 2)OPT flow. Total running time is (m2). Primal-Dual algorithms for LP: Multicommodity Flows 1. Primal-Dual algorithm Edge weights we = 1

Repeat until some e reaches capacity: Find shortest path p Route 2/log(m) flow on p Update w for all e 2 p as e 2. Combinatorial 3. Multiplicative Weights Update Rule we we (1 + ) Output flow. Thm [GK98]: Stops in (m) rounds with (1 2)OPT flow. Total running time is (m2). Starting point for our work: Analogous primal-dual algorithms for SDP?

Difficulties: Positive semidefiniteness hard to maintain Rounding algorithms exploit geometric structure (e.g. negative-type metrics) Matrix operations inefficient to implement Our work: a generic scheme that yields fast, combinatorial, primal-dual algorithms for various optimization problems using SDP Our Results: Primal-Dual algorithms Problem Previous best: O(log n) apx [AHK04] Our alg.:

O(log n) apx Our alg.: O(log n) apx (n2) (n2) (m + n1.5) [AHK04] (n2) (n2) (m + n1.5) Directed Sparsest Cut (n4.5) 2+) (m1.5 + n2+ (m1.5)

Directed Balanced Sep. (n4.5) 2+) (m1.5 + n2+ (m1.5) Undirected Sparsest Cut Undirected Balanced Sep. Our Results: Primal-Dual algorithms Problem Undirected Sparsest Cut Undirected Balanced Sep. Previous best:

O(log n) apx [AHK04] Our alg.: O(log n) apx Our alg.: O(log n) apx (n2) (n2) (m + n1.5) [AHK04] (n2) Cannot be achieved (n2) (m + n1.5) by LPs even! Directed Sparsest Cut

(n4.5) 2+) (m1.5 + n2+ (m1.5) Directed Balanced Sep. (n4.5) 2+) (m1.5 + n2+ (m1.5) Our Results: Near-linear time algorithm for Max Cut (n + m) time algorithm to approximate Max Cut SDP to (1 + o(1)) factor

Previous best: (n2) time algorithm by Klein, Lu 95 Prototype MW for LPs: Winnow [L88] a1 x - 0 0 a2 x - 0 am x - x0 i xi = 1 MW for LP: Init: x = (1/n, , 1/n) Update: xj = xj exp(- aij)/ = norm. factor MW algorithm: boosting, Analysissets, useszero hard-core asgames, potential fn. sum flows,

Thm: Finds x in O(2log(n)/2) iterations. = maxij |aij| x Oracle Find i s.t. ai x < - ai Convex comb. of constraints allowed: i yi ai x < -, where yi 0, i yi Prototype Matrix MW for SDPs A1 X - 0 0 A2 X - 0 Am X - X0 Tr(X) = 1 Matrix MW for SDP: Init: X = I/n Update: X = exp(- ts=1 Ais)/ = norm. factor

Analysis uses as potential fn. Thm: Finds X in O(2log(n)/2) iterations. = maxi kAik X Oracle Find it s.t. Ait X < - Ai t Convex comb. of constraints allowed: i yi AiX < -, where yi 0, i yi = The Matrix Exponential Matrix MW for SDP: Init: X = I/n Update: X = exp(- ts=1 Ais)/ = norm. factor Matrix exponential: exp(A) = I + A + A2/2! + A3/3! +

Always PSD: exp(A) 0 Golden-Thompson inequality: Tricky beast: Tr(exp(A)exp(B)) Tr(exp(A+B)) exp(A+B) = exp(A) exp(B) Computation: O(n3) time Usually, can use J-L lemma Only need exp(A)v products: (m) time Approximation via SDP Relaxations Reduction Input Rounding Algorithm v1 Primal-Dual SDP

0-1 Quadratic Program Relaxation v2 SDP Solver SDP Opt vn SDP: Vector vars Primal-Dual SDP Framework Reduction Input Rounding Algorithm v1 Primal-Dual SDP 0-1 Quadratic Program

Relaxation v2 y1,, ym X vn Matrix MW SDP: Vector vars Approximating Balanced Separator G = (V, E) S S Cut (S, S) is c-balanced if

|S|, |S| cn Min c-Balanced Separator: cbalanced cut of min capacity Numerous applications: Divide-and-conquer algorithms Markov chains Geometric embeddings Clustering Layout problems SDP for Balanced Separator G = (V, E) kvi vjk2 = 0 if i, j on same side, = 1 otherwise S SDP: min i,j 2 E kvi vjk2 S vi = -1 vi = 1 8i: kvik2 = 1

8ijk: kvivjk2 + kvjvkk2 kvivkk2 i, j kvi vjk2 c(1-c)n2 Implementing Oracle Primal: min i,j 2 E kvi vjk2 8i: kvik2 = 1 8ijk: kvivjk2 + kvjvkk2 kvivkk2 i, j kvi vjk2 c(1-c)n2 Oracle: given X (thus, vi), : Bounds checkThm: Given vi, constraints : first and third eigenvalues via inequalities: Max-flow ) desired flow or cut of flow dual vars , multicommodity s.t. demand graph

fij = total1. flow O(log(n)). Laplacian 1. totali,value flow from any node is d between j Multicommodity flow ) desired flow 2. no2. capacity is exceeded ori cut O(log(n)). 2 value 3. i,j fijkv vjkof Conclusions and Future Work Matrix MW algorithm: more applications in

Solving SDPs: e.g. Min Linear Arrangement Quantum algorithms: density matrix is a central concept Learning: e.g. online variance minimization [WK COLT06], online PCA [WK NIPS06] Other applications? Linear time algorithm for Sparsest Cut? Our algorithm runs in (m + n1.5) time for an O(log n) approximation Thank you!

Recently Viewed Presentations

  • AP024 Partner Session Accelerate Building and Delivering Solutions

    AP024 Partner Session Accelerate Building and Delivering Solutions

    Partner Portal Sales Resources. MSSP, programmes and incentives. Sales Process Overview. Prospect / Qualify (20%) Develop (40%) ... Core IO, BRIO, APIO and Cloud. How we sell. Segments, roles and acronyms. MSSP. Roles. The Partner programs to support selling. SIP....
  • The Imperfect

    The Imperfect

    How about those three irregulars? Ser, ir, ver ser ir ver era iba veía eras ibas veías era iba veía éramos íbamos veíamos eran iban veían That's all, folks - no other irregular imperfect forms in Spanish. Ejemplos… To talk...
  • Storage Optimize Storage with BMC TrueSight Capacity Optimization

    Storage Optimize Storage with BMC TrueSight Capacity Optimization

    Storage Infrastructure. SAN Switches. Disk Arrays, Storage Systems. Backups. Monitor FC Ports. Link, Speed, Type. Traffic. Store the data, read and write. Disks ...
  • Chemistry of the mantle - Universiteit Utrecht

    Chemistry of the mantle - Universiteit Utrecht

    Elements that tend to partition into sulphide phases are called chalcophile Mantel geochemistry largely exploits the radioactive decay of certain isotopes. The decay changes the isotope composition of parent and daughter elements Characteristic fingerprints of melts Dating Fundamental ...
  • Hybrid Vehicles Aims and Objectives Aim To be

    Hybrid Vehicles Aims and Objectives Aim To be

    Hybrid Vehicles Hybrid Vehicles The main components include:- Motor High Voltage Battery Power drive Unit DC converter (direct current) Hybrid Vehicles Hybrid Vehicles Toyota Prius Uses a Power Split system the high voltage battery provides power to the motor to...
  • Department of Higher Education and Training Chief Directorate:

    Department of Higher Education and Training Chief Directorate:

    Other Registration, SOR and Examination Issues. ... Work that was not part of the syllabus was tested/work at the wrong level was assessed. The tasks were poorly designed; task did not make sense and had with many errors and marks...
  • Diapositiva 1 - Moebius

    Diapositiva 1 - Moebius

    bienvenidos al mundo de la energia libre
  • Postpartum Hemorrhage - Alhefzi

    Postpartum Hemorrhage - Alhefzi

    Secondary or Delayed or Late Postpartum hemorrhage: Bleeding occurs following delivery of the baby after 24 hours up to 6 weeks. Primary Postpartum Hemorrhage. Causes: 1] Atonic. 2] Traumaic. 3] Mixed. 4] Coagulopathy. Atonic PPH. Contributes for 80 % of...