Approximation Algorithms for Stochastic Optimization

Ensuring that analyses performed on a dataset are representative of the entire population is one of the central problems in statistics. Most classical techniques assume that the dataset is independent of the analyst’s query and break down in the common setting where a dataset is reused for multiple, adaptively chosen, queries. This problem of adaptive data analysis was formalized in the seminal works of Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014).

We identify a remarkably simple set of assumptions under which the queries will continue to be representative even when chosen adaptively: The only requirements are that each query takes as input a random subsample and outputs few bits. This result shows that the noise inherent in subsampling is sufficient to guarantee that query responses generalize. The simplicity of this subsampling-based framework allows it to model a variety of real-world scenarios not covered by prior work.

In addition to its simplicity, we demonstrate the utility of this framework by designing mechanisms for two foundational tasks, statistical queries and median finding. In particular, our mechanism for answering the broadly applicable class of statistical queries is both extremely simple and state of the art in many parameter regimes.

Stochastic optimization is a widely used approach for optimization under uncertainty, where uncertain input parameters are modeled by random variables. Exact or approximation algorithms have been obtained for several fundamental problems in this area. However, a significant limitation of this approach is that it requires full knowledge of the underlying probability distributions. Can we still get good algorithms if these distributions are unknown, and the algorithm needs to learn them through repeated interactions? In this talk, I will discuss a generic online learning algorithm that obtains optimal regret bounds relative to the best algorithms (under known distributions) for a large class of “monotone” stochastic problems. This class includes fundamental problems like single-resource revenue management, Pandora’s box, and stochastic knapsack. Notably, our online algorithm works in a semi-bandit setting, where in each period, the algorithm only observes samples from the random variables that were actually probed.

We consider variants of the classical graph matching problem that exhibit various forms of uncertainty. Online Bipartite Matching considers the problem of finding a maximum weight matching in a bipartite graph when the vertices of one side arrive one by one and, at each arrival, the algorithm must make an immediate and irrevocable decision about whether to match the vertex to one of its neighbors. Variants of the problem consider stochastic arrival models (e.g., arriving vertices are sampled IID from a known distribution). Stochastic Matching (or Matching with Stochastic Edges) considers the standard graph matching problem in settings where the existence of each edge is (initially) unknown to the algorithm and only discovered after querying the edge. Variants of the problem consider the case where each vertex has a “patience”, indicating the maximum number of its incident edges that may be queried. Typically, this patience value is deterministic and known to the algorithm. Online Stochastic Matching combines both of these problems, so that vertices on one side of a bipartite graph arrive one by one, and in each step the algorithm may make multiple attempts to match the vertex until one succeeds, or until the patience is exhausted. We discuss results for some of these variants. A final variant considers the case of unknown (stochastic) patience, i.e. where the patience is drawn from some known distribution and is only learned by the algorithm once it becomes exhausted.

We establish a framework unifying the pathwise search problem and the expanding search problem. We consider a graph $G=(V,E)$ with non-negative vertex weights and a designated start vertex $s$. Furthermore, each edge $e$ is equipped with a non-negative cost and a discount factor ${\alpha }_e\in [0,1]$ such that for the second and further traversals of this edge, its cost is multiplied by ${\alpha }_e$. For a path that starts in $s$, the latency of a vertex is the total cost of that path until the vertex is visited for the first time. The goal is to find a path that starts in $s$ and visits all vertices with positive weight such that the weighted sum of the latencies of all vertices is minimized. If ${\alpha }_e=0$ for all $e\in E$, the problem corresponds to the expanding search problem, and if ${\alpha }_e=1$ for all $e\in E$, it corresponds to the pathwise search problem. We give a polynomial time algorithm that yields a constant approximation factor for all choices of $\alpha \in {[0,1]}^{|E|}$. For $\alpha =0$ and $\alpha =1$, our factor attains the same ratio as the so far best factors for expanding and pathwise search, respectively.

While analyzing algorithms in the worst-case has long served us well, recent years have seen an exciting surge in analyzing algorithms in models that go beyond the worst case. We consider the classical problem of load-balancing, where jobs arrive online and must be assigned to collections of machines to minimize the maximum load. Can we get results better than the adversarial setting if we have a small sample of the upcoming data? The results in this talk are based on work with C.J. Argue, Alan Frieze, and Chris Seiler.

Commonly, in stochastic optimization, one assumes to know the probability distribution(s) the input is coming from. This is often motivated by the availability of historic data. In this talk, we survey different recent results formalizing this aspect and attempting to understand how one can learn the distribution well enough. For example, we might get a number of samples from the distribution. Can we still show that the optimal policy on the empirical distribution has a good performance? And how should we behave in repeated settings, where we get one sample from the distribution per day?

We introduce the study of search games between a mobile Searcher and an immobile Hider in a new setting in which the Searcher has some potentially erroneous information, i.e., a prediction on the Hider’s position. The objective is to establish tight tradeoffs between the consistency of a search strategy (i.e., its worst case expected payoff assuming the prediction is correct) and its robustness (i.e., the worst case expected payoff with no assumptions on the quality of the prediction). Our study is the first to address the full power of mixed (randomized) strategies; previous work focused only on deterministic strategies, or relied on stochastic assumptions that do not guarantee worst-case robustness in adversarial situations. We give Pareto-optimal strategies for three fundamental problems, namely searching in discrete locations, searching with stochastic overlook, and searching in the infinite line. As part of our contribution, we provide a novel framework for proving optimal tradeoffs in search games which is applicable, more broadly, to any two-person zero-sum games in learning-augmented settings.

Consider the triplet $(E,𝒫,\pi )$, where $E$ is a finite ground set, $𝒫\subseteq 2^E$ is a collection of subsets of $E$ and $\pi :𝒫\to [0,1]$ is a requirement function. Given a vector of marginals $\rho \in {[0,1]}^E$, our goal is to find a distribution for a random subset $S\subseteq E$ such that $\mathrm{Pr}[e\in S]={\rho }_e$ for all $e\in E$ and $\mathrm{Pr}[P\cap S\ne \mathrm{\varnothing }]\ge {\pi }_P$ for all $P\in 𝒫$, or to determine that no such distribution exists.

Generalizing results of Dahan, Amin, and Jaillet, we devise a generic decomposition algorithm that solves the above problem when provided with a suitable sequence of admissible support candidates (ASCs). We show how to construct such ASCs for numerous settings, including supermodular requirements, Hoffman-Schwartz-type lattice polyhedra, and abstract networks where $\pi$ fulfils a conservation law. The resulting algorithm can be carried out efficiently when $𝒫$ and $\pi$ can be accessed via appropriate oracles. For any system allowing the construction of ASCs, our results imply a simple polyhedral description of the set of marginal vectors for which the decomposition problem is feasible. Finally, we characterize balanced hypergraphs as the systems $(E,𝒫)$ that allow the perfect decomposition of any marginal vector $\rho \in {[0,1]}^E$, i.e., where we can always find a distribution reaching the highest attainable probability $\mathrm{Pr}[P\cap S\ne \mathrm{\varnothing }]=\min {\sum }_{e\in P}{\rho }_e,1$ for all $P\in 𝒫$.

I will give an overview of basic set selection problems in a model where querying uncertain data incurs a cost. Given subsets of uncertain values, we study two tasks: identifying the minimum element in each set and selecting the subset of minimum total value while querying as few values as possible. These problems fall under the umbrella of explorable uncertainty. In the adversarial setting, strong lower bounds on query complexity extend to a wide range of classical problems such as knapsack, matchings, and linear programming. We then introduce a stochastic variant, where each weight is drawn independently from a known distribution, and present algorithms that, in expectation, beat these adversarial bounds. Our approach builds on a careful analysis of the underlying offline problems, exploiting connections to vertex covers and LP formulations. Finally, I will outline further research directions involving parallelization, robustification, and other extensions.

We consider the following Stochastic Boolean Function Evaluation problem, which is closely related to several problems from the literature. A matroid $ℳ$ (in compact representation) on ground set $E$ is given, and each element $i\in E$ is active independently with known probability $p_i\in (0,1)$. The elements can be queried, upon which it is revealed whether the respective element is active or not. The goal is to find an adaptive querying strategy for determining whether there is a basis of $ℳ$ in which all elements are active, with the objective of minimizing the expected number of queries. When $ℳ$ is a uniform matroid, this is the problem of evaluating a $k$-of-$n$ function, first studied in the 1970s. This problem is well-understood, and has an optimal adaptive strategy that can be computed in polynomial time. Interestingly, already when $ℳ$ is a partition matroid, we show that the standard approaches fail to give even a constant-factor approximation. Our main result is a randomized polynomial- time constant-factor approximation algorithm for this problem. Our algorithm adaptively in- terleaves solutions to several instances of a novel type of stochastic querying problem, with a constraint on the expected cost. We believe that this problem is of independent interest and that several of our techniques have the potential for more general applications.

In this survey talk, we will consider discrete optimization problems where the inputs include probability distributions, and the goal is to maximize the expected reward. Two key benchmarks for these problems are the hindsight (offline) optimum and the optimal (online) policy. A central challenge, regardless of the chosen benchmark, is that optimal algorithms often adapt to the realizations of random variables. This adaptivity can lead to decision trees of exponential size, making the problem computationally intractable. We will explore techniques that focus on non-adaptive algorithms, which offer simpler and more efficient solutions, with only a small loss in performance. We will also discuss advances in stochastic discrete optimization models that incorporate correlations, while maintaining tractability in algorithm design.

We consider the correlated knapsack orienteering (CSKO) problem: we are given a travel budget $B$, processing-time budget $W$, finite metric space $(V,d)$ with root $\rho \in V$, where each vertex is associated with a job with possibly correlated random size and random reward that become known only when the job completes. Random variables are independent across different vertices. The goal is to compute a $\rho$-rooted path of length at most $B$, in a possibly adaptive fashion, that maximizes the reward collected from jobs that are processed by time $W$. To our knowledge, CSKO has not been considered before, though prior work has considered the uncorrelated problem, stochastic knapsack orienteering, and correlated orienteering, which features only one budget constraint on the sum of travel-time and processing-times.

We show that the adaptivity gap of CSKO is not a constant, and is at least $\mathrm{\Omega }(\max \{\sqrt{\log B},\sqrt{\log \log W}\})$. Complementing this, we devise non-adaptive algorithms that obtain: (a) $O(\log \log W)$-approximation in quasi-polytime; and (b) $O(\log W)$-approximation in polytime. We obtain similar guarantees for CSKO with cancellations, wherein a job can be cancelled before its completion time, foregoing its reward. We also consider the special case of CSKO, wherein job sizes are weighted Bernoulli distributions, and more generally where the distributions are supported on at most two points ($2$-CSKO). Although weighted Bernoulli distributions suffice to yield an $\mathrm{\Omega }(\sqrt{\log \log B})$ adaptivity-gap lower bound for (uncorrelated) stochastic orienteering, we show that they are easy instances for CSKO. We develop non-adaptive algorithms that achieve $O(1)$-approximation in polytime for weighted Bernoulli distributions, and in ${(n+\log B)}^{O(\log W)}$-time for the more general case of 2-CSKO.

This talk addresses the problem of computing a scheduling policy that minimizes the total expected completion time of a set of $N$ jobs with stochastic processing times on $m$ parallel identical machines. When all processing times follow Bernoulli-type distributions, Gupta et al. (SODA ’23) exhibited approximation algorithms with an approximation guarantee $\tilde{\text{O}}(\sqrt{m})$, where $m$ is the number of machines and $\tilde{\text{O}}(\cdot )$ suppresses polylogarithmic factors in $N$, improving upon an earlier $\text{O}(m)$ approximation by Eberle et al. (OR Letters ’19) for a special case. The present paper shows that, quite unexpectedly, the problem with Bernoulli-type jobs admits a PTAS whenever the number of different job-size parameters is bounded by a constant. The result is based on a series of transformations of an optimal scheduling policy to a “stratified” policy that makes scheduling decisions at specific points in time only, while losing only a negligible factor in expected cost. An optimal stratified policy is computed using dynamic programming. Two technical issues are solved, namely (i) to ensure that, with at most a slight delay, the stratified policy has an information advantage over the optimal policy, allowing it to simulate its decisions, and (ii) to ensure that the delays do not accumulate, thus solving the trade-off between the complexity of the scheduling policy and its expected cost. Our results also imply a quasi-polynomial $\tilde{\text{O}}\log N$-approximation for the case with an arbitrary number of job sizes.

Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific input features. However, computing Shapley values exactly is expensive: for a general model with $n$ features, $O(2^n)$ model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. However, to the best of our knowledge, Kernel SHAP has no strong non-asymptotic complexity guarantees. We address this issue by introducing Leverage SHAP, a light-weight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just $O(n\log n)$ model evaluations. Our approach takes advantage of a connection between Shapley value estimation and agnostic active learning by employing leverage score sampling, a powerful regression tool. Beyond theoretical guarantees, we show that Leverage SHAP consistently outperforms even the highly optimized implementation of Kernel SHAP available in the ubiquitous SHAP library [Lundberg & Lee, 2017].

Constructing an optimal binary search tree (BST) has long been a foundational problem in data structures. Given a fixed, known probability distribution over keys, Knuth’s seminal result (1971) provides an efficient method for computing the optimal static BST. Later, Mehlhorn (1975) showed that a near-optimal BST can be approximated in linear time. We initiate the study of the robust optimization variant of the classical BST problem by considering settings where the underlying distribution is uncertain. Instead of a single known distribution, we are given $k$ different distributions ${𝒟}_1,{𝒟}_2,\mathrm{\dots },{𝒟}_k$. The goal is to construct a single BST $T$ that performs well across all of them – minimizing the worst-case expected access cost.

In this talk, I will give a simple 1.5-approximation algorithm for $k=2$, which can be generalized to a $0.804k$-approximation for arbitrary $k$. This improvement is achieved by carefully combining two distinct 2-approximation algorithms, leveraging their strengths to refine the approximation ratio. I will also show a hardness result under the Unique Games Conjecture: when $k$ is large, computing an optimal BST is NP-hard, even when each distribution has support of size at most two.

We introduce a stochastic probing problem with correlated items, which we call Bayesian probing, where the correlations are modeled by an underlying graph. In our model, each vertex has a known probability of being active or inactive. Each item is an edge in the graph, and its distribution is the product of its two endpoints. The goal is to adaptively probe items/edges subject to a knapsack constraint to maximize the expected total reward obtained from all probed edges. This problem is a special case of stochastic knapsack with correlations across items and Bayesian active search problems considered in machine learning.

The distinguishing feature of Bayesian probing is that the probing an edge reveals the outcome of both of its endpoints, which induces a Bayesian update on the expected reward of all other incident edges. We design approximation algorithms computing policies that are either fully non-adaptive, or they make a single Bayesian update after using half of the knapsack budget. Our approximation ratios depend on natural graph parameters of the underlying correlation graph.

In the sequential testing problem, the goal is to evaluate a Boolean (or discrete) function with the minimum expected cost where the values of the variables can be learned by paying a cost. The variables take values independent of each other with known probabilities. The problem has been studied in different domains for various applications. In this talk, we concentrate on works that have been published in the last 20 years and provide a general review of the results that have been obtained for different special cases and extensions of the problem. We also provide insights to explore potential reseach areas for future research.

In the prophet inequality we observe a sequence of n random variables one by one and we want to decide when to stop. The reward of a online stopping policy is the variable it stops with. When the random variables are independent and the distributions are known, the optimal stopping policy can be computed in polynomial time via backward induction. A large body of literature is dedicated to bound the ratio between the expected reward of the optimal online policy and the expected offline optimum, under many variants of the problem. When the variables are correlated, no constant approximation with respect to the offline optimum is possible. Moreover, when the variables are correlated, the computation of the optimal online policy becomes challenging, because a naive backward induction algorithm would need to “remember” at each time all previous realizations. Here I propose two models to study the computational complexity of correlated optimal stopping, one easy and one apparently hard:

(1) We are given a set of $m$ scenarios. Each scenario is a deterministic sequence of n values. A realization of the $n$ random variables is drawn as a uniformly chosen scenario. We can compute the optimal online algorithm via backward induction, by noticing that at any given time, the observed values must agree with at least one of the scenarios. Therefore, we can encode past observations by just choosing one scenario that is compatible with them. Thus we can compute the optimal online policy in time $\mathrm{poly}(n,m)$.

(2) We are given a set of m scenarios, but now a scenario is a sequence of $n$ distributions, all supported in a set of $k$ different values. A realization of the $n$ random variables is drawn by first choosing uniformly one scenario, and then drawing each variable independently according to the $n$ distributions of the chosen scenario. Can we compute the optimal online policy in time $\mathrm{poly}(m,n,k)$? If not, can we approximate it?

A target is located at one of the two ends of a discrete path according to a known probability distribution. A Searcher begins at a root node $O$ at time $0$. In each time step, she moves to an adjacent node. Upon reaching a node, she receives a signal that points either left or right. (We assume there is no signal at $O$ at time $0$.) With probability $p\ge 1/2$, the signal points towards the target, otherwise it points in the opposite direction. We wish to find a policy to minimize the expected time to reach the target. Attached is a solution for a path of length $3$. Is there a closed form policy in general?

Motivated by Benedikt Plank’s talk, I propose to relax stochastic combinatorial optimization problems in which there is a hard budget constraint by considereding them under a budget constraint in expectation. One can then ask (i) how to efficiently compute or approximate the best strategy and (ii) by what factor the objective-function value changes in the worst case. Such problems may be interesting by itself, but Benedikt Plank’s talk has shown another motivation. For the $k$-of-$n$ SFBE problem considered in that talk the answer to (ii) was non-constant. What else can we say, e.g., for the ProbeMax problem?

The deliberate idleness problem is a problem in stochastic machine scheduling. In stochastic machine scheduling, we are concerned with the question how to optimally schedule $n$ jobs with stochastic processing requirements on $m$ machines. More specifically, the processing times follows distributions $p_j\sim X_j$, $j=1\mathrm{\dots },n$. The jobs are nonpreemptive, all available at time $0$, and have to be scheduled on $m$ parallel, identical machines. Each machine can only do one job at a time, and a job can go on any of the $m$ machines. Moreover, each job has a weight $w_j$, and we want to find a scheduling policy that minimizes the expected value of the weighted sum of completion times, $E[{\sum }_j{w}_j{C}_j]$. An instance consists of the input of jobs $(w_j,X_j)$, $j=1,\mathrm{\dots },n$, and the encoding of the number of machines $m$.

The solution to such a problem is not a schedule, but a scheduling policy which tells us, at any point in time $t$ (typically when a machine falls idle, but possibly also at other points in time), which job(s) to schedule next. This decision may depend on the input of the problem, and the state of the system at time $t$. The latter is given by time $t$, the set of jobs already completed, the set of jobs currently running together with their conditional distribution of remaining processing time, and the set of jobs not yet started.

Question: Assume $m\ge 3$ machines, and assume that all jobs follow an exponential distribution, $p_j\sim exp({\lambda }_j)$, that is, the processing times are memoryless. Does there always exist an optimal policy that avoids deliberate idleness? That is, as long as there are unprocessed jobs, it would never leave a machine deliberately idle. Some background information follows.

• $\mathrm{■}$

  For arbitrary $p_j\sim X_j$ there are examples showing that deliberate idleness can be necessary, even on $m=2$ machines. See Uetz: When Greediness Fails: Examples from Stochastic Scheduling, OR Lett. 31, 2003, 413-419. (Franziska Eberle might have an example even when all $w_j=1$).

• $\mathrm{■}$

  For $m=2$ machines and $p_j\sim exp({\lambda }_j)$ an optimal policy always exists that avoids deliberate idleness. This is not totally trivial, but not too difficult either, using an exchange argument (and induction).

• $\mathrm{■}$

  WSEPT (greedily schedule jobs in order of ratios $w_j/E{p}_j$) has a performance guarantee of $2-1/m$, whenever the distribution have coefficient of variation $\le 1$, including exponential distributions. See Möhring, Schulz, Uetz: Approximation in stochastic scheduling: the power of LP-based priority policies, J. ACM 46 (1999), 924-942. For a more recent improvement of this upper bound to 4/3, see Jäger, Skutella: Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling, 35th STACS, LIPIcs no. 43, vol. 96, 2018

• $\mathrm{■}$

  When all $w_j=1$, the problem is solved optimally by the SEPT rule, greedily schedule jobs with shortest expected processing time first. See Bruno, Downey, Frederickson: Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan, J. ACM 28 (1981), 100-113.

In the stochastic bin packing problem, we must adaptively pack items with random sizes into unit-sized bins. Each item size is independent with known distribution but unknown realized value. Because of this, we may place an item into a bin such that its realized size overflows the bin capacity. Overflowing a bin incurs an additive penalty. Thus, our objective is to pack all items to minimize the expected number of bins opened plus the penalties for any overflowed bins.

This problem was introduced by Sebastian Perez-Salazar, Mohit Singh, and Alejandro Toriello (https://arxiv.org/abs/2007.11532). Among other things, they prove that in the online setting (items arrive one-by-one and must be packed irrevocably upon arrival), one can achieve a $O(1)$-approximation if all items are drawn i.i.d. from a known distribution and a $O(\log C)$ approximation if all items are exponentially distributed, where $C$ is a function of the parameters of the exponentials.

It would be interesting to give approximation algorithms for more general distributions or consider the case where we do not know the item size distributions.