Showing 1–12 of 12 results for author: Shameli, A

Learning Compiler Pass Orders using Coreset and Normalized Value Prediction

Authors: Youwei Liang, Kevin Stone, Ali Shameli, Chris Cummins, Mostafa Elhoushi, Jiadong Guo, Benoit Steiner, Xiaomeng Yang, Pengtao Xie, Hugh Leather, Yuandong Tian

Abstract: Finding the optimal pass sequence of compilation can lead to a significant reduction in program size and/or improvement in program efficiency. Prior works on compilation pass ordering have two major drawbacks. They either require an excessive budget (in terms of compilation steps) at compile time or fail to generalize to unseen programs. In this paper, for code-size reduction tasks, we propose a n… ▽ More Finding the optimal pass sequence of compilation can lead to a significant reduction in program size and/or improvement in program efficiency. Prior works on compilation pass ordering have two major drawbacks. They either require an excessive budget (in terms of compilation steps) at compile time or fail to generalize to unseen programs. In this paper, for code-size reduction tasks, we propose a novel pipeline to find program-dependent pass sequences within 45 compilation calls. It first identifies a coreset of 50 pass sequences via greedy optimization of a submodular function, and then learns a policy with Graph Neural Network (GNN) to pick the optimal sequence by predicting the normalized values of the pass sequences in the coreset. Despite its simplicity, our pipeline outperforms the default -Oz flag by an average of 4.7% over a large collection (4683) of unseen code repositories from diverse domains across 14 datasets. In comparison, previous approaches like reinforcement learning on the raw pass sequence space may take days to train due to sparse reward, and may not generalize well in held-out ones from different domains. Our results demonstrate that existing human-designed compiler flags can be improved with a simple yet effective technique that transforms the raw action space into a small one with denser rewards. △ Less

Submitted 27 January, 2023; v1 submitted 9 January, 2023; originally announced January 2023.

The Stationary Prophet Inequality Problem

Authors: Kristen Kessel, Amin Saberi, Ali Shameli, David Wajc

Abstract: We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arrive and perish according to Poisson point processes. Buyers arrive similarly and make take-it-or-leave-it offers for unsold items. The objective is to maximize the (infinite) time average revenue of the seller. Our main… ▽ More We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arrive and perish according to Poisson point processes. Buyers arrive similarly and make take-it-or-leave-it offers for unsold items. The objective is to maximize the (infinite) time average revenue of the seller. Our main results are pricing-based policies which (i) achieve a $1/2$-approximation of the optimal offline policy, which is best possible, and (ii) achieve a better than $(1-1/e)$-approximation of the optimal online policy. Result (i) improves upon bounds implied by recent work of Collina et al. (WINE'20), and is the first optimal prophet inequality for a stationary problem. Result (ii) improves upon a $1-1/e$ bound implied by recent work of Aouad and Saritaç (EC'20), and shows that this prevalent bound in online algorithms is not optimal for this problem. △ Less

Submitted 22 July, 2021; originally announced July 2021.

Sobolev Norm Learning Rates for Conditional Mean Embeddings

Authors: Prem Talwai, Ali Shameli, David Simchi-Levi

Abstract: We develop novel learning rates for conditional mean embeddings by applying the theory of interpolation for reproducing kernel Hilbert spaces (RKHS). We derive explicit, adaptive convergence rates for the sample estimator under the misspecifed setting, where the target operator is not Hilbert-Schmidt or bounded with respect to the input/output RKHSs. We demonstrate that in certain parameter regime… ▽ More We develop novel learning rates for conditional mean embeddings by applying the theory of interpolation for reproducing kernel Hilbert spaces (RKHS). We derive explicit, adaptive convergence rates for the sample estimator under the misspecifed setting, where the target operator is not Hilbert-Schmidt or bounded with respect to the input/output RKHSs. We demonstrate that in certain parameter regimes, we can achieve uniform convergence rates in the output RKHS. We hope our analyses will allow the much broader application of conditional mean embeddings to more complex ML/RL settings involving infinite dimensional RKHSs and continuous state spaces. △ Less

Submitted 24 February, 2022; v1 submitted 16 May, 2021; originally announced May 2021.

Comments: Appears in AISTATS 2022

Sample Efficient Graph-Based Optimization with Noisy Observations

Authors: Tan Nguyen, Ali Shameli, Yasin Abbasi-Yadkori, Anup Rao, Branislav Kveton

Abstract: We study sample complexity of optimizing "hill-climbing friendly" functions defined on a graph under noisy observations. We define a notion of convexity, and we show that a variant of best-arm identification can find a near-optimal solution after a small number of queries that is independent of the size of the graph. For functions that have local minima and are nearly convex, we show a sample comp… ▽ More We study sample complexity of optimizing "hill-climbing friendly" functions defined on a graph under noisy observations. We define a notion of convexity, and we show that a variant of best-arm identification can find a near-optimal solution after a small number of queries that is independent of the size of the graph. For functions that have local minima and are nearly convex, we show a sample complexity for the classical simulated annealing under noisy observations. We show effectiveness of the greedy algorithm with restarts and the simulated annealing on problems of graph-based nearest neighbor classification as well as a web document re-ranking application. △ Less

Submitted 4 June, 2020; originally announced June 2020.

Comments: The first version of this paper appeared in AISTATS 2019. Thank to community feedback, some typos and a minor issue have been identified. Specifically, on page 4, column 2, line 18, the statement $Δ_{1,s} \ge (1+m)^{S-1-s} Δ_1$ is not valid, and in the proof of Theorem 2, "By Lemma 1" should be "By Definition 2". These problems are fixed in this updated version published here on arxiv

Journal ref: AISTATS 2019

Commitment on Volunteer Crowdsourcing Platforms: Implications for Growth and Engagement

Authors: Irene Lo, Vahideh Manshadi, Scott Rodilitz, Ali Shameli

Abstract: Volunteer crowdsourcing platforms match volunteers with tasks which are often recurring. To ensure completion of such tasks, platforms frequently use a lever known as "adoption," which amounts to a commitment by the volunteer to repeatedly perform the task. Despite reducing match uncertainty, high levels of adoption can decrease the probability of forming new matches, which in turn can suppress gr… ▽ More Volunteer crowdsourcing platforms match volunteers with tasks which are often recurring. To ensure completion of such tasks, platforms frequently use a lever known as "adoption," which amounts to a commitment by the volunteer to repeatedly perform the task. Despite reducing match uncertainty, high levels of adoption can decrease the probability of forming new matches, which in turn can suppress growth. We study how platforms should manage this trade-off. Our research is motivated by a collaboration with Food Rescue U.S. (FRUS), a volunteer-based food recovery organization active in over 30 locations. For platforms such as FRUS, success crucially depends on volunteer engagement. Consequently, effectively utilizing non-monetary levers, such as adoption, is critical. Motivated by the volunteer management literature and our analysis of FRUS data, we develop a model for two-sided markets which repeatedly match volunteers with tasks. Our model incorporates match uncertainty as well as the negative impact of failing to match on future engagement. We study the platform's optimal policy for setting the adoption level to maximize the total discounted number of matches. We fully characterize the optimal myopic policy and show that it takes a simple form: depending on volunteer characteristics and market thickness, either allow for full adoption or disallow adoption. In the long run, we show that such a policy is either optimal or achieves a constant-factor approximation. Our finding is robust to incorporating heterogeneity in volunteer behavior. Our work sheds light on how two-sided platforms need to carefully control the double-edged impacts that commitment levers have on growth and engagement. A one-size-fits-all solution may not be effective, as the optimal design crucially depends on the characteristics of the volunteer population. △ Less

Submitted 15 July, 2021; v1 submitted 21 May, 2020; originally announced May 2020.

Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

Authors: Arash Asadpour, Rad Niazadeh, Amin Saberi, Ali Shameli

Abstract: We study a submodular maximization problem motivated by applications in online retail. A platform displays a list of products to a user in response to a search query. The user inspects the first $k$ items in the list for a $k$ chosen at random from a given distribution, and decides whether to purchase an item from that set based on a choice model. The goal of the platform is to maximize the engage… ▽ More We study a submodular maximization problem motivated by applications in online retail. A platform displays a list of products to a user in response to a search query. The user inspects the first $k$ items in the list for a $k$ chosen at random from a given distribution, and decides whether to purchase an item from that set based on a choice model. The goal of the platform is to maximize the engagement of the shopper defined as the probability of purchase. This problem gives rise to a less-studied variation of submodular maximization in which we are asked to choose an $\textit{ordering}$ of a set of elements to maximize a linear combination of different submodular functions. First, using a reduction to maximizing submodular functions over matroids, we give an optimal $\left(1-1/e\right)$-approximation for this problem. We then consider a variant in which the platform cares not only about user engagement, but also about diversification across various groups of users, that is, guaranteeing a certain probability of purchase in each group. We characterize the polytope of feasible solutions and give a bi-criteria $((1-1/e)^2,(1-1/e)^2)$-approximation for this problem by rounding an approximate solution of a linear programming relaxation. For rounding, we rely on our reduction and the particular rounding techniques for matroid polytopes. For the special case in which underlying submodular functions are coverage functions -- which is practically relevant in online retail -- we propose an alternative LP relaxation and a simpler randomized rounding for the problem. This approach yields to an optimal bi-criteria $(1-1/e,1-1/e)$-approximation algorithm for the special case of the problem with coverage functions. △ Less

Submitted 20 October, 2022; v1 submitted 21 February, 2020; originally announced February 2020.

Comments: Conference version: ACM EC 2022; journal version: Operation Research

Assignment Mechanisms under Distributional Constraints

Authors: Itai Ashlagi, Amin Saberi, Ali Shameli

Abstract: We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning as many agents as possible. Our first contribution is a generalization of the well-known and widely used serial dictatorship. Our mechanism maintains s… ▽ More We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning as many agents as possible. Our first contribution is a generalization of the well-known and widely used serial dictatorship. Our mechanism maintains several desirable properties of serial dictatorship, including strategyproofness, Pareto efficiency, and computational tractability while satisfying the distributional constraints with a small error. We also propose a generalization of the probabilistic serial algorithm, which finds an ordinally efficient and envy-free assignment, and also satisfies the distributional constraints with a small error. We show, however, that no ordinally efficient and envy-free mechanism is also weakly strategyproof. Both of our algorithms assign at least the same number of students as the optimum fractional assignment. △ Less

Submitted 1 May, 2019; v1 submitted 9 October, 2018; originally announced October 2018.

Comments: 26 pages, conference version published in SODA 2019

Cost Sharing in Two-Sided Markets

Authors: Sreenivas Gollapudi, Kostas Kollias, Ali Shameli

Abstract: Motivated by the emergence of popular service-based two-sided markets where sellers can serve multiple buyers at the same time, we formulate and study the {\em two-sided cost sharing} problem. In two-sided cost sharing, sellers incur different costs for serving different subsets of buyers and buyers have different values for being served by different sellers. Both buyers and sellers are self-inter… ▽ More Motivated by the emergence of popular service-based two-sided markets where sellers can serve multiple buyers at the same time, we formulate and study the {\em two-sided cost sharing} problem. In two-sided cost sharing, sellers incur different costs for serving different subsets of buyers and buyers have different values for being served by different sellers. Both buyers and sellers are self-interested agents whose values and costs are private information. We study the problem from the perspective of an intermediary platform that matches buyers to sellers and assigns prices and wages in an effort to maximize welfare (i.e., buyer values minus seller costs) subject to budget-balance in an incentive compatible manner. In our markets of interest, agents trade the (often same) services multiple times. Moreover, the value and cost for the same service differs based on the context (e.g., location, urgency, weather conditions, etc). In this framework, we design mechanisms that are efficient, ex-ante budget-balanced, ex-ante individually rational, dominant strategy incentive compatible, and ex-ante in the core (a natural generalization of the core that we define here). △ Less

Submitted 13 July, 2021; v1 submitted 7 September, 2018; originally announced September 2018.

Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection

Authors: Nima Anari, Rad Niazadeh, Amin Saberi, Ali Shameli

Abstract: The Bayesian online selection problem aims to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social welfare (or revenue) subject to different structural constraints. Inspired by applications with a hierarchy of service, this paper focuses on the cases where a laminar matroid characterizes the set of served buyers. We give the first Polynomial-Time Approximati… ▽ More The Bayesian online selection problem aims to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social welfare (or revenue) subject to different structural constraints. Inspired by applications with a hierarchy of service, this paper focuses on the cases where a laminar matroid characterizes the set of served buyers. We give the first Polynomial-Time Approximation Scheme (PTAS) for the problem when the laminar matroid has constant depth. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that approximate the optimum online solution with any degree of accuracy, plus a concentration argument showing that rounding incurs a small loss. We also study another variation, which we call the production-constrained problem. The allowable set of served buyers is characterized by a collection of production and shipping constraints that form a particular example of a laminar matroid. Using a similar LP-based approach, we design a PTAS for this problem, although in this special case the depth of the underlying laminar matroid is not necessarily a constant. The analysis exploits the negative dependency of the optimum selection rule in the lower levels of the laminar family. Finally, to demonstrate the generality of our technique, we employ the linear programming-based approach employed in the paper to re-derive some of the classic prophet inequalities known in the literature -- as a side result. △ Less

Submitted 8 March, 2024; v1 submitted 14 July, 2018; originally announced July 2018.

Comments: conference version of this paper appeared as one-page abstract in ACM EC 2019

A Continuation Method for Discrete Optimization and its Application to Nearest Neighbor Classification

Authors: Ali Shameli, Yasin Abbasi-Yadkori

Abstract: The continuation method is a popular approach in non-convex optimization and computer vision. The main idea is to start from a simple function that can be minimized efficiently, and gradually transform it to the more complicated original objective function. The solution of the simpler problem is used as the starting point to solve the original problem. We show a continuation method for discrete op… ▽ More The continuation method is a popular approach in non-convex optimization and computer vision. The main idea is to start from a simple function that can be minimized efficiently, and gradually transform it to the more complicated original objective function. The solution of the simpler problem is used as the starting point to solve the original problem. We show a continuation method for discrete optimization problems. Ideally, we would like the evolved function to be hill-climbing friendly and to have the same global minima as the original function. We show that the proposed continuation method is the best affine approximation of a transformation that is guaranteed to transform the function to a hill-climbing friendly function and to have the same global minima. We show the effectiveness of the proposed technique in the problem of nearest neighbor classification. Although nearest neighbor methods are often competitive in terms of sample efficiency, the computational complexity in the test phase has been a major obstacle in their applicability in big data problems. Using the proposed continuation method, we show an improved graph-based nearest neighbor algorithm. The method is readily understood and easy to implement. We show how the computational complexity of the method in the test phase scales gracefully with the size of the training set, a property that is particularly important in big data applications. △ Less

Submitted 9 February, 2018; originally announced February 2018.

How Gamification Affects Physical Activity: Large-scale Analysis of Walking Challenges in a Mobile Application

Authors: Ali Shameli, Tim Althoff, Amin Saberi, Jure Leskovec

Abstract: Gamification represents an effective way to incentivize user behavior across a number of computing applications. However, despite the fact that physical activity is essential for a healthy lifestyle, surprisingly little is known about how gamification and in particular competitions shape human physical activity. Here we study how competitions affect physical activity. We focus on walking challenge… ▽ More Gamification represents an effective way to incentivize user behavior across a number of computing applications. However, despite the fact that physical activity is essential for a healthy lifestyle, surprisingly little is known about how gamification and in particular competitions shape human physical activity. Here we study how competitions affect physical activity. We focus on walking challenges in a mobile activity tracking application where multiple users compete over who takes the most steps over a predefined number of days. We synthesize our findings in a series of game and app design implications. In particular, we analyze nearly 2,500 physical activity competitions over a period of one year capturing more than 800,000 person days of activity tracking. We observe that during walking competitions, the average user increases physical activity by 23%. Furthermore, there are large increases in activity for both men and women across all ages, and weight status, and even for users that were previously fairly inactive. We also find that the composition of participants greatly affects the dynamics of the game. In particular, if highly unequal participants get matched to each other, then competition suffers and the overall effect on the physical activity drops significantly. Furthermore, competitions with an equal mix of both men and women are more effective in increasing the level of activities. We leverage these insights to develop a statistical model to predict whether or not a competition will be particularly engaging with significant accuracy. Our models can serve as a guideline to help design more engaging competitions that lead to most beneficial behavioral changes. △ Less

Submitted 23 February, 2017; originally announced February 2017.

Comments: WWW 2017

A New Upper Bound on Total Domination Number of Bipartite Graphs

Authors: Saieed Akbari, Pooyan Ehsani, Sahar Qajar, Ali Shameli, Hadi Yami

Abstract: Let $ G $ be a graph. A subset $S \subseteq V(G) $ is called a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $S$. The total domination number, $γ_{t}$($G$), is the minimum cardinality of a total dominating set of $G$. In this paper using a greedy algorithm we provide an upper bound for $γ_{t}$($G$), whenever $G$ is a bipartite graph and $δ(G)$ $\geq$ $k$. More p… ▽ More Let $ G $ be a graph. A subset $S \subseteq V(G) $ is called a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $S$. The total domination number, $γ_{t}$($G$), is the minimum cardinality of a total dominating set of $G$. In this paper using a greedy algorithm we provide an upper bound for $γ_{t}$($G$), whenever $G$ is a bipartite graph and $δ(G)$ $\geq$ $k$. More precisely, we show that if $k$ > 1 is a natural number, then for every bipartite graph $G$ of order $n$ and $δ(G) \ge k$, $ $$γ_{t}$($G$) $\leq$ $n(1- \frac{k!}{\prod_{i=0}^{k-1}(\frac{k}{k-1}+i)}).$ △ Less

Submitted 28 December, 2014; originally announced December 2014.

Comments: 10 pages, journal