Paper ID: 203 Title: Actively Learning Hemimetrics with Applications to Eliciting User Preferences Review #1 ===== Summary of the paper (Summarize the main claims/contributions of the paper.): This paper studies the problem of learning a "hemimetric" (non-symmetric metric) by asking queries of the form "is the distance from i to j of size at least c?" where i and j are indices of points in the space, and c is a variable threshold. Specifically, they are interested in obtaining epsilon approximation of the distances, uniformly over the set of points. By exploiting the triangle inequality, they are able to (in some cases) reduce the number of queries required for this from the naive n^2 (where n is the number of points) to a smaller value. In the most explicit form of their results, when the points are clustered such that all within-cluster distances are smaller than all between-cluster distances (a very strong assumption), they reduce the bound to order nK, where K is the number of clusters. This is also a lower bound. They also study a variant of this setting that admits a certain kind of noise to the problem. Clarity - Justification: Overall, the paper reads well, though it feels somewhat cramped at times (understandable, as they are up against the space constraint). For references like "Problem 11", it took me a while to figure out that this was referring to equation (11) (which displays an optimization problem). Maybe there is a better way to refer to these. Significance - Justification: The techniques and results are not surprising, given the types of queries they are working with. I would have liked to see more interesting special-case conditions analyzed. The cluster assumption they have chosen to study is a very strong one. Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): The very restrictive cluster assumption gives this a feeling like a toy problem. However, the algorithm itself is general, and seems fairly natural. They have also laid out a good foundation of basic results for working with these types of queries. So my evaluation leans slightly toward the positive side. I have a couple comments for the authors' consideration: There is a substantial literature on the optimal query complexity of learning from general types of queries, and one natural question is what that literature can tell us about this setting. For instance, supposing we approximate the set of possible hemimetrics by an epsilon-cover (in sup-norm), we can then pose an Exact learning problem whose query complexity upper bounds the query complexity of the original problem (and I'm guessing is roughly the same). Then the general analysis of learning by general queries by Balcazar, Castro, Guijarro, Kobler & Lindner (2007) (or perhaps even the simpler analysis by Balcazar, Castro & Guijarro, 2001) should have some implication for the optimal query complexity of this problem. It would be interesting to determine the values of the complexity measures studied there, for comparison to the query complexity achieved by the method proposed in the present article. In the example given in the introduction, what would be the motivation for the triangle inequality being satisfied? ===== Review #2 ===== Summary of the paper (Summarize the main claims/contributions of the paper.): The paper presents a model for constructing a matrix with the objective of minimizing its L_\infinity distance from some unknown hemimietric and using an adaptive sampling technique. The authors first introduce a greedy approach (IndGreedy), show its disadvantages, and then introduce their novel algorithm (LearnHM) which has serious improvements over IndGreedy. They then derive complexity bounds, tightness results, and present experimental evaluations. Clarity - Justification: The paper is clearly written, the details are easy to follow. Significance - Justification: The significance is not clear. Learning hemimetrics could be interesting, but the paper does not provide no convincing motivation for this. Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): The motivating example I did not find very fitting. It seems that the goal here would be to increase the number of reviews. Does it really make sense to learn the whole metric in order to obtain reviews? Maybe the ones that are closest - but than it is only some local learning. Which makes more sense, as the matrix you want to learn can be extremely huge when the number of items is large. (It is admitted in lines 618-619 that the running time scales with n^5.) Additionally, I don't see why you don't want to utilize features of the input data (this is made explicit in lines 795-797). A thorough discussion on the existing methods for learning asymmetric distances is also missing. The experimental setup seems quite artificial, especially the preference model in Section 7.2. The authors did not provide convincing motivations. Besides, the baselines don't seem to be very strong, and it is not clear why methods from the literature were not used. For example, why not use (Jamieson and Nowak, 2011a)? You are using triplets anyway in IndGreedy-SIT. And (Liu et al, 2015)? I did not find the claim in lines 795-797 convincing. (See also above.) Nevertheless, the problem could be of interest (especially if they make use of the input features), and the approach is also quite interesting. However, the algorithm is only applicable on very small problems, since the running time scales with n^5. Further questions: - line 566 is confusing. The lower bound you are referring to is presented in the proof. - How reliable is the method proposed in lines 634-636? Especially in view of line 1345. - Do you have results for the running time? ===== Review #3 ===== Summary of the paper (Summarize the main claims/contributions of the paper.): This paper proposes a new problem of learning Hemimetrics actively that has a quantitative interpretation and can be used to encourage users to try different choices. The authors propose a novel algorithm that, thanks to the triangle inequality, exploits the structure of Hemimetrics (e.g. clustered) so that one can construct a better version space and also make an efficient query. The sample complexity of the proposed algorithm is analyzed, and it is theoretically better than a naive strategy that does not exploit the structure (binary search on each pair). The empirical result shows that the Hemimetrics can be learnt more efficiently (w.r.t. sample complexity) than the baselines that learn the metric per pair independently (structure not exploited). Clarity - Justification: The paper is well-written. I have no complaints on the organization. Each section is well structured. Significance - Justification: The problem formulation itself is solid and of practical interest. It makes sense to consider Hemimetrics since one cannot simply negate the incentive. Updating bounds via projection and the proposed solution are nontrivial results, and the sample complexity of the proposed algorithm is solid. Although the experiment is simulated, I think overall the work has enough contribution for being accepted. Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): The experiment was done in simulation only where the underlying metric is truly Hemimetric. I wonder what happens in practice — actually try to make an offer and observe how much asymmetricity one observes and whether or not there is a way to negate the incentive so that one can infer W_ij from W_ji to some degree. It would be interesting to devise an algorithm that works for general Hemimetric while exploiting some partial symmetricity if there is any. ===== Review #4 ===== Summary of the paper (Summarize the main claims/contributions of the paper.): The paper presents an algorithm for learning “Hemimetrics”, that is distances which are not symmetric. The motivation is the context where the distances $D(i,j)$ correspond to the monetary incentive for a user to change her preference from $i$ to $j$, with $i,j=1,2,…n$. Arriving information corresponds to binary indicators $I[D(i,j) < c]$ for some system-provided $c$; the indicator corresponds to the user decision to accept/reject the reward $c$. The algorithm aims to learn all distances $D(i,j)$ within a tolerance level, given sufficient number of suggested rewards and user-decision information. Algorithm “Learn-HM” suggested in the paper is comprised of two main steps: i) an optimisation step to update lower and upper bounds on the range of values of $D$ given incoming information – in the general case this costs $O(n^3)$; ii) a “non-myopic” method for coming up with an effective selection of the node $(i,j)$ to be looked at each time, and the reward to be offered – the approach suggested in the paper does take under consideration the particular Hemimetric structure of $D$, thus is expected to be more effective than standard approaches that simply look at the node with the bigger range between the obtained lower and upper bounds at current step (the cost is $O(n^2)$). The method can adjust to online scenario, when $n$ is not known from the beginning, and in stochastic scenarios where the user-decision is a Bernoulli variable. The total cost of the standard version of the algorithm is $O(n^5)$: the authors briefly describe an approximate version which scales as $O(n^3)$. The paper shows application of the algorithm – versus some competing ones – on some real problems. Clarity - Justification: The paper is written in a simple and clear way. Some extensions of the method (e.g. in the stochastic case) are described in the Appendix. Significance - Justification: I think that the main novelty in the paper is the specification of the non-myopic policy for deciding upon the node and reward to be considered at the current step of the algorithm. I am afraid I am not an expert in field, so I can only say that the paper is well-written with all algorithmic descriptions being clear. I believe sufficient justification is provided for the steps in the development of the method. Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): See above replies. =====