Advanced Techniques in Online and Bandit Algorithms Beyond Norms
Delve into the realm of online and bandit algorithms beyond traditional norms as discussed by Sahil Singla from Georgia Tech in collaboration with Thomas Kesselheim and Marco Molinaro. The presentation explores the design and optimization of algorithms for online settings, shedding light on load balancing, facility location, set cover, Steiner tree, and more. Discover how to minimize norm objectives, consider different norm types, and achieve hindsight optimum in algorithm design. The discussion also extends to competitive ratios, symmetric norms, and packing constraints, offering insights into cutting-edge research in the field. Moreover, a new O(log2d)-competitive algorithm for online load balancing in monotone symmetric norms is presented, with implications for various applications and theoretical developments.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
ONLINE AND BANDIT ALGORITHMS BEYOND ?NORMS Oct 26th, 2022 SAHIL SINGLA GEORGIA TECH JOINT WITH THOMAS KESSELHEIM AND MARCO MOLINARO (APPEARS IN SODA 23)
ONLINE ALGORITHMS T requests arrive online, i.e., one-by-one Examples: Load Balancing: Facility Location: Set Cover: Steiner Tree: or ? 1 1 or ? 1 Serve t-th request immediately on arrival Goal: Minimize a given norm objective norm: Egalitarian 1 norm: Utilitarian ? norm: Interpolates & new applications Online Alg s objective Hindsight optimum ??????????? ????? = HOWTO DESIGN ONLINE ALGORITHMS BEYOND ? NORMS? 2
ONLINE LOAD BALANCING T jobs arrive online and d machines offline. Job t reveals vector v(t) R 0 Find schedule t {1, ,d} Goal: Minimize a given norm || || of Load vector d d machines T jobs (t) 1 t=i T t T i vi Special cases starting at least Graham 66 Aspnes-Azar-Fiat- Plotkin-Waarts STOC 93 norm (Makespan): (log d) tight competitive ratio. p norm: (min {p,log d}) tight competitive ratio. Awerbuch-Azar-Grove-Kao- Krishnan-Vitter FOCS 95 ??????? ? COMPETITIVE RATIO BEYOND ? NORMS? 3
BEYOND ? NORMS (a) Homogeneity: ||c x|| = c ||x|| (b) Triangle Ineq: ||x + y|| ||x|| + ||y|| (c) ||x|| = 0 implies x = ?d (d)0 x y coordinatewise implies ||x|| ||y|| Monotone norms || || We only consider R 0 d Monotone symmetric norms: Invariant to renaming coordinates 1. p norms, and generalizations to Orlicz norms 2. Top-k norms, and generalizations to Ordered norms 3. Operations: Non-neg linear combinations, composition, and norms of sorted vector Chakrabarty-Swamy STOC 19, Ibrahimpur-Swamy FOCS 20, Ibrahimpur-Swamy ICALP 21, Deng-Li-Rabani SODA 23, Recent work on symmetric norms for offline problems Computational vs Information Theoretic 4
NORMS VS XOS VS PACKING Further motivation, but a slight digression Definition via dual norm: ||x|| sup ||w|| 1x w Monotone Norms d Since monotone, only consider w R 0 Usually as a min-objective XOS Monotone Norms Functions Unified Theory? Given ? R 0 Contains submodular functions Usually as max-objective, e.g., in Combinatorial Auctions n, set function f S max w ?1S w for S [n] XOS Functions Packing Constraints Set family? 2[n]whereA ? and B A implies B ? Let ? denote family of maximal sets in ?. Then, rank?S = max Packing Constraints w ? 1S w Usually as constraints in discrete optimization 5
MAIN RESULT THEOREM: There is an O(log2d)-competitive algorithm for online load balancing for monotone symmetric norms. An (logd) lower bound already for norm. Techniques extend to generalizations of Load Balancing and of Bandit Problems. Remarks Can be made polytime given Ball-optimization oracle access. 1. Introduce Gradient-Stable Approximation (GSA) and show that it suffices Proof Steps 2. Design GSA for Top-k norm. 3. Design GSA for symmetric norms by composition of Top-k norms 6
OUTLINE INTRODUCTION: ONLINE ALGORITHMSFOR GENERAL NORMS LOAD BALANCINGVIA GRADIENT-STABILITY DESIGNING GRADIENT-STABLE NORM APPROXIMATIONS FURTHER RESULTSAND OPEN PROBLEMS 7
HOW DOES GREEDY PERFORM? Greedy: Schedule to minimize || (t 1)+ y(t)|| Aspnes-Azar-Fiat- Plotkin-Waarts STOC 93 norm:Greedy is (d) competitive. Different algo: O(log d) competitive ratio, which is tight. Smooth Greedy: Greedy w.r.t. a norm-approximation Contour plots for max and softmax Softmax ln iexp( i) Awerbuch-Azar-Grove-Kao- Krishnan-Vitter FOCS 95 || || || || + lnd O(log d) competitive ratio for norm WHATIS SMOOTH GREEDY FOR GENERAL NORMS? 8
GREEDY ON A NORM APPROXIMATION t 1 + yt Algorithm: Greedily schedule to minimize t . t 1 + yt T 0 = t t 1 ALG Greedy Step t t 1 + y t 1 t Smooth Game Ineq. when c2< 1 T + c2 T c2 0 c1 OPT ALG c1 T So, T + 1 c2 0 1 c2 9
SMOOTH GAME INEQ. VIA SUPERMODULARITY SMOOTH GAME INEQ: If is monotone, subadditive, and (approx.) supermodular then t T t 1 + y t 1 + T 0 t Counter-intuitive: For norms ||y|| ||0|| ||y + z|| ||z|| DEFN(Approx. supermodularity): For vectors ,y,z R 0 + y + z + y + z d & ||z|| 1: t t Then, and t t 1 t + t 1+ t t t 1 t 1+ y t 1 t 1 + t 1+ Adding and taking sum over t, No additive error for T steps t T 0 t t 1+ y t 1 + T 0 T + 10
GRADIENT-STABILITY AND SUPERMODULARITY DEFN(GSA): Gradient-Stable Approx. for || || if for any ,z R 0 1. is monotone, subadditive, and convex. 2. Approx: || || || || + 3. Stability: + z exp ||z|| coordinate-wise. d : Assuming OPT = 1 Examples: : ln iexp( i) p : || + c ??||p for c = Remarks: (a) No additive gradient error. (b) Related defns Azar et al. FOCS 16, Molinaro SODA 17 p 1 ||??||p LEMMA(GSA implies approx. supermodularity): For vectors ,y,z R 0 + y + z + y + z d : exp ||z|| 1 1 Proof: LHS = =0 + y y d exp ||z|| =0 + z + y y d = RHS 11
WHAT DID WE ACHIEVE? 1. || || || || + 2. + z exp ||z|| d machines T jobs Approx- Supermodular Greedy Load Balancing Smooth- Game Ineq Gradient- Stable Approx HOWTO DESIGN GRADIENT-STABLE APPROXFOR NORMS? 12
OUTLINE INTRODUCTION: ONLINE ALGORITHMSFOR GENERAL NORMS LOAD BALANCINGVIA GRADIENT-STABILITY DESIGNING GRADIENT-STABLE NORM APPROXIMATIONS FURTHER RESULTSAND OPEN PROBLEMS 13
SYMMETRIC NORMS BY COMPOSING TOP-K Close connections between Symmetric and Top-k norms: E.g., if ||x||Top k ||y||Top k for every k, then ||x||sym. ||y||sym. By Schur-convexity, or by Fan Dominance thm LEMMA: Any monotone symmetric norm || || can be O(log d) approximated by max of logarithmic many wtd. Top-k norms Similar lemma in Chakrabarty-Swamy STOC 19 Proof intuition: We know ||x|| max Discretize to powers of 2, so only O(log d) weights as poly(d) range. w ?x w For any single weight c, symmetry implies max w ? cx w = c ||?||Top k for some k. 14
GSA FOR TOP-K: INITIAL ATTEMPTS + z exp ||z||Top k Attempt 1: Use the norm directly x ||x||Top k ( ,0, ,0) to ( ,2 ,2 , ,2 ) for 0. Then, 1 from 1 to 0 with ||z|| 0 FTPL-style approach of Kalai-Vempala COLT 03 1 k Attempt 2: Add noise, like x ? ||x + ||Top k for i~Exp (1,1 , , , , ,0,0, ) to (1,1 + , , , , ,0,0, ) for =log d k k 1 times k 1 times Then, 1 from 1 to 0 with ||z|| =2 log d k 15
GSA FOR TOP-K + z exp ||z||Top k Attempt 3. Geometric K with ?[K] = k and an exponential noise: 1 k x ?K, ||x + ?||Top K for i~Exp THEOREM: (1) Approx: 1 e||x||Top k x 1 +1 e ||x||Top k+ logd (2) Stability: + z exp ||z||Top k LEMMA: Composition of norms with GSA also admits a GSA. COROLLARY: For every monotone symm. norm, there is a GSA . 16
WHAT DID WE ACHIEVE? THEOREM: There is an O(log2d)-competitive algorithm for online load balancing for monotone symmetric norms. Approx- Supermodular Norm Greedy Composition GSA for Top-k GSA for Sym. norms Load Balancing Smooth- Game Ineq 1. Add exponential noise 2. Random K with ?[K] = k 17
OUTLINE INTRODUCTION: ONLINE ALGORITHMSFOR GENERAL NORMS LOAD BALANCINGVIA GRADIENT-STABILITY DESIGNING GRADIENT-STABLE NORM APPROXIMATIONS FURTHER RESULTSAND OPEN PROBLEMS 18
BANDIT ALGORITHMS Badanidiyuru-Kleinberg-Slivkins FOCS 13 Immorlica-Sankararaman-Schapire-Slivkins FOCS 19 Kesselheim-S COLT 20 Bandits with Knapsacks There are K fixed actions. Each time-step choose an action xt {e1, ,eK}, then 1. Receive reward rt xtwhere rt 0,1K 2. Incur vector costCt xt where where Ct 0,1d K Given a budgetB, maximize total reward trt xt while || tCt xt|| B THEOREM: An O(log2d)-competitive algorithm for monotone symmetric norms. Proof uses approx. supermod and an approx. converse to Jensen s inequality. Remarks Similar results for the related Bandits with Vector Costs problem. 19
CONCLUSION Approx- Supermodular Norm Greedy Composition GSA for Top-k GSA for Sym. norms Load Balancing Smooth- Game Ineq 1. || || || || + 2. + z exp ||z|| O(log2d)-competitive for symmetric norms Extends to generalizations of Load Balancing and of Bandit Problems. Open Problems: Polylog(d) for monotone norms or O(logd) for symmetric norms Other online problems beyond ? norms Inter-connections between Norms, XOS functions, and Packing constraints QUESTIONS? 20
