Author name cluster

Ehsan Emamjomeh-Zadeh

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.

6 papers

2 author rows

IJCAI Conference 2021 Conference Paper

Jointly Learning Prices and Product Features

Ehsan Emamjomeh-Zadeh
Renato Paes Leme
Jon Schneider
Balasubramanian Sivan

Product Design is an important problem in marketing research where a firm tries to learn what features of a product are more valuable to consumers. We study this problem from the viewpoint of online learning: a firm repeatedly interacts with a buyer by choosing a product configuration as well as a price and observing the buyer's purchasing decision. The goal of the firm is to maximize revenue throughout the course of $T$ rounds by learning the buyer's preferences. We study both the case of a set of discrete products and the case of a continuous set of allowable product features. In both cases we provide nearly tight upper and lower regret bounds.

PDF Details DOI

SODA Conference 2018 Conference Paper

Adaptive Hierarchical Clustering Using Ordinal Queries

Ehsan Emamjomeh-Zadeh
David Kempe 0001

In many applications of clustering (for example, ontologies or clusterings of animal or plant species), hierarchical clusterings are more descriptive than a flat clustering. A hierarchical clustering over n elements is represented by a rooted binary tree with n leaves, each corresponding to one element. The subtrees rooted at interior nodes capture the clusters. In this paper, we study active learning of a hierarchical clustering using only ordinal queries. An ordinal query consists of a set of three elements, and the response to a query reveals the two elements (among the three elements in the query) which are “closer” to each other than to the third one. We say that elements x and x ′ are closer to each other than x ″ if there exists a cluster containing x and x ′, but not x ″. When all the query responses are correct, there is a deterministic algorithm that learns the underlying hierarchical clustering using at most n log 2 n adaptive ordinal queries. We generalize this algorithm to be robust in a model in which each query response is correct independently with probability p > ½, and adversarially incorrect with probability 1 – p. We show that in the presence of noise, our algorithm outputs the correct hierarchical clustering with probability at least 1 – δ, using O ( n log n + n log(1/ δ )) adaptive ordinal queries. For our results, adaptivity is crucial: we prove that even in the absence of noise, every non-adaptive algorithm requires Ω( n 3 ) ordinal queries in the worst case.

Details

NeurIPS Conference 2017 Conference Paper

A General Framework for Robust Interactive Learning

Ehsan Emamjomeh-Zadeh
David Kempe

We propose a general framework for interactively learning models, such as (binary or non-binary) classifiers, orderings/rankings of items, or clusterings of data points. Our framework is based on a generalization of Angluin's equivalence query model and Littlestone's online learning model: in each iteration, the algorithm proposes a model, and the user either accepts it or reveals a specific mistake in the proposal. The feedback is correct only with probability p > 1/2 (and adversarially incorrect with probability 1 - p), i. e. , the algorithm must be able to learn in the presence of arbitrary noise. The algorithm's goal is to learn the ground truth model using few iterations. Our general framework is based on a graph representation of the models and user feedback. To be able to learn efficiently, it is sufficient that there be a graph G whose nodes are the models, and (weighted) edges capture the user feedback, with the property that if s, s* are the proposed and target models, respectively, then any (correct) user feedback s' must lie on a shortest s-s* path in G. Under this one assumption, there is a natural algorithm, reminiscent of the Multiplicative Weights Update algorithm, which will efficiently learn s* even in the presence of noise in the user's feedback. From this general result, we rederive with barely any extra effort classic results on learning of classifiers and a recent result on interactive clustering; in addition, we easily obtain new interactive learning algorithms for ordering/ranking.

PDF Details

TCS Journal 2017 Journal Article

On the rectangle escape problem

AmirMahdi Ahmadinejad
Sepehr Assadi
Ehsan Emamjomeh-Zadeh
Sadra Yazdanbod
Hamid Zarrabi-Zadeh

Motivated by the bus escape routing problem in printed circuit boards, we study the following rectangle escape problem: given a set S of n axis-aligned rectangles inside an axis-aligned rectangular region R, extend each rectangle in S toward one of the four borders of R so that the maximum density over the region R is minimized. The density of each point p ∈ R is defined as the number of extended rectangles containing p. We show that the problem is hard to approximate to within a factor better than 3/2 in general. When the optimal density is sufficiently large, we provide a randomized algorithm that achieves an approximation factor of 1 + ε with high probability improving over the current best 4-approximation algorithm available for the problem. When the optimal density is one, we develop an exact algorithm that finds an optimal solution efficiently. We also provide approximation algorithms and inapproximability results for a restricted version of the problem where rectangles are allowed to escape toward only a subset of directions.

Details DOI

STOC Conference 2016 Conference Paper

Deterministic and probabilistic binary search in graphs

Ehsan Emamjomeh-Zadeh
David Kempe 0001
Vikrant Singhal

We consider the following natural generalization of Binary Search: in a given undirected, positively weighted graph, one vertex is a target . The algorithm’s task is to identify the target by adaptively querying vertices. In response to querying a node q , the algorithm learns either that q is the target, or is given an edge out of q that lies on a shortest path from q to the target. We study this problem in a general noisy model in which each query independently receives a correct answer with probability p > 1/2 (a known constant), and an (adversarial) incorrect one with probability 1 − p . Our main positive result is that when p = 1 (i.e., all answers are correct), log 2 n queries are always sufficient. For general p , we give an (almost information-theoretically optimal) algorithm that uses, in expectation, no more than (1 − δ) log n /1 − H ( p ) + o (log n ) + O (log 2 (1/δ)) queries, and identifies the target correctly with probability at leas 1 − δ. Here, H ( p ) = −( p log p + (1 − p ) log(1 − p )) denotes the entropy. The first bound is achieved by the algorithm that iteratively queries a 1-median of the nodes not ruled out yet; the second bound by careful repeated invocations of a multiplicative weights algorithm. Even for p = 1, we show several hardness results for the problem of determining whether a target can be found using K queries. Our upper bound of log 2 n implies a quasipolynomial-time algorithm for undirected connected graphs; we show that this is best-possible under the Strong Exponential Time Hypothesis (SETH). Furthermore, for directed graphs, or for undirected graphs with non-uniform node querying costs, the problem is PSPACE-complete. For a semi-adaptive version, in which one may query r nodes each in k rounds, we show membership in Σ 2 k −1 in the polynomial hierarchy, and hardness for Σ 2 k −5 .

Details

FOCS Conference 2015 Conference Paper

Mixture Selection, Mechanism Design, and Signaling

Yu Cheng 0002
Ho Yee Cheung
Shaddin Dughmi
Ehsan Emamjomeh-Zadeh
Li Han
Shang-Hua Teng

We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function g from the n-dimensional hypercube to the bounded interval [-1, 1], and an n × rn matrix A with bounded entries, maximize g(Ax) over x in the m-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents in a Bayesian game through the provision of information (a. k. a. signaling). We present an approximation algorithm for this problem when g simultaneously satisfies two “smoothness” properties: Lipschitz continuity with respect to the L ∞ norm, and noise stability. The latter notion, which we define and cater to our setting, controls the degree to which low-probability - and possibly correlated - errors in the inputs of g can impact its output. The approximation guarantee of our algorithm degrades gracefully as a function of the Lipschitz continuity and noise stability of g. In particular, when g is both 0(1)-Lipschitz continuous and 0(1)-stable, we obtain an (additive) polynomial-time approximation scheme (PTAS) for mixture selection. We also show that neither assumption suffices by itself for an additive PTAS, and both assumptions together do not suffice for an additive fully polynomial-time approximation scheme (FPTAS). We apply our algorithm for mixture selection to a number of different game-theoretic applications, focusing on problems from mechanism design and optimal signaling. In particular, we make progress on a number of open problems suggested in prior work by easily reducing them to mixture selection: we resolve an important special case of the small-menu lottery design problem posed by Dughmi, Han, and Nisan [10]; we resolve the problem of revenue-maximizing signaling in Bayesian secondprice auctions posed by Emek et al. [12] and Miltersen and Sheffet [5]; we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi [9]; and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and Camara [3].

Details