Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
74,709 characters · 11 sections · 46 citation commands
Should Humans Lie to Machines? The Incentive Compatibility of Lasso and General Weighted Lasso
Rapid advances in machine learning methods for analyzing big data have given rise to automated systems that employ these methods to predict the best fitting outcomes for users based on their personal characteristics. For example, many online platforms try to predict which content - a song, a video, a post, or an article - is the best fit for each user. Medical providers have also begun using machine learning techniques to automate check-ups and test appointments for patients based on their medical history. Typically, these automated systems use data from past users to estimate a model that relates the best fit for a user (such as the most preferred content or the appropriate medical test) to her characteristics. These estimates are then applied to a new user's characteristics, which she discloses either actively or passively via her past online behavior (which may be reflected in her cookies or collected by her browser). Given the growing interaction of users with such automated systems, it is only natural to ask whether a user should truthfully disclose her characteristics?
If the information the user discloses is also used to exploit her (say, by providing it to third parties for advertising or price discrimination), then the user has an obvious reason not to reveal her private information. The question is whether special features of some popular machine learning methods introduce an incentive to misreport one's personal characteristics even when this information will be used solely for predicting her best outcome?\footnote{In a recent interview of Brian Christian, the author of The Alignment Problem, he notes that \textquotedblleft computers may one day be able not only to learn our behavior but also intuit our values - figure out from our actions what it is we're trying to optimize. ... What if an algorithm intuits the `wrong' values, based on its best read of who we currently are but not of who we aspire to be? Do we really want our computers inferring our values form browser histories? See shaywitz20 for this interview.} This question is of crucial importance:\ If individuals submit false reports to systems that rely on these reports for estimation and predictions, then the conclusions drawn from such estimates and predictions will be wrong and may lead to quite undesirable outcomes (e.g., think of an automated medical platform that schedules tests for patients based on false reports on attributes such as smoking, drinking and physical exercise).
To address the above question, we consider a stylized environment where each user $i$'s ideal option is a linear function $f$ of her privately observed attributes $X_{i}=(X_{i,1},...,X_{i,p})^{\prime}$ such that $f(X_{i} )=X_{i}^{\prime}\mathbf{\beta_{0}}.$ A user may not know the values of the coefficients $\mathbf{\beta_{0},}$ in which case she would have some (possibly degenerate) prior beliefs over them. A \textquotedblleft statistician\textquotedblright, who represents some automated prediction platform has a sample of the attributes of $n$ users and noisy observations on their ideal options. For instance, suppose $f(X_{i})$ is the optimal dosage of some medication when taken immediately at the onset of symptoms, conditional on the patient's medical history $X_{i},$ but the statistician observes the dosage that was given after some delay. Similarly, $f(X_{i})$ may be the mix of news and reality shows that a user with attributes $X_{i}$ actually watches, but the statistician observes only self reports by a user who may have forgotten exactly what he watched.
The statistician uses her sample to estimate the function $f$ by computing an estimate $\mathbf{\hat{\beta}}$ of the true coefficients $\mathbf{\beta_{0}}$. The statistician wishes to apply these estimates to predict the ideal option of a new user, $n+1,$ whose true attributes $X_{n+1}$ are not observed by the statistician. This new user must decide what vector of attributes $R(X_{n+1})\ $(which may differ from the truth) to report to the statistician.
In making this decision, the new user takes into account her beliefs about the statistician's sample (the new user only knows the distribution from which the sample is drawn, but she does not observe its realization), and her beliefs about the true parameters $\beta_{0}$. The statistician then plugs the new user's reported attributes into the estimated function and gives the user the option $R(X_{n+1})^{\prime}\hat{\beta},$ which is the statistician's estimate of the user's ideal option based her report. The new user's expected loss from a report $R(X_{n+1})$ is given by the mean square error between her expectation of the ideal option $X_{n+1}^{\prime}\beta_{0}$ and her assigned option $R(X_{n+1})^{\prime}\hat{\beta}.$ The statistician's estimator is incentive-compatible, if the new user has no incentive to deviate from truthful reporting whatever her attributes are, and for any prior belief on $\beta_{0}:$ I.e., if for every possible value of $\beta_{0}$ and $X_{n+1},$ the expected value of $(X_{n+1}^{\prime}\beta_{0} -R(X_{n+1})^{\prime}\hat{\beta})^{2}$ is minimized at the truth $R(X_{n+1} )=X_{n+1},$ where the expectation is taken with respect to the statistician's sample.
Intuition suggests that an individual cannot benefit from lying to a procedure that is meant to predict the best outcome for her. To counter this intuition, es2019, and es2020 use the above framework to illustrate that a user may have a strict incentive to lie about her attributes when the prediction is based on a linear regression that penalizes non-zero estimated coefficients. The rough intuition is that the user believes that despite the statistician's good intentions, these estimation techniques lead to distortions, which she tries to undo by lying. For instance, given the user's beliefs about the true model parameters, she may be concerned that the estimator will admit too many irrelevant attributes, and hence, she reports a zero value for these attributes (see es2019, and es2020 for more details). However, these papers focus on particular examples in which attributes are binary, the statistician has the same (fixed) finite number of observations on each possible combination of attribute values, and the penalty parameter is fixed and does not adjust to the sample size. That is, these papers only raise the problem of incentive compatibility but do not provide an econometric solution. Hence, they leave open the following important question: For a general environment, are there conditions ensuring that a penalized regression model is incentive compatible in large samples?
Answering this question can potentially allow platforms, like those discussed above, to use machine-learning methods to predict users' most preferred options without worrying that their data is \textquotedblleft contaminated\textquotedblright\ by non-truthful users. Put bluntly, estimates and predictions made by methods that are not incentive-compatible are possibly unreliable since they may be based on false data.
This paper addresses the above open question by first focusing on the most popular form of penalized regressions - the Lasso estimator.\footnote{Our results can be extended to apply to the debiased lasso estimator, but this involves a different proof technique, and hence, is beyond the scope of the current paper.} Borrowing tools from high-dimensional statistics, we establish sufficient conditions for incentive compatibility of the Lasso estimator in large samples. We show that to achieve incentive compatibility, the tuning parameter must be large enough (i.e., it must remain above some threshold as sample size increases) so as to avoid overfitting, which is the main reason why a user may want to lie (see Remark 2 in Section 4). This potential to lie implies that the standard way of choosing small enough tuning parameters to ensure consistency may violate incentive compatibility. We provide simulation results that illustrate how the tuning parameter can be chosen in practice to ensure incentive compatibility. Incentive compatibility may therefore be viewed as an additional important property that should be imposed on estimators on top of consistency and unbiasedness.
Next, we extend our results to a general weighted Lasso, also known as the \textquotedblleft Conservative Lasso\textquotedblright. ck18 develop this estimator as a data-dependent weighted penalized estimator. Conservative Lasso better differentiates between relevant and irrelevant variables, which results in better $l_{2}$ norm errors. The superior model selection properties of the Conservative Lasso (compared to the standard Lasso) is shown in ck18 analytically as well as in simulations. We characterize the conditions for ensuring the incentive-compatibility of the Conservative Lasso in large samples, and show this may require a higher (relative to the standard Lasso) lower bound for the tuning parameter under certain scenarios.
We also offer a new technical contribution by extending the oracle-moment-inequalities of jvdg18 from sub-Gaussian to i.i.d. data. Using a different proof technique, we derive less conservative bounds on the moments of the Lasso estimator and relax the bounded signal to noise ratio assumption in jvdg18. We also extend jvdg18 from Lasso moment estimation to generalized weighted Lasso (Conservative Lasso). It is shown that moment bound estimation results cover also this general class of penalty. These are all new results for general weighted Lasso.
The motivation to focus first on the Lasso estimator stems from the fact that this estimator is the benchmark among all high dimensional statistical estimators that predict large scale models when the number of regressors exceeds the sample size. Following its original proposal by tibshirani96, econometricians and statisticians have used Lasso-based estimators to push the boundaries of economics and finance. One of the most critical issues facing these Lasso type estimators is post-inference after estimation and model selection, which require uniformly valid confidence intervals. In a seminal series of papers, Belloni et al. (2012,2014) solved these issues by introducing the idea of \textquotedblleft partialling out\textquotedblright\ the regressors. A different, but complementary approach, via debiasing-desparsifying is proposed by van2014. ck18 extended the debiasing of van2014 to heteroskedastic-non-sub-Gaussian data with strong oracle optimality properties, thereby proposing a high dimensional estimator that is robust to heteroskedasticity, and with uniformly valid confidence intervals. Lasso-based debiasing are used in panel data models (see, e.g., cgst18, k16, kt19) and for addressing quantile treatment effects and text analysis (see, e.g., cs19 and c20).
The concern that statistical procedures such as estimation, forecasting and classification are vulnerable to manipulation, has been the subject of some recent papers in the computer science literature. In contrast to us, this literature assumes there is an explicit conflict of interest between the statistician and the data providers - either because the latter are concerned about their privacy, they have to incur a cost to provide a precise report, or they have a different objective than the statistician. These papers analyze the Nash equilibria of a game where users submit private values that are used for estimation/classification, and propose incentive schemes that induce truthful reporting. Some notable works in this literature include cdp15, cil15, dfp10, gvz15, hmpw16, mpr12 and pp04. None of these papers consider penalized regression methods, and none of them characterize conditions guaranteeing incentive compatibility of regression techniques when the statistician and users have aligned interests (as is the case in our model).
The remainder of the paper is organized as follows. Section 2 introduces our model and assumptions. Section 3 provides new oracle inequalities. Section 4 characterizes the sufficient conditions for ensuring that Lasso is incentive compatible in large samples. Section 5 extends these results to general weighted Lasso. Section 6 provides simulation results and Section 7 concludes. Appendix A contains the proofs of the results on the Lasso estimator when the number of regressors ($p$) exceed the number of observations ($n$). Appendix B addresses the case of $p\leq n$ and shows how to extend our Lasso resuls when we relax our assumption on the signal to noise ratio. Finally, Appendix C contains the proofs for the general weighted Lasso.
We begin this section by describing our theoretical framework and introducing our notion of incentive-compatibility. We then discuss the key ingredients of our model and conclude by laying out our assumptions on the statistician's data.
Throughout the paper we will use the following notational conventions. For any vector $\nu\in R^{d}$, let $\Vert\nu\Vert_{1},\Vert\nu\Vert_{2},\Vert\nu \Vert_{\infty}$ denote its $l_{1},l_{2},l_{\infty}$ norm respectively, and $\Vert\nu\Vert_{0}$ be the $l_{0}$ norm, which means the total number of nonzero entries. For a set $S\subseteq\{1,2,\cdots,d\}$, let $|S|=s$ be the cardinality of the set. Let $\nu_{S}$ be the modified $\nu$ such that we put 0 when the index does not belong to $S$ (i.e., say $S=\{1,2,6\}$ for a $10\times1$ vector $\nu$, this means that $\nu$ is modified such that now all elements are zero except elements $1,2,6$). Let $\Vert A\Vert_{l_{1}}$ be the maximum absolute column-sum norm of a matrix of dimensions $m\times l$, i.e., $\Vert A\Vert_{l_{1}}=\max_{1\leq k\leq l}\sum_{i=1}^{m}|A_{ik}|$ which is also called the induced $l_{1}$ norm of $A$. Let $\| A \|_{l_{\infty}}:= \max_{1 \le i \le m} \sum_{k=1}^{l} |A_{ik}|$ which is the maximum absolute row sum norm.
Our environment consists of users who are characterized by a set of $p$ personal characteristics. For instance, in the context of medical decision making, a characteristic can represent a risk factor (obesity, smoking, etc.). For each user $i,$ these characteristics are modeled as $p$ explanatory variables, $X_{i,1},...,X_{i,p},$ drawn from some distribution over a subset of $ \mathbb{R} ^{p}$. These attributes determine the ideal option for a user according to the function \[ f(X_{i,1},...,X_{i,p})=\sum_{k=1}^{p}X_{i,k}\beta_{0,k} \] This function applies to all users, who differ only in the values of their characteristics. The realized values of $(X_{i,1},...,X_{i,p})$ are privately observed by user $i.$ A user may or may not know the value of the coefficients $(\beta_{0,1},...,\beta_{0,p}).$ In the latter case, she has some (possibly degenerate) prior beliefs over their values.
A statistician (representing the automated prediction systems described in the introduction) has private access to a sample of $n$ observations. Each observation $i=1,...,n$ consists of the true attributes $X_{i}=(X_{i,1},...,X_{i,p})$ of user $i$ and a noisy signal $y_{i}$ of that user's ideal option,
where $u_{i}$ is random noise that is drawn $i.i.d$ from some distribution with zero mean.\footnote{Access to such observations is a necessary condition for any platform that tries to learn about users (say, Netflix, Spotify). In the introduction, we gave a couple of examples for such data, which may be obtained from a third party, or from marketing surveys.}
The $X_{i}$' s are also i.i.d. across $i$ and exogenous, and will be discussed in detail in Assumption (ref) in the next subsection. $\beta_{0}$ is a $p\times1$ vector, representing the true parameters in $f$. We let $S_{0}=\{j:\beta_{0,j}\neq0\}$ denote the set of relevant regressors with $s_{0}$ being the cardinality of the set $S_{0}$. (i.e., $s_{0}$ of the elements of $\beta_{0}$ are nonzero, and the rest are zero). $s_{0}$ is a nondecreasing function of $n$, and we assume $s_{0}\geq1$. These facts are known to an \textquotedblleft oracle\textquotedblright\ but not to the statistician (and possibly not to a user).
Using her (privately observed) sample, the statistician estimates the function $f$, or equivalently, she estimates the coefficients $\beta_{0,1} ,...,\beta_{0,p}$. When $p>n$, the least squares estimator is infeasible due to singularity of the empirical Gram matrix. Hence, the statistician uses Lasso, the penalized regression procedure that assigns costs to including explanatory variables in the regression. Specifically, she solves the following minimization problem
where $\lambda_{n}>0$ is the penalty (also called tuning parameter)\ that decreases with the number of observations at the rate of $\lambda_{n} =O(\sqrt{lnp/n})$ (an explicit expression for the sequence $\lambda_{n}$ is given in equation ((ref)) in Appendix A).\footnote{We established this rate in Lemma (ref) in Appendix A.}
Given her estimates $\hat{\beta},$ the statistician must take an action $a\in \mathbb{R} $ on behalf of a new user, $j=n+1$. This action is just the statistician's prediction of the ideal option of that user. The new user's payoff from action $a$ is $-(a-f(X_{n+1}))^{2}$, where $f(X_{n+1})$ is the true ideal option associated with her personal attributes $X_{n+1}$.
Since the statistician does not observe $X_{n+1},$ in order to make her prediction of $f(X_{n+1}),$ she asks the $n+1$ user to report a $p\times1$ vector, $R (X_{n+1}),$ which is interpreted as that user's attributes. The statistician then plugs $R (X_{n+1})$ into her estimated model and chooses the action $a=R (X_{n+1})^{\prime}\hat{\beta}.$ When the $n+1$ user decides what attribute values to report, she takes into account that she does not observe the statistician's sample, and hence, does not know the values of the estimated coefficients $\hat{\beta}.$ She only knows the distribution from which the statistician's sample is drawn, and that given her sample, the statistician chooses $\hat{\beta}$ according to ((ref)). Given this, the user chooses the report $R (X_{n+1})$ that minimize her expected loss $E_{\beta_{0},\hat{\beta}}(R (X_{n+1})^{\prime}\hat{\beta}-X_{n+1}^{\prime }\beta_{0})^{2},$ where the expectation is taken with respect to the user's prior beliefs about the true parameters $\beta_{0},$ and her beliefs about the estimate $\hat{\beta}.$ Hence, the new user may decide to lie and report $R (X_{n+1})\neq X_{n+1}.$ In particular, she may decide to \textquotedblleft opt out\textquotedblright\ and submit a vector of zeros.\footnote{In the case in which the individual's attributes are collected \textquotedblleft passively\textquotedblright\ from her browsing history, then reporting a vector of zero attributes can be interpreted as the act of deleting cookies.} Our objective is to understand under what conditions it is in the user's best interest to be truthful regardless of her prior beliefs on $\beta_{0}.$
To introduce our notion of incentive compatibility, consider a user who upon observing her vector of covariates decides which vector of values to report (which may differ from the true values). An estimator is said to be (ex-post) incentive-compatible, if for any vector of covariates, and for any belief over the true model parameters, the user's expected payoff from truthful reporting is at least as high as her expected payoff from any misreport, where the expectation is taken with respect to the statistician's sample.
Incentive compatibility means that the user is unable to perform better by misreporting her personal characteristics, regardless of her beliefs over the true model's parameters in mean squared sense.\footnote{If we were to relax the requirement that truth-telling is preferred for every prior belief over the true model's parameters, we would need to make some assumptions on the user's prior beliefs (see, e.g. Eliaz and Spiegler (2020)). Thus, our incentive-compatibility has the merit of being robust to any specification of prior beliefs.} How should we interpret this requirement, given that we do not necessarily want to think of the user as being sophisticated enough to think in these terms? One interpretation is that lack of incentive compatibility is merely a normative statement about the user's welfare - namely, given our model of how the statistician takes actions on the user's behalf, it would be advisable for her to misrepresent her personal characteristics. Furthermore, there are opportunities for new firms to enter and offer the user paid advice for how to manipulate the procedure - in analogy to the industry of \textquotedblleft search engine optimization\textquotedblright. Incentive compatibility theoretically eliminates the need for such an industry. In the context of the online content provision story, some misreporting strategies take the form of \textquotedblleft deleting cookies\textquotedblright. This deviation is straightforward to implement, and the user can check if it makes her better off in the long run.
Note that incentive-compatibility is not a property that can be tested statistically. To see this, suppose each user is characterized by only a single covariate that is uniformly distributed on $\{0,1\}.$ If users are truthful, then one would expect a 50-50 distribution of $0$'s and $1$'s in the population. However, if each user lies about his covariate, then one would also observe a 50-50 distribution of $0$'s and $1$'s.
Recall that the statistician's sample contains the true attributes of $n$ users. The idea is that the data on these users is obtained through a different process than the way the statistician obtains the data from the $n+1$ user. For instance, as mentioned earlier, this data may be obtained from a marketing survey where there is no incentive to lie. Alternatively, one may interpret our incentive compatibility requirement as a requirement that truth-telling is a Nash equilibrium among all participants - such that given that everyone else is telling the truth, no user has an incentive to lie.
To see that our definition of incentive-compatibility is not vacuous, simply add and subtract the term $X_{n+1}^{\prime}\hat{\beta}$ inside the squared brackets on the left side term of ((ref)), such that
Canceling common terms reduces incentive-compatibility to the following inequality:
Note that this inequality can go either way. For example, if all elements of the vectors, $\hat{\beta},$ $X_{n+1}$ and $\hat{\beta}-\beta_{0}$ are positive, and for every realized $R(X_{n+1})$, the difference $\tilde{X} _{n+1}-X_{n+1}$ is also positive, then incentive-compatibility holds. If, however, $\hat{\beta}-\beta_{0}<0,$ while all the other terms are positive, then incentive-compatibility may be violated. For instance, with one explanatory variable, a very small lie can lead to a very small positive number on the left hand side (due to a small lie being squared), while the right hand side may be positive and slightly larger. For our main result, we analyze the asymptotic version of incentive compatibility.
A weaker, ex-ante notion of incentive-compatibility considers a user, who prior to observing her covariates, commits to a strategy that maps every possible realization of the covariates to a (possibly non-truthful) report of these realized values. This notion fits situations in which the user either automates her reports to the statistician, or delegates the reporting to a third party. According to this notion, the estimator is ex-ante incentive-compatible if on average (over the different realizations of the user's covariates), the $n+1$ user has no incentive to misreport: \[ \int E[(R(X_{n+1})^{\prime}\hat{\beta}-X_{n+1}^{\prime}\beta_{0} )^{2}]dP_{X_{n+1}}\geq\int E[(X_{n+1}^{\prime}\hat{\beta}-X_{n+1}^{\prime }\beta_{0})^{2}]dP_{X_{n+1}}, \] where the integral is computed with respect to the distribution of the new user's attributes. Clearly, if an estimator is (ex-post) incentive-compatible, then it is also ex-ante incentive compatible. Thus, the sufficient conditions for (ex-post)\ incentive-compatibility of the Lasso estimator, which we establish in Section 4, also guarantee ex-ante incentive-compatibility. While ex-ante incentive-compatibility can be achieved with weaker conditions, the proof of these conditions follows from our proof of (ex-post) incentive-compatibility. In light of this, we shall focus on the ex-post notion henceforth.
In this subsection we discuss the motivation for some key ingredients of our model, and we also remark on the implications of making alternative modeling choices.
\noindentThe choice of the Lasso estimator. We chose to focus on Lasso because it is the most basic machine learning technique that engages in model selection. Since this is the first paper to ask, under what conditions are such techniques incentive-compatible, it makes sense to start with the most basic textbook technique. Once we understand whether and how to ensure incentive compatibility in the simplest penalized regression model, we move on to explore the weighted general penalized estimator (the Conservative Lasso) in Section 5.
Nevertheless, it is worth mentioning that Lasso has several desirable properties. First, its prediction error is of the same order of magnitude as if there were an oracle, who could make predictions based on the true model. This is shown in Theorem 6.4 and Corollary 6.3 of bvdg2011, who provide general oracle inequalities for convex loss with Lasso penalty. Second, jwht2013 shows (see p.26) that despite being less flexible than non-linear models such as random forests and deep learning, the Lasso estimator can prevent overfitting, which is clearly a major issue in out-of-sample contexts. In addition, Lasso is a continuous subset selection, which has good prediction properties as shown in p.61-69 of htf2011.
Since we also consider the Conservative Lasso in Section 5, we briefly mention its properties here. Conservative Lasso is a two-step algorithm, where in the first step, standard Lasso is run and all the variables are kept, and then in the second step, a general weighted algorithm is run to select and estimate the relevant variables. Conservative Lasso is therefore a general weighted version of Lasso: when all weights are equal to one in the penalty, it reduces to standard Lasso. Compared with the standard Lasso, the data-dependent penalties of the Conservative Lasso allow for better differentiation of relevant and irrelevant variables as seen in Lemma 1 of ck18. \footnote{The Adaptive Lasso is an alternative estimator that also uses a data-dependent weighted penalty (see zou06). However, in high dimensional econometrics, the first step of the Adaptive Lasso can cut off relevant variables, which can be undesirable as discussed in p.144-145 of ck18.} Further details on the Conservative Lasso will be provided in Section 5.
\noindentThe statistician's benevolence. Our paper addresses the issue raised in Eliaz and Spiegler (2019, 2020) that even if a statistician wants to make the best prediction for the user (so there is no a priori conflict of interest between them), the user may still have an incentive to lie because of the model selection component in Lasso (or any penalized regression for that matter), and because the user does not observe the statistician's sample. Since the source of lying in this no-conflict benchmark comes from the estimation procedure itself, the question is, how can we fix the procedure - without harming its estimation properties - so as to ensure truth-telling?
What if the user and the statistician did have a conflict of interests - say, the statistician uses the information that the user gives him in a way that may harm the user? Then obviously, the user will have an incentive to lie no matter which tuning parameter is chosen. In other words, in such an environment, Lasso (or any other estimator) will not be incentive-compatible unless the user is compensated, or the statistician uses an alternative estimation technique that is not optimal econometrically (say, he deliberately adds noise to it). Exploring this direction is clearly a separate research agenda.
\noindentThe user's loss function. As explained above, incentive-compatibility means that the user cannot profit by misreporting. Suppose the user had a generic loss function $g(\cdot)$, such that $Eg(R(X_{n+1}),X_{n+1})$ denoted the expected payoff of a user whose true characteristics are given by $X_{n+1}$, but she reports the values $R(X_{n+1})$. Then incentive-compatibility requires that $Eg(R(X_{n+1} ),X_{n+1})\geq Eg(X_{n+1},X_{n+1})$ for any realization of $X_{n+1}$ and for any report $R(X_{n+1})$. Note that in general, the user's expected payoff is completely independent of the statistician's loss function. However, without imposing any structure on $g(\cdot)$, it is impossible to characterize a condition that ensures the incentive-compatibility of Lasso.
Given our focus on the no-conflict-of-interests benchmark (which we discussed in the previous point), it is only natural to let the user and the statistician have the same loss function that measures how far (in expectation) the estimate is from the truth. For any loss function one chooses for the statistician, the user has no incentive to lie if the expected loss from lying (i.e., the distance between the predicted best outcome based on lying and the actual ideal outcome for the agent) is higher than under truth-telling. Hence, the definition of incentive-compatibility clearly extends to any loss function shared by the statistician and the user. Of course, for each candidate loss function one would need to find the exact sufficient condition. We chose to focus on the mean squared error since it is the most commonly used loss function.
If the user and the statistician evaluated the estimates using different loss functions, then the incentive compatibility condition will apply only to the user's loss function, and again, the precise sufficient condition for incentive-compatibility will depend on the specification of this function.
In this subsection, we introduce a number of restrictions on the statistician's data. To describe these restrictions, we shall make use of the following notations. Define an $l_{0}$ ball $\mathcal{B}_{l_{0}} (s_{0})=\{\Vert\beta_{0}\Vert_{l_{0}}\leq s_{0}\}$. Denote $\Sigma :=EX_{i}X_{i}^{\prime}$ for $i=1,2,\cdots,n$, let $\hat{\Sigma}:=X^{\prime }X/n$ be the sample counterpart, and let $\phi_{min}(\Sigma)$ denote the minimum eigenvalue of $\Sigma.$ Our first requirement extends the sub-Gaussian data assumption used in statistics:
Our second set of restrictions applies to the first and second moments. These will guarantee the consistency of the Lasso estimator, but will not ensure incentive compatibility (sufficient conditions for incentive compatibility will be introduced in Section 4). We start by defining the maximal value of certain cross products, which will be related to the behavior of moments in high dimensions in our next assumption.
\[ M_{1} := \max_{1 \le i \le n} \max_{1 \le j \le p} | X_{ij} u_{i}|, \]
\[ M_{2} := \max_{1 \le i \le n} \max_{1 \le j \le p } \max_{1 \le l \le p} | X_{il} X_{ij} - E X_{il} X_{ij}|. \]
Note that $M_{1}$ is the maximal covariance between the regressors and errors in a high dimensional context. Roughly speaking, when this covariance is small, it captures exogeneity of the regressors in the sample. $M_{2}$ is the maximal variance of the regressors in the sample. With large $p$ and $n$, these covariance and variance terms can grow arbitrarily large - hence, we need a condition that restricts the growth rate of their moments. Because we are allowing for heteroskedastic data and unbounded regressors, we need to consider the growth rate of higher-order moments. \footnote{Alternatively, we could provide primitives on Assumption (ref) using boundedness of individual moments of $X,u$.}
Assumption (ref)(i) and (ref)(ii) are standard in high dimensional econometrics. In particular, (ref)(i) is used in cck17 allowing them to apply a concentration inequality, and (ref)(ii) is a standard sparsity condition. Note that with Assumption (ref)(ii), Lasso prevents underfitting since letting $\lambda=O(\sqrt{\frac{lnp}{n}})$ implies that $s_{0}\lambda _{n}\rightarrow0,$ which ensures that $\lambda_{n}$ cannot be large enough to generate underfitting. This allows us to establish the consistency of Lasso in Lemmas A.1-A.3 in the Appendix.
Assumption (ref)(iii) ensures that the signal to noise ratio is bounded (see p.2343 of jvdg18). To see this, set $\sigma_{u}^{2}:=var(u_{i})$, the variance of the errors, such that $\sigma_{u}^{2}\geq c>0$, where $c$ is a generic positive constant that is weakly below the minimum eigenvalue of $\Sigma$ (which is positive by Assumption (ref)). Hence, when $E(u_{i}|X_{i})=0$, which is imposed in Assumption 1, \[ \frac{var(y_{i})}{var(u_{i})}=\frac{\beta_{0}^{\prime}\Sigma\beta_{0}} {\sigma_{u}^{2}}+1, \] However, \[ \frac{\beta_{0}^{\prime}\Sigma\beta_{0}}{\sigma_{u}^{2}}+1\geq\frac{\Vert \beta_{0}\Vert_{2}^{2}\phi_{min}(\Sigma)}{\sigma_{u}^{2}}+1. \] where $\phi_{min}(\Sigma)\geq c>0$. Hence, if Assumption (ref)(iii) holds, then the signal to noise ratio satisfies $var(y_{i})/var(u_{i})\geq C_{0} +1>0$, with $C_{0}$ being a positive constant, and defined as $C_{0} :=\frac{\Vert\beta_{0}\Vert_{2}^{2}\phi_{min}(\Sigma)}{\sigma_{u}^{2}}$.
The empirical implication of this is that only a fixed number of nonzero coefficients can be constants, and the other nonzero coefficients have to be local to zero. To see this implication, note that \[ \Vert\beta_{0}\Vert_{2}=\sqrt{\sum_{j=1}^{p}\beta_{0,j}^{2}}=\sqrt{\sum_{j\in S_{0}}\beta_{0,j}^{2}}=O(1). \] since in the case of $s_{0}$ growing with $n$ \[ \sqrt{\sum_{j\in S_{0}}\beta_{0,j}^{2}}=\sqrt{\sum_{j\in F_{1}}\beta_{0,j} ^{2}+\sum_{j\in S_{0}-F_{1}}\beta_{0,j}^{2}}\leq\sqrt{f_{1}C^{2}+(s_{0} -f_{1})\frac{C^{2}}{s_{0}-f_{1}}}=O(1), \] where $F_{1}:=\{j:|\beta_{0,j}|=C\}$ with $|F_{1}|=f_{1}$ being a fixed number, $C$ is a generic positive constant and $F_{2}:=\{j:|\beta_{0,j} |=\frac{C}{\sqrt{s_{0}-f_{1}}}\}$ with $|F_{2}|=s_{0}-f_{1}$. For ease of exposition, we set all coefficients in $F_{1}$ and $F_{2}$ to be the same constants, $C$ and $C/\sqrt{s_{0}-f_{1}},$ respectively. $F_{2}$ contains indices of all local to zero coefficients. This can easily be generalized without affecting our results.
In Appendix B we take a more flexible approach compared with Assumption (ref)(iii). There, we assume that $\Vert\beta_{0}\Vert_{2}=O(\sqrt{s_{0}} )$. In this case, all nonzero coefficients can be large (i.e., none of them are local to zero, as in set $F_{2}$ above). In other words, there is no index set $F_{2}$ as above, but all nonzero coefficients (their indices) are in the set $F_{1}$ above.
As $p$ and $n$ grow large, the total number of nonzero coefficients $s_{0}$ (also known as the sparsity index) can grow arbitrarily large. To guarantee consistency and unbiasedness, it is typically assumed that the product of the sparsity index and the tuning parameter should go to zero. However, this standard condition does not guarantee the incentive compatibility of the Lasso estimator as can be seen in the proof of Theorem (ref) below.
Oracle inequalities in high dimensional statistics are upper bounds on prediction and estimation errors. For our main result, we require moment bounds on the Lasso estimator's error in $l_{1}$ norm. By taking the sample size to be large, we can show that the upper bound on the mean of higher-order moments of Lasso estimation errors tend to zero. We then use this asymptotic result to establish the incentive compatibility of the Lasso estimator in large samples. To illustrate this, we note that from the proof of Theorem (ref) in Appendix (ref), the incentive compatibility constraint is tied to the following expression {
} For incentive compatibility to hold in large samples, we need the sum of the right-hand side terms to be greater than or equal to zero. The first term on the right-hand side ((ref)) is always non-negative. Hence, if we prove that ((ref)) and ((ref)) converge to zero, we establish asymptotic incentive compatibility. However, the size of terms in ((ref)) and ((ref)) will depend on the mean of higher-order estimation errors of Lasso.
To bound these errors, we prove new oracle inequalities, which are different from those that are given in the literature for $\Vert\hat{\beta}-\beta _{0}\Vert_{1}$. These inequalities will serve an important role in proving our main result in the next section (Theorem (ref)). They are also of independent interest as they extend previous results on sub-Gaussian data to heteroskedastic (conditionally) data sets that are commonly used in econometrics. Our proof technique will also consider a less conservative bound compared with jvdg18. Hence, our new inequalities contribute to the literature on high-dimensional econometrics where they can be used for proving generalized semiparametric efficiency of Lasso-type-estimators (as, e.g., in jvdg18).
Our first result in this section is a $k$-th moment bound for the $l_{1}$ norm of the Lasso bias. A key concept used in this result is the exception probability for the event $\mathcal{F}:=\{\mathcal{A}_{1}\cap\mathcal{A} _{2}\}$, where $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ are defined in ((ref)) and ((ref)), which represent the empirical process-noise, and the eigenvalue condition, respectively. The exception probability is the complement of the event $\mathcal{F}$, and is denoted by $P(\mathcal{F}^{c})$. An explicit upper bound for the exception probability is calculated in Lemma (ref).
If we set $k=1$ we can learn whether the Lasso estimator is unbiased. By the above Theorem, Assumption (ref) and ((ref)) imply $s_{0}\lambda _{n}\rightarrow0$. Hence, in large samples, we have unbiasedness in the large $\lambda_{n}$ case. Next, we provide the $k$-th moment bound for $l_{1}$ norm for the Lasso estimator.
This is a new result and a simple extension of Theorem (ref) above. The rate in Theorem diverges to infinity if $s_{0}\rightarrow\infty$ as $n\rightarrow\infty$.
Our first main result, which is new in the literature on penalized regressions, characterizes sufficient conditions for the Lasso estimator to be incentive-compatible for a sufficiently large sample size. In other words, we establish conditions such that when $n\rightarrow\infty,$ \[ E[R(X_{n+1})^{\prime}\hat{\beta}-X_{n+1}^{\prime}\beta_{0}]^{2}\geq E[X_{n+1}^{\prime}\hat{\beta}-X_{n+1}^{\prime}\beta_{0}]^{2}. \] for all $X_{n+1}^{\prime}$ and $R(X_{n+1})^{\prime}$ and for every $\beta_{0} $, where the expectation is taken with respect to the statistician's realized sample (since the reporting user does not observe this sample).
The proof of this result makes use of the following notation.
\[ M_{3}:= \max_{1 \le j \le p} | X_{n+1,j}|, \]
\[ M_{4}:\max_{1\leq j\leq p}|R(X_{n+1,j})-X_{n+1,j}|. \] Note that $M_{4}$ is the absolute magnitude of the potential misreport on a given variable $j$ by the $n+1$ user. Since we deal with ex-post incentive compatibility, $M_{3}$ and $M_{4}$ are deterministic but can grow with $n$. Hence, we allow $M_{3}$ and $M_{4}$ to be nondecreasing in $n$.
\noindentRemarks.
\noindent1. Theorem (ref) establishes that a sufficient condition for incentive compatibility is that the tuning parameter $\lambda_{n}$ needs to be large \textquotedblleft enough\textquotedblright. A simple way to choose $\lambda_{n}$ to satisfy ((ref)) is to use the upper bound of the exception probability \[ \lambda_{n}:=upperbound(P(\mathcal{F}^{c})^{1/8}), \] in Lemma (ref). The simulations in Section 6 address the issue of whether such a bound is feasible.
\noindent2. The typical concern with Lasso is the consistency of the estimator ($\Vert\hat{\beta}-\beta_{0}\Vert_{1}=o_{p}(1)$), which can be achieved by making sure that $\lambda_{n}$ goes to zero at a relatively fast rate (as Lemma (ref) in Appendix A shows, this rate is $s_{0}\lambda _{n}\rightarrow0$). However, if $\lambda_{n}$ gets too small, the Lasso estimator may admit many nonzero variables incorrectly (i.e., it creates an overfit). Consequently, when the number of regressors $p$ is very large, the expectation of the sum of $l_{1}$ errors ($E\Vert\hat{\beta} -\beta_{0}\Vert_{1}$) can grow arbitrarily large, and incentive compatibility may be violated. Put differently, consistency does not imply incentive compatibility in large samples. Thus, simply using the $l_{1}$ estimator bound on its own does not imply a bound for the expectation of $l_{1}$ error.
We illustrate the point with a simple example. Suppose we take a value for $\lambda_{n}$ below the upper bound in Theorem 1 (i.e., $\lambda _{n}<P(\mathcal{F}^{c})^{1/4k}/s_{0}^{1/2}$). In particular, take $\lambda _{n}=P(\mathcal{F}^{c})^{1/2k}/s_{0}^{1/2}$. Then from the proof of Theorem 1-((ref)) we obtain that \[ E\Vert\hat{\beta}-\beta_{0}\Vert_{1}^{k}=O(\lambda_{n}^{-k}P(\mathcal{F} ^{c})^{1/2}), \] But given our choice of $\lambda_{n}$, \[ \lambda_{n}^{-k}P(\mathcal{F}^{c})^{1/2}=[P(\mathcal{F}^{c})^{1/2k} /s_{0}^{1/2}]^{-k}P(\mathcal{F}^{c})^{1/2}=s_{0}^{k/2}\rightarrow\infty. \] Hence, even though there is consistency $(s_{0}\lambda_{n}\rightarrow0)$ under this $\lambda_{n}$ choice (see Remark 5), the moment bound estimation error is diverging. \[ E\Vert\hat{\beta}-\beta_{0}\Vert_{1}^{k}\rightarrow\infty. \]
Why is overfitting a significant issue for incentive compatibility? The intuition is as follows. Suppose the tuning parameter is sufficiently small so that given the user's prior on the true coefficients, she expects that many irrelevant variables will be included in the estimator. To correct this bias, she can report that these variables are equal to zero.
\noindent3. The second sufficient condition ((ref)) allows the distance between the user's report $R (X_{n+1})$ and the truth $X_{n+1}$ to be of any magnitude since $M_{4}\equiv\|R (X_{n+1})-X_{n+1}\Vert_{\infty}$ can be arbitrarily large. Since the above conditions are sufficient but not necessary, it remains an open question whether incentive compatibility can be achieved with a tuning parameter that is lower than the threshold in ((ref)) without restricting the magnitude of the deviation between the user's reported and true attributes.
\noindent4. Note that ((ref)) requires stricter sparsity than Assumption (ref). If $M_{3}=O(1)$ and $M_{4}=O(1)$, then condition ((ref)) amounts to $s_{0}^{3/2}\sqrt{\frac{ln\left( p\right) }{n} }\rightarrow0$, which is a sparsity requirement still stronger than Assumption (ref)(ii). In addition, if we let $M_{4}=O(ln\left( n\right) )$ and $M_{3}=O(ln\left( n\right) ),$ then $s_{0}^{3/2}\sqrt{\frac{ln\left( p\right) }{n}}(ln\left( n\right) )^{2}\leq4s_{0}^{3/2}\sqrt{\frac{ln\left( p\right) }{n}}\rightarrow0$ is needed to get incentive compatibility with $n\leq p$.
\noindent5. A natural question that arises is whether condition ((ref)) is compatible with the $l_{1}$ norm consistency of Lasso. In other words, consistency requires a small $\lambda_{n}$, but incentive compatibility requires a large $\lambda_{n}$, so are they compatible with each other? When we select a large $\lambda_{n}$ to satisfy incentive compatibility, we should not sacrifice consistency - i.e. we need $s_{0}\lambda_{n}\rightarrow0$. To verify whether this is possible, we can take the lower bound on the tuning parameter in ((ref)) and see whether we can achieve consistency. Note that
From ((ref)) in the Appendix, an upper bound on this exception probability is:
where $C_{1}$ and $K$ are positive constants. With $l=1,2$, it therefore follows from ((ref)) and ((ref)) that we need \[ s_{0}^{4}/p^{C_{1}}\rightarrow0,\quad s_{0}^{4}\max_{l}EM_{l}^{2} /nlnp\rightarrow0, \] to have consistency. These two conditions are not unreasonable in the sense that they are consistent with $\left( n,p\right) $ increasing to infinity. Also they are compatible with moments satisfying condition ((ref)) in Theorem 3.
\noindent6. Finally, note that $\lambda_{n}=O(\sqrt{\frac{ln\left( p\right) }{n}})$ represents an upper bound in terms of rates for $\lambda _{n}$, whereas ((ref)) represents a lower bound. We can then take for a positive constant $C>0$ \[ C\frac{\sqrt{ln(p)}}{\sqrt{n}}\geq\lambda_{n}\geq\frac{P(\mathcal{F} ^{c})^{1/8}}{s_{0}^{1/2}}. \] The question is, are there suitable combinations of $n$ and $p$ that satisfy these inequalities? By using algebra and the upper bound for exception probability ((ref)), we obtain the requirement that, \[ Cs_{0}^{1/2}\geq\left[ \frac{2n}{p^{C_{1}}}+\frac{K[EM_{1}^{2}+EM_{2}^{2} ]}{nlnp}\right] ^{1/8}\frac{\sqrt{n}}{\sqrt{lnp}}, \] which is plausible for $p>n$ and large $n$ since the left hand side may diverge and the right side may go to zero. This may be the case for example when $p$ is exponential in $n$, or large $C$.
\noindent7. When we relax Assumption 2(iii) to $\Vert\beta_{0} \Vert_{2}=O(\sqrt{s_{0}})$, the incentive compatibility is still satisfied but under the slightly stronger condition \[ s_{0}^{2}\sqrt{\frac{lnp}{n}}[M_{3}][M_{4}]\rightarrow0. \] The proofs are in Appendix B.2. Remarks 5-6 above still apply but with slightly stronger sparsity conditions.
\noindent8. While Theorem 3 provides sufficient conditions for incentive-compatibility, we can also derive a necessary condition. As we show in Appendix A, incentive-compatibility implies equation (A.52). By Markov's inequality, we obtain that if the Lasso estimator is incentive-compatibile in large samples, then \[ \left[ \sum_{j=1}^{p}(\hat{\beta}_{j}-\beta_{0,j})X_{n+1,j}\right] \left[ \sum_{j=1}^{p}(R(X_{n+1,j})-X_{n+1,j})\hat{\beta}_{j}\right] \overset {p}{\rightarrow}0, \] which implies a weighted consistency condition for the Lasso estimator. Note that a condition like ((ref)) is not involved, and hence, there is still a gap between our sufficient and necessary conditions. It remains a challenging open question whether there exist conditions for asymptotic incentive compatibility of Lasso that are both necessary and sufficient.
In this section we extend our analysis of incentive compatibility to a general weighted penalty function. ck18 propose the Conservative Lasso, which has superior model selection properties relative to the standard Lasso. This is achieved by using a data-weighted penalty function. Specifically, the Conservative Lasso is a two-step estimator \[ \hat{\beta}_{w}=argmin_{\beta\in R^{p}}\{\Vert Y-X\beta\Vert_{n}^{2} +2\lambda_{n}\sum_{j=1}^{p}\hat{w}_{j}|\beta_{j}|\}, \] where $Y=(y_{1},\cdots,y_{i},\cdots,y_{n})^{\prime}$ is an $n\times1$ vector, $X$ is an $n\times p$ matrix, and with the prediction norm for a generic vector $v$ defined as $\Vert v\Vert_{n}^{2}:=n^{-1}\sum_{i=1}^{n}v_{i}^{2}$. The weights $\hat{w}_{j}$ are defined as follows: for each $j=1,\cdots,p$ \[ \hat{w}_{j}=\frac{\lambda_{prec}}{|\hat{\beta}_{j}|\cup\lambda_{prec}}, \] where $\hat{\beta}_{j}$ is the Lasso estimator of Section 2 for variable $j$, and $\lambda_{prec}$ is a positive sequence defined in Lemma (ref) in Appendix C.
Roughly speaking, the Conservative Lasso may be viewed as giving excluded variables in Lasso a \textquotedblleft second chance\textquotedblright. For instance, when $\hat{\beta}_{j}=0$, the weight will be one (in contrast to a weight of infinity in Adaptive Lasso). When $\hat{\beta}_{j}>\lambda_{prec}$, the weight is less than one, so there is a differentiation of weights based on Lasso estimation in the first step. A formal argument for weight properties, and differentiation of relevant and irrelevant coefficients, is given in Lemma 1 of ck18. For problems with the Adaptive Lasso in high dimensional settings, see p.144-145 of ck18.
In order to analyze the incentive-compatibility of the Conservative Lasso, we will need the following assumption:
Assumption (ref)(i) is a major relaxation of the assumptions in Lemma A.7 of ck18 (where it is used to derive $l_{\infty}$ bounds for Conservative Lasso estimators) and in Lemma 4.1 of vdg16. These papers assume that the $l_{\infty}$ matrix norm of the precision matrix is constant, which is quite restrictive since in many realistic environments, the dimension of the matrix is $p\times p$ and its maximum row-sum can grow with $n$.
Assumption (ref)(ii) prevents the maximum absolute coefficient from being a sequence that is local to zero. A local to zero sequence for the maximum coefficient is unrealistic, and furthermore, it implies that all the coefficients in the model converge to zero, which renders the model useless to begin with. Assumption (ref)(iii) is needed for the minimum weights in the Conservative Lasso to be bounded above by 1 (as prescribed by ck18), which constraints the growth rate of $s_{1}$ in Assumption (ref)(i).
To the best of our knowledge, this is an entirely new result for general weight functions such as the Conservative Lasso. This extends a result of jvdg18 from Lasso with subgaussian data to Conservative Lasso with non subgaussian data. The proofs are not trivial and involve finding the rate for minimal estimated weight.
Note that the lower bound for the tuning parameter in Theorem (ref) may be weakly higher than the one in Theorem 1: if $s_{1}\leq\sqrt{s_{0}}$ \[ \frac{P(\mathcal{F}^{c})^{1/6k}}{s_{0}^{1/3}s_{1}^{1/3}}\geq\frac {P(\mathcal{F}^{c})^{1/4k}}{s_{0}^{1/2}}, \] since $s_{0}\geq1$. If, however, $s_{1}>\sqrt{s_{0}}$, then it is not clear which bound will be higher.
Our next result, which is also new in the literature, provides a moment estimator for the Conservative Lasso.
We are now ready to characterize the sufficient conditions for incentive-compatibility in large samples of the Conservative Lasso.
Remarks.
\noindent1. If our Assumption 3 imposed $s_{1}=O(1)$, as in ck18, then we would need a larger bound for the tuning parameter of the Conservative Lasso compared with Lasso. This follows from observing that under this restriction on $s_{1},$ \[ \frac{P(\mathcal{F}^{c})^{1/8}}{s_{0}^{1/2}}\leq\frac{P(\mathcal{F}^{c} )^{1/8}}{s_{0}^{1/4}s_{1}^{1/2}}. \]
\noindent2. A simple way to satisfy the lower bound for the tuning parameter is to choose \[ \lambda_{n}:={\mbox upperbound}\,(P(\mathcal{F}^{c})^{1/12}), \] by setting $s_{0}=1, s_{1}=1$.
\noindent3. A natural question that arises is whether a lower bound for $\lambda_{n}$ is compatible with consistency as in Remark 5 of Theorem 3. Applying the lower bound in Theorem 6, let \[ s_{0}\lambda_{n}=s_{0}^{2/3}s_{1}^{-1/3}P(\mathcal{F}^{c})^{1/12}. \] Using (11) with $l=1,2$ \[ \frac{s_{0}^{8}}{p^{C_{1}}s_{1}^{4}}\rightarrow0,\quad\frac{s_{0}^{8} max_{l}EM_{l}^{2}}{nln\left( p\right) s_{1}^{4}}\rightarrow0. \] Note that the same exercise with the second bound in Theorem 6 results in weaker conditions. These conditions are \[ \frac{s_{0}^{6}}{p^{C_{1}}s_{1}^{4}}\rightarrow0,\,\frac{s_{0}^{6}\max _{l}EM_{l}^{2}}{n(lnp)s_{1}^{4}}\rightarrow0. \]
\noindent4. Note that in a high dimensional penalized regression, the tuning parameter $\lambda_{n}$ is an upper bound on the noise as defined by $\mathcal{A}_{1}$ in (A.6). As in the case of Lasso (see Remark 6 following Theorem 3), we verify whether the lower bound for incentive-compatibility is compatible with the upper bound for noise reduction. Namely, we check whether \[ C\frac{\sqrt{ln\left( p\right) }}{\sqrt{n}}\geq\lambda_{n}\geq \frac{P(\mathcal{F}^{c})^{1/8}}{s_{0}^{1/4} s_{1}^{1/2}}. \] The question is, are there suitable combinations of $n$ and $p$ that satisfy these inequalities? By using algebra and the upper bound for the exception probability ((ref)), we obtain the requirement that, \[ Cs_{0}^{1/4} s_{1}^{1/2} \geq\left[ \frac{2n}{p^{C_{1}}}+\frac{K[EM_{1} ^{2}+EM_{2}^{2}]}{nlnp}\right] ^{1/8}\frac{\sqrt{n}}{\sqrt{lnp}}, \] which is plausible for $p>n$ since the left-hand side may diverge and the right-hand side may go to zero. For example, this may be the case when $p$ is exponential in $n$. If, instead, we were to use \[ C\frac{\sqrt{lnp}}{\sqrt{n}}\geq\lambda_{n}\geq\frac{P(\mathcal{F}^{c} )^{1/12}}{s_{0}^{1/3} s_{1}^{1/3}}. \] we would obtain the requirement that, \[ Cs_{0}^{1/3} s_{1}^{1/3} \geq\left[ \frac{2n}{p^{C_{1}}}+\frac{K[EM_{1} ^{2}+EM_{2}^{2}]}{nlnp}\right] ^{1/12}\frac{\sqrt{n}}{\sqrt{lnp}}, \] As before, this is plausible for $p>n$ since the left hand side may diverge and the right side may go to zero (e.g., when $p$ is exponential in $n$). Note that given that the upper bounds for $\lambda_{n}$ is the same, (see Lemma A.4 of ck18), the lower bound for Conservative Lasso is weakly higher than that of Lasso. Thus, the range of $(n,p)$ values that satisfy both bounds is smaller in Conservative Lasso.
\noindent5. We can also relax Assumption 2(iii) to $\Vert\beta _{0}\Vert_{2}=O(\sqrt{s_{0}})$. The analysis will be similar to that of Lasso (see Appendix B).
This section has three objectives. First, it illustrates how in practice the tuning parameter can be chosen to ensure incentive compatibility of the Lasso estimator. Second, it demonstrates that by appropriately choosing the tuning parameter (in line with the conditions in Theorem (ref)), incentive compatibility is analyzed through the lens of a small lie and larger lie. Finally, we show that incentive compatibility is not vacuous, it is possible to have new users lying to the machines and benefit from that.
We provide a simple simulation setup. Let \[ y_{i}=X_{i}^{\prime}\beta_{0}+u_{i}, \] where $\beta_{0}=(1,0_{p-s_{0}}^{\prime},1_{s_{0}-1}^{\prime})^{\prime}$, $0_{p-s_{0}}$ is a $p-s_{0}$ column vector of all zero elements, and $1_{s_{0}-1}$ is a $s_{0}-1$ dimensional column vector of all ones. Let $s_{0}$ represent the sparsity of the above model and set $s_{0}=5$.
In our design we introduce a multivariate normal distribution for the attributes of users $i=1,\cdots,n$, such that the covariance between the $j$ and $m$-th random variables are governed by \[ \Sigma_{j,m}=0.5^{|j-m|}, \] for $j=1,\dots,p$ and $m=1,\cdots,p$. Thus, the correlation between the adjacent random variables is 0.5, and this declines when the random variables are further apart. This Toeplitz type structure is commonly used in the high dimensional literature (see ck18). The new user has a draw from a $t$ distribution with three degrees of freedom. That new user's draw is deterministic-non-random. It is drawn from $t_{3}$ and that is kept fixed through the iterations so that we can compare between Lasso and Conservative Lasso. The results are presented in Tables 1-4. Tables 1-2 consider Lasso with a \textquotedblleft large\textquotedblright\ lie (the difference between the truth and the new user's report is 2 across all attributes) and with a \textquotedblleft small\textquotedblright\ lie (the difference between the truth and thel report is 0.2 across all attributes). Tables 3-4 consider the Conservative Lasso for the same setup.
For lasso, we aim to demonstrate that with a \textquotedblleft large\textquotedblright\ tuning parameter as in Theorem (ref), incentive compatibility can be achieved when the sample size $n$ is large enough. As mentioned in the previous section, one possible choice of a tuning parameter that satisfies Theorem (ref) is the upper bound on the exception probability, \[ \lambda_{n}\geq upperbound(P(\mathcal{F}^{c})^{1/8}). \] The issue is to make the exception probability, $P(\mathcal{F}^{c})$ operational and usable. Note that an upper bound on this probability is (with positive constants $C_{1}>0,C_{2}>0,K>0$)
by observing that for $l=1,2$
where we use Assumption (ref)(i). Hence, we can write the upper bound of the exception probability by using $p\geq1$ \[ \frac{2}{p^{C_{1}}}+\frac{C_{2}}{(lnp)^{2}}\leq2+\frac{C_{2}}{(lnp)^{2}}. \] The tuning parameter is as follows
where $C_{2}$ can start from a small positive value and stop at a large positive value. We select the values for $C_{2}$ and $\lambda_{n}$ according to the Generalized Information Criterion (GIC) as in Caner and Kock (2018), which gives consistent model selection with weighted Lasso choices in the least squares framework (the choice of tuning parameter with GIC in least squares with Lasso and Conservative Lasso is shown to be consistent in Theorem 5 of Caner and Kock (2018)). Note that the criterion for choosing the tuning parameter should take incentive compatibility into account. Hence, we choose only $C_{2}$ with GIC, but the structure of our tuning parameter is determined by our characterization of incentive compatibility. Therefore, our choice of $\lambda_{n}$ is above a lower bound, which prevents overfitting (this is the novel insight of Theorem (ref)). On the other hand, to prevent a very large $\lambda_{n}$ and ensure consistency of Lasso, the lower bound inversely depends on $p$.
Define
\[ \lambda_{n}^{\ast}:=argmin_{\lambda_{n}\in\Lambda}\left[ ln(\hat{\sigma} ^{2}(\lambda_{n}))+\frac{\hat{s}(\lambda_{n})}{n}ln(n)ln(ln(p))\right] , \] where $\hat{s}(\lambda_{n})$ is the number of nonzero elements in the Lasso estimator, given a choice of $\lambda_{n}$ in a grid $\Lambda$, and $\hat{\sigma}^{2}(\lambda_{n})$ is the mean squared residuals from the Lasso regression, given a choice of $\lambda_{n}$ in a grid $\Lambda$. We form $\Lambda$ as follows:\ we take $C_{2}$ in a grid of values $[2+\frac{C_{2} }{(lnp)^{2}}]$ as in ((ref)). Let $C_{2}:=[0.01,0.1,0.5,1,2,10,100]$, so $\Lambda$ is the grid of values of $\lambda_{n}$ depending on $C_{2}$. The number of iterations is 1,000.
For the Conservative Lasso, the same type of tuning parameter analysis is used, but with Theorem (ref), instead of Theorem 3. Hence, the tuning parameter choice for conservative lasso is:
The Choice of $C_{2}$ is done in the same way as in lasso above. The \textquotedblleft Report\textquotedblright\ column in Tables 1-4 display $E[R(X_{n+1})^{\prime}\hat{\beta}-X_{n+1}^{\prime}\beta_{0}]^{2}$ as the mean squared error from a false report by the user. \textquotedblleft Truth\textquotedblright\ refers to $E[X_{n+1}^{\prime}(\hat{\beta}-\beta _{0})]^{2}$. The difference between $R(X_{n+1})-X_{n+1}$ is kept at two levels: 2 and 0.2 (for all $p$ variables), which represent large, and small deviations from the truth. We have $p=100,200,300,$ and for each $p$ level we analyze $n=100,200,300$.
The numbers in each cell of the tables correspond to the disutility of the user (i.e., the mean square difference between the statistician's estimate and the optimal action). Hence, smaller numbers correspond to higher payoffs. Let us compare the tables when $p=300$ and $n=200.$ In Table 1, which corresponds to a large magnitude of a lie, the user's disutility from reporting the truth is 3.08, while the disutility from lying is 3.86. Hence, the $n+1$ user prefers to be truthful. In Table 2, for a small lie, truth-telling induces a disutility of 3.08, while lying induces a higher disutility of 2.04. Hence a lie is preferred. Thus, even with our lower bound, it is possible to profit from a \textquotedblleft small\textquotedblright\ lie. Note that some of the small lies are prevented by our lower bound as can be seen in $p=200$ with different $n$ in Table 1. So for small lies, guaranteeing incentive-compatibility is more difficult. However, as predicted, all large lies are prevented by our lower bound for the tuning parameter.
Tables 3-4 show the same pattern for Conservative Lasso. The lower bound on the tuning parameter prevents large lies, but dissuading small lies depend on $\left( p,n\right) $ combination. Also, when we move from small to large lie, the mean squared error from lying gets very large. This is evident by comparing Table 1 with Table 2, and comparing Table 3 with Table 4. To give an example, for Conservative Lasso with $p=100\ $and $n=100$, in Table 3 the new user prefers to lie with a mean squared error of 1.55 from lying compared to 2.49 from truth-telling. However, with a larger lie, the mean squared error from lying increases to 5.45 making it not profitable to lie.
The growing reliance on machine learning in automating decisions previously made by people raises the question of how people would interact with these automated systems. In particular, would people have an incentive to act strategically in order to manipulate such automated systems? This strategic interaction will become particularly important when these automated systems start playing a more prominent role in medical decision-making or even in driving.
This paper takes only a small preliminary step towards addressing this question by studying whether a user would want to lie to an automated system that uses Lasso or Conservative Lasso to predict that user's ideal outcome based on her reported attributes. Our main contribution is showing that truthful reporting can be ensured by appropriately adjusting the tuning parameter to be larger than what is required for consistency. Our result is also significant from a pure econometrics point of view: just concentrating on oracle inequalities and post-selection inference can lead to a small tuning parameter, which in turn, can lead to model overfitting, which then introduces an incentive to misreport. If users have an incentive to provide false input to algorithms used for estimation and prediction, then it is no longer clear that one can rely on the output of these algorithms.
\setcounter{equation}{0}\setcounter{lemma}{0}