Abusing Adderall or Ritalin has become more and more common among college students in the United States. This is because the ADHD drugs are amphetamine-like stimulants and they are often abused as so-called "study drugs," where students will take them to stay up longer to study before a test.
Some college students have begun taking modafinil, which is a eugeroic and is also known by brand names such as Alertec, Modavigil, and Provigil. This is a drug that is prescribed to people who suffer from narcolepsy. Narcolepsy is a disorder where a person struggles to stay awake during the day and often falls asleep during relaxing conditions. Physicians prescribe modafinil to people with narcolepsy because it helps them stay awake, which is likely why more and more college students are trying to get their hands on the drug. Although it is an alternative to an amphetamine, it still has a potential abuse and dependency.
Unfortunately, many young people who take ADHD medications or other prescriptions like modafinil do not consider they are abusing drugs or doing something wrong. There is a strong misconception among college students that it is perfectly fine or even normal to take other people's prescription drugs in order to get an extra boost. However, some people are pointing at colleges for creating an atmosphere where students have to be drugged in order to perform well enough. The fear is that these college students are falling into a trap that they will not be able to get out of, especially when test demands coincide with limited maturity and a "party" lifestyle. People can quickly find themselves seeking a chemical solution to every problem they have in life.
In addition to immediate and potential long term effects of modafinil, many experts feel it is important to point out that young people who use prescription drugs nonmedically are also much more likely to abuse other substances as well.
This entry was posted in Drug Abuse, Drug News, Prescription Drug Abuse and tagged modafinil, prescription drug abuse, prescription stimulant, study drug, Substance Abuse on July 20, 2016 by Desert Cove.


text:
Q: using "specialized" in a sentence I am a bit confused about how to use the word "specialized" in a sentence as in the following sentences:

*

*The courses he took in medical school, made him specialize in medicine.

*The courses he took in medical school, helped him to be specialized in medicine.
which one is correct? Or please suggest a better option.....
Please help....

A: In a medical context, you wouldn't normally talk about being "specialized in medicine". You'd be specialized in a specific branch of medicine such as oncology or paediatrics.
With regard to "specialize in" versus "be specialized in", both are fine but your second example comes across somewhat unnaturally. You might also consider "become specialized in".

A: Your sentences do not mean the same thing and so whether they are correct or not depends on what meaning you wish to convey:

*

*The courses he took in medical school, made him specialize in medicine.

means that those courses determined him to study medicine in a more specialized way, (maybe choosing a particular branch as suggested by the previous answer). See to make somebody do something

*The courses he took in medical school, helped him to be/become specialized in medicine.

means that the result of those courses is that now he is specialized. See to help somebody (to) do something

redpajama_set_name: RedPajamaStackExchange


text:
Q: Stop a Background Thread Gracefully I was task with implementing a background thread to do backend async processing with the twist being were certain cases where the job needed to be externally stopped.
I implemented it by wrapping everything within the Runnable in a try catch block and catch the InterruptionException, if caught the thread will simply return and exit.
Runnable task = () -> {
    try {
        while (true) {
            // do stuff

            // sleep for interval
            Thread.sleep(this.checkInterval);
        }
    } catch (InterruptedException ex) {
            // cleanup and exit
            return; // exit thread
    } catch (Exception ex) {
            // cleanup and exit
            return; // exit thread
    }
};

I'm using the ExecutorService SingleThreadExecutor and submitting the job like the following.
this.job = executorService.submit(task);

Then I am stopping the thread using
boolean canceled = this.job.cancel(true);

It seems to work fine since the cancel causes an InterruptionException if the thread is running.
Is this code safe, meaning when cancel is called its always guaranteed to kill the thread?

A: This approach might be OK, provided that your Runnable cooperates with it, and that the work that your Runnable performs can be safely interrupted at any time without causing problems such as inconsistent data.
Another common approach is to define a "running" flag within your Runnable, and set this to false when you want it to terminate. Your Runnable can then check this flag at a convenient and safe point in its processing (such as before each iteration of its main loop).
This approach might not terminate the task immediately, but it ensures that termination happens cleanly and without damage.
Any of these approaches require the cooperation of your Runnable - in general there is no way to safely and reliably terminate a Java thread without its cooperation.


It was 1972. Bruce Lee's early Hong Kong movies were showing up on tv in the states. "Enter the Dragon" would be released in 1973. "Kung Fu" was the hit tv show. "Billy Jack," a horrible movie with a wonderful sentiment and karate undertones, had been in the theaters. Americans were just starting to get a handle on this thing called Karate and Kung Fu.
Judo and Karate had been known for some time of course. But for some reason Judo seemed to be more in the American psyche. We saw things like James Bond practicing Judo and then knocking out villains with a chop ("Goldfinger"). But Judo doesn't really chop and Karate doesn't really throw.
I had tried Judo a few years earlier. It was a small school filled with large, grown men. Being a rather small kid, it did not fit with me very well at the time.
While Karate had been around for centuries it was starting to become popular in the U.S. and I was becoming aware of it myself.
One of the guys in my clique, Brewster, the ladies man as I have described him in other posts, was studying Karate. I expressed some interest so he invited me to tag along one Sunday. The instructor, Sensei James Logue, had been in the army and had just come back to the states after being stationed for several years in Okinawa. There he had trained under Taika Seiyu Oyata, and was the highest ranked Caucasian in Sensei Oyata's style.
We trained in a guy's backyard. There was no organization per se. It was all very old school. Sensei Logue did not even charge us. He did reserve the right to teach only who he wanted to teach. He looked me over for the six hours we worked that first Sunday and then told me I was "allowed" to come back. I was honored.
I trained under Sensei Logue for several years. He moved to another city where he set up a school. I trained there for a while eventually earning a brown belt in that style. But life became life. College, marriage, things like that, so I stopped training with him. But I did not give up my private practicing.
After some of that life stuff I ended up with a wonderful young child. At age nine he was in a little altercation at school. Nothing serious, the kind of thing that happens to every kid at some point. His mom, my first ex, decided he should take karate or something. She called around looking for a place that taught the stuff that Bruce Lee did.
The ex and I had been divorced for almost eight years at the time, the divorce having been finalized shortly after my child's first birthday. One of the agreements of the divorce was that I would visit with my child every single day. I would go over to my ex's house every evening and spend several hours with him. We would do homework or play games or watch tv together.
The martial art classes were offered in the early evening. That was my time with him so I figured, fine, I'll take him. Having some experience of my own but in a completely different style, I would sit and watch him. I would move and squirm wanting to help as my child worked with the instructor. Eventually the instructor suggested that I work with my child. Since they didn't teach children anyway, it would balance out the classes allowing the instructor to watch the class while providing someone for my child to work with.
Because of my prior experience, I took to the new art very quickly. It wasn't long before I was not only helping out my child but helping out other students as well. In a few years I was teaching, not as a job but as a hobby.
The instructor and his wife had long dreamed that they would someday do nothing but teach. The instructor owned a couple of muffler shops in the area. He and his wife worked them by day and taught and trained at night. They were saving and planning for the day they would open a real, official school. Tragically, the wife was killed in a motorcycle accident. The instructor was hit hard by this and I could tell he was about to pack it all up. He felt he couldn't do it all anymore.
I pulled him aside and said, "You are a good teacher. You cannot give up. You shouldn't. Be a black belt. Don't quit." He persevered.
I looked him square in the eye and said, "You f'ing idiot! Isn't that what you have always dreamed about? Call him back tomorrow and take the offer." He did and within a year he was laying plans to build a five-thousand square-foot martial arts facility. Eventually I was offered a paying job teaching and the rest is, as they say, history.
It all started with that first day with visions of David Carradine as Kwai Chang Caine, and Billy Jack, and Bruce Lee in my head and I was given the honor to come back.
I really liked this story. The picture honoring your first instructor was a great addition.
Being part Japanese, I have the greatest admiration for people that understand and live by honor.
All those names brought so many memories back of my Mom. She loved Bruce Lee movies, not to mention the other names in your story. She would buy the movies or TV series. Being German, she didn't really understand some of the plots but she loved the fighting.
My older brother took Kung Fu lessons and when my Mom took me to pick him up I would watch. It looked so cool but I am a big baby and hate to fall or get hit. Unfortunately when it came time for my brother to fight off several men (my brother was an adult by this time) he totally forgot what he learned.
So did you practice the Nunchaku? Not sure if that is spelled correctly. Oh, did you ever have to use your skills?
1. Nunchaku (Nunchucks to Americans): I have trained with them, and taught them. That said, they are useless weapon that belong only to movies. Originally the nunchaku was a farm tool – a rice thrasher.
2. Use of skills: As I teach martial arts, that would be one use. As for what you meant, I have been in 3 street altercations. In one I used the calm and clear thinking to evade the fight. In another I ran to a woman's defense and was able to stop the beating she was receiving while at the same time avoiding any blows with her attacker. In the last, I apprehended a shop lifter who used a snake as a weapon against me. (I guess that is a story I will have to write a post about.) I also "used my skills" as I helped to self-police the Occupy Columbia movement. All that said, I am certain that a great many altercations have been avoided because my training allows me to understand what combat is, and provides me with a presence and calm that drives me to find ways to diffuse, avoid, or evade.
Like anything in life, if you don't keep working it, using it, you lose it. If you snooze, you lose, as the old saying goes. While your brother forgot all of his techniques, if you ask him I imagine that he will tell you there was a calm or confidence in him that he can trace back to his Kung Fu training.
I'm glad you enjoyed the post. Thank you for reading and adding.


text:
\subsection{Our results}
\label{sec:intro:setup}
In this work, we focus on the simple yet prevalent case where the potential
outcomes are linear in the collected features (as in the housing market
disequlibrium example), with a residual (random) error term that is uncorrelated
across potential outcomes.
More precisely,
we consider a setting involving $n$ individuals
(observations) and $k$ potential outcomes (models). Each individual $i \in [n]$ has a feature
vector $\vec{x}^{(i)} \in \mathbb{R}^d$ and each model $j \in [k]$ has a vector of regression
parameters $\vec{w}^*_j \in \mathbb{R}^d$. Then, each individual with feature vector
$\vec{x}$ recieves a label for each outcome $j$ equalling
$\smash{y_{j} = \vec{w}_j^{* \top} \vec{x} + \varepsilon_{j}}$,
where $\vec{\varepsilon}$ is assumed to be an standard multivariate Gaussian random
variable. Our setting will involve self-selection bias arising from the fact
that every individual will only choose to reveal one of their labels,
$j_* \in \{1, \ldots, k\}$, as determined by some function of
that individual's full set of labels $y_{1}, \ldots, y_{k}$.
Our goal in this paper is to estimate the $k$ parameter vectors
$\vec{w}^*_1$, $\dots$, $\vec{w}^*_k$ under both the known-index and
unknown-index observational models.

We begin with our results in the known-index setting, which we formally define
in Definition~\ref{defn:index_observed}:
\begin{description}
  \item[Known-index Setting:] We observe $n$ samples
    $(\vec{x}^{(i)}, y^{(i)}, j_*^{(i)})$, where
    $j_*^{(i)} = S(y_{1}^{(i)}, \dots, y_{k}^{(i)})$, and
    $y^{(i)} = y_{j_*^{(i)}}^{(i)}$ for
    some known self-selection rule
    $S : \mathbb{R}^k \rightarrow \{1, \ldots, k\}$.
\end{description}
Here, we can estimate the unknown parameter vectors $\vec{w}^*_1$, $\dots$,
$\vec{w}^*_k$ to arbitrary accuracy and we allow for quite general
self-selection rules.
In particular, we allow the self-selection rule $S$ to be any
\textit{convex-inducing rule} (Definition~\ref{defn:convex-inducing}):
letting $\vec{y} \in \mathbb{R}^k$ be the vector of potential
outcomes, if we fix the $j$-th
coordinate $y_j$ for any $j \in [k]$, then deciding whether $j$ will be the
winner (i.e., whether $j_* = j$) is the same as
deciding whether $\vec{y}_{-j}$ belongs to some convex set (this convex set
can depend on $y_j$).
We formally define the self-selection rule in Definition
\ref{def:selfSelectionRule} and the convex-inducing self-selection rule in
Definition \ref{defn:convex-inducing}. Below we present an informal version of
our estimation theorem for the known-index case. The corresponding formal
version of the theorem can be found in Theorem \ref{thm:knownIndex}.

\begin{inftheorem}[Known-Index Estimation] \label{infthm:knownIndex}
  Let $(\vec{x}^{(i)}, y^{(i)}, j_*^{(i)})_{i = 1}^n$ be $n$ observations from
  the known-index self-selection model with $k$ linear models $\vec{w}^*_1$,
  $\dots$,  $\vec{w}^*_k$ as described in Section
  \ref{sec:intro:setup}. If the self-selection rule is convex-inducing and that the probability of observing each model is lower
  bounded by $(\alpha / k)$ for some $\alpha > 0$, then there is an estimation algorithm that outputs
  $\hat{\vec{w}}_1$, $\dots$, $\hat{\vec{w}}_k$ with
  $\norm{\hat{\vec{w}}_i - \vec{w}_i^*} \le \varepsilon$, when
  $n \ge \mathrm{poly}(d, k, 1/\alpha, 1/\varepsilon)$. Furthermore, the running time of the algorithm is
  $\mathrm{poly}(d, k, 1/\alpha, 1/\varepsilon)$.
\end{inftheorem}

The case of unknown-index is significantly more challenging and as we already
mentioned even the with infinite number of samples it is unclear if we have
enough information to estimate $\vec{w}_j$'s. We define the setting formally in
Definition \ref{defn:index_unobserved} and informally below:
\begin{description}
    \item[Unknown-index Setting:] We observe $n$ samples of the
    form $(\vec{x}^{(i)}, y^{(i)})$, where $\vec{x}^{(i)} \sim \mathcal{N}(0,
    \bm{I}_d)$, and
    $y^{(i)} = \max_{j \in [k]} y_{j}^{(i)}$.
\end{description}
Our first result below shows this
identifiability and its formal version is Theorem \ref{thm:identifiability_no_index}.

\begin{inftheorem}[Unknown-index Identifiability] \label{infthm:unknownIndex:identifiability}
    If we have infinitely many samples from the unknown-index
    setting, then we can identify
    all $k$ linear models $\vec{w}^*_1$, $\dots$, $\vec{w}^*_k$.
\end{inftheorem}

  Next we continue with finite-sample and finite-time algorithms for the
unknown-index case. To achieve this problem we need some separability assumption
between the $\vec{w}_i^*$.

\begin{infassumption}[Separability Assumption -- See Assumption \ref{as:no_index}] \label{infasp:separability}
    The separability assumption that we use is that the projection of any vector
  $\vec{w}^*_i$ to the direction of any other vector $\vec{w}^*_j$ cannot be
    larger that the norm of $\vec{w}_j^*$ (and in fact, must be at least
    $\Delta$ smaller).
\end{infassumption}

Our first result for arbitrary $k$ guarantees the estimation of the parameter
vectors $\vec{w}^*_i$ within accuracy $1/\mathrm{poly}(k)$. For a formal statement of
the theorem below we refer to Theorem \ref{thm:no_index}.

\begin{inftheorem}[Unknown-index Estimation -- General $k$ Case] \label{infthm:unknownIndex:general}
    Let $(\vec{x}^{(i)}, y^{(i)})_{i = 1}^n$ be $n$ observations from a
  self-selection setting with $k$ linear models $\vec{w}^*_1$, $\dots$,
  $\vec{w}^*_k$ as described in the unknown-index setting of Section
  \ref{sec:intro:setup}. If we also assume Informal Assumption
  \ref{infasp:separability} and that the probability of observing each model is
  lower bounded by $(\alpha / k)$ for some $\alpha > 0$, then there exists an estimation algorithm that outputs
  $\hat{\vec{w}}_1$, $\dots$, $\hat{\vec{w}}_k$ with
  $\norm{\hat{\vec{w}}_i - \vec{w}_i^*} \le 1/\mathrm{poly}(k)$, assuming that
  $n \ge \exp(\mathrm{poly}(k)) \cdot \mathrm{poly}(d, 1/\alpha)$. Furthermore, the running time of our
  algorithm is also $\exp(\mathrm{poly}(k)) \cdot \mathrm{poly}(d, 1/\alpha)$.
\end{inftheorem}

Finally, we study the case where $k = 2$ and show how to estimate the
parameters to arbitrary accuracy. For this we only need a more direct
separability assumption on the parameter vectors:

\begin{infassumption}[$k = 2$ Separability Assumption  -- See Assumption \ref{as:no_index:2}] \label{infasp:separability:2}
    The two weight vectors are separated in Euclidean distance, i.e.,
    $\norm{\vec{w}_1^* - \vec{w}_2^*}_2 \geq \Delta$.
\end{infassumption}

Under the above assumption we can recover the parameters efficiently: for the
formal version of  the informal theorem below we refer to Theorem
\ref{thm:no_index:2}.

\begin{inftheorem}[Unknown-index Estimation -- $k = 2$ Case] \label{infthm:unknownIndex:2}
    Let $\varepsilon > 0$ and $(\vec{x}^{(i)}, y^{(i)})_{i = 1}^n$ be $n$ observations from a
  self-selection setting with $2$ linear models $\vec{w}^*_1$, $\vec{w}^*_2$
  as described in the unknown-index setting of Section \ref{sec:intro:setup}. Under Informal Assumption \ref{infasp:separability:2}, there exists an estimation
  algorithm that outputs $\hat{\vec{w}}_1$, $\hat{\vec{w}}_2$ with
  $\norm{\hat{\vec{w}}_i - \vec{w}_i^*} \le \varepsilon$, assuming that
  $n \ge \mathrm{poly}(d, 1/\alpha, 1/\varepsilon)$. Furthermore, the running time of the
  algorithm is also $\mathrm{poly}(d, 1/\alpha, 1/\varepsilon)$.
\end{inftheorem}

\subsection{Our Contributions and Techniques} \label{sec:intro:contributions}
We initiate a line of work on attaining statistical and
computational efficiency guarantees in the face of structured self-selection
bias.

\paragraph{Known-index case.}
In the known-index case, we require $\mathrm{poly}(1/\varepsilon, k, d)$ sample and time
complexity to estimate all $k$ model parameters to accuracy $\varepsilon$ in $d$
dimensions, and can accommodate quite general selection criteria. To prove this
known-index result, we construct a log-likelihood-inspired objective function that has the true set of parameters as optimum. The key difficulty associated with this formulation is that unlike ``nice'' settings (for example, the data generating model belongs to an exponential family), the log-likelihood involves an integration over possible outputs of the \emph{unobserved} models. This scenario is reminiscent of latent-variable models where strong structural properties on the objective functions are uncommon. Nevertheless, we show that this objective function is \emph{strongly convex} where we crucially rely on the variance reduction properties of log-concave densities conditioned on convex sets. Our next goal is to run projected stochastic gradient descent (PSGD) on this objective function. Unfortunately, in contrast to standard settings in stochastic optimization, we do not have simple
access to unbiased stochastic estimates of the gradient due to the integrating out of the unobserved models in the objective function. Consequently, the gradient in this case involves sampling from the conditional distribution over outputs from the unobserved models given the observed sample at the candidate parameter set currently being considered. To sample from this conditional distribution, we show that a projected version of the Langevin Monte Carlo sampling algorithm due to Bubeck, Eldan and Lehec \citep{bubecksampling} mixes fast and produces an approximate stochastic gradient. Finally, we show that this
approximate stochastic gradient suffices for the PSGD algorithm to converge.
We provide the details of this algorithm and its analysis in Section
\ref{sec:known}.

\paragraph{Identification with unknown index.}
In the more challenging unknown-index case, it is not even clear whether the
parameters $\vec{w}_j$ are even \emph{identifiable} from the sample that we have. First, we show that this is in fact the case. Our proof uses an novel identification argument which we believe can be applied to other self-selection settings beyond the Max-selection criterion considered in this work. Formally speaking, we would like to exhibit the existence of a
mapping $f$ from $\Phi$ to the set of parameters $\vec{W}$ given access to the distribution function, $\Phi$, of the pairs $(\vec{x}, y)$ generated according to the self-selection model with unknown indices. Our construction of $f$ is based on a conditional moment calculation where we analyze the moments of $y$ conditioned on $\vec{x}$ lying in various one-dimensional subspaces. The main observation is that while closed form solutions are not known for the conditional moments, the higher order moments of $y$ still determine the length of the projection of the parameter vector with the largest projection along $x$. Concretely, we show that the higher-order moments of $y$ conditioned on $x$ being parallel to a unit vector $v$ are upper and lower bounded (up to constants) by the moments of normal distribution with $0$ and variance $\max_i (v^\top w_i)^2 + 1$. While a single direction does not uniquely determine any of the underlying parameter vectors, the direction maximizing this quantity over all one dimensional subspaces corresponds to the unit vector along the longest parameter vectors allowing recovery of \emph{one} of $k$ vectors. In the next step, we show that we may effectively ``peel off'' the single identified model from the distribution function, $\Phi$, reducing the problem of recovering the remaining parameter vectors to a self-selection problem with $k - 1$ parameter vectors. A recursive application of this argument allows identification of the remaining parameter vectors one by one.

\paragraph{Estimation with unknown index.}
  We then move our attention to estimation with finite time and samples. We target
the common $\max$-selection criterion and, under some separability assumption
among the $\vec{w}_j$'s, we provide an algorithm with
$\mathrm{poly}(d) \cdot \exp(\mathrm{poly}(k))$ sample and time complexity to estimate the
regression parameters up to error $1/\mathrm{poly}(k)$.
Our technique to prove these finite-time and finite-sample results is to try to
develop a finite accuracy version of our identifiability argument. Unfortunately,
this requires an exponential (in the ambient dimension $d$) sized grid search over the unit sphere. The traditional approach to address such difficulties is to restrict our search to a
suitably chosen $k$ dimensional subspace, $U$, identifiable from the data and
crucially \emph{contains} the parameter vectors, $\vec{w}_i$. We identify this
subspace through the spectrum of a suitably chosen matrix but we encounter an additional
\emph{key} difficulty, compared to the previous applications of this method. While
our choice of matrix, $M \triangleq \mathbb{E} [y^2 \vec{x} \vec{x}^\top]$, is natural, $M$ does not decompose into a independently weighted sum of matrices each corresponding to a single parameter vector, in stark contrast to the scenario encountered in simpler problems such as mixtures of linear regressions. Hence, showing that the top singular singular subspace of $M$
contains the $\vec{w}_i$ is significantly more involved and requires novel
approximation ideas. Despite these difficulties, we derive a closed form expression for $M$ as a (positively) weighted sum of the identity matrix, $I$ and outer products $\vec{w}_i (\vec{w}_i)^\top$ where the coefficients for a single parameter vector \emph{depend} on the other vectors. To obtain this closed form characterization, we replace the max function in the self-selection criterion with a \textit{smooth maximization} function resulting
in a matrix $M'$ approximating $M$ and analyze its spectrum through several careful applications of Stein's Lemma facilitated by the differentiability of the smooth maximization function. Applying a limiting argument to $M'$, we obtain the closed form characterization of $M$ and consequently, show that the span of the parameter vectors $\vec{w}_i$ is contained in the top-$k$ singular subspace of $M$ and the singular values associated with these directions are bounded away from those for the orthogonal complement establishing a strict spectral gap. Having identified the
low-dimensional subspace containing the $w_i$, we may now restrict our search to
this subspace. We conclude our estimation argument with a careful finite-sample
adaptation of our identifiability argument highlighted above.

\paragraph{Efficient estimation for $k=2$.} For the specific yet well-studied case of $k = 2$, e.g. \cite{fair1972methods}, we develop a estimation algorithm based on the method of moments that achieves estimation error $\varepsilon$ with  $\mathrm{poly}(d, 1/\varepsilon)$ time and sample complexity. It is an interesting open problem whether a similar procedure may be derived for the general case.
\medskip

\subsection{Related Work} \label{sec:intro:related}
\input{related}

\subsection{Objective Function for Linear Regression with Self-Selection Bias}
\label{sec:log_lik}

The objective function that we use is inspired by the log-likelihood function.
We show that our objective function is convex (even though linear regression with
self-selection bias does not belong to any exponential family). Suppose we have a
given parameter estimate for the $[\vec{w}_j^*]_{j=1}^k$ given by
$\bm{W} = [\vec{w}_j]_{j=1}^k$ then we define its objective value
$\overline{\ell}(\vec{W})$ as follows.
\begin{align}
    \overline{\ell}(\vec{W})
    &\triangleq
    \frac{1}{n} \sum_{i = 1}^n
        \mathbb{E}_{(y, j_*) \sim \mathcal{D}(\vec{x}^{(i)}; \vec{W}^*)}
        \left[ \ell(\vec{W}; \vec{x}^{(i)}, y, j_*) \right]  \notag \\
    &\triangleq \frac{1}{n} \sum_{i = 1}^n \mathbb{E}_{(y, j_*)} \left[
        \log\lr{f_{\sigma}(y - \bm{w}_{j_*}^\top \vec{x}^{(i)})} +
        \log\lr{\int_{C_{j_*}(y)} \prod_{j \neq j_*}
        f_{\sigma}(\bm{z}_j - \vec{w}_j^\top \vec{x}^{(i)})\, d\bm{z}_{-j_*} }
    \right] \label{eq:objectiveDefinition},
\end{align}
where we recall that $f_\sigma$ is the density function of the standard normal
distribution.
The above expression is based on the population
likelihood under the current estimate $\vec{W}$ of the pair $(y, j_*)$
conditioned on the value of $\vec{x}$: see Appendix
\ref{app:computationsLogLikelihood} for the exact derivation.
The gradient of $\overline{\ell}$ can then be expressed in the following form:
\begin{align}
    \label{eq:ll_grad_i:main}
    \nabla_{\vec{w}_j} \overline{\ell}(\vec{W}) &=
    \frac{1}{n\sigma^2} \sum_{i = 1}^n \Exp_{(y, j_*)} \left[
    \bm{1}_{j = j_*}
    \cdot y +
    \bm{1}_{j \neq j_*} \cdot
    \mathbb{E}_{\vec{z}_{-j_*} \sim \mathcal{N}((\vec{W}^\top x^{(i)})_{-j_*}, \sigma^2 \bm{I}_{k-1})}\left[z_j|\bm{z}_{-j_*} \in C_{j_*}(y)\right]
    - \vec{w}_{j}^\top \vec{x}^{(i)}
    \right] \vec{x}^{(i)}.
\end{align}
The first thing to verify is that the set of true parameters $\vec{W}^*$ are
a stationary point of the objective function that we proposed above. The
proof of the following lemma can be found in Appendix \ref{app:known}.

\begin{lemma} \label{lem:known:stationary}
  It holds that $\nabla \overline{\ell}(\vec{W}^*) = 0$, where
  $\bm{W}^* = [\bm{w}_j^*]_{j=1}^k$ is the set of true parameters
  of the known-index self-selection model described in Definition
  \ref{defn:index_observed}.
\end{lemma}
\begin{proof}
  See Appendix \ref{app:known:stationary}.
\end{proof}

Our goal is to apply projected stochastic gradient descent (PSGD) on
$\overline{\ell}$. To this end, we need to prove that our objective function is
actually strongly concave and hence the optimum of $\overline{\ell}$ is unique and
equal to $\vec{W}^*$. We show this strong convexity in Section
\ref{sec:convexity}. Next, we need to show that we actually apply PSGD and hence
need to find a procedure to sample unbiased estimates of the gradient of
$\bar{\ell}$. Unfortunately the form of the objective function does not allow us
to find such an efficient procedure. For this reason we relax our requirement to
finding approximately unbiased estimates of $\nabla \bar{\ell}$. To achieve this
we use a projected version of Langevin dynamics as we show in Section
\ref{sec:Langevin}. Additionally, we need to show that the second moment of our
gradient estimates cannot be very large which we also show in Section
\ref{sec:Langevin}. Finally, we need to adapt the proof of convergence of PSGD
to show that the small bias that Langevin dynamics introduces can be controlled
in a way that does not severely affect the quality of the output estimation
which we show in Section \ref{sec:biased_sgd}. In Section
\ref{sec:known:main:proof} we combine everything together to prove our
estimation result.

\subsection{Strong Concavity} \label{sec:convexity}

The Hessian of $\overline{\ell}$ is difficult to analyze directly. We thus start
with the Hessian of the log-likelihood for a single sample $(\vec{x}^{(i)},
y^{(i)}, j_*^{(i)})$. In particular, in Appendix
\ref{app:computationsLogLikelihood} we derive the Hessian of this function
$\ell(\vec{W}; \vec{x}^{(i)}, y^{(i)}, j_*^{(i)})$,
which comprises blocks $\bm{H}_{jl}$ such that
\[ (\bm{H}_{j,l})_{ab} = \ddt{(\bm{w}_l)_a}{(\bm{w}_j)_b} \ell(\bm{W};
\vec{x}, y, j_*). \]
Following the computation in Appendix \ref{app:computationsLogLikelihood}, it
follows that for a single sample $\vec{x}, y, j_*$, the matrix block
$\bm{H}_{j,j_*} = 0$ for all $j \neq j_*$. Thus, it remains to consider only the
blocks $\bm{H}_{j_*,j_*}$ and $\bm{H}_{j,l}$ for $j,l \neq j_*$. In Appendix
\ref{app:computationsLogLikelihood} we show that
\begin{align*}
  \bm{H}_{j_*,j_*} = -\frac{1}{\sigma^2}\vec{x}\vec{x}^\top
\end{align*}
and that
\begin{equation*}
  \bm{H}_{\vec{W}_{-j_*}} = \frac{1}{\sigma^4} \lr{
    \text{Cov}_{\bm{z}_{-j_*} \sim \mathcal{N}((\bm{W}^\top \vec{x})_{-j_*},\, \sigma^2 \bm{I}_{k-1})}
        \left[z_j, z_l\,|\, \bm{z}_{-j_*} \in C_{j_*}(y)\right]
    - \sigma^2 \bm{I}
  } \otimes \vec{x}\vec{x}^\top,
\end{equation*}
where $\otimes$ represents the Kronecker product. Now, the key property of
convex-inducing selection functions in our proof is that, for Gaussian random
variables over $\mathbb{R}^{k-1}$, the variance is non-increasing when the
variable is restricted to a convex set.

\begin{lemma}[Corollary 2.1 of \citep{kanter1977reduction}]
    Let $\vec{X} \in \mathbb{R}^n$ be a random vector with Gaussian density
  $f_{\vec{X}}$. For a convex set $A \subseteq \mathbb{R}^n$ with positive mass
  under the distribution of $\vec{X}$, define $\vec{X}_A$ to be $X$ restricted to
  $A$, i.e., a random variable with density
  $f_{\vec{X}_A}(\vec{x}) = f_{\vec{X}}(\vec{x}) \cdot (\int_{A} f_X(\vec{z})\, d\vec{z})^{-1}$.
  Then, for all $\vec{v} \in \mathbb{R}^n$,
  \[ \text{Var}[\vec{v}^\top \vec{X}_A] \leq \text{Var}[\vec{v}^\top \vec{X}]. \]
\end{lemma}

In particular, together with our thickness assumption and properties of the
Kronecker product, this implies that
$\bm{H}_{\vec{W}_{-j_*}} \preceq 0$. Thus, the complete Hessian of the
function $\ell$ can be expressed as a block matrix of the form:
\[ \bm{H}
    = \left[\begin{matrix}
        -\frac{1}{\sigma^2} \vec{x}\vec{x}^\top & \bm{0} \in \mathbb{R}^{d \times d(k-1)} \\
        \bm{0} \in \mathbb{R}^{d(k-1) \times d} & \bm{H}_{\vec{W}_{-j_*}}
    \end{matrix}\right]
    \preceq \left[\begin{matrix}
        -\frac{1}{\sigma^2} \vec{x}\vec{x}^\top & \bm{0} \\
        \bm{0} & \bm{0}
    \end{matrix}\right].
\]
We are now ready to upper bound the Hessian $\bm{H}_{pop}$ of our objective
function $\bar{\ell}$.
In particular,
at this point we can use our minimum-probability assumption
(Assumption \ref{asp:known:1}) and our thickness of covariates assumption
(Assumption \ref{asp:known:2}) from which we get that for the Hessian
$\bm{H}_{pop}$ it holds that
\[ \bm{H}_{pop} \preceq -\frac{\alpha}{\sigma^2 \cdot k} \bm{I}. \]
From the above we conclude that the following lemma

\begin{lemma} \label{lem:strongConcavity}
    The objective function $\bar{\ell}$ is
  $\left(\frac{\alpha}{\sigma^2 \cdot k}\right)$-strongly-concave.
\end{lemma}

\subsection{Approximate Stochastic Gradient Estimation} \label{sec:Langevin}
In this section we describe an algorithm for sampling approximate stochastic
estimates of our objective function $\bar{\ell}$. Our algorithm is based on
projected Langevin dynamics. We start with the expression of the gradient of
$\bar{\ell}$ based on \eqref{eq:ll_grad_i:main}.
\begin{align}
    \label{eq:ll_grad_i:main:2}
    \nabla_{\vec{w}_j} \overline{\ell}(\vec{W}) &=
       \frac{1}{n\sigma^2} \sum_{i = 1}^n \Exp_{(y, j_*)} \left[
       \bm{1}_{j = j_*}
       \cdot y +
       \bm{1}_{j \neq j_*} \cdot
       \mathbb{E}_{\vec{z}_{-j_*} \sim \mathcal{N}((\vec{W}^\top x^{(i)})_{-j_*}, \sigma^2 \bm{I}_{k-1})}\left[z_j|\bm{z}_{-j_*} \in C_{j_*}(y)\right]
       - \vec{w}_{j}^\top \vec{x}^{(i)}
       \right] \vec{x}^{(i)}.
\end{align}
where we remind that $\mathbb{E}_{(y,j^*)}$ denotes the expectation of the pair
$(y^{(i)}, j_*^{(i)})$ conditioned on $\vec{x}^{(i)}$ and $\vec{W}^*$.
To obtain stochastic gradient estimates, we will replace these expectations
with their
corresponding observed values as we will see below. The more difficult step of
the gradient estimation process is
sampling the last term of \eqref{eq:ll_grad_i:main:2}, for which
it suffices to be able to sample the truncated normal distribution
\begin{align}
  \mathcal{N}((\vec{W}^\top x^{(i)})_{-j_*}, \sigma^2 \bm{I}_{k-1};\ C_{j_*}(y))
  \label{eq:difficultTermToSample}
\end{align}
given some set of parameter $\vec{W}$, a vector of covariates
$\vec{x}^{(i)}$ and a pair $(y, j_*)$ drawn from
$\mathcal{D}(\vec{x}^{(i)}; \vec{W}^*)$. The simplest way to get a sample from
\eqref{eq:difficultTermToSample} is to first sample from
$\mathcal{N}((\vec{W}^\top x^{(i)})_{-j_*}, \sigma^2 \bm{I}_{k-1}),$
and then
apply rejection sampling until we get a sample inside $C_{j_*}(y)$.
This is feasible
information-theoretically but it might require a lot of computational steps if
the survival probability of $C_{j_*}(y)$ is small. In particular, the rejection
sampling might require time that is exponential in the norm of the $\vec{W}_j$'s.
For this reason, if we require statistical efficiency we need to apply a more
elaborate technique. In particular, we use projected Langevin
dynamics. Let $K = S_{j_*}(y) \cap \mathcal{B}(R)$ for some sufficiently large
constant $R$ and let $\vec{\mu}_{-j_*} = (\vec{W}^\top \vec{x}^{(i)})_{-j_*}$
for the rest of this section. The iteration of projected Langevin algorithm for
sampling
is the following \cite{bubecksampling}:
\begin{align}
  \vec{z}^{(t + 1)} = \Pi_K\left(\vec{z}^{(t)} - \frac{\gamma}{2 \cdot \sigma^2}
  (\vec{z}^{(t)} - \vec{\mu}_{-j_*}) + \sqrt{\gamma} \cdot \vec{\xi}^{(t)} \right) \label{eq:projectedLangevin}
\end{align}
where $\vec{\xi}^{(1)}, \vec{\xi}^{(2)}, \dots$ are i.i.d. samples from the
standard normal distribution in $(k - 1)$-dimensions. The next lemma describes
the sampling guarantees of the Langevin iteration \eqref{eq:projectedLangevin}.

\begin{lemma} \label{lem:samp_trunc}
    Let $L \subset \mathbb{R}^{(k - 1)}$ be a convex set with
  $\mathbb{P}_{\mathcal{N}(\vec{0}, \sigma^2 \vec{I})}(L) \geq \alpha$ for $\alpha > 0$.
  Then, for any $\vec{\mu}_{-j_*} \in \mathbb{R}^{k - 1}$ and $\epsilon \in (0, 1/2]$, the
  projected Langevin sampling algorithm \eqref{eq:projectedLangevin} with
    $K = L \cap \mathcal{B}(R)$ for some appropriate value $R$, and initialized
    with $\bm{z}^{(0)} = \Pi_K(\bm{0}_{k-1})$, generates a random
  variable $\hat{\vec{X}} = \vec{z}^{(m)}$ satisfying
    \begin{equation*}
        \mathrm{TV} \left(\widehat{\vec{X}}, \mathcal{N}(\vec{\mu}_{-j_*}, \sigma^2 \cdot \vec{I}_{k-1}, K)\right) \leq
        \epsilon
    \end{equation*}
  assuming that the number of steps $m$ is larger that
  $\mathrm{poly} (k, \norm{\vec{w}}, 1 / \epsilon, 1 / \alpha, \sigma^2, 1/\sigma^2)$.
\end{lemma}
\begin{proof}
The proof of this lemma can be found in Appendix \ref{app:lem:samp_trunc}.
\end{proof}
\smallskip

Now that we can sample from the distribution
\eqref{eq:difficultTermToSample}, we can move to approximately estimating a
stochastic gradient of $\overline{\ell}$. First, we sample uniformly $i \in [n]$a
uniformly at random, and we fix the corresponding $\vec{x}^{(i)}$. Then, we use
the $i$-th sample from the true model to substitute in the pair $(y, j_*)$.
Finally, we use the Langevin algorithm that we described above to sample
\eqref{eq:difficultTermToSample}. Before moving to bounding the bias of our
estimator there is one more thing that we need to take care of, and this is that
for every $\vec{x}^{(i)}$ we only have one sample of the pair $(y, j_*)$. Hence,
we need to make sure that during the execution of the algorithm while we pick
the indices $i \in [n]$ uniformly at random we will never pick the same
index $i$ twice. To ensure that we are going to require more samples than the
ones we need.

Let $n$ be the total number of samples that we have and $T$ be total number of
samples that we need for our PSGD algorithm. A straightforward birthday paradox
calculation
yields that the probability
of sampling the same $i$ twice is at most $2 T^2/n$. Thus,
if we pick $n \ge 2 T^2/\zeta$, then the collision probability
during the execution of the PSGD algorithm is at most $\zeta$.
\smallskip

We are now ready to put everything together in algorithm that
describes our combined estimation procedure. The following lemma whose proof be
found in Appendix \ref{app:lem:samplingGradient} describes the performance
guarantees of the above estimation algorithm.

\begin{algorithm}[t]
    \caption{Approximate Stochastic Gradient Estimation Algorithm}\label{alg:langevin}
    \begin{algorithmic}[1]
    \Procedure{EstimateGradient}{$\vec{W}$}
        \State sample $i$ uniformly from $[n]$
        \State $K \gets C_{j_*^{(i)}}(y^{(i)}) \cap \mathcal{B}(R)$
        \State $\vec{\mu} \gets (\vec{W}^\top \vec{x}^{(i)})_{-j_*^{(i)}}$
        \State $\vec{z}^{(0)} \gets \Pi_K(\vec{0})$
        \For{$t = 1,\ldots, m$}
            \State sample $\vec{\xi}^{(t-1)}$ from $\mathcal{N}(\vec{0}, \vec{I})$
            \State  $\vec{z}^{(t)} \gets \Pi_{K}\left(\vec{z}^{(t-1)} -
            \frac{\gamma}{2 \cdot \sigma^2} (\vec{z}^{(t-1)} - \vec{\mu}) +
            \sqrt{\gamma} \cdot \vec{\xi}^{(t-1)} \right)$
        \EndFor
        \For{$j = 1,\ldots, k$}
        \State $\vec{g}_j \gets \frac{1}{\sigma^2} \left(
        \bm{1}_{j_*^{(i)} = j} \vec{y}^{(i)} + \bm{1}_{j_*^{(i)} \neq j} \cdot
        z^{(m)}_j
          - \vec{w}_j^\top \vec{x}^{(i)}
          \right) \cdot \vec{x}^{(i)}$
        \EndFor
        \State \Return $\vec{g} = (\vec{g}_1, \dots, \vec{g}_k)$
    \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{algorithm}[t]
    \caption{Projected Stochastic Gradient Descent}\label{alg:psgd}
    \begin{algorithmic}[1]
    \Procedure{PSGD}{}
       \State $\vec{W}^{(0)} \gets 0$
       \For{$t = 1, \ldots, T$}
          \State $\eta_t \gets 1/\lambda \cdot t$
          \State $\vec{g} \gets \textsc{EstimateGradient}(\vec{W}^{(t)})$
           \State $\vec{w}^{(t)}_j \gets \Pi_{\mathcal{K}}\lr{\vec{w}^{(t)}_j
           - \eta_t \cdot \vec{g}^{(t)}_j}$ for all $j \in [k]$
       \EndFor
       \State \Return $\bar{\vec{W}} \triangleq \frac{1}{T} \sum_{t = 1}^{T} \left(\vec{w}^{(t)}_j\right)_{j = 1}^k$
    \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{lemma} \label{lem:samplingGradient}
    Let $\vec{g}^{(1)}, \dots, \vec{g}^{(T)}$ be a sequence of outputs of
  Algorithm \ref{alg:langevin} when used with input
  $\vec{W}^{(1)}, \dots, \vec{W}^{(T)}$, where
  $\norm{\vec{W}^{(p)}}_2 \le k \cdot B$ and $\vec{W}^{(p)}$ can
  depend on $\vec{W}^{(p - 1)}, \vec{g}^{(p - 1)}$. If $n \ge 2 T^2/\zeta$,
  for the hyperparameters $\eta$, $R$, it holds that
  $R, 1/\eta \le \mathrm{poly} (k, B, 1 / \beta, 1 / \alpha, \sigma^2, 1/\sigma^2)$, and $m \ge \mathrm{poly} (k, B, 1 / \beta, 1 / \alpha, \sigma^2, 1/\sigma^2)$
  then with probability at least $1 - \zeta$ it holds that for every $p \in [T]$
  \begin{align}
    \norm{\Exp \left[\vec{g}^{p} \mid \vec{W}^{(p - 1)}, \vec{g}^{(p - 1)} \right]  -  \nabla \bar{\ell}(\vec{W}^{(p)})}_2 \le \beta. \label{eq:boundOnBias}
  \end{align}
\end{lemma}

\subsection{Stochastic Gradient Descent with Biased Gradients}
\label{sec:biased_sgd}

  In the previous section we showed that we can compute approximate stochastic
gradients of the strongly-concave function $\bar{\ell}$. In this section we show
that this is enough to approximately optimize $\bar{\ell}$ using projected
gradient descent. We start with a description of the PSGD algorithm.

\begin{lemma}%
    \label{lemma:sgd}
    Let $f: \mathbb{R}^k \to \mathbb{R}$ be a convex function, $\mathcal{K} \subset
    \mathbb{R}^k$ a convex set, and fix an initial estimate $w^{(0)} \in \mathcal{K}$.
    Now, let $\vec{x}^{(1)}, \ldots, \vec{x}^{(T)}$ be the iterates generated by
    running $T$
    steps of projected SGD using gradient estimates
    $\vec{g}^{(1)}, \ldots, \vec{g}^{(M)}$
    satisfying $\mathbb{E}[\vec{g}^{(i)} | \vec{x}^{(i-1)}] =
    \nabla f(\vec{x}^{(i-1)}) + \vec{b}^{(i)}
    $. Let $\vec{x}_* = \arg\min_{\vec{x} \in
    \mathcal{K}} f(w)$ be a minimizer of $f$. Then, if we assume:
    \begin{enumerate}
        \item[(i)] \textbf{Bounded step variance:}
        $\mathbb{E}\left[\|\vec{g}^{(i)}\|_2^2 \right] \leq \rho^2$,
        \item[(ii)] \textbf{Strong convexity:}
        $f$ is $\lambda$-strongly convex, and
        \item[(iii)] \textbf{Bounded gradient bias:}
        $\|\vec{b}^{(i)}\| \leq
        \frac{\rho^2}{2\cdot \lambda\cdot \mathrm{diam}(\mathcal{K}) \cdot i},$
    \end{enumerate}
    then the average iterate $\hat{\vec{x}} = \frac{1}{T} \sum_{t=1}^T \vec{x}^{(t)}$
    satisfies
    $\mathbb{E}[f(\hat{\vec{x}}) - f(\vec{x}_*)]
    \leq \frac{\rho^2}{\lambda T}(1
    + \log(T))$.
\end{lemma}
\begin{proof}
    See Appendix \ref{app:bias_sgd_proof}.
\end{proof}

\subsection{Proof of Theorem \ref{thm:knownIndex}}
\label{sec:known:main:proof}
We are now ready to combine the results of the previous sections into a recovery
guarantee for $\bm{W}^* = \{\vec{w}_i\}$. In particular, we will apply Lemma \ref{lemma:sgd}
to show that Algorithm \ref{alg:psgd} converges to an average iterate $\hat{\vec{W}}$
that is close to $\bm{W}^*$.
First, observe that the norm of the gradient estimates outputted by Lemma \ref{app:lem:samp_trunc}
are bounded in norm by
\begin{align*}
    \mathbb{E}\left[\|v\|_2^2\right] \leq \mathbb{E}\left[
        \sum_{j=1}^k \left\| \nabla_{\vec{w}_j} \ell(\bm{W}; (\vec{x}, i, y)) \right\|^2
    \right] + \beta,
\end{align*}
where $\beta$ is as in Lemma \ref{lem:samp_trunc}.
Our bounds on the norm of the weights and covariates directly implies
\[
    \mathbb{E}\left[\|v\|_2^2\right] \in O\lr{k\cdot \text{poly}(B, C)} + \beta.
\]
Next, Lemma \ref{lem:strongConcavity} guarantees that $f$ in Lemma \ref{lemma:sgd} is
strongly convex with $\lambda = \alpha/(\sigma k)$.
Finally, Lemma \ref{lem:samp_trunc} ensures access to gradients with appropriately
bounded bias (i.e., satisfying assumptions (i) and (iii) in Lemma \ref{lemma:sgd})
in $\text{poly}(k, B, C, T, 1/\alpha, \sigma^2, 1/\sigma^2)$-time.
We are thus free to apply Lemma \ref{lemma:sgd} to our
problem---after averaging $T$ steps of projected stochastic gradient
descent, we will find $\bm{W} = \{\vec{w}_j\}_{j=1}^k$ such that
\begin{align}
    \label{eq:sgd_bound}
    \mathbb{E}[\overline{\ell}(\bm{W})] - \overline{\ell}(\bm{W}^*)
        \leq \frac{\sigma^2 \cdot k^2\cdot \mathrm{poly}(B, C)}{2\cdot \alpha\cdot T} (1 + \log(T)).
\end{align}
An application of Markov's inequality shows that, with probability at least $1 -
\delta$,
\[
    \overline{\ell}(\bm{W}) - \overline{\ell}(\bm{W}^*)
        \leq \frac{\sigma^2 \cdot k^2\cdot \mathrm{poly}(B, C, 1/\delta)}{2\cdot \alpha\cdot T} (1 + \log(T)).
\]
Thus, we can condition on the event in \eqref{eq:sgd_bound} while only losing a
factor of $1 - \delta$ in success probability. Finally, a parameter-space
recovery bound follows from another application of convexity:
\[
    \left\|\bm{W} - \bm{W}^* \right\|_F
        \leq \frac{\sigma^4 \cdot k^3\cdot \mathrm{poly}(B, C, 1/\delta)}{\alpha^2\cdot T} (1 + \log(T)).
\]

\section{Introduction}
    \label{sec:intro}
    \input{intro}

    \section{Model and Main Results} \label{sec:model}
    \input{setup}

    \section{Parameter Estimation for the Known-Index Setting} \label{sec:known}
    \input{known_index}

    \section{Parameter Estimation for the Unknown-index Setting} \label{sec:unknown}
    \input{unknown_index}

\section{Acknowledgements}
This work is supported by NSF Awards CCF-1901292, DMS-2022448 and
DMS2134108, a Simons Investigator Award, the Simons Collaboration on the Theory
of Algorithmic Fairness, a DSTA grant, the DOE PhILMs project
(DE-AC05-76RL01830), an Open Philanthropy AI Fellowship and a Microsoft
Research-BAIR Open Research Commons grant.

\printbibliography

\clearpage

\subsection{Known-Index Setting} \label{sec:model:knownIndex}

  We start with the definition of a self-selection rule that is fundamental in
the modeling of the linear regression problem with self-selection bias in the
known-index setting.

\begin{definition}[Self-Selection Rule] \label{def:selfSelectionRule}
  A \textit{self-selection rule} is a function
  $S: \mathbb{R}^k \to [k]$. We assume throughout this work that we have query
  access to $S$, i.e.  for every $\bm{y} \in \mathbb{R}^k$ there is an oracle
  that outputs $S(\bm{y})$.
  We also define a \underline{slice} $S_j(a)$ of $S$ as follows:
  \[
    S_j: \mathbb{R} \to \mathbb{R}^{k} \qquad
    S_j(a) \triangleq \{\bm{y} \in \mathbb{R}^k: S(\bm{y}) = j, \bm{y}_j = a\}.
  \]
\end{definition}

  The first setting that we consider is the \textit{known-index setting}, where
the observed data for each covariate include the response variable, as well as
the index of the corresponding regressor.

\begin{definition}[Self-Selection with Observed Index]
    \label{defn:index_observed}
      Self-selection with observed index is parameterized by an unknown set of
    weight vectors $\vec{w}^*_1,\ldots \vec{w}_k^* \in \mathbb{R}^d$, a known
    variance $\sigma > 0$,
    and a self-selection rule
    $S: \mathbb{R}^k \rightarrow [k]$. For $i \in [n]$, an observation
    $(\vec{x}^{(i)}, y^{(i)}, j_*^{(i)})$ in this model is a triplet, comprising
    a feature vector $\vec{x}^{(i)}$, and a pair $(y^{(i)},j_*^{(i)})$ sampled as
    follows conditioning on $\vec{x}^{(i)}$:
    \begin{enumerate}
        \item[(1)] Sample the latent variables $y_{j}^{(i)} \sim  \mathcal{N}(\vec{w}_j^{* \top} \vec{x}^{(i)},
        \sigma^2)$ for each $j \in [k]$.
        \item[(2)] Reveal the observation index $j_*^{(i)} =
        S(y_{1}^{(i)},\ldots,y_{k}^{(i)})$
        and the response variable $y^{(i)} = y_{j_*^{(i)}}^{(i)}$
    \end{enumerate}
    For a fixed $\vec{x}$ and $\vec{W}^*=(\vec{w}^*_1,\ldots \vec{w}_k^*)$,  we use $\mathcal{D}(\vec{x}; \vec{W}^*)$ to denote the
    probability distribution of the pair $(i, y)$ sampled according  to Steps (1) and (2) above. For example, if
    $S(y_{1}^{(i)},\ldots,y_{k}^{(i)}) = \arg\max_{j \in [k]} y_{j}^{(i)}$, then under
    this model we observe only the largest $y_{j}^{(i)}$ and its index. Our goal is
    to obtain an accurate estimate $\hat{\vec{w}}_j$ for each $\vec{w}^*_j$ given
    only samples from the above model.
\end{definition}

\noindent In most of this paper we are mainly concerned with estimating
the weights $\vec{w_1^*}$, $\ldots$, $\vec{w_k^*}$ from observation of the
covariates and the {\em maximal} response variable
\[y = \max_{j \in [k]}\ \{\vec{w_j}^\top \vec{x} + \bm{\varepsilon}_j\}, \qquad \text{
where } \bm{\varepsilon} \sim \mathcal{N}(0, \sigma^2 \cdot \bm{I}_{k}). \]
In the observed-index setting, however, it turns out that our efficient estimation
can be applied to a much larger set of selection functions $S(\{y_j\})$, which we
call {\em convex-inducing}.

\begin{definition}[Convex-inducing Self-Selection Function]
    \label{defn:convex-inducing}
    We call a self-selection function $S: \mathbb{R}^k \to [k]$ {\em
    convex-inducing} if, for each $j \in [k]$ and $a \in \mathbb{R}$, there
    exists a convex set $C_j(a)$ such that
    \[
        S_{j}(a) = \bm{1}\{\bm{y}_{-j} \in C_j(a)\},
    \]
    where $S_j(a)$
    are the slices defined in Definition \ref{def:selfSelectionRule}.
\end{definition}

Notably, setting $S(\bm{y}) = \arg\max_{j \in [k]} \bm{y}_j$ recovers the maximum-response
observation model, and this choice of $S(\cdot)$ also satisfies Definition
\ref{defn:convex-inducing} with $C_j(a) = (-\infty, a]^{k-1}$. The definition
also allows us to capture cases beyond the maximum; for example, convex-inducing
functions also include $S(\bm{y}) = \arg\max_{j \in [k]} f(\bm{y}_j)$ for any
monotonic function $f$.

In order for our estimation procedure to succeed we use the following assumptions
on the feature and parameter vectors which are classical even in many standard
linear regression instances.

\begin{assumption}[Feature and Parameter Vectors] \label{asp:known:1}
    For the set of feature vectors $\{\vec{x}^{(i)}\}_{i = 1}^n$ that we have
  observed we assume that:
  \begin{align} \label{eq:asp:known}
    \norm{\vec{x}^{(i)}}_2 \le C \quad \text{for all $i \in [n] \quad$ and } \quad \quad
    \frac{1}{n} \sum_{i = 1}^n \vec{x}^{(i)} \vec{x}^{(i) \top} \succeq \mathbf{I}.
  \end{align}
  For the true parameter vectors $\vec{w}_1^*$, $\ldots$, $\vec{w}_k^*$ we
  assume that $\norm{\vec{w}_j^*}_2 \le B$.
\end{assumption}

Although our theorem allows for a wide range of self-selection rules, we need some
additional assumptions that allow the recovery of every parameter vector
$\vec{w}_j$. To see why this is needed imagine the setting where the
self-selection rule $S$ is the $\argmax$ and for some $j$ the coordinates of
$\vec{w}_j$ are extremely small. In this case it is impossible to hope to estimate
$\vec{w}_j$ since there is a huge probability that we do not even observe one
sample of the form $y = \vec{x}^T \vec{w}_j + \varepsilon_j$. For this reason we need the
following assumption.

\begin{assumption}[Survival Probability -- Self-Selection Rule] \label{asp:known:2}
  For every sample $(\vec{x}, y, j_*)$ that we have observed,
  the following properties hold:
  \begin{itemize}
    \item[(i)] for every sample $\vec{x}^{(i)}$ and every $j \in [k]$, the
    probability that $j_* = j$ is at least $\alpha / k$ for some constant $\alpha$;
    \item[(ii)] the mass of the set $C_{j_*}(y)$ with respect to
    $\mathcal{N}((\vec{W}^{* \top} \vec{x})_{-j_*}, \sigma^2 \cdot \vec{I}_{k-1})$
    is at least $\alpha$.
  \end{itemize}
\end{assumption}

Finally, we need to assume oracle access to a self-selection rule $S(\cdot)$
that is convex-inducing, in the same sense introduced in Definition
\ref{defn:convex-inducing}:
\begin{assumption}[Self-Selection Rule] \label{asp:known:3}
  We assume that the self-selection rule $S: \mathbb{R}^k \to [k]$ is
  convex-inducing, and that for every $j \in [k]$ and $y \in \mathbb{R}$ we have access
  to the following:
  \begin{itemize}
    \item[(i)] a membership oracle for $S(y)$, i.e., for every
    $\vec{y} \in \mathbb{R}^{k}$ and $j \in [k]$, we can answer whether $S(\vec{y}) = j$
    or not, and
    \item[(ii)] a projection oracle to the convex sets $C_j(y)$ that correspond
    to slices $S_j(y)$ of the self-selection rule, i.e., for every
    $\vec{y} \in \mathbb{R}^{k}$ such that $\vec{y} \not\in S_j(a)$, we can efficiently
    compute the nearest vector $\vec{y}'$ such that $\vec{y}'_j$
      $\argmin_{\vec{s} \in S_i(y)} \norm{\vec{z} - \vec{s}}$.
  \end{itemize}
\end{assumption}

Using the above definitions and assumptions we are now ready to state our main
theorem for the known-index setting.

\begin{theorem}[Known-Index Estimation] \label{thm:knownIndex}
    Let $(\vec{x}^{(i)}, y^{(i)}, i^{(i)})_{i = 1}^n$ be $n$ observations from
  a self-selection setting with $k$ linear models $\vec{w}^*_1$, $\dots$,
  $\vec{w}^*_k$ as described in Definition \ref{defn:index_observed}. Under Assumptions \ref{asp:known:1}, \ref{asp:known:2}(i), and \ref{asp:known:3}(i),
  there exists an estimation algorithm that outputs $\hat{\vec{w}}_1$, $\dots$,
  $\hat{\vec{w}}_k$ such that with probability at least $0.99$, for every
  $j \in [k]$
  \[ \norm{\hat{\vec{w}}_i - \vec{w}_i^*}_2^2 \le \mathrm{poly}(\sigma, k, 1/\alpha, B, C) \cdot \frac{\log(n)}{n}.\]
  If we additionally assume the Assumptions \ref{asp:known:2}(ii), and
  \ref{asp:known:3}(ii), then the running time of the algorithm is
  $\mathrm{poly}(n, d, k, 1/\alpha, B, C, \sigma, 1/\sigma)$.
\end{theorem}

  In Section \ref{sec:known}, we explain our algorithm for proving Theorem
\ref{thm:knownIndex} and we describe the main ideas and techniques for the proof.
To construct an efficient algorithm we use an interesting combination of
projected gradient descent and the Langevin algorithm, after we develop an
appropriate objective function.

\subsection{Unknown-Index Setting} \label{sec:model:unknownIndex}

We next consider the more challenging {\em unknown-index} setting, where we have
sample access to the response variable, but do not observe the index of the
corresponding weight vector. In this more challenging setting, we make a few
additional assumptions on the structure of the problem, namely that the
covariates $\vec{x}^{(i)}$ are drawn from an mean-zero identity-covariance
Gaussian distribution (rather than being arbitrary); that the noise terms
$\vec{\varepsilon}^{(i)}$ are also identity-covariance (rather than $\sigma\cdot
\bm{I}_k$ for $\sigma > 0$); and that the self-selection rule is the maximum
response rule $S(\bm{y}) = \arg\max_{j \in [k]} \bm{y}_j$ (rather than an arbitrary
convex-inducing rule).

\begin{definition}[Self-Selection with Unknown Index]
    \label{defn:index_unobserved}
    Just as for Definition \ref{defn:index_observed}, we have a set of weight
  vectors $\vec{w}^*_1,\ldots \vec{w}^*_k \in \mathbb{R}^d$.
  We assume that vectors $\vec{x}^{(i)}$ are drawn i.i.d. from the standard
  multivariate normal distribution $\mathcal{N}(\vec{0}, \bm{I}_d)$. For
  each sampled covariate $\vec{x}^{(i)}$, we:
  \begin{enumerate}
    \item[(1)] Sample $y_{j}^{(i)} \sim \mathcal{N}(\vec{w_j}^{* \top}
    \vec{x}^{(i)}, 1)$ for each $j \in [k]$.
    \item[(2)] Compute the maximum response $y^{(i)} = \max_{j \in [k]} y_{j}^{(i)}$.
    \item[(3)] Observe only the covariate-response pair $(\vec{x}^{(i)},
    y^{(i)})$: in particular, we do not observe the index of the maximum
    response.
  \end{enumerate}
  Our goal is to obtain an accurate estimate $\hat{\vec{w}}_j$ for each
  $\vec{w}^*_j$ given only samples from the above model.
\end{definition}

This model resembles mixtures of linear regressions, with the key
difference being that in the latter, the index of the weight vector used for
each covariate is sampled i.i.d. from a categorical distribution with fixed
mixture probability. In contrast, here the probability of observing a response
from a given weight vector depends on both the covariate and the sampled noise
$\eta_i$.
\smallskip

  In this model it is not even clear that estimation of $\vec{w}^*_j$'s is
  possible:
indeed, our first result (Theorem \ref{thm:identifiability_no_index}) is an
information-theoretic one that shows (infinite-sample) identifiability for
unknown-index model.
To show this information-theoretic result, we use a novel argument that might be
of independent interest---we believe that it can be used to show the
identifiability of other statistical problems with self-selection bias as well.
The proof of the theorem below is presented in Section
\ref{ssec:identifiability}.

\begin{restatable}{theorem}{unknownidentify} \label{thm:identifiability_no_index}
    Let $\vec{W}^* = [\vec{w}^*_j]_{j = 1}^k \in \mathbb{R}^{d \times k}$ and
  $\Phi_{\vec{W}^*}$ be the distribution function of the pairs
  $(\vec{x}^{(i)}, y^{(i)})$ associated with the self-selection model with
  unknown indices as described in Definition~\ref{defn:index_unobserved}.
  Then, there exists a function $f$ satisfying:
  \begin{equation*}
    \forall~\vec{W}^* = [\vec{w}^*_j]_{j = 1}^k \subset \mathbb{R}^d ~ \text{it holds that} ~ f(\Phi_{\vec{W}^*}) = \vec{W}^*.
  \end{equation*}
\end{restatable}

\noindent In order to transform the above information-theoretic result to a
finite-sample and finite-time bound in the unknown-index case, we need the
following separability assumption among the $\vec{w}^*_j$'s.

\begin{assumption}[Separability Assumption] %
\label{as:no_index}
  For some known real values $B$, $\Delta$ it holds that:
\begin{equation*}
  \forall i \neq j: \frac{\abs*{{\vec{w}_i^{* \top} \vec{w}^*_j}}}{\norm{\vec{w}^*_j}} + \Delta \leq \norm{\vec{w}^*_j} \text{ and } \max_{j \in [k]} \norm{\vec{w}^*_j} \leq B.
  \tag{A} \label{eq:asump_no_index}
 \end{equation*}
\end{assumption}

\begin{theorem}[Unknown-Index Estimation]
    \label{thm:no_index}
    Let $(\vec{x}^{(i)}, y^{(i)})_{i = 1}^n$ be $n$ observations from a
  self-selection setting with $k$ linear models $\vec{w}^*_1$, $\dots$,
  $\vec{w}^*_k$ as described in the unknown-index setting in Definition
  \ref{defn:index_unobserved}. If we assume Assumption \ref{asp:known:2}(i) and
  Assumption \ref{as:no_index}, then there exists an estimation algorithm that
  outputs $\hat{\vec{w}}_1$, $\dots$, $\hat{\vec{w}}_k$ such that with
  probability at least $0.99$, for every $j \in [k]$
  \[ \norm{\hat{\vec{w}}_j - \vec{w}_j^*}_2 \le \varepsilon,\]
  as long as
  $n \geq \mathrm{poly} (d) \cdot \exp \blr{\mathrm{poly} (B / \varepsilon) \cdot \widetilde{O}(k)}$ and
  $\varepsilon \le \Delta/16$.
  Furthermore, the running time of the algorithm is at most
  $n \cdot \exp \blr{\mathrm{poly} (B / \varepsilon) \cdot \widetilde{O} (k)}$.
\end{theorem}

  Our estimation algorithm above only makes sense for $\varepsilon = 1/\mathrm{poly}(k)$ and
resembles the corresponding results of mixtures of linear regressions
\cite{li2018learning, chen2020learning}. What we are missing for this model is a
local analysis corresponding to \cite{kwon2020converges} that will enable us to
get error $\varepsilon$ with running time and number of samples that are polynomial in
$1/\varepsilon$. In the special, yet very relevant case of $k = 2$, we are able to
improve our aforementioned result and show that a moment-based algorithm
efficiently recovers $\vec{w}_1$ and $\vec{w}_2$ up to $\varepsilon$ with running time
and number of samples that are polynomial in $1/\varepsilon$, under the following
slightly different separability assumption.

\begin{assumption}[Separability Assumption -- $k = 2$] %
\label{as:no_index:2}
    For some \emph{known} $B, \Delta > 0$ it holds that
  \begin{equation*}
    \norm{\vec{w}_1^* - \vec{w}_2^*}_2 \ge \Delta \quad \text{ and } \quad \max_{j \in [k]} \norm{\vec{w}_j^*} \leq B  ~~~ \forall i \in [2]. \tag{B}
     \label{eq:asump_no_index:2}
  \end{equation*}
\end{assumption}

\begin{theorem}[Unknown-Index Estimation -- $k = 2$]
    \label{thm:no_index:2}
    Let $(\vec{x}^{(i)}, y^{(i)})_{i = 1}^n$ be $n$ observations from a
  self-selection setting with $2$ linear models $\vec{w}^*_1$, $\vec{w}^*_2$ as
  described in the unknown-index setting of Section \ref{sec:model}. If we assume
  Assumption \ref{asp:known:2} and Assumption \ref{as:no_index:2}, then there
  exists an estimation algorithm that outputs $\hat{\vec{w}}_1$,
  $\hat{\vec{w}}_2$ such that with probability at least $0.99$, for every
  $j \in [2]$
  \[ \norm{\hat{\vec{w}}_j - \vec{w}_j^*}_2 \le \varepsilon,\]
  as long as $n \geq \mathrm{poly} (d, 1/\varepsilon, \Delta, B, 1/\alpha)$ and
  $\varepsilon \le \Delta/10$. Furthermore, the running time of the algorithm is at most
  $n \cdot \mathrm{poly} (d, 1/\varepsilon, \Delta, B, 1/\alpha)$.
\end{theorem}

  In Section \ref{sec:unknown} we describe the algorithms and proofs for Theorem
\ref{thm:no_index} and Theorem \ref{thm:no_index:2}.
\medskip

\noindent \textbf{Remark.} (High-Probability Results)
    All of the above results are expressed in term of constant probability of
  error. We can boost this probability to $\delta$ by paying an additional
  $\log(1/\delta)$ factor in the sample and time complexities. This boosting can
  be done because we are solving a parametric problem and it a folklore idea that
  any probability of error less that $1/2$ can be boosted to $\delta$. Roughly
  the way that this boosting works is that we run the algorithm independently
  $\log(1/\delta)$ times and from the $\log(1/\delta)$ different estimates we
  keep one that contains at least half of all the others within a ball of radius
  $2 \varepsilon$.

\subsection{Identifiability with Unknown Indices}
\label{ssec:identifiability}
Here, we establish the information theoretic identifiability of the self-selection model with unknown indices. Recall, that we receive samples generated according to $y = \max_{j = 1}^k w_j^\top x + \eta_j$ where $x \thicksim \mathcal{N} (0, I)$ and $\eta_j \overset{iid}{\thicksim} \mathcal{N} (0, 1)$. We now establish the following theorem:

\unknownidentify*

\begin{proof}
    Our proof will be based on an inductive argument on the number of components, $k$. We will use a peeling argument to reduce the parameter recovery problem with $k$ components to one with $k - 1$ components. The base case when $k = 1$, reduces to standard linear regression where, for example, $\mathbb{E} [xy] = w_1$ suffices. For the inductive argument, suppose $k > 1$ and consider the following function:
    \begin{equation*}
        \forall v \in \mathbb{R}^d, \norm{v} = 1: F(v) = \lim_{\text{Even } p \to \infty} \lim_{\gamma \to 0} \lr{\frac{\mathbb{E} \sqlr{y^p \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma}}{(p-1)!!}}^{1 / p}.
    \end{equation*}
    We will now show that the above function is well defined for all $\norm{v} = 1$. The conditional moments may be evaluated with access to the distribution function $\Phi_{\mc{W}}$. Defining $j^* = \argmax_{j \in [k]} \abs{v^\top w_j}$ and $\sigma_j = \abs{v^\top \vec{w}_{j}}$, we now lower bound the conditional moment:
    \begin{align*}
        \mathbb{E} [y^p \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma] &\geq \mathbb{E} [y^p \cdot \bm{1} \blr{\vec{w}_{j^*}^\top x + \eta_{j^*}\geq 0} \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma] \geq \frac{1}{2} \cdot \mathbb{E} [y_{j^*}^p\mid \norm{\mathcal{P}^\perp_v x} \leq \gamma] \\
        &\geq \frac{1}{2} \cdot \mathbb{E} [(\vec{w}_{j^*}^\top \mathcal{P}_v (x) + \eta_{j^*} + \vec{w}_{j^*}^\top \mathcal{P}^\perp_v (x))^p\mid \norm{\mathcal{P}^\perp_v x} \leq \gamma] \\
        &\geq \frac{1}{2} \cdot \mathbb{E} \sqlr{\sum_{l = 0}^{p / 2} \binom{p}{2l} (\vec{w}_{j^*}^\top \mathcal{P}_v (x) + \eta_{j^*})^{p - 2l} (\vec{w}_{j^*}^\top \mathcal{P}^\perp_v (x))^{2l} \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma} \\
        &\geq \frac{1}{2} \cdot (p - 1)!! \cdot (\sigma_{j^*}^2 + 1)^{p / 2}.
    \end{align*}
    Through a similar computation, we obtain an upper bound on the conditional moment:
    \begin{align*}
        &\mathbb{E} [y^p \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma] \\
        &\leq \sum_{j = 1}^k \mathbb{E} [(\vec{w}_j^\top x + \eta_j)^p \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma] \\
        &= \sum_{j = 1}^k \mathbb{E} [(\vec{w}_j^\top \mathcal{P}_v x + \eta_j + \vec{w}_j^\top \mathcal{P}^\perp_v x)^p\mid \norm{\mathcal{P}^\perp_v x} \leq \gamma] \\
        &= \sum_{j = 1}^k \mathbb{E} \sqlr{\sum_{l = 0}^{p / 2} \binom{p}{2l} (\vec{w}_{j}^\top \mathcal{P}_v (x) + \eta_{j})^{p - 2l}(\vec{w}_{j}^\top \mathcal{P}^\perp_v (x))^{2l} \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma} \\
        &\leq \sum_{j = 1}^k (p - 1)!! \cdot (\sigma_j^2 + 1)^{p / 2} + \sum_{l = 1}^{p / 2} \mathbb{E} \binom{p}{2l} \sqlr{(\vec{w}_{j}^\top \mathcal{P}_v (x) + \eta_{j})^{p - 2l} (\vec{w}_{j}^\top \mathcal{P}^\perp_v (x))^{2l} \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma} \\
        &\leq k \cdot (p - 1)!! \cdot (\sigma_{j^*}^2 + 1)^{p / 2} + \sum_{j = 1}^k \sum_{l = 1}^{p / 2} \binom{p}{2l} \mathbb{E} \sqlr{(\vec{w}_{j}^\top \mathcal{P}_v (x) + \eta_{j})^{p - 2l} (\gamma \cdot \norm{\vec{w}_j})^{2l} \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma}.
    \end{align*}
    From the previous two displays, we get by taking $p^{th}$ roots and taking the limit as $\gamma \to 0$:
    \begin{equation*}
        \lr{\frac{1}{2}}^{1 / p}\cdot \sqrt{(\sigma_{j^*}^2 + 1)} \leq \lim_{\gamma \to 0} \lr{\frac{\mathbb{E} [y^p \mid \norm{\mathcal{P}^\perp_v x} \leq \gamma]}{(p - 1)!!}}^{1 / p} \leq k^{1 / p}\cdot \sqrt{(\sigma_{j^*}^2 + 1)}.
    \end{equation*}
    Taking $p \to \infty$, we obtain:
    \begin{equation}
        \label{eq:f_def}
        F(v) = \sqrt{\max_{j} \abs{w_j^\top v}^2 + 1}.
    \end{equation}
    Now, let $v^*$ be such that $v^* = \argmax_{\norm{v} = 1} F(v)$. From \eqref{eq:f_def}, we get that $v^* = \pm w_{j^*}$ for some $j^* \in [k]$ satisfying $j^* = \argmax_{j} \norm{w_j}$. Furthermore, $\sigma^* \coloneqq \norm{w_{j^*}} = \sqrt{F(v^*)^2 - 1}$. To identify the correct sign, consider the random variable $(x, y - x^\top (\sigma^* v^*))$. Note that this is a max-selection model with parameter set $\{w_j - \sigma^* v^*\}_{j \in [k]}$ with associated function $\wt{F}$ defined analogously to $F$. Now, we have the following two cases:
    \begin{itemize}
        \item[] \textbf{Case 1: } $\wt{F} (v^*) = \sqrt{4 \cdot (\sigma^*)^2 + 1}$. In this case, there exists $w \in \mc{W}$ with $w = - \sigma^* v^*$
        \item[] \textbf{Case 2: } $\wt{F} (v^*) < \sqrt{4 \cdot (\sigma^*)^2 + 1}$. In this case, we must have $w_{j^*} = \sigma^* v^*$.
    \end{itemize}
    In either case, we identify a single $w \in \mc{W}$. To complete the reduction, note that $(x, y - w^\top x)$ is a self-selection model with parameter set $\mc{W}^\prime = \{w_j - w\}_{j \in [k]}$. Defining the $k - 1$ sized point set $\mc{W}^\dagger = \{w_j - w\}_{\substack{j \in [k], j \neq j^*}}$, we note the relationship between the distribution functions $\Phi_{\mc{W}^\prime}$ and $\Phi_{\mc{W}^\dagger}$ for all $S \subset \mathbb{R}^d$ with $\P \blr{x \in S} \neq 0$:
    \begin{equation*}
        \forall t \in \mathbb{R}: \Phi_{W^\dagger} (S \times (-\infty, t]) = \frac{\Phi_{W^\prime} (S \times (-\infty, t])}{\Phi (t)}.
    \end{equation*}
    Hence, the distribution function $\Phi_{\mc{W}^\dagger}$ is a function of the distribution function of $\Phi_{\mc{W}^\prime}$ which is in turn a function of the distribution function of $\Phi_{\mc{W}}$. From our induction hypothesis, we have that $\mc{W}^\dagger$ is identifiable from $\Phi_{\mc{W}^\dagger}$ and consequently, from $\Phi_{\mc{W}}$. The proof of the inductive step now follows from the observation that $\mc{W} = \{z + w\}_{z \in \mc{W}^\prime} \cup \{w\}$.
\end{proof}

\subsection{Finding an $O(k)$-subspace}
\label{ssec:identifying_subspace}
\newcommand{\bm{M}}{\bm{M}}
We now move towards a finite-sample estimation algorithm for the unknown-index
case. The first step in our approach is an algorithm for approximately
identifying a size-$k$ subspace that has high overlap with $\text{span}(w_1,
\ldots, w_k)$.
In order to estimate the subspace, we will consider the matrix
$\bm{M} = \mathbb{E}\lr{\max(0, y)^2\cdot \vec{x}\vec{x}^\top}$. The following Lemma
shows that the top $k$ eigenvectors of $\bm{M}$ capture the span of the weight
vectors $w_k$:

\begin{lemma}[Weighted covariance]
    \label{lemma:svd_cov}
    Consider the matrix $\bm{M} = \mathbb{E}\lr{\max(0, y)^2 \cdot
    \vec{x}\vec{x}^\top}$, and let $$p_i = \mathbb{P}\lr{\left\{
    i = \argmax_{j \in [k]} w_j^\top \vec{x} + \eta_j\right\}
    \text{ and } \left\{ w_i^\top \vec{x} + \eta_i > 0\right\}}.$$ Then,
    \[
        \bm{M} = \mathbb{E}\lr{\max(0, y)^2} \cdot \bm{I} + 2\sum_{i=1}^{k} p_i \cdot w_iw_i^\top.
    \]
\end{lemma}
\begin{proof}
    \input{subspace_sq}
\end{proof}

We now use the spectral gap shown in the previous Lemma, in combination with a
matrix concentration argument, to argue that $k$-SVD on $\bm{M} -
\mathbb{E}[y^2]\cdot \bm{I}$ (where $\bm{M}$ is as defined in the previous Lemma)
will approximately recover the span of the $\{\vec{w_i}\}$.
We use as a primitive the following result about $k$-SVD:
\begin{fact}[\citep{rokhlin2010randomized}]
    \label{fac:k_svd}
    Let $M \in \mathbb{R}^{k \times k}$, and let $\sigma_1 \geq \sigma_2,
    \geq \ldots \geq \sigma_d$ denote the non-zero singular values of M. For
    any $j \in [k-1]$, define the spectral gap $g_j = \sigma_j /
    \sigma_{j+1}$. Furthermore, suppose we have access to an oracle which
    computes $Mv$ for any $v \in \mathbb{R}^k$ in time $R$. Then, for any
    $\eta, \delta > 0$, there is an algorithm $\textsc{ApproxSVD}(M,
    \eta, \delta)$ which runs in time $\tilde{O}(\frac{j \cdot R}{\min(1, g_j - 1)} \cdot log(k/(\eta \delta))$
    and with probability at least $1 - \delta$ outputs $U \in R^{k\times j}$
    with orthonormal columns so that $\|U - U_j\|_2 < \eta$, where $U_k$ is
    the matrix whose columns are the top $j$ right singular vectors of M.
\end{fact}

The combination of Lemma \ref{lemma:svd_cov} and Fact \ref{fac:k_svd} imply that it
suffices to show concentration of the average of a sequence $M^{x_i,y_i}$. The
following Lemma helps us establish this concentration:
\begin{restatable}{lemma}{svdconc}
    \label{lem:svd_conc}
    Suppose we generate $n$ samples $(\vec{x}^{(l)}, y^{(l)}) \sim X, Y$ from the
    self-selected linear regression model, i.e., $\vec{x}^{(l)} \sim
    \mathcal{N}(0, \bm{I}_d)$, then $y^{(l)}_i = \bm{w}_i^\top \vec{x}^{(l)} +
    \mathcal{N}(0, 1)$ for vectors $\vec{w_i} \in \mathbb{R}^d$ with $\|\vec{w_i}\|_2 \leq B$, and $y^{(l)} = \max_{i \in [k]} y^{(l)}_i$. Define the
    empirical second-moment matrix
    \begin{align*}
        \widehat{\bm{M}} = \frac{1}{n}\sum_{l=1}^n \max(0, y^{(l)})^2 \cdot \vec{x}^{(l)} {\vec{x}^{(l)}}^\top.
    \end{align*}
    Fix any $\delta \in (0, 1)$. Then, if $n \geq \Omega(\max(1/\delta, d))$,
    with probability at least $1 - \delta$,
    \begin{align*}
        \left\|\widehat{\bm{M}} - \mathbb{E}[\widehat{\bm{M}} ]\right\|_2 \in O\lr{
            \mathrm{poly}(B)\cdot \frac{\log(kn)}{\sqrt{n}}
            \max\left\{
                \sqrt{\log(2/\delta)},\sqrt{d}
            \right\}
        }.
    \end{align*}
\end{restatable}
\begin{proof}
    See Appendix \ref{app:proof:svd_conc}.
\end{proof}
\noindent We can thus
approximately identify the
relevant subspace in polynomial time.

\subsection{Estimating Parameters using the Low-Dimensional Subspace}
\label{ssec:est_low_dim}
\input{ui_estimation_old}

\subsection{Estimation in the $k = 2$ case}
We will now demonstrate how, when $k = 2$, we can use a moment-based
algorithm to estimate $\{\vec{w_1}, \vec{w_2}\}$ in $\text{poly}(1/\epsilon$)
time. The algorithm will operate as follows:
\begin{enumerate}
    \item Using the procedure outlined in Section \ref{ssec:identifying_subspace}, find an
    approximation $U$ to the linear subspace $U^*$ containing
    $\text{span}(\vec{w_1}, \vec{w_2})$.
    \item Set up an $\epsilon$-covering over the span of $U$. Since we assume
    $\|\vec{w_i}\| \leq 1$, the covering is of size $O(1/\epsilon^2)$.
    \item For each element $\widehat{\vec{w}}$ of the
    covering, collect samples $(\vec{x}, y - \vec{x}^\top \vec{v}_t)$ where $(x, y)$ are from the
    no-index self selection model.
    \item Using the moments of $y - \vec{x}^\top \widehat{\vec{w}}$ estimate
    $\min_{i \in \{0, 1\}} \|\vec{w_i} - \vec{w}\|^2$. We will show that
    $O(\frac{1}{\delta\varepsilon^2\text{poly}(B)})$ suffices to get an
    $\epsilon$-close approximation to this quantity $1-\delta$. Setting
    $\delta = O(\rho \epsilon^2)$ for some $\rho < 1$ ensures that we get
    accurate estimates of this quantity for each element $\vec{w}$ of our covering.
    \item As long as $\vec{w_1}$ and $\vec{w_2}$ are sufficiently separated,
    we can estimate $\vec{w_1}$ to be the minimum of our estimate over the
    $\epsilon$-covering, i.e., $\widehat{\vec{w_1}} = \arg\min_{w} \min_{i \in \{0, 1\}}
    \|\vec{w_i} - \vec{w}\|$. We can then estimate $\vec{w_2}$ to be the
    minimizer of the estimate over points that are $\Delta$-far from
    $\widehat{\vec{w_1}}$.
\end{enumerate}

Turning this outline into an efficient algorithm entails tackling a few distinct
technical challenges. First, we will show how to estimate $\min_{i \in \{0, 1\}}
\|\vec{w_i} - \vec{v}_t\|$ using samples $(\vec{x}, y)$ from our data-generating
process. Then, we will show that our sequential approach to estimating
$\vec{w_1}$ and $\vec{w_2}$ indeed suffices to recover both with good enough
accuracy. Finally, we will show that the error incurred by the subspace-finding
step does not adversely affect our estimation of the weight vectors.

\paragraph{Distance to the nearest weight vector.}
When $k = 2$, direct integration allows us to compute the moment generating
function of $y = \max \{\vec{w_1}^\top \vec{x} + \eta_1, \vec{w_2}^\top
\vec{x} + \eta_2\}$ in terms of the covariance matrix between $y_1$ and
$y_2$. This in turn allows us to accurately estimate the lesser of
$\text{Var}[y_1]$ and $\text{Var}[y_2]$, as captured by the following Lemma:
\begin{lemma} \label{lem:minVariance}
    Given a two-dimensional Gaussian random variable $z \sim \mathcal{N}(0,
    \Sigma)$ with $0 \prec \Sigma \in \mathbb{R}^2$, there exists an
    algorithm $\textsc{MinVariance}(\delta, \epsilon)$ which given
    $O(\frac{1}{\delta\epsilon^2})$ samples, outputs an estimate
    $\widehat{\sigma}$ of $\min_{0, 1} \Sigma_{ii}$ satisfying
    \[
        (1 - \beta)\lr{\min_{0, 1} \Sigma_{ii}} \leq \widehat{\sigma} \leq (1 + \beta) \lr{\min_{0, 1} \Sigma_{ii}}
    \]
    with probability $1 - \delta$.
\end{lemma}
\begin{proof}
    \input{k_equals_two}
\end{proof}
As a corollary of this result, we can estimate $\min_{i \in \{0, 1\}}
\|\vec{w_i} - \vec{w}\|^2$ to $\epsilon$-precision with probability at least $1
- \delta$:
\begin{corollary}
    Suppose we have samples $\{(x, y)\}$ generated from the self-selection model
    with unobserved index. Suppose further that $\|\vec{w_i}\| \leq B$ for $i
    \{0, 1\}$. Then, we can use the \textsc{MinVariance} algorithm of Lemma
    \ref{lem:minVariance} to recover $\sigma$ such that with probability at least
    $1 - \delta$,
    \[
        \left|\sigma - \min_{i \in \{0, 1\}} \|\vec{w_i} - \vec{w}\|^2 \right| \leq \epsilon.
    \]
\end{corollary} \label{cor:minVariance}
\begin{proof}
    Define the random variable $X = y - \vec{w}^\top x$. Then, $X$ is the
    maximum of the two Gaussian random variables
    $X_1 = (\vec{w_1} - \vec{w})^\top \vec{x} + \eta_i$ and
    $X_2 = (\vec{w_2} - \vec{w})^\top \vec{x} + \eta_i$.
    In particular, $\text{Var}[X_i] = \|\vec{w_i} - \vec{w}\|^2 + 1$. Thus, by
    applying the \textsc{MinVariance} algorithm to $X$, we can recover the
    desired quantity.
\end{proof}

\paragraph{Accuracy loss due to subspace recovery.}

From Section \ref{ssec:identifying_subspace}, we may assume the existence of a
$2$-dimensional subspace $\hat{U}$ satisfying the following:
\begin{equation*}
    \forall i \in [2]: \frac{\norm{w_i - \mathcal{P}_{\hat{U}} w_i}}{\norm{w_i}} \leq \varepsilon/2
\end{equation*}
where to find $\hat{U}$ we need $\mathrm{poly}(d, 1/\varepsilon, B, 1/\alpha)$ sample and time
complexity. Now from Corollary \ref{cor:minVariance} we have that if we estimate
$\sigma_{\min}$ within accuracy $\varepsilon/10$ then we can identify the point on the
$2$-dimensional $\varepsilon/2$-cover that is at least $\varepsilon$ close to $\vec{w}_1$,
assuming also that $\vec{w}_2$ is at least $\Delta \ge \varepsilon$ far away from
$\vec{w}_1$. Once we have identified $\vec{w}_1$ we can substract
$\vec{w}_1^{\top} \vec{x}$ from all the next samples of the form $(\vec{x}, y)$
find the minimum variance among the grid points that are at least $\Delta - \varepsilon$
far away from the estimated $\vec{w}_1$ and this way we are guaranteed to recover
the remaining $\vec{w}_2$ as well.

redpajama_set_name: RedPajamaArXiv


Thursday Momo came up and met me to have a little sister date. We had a quick dinner at my favorite Mexican joint where all the waiters drooled over Momo the whole time. Then we zipped over to the dollar store for movie candy before going to see Avatar in 3d. OMG this movie is just fabulous. I want to see it again! I can't remember if/when I've ever seen a 3d movie in the theatre before. Thankfully they've moved on from those red & blue saran wrap paper glasses. We were given black Risky Business glasses with clear lenses. I swear I just wanted to climb into the screen and live on Pandora. I loved all the glow in the dark stuff! So good. I'm glad we waited to see it after the crowds died down cause I went straight into my ugly cry. Momo & I had a great time. I love spending time with her!


Otočac is the center of Gacka and the seat of the City, also one of the oldest Croatian settlements. It is mentioned for the first time by a famous Baška plateau adn got the name by the natural river island in the middle of Gacka River, where it was fortified by walls and towers for defense.
Through Gacka valley where Otočac is situated, the river Gacka, one of the most beautiful and most beautiful rivers in Croatiaa and is one of the 3 most famous waters in the world that emerge unexpectedly behind the Velebit mountains. The fish trout, which is the world's most famous in river Gacka, is growing about five times faster than in other rivers in the karst region. That is why capital specimens of trout grow up to 5kg and fishing is very popular. So you must visit the Croatian Center for Indigenous karst fish and crabs.
Otočac is at great position because it is close to the natural sights and can be reached quickly to the beach. So during the day you can enjoy the sea and the sun, and in the evening relax in the city at a pleasant temperature. The National Parks of Plitvice and the North Velebit are nearby. If you want an active holiday, you can ride a bike through bicycle trails, walk or hike.
The surrounding area of Otočac has many interesting places. Nearby is a haven for young bear (Kutarevo) and village of Švica with lakes and waterfalls. If you like adrenaline or aviation, visit the sports aerodrome 3km southeast of Otočac and visit the remains of Fortica fort on the hill above Otočac.


Welcome to the Debt Free Miracle Affiliate Area!
That is your new link to send out for you to earn your gigantic 50% commissions for promoting the "Debt Free Miracle" ebook.
2--For example, suppose Ken Bryan is registered at ClickBank and his nickname there is "kbryan".
The above would be the link he sends out to his list. It's as simple as that.


I wouldn't know and neither would you. You're numb remember? It doesn't matter, just forget it.
What do you want me to do? You want me to be happy when you can't even be there when I need you? Yeah, that's gonna happen.
James, what do you want from me? Why are you still talking to me?
I don't know, you would.
Whatever you say, since you know me so well.
Would you please leave me alone.
So now you receive messages?
Do it yourself. I'm leaving.
Leave me alone okay? You want me to say yes? Fine, I hate you. Happy?
Whatever. Just leave me alone.


text:
Q: Troubleshoot permissions on a database I am trying to share across two snowflake accounts for same region I have two Snowflake account and need to clone or copy the databases and tables on the same region.
Solutions that I am trying to replicate:
Data Sharing Intro Reference
I read that:

"Snowflake supports using grants to provide granular access control to
  selected objects (schemas, tables, secure views, and secure UDFs) in
  the database (i.e., you grant access privileges for one or more
  specific objects within the database)."

It sounds like I could share a UDF with the database I want to share with the account, but read only features. This is confirmed:

" ...but cannot perform any of the DML tasks that are allowed in a
  full account (data loading, insert, update, etc.)."

Setting up one account as a provider:
USE ROLE ACCOUNTADMIN;

CREATE MANAGED ACCOUNT reader_acct1
    ADMIN_NAME = user1 , ADMIN_PASSWORD = 'Sdfed43da!44' ,
    TYPE = READER;

//create share
CREATE SHARE Articlelibary_share;

GRANT USAGE ON DATABASE Snapshots TO SHARE Articlelibary_share;

GRANT USAGE ON SCHEMA Snapshots.public TO SHARE Articlelibary_share;

GRANT SELECT ON TABLE Snapshots.public.Articlelibary_TEST TO SHARE Articlelibary_share;

However the error I am getting the error in my worksheet that says:

SQL compilation error: Database 'SNAPSHOTS' does not exist or not
  authorized.

What I have found is that when I am in the ACCOUNTADMIN role I can see the snapshot table, however, in the SYSADMIN I cannot see the the Snapshots table.
So, how can I fix the Database/Table permissions so that I can add it to the share?

A: The activities of creating a share and allowing access to other accounts has to be performed only by the ACCOUNTADMIN and that is the reason for the error that you are seeing.
From Documentation it is very clear :
https://docs.snowflake.net/manuals/user-guide/data-sharing-gs.html#getting-started-with-secure-data-sharing
To perform the tasks described in this topic, you must use the ACCOUNTADMIN role.


Micropore, Inc. has developed a revolutionary reactive plastic for use in adsorbent applications. ExtendAir Reactive Plastic Cartridges (RPCs) are designed for rebreathing and life support equipment, replacing the granular CO2 scrubbers currently used. This patented technology dramatically improves duration and ease-of-use, while eliminating many of the problems associated with granular adsorbents.
Of all the many benefi cial features of RPCs, the one that is most exciting is the factory-molded airfl ow channels. This eliminates both channeling problems and performance variability inherent in granular systems. An RPC's mean duration is repeatable to +/- 5% within two standard deviations, while granular performance is no better than +/- 30%. Because granular adsorbent scrubbers are typically oversized to account for this largeperformance variation, ExtendAir RPC scrubbers will have the lightest weight and smallest size, or the longest duration possible for a given scrubber volume.
HOW much better? At a minimum, duration is improved 25% due to a higher density of adsorbent alone. As the use conditions become more extreme (higher work rates, lower temperatures, higher pressures), the performance advantages are even greater. This graph shows the increase in duration (at 32°F and 150 ft. depth) compared to granules at various breathing rates.


text:
Q: Number of $3$-regular tree graphs with $n$ stray edges I'm working on the problem of finding all the isomorphism classes of 3-regular (each node has exactly 3 neighbours) fully connected tree (no loops) graphs with $n$ stray edges. This seems like a problem that would have been done before but I'm not sure of the terminology to search for it.
We may rephrase this as "number of tree graphs with n nodes of degree 1 (I'll call stray nodes) and all other nodes of degree 3". All isomorphisms are then generated by permutations of the $n$ stray nodes under the symmetric group $S_n$.
Some examples: I draw the stray nodes in light grey and label them $\{1\dots n\}$. The cases where $n=1$ and $n=2$ are degenerate.

*

*For $n=3$, $n=4$ and $n=5$ there is only one such graph.

*For all $n$ there is always a $K$ shaped graph

*For $n=6$ there are two. The corresponding $K$ graph described above and also this one.
What I've done so far
I have attempted to consider this algebraically. All nodes being degree 3 allows us to think of connecting two edges as a binary operation on the edges. As in we may consider connecting two edges as
$$(\_,\_): E \times E \mapsto E$$
This product commutes but is not associative. We also need a relation between edges $\sim$ which identifies two edges and connects their respective nodes. This relation is symmetric. If we then start with our $n$ stray edges, which I'll index with $\{1 \dots n\}$ also, our graph may be considered as a nested product of these edges with at least two edges related by $\sim$. For example the graph for $n=5$ would be
$$(((1,2),3),4) \sim 5 $$
and for $n=6$ the case that isn't the $K$ graph would be
$$(((1,2),(3,4)),5) \sim 6$$
Here I work through the above example and label the edges as I go.
There are many equivalent ways to write the same graph in this bracketing notation. We see that we can omit the $\sim n$ part if we are forced to choose a bracketing similar to the last two examples where on one side of $\sim$ is just $n$. Using this restriction we can equivalently write the $n=5$ graph as
$$(((1,2),3),4)$$
where the $\sim 5$ is inferred.
An isomorphic graph can be constructed by acting with $S_n$ on the bracket in the obvious way. We may then omit the numbers to represent an isomorphism class. For example for the $n=5$ graph
$$(((\bullet, \bullet),\bullet),\bullet)$$
Remember this product is still commutative so
$$(((\bullet, \bullet),\bullet),\bullet) = ((\bullet, (\bullet, \bullet)),\bullet)$$
for example.
Unfortunately this doesn't work as $((\bullet,\bullet),(\bullet,\bullet))$ and $(((\bullet, \bullet),\bullet),\bullet)$ are isomorphic graphs but not equal bracketings. I'm not sure if there's any way to fix this idea.


No summer picnic or backyard barbeque can be complete without watermelon. This sweet, juicy and refreshing fruit is a favorite among both kids and adults and best of all, it is good for us too.
Watermelon is low in calories, (only 40 calories per cup) and fat, cholesterol and sodium free. Appropriately named, watermelon contains over 90% water so eating it can also help to keep you hydrated on hot summer days. In addition, watermelon is packed with anti-oxidants including vitamin A and C and lycopene. Antioxidants protect our body cells from damage caused by free radicals. Free radicals are produced when our cells burn oxygen during normal body processes or from environmental factors like tobacco smoke and radiation. Overtime, damage from free radicals may lead to health problems such as heart disease, cancer, diabetes and other diseases. Eating foods rich in anti-oxidants, like watermelon, can help reduce our risk for developing health problems caused by free radical damage.
When shopping for the perfect watermelon for your summer picnic, look for one that is symmetrical and heavy for its size with dried stems and yellowish undersides. To store, keep whole watermelons at room temperature and refrigerate cut watermelon in an airtight container and use within 5 days.
For a delicious recipe that includes watermelon, try this one for Watermelon Granita.


text:
export default [
  ['Set up a Kubernetes cluster'],
  ['Learn Haskell well', false, true],
  ['Give a speech about programming', false, true],
  ['Join a team of highly-skilled and experienced people', true],
  ['Improve my spoken English', true],
  ['Sharpen my TypeScript skills', true],
  ['Contribute to an open source project', true],
  ['Write more tests and explore TDD approach', true],
  ['Increase presence on StackOverflow', true]
]

redpajama_set_name: RedPajamaGithub


text:
Current: Dragon Ball Z: Kakarot Lands On PS4 In Early 2020
Bandai Namco Entertainment CyberConnect 2 Dragon Ball Z: Kakarot E3 2019 PS4
Dragon Ball Z: Kakarot Lands On PS4 In Early 2020
Joe Apsey / June 14, 2019
Dragon Ball Z: Kakarot from the folks at Bandai Namco and CyberConnect 2 is a brand new action RPG announced during E3 2019. The game arrives on PS4 in early 2020.
The description for the PlayStation trailer offers a deeper description of the new action RPG:
Relive the story of Goku in DRAGON BALL Z: KAKAROT! Beyond the epic battles, experience life in the DRAGON BALL Z world as you fight, fish, eat, and train with Goku. Explore the new areas and adventures as you advance through the story and form powerful bonds with other heroes from the DRAGON BALL Z universe.
You can check out the announcement trailer below:
This is one of many announcements during E3 2019. Bandai Namco also announced Ni No Kuni: Wrath of the White Witch Remastered, a remaster of the cult-hit PS3 JRPG. Tales of Arise is the next game in the Tale of series and it is a huge step up from the last entry, offering gorgeous landscapes and effects. Finally, Elden Ring was announced, which is the next game from FromSoftware. George R.R. Martin has contributed to building the world of the game.
This news comes during E3 2019. You can watch all of the livestreams, as well as every conference at E3 2019 on our E3 2019 Livestream page.
Struggling to keep up on the news at E3? Check out our full E3 Announcements and News list, containing every reveal during the week-long show across all the conferences. You can also check out a variety of rumours that are surrounding the show. If you would prefer to see the reveals as they happen, you can take use our E3 2019 live feed, which will update with the new announcements as they happen.
Dragon Ball Z: Kakarot releases for PlayStation 4 in early 2020.
What are your thoughts on the game? Are you excited for a new Dragon Ball RPG?
Action > RPG

redpajama_set_name: RedPajamaCommonCrawl


text:
Q: How to access/select nested data frame column with dplyr I have the following data frame:
library(tidyverse)
iris %>%
  dplyr::select(Species, Petal.Width) %>%
  as_tibble()

Then I group by Species to get mean_se with the following line of code:
df <- iris %>%
  dplyr::select(Species, Petal.Width) %>%
  as_tibble() %>%
  group_by(Species) %>%
  mutate(ms = mean_se(Petal.Width))

It looks like this:
 df
# A tibble: 150 x 3
# Groups:   Species [3]
   Species Petal.Width  ms$y $ymin $ymax
   <fct>         <dbl> <dbl> <dbl> <dbl>
 1 setosa          0.2 0.246 0.231 0.261
 2 setosa          0.2 0.246 0.231 0.261
 3 setosa          0.2 0.246 0.231 0.261
 4 setosa          0.2 0.246 0.231 0.261
 5 setosa          0.2 0.246 0.231 0.261
 6 setosa          0.4 0.246 0.231 0.261
 7 setosa          0.3 0.246 0.231 0.261
 8 setosa          0.2 0.246 0.231 0.261
 9 setosa          0.2 0.246 0.231 0.261
10 setosa          0.1 0.246 0.231 0.261

However when I want to select ms$y and $ymax column, like this
> df %>% dplyr::select(Species, ms$y, $ymax)
Error: unexpected '$' in "df %>% dplyr::select(Species, ms$y, $"

It fails. What's the way to do it?

A: It gets stored as a nested dataframe. You can convert it to normal dataframe as :
library(tidyverse)

iris %>%
  select(Species, Petal.Width) %>%
  as_tibble() %>%
  group_by(Species) %>%
  mutate(ms = mean_se(Petal.Width)) %>%
  ungroup -> tmp

df <- bind_cols(tmp %>% select(-ms), tmp$ms)
df

# A tibble: 150 x 5
#   Species Petal.Width     y  ymin  ymax
#   <fct>         <dbl> <dbl> <dbl> <dbl>
# 1 setosa          0.2 0.246 0.231 0.261
# 2 setosa          0.2 0.246 0.231 0.261
# 3 setosa          0.2 0.246 0.231 0.261
# 4 setosa          0.2 0.246 0.231 0.261
# 5 setosa          0.2 0.246 0.231 0.261
# 6 setosa          0.4 0.246 0.231 0.261
# 7 setosa          0.3 0.246 0.231 0.261
# 8 setosa          0.2 0.246 0.231 0.261
# 9 setosa          0.2 0.246 0.231 0.261
#10 setosa          0.1 0.246 0.231 0.261
# … with 140 more rows

Select the columns you need.
df %>% select(Species, y, ymax)

# A tibble: 150 x 3
#   Species     y  ymax
#   <fct>   <dbl> <dbl>
# 1 setosa  0.246 0.261
# 2 setosa  0.246 0.261
# 3 setosa  0.246 0.261
# 4 setosa  0.246 0.261
# 5 setosa  0.246 0.261
# 6 setosa  0.246 0.261
# 7 setosa  0.246 0.261
# 8 setosa  0.246 0.261
# 9 setosa  0.246 0.261
#10 setosa  0.246 0.261
# … with 140 more rows

Another way without creating temporary variable tmp would be :
iris %>%
  select(Species, Petal.Width) %>%
  as_tibble() %>%
  group_by(Species) %>%
  mutate(ms = list(mean_se(Petal.Width))) %>%
  unnest(ms) %>%
  ungroup


DanceFest Milford offers a stage for renowned and emerging dance companies. The 2019 festival will feature a range of performances and workshops. A daring and intriguing set of artists will take over downtown Milford with site-specific performances. Headlining dance companies, including renowned David Parker & The Bang Group,Tina Croll Dance Company, DanielRose Projects and Hanna Q Dance Company, will perform at the Delaware Valley High School Auditorium. Make it a mini vacation, come enjoy dance, nature and beautiful historic Milford in the middle of blooming spring. Shop in the boutiques, antique stores, and galleries. Have a delicious lunch or dinner in the excellent restaurants and bars. Event dates are May 17-19 and July 12-13, 2019. See website for full schedule.