Search

A large proportion of jobs submitted to modern computing clusters and data centers are parallelizable and capable of running on a flexible number of computing cores or servers. Although allocating more servers to such a job results in a higher speed-up in the job's execution, it reduces the number of servers available to other jobs, which in the worst case, can result in an incoming job not finding any available server to run immediately upon arrival. Hence, a key question to address is: how to optimally allocate servers to jobs such that (i) the average execution time across jobs is minimized and (ii) almost all jobs find at least one server immediately upon arrival. To address this question, we consider a system with $n$ servers, where jobs are parallelizable up to $d^{(n)}$ servers and the speed-up function of jobs is concave and increasing. Jobs not finding any available servers upon entry are blocked and lost. We propose a simple server allocation scheme that achieves the minimum average execution time of accepted jobs while ensuring that the blocking probability of jobs vanishes as the system becomes large ($n \to \infty$). This result is established for various traffic conditions as well as for heterogeneous workloads. To prove our result, we employ Stein's method which also yields non-asymptotic bounds on the blocking probability and the mean execution time. Furthermore, our simulations show that the performance of the scheme is insensitive to the distribution of job execution times.

In pool-based active learning, the learner is given an unlabeled data set and aims to efficiently learn the unknown hypothesis by querying the labels of the data points. This can be formulated as the classical Optimal Decision Tree (ODT) problem: Given a set of tests, a set of hypotheses, and an outcome for each pair of test and hypothesis, our objective is to find a low-cost testing procedure (i.e., decision tree) that identifies the true hypothesis. This optimization problem has been extensively studied under the assumption that each test generates a deterministic outcome. However, in numerous applications, for example, clinical trials, the outcomes may be uncertain, which renders the ideas from the deterministic setting invalid. In this work, we study a fundamental variant of the ODT problem in which some test outcomes are noisy, even in the more general case where the noise is persistent, i.e., repeating a test gives the same noisy output. Our approximation algorithms provide guarantees that are nearly best possible and hold for the general case of a large number of noisy outcomes per test or per hypothesis where the performance degrades continuously with this number. We numerically evaluated our algorithms for identifying toxic chemicals and learning linear classifiers, and observed that our algorithms have costs very close to the information-theoretic minimum.

Modern platforms leverage randomized experiments to make informed decisions from a given set of items (``treatments''). As a particularly challenging scenario, these items may (i) arrive in high volume, with thousands of new items being released per hour, and (ii) have short lifetime, say, due to the item's transient nature or underlying non-stationarity that impels the platform to perceive the same item as distinct copies over time. Thus motivated, we study a Bayesian multiple-play bandit problem that encapsulates the key features of the multivariate testing (or ``multi-A/B testing'') problem with a high volume of short-lived arms. In each round, a set of $k$ arms arrive, each available for $w$ rounds. Without knowing the mean reward for each arm, the learner selects a multiset of $n$ arms and immediately observes their realized rewards. We aim to minimize the loss due to not knowing the mean rewards, averaged over instances generated from a given prior distribution. We show that when $k = O(n^\rho)$ for some constant $\rho>0$, our proposed policy has $\tilde O(n^{-\min \{\rho, \frac 12 (1+\frac 1w)^{-1}\}})$ loss on a sufficiently large class of prior distributions. We complement this result by showing that every policy suffers $\Omega (n^{-\min \{\rho, \frac 12\}})$ loss on the same class of distributions. We further validate the effectiveness of our policy through a large-scale field experiment on {\em Glance}, a content-card-serving platform that faces exactly the above challenge. A simple variant of our policy outperforms the platform's current recommender by 4.32\% in total duration and 7.48\% in total number of click-throughs.

Consider a single-product revenue-maximization problem where the seller monotonically decreases the price in $n$ rounds with an unknown demand model coming from a given family. Without monotonicity, the minimax regret is $\tilde O(n^{2/3})$ for the Lipschitz demand family and $\tilde O(n^{1/2})$ for a general class of parametric demand models. With monotonicity, the minimax regret is $\tilde O(n^{3/4})$ if the revenue function is Lipschitz and unimodal. However, the minimax regret for parametric families remained open. In this work, we provide a complete settlement for this fundamental problem. We introduce the crossing number to measure the complexity of a family of demand functions. In particular, the family of degree-$k$ polynomials has a crossing number $k$. Based on conservatism under uncertainty, we present (i) a policy with an optimal $\Theta(\log^2 n)$ regret for families with crossing number $k=0$, and (ii) another policy with an optimal $\tilde \Theta(n^{k/(k+1)})$ regret when $k\ge 1$. These bounds are asymptotically higher than the $\tilde O(\log n)$ and $\tilde \Theta(\sqrt n)$ minimax regret for the same families without the monotonicity constraint.

We analyze a general problem in a crowd-sourced setting where one user asks a question (also called item) and other users return answers (also called labels) for this question. Different from existing crowd sourcing work which focuses on finding the most appropriate label for the question (the "truth"), our problem is to determine a ranking of the users based on their ability to answer questions. We call this problem "ability discovery" to emphasize the connection to and duality with the more well-studied problem of "truth discovery". To model items and their labels in a principled way, we draw upon Item Response Theory (IRT) which is the widely accepted theory behind standardized tests such as SAT and GRE. We start from an idealized setting where the relative performance of users is consistent across items and better users choose better fitting labels for each item. We posit that a principled algorithmic solution to our more general problem should solve this ideal setting correctly and observe that the response matrices in this setting obey the Consecutive Ones Property (C1P). While C1P is well understood algorithmically with various discrete algorithms, we devise a novel variant of the HITS algorithm which we call "HITSNDIFFS" (or HND), and prove that it can recover the ideal C1P-permutation in case it exists. Unlike fast combinatorial algorithms for finding the consecutive ones permutation (if it exists), HND also returns an ordering when such a permutation does not exist. Thus it provides a principled heuristic for our problem that is guaranteed to return the correct answer in the ideal setting. Our experiments show that HND produces user rankings with robustly high accuracy compared to state-of-the-art truth discovery methods. We also show that our novel variant of HITS scales better in the number of users than ABH, the only prior spectral C1P reconstruction algorithm., Comment: 22 pages, 14 figures, long version of of ICDE 2024 conference paper

In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut is equal to the maximum number of disjoint dijoins. However, prior to our work, it was not even known whether at least $3$ disjoint dijoins exist in a digraph whose minimum dicut size is arbitrarily large. By building connections with nowhere-zero (circular) $k$-flows, we prove that every digraph with minimum dicut size $\tau$ contains $\frac{\tau}{k}$ disjoint dijoins if the underlying undirected graph admits a nowhere-zero (circular) $k$-flow. The existence of nowhere-zero $6$-flows in $2$-edge-connected graphs (Seymour 1981) directly leads to the existence of $\frac{\tau}{6}$ disjoint dijoins in any digraph with minimum dicut size $\tau$, which can be found in polynomial time as well. The existence of nowhere-zero circular $(2+\frac{1}{p})$-flows in $6p$-edge-connected graphs (Lov\'asz et al 2013) directly leads to the existence of $\frac{\tau p}{2p+1}$ disjoint dijoins in any digraph with minimum dicut size $\tau$ whose underlying undirected graph is $6p$-edge-connected.

In this paper, we study systems where each job or request can be split into a flexible number of sub-jobs up to a maximum limit. The number of sub-jobs a job is split into depends on the number of available servers found upon its arrival. All sub-jobs of a job are then processed in parallel at different servers leading to a linear speed-up of the job. We refer to such jobs as {\em adaptive multi-server jobs}. We study the problem of optimal assignment of such jobs when each server can process at most one sub-job at any given instant and there is no waiting room in the system. We assume that, upon arrival, a job can only access a randomly sampled subset of $k(n)$ servers from a total of $n$ servers, and the number of sub-jobs is determined based on the number of idle servers within the sampled subset. We analyze the steady-state performance of the system when system load varies according to $\lambda(n) =1 - \beta n^{-\alpha}$ for $\alpha \in [0,1)$, and $\beta \geq 0$. Our interest is to find how large the subset $k(n)$ should be in order to have zero blocking and maximum speed-up in the limit as $n \to \infty$. We first characterize the system's performance when the jobs have access to the full system, i.e., $k(n)=n$. In this setting, we show that the blocking probability approaches to zero at the rate $O(1/\sqrt{n})$ and the mean response time of accepted jobs approaches to its minimum achievable value at rate $O(1/n)$. We then consider the case where the jobs only have access to subset of servers, i.e., $k(n) < n$. We show that as long as $k(n)=\omega(n^\alpha)$, the same asymptotic performance can be achieved as in the case with full system access. In particular, for $k(n)=\Theta(n^\alpha \log n)$, we show that both the blocking probability and the mean response time approach to their desired limits at rate $O(n^{-(1-\alpha)/2})$.

The classic newsvendor model yields an optimal decision for a "newsvendor" selecting a quantity of inventory, under the assumption that the demand is drawn from a known distribution. Motivated by applications such as cloud provisioning and staffing, we consider a setting in which newsvendor-type decisions must be made sequentially, in the face of demand drawn from a stochastic process that is both unknown and nonstationary. All prior work on this problem either (a) assumes that the level of nonstationarity is known, or (b) imposes additional statistical assumptions that enable accurate predictions of the unknown demand. We study the Nonstationary Newsvendor, with and without predictions. We first, in the setting without predictions, design a policy which we prove (via matching upper and lower bounds) achieves order-optimal regret -- ours is the first policy to accomplish this without being given the level of nonstationarity of the underlying demand. We then, for the first time, introduce a model for generic (i.e. with no statistical assumptions) predictions with arbitrary accuracy, and propose a policy that incorporates these predictions without being given their accuracy. We upper bound the regret of this policy, and show that it matches the best achievable regret had the accuracy of the predictions been known. Finally, we empirically validate our new policy with experiments based on three real-world datasets containing thousands of time-series, showing that it succeeds in closing approximately 74% of the gap between the best approaches based on nonstationarity and predictions alone.

Structural alterations of the midsagittal corpus callosum (midCC) have been associated with a wide range of brain disorders. The midCC is visible on most MRI contrasts and in many acquisitions with a limited field-of-view. Here, we present an automated tool for segmenting and assessing the shape of the midCC from T1w, T2w, and FLAIR images. We train a UNet on images from multiple public datasets to obtain midCC segmentations. A quality control algorithm is also built-in, trained on the midCC shape features. We calculate intraclass correlations (ICC) and average Dice scores in a test-retest dataset to assess segmentation reliability. We test our segmentation on poor quality and partial brain scans. We highlight the biological significance of our extracted features using data from over 40,000 individuals from the UK Biobank; we classify clinically defined shape abnormalities and perform genetic analyses.

We introduce a generic technique to obtain linear relaxations of semidefinite programs with provable guarantees based on the commutativity of the constraint and the objective matrices. We study conditions under which the optimal value of the SDP and the proposed linear relaxation match, which we then relax to provide a flexible methodology to derive effective linear relaxations. We specialize these results to provide linear programs that approximate well-known semidefinite programs for the max cut problem proposed by Poljak and Rendl, and the Lovasz theta number; we prove that the linear program proposed for max cut certifies a known eigenvalue bound for the maximum cut value and is in fact stronger. Our ideas can be used to warm-start algorithms that solve semidefinite programs by iterative polyhedral approximation of the feasible region. We verify this capability through multiple experiments on the max cut semidefinite program, the Lovasz theta number and on three families of semidefinite programs obtained as convex relaxations of certain quadratically constrained quadratic problems., Comment: Updated version. Changed first section, added experiments on random QCQPs

Many applications such as hiring and university admissions involve evaluation and selection of applicants. These tasks are fundamentally difficult, and require combining evidence from multiple different aspects (what we term "attributes"). In these applications, the number of applicants is often large, and a common practice is to assign the task to multiple evaluators in a distributed fashion. Specifically, in the often-used holistic allocation, each evaluator is assigned a subset of the applicants, and is asked to assess all relevant information for their assigned applicants. However, such an evaluation process is subject to issues such as miscalibration (evaluators see only a small fraction of the applicants and may not get a good sense of relative quality), and discrimination (evaluators are influenced by irrelevant information about the applicants). We identify that such attribute-based evaluation allows alternative allocation schemes. Specifically, we consider assigning each evaluator more applicants but fewer attributes per applicant, termed segmented allocation. We compare segmented allocation to holistic allocation on several dimensions via theoretical and experimental methods. We establish various tradeoffs between these two approaches, and identify conditions under which one approach results in more accurate evaluation than the other.

In the Steiner Tree Augmentation Problem (STAP), we are given a graph $G = (V,E)$, a set of terminals $R \subseteq V$, and a Steiner tree $T$ spanning $R$. The edges $L := E \setminus E(T)$ are called links and have non-negative costs. The goal is to augment $T$ by adding a minimum cost set of links, so that there are 2 edge-disjoint paths between each pair of vertices in $R$. This problem is a special case of the Survivable Network Design Problem, which can be approximated to within a factor of 2 using iterative rounding~\cite{J2001}. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular, we achieve an approximation ratio of $(1.5 + \varepsilon)$. To do this, we employ the Local Search approach of~\cite{TZ2022} for the Tree Augmentation Problem and generalize their main decomposition theorem from links (of size two) to hyper-links. We also consider the Node-Weighted Steiner Tree Augmentation Problem (NW-STAP) in which the non-terminal nodes have non-negative costs. We seek a cheapest subset $S \subseteq V \setminus R$ so that $G[R \cup S]$ is 2-edge-connected. Using a result of Nutov~\cite{N2010}, there exists an $O(\log |R|)$-approximation for this problem. We provide an $O(\log^2 (|R|))$-approximation algorithm for NW-STAP using a greedy algorithm leveraging the spider decomposition of optimal solutions.