Arrow Research search

Author name cluster

Robert Kleinberg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

55 papers
2 author rows

Possible papers

55

FOCS Conference 2025 Conference Paper

Near-Optimal Algorithms for Omniprediction

  • Princewill Okoroafor
  • Robert Kleinberg
  • Michael P. Kim

Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class ℋ, simultaneously for every loss function within a class of losses ℒ. In this work, we give near-optimal learning algorithms for omniprediction, in both the online and offline settings. To begin, we give an oracle-efficient online learning algorithm that achieves (ℒ, ℋ)-omniprediction with $\tilde O\left( {\sqrt {T\log |\mathcal{H}|} } \right)$ regret for any class of Lipschitz loss functions ℒ ⊆ ℒ Lip. Quite surprisingly, this regret bound matches the optimal regret for minimization of a single loss function (up to a $\sqrt {\log (T)} $ factor). Given this online algorithm, we develop an online-to-offline conversion that achieves near-optimal complexity across a number of measures. In particular, for all bounded loss functions within the class of Bounded Variation losses ℒ BV (which include all convex, all Lipschitz, and all proper losses) and any (possibly-infinite) ℋ, we obtain an offline learning algorithm that, leveraging an (offline) ERM oracle and m samples from $\mathcal{D}$, returns an efficient (ℒ BV, ℋ, ε(m))-omnipredictor for ε(m) scaling near-linearly in the Rademacher complexity of Th◦ℋ, the class of all binary threshold functions on ℋ.

Details

STOC Conference 2024 Conference Paper

Breaking the VLB Barrier for Oblivious Reconfigurable Networks

  • Tegan Wilson
  • Daniel Amir
  • Nitika Saran
  • Robert Kleinberg
  • Vishal Shrivastav
  • Hakim Weatherspoon

In a landmark 1981 paper, Valiant and Brebner gave birth to the study of oblivious routing and, simultaneously, introduced its most powerful and ubiquitous method: Valiant load balancing (VLB) . By routing messages through a randomly sampled intermediate node, VLB lengthens routing paths by a factor of two but gains the crucial property of obliviousness : it balances load in a completely decentralized manner, with no global knowledge of the communication pattern. Forty years later, with datacenters handling workloads whose communication pattern varies too rapidly to allow centralized coordination, oblivious routing is as relevant as ever, and VLB continues to take center stage as a widely used — and in some settings, provably optimal — way to balance load in the network obliviously to the traffic demands. However, the ability of the network to rapidly reconfigure its interconnection topology gives rise to new possibilities. In this work we revisit the question of whether VLB remains optimal in the novel setting of reconfigurable networks. Prior work showed that VLB achieves the optimal tradeoff between latency and guaranteed throughput. In this work we show that a strictly superior latency-throughput tradeoff is achievable when the throughput bound is relaxed to hold with high probability. The same improved tradeoff is also achievable with guaranteed throughput under time-stationary demands, provided the latency bound is relaxed to hold with high probability and that the network is allowed to be semi-oblivious , using an oblivious (randomized) connection schedule but demand-aware routing. We prove that the latter result is not achievable by any fully-oblivious reconfigurable network design, marking a rare case in which semi-oblivious routing has a provable asymptotic advantage over oblivious routing. Our results are enabled by a novel oblivious routing scheme that improves VLB by stretching routing paths the minimum possible amount — an additive stretch of 1 rather than a multiplicative stretch of 2 — yet still manages to balance load with high probability when either the traffic demand matrix or the network’s interconnection schedule are shuffled by a uniformly random permutation. To analyze our routing scheme we prove an exponential tail bound which may be of independent interest, concerning the distribution of values of a bilinear form on an orbit of a permutation group action.

Details

SODA Conference 2023 Conference Paper

Non-Stochastic CDF Estimation Using Threshold Queries

  • Princewill Okoroafor
  • Vaishnavi Gupta
  • Robert Kleinberg

Estimating the empirical distribution of a scalar-valued data set is a basic and fundamental task. In this paper, we tackle the problem of estimating an empirical distribution in a setting with two challenging features. First, the algorithm does not directly observe the data; instead, it only asks a limited number of threshold queries about each sample. Second, the data are not assumed to be independent and identically distributed; instead, we allow for an arbitrary process generating the samples, including an adaptive adversary. These considerations are relevant, for example, when modeling a seller experimenting with posted prices to estimate the distribution of consumers' willingness to pay for a product: offering a price and observing a consumer's purchase decision is equivalent to asking a single threshold query about their value, and the distribution of consumers' values may be non-stationary over time, as early adopters may differ markedly from late adopters. Our main result quantifies, to within a constant factor, the sample complexity of estimating the empirical CDF of a sequence of elements of [ n ], up to ε additive error, using one threshold query per sample. The complexity depends only logarithmically on n, and our result can be interpreted as extending the existing logarithmic-complexity results for noisy binary search to the more challenging setting where noise is non-stochastic. Along the way to designing our algorithm, we consider a more general model in which the algorithm is allowed to make a limited number of simultaneous threshold queries on each sample. We solve this problem using Blackwell's Approachability Theorem and the exponential weights method. As a side result of independent interest, we characterize the minimum number of simultaneous threshold queries required by deterministic CDF estimation algorithms.

Details

NeurIPS Conference 2023 Conference Paper

Online Convex Optimization with Unbounded Memory

  • Raunak Kumar
  • Sarah Dean
  • Robert Kleinberg

Online convex optimization (OCO) is a widely used framework in online learning. In each round, the learner chooses a decision in a convex set and an adversary chooses a convex loss function, and then the learner suffers the loss associated with their current decision. However, in many applications the learner's loss depends not only on the current decision but on the entire history of decisions until that point. The OCO framework and its existing generalizations do not capture this, and they can only be applied to many settings of interest after a long series of approximation arguments. They also leave open the question of whether the dependence on memory is tight because there are no non-trivial lower bounds. In this work we introduce a generalization of the OCO framework, ``Online Convex Optimization with Unbounded Memory'', that captures long-term dependence on past decisions. We introduce the notion of $p$-effective memory capacity, $H_p$, that quantifies the maximum influence of past decisions on present losses. We prove an $O(\sqrt{H_p T})$ upper bound on the policy regret and a matching (worst-case) lower bound. As a special case, we prove the first non-trivial lower bound for OCO with finite memory~\citep{anavaHM2015online}, which could be of independent interest, and also improve existing upper bounds. We demonstrate the broad applicability of our framework by using it to derive regret bounds, and to improve and simplify existing regret bound derivations, for a variety of online learning problems including online linear control and an online variant of performative prediction.

PDF Details

NeurIPS Conference 2022 Conference Paper

Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem

  • Raunak Kumar
  • Robert Kleinberg

Bandits with knapsacks (BwK) is an influential model of sequential decision-making under uncertainty that incorporates resource consumption constraints. In each round, the decision-maker observes an outcome consisting of a reward and a vector of nonnegative resource consumptions, and the budget of each resource is decremented by its consumption. In this paper we introduce a natural generalization of the stochastic BwK problem that allows non-monotonic resource utilization. In each round, the decision-maker observes an outcome consisting of a reward and a vector of resource drifts that can be positive, negative or zero, and the budget of each resource is incremented by its drift. Our main result is a Markov decision process (MDP) policy that has constant regret against a linear programming (LP) relaxation when the decision-maker knows the true outcome distributions. We build upon this to develop a learning algorithm that has logarithmic regret against the same LP relaxation when the decision-maker does not know the true outcome distributions. We also present a reduction from BwK to our model that shows our regret bound matches existing results.

PDF Details

STOC Conference 2022 Conference Paper

Optimal oblivious reconfigurable networks

  • Daniel Amir
  • Tegan Wilson
  • Vishal Shrivastav
  • Hakim Weatherspoon
  • Robert Kleinberg
  • Rachit Agarwal 0001

Oblivious routing has a long history in both the theory and practice of networking. In this work we initiate the formal study of oblivious routing in the context of reconfigurable networks, a new architecture that has recently come to the fore in datacenter networking. These networks allow a rapidly changing bounded-degree pattern of interconnections between nodes, but the network topology and the selection of routing paths must both be oblivious to the traffic demand matrix. Our focus is on the trade-off between maximizing throughput and minimizing latency in these networks. For every constant throughput rate, we characterize (up to a constant factor) the minimum latency achievable by an oblivious reconfigurable network design that satisfies the given throughput guarantee. The trade-off between these two objectives turns out to be surprisingly subtle: the curve depicting it has an unexpected scalloped shape reflecting the fact that load-balancing becomes more difficult when the average length of routing paths is not an integer because equalizing all the path lengths is not possible. The proof of our lower bound uses LP duality to verify that Valiant load balancing is the most efficient oblivious routing scheme when used in combination with an optimally-designed reconfigurable network topology. The proof of our upper bound uses an algebraic construction in which the network nodes are identified with vectors over a finite field, the network topology is described by either the elementary basis or a sequence of Vandermonde matrices, and routing paths are constructed by selecting columns of these matrices to yield the appropriate mixture of path lengths within the shortest possible time interval.

Details

SODA Conference 2021 Conference Paper

Constrained-Order Prophet Inequalities

  • Makis Arsenis
  • Odysseas Drosis
  • Robert Kleinberg

Free order prophet inequalities bound the ratio between the expected value obtained by two parties each selecting one value from a set of independent random variables: a “prophet” who knows the value of each variable and may select the maximum one, and a “gambler” who is free to choose the order in which to observe the values but must select one of them immediately after observing it, without knowing what values will be sampled for the unobserved variables. It is known that the gambler can always ensure an expected payoff at least 0. 669 … times as great as that of the prophet. In fact, even if the gambler uses a threshold stopping rule, meaning there is a fixed threshold value such that the gambler rejects every sample below the threshold and accepts every sample above it, the threshold can always be chosen so that the gambler-to-prophet ratio is at least. … In contrast, if the gambler must observe the values in a predetermined order, the tight bound for the gambler-to-prophet ratio is 1/2. In this work we investigate a model that interpolates between these two extremes. We assume there is a predefined set of permutations of the set indexing the random variables, and the gambler is free to choose the order of observation to be any one of these predefined permutations. Surprisingly, we show that even when only two orderings are allowed — namely, the forward and reverse orderings — the gambler-to-prophet ratio improves to …, the inverse of the golden ratio. As the number of allowed permutations grows beyond 2, a striking “double plateau” phenomenon emerges: after increasing from 0. 5 to φ –1 when two permutations are allowed, the gambler-to-prophet ratio achievable by threshold stopping rules does not exceed φ –1 + o (1) until the number of allowed permutations grows to O (log n ). The ratio reaches for a suitably chosen set of O (poly( ∊ –1 ) · log n ) permutations and does not exceed even when the full set of n! permutations is allowed.

Details

ICML Conference 2019 Conference Paper

Direct Uncertainty Prediction for Medical Second Opinions

  • Maithra Raghu
  • Katy Blumer
  • Rory Sayres
  • Ziad Obermeyer
  • Robert Kleinberg
  • Sendhil Mullainathan
  • Jon M. Kleinberg

The issue of disagreements amongst human experts is a ubiquitous one in both machine learning and medicine. In medicine, this often corresponds to doctor disagreements on a patient diagnosis. In this work, we show that machine learning models can be successfully trained to give uncertainty scores to data instances that result in high expert disagreements. In particular, they can identify patient cases that would benefit most from a medical second opinion. Our central methodological finding is that Direct Uncertainty Prediction (DUP), training a model to predict an uncertainty score directly from the raw patient features, works better than Uncertainty Via Classification, the two step process of training a classifier and postprocessing the output distribution to give an uncertainty score. We show this both with a theoretical result, and on extensive evaluations on a large scale medical imaging application.

Details

NeurIPS Conference 2019 Conference Paper

Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration

  • Robert Kleinberg
  • Kevin Leyton-Brown
  • Brendan Lucier
  • Devon Graham

Algorithm configuration methods optimize the performance of a parameterized heuristic algorithm on a given distribution of problem instances. Recent work introduced an algorithm configuration procedure ( Structured Procrastination'') that provably achieves near optimal performance with high probability and with nearly minimal runtime in the worst case. It also offers an anytime property: it keeps tightening its optimality guarantees the longer it is run. Unfortunately, Structured Procrastination is not adaptive to characteristics of the parameterized algorithm: it treats every input like the worst case. Follow-up work ( LeapsAndBounds'') achieves adaptivity but trades away the anytime property. This paper introduces a new algorithm, ``Structured Procrastination with Confidence'', that preserves the near-optimality and anytime properties of Structured Procrastination while adding adaptivity. In particular, the new algorithm will perform dramatically faster in settings where many algorithm configurations perform poorly. We show empirically both that such settings arise frequently in practice and that the anytime property is useful for finding good configurations quickly.

PDF Details

ICML Conference 2018 Conference Paper

An Alternative View: When Does SGD Escape Local Minima?

  • Robert Kleinberg
  • Yuanzhi Li
  • Yang Yuan 0010

Stochastic gradient descent (SGD) is widely used in machine learning. Although being commonly viewed as a fast but not accurate version of gradient descent (GD), it always finds better solutions than GD for modern neural networks. In order to understand this phenomenon, we take an alternative view that SGD is working on the convolved (thus smoothed) version of the loss function. We show that, even if the function $f$ has many bad local minima or saddle points, as long as for every point $x$, the weighted average of the gradients of its neighborhoods is one point convex with respect to the desired solution $x^*$, SGD will get close to, and then stay around $x^*$ with constant probability. Our result identifies a set of functions that SGD provably works, which is much larger than the set of convex functions. Empirically, we observe that the loss surface of neural networks enjoys nice one point convexity properties locally, therefore our theorem helps explain why SGD works so well for neural networks.

Details

ICML Conference 2018 Conference Paper

Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?

  • Maithra Raghu
  • Alex Irpan
  • Jacob Andreas
  • Robert Kleinberg
  • Quoc V. Le
  • Jon M. Kleinberg

Deep reinforcement learning has achieved many recent successes, but our understanding of its strengths and limitations is hampered by the lack of rich environments in which we can fully characterize optimal behavior, and correspondingly diagnose individual actions against such a characterization. Here we consider a family of combinatorial games, arising from work of Erdos, Selfridge, and Spencer, and we propose their use as environments for evaluating and comparing different approaches to reinforcement learning. These games have a number of appealing features: they are challenging for current learning approaches, but they form (i) a low-dimensional, simply parametrized environment where (ii) there is a linear closed form solution for optimal behavior from any state, and (iii) the difficulty of the game can be tuned by changing environment parameters in an interpretable way. We use these Erdos-Selfridge-Spencer games not only to compare different algorithms, but test for generalization, make comparisons to supervised learning, analyse multiagent play, and even develop a self play algorithm.

Details

FOCS Conference 2018 Conference Paper

Recharging Bandits

  • Robert Kleinberg
  • Nicole Immorlica

We introduce a general model of bandit problems in which the expected payout of an arm is an increasing concave function of the time since it was last played. We first develop a PTAS for the underlying optimization problem of determining a reward-maximizing sequence of arm pulls. We then show how to use this PTAS in a learning setting to obtain sublinear regret.

Details

STOC Conference 2017 Conference Paper

Beating 1-1/e for ordered prophets

  • Melika Abolhassani
  • Soheil Ehsani
  • Hossein Esfandiari
  • MohammadTaghi Hajiaghayi
  • Robert Kleinberg
  • Brendan Lucier

Hill and Kertz studied the prophet inequality on iid distributions [ The Annals of Probability 1982 ]. They proved a theoretical bound of 1 - 1/ e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is 1/1+1/ e ≃ 0.731. This conjecture remained open prior to this paper for over 30 years. In this paper we present a threshold-based algorithm for the prophet inequality with n iid distributions. Using a nontrivial and novel approach we show that our algorithm is a 0.738-approximation algorithm. By beating the bound of 1/1+1/ e , this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-uniform distributions and discuss its applications in mechanism design.

Details

STOC Conference 2017 Conference Paper

Bernoulli factories and black-box reductions in mechanism design

  • Shaddin Dughmi
  • Jason D. Hartline
  • Robert Kleinberg
  • Rad Niazadeh

We provide a polynomial-time reduction from Bayesian incentive-compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces. The key technical barrier preventing exact incentive compatibility in prior black-box reductions is that repairing violations of incentive constraints requires understanding the distribution of the mechanism's output, which is typically #P-hard to compute. Reductions that instead estimate the output distribution by sampling inevitably suffer from sampling error, which typically precludes exact incentive compatibility. We overcome this barrier by employing and generalizing the computational model in the literature on "Bernoulli Factories". In a Bernoulli factory problem, one is given a function mapping the bias of an 'input coin' to that of an 'output coin', and the challenge is to efficiently simulate the output coin given only sample access to the input coin. Consider a generalization which we call the "expectations from samples" computational model, in which a problem instance is specified by a function mapping the expected values of a set of input distributions to a distribution over outcomes. The challenge is to give a polynomial time algorithm that exactly samples from the distribution over outcomes given only sample access to the input distributions. In this model we give a polynomial time algorithm for the function given by "exponential weights": expected values of the input distributions correspond to the weights of alternatives and we wish to select an alternative with probability proportional to its weight. This algorithm is the key ingredient in designing an incentive compatible mechanism for bipartite matching, which can be used to make the approximately incentive compatible reduction of Hartline-Malekian-Kleinberg [2015] exactly incentive compatible.

Details

IJCAI Conference 2017 Conference Paper

Efficiency Through Procrastination: Approximately Optimal Algorithm Configuration with Runtime Guarantees

  • Robert Kleinberg
  • Kevin Leyton-Brown
  • Brendan Lucier

Algorithm configuration methods have achieved much practical success, but to date have not been backed by meaningful performance guarantees. We address this gap with a new algorithm configuration framework, Structured Procrastination. With high probability and nearly as quickly as possible in the worst case, our framework finds an algorithm configuration that provably achieves near optimal performance. Moreover, its running time requirements asymptotically dominate those of existing methods.

PDF Details

SODA Conference 2017 Conference Paper

Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals

  • Nicole Immorlica
  • Robert Kleinberg
  • Brendan Lucier
  • Morteza Zadomighaddam

We prove that the two-dimensional Schelling segregation model yields monochromatic regions of size exponential in the area of individuals’ neighborhoods, provided that the tolerance parameter is a constant strictly less than 1/2 but sufficiently close to it. Our analysis makes use of a connection with the first-passage percolation model from the theory of stochastic processes.

Details

SODA Conference 2015 Conference Paper

On the Complexity of Computing an Equilibrium in Combinatorial Auctions

  • Shahar Dobzinski
  • Hu Fu 0001
  • Robert Kleinberg

We study combinatorial auctions where each item is sold separately but simultaneously via a second price auction. We ask whether it is possible to efficiently compute in this game a pure Nash equilibrium with social welfare close to the optimal one. We show that when the valuations of the bidders are submodular, in many interesting settings (e. g. , constant number of bidders, budget additive bidders) computing an equilibrium with good welfare is essentially as easy as computing, completely ignoring incentives issues, an allocation with good welfare. On the other hand, for subadditive valuations, we show that computing an equilibrium requires exponential communication. Finally, for XOS (a. k. a. fractionally subadditive) valuations, we show that if there exists an efficient algorithm that finds an equilibrium, it must use techniques that are very different from the ones currently known.

Details

ICML Conference 2014 Conference Paper

Combinatorial Partial Monitoring Game with Linear Feedback and Its Applications

  • Tian Lin
  • Bruno D. Abrahao
  • Robert Kleinberg
  • John C. S. Lui
  • Wei Chen 0013

In online learning, a player chooses actions to play and receives reward and feedback from the environment with the goal of maximizing her reward over time. In this paper, we propose the model of combinatorial partial monitoring games with linear feedback, a model which simultaneously addresses limited feedback, infinite outcome space of the environment and exponentially large action space of the player. We present the Global Confidence Bound (GCB) algorithm, which integrates ideas from both combinatorial multi-armed bandits and finite partial monitoring games to handle all the above issues. GCB only requires feedback on a small set of actions and achieves O(T^\frac23\log T) distribution-independent regret and O(\log T) distribution-dependent regret (the latter assuming unique optimal action), where T is the total time steps played. Moreover, the regret bounds only depend linearly on \log |X| rather than |X|, where X is the action space. GCB isolates offline optimization tasks from online learning and avoids explicit enumeration of all actions in the online learning part. We demonstrate that our model and algorithm can be applied to a crowdsourcing application leading to both an efficient learning algorithm and low regret, and argue that they can be applied to a wide range of combinatorial applications constrained with limited feedback.

Details

SODA Conference 2014 Conference Paper

Prophet Inequalities with Limited Information

  • Pablo Daniel Azar
  • Robert Kleinberg
  • S. Matthew Weinberg

In the classical prophet inequality, a gambler observes a sequence of stochastic rewards V 1, …, V n and must decide, for each reward V i, whether to keep it and stop the game or to forfeit the reward forever and reveal the next value V i. The gambler's goal is to obtain a constant fraction of the expected reward that the optimal offline algorithm would get. Recently, prophet inequalities have been generalized to settings where the gambler can choose k items, and, more generally, where he can choose any independent set in a matroid. However, all the existing algorithms require the gambler to know the distribution from which the rewards V 1, …, V n are drawn. The assumption that the gambler knows the distribution from which V 1, …, V n are drawn is very strong. Instead, we work with the much simpler assumption that the gambler only knows a few samples from this distribution. We construct the first single-sample prophet inequalities for many settings of interest, whose guarantees all match the best possible asymptotically, even with full knowledge of the distribution. Specifically, we provide a novel single-sample algorithm when the gambler can choose any k elements whose analysis is based on random walks with limited correlation. In addition, we provide a black-box method for converting specific types of solutions to the related secretary problem to single-sample prophet inequalities, and apply it to several existing algorithms. Finally, we provide a constant-sample prophet inequality for constant-degree bipartite matchings. In addition, we apply these results to design the first posted-price and multi-dimensional auction mechanisms with limited information in settings with asymmetric bidders. Connections between prophet inequalities and posted-price mechanisms are already known, but applying the existing framework requires knowledge of the underlying distributions, as well as the so-called “virtual values” even when the underlying prophet inequalities do not. We therefore provide an extension of this framework that bypasses virtual values altogether, allowing our mechanisms to take full advantage of the limited information required by our new prophet inequalities.

Details

FOCS Conference 2013 Conference Paper

Bandits with Knapsacks

  • Ashwinkumar Badanidiyuru
  • Robert Kleinberg
  • Aleksandrs Slivkins

Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trials, to communication networks, to Web search and advertising. In many of these application domains the learner may be constrained by one or more supply (or budget) limits, in addition to the customary limitation on the time horizon. The literature lacks a general model encompassing these sorts of problems. We introduce such a model, called "bandits with knapsacks", that combines aspects of stochastic integer programming with online learning. A distinctive feature of our problem, in comparison to the existing regret-minimization literature, is that the optimal policy for a given latent distribution may significantly outperform the policy that plays the optimal fixed arm. Consequently, achieving sub linear regret in the bandits-with-knapsacks problem is significantly more challenging than in conventional bandit problems. We present two algorithms whose reward is close to the information-theoretic optimum: one is based on a novel "balanced exploration" paradigm, while the other is a primal-dual algorithm that uses multiplicative updates. Further, we prove that the regret achieved by both algorithms is optimal up to polylogarithmic factors. We illustrate the generality of the problem by presenting applications in a number of different domains including electronic commerce, routing, and scheduling. As one example of a concrete application, we consider the problem of dynamic posted pricing with limited supply and obtain the first algorithm whose regret, with respect to the optimal dynamic policy, is sub linear in the supply.

Details

SODA Conference 2013 Conference Paper

Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching

  • Nikhil R. Devanur
  • Kamal Jain
  • Robert Kleinberg

We give a simple proof that the ranking algorithm of Karp, Vazirani and Vazirani [KVV90] is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. The approach also generalizes easily to the vertex-weighted version considered by Agarwal et al. [AGKM11]. Further we show that the proof is very similar to the deterministic primal-dual argument for the online budgeted allocation problem with small bids (also called the AdWords problem) of Mehta et al. [MSVV05].

Details

STOC Conference 2012 Conference Paper

Improving christofides' algorithm for the s-t path TSP

  • Hyung-Chan An
  • Robert Kleinberg
  • David B. Shmoys

We present a deterministic (1+√5/2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on $n$ vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact had been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides' algorithm variant. Our algorithm also proves an upper bound of 1+√5/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.

Details

STOC Conference 2012 Conference Paper

Matroid prophet inequalities

  • Robert Kleinberg
  • S. Matthew Weinberg

Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve at least half as much reward, in expectation, as a "prophet" who knows the sampled values of each random variable and can choose the largest one. We generalize this result to the setting in which the gambler and the prophet are allowed to make more than one selection, subject to a matroid constraint. We show that the gambler can still achieve at least half as much reward as the prophet; this result is the best possible, since it is known that the ratio cannot be improved even in the original prophet inequality, which corresponds to the special case of rank-one matroids. Generalizing the result still further, we show that under an intersection of $p$ matroid constraints, the prophet's reward exceeds the gambler's by a factor of at most $O(p)$, and this factor is also tight. Beyond their interest as theorems about pure online algoritms or optimal stopping rules, these results also have applications to mechanism design. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate optimal mechanisms in both single-parameter and multi-parameter Bayesian settings. In particular, our results imply the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings.

Details

SODA Conference 2012 Conference Paper

Sketching valuation functions

  • Ashwinkumar Badanidiyuru
  • Shahar Dobzinski
  • Hu Fu 0001
  • Robert Kleinberg
  • Noam Nisan
  • Tim Roughgarden

Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes of set functions can be sketched. More formally let f be a function mapping subsets of some ground set [ n ] to the non-negative real numbers. We say that f′ is an α-sketch of f if for every set S, the value f′ ( S ) lies between f ( S )/α and f ( S ), and f′ can be specified by poly( n ) bits. We show that for every subadditive function f there exists an α-sketch where α = n 1/2 · O (polylog( n )). Furthermore, we provide an algorithm that finds these sketches with a polynomial number of demand queries. This is essentially the best we can hope for since: 1. We show that there exist subadditive functions (in fact, XOS functions) that do not admit an o ( n 1/2 ) sketch. (Balcan and Harvey [3] previously showed that there exist functions belonging to the class of substitutes valuations that do not admit an O ( n 1/3 ) sketch.) 2. We prove that every deterministic algorithm that accesses the function via value queries only cannot guarantee a sketching ratio better than n 1−ε. We also show that coverage functions, an interesting subclass of submodular functions, admit arbitrarily good sketches. Finally, we show an interesting connection between sketching and learning. We show that for every class of valuations, if the class admits an α-sketch, then it can be α-approximately learned in the PMAC model of Balcan and Harvey. The bounds we prove are only information-theoretic and do not imply the existence of computationally efficient learning algorithms in general.

Details

FOCS Conference 2011 Conference Paper

Lexicographic Products and the Power of Non-linear Network Coding

  • Anna Blasiak
  • Robert Kleinberg
  • Eyal Lubetzky

We introduce a technique for establishing and amplifying gaps between parameters of network coding and index coding problems. The technique uses linear programs to establish separations between combinatorial and coding-theoretic parameters and applies hyper graph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that this is a valid dual solution of the product. Our result is general enough to apply to a large family of linear programs. This blend of linear programs and lexicographic products gives a recipe for constructing hard instances in which the gap between combinatorial or coding-theoretic parameters is polynomially large. We find polynomial gaps in cases in which the largest previously known gaps were only small constant factors or entirely unknown. Most notably, we show a polynomial separation between linear and non-linear network coding rates. This involves exploiting a connection between matroids and index coding to establish a previously unknown separation between linear and non-linear index coding rates. We also construct index coding problems with a polynomial gap between the broadcast rate and the trivial lower bound for which no gap was previously known.

Details

STOC Conference 2011 Conference Paper

Optimal auctions with correlated bidders are easy

  • Shahar Dobzinski
  • Hu Fu 0001
  • Robert Kleinberg

We consider the problem of designing a revenue-maximizing auction for a single item, when the values of the bidders are drawn from a correlated distribution. We observe that there exists an algorithm that finds the optimal randomized mechanism that runs in time polynomial in the size of the support. We leverage this result to show that in the oracle model introduced by Ronen and Saberi [FOCS'02], there exists a polynomial time truthful in expectation mechanism that provides a (1.5+ε)-approximation to the revenue achievable by an optimal truthful-in-expectation mechanism, and a polynomial time deterministic truthful mechanism that guarantees 5/3 approximation to the revenue achievable by an optimal deterministic truthful mechanism. We show that the 5/3-approximation mechanism provides the same approximation ratio also with respect to the optimal truthful-in-expectation mechanism. This shows that the performance gap between truthful-in-expectation and deterministic mechanisms is relatively small. En route, we solve an open question of Mehta and Vazirani [EC'04]. Finally, we extend some of our results to the multi-item case, and show how to compute the optimal truthful-in-expectation mechanisms for bidders with more complex valuations.

Details

FOCS Conference 2011 Conference Paper

Which Networks are Least Susceptible to Cascading Failures?

  • Lawrence E. Blume
  • David A. Easley
  • Jon M. Kleinberg
  • Robert Kleinberg
  • Éva Tardos

The spread of a cascading failure through a network is an issue that comes up in many domains - in the contagious failures that spread among financial institutions during a financial crisis, through nodes of a power grid or communication network during a widespread outage, or through a human population during the outbreak of an epidemic disease. Here we study a natural model of threshold contagion: each node v is assigned a numerical threshold ℓ(v) drawn independently from an underlying distribution μ, and v will fail as soon as ℓ(v) of its neighbors fail. Despite the simplicity of the formulation, it has been very challenging to analyze the failure processes that arise from arbitrary threshold distributions; even qualitative questions concerning which graphs are the most resilient to cascading failures in these models have been difficult to resolve. Here we develop a set of new techniques for analyzing the failure probabilities of nodes in arbitrary graphs under this model, and we compare different graphs G according to their μ-risk, defined as the maximum failure probability of any node in G when thresholds are drawn from μ. We find that the space of threshold distributions has a surprisingly rich structure when we consider the risk that these thresholds induce on different graphs: small shifts in the distribution of the thresholds can favor graphs with a maximally clustered structure (i. e. , cliques), those with a maximally branching structure (trees), or even intermediate hybrids.

Details

AAAI Conference 2010 Conference Paper

Nonmanipulable Randomized Tournament Selections

  • Alon Altman
  • Robert Kleinberg

Tournament solution concepts, selecting winners based on a pairwise dominance relation are an important structure often used in sports, as well as elections, and argumentation theory. Manipulation of such choice rules by coalitions of agents are a significant problem in most common rules. We deal with the problem of the manipulation of randomized choice rules by coalitions varying from a single agent, to two or more agents. We define two notions of coalitional manipulations of such choice rules based on whether or not utility is transferable. We show useful choice rules satisfying both notions of nonmanipulability, and for the transferable utility case provide bounds on the level of Condorcet consistency.

PDF Details

SODA Conference 2010 Conference Paper

Pricing Randomized Allocations

  • Patrick Briest
  • Shuchi Chawla 0001
  • Robert Kleinberg
  • S. Matthew Weinberg

Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational mechanism design. We investigate the role of randomized outcomes (henceforth, “lotteries”) in the context of a fundamental and archetypical multi-parameter mechanism design problem: selling heterogeneous items to unit-demand bidders. To what extent can a seller improve her revenue by pricing lotteries rather than items, and does this modification of the problem affect its computational tractability? Our results show that the answers to these questions hinge on whether consumers can purchase only one lottery (the buy-one model) or purchase any set of lotteries and receive an independent sample from each (the buy-many model). In the buy-one model, there is a polynomial-time algorithm to compute the revenue-maximizing envy-free prices (thus overcoming the inapproximability of the corresponding item pricing problem) and the revenue of the optimal lottery system can exceed the revenue of the optimal item pricing by an unbounded factor as long as the number of item types is at least 4. In the buy-many model with n item types, the profit achieved by lottery pricing can exceed item pricing by a factor of Θ(log n ) but not more, and optimal lottery pricing cannot be approximated within a factor of ( n ε ) for some ε > 0, unless NP ⊆ ∩ δ>0 BPTIME. Our lower bounds rely on a mixture of geometric and algebraic techniques, whereas the upper bounds use a novel rounding scheme to transform a mechanism with randomized outcomes into one with deterministic outcomes while losing only a bounded amount of revenue.

Details

STOC Conference 2009 Conference Paper

Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract

  • Robert Kleinberg
  • Georgios Piliouras
  • Éva Tardos

We study the outcome of natural learning algorithms in atomic congestion games. Atomic congestion games have a wide variety of equilibria often with vastly differing social costs. We show that in almost all such games, the well-known multiplicative-weights learning algorithm results in convergence to pure equilibria. Our results show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game introduced by Koutsoupias and Papadimitriou, which has super-constant price of anarchy and has correlated equilibria that are exponentially worse than any mixed Nash equilibrium.

Details

ICML Conference 2008 Conference Paper

Learning diverse rankings with multi-armed bandits

  • Filip Radlinski
  • Robert Kleinberg
  • Thorsten Joachims

Algorithms for learning to rank Web documents usually assume a document's relevance is independent of other documents. This leads to learned ranking functions that produce rankings with redundant results. In contrast, user studies have shown that diversity at high ranks is often preferred. We present two online learning algorithms that directly learn a diverse ranking of documents based on users' clicking behavior. We show that these algorithms minimize abandonment, or alternatively, maximize the probability that a relevant document is found in the top k positions of a ranking. Moreover, one of our algorithms asymptotically achieves optimal worst-case performance even if users' interests change.

Details

STOC Conference 2008 Conference Paper

Multi-armed bandits in metric spaces

  • Robert Kleinberg
  • Aleksandrs Slivkins
  • Eli Upfal

In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of $n$ trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. In this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the "Lipschitz MAB problem". We present a complete solution for the multi-armed problem in this setting. That is, for every metric space (L,X) we define an isometry invariant Max Min COV(X) which bounds from below the performance of Lipschitz MAB algorithms for $X$, and we present an algorithm which comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions.

Details

FOCS Conference 2005 Conference Paper

Group-theoretic Algorithms for Matrix Multiplication

  • Henry Cohn
  • Robert Kleinberg
  • Balázs Szegedy
  • Chris Umans

We further develop the group-theoretic approach to fast matrix multiplication introduced by Cohn and Umans, and for the first time use it to derive algorithms asymptotically faster than the standard algorithm. We describe several families of wreath product groups that achieve matrix multiplication exponent less than 3, the asymptotically fastest of which achieves exponent 2. 41. We present two conjectures regarding specific improvements, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.

Details

STOC Conference 2004 Conference Paper

(Almost) tight bounds and existence theorems for confluent flows

  • Jiangzhuo Chen
  • Robert Kleinberg
  • László Lovász 0001
  • Rajmohan Rajaraman
  • Ravi Sundaram
  • Adrian Vetta

A flow is said to be confluent if at any node all the flow leaves along a single edge. Given a directed graph G with k sinks and non-negative demands on all the nodes of G , we consider the problem of determining a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized. Confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are confluent since Internet routing is destination based.We present near-tight approximation algorithms, hardness results, and existence theorems for confluent flows. The main result of this paper is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln( k ) in G , if G admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph G that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than H k , thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (lg k )/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if G admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in G with congestion at most 1 that satisfies 1/3 fraction of total demand.We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph were k connected. In particular, we prove that k -connected graphs with k sinks admit confluent flows of congestion less than C + d max , where C is the congestion of the best splittable flow, and d max is the maximum demand of any node in G . The proof of this existence theorem is non-constructive and relies on topological techniques introduced in [16].

Details

STOC Conference 2004 Conference Paper

Adaptive routing with end-to-end feedback: distributed learning and geometric approaches

  • Baruch Awerbuch
  • Robert Kleinberg

Minimal delay routing is a fundamental task in networks. Since delays depend on the (potentially unpredictable) traffic distribution, online delay optimization can be quite challenging. While uncertainty about the current network delays may make the current routing choices sub-optimal, the algorithm can nevertheless try to learn the traffic patterns and keep adapting its choice of routing paths so as to perform nearly as well as the best static path. This online shortest path problem is a special case of online linear optimization , a problem in which an online algorithm must choose, in each round, a strategy from some compact set S ⊆ R d so as to try to minimize a linear cost function which is only revealed at the end of the round. Kalai and Vempala[4] gave an algorithm for such problems in the transparent feedback model, where the entire cost function is revealed at the end of the round. Here we present an algorithm for online linear optimization in the more challenging opaque feedback model, in which only the cost of the chosen strategy is revealed at the end of the round. In the special case of shortest paths, opaque feedback corresponds to the notion that in each round the algorithm learns only the end-to-end cost of the chosen path, not the cost of every edge in the network.We also present a second algorithm for online shortest paths, which solves the shortest-path problem using a chain of online decision oracles, one at each node of the graph. This has several advantages over the online linear optimization approach. First, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. Second, even in the case of an oblivious adversary, the second algorithm performs better than the first, as measured by their additive regret.

Details

NeurIPS Conference 2004 Conference Paper

Nearly Tight Bounds for the Continuum-Armed Bandit Problem

  • Robert Kleinberg

In the multi-armed bandit problem, an online algorithm must choose from a set of strategies in a sequence of n trials so as to minimize the total cost of the chosen strategies. While nearly tight upper and lower bounds are known in the case when the strategy set is finite, much less is known when there is an infinite strategy set. Here we consider the case when the set of strategies is a subset of Rd, and the cost functions are continuous. In the d = 1 case, we improve on the best-known upper and lower bounds, closing the gap to a sublogarithmic factor. We also con- sider the case where d > 1 and the cost functions are convex, adapting a recent online convex optimization algorithm of Zinkevich to the sparser feedback model of the multi-armed bandit problem. 1 Introduction In an online decision problem, an algorithm must choose from among a set of strategies in each of n consecutive trials so as to minimize the total cost of the chosen strategies. The costs of strategies are specified by a real-valued function which is defined on the entire strategy set and which varies over time in a manner initially unknown to the algorithm. The archetypical online decision problems are the best expert problem, in which the entire cost function is revealed to the algorithm as feedback at the end of each trial, and the multi- armed bandit problem, in which the feedback reveals only the cost of the chosen strategy. The names of the two problems are derived from the metaphors of combining expert advice (in the case of the best expert problem) and learning to play the best slot machine in a casino (in the case of the multi-armed bandit problem). The applications of online decision problems are too numerous to be listed here. In ad- dition to occupying a central position in online learning theory, algorithms for such prob- lems have been applied in numerous other areas of computer science, such as paging and caching [6, 14], data structures [7], routing [4, 5], wireless networks [19], and online auc- tion mechanisms [8, 15]. Algorithms for online decision problems are also applied in a broad range of fields outside computer science, including statistics (sequential design of experiments [18]), economics (pricing [20]), game theory (adaptive game playing [13]), and medical decision making (optimal design of clinical trials [10]). Multi-armed bandit problems have been studied quite thoroughly in the case of a finite strategy set, and the performance of the optimal algorithm (as a function of n) is known M. I. T. CSAIL, Cambridge, MA 02139. Email: rdk@csail. mit. edu. Supported by a Fannie and John Hertz Foundation Fellowship. up to a constant factor [3, 18]. In contrast, much less is known in the case of an infinite strategy set. In this paper, we consider multi-armed bandit problems with a continuum of strategies, parameterized by one or more real numbers. In other words, we are studying online learning problems in which the learner designates a strategy in each time step by specifying a d-tuple of real numbers (x1, .. ., xd); the cost function is then evaluated at (x1, .. ., xd) and this number is reported to the algorithm as feedback. Recent progress on such problems has been spurred by the discovery of new algorithms (e. g. [4, 9, 16, 21]) as well as compelling applications. Two such applications are online auction mechanism design [8, 15], in which the strategy space is an interval of feasible prices, and online oblivious routing [5], in which the strategy space is a flow polytope. Algorithms for online decisions problems are often evaluated in terms of their regret, de- fined as the difference in expected cost between the sequence of strategies chosen by the algorithm and the best fixed (i. e. not time-varying) strategy. While tight upper and lower bounds on the regret of algorithms for the K-armed bandit problem have been known for many years [3, 18], our knowledge of such bounds for continuum-armed bandit prob- lems is much less satisfactory. For a one-dimensional strategy space, the first algorithm with sublinear regret appeared in [1], while the first polynomial lower bound on regret ap- peared in [15]. For Lipschitz-continuous cost functions (the case introduced in [1]), the best known upper and lower bounds for this problem are currently O(n3/4) and (n1/2), respectively [1, 15], leaving as an open question the problem of determining tight bounds for the regret as a function of n. Here, we solve this open problem by sharpening the up- per and lower bounds to O(n2/3 log1/3(n)) and (n2/3), respectively, closing the gap to a sublogarithmic factor. Note that this requires improving the best known algorithm as well as the lower bound technique. Recently, and independently, Eric Cope [11] considered a class of cost functions obeying a more restrictive condition on the shape of the function near its optimum, and for such functions he obtained a sharper bound on regret than the bound proved here for uniformly locally Lipschitz cost functions. Cope requires that each cost function C achieves its op- timum at a unique point, and that there exist constants K0 > 0 and p 1 such that for all x, |C(x) - C()| K0 x - p. For this class of cost functions -- which is probably broad enough to capture most cases of practical interest -- he proves that the regret of the optimal continuum-armed bandit algorithm is O(n-1/2), and that this bound is tight. For a d-dimensional strategy space, any multi-armed bandit algorithm must suffer regret depending exponentially on d unless the cost functions are further constrained. (This is demonstrated by a simple counterexample in which the cost function is identically zero in all but one orthant of Rd, takes a negative value somewhere in that orthant, and does not vary over time. ) For the best-expert problem, algorithms whose regret is polynomial in d and sublinear in n are known for the case of cost functions which are constrained to be linear [16] or convex [21]. In the case of linear cost functions, the relevant algorithm has been adapted to the multi-armed bandit setting in [4, 9]. Here we adapt the online convex programming algorithm of [21] to the continuum-armed bandit setting, obtaining the first known algorithm for this problem to achieve regret depending polynomially on d and sublinearly on n. A remarkably similar algorithm was discovered independently and simultaneously by Flaxman, Kalai, and McMahan [12]. Their algorithm and analysis are superior to ours, requiring fewer smoothness assumptions on the cost functions and producing a tighter upper bound on regret. 2 Terminology and Conventions We will assume that a strategy set S Rd is given, and that it is a compact subset of Rd. Time steps will be denoted by the numbers {1, 2, .. ., n}. For each t {1, 2, .. ., n} a cost function Ct: S R is given. These cost functions must satisfy a continuity property based on the following definition. A function f is uniformly locally Lipschitz with constant L (0 L 0) if it is the case that for all u, u S with u - u, |f(u) - f(u )| L u - u. (Here, denotes the Euclidean norm on Rd. ) The class of all such functions f will be denoted by ulL(, L, ). We will consider two models which may govern the cost functions. The first of these is identical with the continuum-armed bandit problem considered in [1], except that [1] formulates the problem in terms of maximizing reward rather than minimizing cost. The second model concerns a sequence of cost functions chosen by an oblivious adversary. Random The functions C1, .. ., Cn are independent, identically distributed random sam- ples from a probability distribution on functions C: S R. The expected cost function C: S R is defined by C(u) = E(C(u)) where C is a random sample from this distribution. This function C is required to belong to ulL(, L, ) for some specified, L, . In addition, we assume there exist positive constants, s0 such that if C is a random sample from the given distribution on cost functions, then 1 E(esC(u)) e 2s2 2 |s| s0, u S. The "best strategy" u is defined to be any element of arg min uS C (u). (This set is non-empty, by the compactness of S. ) Adversarial The functions C1, .. ., Cn are a fixed sequence of functions in ulL(, L, ), taking values in [0, 1]. The "best strategy" u is defined to be any element of arg min n uS C t=1 t(u). (Again, this set is non-empty by compactness. ) A multi-armed bandit algorithm is a rule for deciding which strategy to play at time t, given the outcomes of the first t - 1 trials. More formally, a deterministic multi-armed bandit algorithm U is a sequence of functions U1, U2, .. . such that Ut: (S R)t-1 S. The interpretation is that Ut(u1, x1, u2, x2, .. ., ut-1, xt-1) defines the strategy to be chosen at time t if the algorithm's first t - 1 choices were u1, .. ., ut-1 respectively, and their costs were x1, .. ., xt-1 respectively. A randomized multi-armed bandit algorithm is a proba- bility distribution over deterministic multi-armed bandit algorithms. (If the cost functions are random, we will assume their randomness is independent of the algorithm's random choices. ) For a randomized multi-armed bandit algorithm, the n-step regret Rn is the ex- pected difference in total cost between the algorithm's chosen strategies u1, u2, .. ., un and the best strategy u, i. e. n Rn = E Ct(ut) - Ct(u). t=1 Here, the expectation is over the algorithm's random choices and (in the random-costs model) the randomness of the cost functions. 3 Algorithms for the one-parameter case (d = 1) The continuum-bandit algorithm presented in [1] is based on computing an estimate ^ C of the expected cost function C which converges almost surely to C as n. This estimate is obtained by devoting a small fraction of the time steps (tending to zero as n ) to sampling the random cost functions at an approximately equally-spaced sequence of "design points" in the strategy set, and combining these samples using a kernel estimator. When the algorithm is not sampling a design point, it chooses a strategy which minimizes expected cost according to the current estimate ^ C. The convergence of ^ C to C ensures that the average cost in these "exploitation steps" converges to the minimum value of C. A drawback of this approach is its emphasis on estimating the entire function C. Since the algorithm's goal is to minimize cost, its estimate of C need only be accurate for strategies where C is near its minimum. Elsewhere a crude estimate of C would have sufficed, since such strategies may safely be ignored by the algorithm. The algorithm in [1] thus uses its sampling steps inefficiently, focusing too much attention on portions of the strategy interval where an accurate estimate of C is unnecessary. We adopt a different approach which eliminates this inefficiency and also leads to a much simpler algorithm. First we discretize the strategy space by constraining the algorithm to choose strategies only from a fixed, finite set of K equally spaced design points {1/K, 2/K, .. ., 1}. (For simplicity, we are assuming here and for the rest of this section that S = [0, 1]. ) This reduces the continuum-armed bandit problem to a finite-armed bandit problem, and we may apply one of the standard algorithms for such problems. Our continuum-armed bandit algorithm is shown in Figure 1. The outer loop uses a standard doubling technique to transform a non-uniform algorithm to a uniform one. The inner loop requires a subroutine MAB which should implement a finite-armed bandit algorithm appropriate for the cost model under consideration. For example, MAB could be the algorithm UCB1 of [2] in the random case, or the algorithm Exp3 of [3] in the adversarial case. The semantics of MAB are as follows: it is initialized with a finite set of strategies; subsequently it recommends strategies in this set, waits to learn the feedback score for its recommendation, and updates its recommendation when the feedback is received. The analysis of this algorithm will ensure that its choices have low regret relative to the best design point. The Lipschitz regularity of C guarantees that the best design point performs nearly as well, on average, as the best strategy in S. ALGORITHM CAB1 T 1 while T n 1 2+1 K T log T Initialize MAB with strategy set {1/K, 2/K, .. ., 1}. for t = T, T + 1, .. ., min(2T - 1, n) Get strategy ut from MAB. Play ut and discover Ct(ut). Feed 1 - Ct(ut) back to MAB. end T 2T end Figure 1: Algorithm for the one-parameter continuum-armed bandit problem Theorem 3. 1. In both the random and adversarial models, the regret of algorithm CAB1 +1 is O(n 2+1 log 2+1 (n)). Proof Sketch. Let q =, so that the regret bound is O(n1-q logq(n)). It suffices to 2+1 prove that the regret in the inner loop is O(T 1-q logq(T )); if so, then we may sum this bound over all iterations of the inner loop to get a geometric progression with constant ratio, whose largest term is O(n1-q logq(n)). So from now on assume that T is fixed and that K is defined as in Figure 1, and for simplicity renumber the T steps in this iteration of inner loop so that the first is step 1 and the last is step T. Let u be the best strategy in S, and let u be the element of {1/K, 2/K, .. ., 1} nearest to u. Then T |u - u| T T E Ct(u ) - Ct(u) = O T 1-q logq(T ). K t=1 It remains to show that E T C t=1 t(ut) - Ct(u ) = O T 1-q logq(T ). For the adver- sarial model, this follows directly from Corollary 4. 2 in [3], which asserts that the regret of Exp3 is O T K log K. For the random model, a separate argument is required. (The upper bound for the adversarial model doesn't directly imply an upper bound for the random model, since the cost functions are required to take values in [0, 1] in the ad- versarial model but not in the random model. ) For u {1/K, 2/K, .. ., 1} let (u) = C(u) - C(u ). Let = K log(T)/T, and partition the set {1/K, 2/K, .. ., 1} into two subsets A, B according to whether (u) 0, the middle third of [ak-1, bk-1] is subdivided into intervals of width wk = 3-k! , and [ak, bk] is one of these subintervals chosen uniformly at random. Now let f (x) = 1/3 + 3-1 - 1/3 w k B[ak, bk](x). k=1 Finally, define a probability distribution on functions C: [0, 1] [0, 1] by the following rule: sample uniformly at random from the open interval (0, 1) and put C(x) = f(x). The relevant technical properties of this construction are summarized in the following lemma. Lemma 4. 1. Let {u} = [a k=1 k, bk]. The function f (x) belongs to ulL(, L, ) for some constants L, , it takes values in [1/3, 2/3], and it is uniquely maximized at u. For each (0, 1), the function C(x) = f(x) belongs to ulL(, L, ) for some constants L, , and is uniquely minimized at u. The same two properties are satisfied by the function C(x) = E(0, 1) f(x) = (1 + f(x))-1. Theorem 4. 2. For any randomized multi-armed bandit algorithm, there exists a probability distribution on cost functions such that for all +1 -o(1) n 2+1 kw k = n. k Although this proof sketch rests on a much more complicated construction than the lower bound proof for the finite-armed bandit problem given by Auer et al in [3], one may follow essentially the same series of steps as in their proof to make the sketch given above into a rigorous proof. The only significant technical difference is that we are working with continuous-valued rather than discrete-valued random variables, which necessitates using the differential Kullback-Leibler distance1 rather than working with the discrete Kullback- Leibler distance as in [3]. 5 An online convex optimization algorithm We turn now to continuum-armed bandit problems with a strategy space of dimension d > 1. As mentioned in the introduction, for any randomized multi-armed bandit al- gorithm there is a cost function C (with any desired degree of smoothness and bound- edness) such that the algorithm's regret is (2d) when faced with the input sequence C1 = C2 =. .. = Cn = C. As a counterpoint to this negative result, we seek interesting classes of cost functions which admit a continuum-armed bandit algorithm whose regret is polynomial in d (and, as always, sublinear in n). A natural candidate is the class of convex, smooth functions on a closed, bounded, convex strategy set S Rd, since this is the most 1Defined by the formula KL(P Q) = R log (p(x)/q(x)) dp(x), for probability distributions P, Q with density functions p, q. general class of functions for which the corresponding best-expert problem is known to admit an efficient algorithm, namely Zinkevich's greedy projection algorithm [21]. Greedy projection is initialized with a sequence of learning rates 1 > 2 >. .. . It selects an arbitrary initial strategy u1 S and updates its strategy in each subsequent time step t according to the rule ut+1 = P (ut - t Ct(ut)), where Ct(ut) is the gradient of Ct at ut and P: Rd S is the projection operator which maps each point of Rd to the nearest point of S. (Here, distance is measured according to the Euclidean norm. ) Note that greedy projection is nearly a multi-armed bandit algorithm: if the algorithm's feedback when sampling strategy ut were the vector Ct(ut) rather than the number Ct(ut), it would have all the information required to run greedy projection. To adapt this algorithm to the multi-armed bandit setting, we use the following idea: group the timeline into phases of d + 1 consecutive steps, with a cost function C for each phase defined by averaging the cost functions at each time step of. In each phase use trials at d + 1 affinely independent points of S, located at or near ut, to estimate the gradient C(ut). 2 To describe the algorithm, it helps to assume that the convex set S is in isotropic position in Rd. (If not, we may bring it into isotropic position by an affine transformation of the coordi- nate system. This does not increase the regret by a factor of more than d2. ) The algorithm, which we will call simulated greedy projection, works as follows. It is initialized with a sequence of "learning rates" 1, 2, .. . and "frame sizes" 1, 2, .. .. At the beginning of a phase, we assume the algorithm has determined a basepoint strategy u. (An arbitrary u may be used in the first phase. ) The algorithm chooses a set of (d + 1) affinely indepen- dent points {x0 = u, x1, x2, .. ., xd} with the property that for any y S, the difference y - x0 may be expressed as a linear combination of the vectors {xi - x0: 1 i d} using coefficients in [-2, 2]. (Such a set is called an approximate barycentric spanner, and may computed efficiently using an algorithm specified in [4]. ) We then choose a random bijection mapping the time steps in phase into the set {0, 1, .. ., d}, and in step t we sample the strategy yt = u + (x(t) -u). At the end of the phase we let B denote the unique affine function whose values at the points yt are equal to the costs observed during the phase at those points. The basepoint for the next phase is determined according to Zinkevich's update rule u = P (u - B(u)). 3 Theorem 5. 1. Assume that S is in isotropic position and that the cost functions satisfy Ct(x) 1 for all x S, 1tn, and that in addition the Hessian matrix of Ct(x) at each point x S has Frobenius norm bounded above by a constant. If k = k-3/4 and k = k-1/4, then the regret of the simulated greedy projection algorithm is O(d3n3/4). Proof sketch. In each phase, let Y = {y0, .. ., yd} be the set of points which were sampled, and define the following four functions: C, the average of the cost functions in phase; , the linearization of C at u, defined by the formula (x) = C(u) (x - u) + C(u); L, the unique affine function which agrees with C at each point of Y; and B, the affine function computed by the algorithm at the end of phase. The algorithm is simply run- ning greedy projection with respect to the simulated cost functions B, and it consequently satisfies a low-regret bound with respect to those functions. The expected value of B(u) is L(u) for every u. (Proof: both are affine functions, and they agree on every point of 2Flaxman, Kalai, and McMahan [12], with characteristic elegance, supply an algorithm which counterintuitively obtains an unbiased estimate of the approximate gradient using only a single sam- ple. Thus they avoid grouping the timeline into phases and improve the algorithm's convergence time by a factor of d. 3Readers familiar with Kiefer-Wolfowitz stochastic approximation [17] will note the similarity with our algorithm. The random bijection -- which is unnecessary in the Kiefer-Wolfowitz algo- rithm -- is used here to defend against the oblivious adversary. Y. ) Hence we obtain a low-regret bound with respect to L. To transfer this over to a low- regret bound for the original problem, we need to bound several additional terms: the regret experienced because the algorithm was using u + (x(t) - u) instead of u, the dif- ference between L(u) and (u), and the difference between (u) and C(u). In each case, the desired upper bound can be inferred from properties of barycentric spanners, or from the convexity of C and the bounds on its first and second derivatives.

PDF Details

FOCS Conference 2003 Conference Paper

The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions

  • Robert Kleinberg
  • Frank Thomson Leighton

We consider price-setting algorithms for a simple market in which a seller has an unlimited supply of identical copies of some good, and interacts sequentially with a pool of n buyers, each of whom wants at most one copy of the good. In each transaction, the seller offers a price between 0 and 1, and the buyer decides whether or not to buy, by comparing the offered price to his privately-held valuation for the good. The price offered to a given buyer may be influenced by the outcomes of prior transactions, but each individual buyer participates only once. In this setting, what is the value of knowing the demand curve? In other words, how much revenue can an uninformed seller expect to obtain, relative to a seller with prior information about the buyers' valuations? The answer depends on how the buyers' valuations are modeled. We analyze three cases - identical, random, and worst-case valuations - in each case deriving upper and lower bounds which match within a sublogarithmic factor.

Details
v2026.09.13