Algorithms & Complexity

Group

Research

Teaching

Theses

back to main page

Logbook Optimization and Uncertainty - Summer 2023

• Lecture 24 -- 13.07.2023:
  Zero-Sum Games, definition, Rock-Paper-Scissors, worst-case analysis of algorithms as a zero-sum game, sequential versions of the game, Minimax-Theorem, proof using no-regret learning, implications and consequences.

  Literature:
  • Notes: Section 7.4



• Lecture 23 -- 11.07.2023:
  Experts problem as a special case of online convex optimization, Euclidean and Entropical regularizers, Lipschitz condition, σ-strong convexity, upper bound on the regret of FTRL, connections of FTRL to RWM and GIGA in the Experts problem.

  Literature:
  • Notes: Sections 7.3.2



• Lecture 22 -- 06.07.2023:
  Online convex optimization, convexity properties, gradient descent, generalized infinitesimal gradient ascent (GIGA), regret of at most Δ²/(2η) + TηG²/2, where G upper bounds the gradient and Δ the diameter of the ground set. GIGA is a no-regret algorithm. Follow-the-Regularized-Leader (FTRL), bound on the total regret

  Literature:
  • Notes: Section 7.3, 7.3.1, 7.3.2
  • M. Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML 2003.



• Lecture 21 -- 04.07.2023:
  Adversarial Multi-Armed Bandits, Exp3-Algorithm, regret at most 3$\sqrt{n\; T\; ln\; n}$, Exp3 is a no-(external)-regret algorithm, proof of upper bound on total expected cost.

  Literature:
  • Notes: Section 7.2
  • P. Auer, N. Cesa-Bianchi, Y. Freund, R. Schapire. The Nonstochastic Multiarmed Bandit Problem. SIAM Journal on Computing 32(1):48-77, 2003.



• Lecture 20 -- 29.06.2023:
  Stochastic MAB, UCB1 algorithm, proof of the regret bound (Lemmas 21 and 22). Expert classification, Weighted Majority algorithm, proof of upper bound on the number of mistakes in terms of mistakes of the best classifier. Experts problem, Randomized Weighted Majority algorithm (RWM), definition regret, regret of RWM is at most 2$\sqrt{T\; ln\; n}$, RWM is a no-(external)-regret algorithm, proof of upper bound on total expected cost.

  Literature:
  • Notes: Sections 6.3 (from Lemma 22) and 7.1
  • N. Littlestone, M. Warmuth. The Weighted Majority Algorithm. Information and Computation 108(2):212-261, 1994.



• Lecture 19 -- 27.06.2023:
  Markovian MAB, proof of optimality of the Gittins index policy. Stochastic multi-armed bandits, definition, regret, simple explore-then-exploit algorithm, regret sublinear in T; UCB1 algorithm, regret bound of O(n log T) when best expectation of any arm has a constant leading margin.

  Literature:
  • Notes: Section 6.2 (Theorem 30), Section 6.3 (until Lemma 22)
  • P. Auer, N. Cesa-Bianchi, P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning 47(2):235–256, 2002



• Lecture 18 -- 22.06.2023:
  Markovian single-armed bandits, definition, charges for play, definition Gittins index, Markovian multi-armed bandits, Gittins index policy, parts of the proof of optimality (Lemmas 19 and 20)

  Literature:
  • Notes: Section 6.2 (until proof of Theorem 30)



• Lecture 17 -- 20.06.2023:
  Infinite Markov decision processes, definition with discounted rewards, optimal Markovian policy, value iteration, policy iteration, convergence proofs.

  Literature:
  • Notes: Section 6.1



• Lecture 16 -- 15.06.2023:
  Delegated search problem, connection to prophet inequalities, median-prophet algorithm, proof of 2-approximation w.r.t. optimal value in the undelegated search problem

  Literature:
  • Notes: Section 5.2
  • J. Kleinberg, R. Kleinberg. Delegated Search Approximates Efficient Search. EC 2018.



• Lecture 15 -- 13.06.2023:
  Persuasion with IID boxes, construction of LP, rounding algorithm, proof of (1-1/e)^-1-approximation and persuasiveness. Persuasion with independent boxes, SSQ-box, construction of LP, rounding algorithm, proof of 4-approximation and persuasiveness.

  For the proof of persuasiveness in the IID case, see page 70 in the notes. The argument given in the lecture only applies if the recommneded box is a yes-box and the non-recommended box is a no-box. However, a recommended box could also be a no-box and/or a non-recommended one a yes-box. This must be incorporated into the analysis!

  Literature:
  • Notes: Sections 5.1.1, 5.1.2
  • N. Hahn, M. Hoefer, R. Smorodinsky. Prophet Inequalities for Bayesian Persuasion. IJCAI 2020.



• Lecture 14 -- 01.06.2023:
  Bayesian persuasion, model and example, there is optimal scheme φ^* that is direct and persuasive, computing φ^* via LP for explicitly represented distribution D. IID case: symmetry of φ^* and consequences

  Literature:
  • Notes: Sections 5.1, 5.1.1
  • S. Dughmi, H. Xu. Algorithmic Bayesian Persuasion. STOC 2016.



• Lecture 13 -- 30.05.2023:
  Probing with opening cost, Pandora's Box problem, fair cap as an estimator of the value of the box after subtracting the opening cost, optimal policy greedily opens boxes in non-increasing order of fair cap

  Literature:
  • Notes: Section 4.3
  • M. Weitzman. Optimal search for the best alternative. Econometrica 47(3):641-654, 1979
  • Bo Waggoners Blog Post



• Lecture 12 -- 25.05.2023:
  Testing, k-TestMax, testing a box = refining the support region in which realization is located, testing vs. probing, testing policy for the IID case that obtains at least 1-1/e^1/4-o(1) of the expected reward of the optimal probing policy

  Literature:
  • Notes: Section 4.2
  • M. Hoefer, K. Schewior, D. Schmand. Stochastic Probing with Increasing Precision. IJCAI 2021.



• Lecture 11 -- 23.05.2023:
  Probing, k-ProbeMax, non-adaptive and adaptive policies, adaptivity gap, adaptivity gap for k-ProbeMax is at most 8, bounding the optimum using a linear program, deriving a non-adaptive policy from the LP optimum.

  Literature:
  • Notes: Section 4.1
  • A. Asadpour, H. Nazerzadeh. Maximizing Stochastic Monotone Submodular Functions. Management Science 62(8):2374-2391, 2016.



• Lecture 10 -- 11.05.2023:
  Online independent set, extensions of the algorithm to (1) graphs with bounded inductive independence number, (2) a graph sampling model.

  Literature:
  • Notes: Section 3.4.3
  • O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods. ICALP 2014.
  • Y. Ye, A. Borodin. Elimination Graphs. ACM Transactions on Algorithms 8(2):774-785, 2012.



• Lecture 9 -- 09.05.2023:
  Online independent set and the interval scheduling problem, prophet interval scheduling, 4-competitive algorithm, proof of the competitive ratio. Secretary independent set with random-order arrival, 8-competitive algorithm, proof by adjusting the arguments for the prophet case.

  Literature:
  • Notes: Sections 3.4.1, 3.4.2
  • O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods. ICALP 2014.



• Lecture 8 -- 04.05.2023:
  Yao's principle, given any input distribution, the best deterministic algorithm for that distribution performs better than any randomized algorithm on worst-case input, lower bound of Ω(n) on the competitive ratio of any randomized algorithm for OnlineMax. Online Independent Set, interval scheduling, lower bound Ω(n) on the competitive ratio, Prophet Interval Scheduling, 4-competitive algorithm.

  Literature:
  • Notes: Sections 3.3, 3.4, 3.4.1
  • A. C.-C. Yao. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). FOCS 1977.
  • O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods. ICALP 2014.



• Lecture 7 -- 02.05.2023:
  Examples for finite-time MDPs and optimal policies. SkiRental: Buy only on the first open day when there are at least ⌊((B-1)/q)+2⌋ days remaining; Prophet: accept any person as soon as it has more value than the expected value obtained by the optimal policy in the subsequent rounds.
  
  Indeed, ⌊((B-1)/q)+2⌋, since we compare C(T-1) and B.

  Literature:
  • Notes: Section 3.2.2



• Lecture 6 -- 27.04.2023:
  PrizeCollection problem, definition Markov decision process (MDP), optimal policy π^* for finite time horizon, existence of π^* that is Markovian, computation via a dynamic program (DP), example DP for PrizeCollection, alternative characterization of optimal policy: Sort envelopes in non-increasing order of v_iq_i/(1-q_i)

  Literature:
  • Notes: Sections 3.2, 3.2.1, 3.2.2



• Lecture 5 -- 25.04.2023:
  OnlineMax with independent distributions, prophet inequalities in the general case, 2-competitive, tightness example; prophet inequality in the identical case, 1.58-competitive, discussion of improved approaches

  Literature:
  • Notes: Section 3.1
  • J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, T. Vredeveld. Recent developments in prophet inequalities. SIGecom Exchanges 17(1):61–70, 2018
  • E. Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals of Probability 12(4):1213–1216, 1984.



• Lecture 4 -- 20.04.2023:
  Item Allocation Problem, at least b ≥ 1 copies per item, bundles of size at most d, optimal fractional solution via linear programming, extension of the secretary algorithm is O(d^1/b)-competitive.

  Literature:
  • Notes: Section 2.4
  • T. Kesselheim, K. Radke, A. Tönnis, B. Vöcking. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. ESA 2013.



• Lecture 3 -- 18.04.2023:
  Stochastic concepts and tools, probability distributions, events, independence, conditional probabilities, law of total probability. Random variables, expectation, linearity of expectation. Concentration: Markov inequality, Chernoff bounds.

  Literature:
  • Notes: Appendix A
  • Linearity of Expectation
  • Markov and Chebyshev Inequalities
  • Chernoff bounds



• Lecture 2 -- 13.04.2023:
  Secretary problem, e+o(1)-competitive algorithm, proof of the ratio. Max-weight bipartite matching, motivation via sponsored search, secretary matching problem, extension of the standard algorithm is e+o(1)-competitive. Main proof steps: expected value of random selected edge in round t is at least v(M^*)/n, probability to accept any such edge is s/(t-1).

  Literature:
  • Notes: Sections 2.2, 2.3
  • T. Kesselheim, K. Radke, A. Tönnis, B. Vöcking. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. ESA 2013.



• Lecture 1 -- 11.04.2023:
  (1) Organization and overview.
  (2) Fundamentals in online algorithms: Competitive ratio, deterministic and randomized algorithms, randomi­za­tion in the input.
  (3) OnlineMax problem, lower bound Ω(n) on the competitive ratio. Secretary problem = OnlineMax with random-order arrival, e+o(1)-competitive algorithm.

  Literature:
  • Notes: Chapter 1, Sections 2, 2.1, 2.2
  • Given its huge popularity, there are many surveys on the secretary problem. Here is a rather classic one:
    P.R. Freeman. The Secretary Problem and Its Extensions: A Review. Int. Stat. Rev., Vol. 51(2):189-206, 1983.