Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learning
Authors: Austin Xu
Andrew McRae
Jingyan Wang
Mark A. Davenport
Ashwin Pananjady
Venue: NeurIPS 2023 poster (2023)
Keywords: human querying
high dimensional low rank matrix estimation
metric learning
TL;DR: We propose a new human query, apply it to the problem of low-rank metric learning, and prove sample complexity upper bounds in a high-dimensional setting.

Abstract: We introduce a new type of query mechanism for collecting human feedback, called the perceptual adjustment query (PAQ). Being both informative and cognitively lightweight, the PAQ adopts an inverted measurement scheme, and combines advantages from both cardinal and ordinal queries. We showcase the PAQ in the metric learning problem, where we collect PAQ measurements to learn an unknown Mahalanobis distance. This gives rise to a high-dimensional, low-rank matrix estimation problem to which standard matrix estimators cannot be applied. Consequently, we develop a two-stage estimator for metric learning from PAQs, and provide sample complexity guarantees for this estimator. We present numerical simulations demonstrating the performance of the estimator and its notable properties.

Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learning
Austin Xu* Georgia Institute of Technology
Andrew D. McRae EPFL
Jingyan Wang
Georgia Institute of Technology
Mark A. Davenport Georgia Institute of Technology
Ashwin Pananjady
Georgia Institute Technology
Abstract
We introduce new type of query mechanism for collecting human feedback, called the perceptual adjustment query (PAQ). Being both informative and cognitively lightweight, the PAQ adopts inverted measurement scheme, and combines advan- tages from both cardinal and ordinal queries. We showcase the PAQ in the metric learning problem, where collect PAQ measurements to learn unknown Maha- lanobis distance. This gives rise to a high-dimensional. low-rank matrix estimation problem which standard matrix estimators cannot be applied. Consequently, we develop a two-stage estimator for metric learning from PAQs, and provide sample complexity guarantees for this estimator. We present numerical simulations demonstrating the performance of the estimator and its notable properties.
Introduction
Should we query cardinal or ordinal data from people? This question arises in a broad range of appli- cations, such as in conducting surveys [H31,, grading assignments [4] evaluating employees [6], and comparing rating products 7 g name few. Cardinal data numerical scores. For example, teachers score writing assignments in the range of 0-100, and survey respondents express their agreement with statement on scale of 7. Ordinal data are relations between items, such as pairwise comparisons (choosing the better item in a pair) and rankings (ordering all or subset of items). There no free lunch, and both cardinal and ordinal queries have pros and cons.
On the one hand, collecting ordinal data typically more efficient in terms of worker time and cognitive load [9], and surprisingly often matches exceeds the accuracy of cardinal data 99.. The information contained in ordinal queries, however, is fundamentally limited and lacks expressiveness. For example, pairwise comparisons elicit binary responses where two items compared against each other, but the absolute placement of these items with respect to the entire pool is lost. On the other hand, cardinal data more expressive [T0. For example, assigning two items scores of and 2 conveys a very different message from assigning them scores of 9 and 10, or 1 and 10, although all yield the same pairwise comparison outcome. However, the expressiveness of cardinal data often comes at the cost of miscalibration: Prior work has shown that different people have different scales
[T], and even a single person's 's scale can drift over time (e.g., and intra-person discrepancies make it challenging to interpret and aggregate raw scores effectively.
) These inter-person
The goal of this paper is study whether queries to achieve the best of both worlds. Specifically, we pose the research question:
combine the advantages of cardinal and ordinal
"Contact: axudgatech. edu. The full version of this work can be found arXiv
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

A $2 bus ride that takes 40 minutes
Adjust slider until you no longer prefer minute taxi ride
$O
$19
Reference item
Adjust slider until the fruit is dissimilar to the reference
Reference item
Figure 1: The user interface for perceptual adjustment query (PAQ) for preference learning (top) and similarity learning (bottom).
Can develop new paradigm for human data elicitation that is expressive, accurate, and cognitively lightweight?
Towards this goal, we extract key features of both cardinal and ordinal queries, and propose new type of query scheme that we term the perceptual adjustment query (PAQ). As a thought experiment, consider the task of learning an individual's preferences between modes of transport. The query can take the following forms:
Ordinal: Do you prefer $2 bus ride that takes 40 minutes $25 taxi that takes 10 minutes?
Cardinal: On scale of 0 to 1, how much do you value $2 bus ride that takes 40 minutes?
Proposed approach: To reach the same level of preference for a $2 bus trip that takes 40 minutes, a taxi that takes 10 minutes would cost Sx.
A user interface for the proposed approach is shown in Figure (top). We present the user reference item (a $2 bus ride that takes 40 minutes) and a sliding bar representing the number of dollars (x) for the 10-minute taxi cost. As the user adjusts the slider, the value of starts with 0 and gradually increases on a continuous scale. The user is instructed to place the slider at a point where they equally prefer $2 bus ride and taxi ride of dollars ( The PAQ thus combines ordinal and cardinal elicitation in an intuitive fashion: We obtain ordinal information by asking the user to make cognitive judgments in relative sense by comparing items, and cardinal information
be extracted from the location of the slider. The ordinal reasoning endows the query with accuracy and efficiency, while the cardinal output enables more expressive response. Moreover, this cardinal output mitigates miscalibration, because instead of asking the user to rate on subjective and ambiguous notion (i.e., preference), provide the user reference object (i.e., the $2 bus ride) to anchor their rating scale.
Beyond combining the strengths of cardinal and ordinal queries, PAQs have additional advantages that are well illustrated with the example in Figure I (bottom). First, PAQs provide users with the context of a specific (continuous) dimension along which items vary. For example, consider a pairwise comparison between the reference item and the "yellow apple selected in Figure [1] They have similar shapes, but different colors. If these two items are shown to the user in isolation, the user lacks context judge whether they should be considered similar dissimilar. In contrast, the full spectrum provided in PAQS tells the user that the similarity judgment is apples vs. pears. The access such context improves self-consistency in responses [14] Second, PAQS provide "hard examples" by design and thus enable effective learning. Consider Figure T (bottom): Items on the left of the spectrum are apples (clearly similar the reference), and items on the right are pears (clearly dissimilar to the reference), and only a small subset of items in the middle appear ambiguous. PAQS collect information precisely about "confusing" items in this ambiguous region. On the other hand, ordinal queries are constructed by selecting uniformly at random from the items shown, an item in the ambiguous region will rarely be presented the user.
"The ordinal component is crucial in our proposed perceptual adjustment query we provide a reference item and instruct people to make relational judgment of the target item compared to the reference item. Hence, the perceptual adjustment query is distinct from sliding survey questions that elicit purely cardinal responses.

---

The advantages of PAQs makes their deployment appealing in variety of problem settings. For example, practitioners may deploy PAQs to learn human preferences, like in the taxi and bus example in Figure [ or more complex settings such as housing preferences, where multiple features (price, square footage, proximity to employment etc.) vary as the slider moved. PAQs can also be used to learn models for human perception, such as characterizing the extent of color blindness for given user. One can present a user with red-green color blindness a sequence of colors that slowly transitions between red and green, and ask them to drag the slider until they perceive difference in colors. An extended discussion of applications is provided in the full version of this paper on arxiv In this paper, we focus on learning metrics to characterize human perception. In this problem, items are represented by points in a (possibly (igh-dimensiona) space, and the goal is to learn a distance metric such that smaller distance between a pair of items means that they are semantically and perceptually closer, and vice versa. Figure [ for metric learning, where the user is instructed to place the slider the precise point where the object appears to transition from being similar to dissimilar. To construct a sequence of images as shown in Figure (bottom), one can traverse path in the latent space of generative model given a latent feature vector, the generative model synthesizes a corresponding image.
(bottom) presents a PAQ for collecting similarity data
1.1 Do PAQs improve upon ordinal queries? A simulation vignette
Consider the problem of Mahalanobis metric learning, which forms the focus of this paper. In this setting, items are represented as points in the vector space R which is in turn endowed with a Mahalanobis metric parametrized by a symmetric positive semidefiiite matrix Σ' E RRdxd The (dis-)simillrity of two items is determined by their distance under the metric: The larger the (squared) distance || x I|2_- = (a x²) E''(x x²) between two items x and x'' is, the more dissimilar the items are. We are particularly interested in the setting in which Σ* is low-rank. Established approaches in metric learning use ordinal queries, such as pairwise comparisons ("Are items æ and æ' similar?"" 18) triplet comparisons [19] ("Which of the two items and æ2 is closer to reference item xy "")"", and ranking- k queries ("Given a reference item Bg. rank the set of items 21,...., 3y in terms of similarity to xo [14.
We compare the performance of such queries against PAQs in a toy metric learning setup. In particular, we choose a random low-rank matrix Σ* in dimension 50 with rank 10 (see Appendix B for our precise construction) and use the models and ttate-of-the-art algorithms of [99
to produce
pairwise, triplet, and ranking-k queries and estimate the low-rank metric. In addition to these ordinal queries, we simulate PAQ responses under the model presented in Section ( and use our algorithm (see Section 3) for estimation. To simplify the example, all query responses are generated in noiseless fashion-for example, the triplet comparison always returns the closer item to the reference. We present our results in Figure 2 which illustrates a significant gap in information richness between PAQs and a variety of ordinal queries. The number of PAQ responses needed to attain a reasonable normalized error is dramatically lower than those of typical ordinal queries, illustrating that PAQs can greatly improve upon the performance of existing ordinal queries for metric learning. The rest of paper explores this opportunity: It aims to make the deployment of PAQs theoretically grounded by designing provable methodology for learning a low-rank metric from PAQ responses.
1.2 Our contributions and organization
In addition to introducing the perceptual adjustment query (PAQ), we demonstrate its applicability to metric learning under a Mahalanobis metric. We first present a mathematical formulation of this estimation problem in Section 2 We then show that the sliding bar response can be viewed as an inverted measurement of the metric matrix that we want to estimate, which allows us to restate our problem as that of estimating a low-rank matrix from a specific type of trace measurement (Section 3) However, our PAQ formulation differs from classical matrix estimation due to two technical challenges: (a) the sensing matrices and noise are correlated, and (b) the sensing matrices are heavy-tailed. As result, standard matrix estimation algorithms give rise to biased estimators. We propose a query procedure and an estimator that overcome these two challenges, and we prove statistical error bounds on the estimation error (Section D The unconventional nature of the sensing
model and estimator causes unexpected behaviors in our error bounds; in Section 5, simulations verifying that these behaviors also appear in practice.
we present
3

---

Error vs. number of noiseless responses
PAQ reeeeaaiee
1.0
0.4
Reference
item
6.2
0.00
1500
2000
Number
Performance of noiseless PAQs and various ordinal queries for low-rank metric learning, We plot the mean and standard error of the mean (shaded regions, not visible) of the nor- malized estimation error over 10 trials.
Figure 2:
Figure 3: The perceptual adjustment query. Given a ref- erence item æ and a query vector a, a continuous path of items is formed {æ + ya E [0, oo). Then, user is asked to pick the first item along this path that dissimilar to the reference item, denoted by ya.
1.3 Related work
We discuss related work on metric learning and the statistical techniques that we use.
Metric learning. As discussed in Section 1.1 prior work in metric learning (20] considers wide variety of ordinal queries. PAQ can viewed as extending a discrete set of items presented to users to continuous spectrum, which is natural when one uses generative model such as a GAN [2]] rank the items, whereas in PAQ the ranking is provided by the feature space and ask people to identify transition point (similar vs. dissimilar) in this ranking.
However, the goal tuple queries
Statistical techniques. In our theoretical results, we apply techniques from the high-dimensional statistics literature. Our theoretical formulation (presented in Section 3 resembles the problem of
low-rank matrix estimation from trace measurements (e-g.. 23 28
see 29 for more complete
overview), and, in particular, when the sensing matrix is of rank one 30 in Section our model presents two important distinctions from prior literature. our case, the sensing matrices are both heavy-tailed and correlated with the measurement noise. The heavy-tailed matrices violate the assumptions of much prior work that relies on sub-Gaussian or sub-exponential assumptions the sensing matrices. Prior work has attempted to address the challenge of heavy tails with methods such as robust loss functions [34 35 or the "median-of-meet ofemn- approach (36/38). We
33 However, as discussed
draw particular inspiration from Fan et al. [39], which considers truncation to control heavy-tailed behavior for a variety of problems. However, in the low-rank matrix estimation setting, Fan et al. [39] only analyze the case of heavy-tailed noise under sub-Gaussian design, meaning their methodology and results are not applicable to our problem setting.
2 Model
In this section, we present our model for the perceptual adjustment query (PAQ) in the context of its application to metric learning.
2.1 Mahalanobis metric learning
We consider a d-dimensional feature space where each item represented by point in Rd. The distance metric model for human similarity perception posits that there is metric on Rd that measures how dissimilar items are perceived to be. recent line of work [40] 41 has modeled the distance metric
Mahalanobis metric. If Σ* dd is symmetric positive semidefinite (PSD) matrix, the squared Mahalanobis distance with respect to Σ* between items æ and x' e Rd is | - I - items x and x': If we further have a perceptual boundary value y > O, this model posits that items x, x are perceived as similar if ||æ x' x'1 y and dissimilar if || x' x'1 2 y. We adopt high--imennn nigh-dimensional framework and, following
1.. := (æ= x')² (x x'). The distance represents the extent of dissimilarity between
assume that the matrix Σ is low-rank.
Note that if the goal is to predict whether two items are similar dissimilar via computing the relation ||æc x'' 2l| ž y, then this problem is scale-invariant, in the sense that two items are predicted as similar (or dissimilar) according to (Σ', v), if and only if they are predicted as similar (or dissimilar)

---

according to (Cscale E", Cscalel/) for any scaling factor Cscale > 0. We are thus interested in finding the equivalence class of solutions {(Csalt Cscale?): : Cscale > 0}. Therefore, in practice, one can set y to be any positive scalar and then estimate the corresponding Σ* Indeed, our theoretical error bounds on Σ -- ||
exhibit natural scale-equivarian property (see Section 4 Scale Equivariance).
2.2 The perceptual adjustment query (PAQ)
We assume that every point in our feature space F corresponds some item. Recall from Figure that a PAQ collects similarity data between a pair of items, where reference item is fixed, and spectrum of target items is generated from a one-dimensional path in the feature space. Denote the reference item by æ E IRd. The target items can be generated by any path in Rd but, for simplicity, we consider straight lines. For any vector a E RR we construct the line {a + 7a y E [0, oo) We call this vector a the query vector. As shown in Figure Bl the user moves the slider from left to right, and the value of 7 increases proportionally to the distance traversed by the slider. Note that the value y is dimensionless.
!
The user instructed to stop the slider the transition point where the target item transitions from being similar to dissimilar with the reference item. According to our model, this transition point occurs when the -a-Mahhllnoobis distance between the target item and the reference item is y. The (noiseless) transition point, denoted by 7+. satisfies the equation
y | (ac + ?. 2.a E'a.
(1)
Note that the ideal PAQ response 7 does not depend on the specific reference item æ but rather only on the query direction and the (unknown) metric matrix Σ". When querying users with PAQs, the practitioner has control over how the query vectors a are selected, which we discuss in Section 3.2
2.3
Noise model
We model the noise in human responses as follows: In the PAQ response (T). we replace the boundary value y by y 77, where IR represents noise. Thus the user provides noisy response y whose value satisfies 7 a E' a = y + 17. Substituting in ( we have 72 = ?
Σ.a- This model captures qualitatively how we would expect the variance of due to noise to scale. To see why, recall that y is proportional to the distance traversed by the slider the user interface Figure (bbutoom) If a E'a a is large, then the semantic meaning of the item changes rapidly as the user moves the slider, and the slider will stop at a position that is close to the true transition point. On the other hand, if a Σ'a a is small, then the item changes slowly the user moves the slider. It is then hard to determine where exactly the transition occurs, so the slider may stop in a larger interval around the transition point.
3 Methodology
In this section, we formally present the statistical estimation problem for metric learning from noisy PAQ data, and we develop our algorithm for estimating the true metric matrix Σ*
3.1 Statistical estimation
Assume we collect N PAQ responses, using N query vectors {a: N. that we selee Denote the noise associated with these queries by random variables 71, ......, TNN E R. We obtain PAQ responses, denoted by .,...., YN. that satisfy
y + 1ii, i= 1,..., N.
We assume the noise variable v is independen For the query a, has zero mean and variance u², and bounded, with - S < n7 for some constant 17' 2 O. Note that we must have 17 + y 2 0 since 7² 2 0; in addition, we place upper bound 17 on the noise.
In what follows, use the terms "responses""mmmesuuummne vector"""sennsing vector" interchangeably for a.
interchangeably for y, and the terms "query
"This could be relaxed by placing conditions on the conditional distributions of r given (and even the reference point œ)) but we omit this for simplicity.
5

---

Given the query directions {a and the PAQ responses {y we want to estimate the matrix Σ. We first rewrite our measurement model as follows: Recall that the matrix inner product is denoted by (A, B) == tr (A B) for any two matrices A and B of compatible dimension. Then from we write
7
y
(3)
E'a
Plugging 3 once more into ( we have
y リ+ (A Σ")
where
+ 17 A An aaa a. T' aa
Hence, problem resembles trace regression, and, in particular, low-rank matrix estimation from rank-one measurements (because the matrix inv has rank 1) [11 30 32 33]. We call A inv the sensing matrix, and the sensing vector. Classical trace regression assumes that make (noisy) observations the form y = [A, "") + where A is fixed before we make the measurement; in our problem, the sensing matrix inn depends a. Hence, the process of obtaining a PAQ response can be viewed as an inversion of the standard trace measurement process. The inverse nature of our problem makes estimator design more challenging, as we discuss in the following section.
observed response y and associated sensing vector
3.2 Algorithm
As our first attempt at a procedure to estimate Σ*, we follow the literature 24 33 and consider randomly sampling i.i.d. vectors a, ~ (0, We then standard least-squares estimation of E" Since we expect E to be low-rank, we add nuclear-norm regularization to promote low rank. In particular, solve the following program:
N Σ 1=1
min E
(y 1
(A
)) + AN E
(5)
N
where AN >> O is regularization parameter. This is convex semidefinite program and can be solved with standard off-the-shelf solvers. However, the inverted form of our measurement model creates two critical issues when naīvely using (5):
Bias of standard matrix estimators due to dependence. Note that the sensing matrix 4 depends on the noise 1). Quantitatively, we have | iNv] * (see Appendix D. Standard trace regression analyses require that this quantity be zero, typically assuming (at least) that is zero- mean conditioned on the sensing matrix A. The failure of this to hold in our case introduces bias that does not decrease with the sample size N.
Heavy-tailed sensing matrix. The factor E'a in A (see Equation (4 makes A heavy- tailed in general. When a is Gaussian, the term E' is an inverse weighted chi-square random variable, whose higher-order moments infinite (and the number of finite moments depends the rank of )* This makes eтror analysis more difficult, as standard analyses require the sensing matrix A concentrate well (c.g.. be sub-exponential).
To overcome these challenges, make two key modifications to the procedure
Step 1: Bias reduction via averaging, First, we want to mitigate the bias due to the dependence between the sensing matrix Ainv and the noise 77. The bias term E [vv] scales proportionally to
E In(y + 7 E |n? Therefore, to reduce this bias in the least-squares estimator (5). we need to reduce the noise variance. We reduce the effective noise variance (and hence the bias) by averaging i..d. samples. Operationally, instead of obtaining N measurements from N distinct sensing vectors (a we draw sensing vectors {a, } and collect m measurements, denoted by (,,") m 1 corresponding to each sensing vector a; We refer to n the number of (distinct) sensing vectors.

---

Algorithm Inverted measurement sensing, averaging, and truncation.
Input: number of total measurements N, averaging parameter (that divides N), truncation threshold r, measurement value y
1: Compute the number of sensing vectors T2
N
2: for = 1 to n do
3: Draw sensing vector a, from standard multivariate normal distribution
4: Obtain m PAQ measurements (7,))),,.... (7; (m))) with a, and y.
5: Bias elimination via averaging: compute averaged response 7/2 1 2===1 (7: )))
6: Heavy tail mitigation via truncation: compute truncated response 7 79 AT.
7: end for
Output: truncated responses ...... 7n
To keep the total number of measurements constant, later. For each sensing vector a;, we compute the empirical mean of the m measurements:
where the value of m is specified
1 m
m
(5)
V+ n
(6)
m
m /=1 D'a,
E'a,
1/ (5) ンド=
where define the average noise by fj:
This averaging operation reduces the
effective noise variance from var(n:) = V2 to var v/ If is small, we may have large error due to an insufficient number of query vectors a, On the other hand, a small m leads large bias. Therefore, we set the value of m carefully to balance these two effects. This is studied theoretically in Section 4 and demonstrated empirically in Section 5
Step 2: Heavy tail mitigation via truncation. Next, we need to control the heavy-tailed behavior introduced by the a ब.ं term in the sensing matrix Ann Note that the sample averaging procedure (6) does not mitigate this problem. We adopt the approach [39] and truncate the observations. Specifically, truncate the averaged measurements 7/2 to 722 := 72 where 7 > 0 is truncation threshold that we specify later. We then construct the truncated sensing matrices
y/ + iBs a. ((a E'a: AT) a.a,
= aa, =
1=
While truncation mitigates heavy-tailed behavior, also introduces additional bias in our estimate. The truncation threshold 7 therefore gives us another tradeoff, and in our analysis to follow, carefully set the value of r to balance the effects of heavy-tailedness and bias.
Final algorithm. Before presenting our final optimization program, we summarize our assumptions and sensing model below.
The noise values π)s are i.i.d copies of the random variable rj, which independent of the random sensing vector a. The random noise is (1) zero-mean: E [y] O, and (2) bounded: There exists a positive constant ny such that -y S 17 S n7 with probability 1.
Assumption 1.
We choose the sensing vector distribution be the standard multivariate normal distribution and collect, average, and truncate N PAQ responses following Algorithm [ This process yields n truncated responses 7/- ... 72- We then use these truncated responses to form the averaged and truncated matrices [A.] which we substitute into the original least-squares problem ( To estimate E solve
E E arg min
1 ( + An E|
(8)
n1
where, again, A, is regularization parameter that we specify later.
Practical considerations. In the averaging step, we collect measurements for each sensing vector a, These measurements could be collected from m different users. Furthermore, recall from
Section 2.2 that the measurements do not depend on the reference item As result, may
7

---

also collect multiple responses from the same user by presenting the same query vector a, with different reference items. In addition, recall from Section that user responses are inverinva Practitioners are hence free to set the boundary to be any positive value of their choice without loss of generality, and the noise 7 scales accordingly with y. The user interface does not depend on the value of
4 Theoretical results
We now present our main theoretical result, which is a finite-sample error bound for estimating a low-rank metric from inverted measurements with the nuclear norm regularized estimator (8) Our error bound is generally stated, and depends on the averaging parameter and the truncation threshold т. Recall that vy denotes the variance of 77. define the quantities y² := y + '/ and By - median(n). We further denote by 01 2 .... or > the non-zero singular values of Σ.
Theorem Suppose E* is rank with > Assume that we choose the sensing vector distribution the be the standard multivariate normal distribution, that Assumption 2 holds on the noise, and that we collect, average, and truncate measurements following Algorithm [
Further, assume that the truncation threshold T satisfies Z - Then there are positive constants c, C, Cr and Cz, such that if the regularization parameter and the number of sensing vectors satisfy
3
d
d
y
V
An Ci
n"
-T
and 2 C2rd,
(9)
OCT
n
O+T
O,T m
then any solution Σ to the optimization program
satisfies
(2')
| - E" Sc
vrdu
(10)
My
with probability at least 1 4e- cm
The proof of Theorem iss presented in Appendix E The two sources of bias discussed in Section 3.2 appear in the expression (9) for the regularization parameter X,, (and consequently the error bound (10 The term scaling 1/T corresponds the bias induced by truncation, and decreases as truncation gets milder (i.e., as the threshold т gets larger). The term scaling as v²//m corresponds to the bias arising from dependence between the noise and sensing matrix. As discussed in Section 3.2 in this model, m-averaging results in a bias that scales like 1/m. Given the dependence of the estimation error bound on the parameters m and т, carefully set these parameters to obtain tight bound as a function of the number of total measurements N = mn. These choices for m and т. along with the final estimation error, are presented in the following corollary, proved in Appendix H
Corollary 1. Recall that N mn. Assume that the conditions of Theorem 2 hold, and set the values of the constants (c, C, C1, C2) according to Theorem 1 Suppose that the number of total measurements satisfies
20 2/2 V²
2/2 v { (card]
N >
(11)
(yt)²
Set the averaging parameter m. and truncation threshold T to be
1/a
and T= y¹ N
(12)
ty
d
opr md.'
and set An equal to its lower bound in With probability at least 4e-d e cN/m we have:
2 d (a) If
1 v
then any solution E to the optimization program No
satisfies
| 15-E E' C² of (y
(
d
1/a
3/2
(13)
or 22
N
8

---

2 (b) If (uty S /V2 No then any solution E to the optimization program g
satisfies
I E'Irr & C² oi
3/
d
(14)
Hyy
N
In both cases, C" = 3C C₁.
few comments are warranted about our enror bounds
13 and 14
Error rates and noise regimes. Under the standard trace measurement model, it is known that if the measurement matrices are i.i.d. according to some sub- Gaussian distribution and the number of measurements satisfies N Z rd, then nuclear norm regularized estimators achieve an error that
scales like / / 24 25 Such result is also known to be minimax optimal 25
Allowing
heavier-tailed assumptions on the sensing matrices, such as sub-exponential 33
42 or bounded
fourth moment [39] typically results in additional log d factors but does not impact the exponent
1/2 in the error rate. However, crucial assumption these results that EE there is no bias due to measurement noise. Our inverted measurement sensing matrix is not only heavy-tailed but also Icads to bias (sce Lemma | in Appendix D.I). Nevertheless, we are able to reduce the bias and trade it for variance, ensuring consistent estimation in all regimes.
[ itv = 0, and thus
In Corollary there two distinct cases for error rate which correspond two different noise regimes induced by the quantity (o)("")), which captures the noise level in our measurements. In particular, the two cases Corollary correspond two regimes with distinct bias behavior:
(a) High-noise regime: this setting, the bias due to measurement noise non-negligible. As result, we employ averaging with large m, which results in the rate scaling as (d/N)/s.
(b) Low-noise regime: In this setting, the measurement noise bias is dominated by the variance, and thus has negligible impact on the estimation error. As a result, we are able to achieve rate of order (d/N) which consistent with established results for low-rank matrix estimation.
Sample complexity. Since the degrees freedom in a rank-r matrix of size x d order rd, one expects that the minimum number of measurements to identify rank-r matrix is of order rd. This reflected in Theorem I which assumes that the number of distinct sensing vectors {a,} satisfies n Z rd. In the high-noise regime, from 12) in Corollary | we have that m scales like (N/d)/ V/_ Thus, the total number measurements is
mn Z (N/d)Vs rd Z N and hence N Z ddd. Given that the rank is assumed to be relatively small compared to the dimension, the extra factor of /F is relatively small price to pay obtain consistent estimation. In the low-noise regime, it can be verified that averaging is needed, and we only require N n Z rd.
in 12 due the low-noise condition 1 22/(0 vd/N. No
Dependence on rank. When compared to standard results, Corollary I differs in its dependence on rank. First, the matrix Σ assumed to have rank 8. This prevents the term a Σ.a from making the sensing matrices so heavy-tailed that even truncation does not help. We empirically show that the assumption of > 8 necessary in Section 5 Second, there is an additional factor of in our rate for both noise regimes. To interpret this, note that if Σ* has non-zero singular values in fixed range, then E [a Σ inversely proportional to a "'a, a, increasing r decreases the magnitude of inv and thus also (for a fixed noise level) the signal-to-noiss, ratio.
(Σ*) = r. Since the "magnitude" of the sensing matrix A inv is
Scale equivariance. As discussed Section 2.1 the metric learning from PAQs problem aims to find an equivalence class {CCscate Coccale)) ) Cscale 0}. and the ground-truth Σ* is defined with respect a particular choice of y. Accordingly, our error bounds are scale-equivariant: If we instead replaced y with Cscale?/, the bounds
(13) and (14) would scale linearly in Cscale This fact is precisely verified Appendix [ and relies on the fact that the noise also scales appropriately Gsaaee Thus practitioners may simply set y to be any positive number.

---

0.0
1-
Normelzed est emtrr (lgg
-00.5
Nermallees aror
d (40x 421 WAU 1000
(Cee XOL 10U
-1.
-1.0
eros, ND0 464
Normaltzed edt
-15
-1.5
2.0
-2.0
aver, Nbl 1002
-2.5
3.0
5.50
0.0
10
30 Avereging perameter
Nomalized total messurements Nid (log10)
Number of total meszuremens (log10)
(b)
(c)
Figure 4: Simulations quantifying the effect of dimension d, rank r, and averaging parameter m on estimation error. Shaded areas correspond standard error of the mean but sometimes not visible.
5 Numerical simulations
In this section, we provide numerical simulations investigating the effects of the various problem and estimation parameters. For all results, report the normalized estimation error |Σ Σ- |F Σ averaged over 20 trials. Shaded areas (sometimes not visible) represent standard error of the mean. For all experiments, we follow [19] and generate the ground torund metric matrix E vrr
UU where U Rdxr is randomly generated matrix with orthonormal columns. The noise 17 is sampled from a uniform distribution on [-n]" .7"] (where ny S y). We set the regularization parameter, truncation consistent with theoretical results (see Eqs. ( and (12). cross-validating to choose the constant factors. We solve the optimization problem using
threshold, and averaging parameter in a
cvxpy 43 44]. Code for all simulations provided at witttts::/ httttt::///gitiii //github com/ wwwsinnuu7//pa// /pqq
Effects of dimension and rank. Our first set of experiments characterizes the effects of dimension and matrix rank For all experiments, unless are sweeping specific parameter, we set y 200, = 50, r= 15, and s7 = 10. Fig. shows the performance for varying values of d plotted against the normalized sample size N/d. For all dimensions d, the error decays to measurements N increases. Furthermore, the error curves are well-aligned when the sample size is normalized by d with fixed r, empirically aligning with Corollary D Fig. shows the performance for varying values of rank r. Recall that for our theoretical results we assume r > 8 to ensure that the quadratic term a E' a in the denominator of sensing matrices does not lead excessively heavy-tailed behavior. When error increases as the rank increases. A clear phase transition occurs at r 8. The error still decreases with N for r < 8, but at markedly slower rate than when r >> 8. This empirically demonstrates that when < 8, the sensing matrix tails are heavy to be mitigated by truncation.
the total number of
8, the number of measurements required for the same estimation
Effect of averaging parameter m. Equation (12) suggests that the averaging parameter m should scale proportionally to (N/d)*/. To test this, we set y 200, d 50, r 9, and Ty = 200. We vary values of m for different choices of the (N, pair, shown in Fig. 4c The empirically optimal choice of m is observed to be the same when N/d / is fixed, regardless of the particular choices of N or d (the green and red curves overlap, and the blue and orange curves overlap). Moreover, the optimal m is smaller when N/d = 400 compared to when N/d = 1000.
Discussion
In this paper we introduced the perceptual adjustment query, cognitively lightweight way obtain expressive responses from humans. We specifically investigate using PAQs for human perceptual similarity learning. We use a Mahalanobis distance-based model for human similarity perception and use PAQs to estimate the unknown metric. Using random measurements to learn an unknown Mahalanobis metric gives rise to the new inverted measurement scheme for high dimensional low rank matrix estimation which violates commonly held assumptions for existing estimators. We developed a two-stage estimator and provide corresponding sample complexity guarantees. This work opens up many interesting lines of future work in inverted measurements. One key direction is to characterize their fundamental limits with information- theoretic lower bounds.
aefroatiio--hhoortte
10

---

Acknowledgments
AX was supported by National Science Foundation grant CCF-2107455. JW was supported by the Ronald J. and Carol T. Beerman President's Postdoctoral Fellowship and the Algorithms and Randomness Center Postdoctoral Fellowship at Georgia Tech. MD was supported by National Science Foundation grants CCF-2107453 IIS-221218 and RMS-2134037. AP was supported in part by the National Science Foundation grants CCF-2107455 and DMS- 2210744, and by research awards/gifts from Adobe, Amazon and Mathworks.
References
[1] William L. Rankin and Joel W. Grube. A comparison of ranking and rating procedures for value system measurement. European Journal of Social Psychology, 10(3):233-24 1980.
[2] Anne-Wi Harzing, Joyce Baldueza, Wilhelm
Cordula Barzantny, Anne Canabal, Anabella Davila, Alvaro Espejo, Rita Ferreira, Axele Giroud, Kathrin Koester, Yung- Kuei Liang, Audra Mockaitis, Michael J. Morley, Barbara Myloni, Joseph O.T. Odusanya, Sharon Leiba O' Sullivan, Ananda Kumar Palaniappan, Paulo Prochno, Srabani Roy Choudhury, Ayse maka-Helmhoutt Sununta Siengthai, Linda Viswat, Ayda Uzuncarsili Soydas, and Lena Zander. Rating versus ranking: What is the best way to reduce response and language bias in cross-national research? International Business Review, 18(4):417-432, 2009. ISSN 0969-5931.
[3] Georgios N. Yannakakis and John Hallam. Ranking vs. preference: A comparative study of self-reporting. In Sidney D D'Mello, Arthur Graesser, Björn Schuller, and Jean- ClanCClaude Martin, editors, Affective Computing and Intelligent Interaction, pages 437-446, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-9-6442-24600-55
[4] Nihar B. Shah, Joseph K Bradley, Abhay Parekh, Martin Wainwright, and Kannan Ramchandran. A case for ordinal peer-evaluation in MOOCs. In NIPS Workshop on Data Driven Education, 2013.
[5] Karthik Raman and Thorsten Joachims. Methods for ordinal peer grading. In Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining, volume 20, 2014.
[6] Richard D. Goffin and James M. Olson. Is it all relative? Comparative judgments and the possible improvement of self-ratings and ratings of others. Perspectives on Psychological Science, 6(1):48600, 2011.
[7] William Bamett. The modern theory of consumer behavior: Ordinal or cardinal? The Quarterly Journal of Austrian Economics, 6(1):41-6) 2003.
[8] Richard Batley. On ordinal utility, cardinal utility and random utility. Theory and Decision, 64: 37-63, 2008
[9] Nihar B. Shah, Sivaraman Balakrishnan, Joseph Bradlcy, Abhay Parekh, Kannan Ramchandran, and Martin J. Wainwright. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. Journal of Machine Learning Research, 17(58):1-47, 2016.
[10] Jingyan Wang and Nihar B. Shah. Your my 1, your 3 my 9: Handling arbitrary miscalibrations in ratings. In Proceedings of the 18th International Conference Autonomous Agents and Multiagent Systems, 2019.
[11] Dale Griffin and Lyle Brenner. Perspectives on Probability Judgment Calibration, chapter 9. Wiley-Blackkell, 2008. ISBN 9780470752937.
[12] Polina Harik, Brian Clauser, Irina Grabovsky, Ronald Nungester, David Swanson, and Ratna Nandakumar. An examination of rater drift within a generalizability theory framework. Journal of Educational Measurement, 46:43-58, 2009.
[13] Carol M. Myford and Edward W. Wolfe. Monitoring rater performance over time: A framework for detecting differential accuracy and differential scale category use. Journal of Educational Measurement, 46(4):371-389 2009.
11

---

[14] Gregory Canal, Stefano Fenu, and Christopher Rozell. Active ordinal querying for tuplewise similarity learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 2020.
[15] Yiming Ying, Kaizhu Huang, and Colin Campbell. Sparse metric learning via smooth optimiza- tion. Advances in Neural Information Processing Systems, 22, 2009.
[16] Wei Bian and Dacheng Tao. Constrained empirical risk minimization framework for distance metric learning. IEEE Transactions on Neural Networks and Learning Systems, 23(8):1 194- 1 1205, 2012.
[17] Zheng-CUI Chu Guo and Yiming Ying. Guaranteed classification via regularized similarity learning. Neural Computation, 26(3):497-522 2014.
[18] Aurélien Bellet and Amaury Habrard, Robustness and generalization for metric learning. Neurocomputing, 151:259-267, 2015.
[19] Blake Mason, Lalit Jain, and Robert Nowak. Learning low-dimensional metrics. In Advances in Neural Information Processing Systems, volume 30, 2017.
[20] Aurélien Bellet, Amaury Habrard, and Marc Sebban. Metric Learning. Springer Nature, 2022.
[21] Ian Goodfellow, Jean Pouget-Abadis Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems (NeurIPS), 27, 2014.
[22] Tero Karras, Samuli Laine, Mïika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Analyzing and improving the image quality of stylegan. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pages 8110-8119, 2020.
[23] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, (333):77-5501, 2010.
[24] Sahand Negahban and Martin Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. The Annals of Statistics, 1992)10099-099,, 2011.
[25] A Tsybakov and A Rohde. Estimation of high-dimensional low-rank matrices. The Annals of Statistics, 39(2) 2011.
[26] Emmanuel J Candes and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Transactions on Information Thheory 57(4):2342 2359, 2011.
[27] Sahand Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu. A unified framework for high-dimensiooal analysis of M -eestimators with decomposable regularizers. Statistical Science, 27(4):538-557, 2012.
[28] T Tony Cai and Anru Zhang. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE Transactions on Information Theory, 60(1):122-132, 2013.
[29] Mark A Davenport and Justin Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing, 10(4):608-62) 622, 2016.
[30] Yuxin Chen, Yuejie Chi, and Andrea J Goldsmith. Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Transactions on Information Theory, (7): 4034-4059, 2015.
[31] T Tony Cai and Anru Zhang. ROP: Matrix recovery via rank-one projections. The Annals of Statistics, 43(1) 13(1):102-11 138, 2015.
[32] Richard Kueng, Holger Rauhut, and Ulrich Terstiege. Low rank matrix recovery from rank one measurements. Applied and Computational Harmonic Analysis, 42(1):88-11) 116, 2017.
12

---

[33] Andrew D McRae, Justin Romberg, and Mark A Davenport. Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer. IEEE Transactions on Information Theory, 69(3): 866-1882, 2022.
[34] Po-Ling Loh. Statistical consistency and asymptotic normality for high-dimensional robust M-estimators. The Annals of Statistics, 45(2):866-89) 2017. doi: 10. 10.1214/16-A0S4771
[35] Jianqing Fan, Quefeng Li, and Yuyan Wang. Estimation of high dimensional mean regression in the absence of symmetry and light tail assumptions. Journal of the Royal Statistical Society Series B, Statistical methodology. 79(1) (9(1):247-655 2016.
[36] Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983.
[37] Stanislav Minsker. Geometric median and robust estimation in Banach spaces, Bernoulli, 21(4): 2308 2335, 2015.
[38] Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. Journal of Machine Learning Research, 17(1):543-582, 2016.
[39] Jianqing Fan, Weichen Wang, and Ziwei Zhu. A shrinkage principle for heavy-tailed data: figh-dimensional robust low-rank matrix recovery. The Annals of Statistics, 49(3):123--120 2021.
[40] Austin Xu and Mark Davenport. Simultancous preference and metric learning from paired comparisons. Advances in Neural Information Processing Systems, 33, 2020.
[41] Gregory Canal, Blake Mason, Ramya Korlakai Vinayak, and Robert Nowak. One for all: Simultaneous metric and preference learning over multiple users. In Advances in Neural Information Processing Systems, volume 35, 2022.
[42] Sahand Negahban and Martin J Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Journal of Machine Learning Research, 13(1):1665- 1697, 2012.
[43] Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[44] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 60, 2018.
[45] Andrew K Massimino and Mark A Davenport. As you like it: Localization via paired compar- isons. Journal of Machine Learning Research, 22(1):8357-885) 88997,83350000 2021.
[46] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[47] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. ISBN 9780199535255. 00110001.
doi: 10. 1.11933/cpofoss0007119955333333
[48] Yong Bao and Raymond Kan. On the moments of ratios of quadratic forms normal random variables. Journal of Multivariate Analysis, 117:229-245. 2013.
the [49] Shahar Mendelson. Learning without concentration. Journal the ACM (JACM), 62(3):1-25, 2015.
[50] Joel A Tropp. Convex recovery of structured signal from independent random linear measure- ments. Sampling Theory, a Renaissance; Compressive Sensing and Other Developments, pages 67-101,
[51] Mark Rudelson and Roman Vershynin. Hanson- Hannon-Wrightt tion. Electronic Communications in Probability, 18:1-9, 2013.
Wright inequality and sub-guussaes gaussian concentra-
[52] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 2010.
13

---

A Broader impacts and limitations
In this section, we discuss the broader impacts and limitations of our work.
A.1 Broader impacts
Automated systems that use human feedback are being used in increasing number of contexts, spanning everything from predicting user preferences to finetuning language models. It is important ensure that such systems accurate and consistent manner. Using the perceptual adjustment query to collect data in such settings could lead more expressive responses without heavy cognitive burdens on users. Furthermore, providing a user the additional context of a continuous spectrum of items may result in more self- consistent responses. The downstream effects of collecting more expressive and self-consistent human responses could lead to improved models or entirely new paradigms of model development for a myriad of problem settings. With these advantages come associated risks as well. Due to how expressive the responses to PAQs are, the effects of adversarial responses may be magnified. That is, an adversary purposely chooses to respond in an antagonistic manner, models trained with PAQs may be trained poorly or in opposition to the stated goal. Mitigating such effects likely requires holistic approach from both the query design and robust model design perspectives.
accurate possible; this naturally requires humans respond in an
A.2 Limitations
From a data collection perspective, the perceptual adjustment query requires access to continuous space where each point corresponds to an item. In many applications, assuming access to this continuous space is reasonable. For example, if we use PAQs to characterize color blindness, then natural continuous space is the RGB color space. In general, we situate our data collection within the latent space of a generative model, such GAN. While GANs are capable of producing extremely high fidelity images, these images are not always free of semantically meaningful artifacts. Our query design and modeling assumptions do explicitly consider the case where a portion of the continuous spectrum of items may be corrupted. Furthermore, because our work is an initial exploration into low-rank matrix estimation from inverted measurements, we have not considered scenarios such as unbounded noise or heavier-tailee sensing vectors, and we have not established information-theoeeee lower bounds for the inverted measurement paradigm. We hope that further exploration of the inverted measurement paradigm will lead to a rich line of follow-up work.
B Simulation details
In this section, we provide details for the simulation results presented in Figure 2 For our experiments,
we adopt a normalized version of the setup of (30 and form the metric E by " LL / | ||F- where L is a 50 x 10 matrix with i.i.d. Gaussian entries. We sweep the number of query responses
N, estimate the metric with Σ, and report the normalized estimation error | - Σ|1F [||/|||[* | averaged over 10 independent trials. For each query response, items are drawn i.i.d. from a standard
multivariate normal distribution, similar to 45
Pairwise comparison setup. For pairwise comparisons, we use value of y 10 to denote the squared distance at which items become dissimilar, following our distance-based model for human (8) (
perception (see Section 2.1 For the i-th pairwise comparisons, we draw two items Φ , 222 i...d. from a standard multivariate normal distribution. We record the pairwise comparison outcome 1 - y). To estimate the metric from pairwise comparisons, e; E {[1,++1 as & = sign([>= -() ||
utilize nurlear-norm regularized hinge loss and solve the following optimization problem:
N
εpc arg min
Σ
max (0, y =1 x. (11)) + \ve E||.
Ero
N
Triplet setup. For the i-th triplet, we draw three items 21 (0 2..
(t) i..dd from a standard
multivariate normal distribution and record the outcome {-1,+11 e, sign([|=]*
14

---

(3) 1. 22 3.
To estimate the metric from triplet responses, we follow [99 and utilize a nuclear- norm regularized hinge loss and solve the following optimization problem:
|
(5)
N
En E arg min E-0
max 0, 0, - (112f
11 - -1 - xx- 133 EII.
N
1=1
Ranking-k query setup. For the i-th ranking query with a reference item æn and &t items 21..... 24 to be ranked, draw all items i.i.d. from standard multivariate normal distribution. For each item Zk, we compute the squared distance ||z0 2 To determine the ranking of items, we sort the items based on this squared distance. To estimate the metric, follow the approach of [14] and decompose the full ranking into its constituent triplets. A ranking consisting of & items can equivalently be decomposed into k(k 1)/2 triplet responses. To estimate the metric, decompose each ranking query and use the triplet estimator presented above with regularization parameter AR to obtain estimate ER
PAQ setup. For the i-th PAQ response, we draw the reference item æ; and query vector a; ii.d. from the standard multivariate normal distribution. We then receive scaling 7 satisfying y a E' az with y 10. To perform estimation, we leverage our method presented in Section 3 Our theoretical results indicate that the averaging parameter m should be set to 1 in the noiseless setting. Furthermore, the truncation threshold is large relative to responses 7/, meaning no truncation is employed. As a result, we solve the nuclear-norm regularized trace regression problem
N
ΣPAQ arg min E
1
Σ (a.a, Σ)
y 7/
+ APxQ E
In all cases above, we solve all optimization problems with cvxpy and normalize the estimated metric {PC. T. R-k, PAQ) to be unit Frobenius norm to ensure consistent scaling when compared against the true metric E' We use value of 0.05 for all regularization parameters X(PC, R-k, and observe similar performance trends for other choices of regularization parameter.
C Scale equivariance
In this section, we verify the scale-equivariance of our derived theoretical bounds (3) and (4p. Specifically, we denote by E* and Σ the ground-truth and the estimated matrices corresponding to value y. We denote by Σ and Σ. the ground- truth and estimated matrices corresponding to value Cscaley for any Gucale > By definition, we have Σ E' and it can be verified that solving the optimization program ( yields Σ, Oscale Σ. Hence, one expects the error bound to scale as Cscale. To verify this linear scaling in Cscale, confirm that the noise v) scales Gscale-
Under the ground-truth metric Στ, if the user responds with an item that distance y + y) away from the reference item, then that same item is distance Cacale (y + 17) away from the reference under the scaled setting. As a result, the noise scales as a result the choice of y. Therefore, the following values in the upper bound (13) can be written scaled versions of their corresponding "ground-truth" values.
Noise
17 Cscale 7)x
Noise median
My = Cscale Myy
Noise upper bound
n = Cscale 7
Boundary upper bound
y" Cscale (V+ + n
Noise variance
2 2
Singular values
Tk Cscale Ji 1,...."
"
scale 4)*
Substituting these scaled expressions into the upper bounds and 14). we have
[Σ.- Ex S Cscale O" (ot)² (ul) 1/
(12,.)
d 1/3
4/2
of
(mg)2
N
15

---

in the high-noise regime and
(ot)²
31
d
1/2
E. EgllF S
Cscale C²
o
N
in the low-noise regime. Note that the constant C' is independent of Cscale-
D Preliminaries and notation
In this section, provide overview of the key tools that are utilized in our proofs. We first introduce notation which used throughout our proofs.
Notation. For two real numbers and b, let A b min Given vector E R denote ||>|| and || as the & and &2 norm, respectively. Denote 54-1 = for E Rd |||||| 1] to be the set of vectors with unit f2 norm. Given a matrix A E xd2, denote ||A|| |||| and || op as the Frobenius norm, nuclear norm, and operator norm, respectively. Denote gdxd
{A E R
A AT) to be the set of symmetric d d matrices. Denote A to mean A symmetric positive semi-definite For A 0, define the (pseudo-) inner product (æx, y) A
x T "Ay and the associated
(pseudo-) norm | A v Ax. For matrices A, E gd xds denote (A, B) = tr (A B) as the Frobenius inner product.
We use the notation f(z) I g()) denote that there exists some universal positive constant > such that fz) S c ((x), and use the notation f(x) Z g(r) when g(x) 2 f(z).
We define random matrices
À ==
= y+ aa
(15)
a
and
Ā Ā=
y リ+ n*a
At
aa
(16)
as the sensing matrix formed with the m-averaged responses and truncated responses 7, respectively.
D.1 Inverted measurement sensing matrices result in estimation bias
Recall from Equation 4 that the random sensing matrix A inv takes the form
y + Σ aa
Standard trace regression analysis assumes that for some sensing matrix and measurement noise [nA] O. Specifically, is often typically assumed that 77 is zero-mes menn conditioned on the sensing matrix A. The following lemma shows that for the inverted measurements, we have E|nA'n inv o resulting in bias in estimation.
Lemma 1. Let A jnv be the random matrix defined in Eq. (4) and be the measurement noise. Then
[ inv
0.
The proof of Lemma]) is provided in Appendix I.6.I Hence, utilizing established low-rank matrix estimators for inverted measurements results in biased estimation.
D.2 Sub-exponential random variables
Our analysis utilizes properties of sub-exponential random variables, class of random variables with heavier tails than the Gaussian distribution.
Lemma 2 (Moment bounds for sub-exponential random variables 46 Proposition 2.7.1(b)).. If
X is a sub expoonnnottaall random variable, then there exists some constant e (only dependent the distribution of the random variable X) such that for all integers 2 1,
(E|XP) 1/ ep.
16

---

D.3 Bernstein's 's inequality
In our proofs, we use Bernstein's inequality to bound the sums of independent sub-exponential random variables.
Lemma 3 (Bernstein's inequality, adapted from 47 Theorem 2.10)). Let Xi...., Xn be independent real-valued random variables. Assume there exist positive numbers u1 and u2 such that
p! U1 for all integers p 2 2,
X S u1
and E| -
2
Then for all t >> 0,
P - Σ (x, -X,,l]
2ui
u2t s 22ep(--t).
[(,,))
n
n
D.4 Moments of the ratios of quadratic forms
The quadratic term a E*a appears in the denominator of sensing matrices, we use the following result to quantify the moments of the ratios of quadratic forms.
Lemma 4. There exists an absolute constant > such that the following is true. Let a ~ N Ia). E Radd be any PSD matrix with rank r, and U E dddd be an arbitrary symmetric matrix.
(a) Suppose that r > Then we have
E
a a==a
Oty4"
(b) Suppose that >>> 2. Then we have
E
a
Ua
S o,r
|U]|.
a aTEa
The proof of Lemma is presented in Appendix D.6.2
D.5 A fourth moment bound for 72
Recall from Equation (6) that the averaged measurement 722 takes the form
7/2 1 П リナク (
u+N T a. a: Σ'a
Throughout analysis, utilize the fact that 8² has bounded fourth moment, characterized in the following lemma.
Lemma 5. Assume r > Then there exists a universal constant c O, such that
(52) < c y u+7! 17'
where is the smallest non-zero singular value of Σ*
The proof Lemma is presented Appendix D.6.3 For notational simplicity of the proofs, we
denote M =
y+n
d,7
D.6 Proofs of preliminary lemmas
In this section, we present proofs for preliminary lemmas from Appendices D.I D.4 and D.5
17

---

D.6.1 Proof of Lemmal 1
Using the independence of the noise and the sensing vector a, and the assumption that v) is zero mean, we have
71 + 11)
E | inv] = E
a a.a aa
= E. [n(v + v))]
a0
a
E
1
uig E
aa
(17)
E'a
The expectation in 17 is non-zero, because the random matrix D.a aa is symmetric positive definite almost surely. Therefore, we have [N] A O, as desired.
D.6.2 Proof of Lemma 4
Since Σ" is symmetric positive semidefinite, it be decomposed QEQT, where Q is square orthonormal matrix and Σ diagonal matrix with non-negative entries. Multiplying a by any square orthonormal matrix does not change its distribution. Therefore, without loss of generality, assume that E' is diagonal with all non-negative diagonal entries. We first note that the moments of the ratios in both parts of Lemma exist, because by [8 Proposition for non-negative integers
(a Ua)"
p and q, the quantity E
(a Er exists > 9. Furthermore, we use the following expression
from 48 Proposition 2):
E Ua) P
1 I'(a)
19-1 A ..IEE E A dt,
(18)
a
where A, (Ia + 2 and A is the determinant of A, To characterize the determinant A we note that A, is diagonal matrix whose d diagonal entries are
1
1, ....
(1 + 2to 1/2"
(1 2to,) 1/22
Hence, the determinant is the product bounded as:
Arl II
Furthermore, this product can be
(1+210;)*
A S
(19)
(1 270,)
We now prove parts (a) and (b) separately.
Part (a). Using the integral expression determinant, we have
18 with p = and 4, and the upper bound 19 on the
1
E
3 | dt
>'a
T(4)
1
3
2to 3/2 dt.
T(4)
(1
18

---

Denoting s : 1 + 2to,, we have
[
(8-1)
1
E
87/2 ds
a
2[(4)
20,,
1)3
ds
8//2
8
8
1
ds
87/2
8/2
8
8
1
6
2
1
6
T
0 04/4
as desired.
Part (b).
Using the integral expression (18) p - 1 and the upper bound (19) on the determinant,
we have
TUa
1
A E T. Ta A.AAA dl
a E'a
[(1)
1 r(1)
E 3(a A,U dt. (1 + 2to,
(20)
We bound the expectation term in 20 Note that for No, Ia), have E [a Ba] tr (B) for any symmetric matrix B. Therefore, we have
E a A. tr (AUA,)
AUAI
UU],,
(21)
where (i) the fact that tr (B) < |B|| for any symmetric matrix B. Furthermore, (ii) follows
from Hölder's inequality for Schatten-p norms, where have that || A.ll- < | |
Because A, is diagonal and the entries of A, are bounded between 0 and bound the operator
norm as Atllop < 1. Substituting
to 20
we obtain
Ua a Σ
|U|,
(1+ + 21o dt
1
|
orr
desired.
19

---

D.6.3 Proof of Lemma 5
By the assumption that the noise is upper bounded by n7,, we have + S + n7" Therefore, we have
E B E
y + fj
D'a
$ (v + 17 17
E+aa
SV
1
0,4
where step (i) applies part (a) of Lemma
E
Proof of Theorem
Recall that we assume we collect N measurements under the inverted measurements sensing model presented in Algorithm [ with standard Gaussian sensing vectors and bounded noise, mean-zero
noise (Assumption I
We first introduce a restricted strong convexity (RSC) condition that our proof relies on. Since the matrix E' is assumed to be symmetric positive semidefinite matrices and of rank r, we follow [24] and consider restricted set on which we analyze the behavior of the sensing matrices A, We call this set the "error set", defined by:
ع {-(UE
|| S guxd;
< 4/2r
(22)
where recall that Sdxd denotes the set of symmetric d d matrices. We say that shrunken sensing matrices ) satisfy restricted strong convexity (RSC) condition over the error set E, if there exists some positive constant >> O such that
n [A. 2 u (A..
for all U E.
(23)
The following proposition shows that the estimation error, when the sensing matrices satisfy the RSC condition and the regularization parameter is sufficiently large.
Proposition 1 (39 Theorem 1] with q 0). Suppose that E has rank and the shrunken sensing
matrices satisfy the restricted strong convexity condition the regularization parameter satisfies
23
with positive constant >> 0. Then if
An
VA,
A,
Σ* A
(24)
lop
any optimal solution Σ of the optimization program
satisfies
| -' S 32
K
This theorem is special case of Theorem in [39 which is in turn adapted from Theorem I in (44] (see 24 or 399 for the proof). Proposition]] Tis is a deterministic and nonasymptotic result and provides roadmap for proving
desired upper bound. First, show that the operator norm (24) can be
upper bounded with high probability, allowing us to set the regularization parameter X, accordingly.
Second, we show that the RSC condition 23 is satisfied with high probability. We begin by bounding
the operator norm (24) in the following proposition.
Proposition 2. Let y = tn Suppose that E has rank r, with r > 8. Then there exists a positive absolute constant C₁ such that
2
A Σ (A.
EAA
y²
y
1
-
+
o
op
(25)
with probability at least 1 4exp (-d).
20

---

The proof of Proposition is provided in Appendix E.1 Next, we show that the RSC condition 23 satisfied with high probability, is done in the following proposition.
Proposition 3. Let by be the median of + 7. Suppose that the truncation threshold T satisfies 2
My tr()))) Then there exist positive absolute constants Kg, c, and C such that if the number of sensing vectors satisfy
n2 2 Crd
then we have
n
My ) || tr (E*)
U)2 2 ne
(26)
simultaneously for all matrices U E & with probability at least 1 - exx(-cnn), where & is the error set defined in Equation 22)
The proof of Proposition is provided in Appendix E.2
We now utilize the results of Propositions 12
3 derive our final error bound. By Proposition the operator norm (24 can be upper bounded with high probability. We set the regularization parameter A. to satisfy
y 0,T
An 2 Ci yt
+
9
o,r
where C₁ is the constant in Proposition 2 Furthermore, by Proposition we have that there exist universal constant C2 > 0 such that if the number of sensing vectors satisfies C2rd, the
with high probability. Taking a union bound, we have that Proposition 2 and Proposition hold simultaneously with probability least
RSC condition (33 holds for constant x = kC ir(""))
1 - ex)( exp(-en). Invoking Proposition we have
An
|Σ E'Ile S 32
Mg tr(2"))
KL
Σ
2
rrn
Bly
with probability at least - 4 4exp(-d)
- exp( -n), as desired.
E.1 Proof of Proposition 2
In the proof, decompose the operator norm
Σ yA, - 1=1
E*)
from 25 into
op
individual terms and bound them separately. Recall the definitions of random matrices A from Equation 15 and Á from Equation 16
Step 1: decompose the error into five terms. quantities as follows:
We begin by adding and subtracting multiple
y
Σ
A
M A.
YA
E
8
+
- E [vA]
1 n n Σ (A, E
[
E
(A, Σ A
A
+
(A, Σ A
1
E
+ E
E [WA]
72
R
(A,EE)
- E
AA
E [
+
E
Σ
(A. A.
(27)
1=1
21

---

where step (i) is true by substituting y = (A. to the term of E [yA] and the fact that the noise term 1j is zero-mean. By triangle inequality, we group the terms in (27 and bound the operator norm by
n n
y
y
Σ
2 A
A
y y
1 Σ
A
E
A
op
Torm
E A
Term 2
(A. E A
+
op
Term
(A. > A
1 Σ (A E' )
A
71
op
Term 4
E
[A
(28)
op
Term
In the remaining proof, bound the five terms in 28 individually. We first discuss the nature of these five terms.
Terms 1 and 4: These two terms characterize the difference between the empirical mean of quantities involving A and their true expectation (see Lemma 6 and Lemma 9). In the proof, we show that the empirical mean concentrates around the expectation with high probability, as a function of the number of sensing vectors n.
Terms 2 and 3: These two terms characterize the difference in expectation introduced by truncating A to A (see Lemma 7 and Lemma 8) Hence, these two terms characterize biases that arise from truncation. They diminish as r - co, because setting T to oc is equivalent to no thresholding, and hence A becomes identical to A. Since expectations are considered, these two terms depend on the threshold r, but not the number of sensing vectors n or the averaging parameter m.
Term 5: Term 5 is a bias term that arises from the fact that the mean of the noise conditioned on sensing matrix A is non-zero. We show that this bias scales like (see Lemma 10 in terms of the averaging parameter m.
Putting these terms together, Terms and 4 depend on n, Terms 2 and 3 depend on t, and Term 5 depends on m. In Corollary I we set the values of T, n and m to balance these terms.
Step 2: bound the five terms individually. In what follows, we provide five lemmas to bound each of the five terms individually. fourth moment of the m-sample averaged measurements 3². As shown in Lemma in Appendix D.5 for some absolute constant e, this fourth moment can be upper bounded by a quantity that we denote M:
the proofs of the five lemmas, we rely on an upper bound on the
y
B(( < M =
(29)
We also rely heavily on the following truncation properties relating the m-sample averaged measure- ments 52 and truncated measurements 2:
52 T
(TPI)
7/ < 77
(TP2)
7 - 52 = (5? -
1 2 r).
(TP3)
The following lemma provides bound for Term 1.
22

---

Lemma 6. Let A exists an absolute constant such that for any t O, we have
An be i.i.d copies of random matrix A as defined in Equation 16 There
1 1=1
-
-
M t
Tt
sc
op
with probability at least 1 9d exp (-t).
The proof of Lemma 6 is provided in Appendix E.I.I Term 2.
The next lemma provides an upper bound for
Lemma 7. Let A and A be the random matrices defined in Equation 15 and Equation (16). respectively, Then there exists an absolute constant e > such that
CM 1/2
A
E
A
op
The proof of Lemma is provided in Appendix E.1.2
The following lemma provides upper bound
for Term 3. Recall that the quantity y denotes y+ " n
Lemma 8. Let A and Á be the random matrices defined in Equation 15 and Equation (16). respectively. Then there exists an absolute constant e such that
M
E [AA 1E (A. (A,))) E
The proof of Lemma 8 is provided in Appendix E.1.3 for Term
The following lemma provides upper bound
Lemma 9. Let A A Ān be i.id copies of random matrix Å defined in Equation (16. exists an absolute constant >> O such that for any I >> O, we have
There
E
(A Σ" A
A
E" A
S Scy'
M n
rt
n1
op
with probability at least 1 2 gd cxp (-t).
The proof of Lemma is provided in Appendix E.1.4 We note that Terms 2 and 3 are bias that result from shrinkage, but crucially are inversely dependent on the shrinkage threshold т. This fact allows us to set that the order of Terms 2 and 3 match the order of Terms and 4.
The final lemma bounds Term 5, which a bias that arises from the dependence of the sensing matrix A on the noise
Lemma 10. Let be the random matrix defined in Equation 15 Suppose that Σ* has rank r with
> 2. Then there exists absolute constant >> O such that
E
||
[1.p]
o,r m
The proof of Lemma 10 provided Appendix E.1.5 We note that the bias scales with the variance of the m-sample averaged noise 77, which scales inversely with m.
Step 3: combine the five terms. We set (log + 1)d. Substituting the bounds from Lemmas 10 back to 28 and taking a union bound, we have that with probability at least exp( -dd.
1
M
A
( +1
M
M
1
7
o,r
m
lp
(1) y
y
d +
y'
12
-T
+
+
o,r
O,
7
o,
where step (i) is true by substituting in the expression
29 for M.
23

---

E.1.1 Proof of Lemma 6
Let A4 C S be a -covering of the d-dimensional unit sphere S := far E R4 |||||| = 1}.
By a covering argument [46] Exercise 4,4.3), for any symmetric matrix U E Sdxx its operator norm is bounded by ||'|lop ou v Uv Hence, we have
Σ A A
2 sup mEA1
Σ
A.
[
v
op
1=1
2 sup
Σ i=1
A,
E
Av
(30)
We invoke Bernstein's 's inequality. We first show that the Bernstein condition holds. Namely, we show that for each integer p 2 2, we have that for any unit vector Rdd
p!
Ao
2 U1 22
P-2
(31)
where #1 M and U2 = C2T for some universal positive constants and c2. Given the Bernstein condition 31 we then apply Bernstein's ' inequality bound (30).
We fix any unit vector Rdd Since À = 72aa" T, we have o T Äv = (2 T a2 Recall that the random vector a is distributed as a ~ (O Ia). Since v a unit vector, it follows that v a ~ (O0 1). Denote by G ~ NN 1) a standard normal random variable. For any integer p 2, we have
Proving the Bernstein condition (31).
E U Av
= E
TP 2B (52) G2p
(i)
(7²)² G20)
(m)
S p-2
(77)
E ( 1/2
--ー (M E (G')))²
(32)
where steps (i) and (ii) follow from TP1) and (TP2). respectively; step (iii) follows from Cauchy- Schwarz inequality; and step (iv) follows upper bounding the fourth moment of 72 with the quantity M from Equation (29).
Note that since G is standard normal, by definition G² follows Chi-Square distribution with degree of freedom, and hence sub-exponential By Lemma 2 in Appendix D.2 there exists some constant
> such that we have (E [() 1/r S cp for all p 2 1. Hence, we have (E [G4r]] 1/2y 2cp and
(E [G40]) < (2cp)* = (2))² (2ec)²
p! (2ec)"
(33)
where step (i) is true by Stirling's inequality that for all p 2 1,
p!
2mp cat+1
(
Substituting (33) back to 32 and rearranging terms completes the proof of the Bernstein condi- tion (TT).
Applying Bernstein's inequality to bound 30
By Bernstein's 's inequality (see Lemma 3 given
condition 31.. we have that for any unit vector v E I&d and any f. 0,
IP
Σ im1
A,u
E
Av
2 2
c1
M 1
C2Tt )) < exx (-t).
(34)
24

---

By 44 Corollary 4.2.13), the cardinality of the covering set A, is bounded above by 9d. Therefore, taking a union bound on (34). we have
C271) ))
sup sEAr
A
E
AA
22 2
S 22 gd exp (-t(- (35)
n
Substituting in
(3
35
for any t >
O, we have
P
! Σ i=1
A.
E
A
M
+
2 1 - 9. exx(-t)) Tt
op
as desired.
E.1.2 Proof of Lemmal
By definition of the operator norm, we have
A
E
[
sup wES4-1
T
[A]
E
A
v
We fix any E sd-1, and bound v T (E [A]
1
A
v. Similar to the proof of Lemma 6 we note
that v a (00 1) and denote the random variable G ~ .N(0,)), 1). Substituting in the expression for sensing matrices A and A, have
T
E
A
- E A
5 aa T - - aa |
E [(T --) G*]
@ E [1 77) G2 1152 2(7227]]
=E|/2G2-119
(E[()"09)] E [L 2 +|] 1/2
133 w
1/2
E [1 (1991
(36)
where where step (i) is true because 72 2 72 from to TP2) step (ii) is true due to TP3). and
steps (iii) and (iv) follow from Cauchy-Sehwarz inequality. We proceed by bounding each of the
terms in 36) separately. First, we can upper bound the fourth moment IE []>21[] by the quantity M
from Equation 29 Second, G² is sub- sub-exponential random variable. By Lemma Din Appendix D.2
we have that E ||G V S c for some constant c. It remains to bound the term
(P(F2 (6)))))
We have
i E 17912
P(7²
P
2
2 T)
72
(E 15714) 1/2
72
1/2
72
where step (i) follows from Markov's inequality, step (ii) follows from Cauchy-Schwarz inequality,
and step (iii) follows from the fourth moment bound on the averaged scaling 22. Putting everything together back to (36), we have
M/42
A
[
S
T
for any vector v E Sd Therefore,
1/ 1/2
E
A
EE
AA
S
op
as desired.
25

---

E.1.3 Proof of Lemma 8
Substituting in the definitions A aaa and A aaaa we have
(A, Σ" A A (A, Σ" Ā (5* 7*) (a E'aa
Therefore, our goal is to bound the operator norm
[1 - -7t (a Σ'aa an llop
r" (7 (71-7") (a Σ' an o//.
sup wESS-1
Similar to the proof of Lemma
fix any vector Sd-1, Again, note that v N(0, and
denote G ~ (0, 1). We have
E [[7* 7*) (a E'aa aa
@ ["
(a G
Fa
=
@
S B (
@
2E [[y+ (F- G²]
x 2(y + | (17 12 2 +
where steps (i) and (ii) are true because 2 72 from (T22). step (iii) follows from the definition
5² y+ and step (iv) follows from (T33) and the definition of r) as the upper bound on the noise 77.
The rest of the proof follows the exact steps of the proof of Lemma 7 in Appendix E.1.2 Therefore, we have the bound
y 4
B (5* -71 (a ''aaa aa 1lop 7
as desired.
E.1.4 Proof Lemma
The proof follows the steps as in the proof of Lemma 6 and we describe the difference the two proofs. We again apply Bernstein's 's inequality.
Proving Bernstein condition. We prove Bernstein condition with и1 ci + ))²)² and
U2 = C2 (y + +T) Namely, for every integer
2 2, we have (cf. (31 in Lemma 6
E (Ā, M Au |
< p! unng-
p-2
(37)
2
To show 37 plug in Ā aaaa
T and have
1 T (T(ÁĀ Σー Av
E
(7 a a²
TT Au
E (52 T 'ta)
1 A
E
(y + 7)
Av
1P
I (y + m P.
1
Au
(38)
セ+ー where step (i) follows from (P2 step (ii) follows from the definition 722 a X and step (iii) follows from the definition of s7 as the upper bound on the noise Substituting in 31 from Lemma bound term E v T Äu
(8) completes the proof of the Bernstein condition (37)
26

---

Applying Bernstein's inequality. The rest of the proof follows in the same manner as the proof of Lemma 6 in Appendix E.1.1. with an additional factor (y n7)). We have
(A,2*) )
Σ n
(A Σ A
Sx¹ (v
M
rt
71
11
op
with probability at least 1- gd
exp (-t), as desired.
E.1.5 Proof of Lemma 10
Recall that by definition A = == aa
v+ Dia
aa
We have
EE [A llop
B iT2 77)
aa
a
Σ'a
B 7)]
aa
E
Σ
op
aa
T
E
(39)
m
Σ a
op
To bound the operator norm term we have
39
we apply Lemma
in Appendix D.4
For any matrix U,
a Ua
S 1
U1|.
(40)
a E'a
d,r
Note that E'a is symmetric positive semidefinite, so we have
aa
aa
E
sup v
v
E
Σ
Σ.a
1p
(vo') )a
sup
vC84
a+a
| ||.
sup 0,4 wES4-1
(41)
o,r
where step (i) is true by substituting in 40 with U vo" and step (ii) is true because is unit norm, and hence l || = 1. Substituting back to (39). we have
1 2
E
|A
lop x
orr m
as desired.
E.2 Proof of Proposition
We analyze the term 1 Σ (Ā, U\² from 26 Recall from the definition of Ā that for any i
t=1
I....n
y y Th
A, 3= aaaa
AT AT) a;a
a E'a;
so we have
( U3
a. E'a, 1T)
+ 7
(a (a.)).)
(42)
27

---

From 42 we have that for any matrix U, the term
Σ
(Ai, Uy is nondecreasing in 7 when > 0.
Defining a random matrix
A' =
y+ AT'
an
(43)
D'a
for any r' E (0, r]. we have
Uy Σ Uy?
Uy?
(44)
where for every i = 1,..., n, matrix A is formed with the same realizations of random quantities a, and iJ A, The two matrices only differ in choice of truncation threshold: r' instead of As result, for the rest of the proof, we lower bound
Uy² for an appropriate choice of r' be
specified later. To proceed,
small-ball argument 44 50] based the following lemma.
Lemma 11 (550, Proposition 5. adapted to our notation). Let X....., X, E Rdddd be i.i.d. copies of random matrix X Raxdd Let E Rddd be subset of matrices. Let & > 0 and Q be real values such that for every matrix U E E, the marginal tail condition holds:
((K 2E) Q.
(45)
Define the Rademacher width as
Σ E (X, x U)
W:
sup
UEE 72
where E1...., En are i.i.d. Rademacher random variables independent of (Xi]veln) Then any t 0, we have
1/2
n Σ U)) T1
1
inf UEE
2 2E(Q - - 2W.
with probability at least
exp
nt²
Recall the error set & defined in Equation (2)). Because the claim (26) is invariant to scaling, it suffices prove it for ||U|| = Correspondingly, define the E
E = E E Bddd ||[|==== = =}
(U gaxd, ||U|| = 1, |U|| 4v
(46)
We invoke Lemma 11 with set E defined above, X, Āy' el (1( AF') and Q c2. where My is the median of fj and and 62, constants to be specified later. The rest of the proof is comprised two steps. We first verify that our choices for & and Q are valid for establishing the marginal tail condition (45). We then bound the Rademacher width W above. The following lemma verifies our choices for and Q-
Lemma 12, Consider any T' E (0, T]. There exist absolute constants C1,, C2 > 0 such that for every U E, we have
P (1TT
U3 2
Hl A )) 2 C2.
tr (E+)
The proof of Lemma 12 is presented in Appendix E.2.1 We now turn to the second step of the proof, which is bounding the Rademacher width W. The next lemma characterizes this width.
Lemma 13. Consider any r' E (0,7]- Let
A E Raxd be i.id. copies of the random matrix A E Igdxd defined in Equation (43. Let E be the set defined in Equation (46). Then, there exists some absolute constants er and e2 such that if n ctd, then we have
rd n
E
sup n
Σ (,(At' Uy
S C2T
1=1
28

---

this choice of r' satisfies The proof of Lemma 13 is presented in Appendix E.2.2 condition for Lemma
Lemma establishes the marginal tail and Lemma [3 upper bounds the Rademacher width. We now invoke Lemma 11 and substitute in the upper bound for the Rademacher width W. For some constant ca, if
n 2 c,d, we have that with probability at least - exp exep
1/2
1/2
inf UeB
1 S(A.
inf UEE
Σ i=1
(TT .U)²
i=1
My
AT' (E+)
(c2 - -C3 V
rd
2 tr
where step (i) true due to the monotonicity property 44).. We set T'
in("")' where recall that My
the median of the random quantity 17. By the assumption 7 2 tr(z
My
S T. Setting
62 we have that with probability at least 1 - exp = 2
1/2
1
C102 By
Hy
rd
inf UEE
C3
4 tr())
tr (E+)
n
1=1
| = 1. As result, if 2 max {
2
Recall from the definition of 446 that
Aes
.c rd, we
0102
have
n A., U32
)
2
inf UEE
C1 My tr (E*)
|1118
with probability at least 1 - exp
We conclude by setting Kic
( (11c2) (=
1
8 and
(
C = max
4na c3
C4
in Proposition 3
E.2.1 Proof of Lemma 12
We fix any U E E. Recall that My denotes the median of y + 17. Let & be the event that 7 2 My- which occurs with probability 2. For any & > O, because the averaged noise i) and sensing vector are independent, we have
P (((ā"' U)
y + 17
AF'
(aa "eaTU))22 25
a Σ*a
a Σ*a AF
y +
1(a ((aaT,U))= ,U)] (g) (g)
P
a Σ AT)
1 1
((aaT.U) ,U) g6
2
Hy AT)
|aa ,U> 2
(47)
a Σ
where step (i) is true by plugging in the definition of A=', and step (ii) is true by the definition of the event G. We proceed by bounding the terms in (7) separately.
Lower bound on (aaa) T [.)) We use the approach from inequality,
32 Section 4.1]. By Paley -Zy Zygmund
E ,
P (IKaa ,Uy²² _ [aa ,u>?)
2 4
(48)
E
(aaT , ,U>1"
29

---

We now analyze the terms in (48). As noted in B2 Section 4.1], there exists some constant C1 > 0 such that for any matrix U with U 1,
E KaaT T, .
21 21 and E Kaa T
_ S c1 (B
,)>)²)) {
(49)
Note that by the definition of the set E, every matrix U E E satisfies
||U|| = 1. Utilizing
inequalities 48 and (49) there exists positive constant 02 such that
P (IKaaT. .u
IV
(50)
Upper bound on a T a'a. By Hanson-Wright inequality [5I] Theorem 1.1], there exist some positive absolute constants 0g and eĄ such that for any > 0, we have
IP a E'a S (x") + E || FV 1 llop
:)) ll))))))
1 1-11-22p0 eexp(cxtt (-c+t).
We set 1 log( +) that 2 eexp (cl) - Since E³ is symmetric positive semidefinite, have
co
Σ F S tr (Σ*) and Σ llop tr (Σ*) As result, we have that there exists some constant > 0 such that
P(a a E'a S cs ir
C2
(51)
2
Substituting the two bounds back to 47 By union bound of (50) and 51 we have
IP
Hy
^+)
|aaa
T _U)
2
Hy
)+))
a
Cs tr (x+)
P
Ny
AT'
My
Ar') +P
(aa ,U) 2
1
-1
a a
tr (E))
2
2 P
Hy
My
((aaT T UU\
1 - -1 02
(52)
a E'a
Cs tr
E**)
2
Combining (22 and (47) and redefining constant C2 appropriately, we have
IP (K
Uy
1 1( tr
A1)) 2 (x-)
My
as desired.
E.2.2 Proof of Lemma 13
We begin by noting that for any matrix U E E.
E
sup UEE
Σ
n
(
U)
(
SE R
sup
1 a
A
|U ||
n
UEE
n
1
4
A
(53)
where step (i) follows from Hölder's inequality, and step (ii) follows from the fact that |0 || < 4 2r 2r
from the definition of the set E. It remains to bound the expectation of the operator norm in (53)
We follow the standard covering arguments in [52 Section 5.4.1], [50 Section 8.6), [32 Section 4.1]. with slight modification to accommodate the bounded term
v
AT') that appears in
a. D.
each the matrices A As a result, there exist universal constants 0₁ and C2 such that if n satisfies cjd, then we have
S 027 022 V
=
n
We conclude by re-defining e2 appropriately.
30

---

Proof of Corollary I
We proceed by considering two cases. For each case, the proof consists of two steps. We first verify that the choices of the averaging parameter m and truncation threshold
1/8 N
y
N
d and
(54)
o,T
md'
satisfy the assumptions of Theorem namely n 2 C2rd and 7 2
My tr(x.)
We then invoke Theorem
F.1 Case high-noise regime
In this case, have (er
which means by setting m according Equation (54) we have
N
m 2 2. As a result, the bound
2
V2
N
12
N
7
2
(55)
(yt)²
d
(yt)2
d
holds in the high-noise regime.
Verifying the condition on n.
Recall that
We have
m
2
-
1/3
N ④ N
D
N
m
(y7)
)2
(v²)²
2
1/3
N2d
1/2
(u
v2
C2
p
1/2
(3/12
C2rd,
where step (i) is true by plugging in the choice of from
and applying the bound 555). and (54)
step (ii) is true by substituting in the assumption 20 2/2 2n
//ad. Thus the condition (2)))²
Card of Theorem iis satisfied.
Verifying the condition on т. For the term
N in the expression of 7 in note that, by
the previous point, m 2 rd (with constant that is greater than 1). Thus it suffices verify that
dm /r 1.
Therefore, to verify the condition 5 2
By tr(--f.
y!
(56)
Tpr
(2+)
By definition, we have y 2 py- Furthermore, since E' is symmetric positive semidefinite, its eigenvalues all non-negative and are identical to its singular values, and hence (E*) 2 d, verifying the condition (56).
Invoking Theorem By setting An, its lower bound in and substituting in N and our
choice of 5 from (44] we have
(v1)²
md
An Ci
(57)
Tr
N
31

---

Substituting this expression of An to the error bound from (54) to (57] and defining C' 3C C₁. we have
10
then substituting in our choice of m
tr ( 1Σ E' |F C
(0
())))
va
d
1/a
vF
Jrr
m
Using the fact that tr (E*) o1r. we have
Σ Ed S of (y))
(2))
d
1/3
///2
14
N
as desired.
F.2 Case low-noise regime
In this case, have (ØT)² A. which means by setting m according Equation (54) we have
m 1. As a result, no averaging occurs.
Because 1 in this case, have that N. By assumption, we have that N 2 C2rd, satisfying the condition n 2 C2rd in Theorem
Verifying the condition
Verifying the condition on T. By the same analysis in Case have that the condition
7 2 By in Theorem --
Invoking Theorem By setting An to its lower bound in
p
substituting in our choice of
from 144 and noting m = 1, we have
(2)) OrT
d
An = C1
1?
(58)
o,T
We define C' 3C C1 and note that under Case Substituting this expression of X in (58) the error bound (TO) then using the fact that under Case the bound v S (x+)2 N holds, we have
tr
(E*)
yt
rd N
E E" 5
V
orr
Uyy
Using the fact that tr (E*) Sir we have
of
y
r3d
| -
V
Fly
N
as desired.
32


Reviews:
[{"review_id": "BXNVYdY0g1", "reviewer": "Reviewer_Ehde", "summary": "This paper proposes to collect users' perceptual adjustment queries (PAQ) to capture change points in a semantic space. In contrast to ordinal and cardinal data, PAQ better aligns with human perception and is cheap to collect. PAQ can be used to learn the semantic space manifold by solving a row-rank optimization algorithm. The paper proposes theoretical guarantees accompanied by numerical results.", "questions": "The demonstration in Figure 2. looks very similar to embedding spaces of images. Have you considered using PAQ to learn the underlying embedding spaces for languages and images?", "limitations": "See \"weaknesses.\"", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. PAQ is conceptually novel, easy to collect, and aligns with human perception of concepts.\n2. The metric learning algorithm is straightforward and is backed with theoretical guarantees.", "weaknesses": "1. The paper does not provide a downstream use case for PAQ.\n2. Selecting the direction $a$ is challenging in high dimensions. \n3. The truncation trick in line 219 seems ad hoc to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions. We are delighted that you find our proposed query conceptually novel, well-motivated, and easy to implement. \n\n> The paper does not provide a downstream use case for PAQ.\n\nWe agree with the reviewer that a discussion of downstream use cases for PAQs would improve the paper. We emphasize that the PAQ is broadly applicable to many downstream tasks, but we keep the PAQ framework general from the perspective of query design in our presentation. In the global response, we highlight two examples of applications for which the PAQ is well-suited: querying for housing similarity and characterizing color perception.\n\n>  Selecting the direction a is challenging in high dimensions. \n\nWe agree that the problem of selecting an “optimal” query direction is extremely interesting, and presents an avenue for future work. We draw $a$ from the standard $d$-dimensional normal distribution, which means that the direction of $a$ is uniformly distributed in $\\mathbb{R}^d$. Due to the inverted nature of our measurements, it was not obvious that this choice of $a$ would allow us to perform consistent and theoretically justified estimation. However, we are able to design an estimator with this choice of $a$ and prove non-trivial theoretical bounds. In practice, selecting semantically meaningful directions in an active manner is an interesting line of future exploration. \n\n> The truncation trick in line 219 seems ad hoc to me.\n\nDue to the inverse quadratic term in Equation (6), the sensing matrices are heavy-tailed.\nAs a result, we utilize truncation to mitigate the effects of the heavy tail to ensure our measurements do not deviate “too far” from the probabilistically expected response. A similar technique has been shown to mitigate heavy tails when the truncation threshold is set carefully [FWZ21].\n \n> The demonstration in Figure 2. looks very similar to embedding spaces of images. Have you considered using PAQ to learn the underlying embedding spaces for languages and images?\n\nWe thank the reviewer for this suggestion. We consider an exploration of leveraging PAQs in learning representations an exciting and critical exploration of future work. We hope that by combining the advantages of cardinal and ordinal feedback, any representations learned from PAQ responses will inherit the strengths of representations learned solely from ordinal or cardinal feedback.\n\nWe emphasize that the PAQ is broadly applicable in a number of downstream applications, two of which we highlight in the global response.\n\n[FWZ21] J. Fan, W. Wang, Z. Zhu, “A shrinkage principle for heavy-tailed data: High-dimensional robust low-rank matrix recovery,” in the Annals of Statistics 2021."}, {"review_id": "MYySFMQFrk", "reviewer": "Reviewer_sAC6", "summary": " this paper introduces the Perceptual Adjustment Query (PAQ) mechanism for collecting human feedback in a cognitively lightweight manner, which combines advantages from both ordinal and cardinal queries. \nThe authors apply PAQs to the problem of  metric learning under a Mahalanobis metric.\n\n", "questions": "same as above. ", "limitations": "yes. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The introduction of the Perceptual Adjustment Query (PAQ) as a hybrid of ordinal and cardinal queries is a novel contribution. This mechanism offers the advantages of both query types.\n\n- The paper applies the PAQ scheme to the framework of metric learning for human perception. This application demonstrates the utility of PAQs in learning distance metrics and capturing similarities and dissimilarities in perceptual data.\n\n- The authors provide sample complexity guarantees and numerical experiments for the proposed estimator, which offer insights into the understanding of the PAQ-based approach.\n\n\n", "weaknesses": "\n1. The paper is based on the idea that the PAQ style of queries is more useful than ordinal or cardinal queries. But it is not clear how this can be tested. The paper would benefit from discussing potential real-world applications where the PAQ mechanism could be better than other relatedapproaches. This discussion would provide insights into the impact of the proposed approach.\n2. Similarly, I think the paper would benefit from exploring additional tasks other than Mahalanobis metric learning, \n3. Limited Evaluation: While the paper mentions ”extensive numerical simulations” to demonstrate the performance and properties of the estimator, it would be beneficial to provide more experimental results. Additional evaluation metrics and comparisons with alternative approaches would strengthen the paper's contributions. For example:\n- Apply this approach to tasks other than Mahalanobis metric learning ? \n- Comparison: The experiments focus solely on evaluating the PAQ-based metric learning method. Including a comparative analysis with existing approaches or baselines would provide a more comprehensive evaluation and further validate the proposed approach.\n- How is the data collected different from ordinal/cardinal queries? Can this difference be demonstrated experimentally? \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and feedback. We are grateful that you appreciate the advantages of PAQs and our sample complexity guarantees. \n\n> Limited Evaluation: While the paper mentions ”extensive numerical simulations” to demonstrate the performance and properties of the estimator, it would be beneficial to provide more experimental results. Additional evaluation metrics and comparisons with alternative approaches would strengthen the paper's contributions.\n\n> Comparison: The experiments focus solely on evaluating the PAQ-based metric learning method. Including a comparative analysis with existing approaches or baselines would provide a more comprehensive evaluation and further validate the proposed approach.\n\nWe have performed a new set of simulation experiments comparing PAQs against two often used queries in metric learning: Triplets and binary comparisons (please see the global response and attached PDF for full details). To summarize, PAQs drastically outperform these two alternative approaches, greatly reducing the number of queries needed to achieve a particular error level.\n\nThe numerical simulations that we presented in the paper are exactly as noted: to verify our theoretical results. We view this paper as one that 1.) formalizes the query and 2.) establishes a theoretical foundation in an important area that highlights novel technical challenges that arise when working with a new query paradigm. We see user studies as an important avenue for future work. \n\n> The paper would benefit from discussing potential real-world applications where the PAQ mechanism could be better than other related approaches. This discussion would provide insights into the impact of the proposed approach.\n\nWe agree with the reviewer that our paper would benefit from a prolonged discussion of real-world applications and plan on incorporating such a discussion in our revision. We emphasize that the PAQ is broadly applicable to many downstream tasks, and highlight two such examples for which the PAQ is well-suited in the global response: characterizing color perception and querying for housing similarity.\n\n> Similarly, I think the paper would benefit from exploring additional tasks other than Mahalanobis metric learning, \n> Apply this approach to tasks other than Mahalanobis metric learning ? \n\nWe emphasize that we purposely chose to limit the scope of this work to Mahalanobis metric learning precisely due to the unique and novel technical challenges it poses from a theoretical perspective. Because metric learning can be applied to a myriad of applications (see global response for an non-exhaustive list), many works in this field are self-contained, focusing only on metric learning. However, in our revision, we will include descriptions for how to apply PAQs to different settings and tasks.\n\nSpecifically, as mentioned in the global common response, the focus on metric learning allows us to bring two novel problem to the high-dimensional statistics and low-rank matrix sensing communities: the un-studied inverted measurement scheme and estimator design under simultaneously heavy-tailed and bias-inducing sensing matrices. We present, to the best of our knowledge, the first estimator that under these novel problem settings. \n\n> How is the data collected different from ordinal/cardinal queries? Can this difference be demonstrated experimentally?\n\nThe user’s response to a PAQ is the item along the path where the transition from similar items to dissimilar items occurs. This response is inherently much richer than ordinal query responses, which only reveal quantized similarity judgements (e.g., “Item A is more similar to the reference item than item B”). The PAQ response item can equivalently be viewed as a scaling of the query vector $a$. We note that while the response can be viewed as a scalar, it is inherently different from a cardinal response. PAQ responses are anchored to a reference object, thus providing context for users to make similarity judgments. This context is missing from cardinal queries, which ask for an absolute similarity rating (e.g., “On a scale from 1 - 10, how similar are these items?”), leading to issues such as miscalibration.\n\nWe demonstrate the effect of the different response types between PAQs and common ordinal queries in our new set of simulation results (please see global response and attached PDF)."}, {"review_id": "lbfEDlYBsO", "reviewer": "Reviewer_eVNV", "summary": "People evaluate things in two ways: scoring and comparing, which is the process of generating cardinal data and ordinal data. However, since different people have different scales, the cardinal data are more influenced by people's subjective perception, while the ordinal data are fundamentally limited and laces expressiveness because the comparison results are only for several things. Therefore, the paper introduces a new type of informative and yet cognitively lightweight evaluation mechanism for collecting human feedback. Specifically, by generating a series of consecutive items between two things, one progressively compares the reference item with other items, making cognitive judgments in a relative sense while identifying a transition point (similar vs. dissimilar) in the ranking.  Subsequently, the Mahalanobis distance metric learning model is proposed based on the above evaluation mechanism, where the model requires that the learned metric makes each reference sample as close as possible to its generated transition point. Moreover, the generalized error bound analysis of the proposed model is given. ", "questions": "1.  While novel ideas and theories are important, it is sufficient experimentation that will prove the value of the proposed method. It is recommended that sufficient experiments be added to the text to fully demonstrate the significance of the proposed model.\n2.  Comparison with existing metric learning and discussion are lacking, and it is suggested to add relevant literature descriptions to highlight the contribution of the proposed method.", "limitations": "The idea is novel, the model is simple, and it is suggested that the proposed method be extended to more complex multi-metric and deep metric learning models to enhance the usefulness of the proposed theory and model.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The idea of the paper is novel. The paper presents a novel query mechanism and uses it to propose an efficient and easily solvable metric learning model.", "weaknesses": "The idea of the paper is novel, however the experiments are very inadequate and not at all compared with any known metric learning algorithms. It is suggested to add comparative experiments with existing metric learning algorithms under different perspectives to fully illustrate the value of the proposed algorithm. Meanwhile, there are some expression and formatting problems with the paper. The details are as follows:\n1. Lack of description of existing relevant metric learning.\n2. There are major problems with the format of references, such as the lack of journal names and page numbers in some citations, as well as the problem of inconsistent cases between the paper name and the journal name.\n3 There are inconsistencies in expression or format. For example, “metric model” and “measurement model”, “In metric learning” and “In our theoretical results”.\n4 The usage of some symbols is inconsistent with the conventions of metric learning. For example, y often indicates a label in metric learning, there is a symbol with an arrow to indicate a constant that has not seen such usage, and there is a greater than or equal symbol with a wavy line that does not understand its meaning.\n5. There are some grammatical errors, please proofread carefully. For example, “such as in conducting surveys, grading assignments,…”should remove “in”, inconsistent case after the initial letter of the colon.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and feedback. We are grateful that you appreciate the novelty of our proposed query.\n\n>While novel ideas and theories are important, it is sufficient experimentation that will prove the value of the proposed method. It is recommended that sufficient experiments be added to the text to fully demonstrate the significance of the proposed model.\n\n>Comparison with existing metric learning … are lacking\n\n\nWe emphasize that the focus of this work is to provide fundamental understanding to the proposed new query type, as opposed to empirical improvement on certain tasks or datasets. We chose to limit the scope of this work to metric learning precisely to highlight these unique theoretical challenges, and provide solutions that are of independent interest to the statistics community. \n\nSpecifically, as mentioned in the global response, the focus on metric learning allows us to bring two novel problems to the high-dimensional statistics and low-rank matrix sensing communities: the un-studied inverted measurement scheme and estimator design under simultaneously heavy-tailed and bias-inducing sensing matrices. We present, to the best of our knowledge, the first estimator under these novel problem settings.\n\nTo further our fundamental understanding, we have performed a new set of simulation experiments comparing PAQs against two often used queries in metric learning: Triplets and binary comparisons (please see the global response and the attached PDF for full results). We show that PAQs drastically outperform the two baselines, greatly reducing the number of queries needed to achieve a particular error level.\n\n\n> Lack of description of existing relevant metric learning.\n\n> It is suggested to add relevant literature descriptions to highlight the contribution of the proposed method.\n\nMetric learning has a rich history in machine learning and signal processing, and we limit ourselves to discussing the literature that is most closely related to our contribution. In hindsight, we see that the choice of title for this subsection (“Metric learning”) may be overly broad, and will change it in a future revision to read “Mahalanobis metric learning”. In Section 1.2 (Related work), we describe existing work on Mahalanobis metric learning in detail, and concretely mention differences between our work and existing work.\n\nIf the reviewer has specific suggestions or examples of the type of description they would like to see in our paper, we would be happy to have a discussion centered around that.\n\n\n>There are inconsistencies in expression or format. For example, “metric model” and “measurement model”, “In metric learning” and “In our theoretical results”. \n\nWe thank the reviewer for pointing this out. We will do a thorough edit to ensure consistency in the camera-ready version.  \n\nThat said, we emphasize that:\n- The model of human perception (“metric model”) and the schema under which we collect responses (“measurement model”) are two distinct things. \n- Furthermore, “In metric learning” refers broadly to the field of metric learning, whereas “in our theoretical results” refers specifically to our estimator construction and analysis. \n\t- Such expressions (or slight variations) are commonly used in the literature. \n\t- For example, the phrase “in metric learning” appears in the abstract of a well-cited survey paper [Kulis13], whereas the phrase “in our theoretical analyses” appears in a foundational paper on low-rank matrix sensing [NW11]. \n\n>The usage of some symbols is inconsistent with the conventions of metric learning. For example, y often indicates a label in metric learning, there is a symbol with an arrow to indicate a constant that has not seen such usage, and there is a greater than or equal symbol with a wavy line that does not understand its meaning.\n\nWe will conduct a full review to iron out any notational issues.\n\nWe emphasize that:\n- We appreciate the reviewer bringing this up as a source of potential confusion and will consider changing notation for future drafts. \n- The notation $y$ was chosen due to its connection to the matrix sensing literature.\n\t- In particular, measurement values in matrix sensing literature of the form $y = \\langle A, \\Sigma^\\star \\rangle + \\eta$ is the standard. \n\t- Towards this end, we clearly define y in section 2.1\n- Assuming the symbol being referred to is $\\eta^\\uparrow$, this is defined on line 169 as the upper bound of the noise. This is referred to again in line 246, right before Theorem 1. Furthermore, the combined quantity $y^\\uparrow$ is defined in the Theorem statement and does not appear before this definition. We are happy to revise these quantities to be $\\eta^{max}$ and $y^{max}$ to avoid any unwarranted confusion.\n- We follow the standard statistics literature and use $\\lesssim$ and $\\gtrsim$ to compare the order of two quantities (defined in Appendix B on Page 13 for completeness).\n\n> There are major problems with the format of references, such as the lack of journal names and page numbers in some citations, as well as the problem of inconsistent cases between the paper name and the journal name.\n\n> There are some grammatical errors, please proofread carefully. For example, “such as in conducting surveys, grading assignments,…”should remove “in”, inconsistent case after the initial letter of the colon.\n\nThank you for bringing this to our attention. We will correct any reference inconsistencies and grammatical mistakes in the camera-ready version.\n"}, {"review_id": "qhUl0szEEF", "reviewer": "Reviewer_H5Pr", "summary": "This paper introduces perceptual adjustment query (PAQ), which combines cardinal reporting and ordinal reasoning using a sliding bar for relational questions through identifying the transition point (similar vs. dissimilar) along a continuum to the reference item. Formulating the problem as Mahalanobis distance learning in the feature space, this gives rise to a high-dimensional, low-rank matrix estimation problem. The authors propose two techniques including sample averaging and truncation to overcome challenges not present in classical low-rank matrix estimation problems and prove statistical bounds on the estimator error.", "questions": "1. What are the main contributions of this work? The authors claim both the proposal of the PAQ for the Mahalanobis metric learning and the solution to the associated matrix estimation problem in Section 1.1. Therefore, both should be validated quantitatively to make this work coherent and complete.\n\n2. The definition of the perceptual adjustment query in Section 2.2 does not seem to be dependent on a latent space associated with a item decoder/generator but only a feature space. Could the PAQ be applied to items solely within a feature space where a decoder/generator is not feasible, such as in the case of housing pricing similarity?\n\n3. The authors mention in Section 5 that they \"cross-validate to chose the constant factor.\" How to perform cross-validation in practice, given that only human responses and query vectors are available? Also, the boundary value y is set at 200, which seems to be an unusually large number. Although the actual value of y may not be critical due to the scale invariance property, the noise variance scales with y.\n\n4. The authors mention that they \"develop a two-stage estimator for metric learning from PAQs\". What are those two stages? From Algorithm 1, there seems to be only one stage.", "limitations": "The authors provide a discussion of limitations and potential societal impact in Appendix A.1 and A.2.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper studies the interesting problem of collecting more expressive and self-consistent human responses without heavy cognitive burden on users. The proposed PAQ method appears to achieve this by combining the advantages of both cardinal and ordinal queries. This gives a continuous way of constructing the tuplewise similarity queries [1]. And instead of asking for similarity, it asks for the transition point from similar to dissimilar. \n\n2. Thanks to the new approach for collecting human responses, the formulated Mahalanobis metric learning problem encounters several new challenges, including dependent noise and a heavy-tailed sensing matrix. To address these issues, the authors propose to leverage the averaging and truncation techniques. Both theoretical and simulation analyses demonstrate the efficacy of these methods.\n\n3. This paper presents a coherent structure and is easy to follow.\n\n[1] G. Canal, S. Fenu, and C. Rozell. Active ordinal querying for tuplewise similarity learning. AAAI 2020.", "weaknesses": "1. One major concern regarding this work is the lack of empirical validation for the proposed PAQ in real-world applications. The authors offer a conceptual explanation of its functionality and user interface design but fail to provide any implementation guidance. For instance, the practical implementation of the continuum remains unclear - should it be continuous or discretized? Moreover, the authors do not provide any synthetic tests or real human responses to support the claimed benefits or practical applicability of the proposed PAQ. The current validation relies solely on simulation results, which assess the theoretical analysis in relatively low-dimensional settings instead of truly high-dimensional scenarios.\n\n2. Another concern is the dependence of the proposed method on a pre-trained generative model that exhibits a linear latent space. This constraint limits the method's broad applicability compared to existing methods, such as tuplewise queries [1]. Also, many items generated along the line may be invalid in specific domains, such as molecules and proteins.\n\n3. The proposed solutions to the two challenges seem somewhat expected: averaging to reduce the variance and truncation to mitigate the heavy-tail issue have been commonly used in similar situations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and feedback. We are grateful that you appreciate the advantages of our proposed query and the writing of the paper.\n\n> What are the main contributions of this work?\n\nPlease see the global response for a detailed response. In summary, our paper has three main contributions: The PAQ, the measurement scheme that arises when applying PAQs to low-rank metric learning, and the resulting estimator and corresponding theoretical guarantees. We emphasize the latter two contributions are of independent methodological interest to the low-rank matrix estimation community.\n\n> The current validation relies solely on simulation results, which assess the theoretical analysis in relatively low-dimensional settings instead of truly high-dimensional scenarios.\n\n>The authors claim both the proposal of the PAQ for the Mahalanobis metric learning and the solution to the associated matrix estimation problem in Section 1.1. Therefore, both should be validated quantitatively to make this work coherent and complete.\n\nWe have performed additional experiments comparing PAQs against two often used queries in metric learning: Triplets and binary comparisons. For full results, please see the global response and the attached PDF. To summarize, PAQs drastically outperform the two baselines, greatly reducing the number of queries needed to achieve a particular error level.\n\n> The proposed solutions to the two challenges seem somewhat expected: averaging to reduce the variance and truncation to mitigate the heavy-tail issue have been commonly used in similar situations.\n\nWhile averaging and truncation has been used in other statistics problems, the employment of these techniques was not obvious for two reasons:\n\n1.) The proposed solutions are in response to the simultaneous occurrence of two problems: estimator bias and heavy-tailed design. To our knowledge, no work has addressed both of these problems simultaneously in the low-rank sensing literature, meaning our contribution of the average-then-truncate estimator is completely novel.\n\n 2.) The averaging step is utilized to ensure our estimator is consistent, not simply to reduce variance. If the averaging step is omitted, the estimation error remains bounded away from zero no matter how large N grows, i.e., the estimator without the averaging step is biased. \n\nConsidering practical points made estimator design even more challenging: We must design an estimator that does not impose any burdens at response time. To this point, both averaging and truncation steps are applied after collecting user responses, meaning no additional action is required from the user to ensure consistent estimation.\n\n> Another concern is the dependence of the proposed method on a pre-trained generative model that exhibits a linear latent space. This constraint limits the method's broad applicability...\n\nWe emphasize that the latent space of a generative model is an example setting, but the PAQ is not constrained to this setting. We analyze the PAQ under the case where the user traverses the continuous feature space in a linear manner, and define the query for this analysis setting. However, in practice, there is no requirement that the path of points presented to a user be a straight line. We consider designing informative paths as an interesting avenue for future work. \n\n> Could the PAQ be applied to items solely within a feature space where a decoder/generator is not feasible, such as in the case of housing pricing similarity?\n\nYes. We emphasize that the PAQ is broadly applicable, including the application of housing price similarity (see global response). The PAQ can be in a variety of settings, notably any continuous valued feature space.\n\n> One major concern regarding this work is the lack of empirical validation for the proposed PAQ in real-world applications. The authors offer a conceptual explanation of its functionality and user interface design but fail to provide any implementation guidance. For instance, the practical implementation of the continuum remains unclear - should it be continuous or discretized?\n\nIn practice, these details are left to practitioners to adapt to their specific use cases. However, we will be sure to include a broad discussion of potential practical details in our revision along with a detailed discussion of example use cases. \n\nTowards the specific point of discrete vs. continuous implementation, we note that the implementation can be either. We focus on the continuous case in the paper for analysis purposes, but note that discretizing the path of points can be viewed as a form of bounded noise (with discrete support) in our measurements, with the noise being bounded by the quantization level. Since our theoretical results only assume bounded noise, they cover this discrete setting too.\n\n> The authors mention in Section 5 that they \"cross-validate to chose the constant factor.\" How to perform cross-validation in practice, given that only human responses and query vectors are available? \n\nIn practice, one may perform (cross-)validation as follows. First, we collect responses from a human and split it up into a train/validation set. Then we apply our estimator to the training set, employing averaging and truncation, and solving the regularized optimization problem. We can then choose our hyperparameters to minimize validation error. Note that in this cross-validation procedure, we only use human responses and query vectors, i.e., no “ground-truth” is needed.\n\n> The authors mention that they \"develop a two-stage estimator for metric learning from PAQs\". What are those two stages? From Algorithm 1, there seems to be only one stage.\n\nThe two stages refer to 1.) preprocessing (i.e., averaging and truncation) and 2.) solving the regularized estimation problem. We will clarify this in the camera-ready version.\n"}]

Author rebuttal:
We thank the reviewers for their time and thoughtful feedback. The reviews especially recognized the novelty of the parametric adjustment query (reviewers Ehde, sAC6, eVNV, H5Pr) in combining “the advantages of both cardinal and ordinal queries” to alleviate cognitive burden on respondents while maintaining information richness.

Below, we address three common comments among the reviewers. Other comments are responded individually to the reviewer’s thread.

**Main contributions.** We emphasize three main contributions of the paper:
1.) The proposal of using parametric adjustment query (PAQ) for data collection
2.) The resulting inverted measurement scheme, and formulation of the low-rank matrix estimation problem with an unconventional construction of the sensing matrices, which arises when applying PAQs to metric learning.
3.) A novel estimator and corresponding theoretical sample complexity guarantees

In particular, we believe contributions 2.) and 3.) are of independent methodological interest, especially to the high-dimensional statistics community. The inverted measurement scheme, to our knowledge, is unstudied and poses several major technical challenges from an estimator design perspective. Namely, inverted measurements violate two key assumptions found in the standard matrix sensing measurement model: independent sensing matrices and noise, and “well-behaved” (non-heavy tailed) sensing matrices. Violations of these two assumptions result specifically in estimator bias. We take advantage of the specific properties of the estimation bias, namely that it scales with noise variance, to employ averaging in a way to reduce bias. In all, our estimator is designed specifically to address these technical challenges, and is of independent interest to the low-rank matrix sensing community.

**Comparison against other queries (Reviewers sAC6, eVNV, H5Pr).** We performed a new set of simulation experiments comparing PAQs against two other common query types in the case of learning a low-dimensional Mahalanobis metric. We compare against triplets (“given reference item A, which of items B and C are most similar to A?”) and binary comparisons (“Are items A and B similar?”) in both the noisy and noiseless settings, reporting normalized estimation error, and attach the associated results in our response PDF. We will update our camera-ready version with these experiments.

To summarize the results: In both the noiseless and noisy regimes, PAQ outperforms both common baselines substantially. For example, in the noisy regime with 800 responses, the normalized estimation error is
- PAQ: 0.18
- Triplets: 0.73
- Binary comparison: 0.96

**This is a drastic reduction in the number of samples needed to achieve good estimation error, demonstrating the power of learning from PAQ responses over established queries.**

**Downstream application of PAQs (Reviewers Ehde, sAC6, H5Pr).** We keep the PAQ framework general from the perspective of query design. We showcase the utility of PAQs on the widely-used metric learning problem, which has several applications, such as similarity learning, preference learning [XD20, CMVN22], classification [WS09, KHWRB12], and representation learning [JJN16]. When applied to metric learning, it can be incorporated with applications such as learning image embeddings. 

One example of a use case of PAQs for similarity learning is specifically mentioned by reviewer H5Pr: housing price similarity. As the user moves along the path, they see gradually changing features such as housing price, square footage, monthly fees and taxes, estimated repair costs, etc, to which they mark the first instance where they feel the house is no longer “worth it”. 

Aside from metric learning, PAQ can be used to elicit data for other human perception tasks. For example, one can study color perception to characterize color-blindness. For a user with red-green color blindness, we can present the user with an image of a red square and a sequence of points that slowly transitions from red to green, and ask them to drag the slider until they perceive a difference in colors. The answers to a set of PAQs would allow us to characterize how the user perceives colors and help tailor color correction for that user. We briefly mentioned this application along with others in Sec 6, and will include the above extended discussions in the longer camera-ready version. For example, for a user with red-green color blindness, we can present the user with an image of a red square and a sequence of colors that slowly transitions from red to green, and ask them to drag the slider until they perceive a difference in colors. In such a setting PAQs thrive by presenting users both with context (the full sequence of colors and the reference color) while eliciting a response that cuts to the core of what we want to learn: At what point can you start distinguishing colors? In this scenario, asking a user for ordinal feedback such as binary comparisons quantizes differences in color perception to the point where finding this transition point is difficult. On the other hand, asking users for a cardinal rating of color similarity is an extremely ill-defined task prone to the typical drawbacks of cardinal data elicitation, such as miscalibration and scale drift.

[XD20] A. Xu and M. A. Davenport, “Simultaneous Preference and Metric Learning from Paired Comparisons,” in NeurIPS 2020
[CMVN22] G. Canal, B. Mason, R. K. Vinayak, R. Nowak, “One for All: Simultaneous Metric and Preference Learning over Multiple Users,” in NeurIPS 2022
[WS09] K. Weinberger, L. K. Saul, “Distance metric learning for large margin nearest neighbor classification,” in JMLR 2009
[KHWRB12] M. Kostinger, M. Hirzer, P. Wohlhart, P. M. Roth, H. Bischof, “Large Scale Metric Learning from Equivalence Constraints,” in CVPR 2012
[JJN16] L. Jain, K. G. Jamieson, R. Nowak, “Finite sample prediction and recovery bounds for ordinal embedding,” in NeurIPS 2016

Meta-review: This paper introduced the Perceptual Adjustment Query (PAQ) as a hybrid of ordinal and cardinal queries which is well motivated by practical problems.  The authors propose two techniques including sample averaging and truncation to overcome challenges that do not present in classical low-rank matrix estimation problems and prove statistical bounds on the estimator error.  

The reviews collectively acknowledge the innovation of PAQ and the proposed approach.  There is also a nice theory about its statistical error estimation.   While certain reviewers expressed reservations regarding the limited experimentation and requested additional empirical evidence, the authors' response is notably convincing to me.  

Given these factors, I am inclined to recommend the paper for acceptance due to its inventive approach, solid theoretical underpinning, and the author's adept addressing of reviewer concerns.
Decision: Accept (poster)