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

A distribution on $\mathbb{R}^d$ is log-concave if the logarithm
of its probability density function is concave:

\begin{definition}[Log-concave Density] \label{def:lc}
A probability density function $f : \mathbb{R}^d \to \mathbb{R}_+$, $d \in \mathbb{Z}_+$, is called {\em log-concave}
if there exists an upper semi-continuous concave function $\phi: \mathbb{R}^d \to [-\infty, \infty)$
such that $f(x) = e^{\phi(x)}$ for all $x \in \mathbb{R}^d$.
We will denote by $\mathcal{F}_d$ the set of upper semi-continuous,
log-concave densities with respect to the Lebesgue
measure on $\mathbb{R}^d$.
\end{definition}

Log-concave densities form a broad nonparametric family
encompassing a wide range of fundamental distributions, including
the uniform, normal, exponential, logistic, extreme value,
Laplace, Weibull, Gamma, Chi and Chi-Squared, and Beta distributions (see, e.g.,~\cite{BagnoliBergstrom05}).
Log-concave probability measures have been extensively investigated in several scientific disciplines,
including economics, probability theory and statistics, computer science,
and geometry (see, e.g.,~\cite{Stanley:89, An:95, LV07, Walther09, SW14-survey}).
The problem of {\em density estimation} for log-concave distributions is of central importance
in the area of non-parametric estimation (see, e.g., ~\cite{Walther09, SW14-survey, Sam17-survey})
and has received significant attention during the past decade in statistics~\cite{CSS10,
DumbgenRufibach:09, DossW16, ChenSam13, KimSam16, BalDoss14, HW16}
and computer science~\cite{CDSS13, CDSS14, ADLS17, CanonneDGR16, DKS16-proper-lc,
DiakonikolasKS17-lc, CDSS18}.

One reason the class of log-concave distributions has attracted this attention, both from the theoretical and practical communities, is that log-concavity is a very natural ``shape constraint,'' which places significantly fewer assumptions on the distribution in question than most parameterized classes of distributions. In extremely high-dimensional settings when the amount of available data is not too much larger than the dimensionality, fitting a multivariate Gaussian (or some other parametric distribution) to the data might be all one can hope to do.  For many practical settings, however, the dimensionality is modest (e.g., 5-20) and the amount of data is significantly larger (e.g., hundreds of thousands or millions).  In such settings, making a strong assumption on the parametric form of the underlying distribution is unnecessary---there is sufficient data to fit a significantly broader class of distributions, and log-concave distributions are one of the most natural such classes. From a practical perspective, even in the univariate setting, computing the log-concave density that maximizes the likelihood of the available data is a useful primitive, with the R implementation of Rufibach and Duembgen having over 39,000 downloads~\cite{logcondens}.  As we discuss below, the amount of data required to \emph{learn} a log-concave distribution scales exponentially in the dimension, in contrast to most parametric classes of distributions. Nevertheless, for the many practical settings with modest dimensionality and large amounts of data, there \emph{is} sufficient data to learn.  The question now is computational: how does one compute the best-fit log-concave distribution?  We focus on this algorithmic question:
\begin{center}
{\em Is there an efficient algorithm to compute the log-concave MLE for datapoints in $\mathbb{R}^d$?}
\end{center}
Obtaining an understanding of the above algorithmic
question is of interest for a number of reasons.
First, the log-concave MLE is {\em the} prototypical statistical estimator for the class, is fully automatic
(in contrast to kernel-based estimators, for example), and was very recently shown to achieve the minimax optimal sample complexity for the task of learning a log-concave distribution (up to logarithmic factors)~\cite{CDSS18, DaganK19}.  The log-concave MLE also has an intriguing geometry that is of interest from a purely theoretical standpoint~\cite{CSS10, RSU17}.
Developing an efficient algorithm for computing the log-concave MLE is of significant theoretical interest, and would also allow this general non-parametric class of distributions to be leveraged in the many practical settings where  the dimensionality is moderate and the amount of data is large.  We refer the reader to the recent survey~\cite{Sam17-survey} for a more thorough justification for why the log-concave MLE is a desirable distribution to compute.

\iffalse
Finally, we note that an efficient algorithm to compute the MLE
would yield the first efficient {\em proper} learning algorithm for the class of multivariate log-concave densities.

Recent work~\cite{KimSam16, CDSS18, DaganK19} has nearly characterized
the rate of convergence (aka sample complexity) of the log-concave MLE with respect
to the squared Hellinger loss. However, the question of efficient computability has remained open. \cite{CSS10}  established several key structural properties of the multivariate log-concave MLE and proposed a convex formulation to find it (see also~\cite{CuleS10}). Alas, the work~\cite{CSS10} does not give a polynomial time algorithm to compute it; in fact, the approach in~\cite{CSS10} \emph{cannot} lead to an algorithm with runtime better than $n^{\Omega(d)}$, where $n$ is the sample size and $d$ is the dimension.
That is, the running time dependence on the dimension $d$ in their approach is inherently exponential. This exponential dependence is illustrated in the experimental evaluation
of the method proposed in~\cite{CSS10}, demonstrating that the algorithm is prohibitively slow to beyond dimension 4. Recent work by \cite{RS18} proposed
a non-convex optimization approach to the problem of computing the log-concave MLE,
which seems to exhibit faster practical runtimes (scaling to $6$ or higher dimensions).
Unfortunately, their method is of a heuristic nature, in the sense that there is no
guarantee that their solution will converge to the log-concave MLE.

There are two main strands of research in density estimation.
The first one concerns the learnability of {\em high-dimensional parametric}
distribution families, e.g., mixtures of Gaussians. The sample complexity of learning parametric families is typically polynomial in the dimension and the goal is to design computationally efficient algorithms. The second research strand --- which is the focus of this paper --- studies the learnability of {\em low-dimensional nonparametric} distribution families under various assumptions on the shape of the underlying density. There has been a long line of work on this strand within statistics since the 1950s and, more recently, in computer science.  The majority of this literature has studied the univariate (one-dimensional) setting which is by now fairly well-understood for a wide range of distributions. On the other hand, the {\em multivariate} setting is significantly more challenging and significant gaps in our understanding remain even for $d=2$.
\fi

\subsection{Our Results and Techniques} \label{sec:results}

The main result of this paper is the first efficient algorithm to
compute the multivariate log-concave MLE.
For concreteness, we formally define the log-concave MLE:

\begin{definition}[Log-concave MLE] \label{def:mle}
Let $X_1, \ldots, X_n \in \mathbb{R}^d$.
The log-concave MLE, $\mathop{\widehat{f}_n} = \mathop{\widehat{f}_n}(X_1, \ldots, X_n)$,
is the density $\mathop{\widehat{f}_n} \in \mathcal{F}_d$ which maximizes the log-likelihood
$\ell(f) \stackrel{{\mathrm {\footnotesize def}}}{=}  \sum_{i=1}^n \ln(f(X_i))$
over $f \in \mathcal{F}_d$.
\end{definition}

\noindent As shown in~\cite{CSS10},
the log-concave MLE $\mathop{\widehat{f}_n}$ exists and is unique.
Our main result is the first efficient algorithm to compute it
up to any desired accuracy.

\begin{theorem}[Main Result] \label{thm:main}
Fix $d \in \mathbb{Z}_+$ and $0<\epsilon, \tau<1$. There is an algorithm that, on input any set of points $X_1, \ldots, X_n$ in $\mathbb{R}^d$, and $0< \epsilon$, $\tau < 1$,
runs in $\mathrm{poly}(n, d, 1/\epsilon, \log(1/\tau))$ time and with probability at least $1-\tau$
outputs a succinct description of a log-concave density $h^{\ast} \in \mathcal{F}_d$ such that
$\ell(h^{\ast}) \geq \ell(\mathop{\widehat{f}_n})-\epsilon.$
\end{theorem}

Our algorithm does {\em not} require
that the input points $X_1, \ldots, X_n$ in $\mathbb{R}^d$ are i.i.d. samples from a log-concave density,
i.e., it efficiently solves the MLE optimization problem for any input set of points.
We also note that the succinct output description of $h^{\ast}$ allows for both efficient
evaluation and efficient sampling. That is, we can efficiently approximate the density at a given point (within multiplicative accuracy), and efficient sample from a distribution that is close in total variation distance.

Recent work~\cite{CDSS18,DaganK19} has shown that the log-concave MLE is minimax optimal,
within a logarithmic factor, with respect to squared Hellinger distance.
In particular, the minimax rate of convergence with $n$ samples
is $\tilde{\Theta}_d{ \left( n^{-2/(d+1)} \right)}$. Combining this sample complexity bound with our Theorem~\ref{thm:main}, we obtain the first sample near-optimal and
computationally efficient {\em proper} learning algorithm for multivariate log-concave densities.
See Theorem~\ref{thm:global-loss} in Appendix~\ref{app:learning}.

\iffalse
Recall that the squared Hellinger loss between two distributions with densities
$f, g: \mathbb{R}^d \to \mathbb{R}_+$ is $h^2(f, g) = (1/2) \cdot \int_{\mathbb{R}^d} ( \sqrt{f(x)} - \sqrt{g(x)})^2 dx$.
Combined with the known rate of convergence of the log-concave MLE with respect to
the squared Hellinger loss, Theorem~3 in~\cite{CDSS18}, Theorem~\ref{thm:main} implies the following:

\begin{theorem} \label{thm:global-loss}
Fix $d \in \mathbb{Z}_+$ and $0<\epsilon, \tau<1$. Let $n = \nnew{\Omega} \left( (d^2/\epsilon) \ln^3(d/(\epsilon\tau))  \right)^{(d+3)/2}$.
There is an algorithm that, given $n$ iid samples from an unknown log-concave density $f_0 \in  \mathcal{F}_d$,
runs in $\mathrm{poly}(n)$ time and outputs a log-concave density $h^{\ast} \in \mathcal{F}_d$ such that
with probability at least $1-\tau$, we have that $h^2(h^{\ast}, f_0) \leq \epsilon$.
\end{theorem}

We note that Theorem~\ref{thm:global-loss} yields the first efficient proper learning algorithm
for multivariate log-concave densities under a global loss function, for any constant dimension.
\fi

\paragraph{Technical Overview}

Here we provide an overview of our algorithmic approach.
Notably, our algorithm does {\em not} require the assumption that the input points
are samples from a log-concave distribution. It runs in $\mathrm{poly}(n, d, 1/\epsilon)$
on {\em any} set of input points and outputs an $\epsilon$-accurate solution to the log-concve MLE.
Our algorithm proceeds by convex optimization:
We formulate the problem of computing the log-concave MLE of a set of $n$ points in $\mathbb{R}^d$
as a convex optimization problem that we solve via an appropriate first-order method.
It should be emphasized that one needs to overcome
several non-trivial technical challenges to implement this plan.

The first difficulty lies in choosing the right (convex) formulation.
Previous work~\cite{CSS10} has considered a convex formulation of the problem
that inherently fails, i.e., it cannot lead to a polynomial time algorithm.
Given our convex formulation, a second difficulty arises:
we do not have direct access to the (sub-)gradients of the objective function and the naive algorithm
to compute a subgradient at a point takes exponential time. Hence, a second challenge
is how to obtain an efficient algorithm for this task. One of our main contributions is
a randomized polynomial time algorithm to approximately compute a subgradient of the objective function. Our algorithm for this task leverages structural results on log-concave densities established in~\cite{CDSS18} combined with classical algorithmic results on approximating the volume of convex bodies and uniformly sampling from convex sets~\cite{kannan1997random, lovasz2006simulated, lovasz2006hit}.

We now proceed to explain our convex optimization formulation.
Our starting point is a key structural property
of the log-concave MLE, shown in~\cite{CSS10}: The logarithm of the log-concave MLE
$\ln \mathop{\widehat{f}_n}$, is a ``tent'' function, whose parameters are the values $y_1, \ldots, y_n$
of the log density at the $n$ input points $x^{(1)}, \ldots, x^{(n)}$,
and whose log-likelihoods correspond to polyhedra.
Our conceptual contribution lies in observing that while tent distributions
are not an exponential family, they ``locally'' retain many properties
of exponential families (Definition~\ref{def:LE}).
This high-level similarity can be leveraged to obtain a convex formulation of
the log-concave MLE that is  similar in spirit to the standard convex formulation of the exponential family MLE~\cite{wainwright2008graphical}.
Specifically, we seek to maximize the log-likelihood of the probability density function
obtained by normalizing the \nnew{log-concave function} whose logarithm
is the convex hull of the log densities at the samples.
This objective function is a concave function of the parameters,
so we end up with a (non-differentiable) convex optimization problem. The crucial observation is that
the subgradient of this objective at a given point $y$
is given by an expectation under the current hypothesis density at $y$.

Given our convex formulation, we would like to use a first-order method to efficiently
find an $\epsilon$-approximate optimum. We note that the objective function is not differentiable everywhere, hence we need to work with subgradients. We show that the subgradient of the objective function is bounded in $\ell_2$-norm at each point, i.e., the objective function is Lipschitz. Another important structural result (Lemma~\ref{lemma:radiusbound}) allows us to essentially restrict the domain of our optimization problem to a compact convex set of appropriately bounded diameter $D = \mathrm{poly}(n, d)$.
This is crucial for us, as the diameter bound implies an upper bound on
the number of iterations of a first-order method. Given the above, we can in principle use a projected subgradient method to find
an approximate optimum to our optimization problem,
i.e., find a log-concave density whose log-likelihood is $\epsilon$-optimal.

It remains to describe how we can efficiently compute a subgradient of our objective function.
Note that the log density of our hypothesis
can be considered as an unbounded convex polytope. The previous approach to calculate the subgradient in~\cite{CSS10}
relied on decomposing this polytope into faces and obtaining a closed form
for the underlying integral over these faces (that gives their contribution to the subgradient).
However, this convex polytope is given by $n$ vertices in $d$ dimensions, and therefore the number of its faces can be $n^{\Omega(d)}$. So, such an algorithm
cannot run in polynomial time.

Instead, we note that we can use a linear program (see proof of Lemma \ref{lemma:tentlocallyexp}) to evaluate a function proportional
to the hypothesis density at a point in time polynomial in $n$ and $d$. To use this oracle
for the density in order to produce samples from the hypothesis density,
we use Markov Chain Monte Carlo (MCMC) methods. In particular, we use MCMC
to draw samples from the uniform distribution on super-level sets and estimate their volumes.
With appropriate rejection sampling, we can use these samples to obtain
samples from a distribution that is close to the hypothesis density. See Lemma \ref{lem:sampling}. (We note that it does not suffice to simply run a standard log-concave density sampling technique such as hit-and-run \cite{lovasz2006fast}. These random walks require a hot start which is no easier than the sampling technique we propose.)

Since the subgradient of the objective can be expressed as an expectation over this density,
we can use these samples to sample from a distribution whose expectation is close to a subgradient. We then use stochastic subgradient descent to find an approximately optimal solution to the convex optimization problem. The hypothesis density this method outputs has log-likelihood close to the maximum.

\iffalse The correctness of the above algorithm relies on this preservation of properties of exponential families. In fact, tent distributions can be viewed as the union of a finite collection of exponential families that share a log-partition function. This union preserves the following properties of the maximum likelihood geometry that makes maximum likelihood estimation tractable:
\begin{enumerate}
    \item The objective is convex.
    \item Samples from the distributions can be used to compute unbiased estimates of the gradient of the likelihood with respect to a natural parameterization.
\end{enumerate}
Finally, we show that the solution to the log-concave MLE is a particular solution to the tent-density maximum likelihood problem.

\fi

\subsection{Related Work} \label{ssec:related}

There are two main strands of research in density estimation.
The first one concerns the learnability of  high-dimensional parametric distributions, e.g., mixtures of Gaussians. The sample complexity of learning parametric families is typically polynomial in the dimension and the challenge is to design computationally efficient algorithms. The second research strand --- which is the focus of this paper --- considers the problem of learning a probability distribution under various non-parametric assumptions on the shape of the underlying density, typically focusing on the univariate or small constant dimensional regime. There has been a long line of work in this vein within statistics since the 1950s, dating back to the pioneering work of~\cite{Grenander:56} who analyzed the MLE of a univariate monotone density. Since then, shape constrained density estimation has been an active research area
with a rich literature in mathematical statistics and, more recently, in computer science. The reader is referred to~\cite{BBBB:72} for a summary of the early work and to~\cite{GJ:14} for a recent book on the subject.

The standard method used in statistics for density estimation problems of this form
is the MLE. See~\cite{Brunk:58, PrakasaRao:69, Wegman:70,
HansonP:76, Groeneboom:85, Birge:87, Birge:87b,Fougeres:97,ChanTong:04,BW07aos, JW:09,
DumbgenRufibach:09, BRW:09aos, GW09sc, BW10sn, KoenkerM:10aos, Walther09,
ChenSam13, KimSam16, BalDoss14, HW16, CDSS18} for a partial list of works analyzing the MLE for various distribution families.
During the past decade, there has been a body of algorithmic work on shape constrained density estimation
in computer science with a focus on both sample and computational efficiency~\cite{DDS12soda, DDS12stoc, DDOST13focs, CDSS13, CDSS14, CDSS14b, ADHLS15, ADLS17, DKS15, DKS15b, DDKT15, DKS16, DiakonikolasKS17-lc, DiakonikolasLS18}. The majority of this literature has studied the univariate (one-dimensional) setting which is by now fairly well-understood for a wide range of distributions. On the other hand, the {\em multivariate} setting is significantly more challenging and wide gaps in our understanding remain even for $d=2$.

For the specific problem of learning a log-concave distribution,
a line of work in statistics~\cite{CSS10, DumbgenRufibach:09, DossW16, ChenSam13, BalDoss14} has characterized the global consistency properties of the log-concave multivariate MLE.
Regarding finite sample bounds,~\cite{KimSam16, DaganK19} gave
a sample complexity {\em lower bound} of $\Omega_d \left( (1/\epsilon)^{(d+1)/2} \right)$
for $d \in \mathbb{Z}_+$ that holds for {\em any} estimator, and \cite{KimSam16} gave
a near-optimal sample complexity {\em upper bound} for the log-concave MLE for $d \leq 3$.
\cite{DiakonikolasKS17-lc} established the first finite sample complexity upper bound for learning multivariate log-concave densities under global loss functions. Their estimator (which is different than the MLE and seems hard to compute in multiple dimensions) learns log-concave densities on $\mathbb{R}^d$ within squared Hellinger loss $\epsilon$ with $\tilde{O}_d \left( (1/\epsilon)^{(d+5)/2} \right)$ samples. \cite{CDSS18} showed a sample complexity upper bound of $\tilde{O}_d \left( (1/\epsilon)^{(d+3)/2} \right)$ for the multivariate log-concave MLE with respect to squared Hellinger loss, thus obtaining the first finite sample complexity upper bound for this estimator in dimension $d\geq 4$. Building on their techniques, this bound was subsequently improved in ~\cite{DaganK19} to a near-minimax optimal bound of $\tilde{O}_d \left( (1/\epsilon)^{(d+1)/2} \right)$.
Alas, the {\em }computational complexity of the log-concave MLE has remained open in
the multivariate case. Finally, we note that a recent work~\cite{DLS19} obtained a non-proper estimator
for multivariate log-concave densities with sample complexity $\tilde{O}_d((1/\epsilon)^{d+2})$ (i.e., at least quadratic in that of the MLE) and runtime $\tilde{O}_d((1/\epsilon)^{2d+2})$.

On the empirical side, recent work~\cite{RS18} proposed
a non-convex optimization approach to the problem of computing the log-concave MLE,
which seems to exhibit superior performance in practice in comparison to previous implementations (scaling to $6$ or higher dimensions).  Unfortunately, their method is of a heuristic nature, in the sense that there is no
guarantee that their solution will converge to the log-concave MLE.

The present paper is a merger of two independent works~\cite{AV18, DSS18}, proposing essentially the same algorithm to compute the log-concave MLE. Here we provide a unified presentation of these works with an arguably conceptually cleaner analysis.

\iffalse~\cite{KimSam16, HW16} showed that $\Theta(\epsilon^{-5/4})$ samples
are necessary and sufficient to learn an arbitrary univariate log-concave density over $\mathbb{R}$ within squared Hellinger loss $\epsilon$.  In the multivariate setting, a sequence of recent work~\cite{KimSam16, CDSS18, DaganK19} has nearly characterized the sample complexity of learning a log-concave distribution in terms of squared Hellinger loss, with the conclusion that the log-concave MLE is sample optimal, up to logarithmic factors.  The question of efficient computability has remained open. \cite{CSS10}  established several key structural properties of the multivariate log-concave MLE and proposed a convex formulation to find it (see also~\cite{CuleS10}). Alas, the characterization in~\cite{CSS10} does not yield a polynomial time algorithm to compute it; in fact, the approach in~\cite{CSS10} \emph{cannot} lead to an algorithm with runtime better than $n^{\Omega(d)}$, where $n$ is the sample size and $d$ is the dimension.  That is, the running time dependence on the dimension $d$ in their approach is inherently exponential. This exponential dependence is illustrated in the experimental evaluation of the method proposed in~\cite{CSS10}, demonstrating that the algorithm is prohibitively slow to beyond dimension 4. Recent work by \cite{RS18} proposed
a non-convex optimization approach to the problem of computing the log-concave MLE,
which seems to exhibit faster practical runtimes (scaling to $6$ or higher dimensions).
Unfortunately, their method is of a heuristic nature, in the sense that there is no
guarantee that their solution will converge to the log-concave MLE.\fi

\iffalse We describe the prior work that is directly related
to the results of this paper. Additional related
literature can be found in Appendix~\ref{app:related}.
\fi

\begin{comment}
The geometry of exponential family maximum likelihood estimation has been extensively studied.  For example, we have natural stochastic oracles for both the gradient and Hessian of the objective function (see e.g.~\cite{wainwright2008graphical}).  Despite this, we still lack algorithms that converge faster than at a sublinear rate.  It is certainly plausible that faster algorithms exist, perhaps either of the form of a stochastic Newton-type algorithm, or via a cutting plane method in an appropriate metric.
\end{comment}

\section{Preliminaries \label{sec:prelim}}

\noindent {\bf Notation.} We denote by $X_1,\ldots,X_n\in \mathbb{R}^d$ the sequence of samples. We denote by $S_n = \mathrm{Conv}(\{X_i\}_{i=1}^n)$ the convex hull of $X_1,\ldots,X_n$, and by $X$ the $d\times n$ matrix with columns vectors $X_1,\ldots,X_n$.
We write $\mathbbm{1}$ for the all-ones vector of the appropriate length.
For a set $Y\subset Z$, $\mathbbm 1_Y$ denotes the indicator function for $Y$.

\medskip

\noindent {\bf Tent Densities.}
We start by defining tent functions and tent densities:
\begin{definition}[Tent Function] \label{def:tent}
For $y = (y_1, \ldots, y_n) \in \mathbb{R}^n$ and a set of points $X_1, \ldots, X_n$ in $\mathbb{R}^d$,
we define the tent function $h_{X,y}: \mathbb{R}^d \to \mathbb{R}$ as follows:
\[
h_{X,y}(x) = \left\{\begin{array}{ll}
\max \{ z \in \mathbb{R} \textrm{ such that } (x, z) \in \mathrm{Conv}(\{(X_i, y_i)\}_{i=1}^n)\} & \text{ if } x\in S_n\\
 -\infty & \text{ if } x\notin S_n
 \end{array}\right.
\]
\end{definition}
The points $(X_i, y_i)$ are referred to as \emph{tent poles}.
(See Figure \ref{fig:tent} for the graph of an example tent function.)

\begin{figure}[h!]
    \centering
    \includegraphics[width=0.9\linewidth]{tentsubdivision.png}
    \caption{An example of a tent function and its corresponding regular subdivision. Notice that the regular subdivision is \emph{not} a regular triangulation.}
    \label{fig:tent}
\end{figure}

Let $p_{X,y}(x) = c\exp(h_{X,y}(x))$  with $c$ chosen such that $p_{X,y}(x)$ integrates to one. We refer to $p_{X,y}$ as a \emph{tent density} and the corresponding distribution as a \emph{tent distribution}. Note that the support of a \emph{tent distribution} must be within the convex hull of $X_1,\ldots,X_n$. For the remainder of the paper, we choose a scaling such that $\mathbbm{1}^T y = 0$. This scaling is arbitrary, and has no significant effect on either the algorithm or its analysis.

Tent densities are notable because they contain solutions to the log-concave MLE~\cite{CSS10}. The solution to the log-concave MLE over $X_1,\ldots,X_n$ is always a tent density, because tent densities with tent poles $X_1,\ldots,X_n$ are the minimal log-concave functions with log densities $y_1,\ldots,y_n$ at points $X_1,\ldots,X_n$.

The algorithm which we present can be thought of as an optimization over tent functions. In Section \ref{sec:suffstat}, we will show that tent distributions retain important properties of exponential families which will be useful to establish the correctness of our algorithm.

\medskip

\noindent {\bf Regular Subdivisions.}
Given a tent function $h_{X,y}$ with $h_{X,y} (X_i) = y_i$, its associated \emph{regular subdivision} $\Delta_{X,y}$ of $X$ is a collection of subsets of $X_1, \ldots, X_n \in \mathbb R^d$ whose convex hulls are the regions of linearity of $h_{X,y}$. See Figure \ref{fig:tent} for an illustration of a tent function and its regular subdivision. We refer to these polytopes of linearity as \emph{cells}. We say that $\Delta_{X,y}$ is a \emph{regular triangulation} of $X$ if every cell is a $d-$dimensional simplex.

It is helpful to think of regular subdivisions in the following way: Consider the hyperplane $H$ in $\mathbb R^{d+1}$ obtained by fixing the last coordinate. Consider the function $h_{X,y}$ as a polytope and project each face onto $H$. Each cell is a projection of a face, and together the cells partition the convex hull of $X_1, \ldots ,X_n$.  Observe that regular subdivisions may vary with $y$. Figure \ref{fig:changediv} provides one example of how changing the $y$ vector changes the regular subdivision.

\begin{figure}[h!]
    \centering
    \includegraphics[width=0.9\linewidth]{ChangingSubdivisions.png}
    \caption{Changing the height of the tent poles can change the induced regular subdivision (shown in purple). }
    \label{fig:changediv}
\end{figure}

For a given regular triangulation $\Delta$, the associated \emph{consistent neighborhood} $N_{\Delta}$  is the set of all $y \in \mathbb R^n$,  such that $ \Delta_{X,y} =\Delta$.  That is, consistent neighborhoods are the sets of parameters where the \emph{regular triangulation} remains fixed. Note that these neighborhoods are open and  their closures cover the whole space. See Figure~\ref{fig:changediv} for an example of how crossing between consistent neighborhoods results in different subdivisions.
We note that for fixed $X$, when $y$ is chosen in general position, $\Delta_{X,y}$ is always a regular triangulation.

\section{Locally Exponential Convex Programs\label{sec:math}}
In this section, we lay the foundations for the algorithm presented in the next section. We present the ``locally" exponential form of tent distributions and show it has the necessary properties to enable efficient computation of the log-concave MLE. Though they form a broader class of distributions, ``locally" exponential distributions share some important properties of exponential families. Namely, the log-likelihood optimization is convex, and the expectation of the sufficient statistic is a subgradient. This will allows us to formulate a convex program which we will be able to solve in polynomial time.

\begin{definition} \label{def:LE}
Let $T$ be some function (possibly parametrized by $y$) and let $q_y = \exp \left ( \langle T(x),y\rangle - A(y) \right)$ be a family of probability densities parametrized by $y$ with $A(y)$ acting to normalize the density so it integrates to $1$. We say that the family $\{ q_y \}$ is \emph{locally-exponential} if the following hold: (1) $A(y)$ is convex in $y$, and (2)  $\mathbb E_{x \sim \nnew{q}_y} [T(x)] \in \partial_y A(y)$.
\end{definition}
Note that the above definition differs from an exponential family in that for exponential families $T$ may not depend on $y$.

In this section, we derive a sufficient statistic, the \emph{polyhedral statistic}, that shows that tent distributions are in fact locally exponential. More formally, we show:
\begin{lemma}\label{lemma:tentlocallyexp}
For tent poles $X_1, \ldots, X_n$, there exists a function $T_{X,y}: \mathbb R^d \rightarrow \mathbb R^n$ (the polyhedral statistic) such that  $p_{X,y}(x) = \exp \left ( \langle T_{X,y}(x),y\rangle - A(y) \right)$ corresponds to the family of tent-distributions such that $\{ p_{X,y} \}$ is locally exponential. Furthermore, $T_{X,y}$ is computable in time $\mathrm{poly}(n,d)$.
\end{lemma}

Since we know that the log-concave MLE is a tent distribution, and all tent-distributions are log-concave, we know that the optimum of the maximum likelihood convex program in Equation \eqref{eqn:optformnew} corresponds to the log-concave MLE.

\begin{align}
    \textrm{MLE of tents } =\max\limits_{y}& \sum\limits_i h_{X,y}(X_i) - \log \int \exp h_{X,y}(x) dx     =\max\limits_{y}& \sum\limits_i y_i - A(y) \label{eqn:optformnew}
\end{align}

Combining the above with the fact that the sufficient statistic allows us to compute the stochastic subgradient suggests that Algorithm \ref{alg:complete} can compute the log-concave MLE in polynomial time.

\begin{algorithm}[H]
\begin{algorithmic}
\State $y \gets 0$; $c \gets 8n^2d \log (2nd)$; $m \gets \frac{2 c^2}{\epsilon^2}$\\
\For{$i\gets 1,m$} \\
    ~~~~ $\eta \gets  c / \sqrt i$\\
    ~~~~ $s \sim p_{X,y}$ \Comment{Using Lemma \ref{lem:sampling}}\\
    ~~~~ $y \gets y + \eta \left  (\frac 1 n\mathbbm 1 - T_{X,y}(s) \right)$ \Comment{$T$ computed via Lemma \ref{lemma:tentlocallyexp}. $\frac 1 n\mathbbm 1$ follows from Equation~\eqref{eqn:optformnew}}
\EndFor
\Return $y$
\end{algorithmic}
\caption{ComputeLogConcaveMLE($X_1, \ldots, X_n, \epsilon$)
\label{alg:complete}}
\end{algorithm}

\begin{comment}
 \begin{algorithm}[H]
 \caption{Stochastic First Order Algorithm for Computing the Log-Concave MLE}
 \label{alg:sketch}
 \begin{algorithmic}
    \Function{ComputeLogConMLE}{$X_1,...X_n$}
    \State $y \gets 0$
    \For{$i \gets 1,m$}
    \State $s \sim p(X,y)$ \Comment{sample}
    \State  $y \gets y + \eta_i \left  (\frac 1 n\mathbbm 1_n - T_{X,y}(s) \right)$ \Comment{subgrad}
    \EndFor
	\Return $y$
    \EndFunction
 \end{algorithmic}
  \end{algorithm}
  \end{comment}

Proving lemma \ref{lemma:tentlocallyexp} and highlighting the connection to exponential families will be the focus of this section. Section \ref{sec:alg} will fill in the remaining details by establishing polynomial time methods for sampling from tent distributions and bounding the number of iterations for stochastic gradient descent to converge.

A reader familiar with exponential families may note that Equation \eqref{eqn:optformnew} and algorithm \eqref{alg:complete} share a superficial similarity with the exponential family maximum likelihood problem. We develop this connection further in this section, generalizing some tools that were originally limited to exponential families. Note this applies even though the log-concave MLE is a \emph{non-parametric} statistics problem.

\begin{comment}

This section explores the connection between a family of distributions important for log-concave maximum likelihood estimation, tent distributions, and exponential families. We hope this section will provide the reader with intuition for the algorithm before the details of the proofs and implementation are explored in the next section.

After defining tent distributions we show that they retain many of the properties of exponential families. In fact they preserve the properties that make the standard exponential family maximum likelihood estimation algorithm tractable. We then characterize the log-concave MLE as a particular tent distribution maximum likelihood estimate, yielding the first algorithm for computing with a polynomial runtime dependence on both the number of samples and dimension.
\end{comment}

\subsection{The Polyhedral Sufficient Statistic \label{sec:suffstat}}
Consider a regular triangulation $\Delta$ corresponding to tent distribution parametrized by $X$ and $y$. The \emph{polyhedral statistic} is the function $$T_{X,y}(x): S_n \rightarrow [0,1]^n,$$ that expresses $x$ as a convex combination of corners of the cell containing $x$ in $\Delta_y$. That is $x = X T_{X,y}(x)$ where  $\lvert \lvert T_y(x) \rvert \rvert_1 = 1$ and $T_y(x)_i = 0$ if $X_i$ is not a corner of the cell containing $x$. The polyhedral statistic gives an alternative way of writing tent functions and tent densities:
$$ h_{X,y}(x) = \langle T_y(x), y \rangle ~~~~~~~~~~ p_{X,y}(x) = \exp( \langle T_y(x), y \rangle) \;.$$

If we restrict $y$ such that $\sum\limits_i y_i = 0$ and define $A(y) = \log \int\limits_x p_{X,y}(x) dx$, then we can see that for every consistent neighborhood $N_\Delta$ we have an exponential family of the form
\begin{align}
     \exp\left ( \langle T_y(x), \theta \rangle - A(y) \right ) \; \textrm{ for }  \theta \in N_\Delta \;. \label{eqn:expfam}
\end{align}
While Equation \eqref{eqn:expfam} shows how subsets of tent distributions are exponential families, it also helps highlight why tent distributions are \emph{not} an exponential family. The sufficient statistic depends on $y$ through the regular subdivision. This means that tent distributions do not admit the same factorized form as exponential families since the sufficient statistic depends on $y$.

Note that we can use any ordering of $X_1,\ldots,X_n$ to define the polyhedral sufficient statistic everywhere including on regular subdivisions that are \emph{not} regular triangulations. Also note that, assuming that no $X_i = X_j, i \neq j$, eliminating the last coordinate using the constraint $\mathbbm 1_n^T \theta = 0$ makes each exponential family minimal. In other words, over regions where the regular subdivision does not change (for example the consistent neighborhoods), tent distributions are minimal exponential families. This means the set of tent distribution can be seen as the finite union of a set of minimal exponential families. We refer to Equation \eqref{eqn:expform} as the exponential form for tent densities:
\begin{equation}
    p_{X,y} (x) = \exp\left ( \langle T_{X,y}(x), y \rangle - A(y) \right ) \mathbbm 1_{S_n}(x). \label{eqn:expform}
\end{equation}

Both the polyhedral statistic and tent density queries can be computed in polynomial time with the packing linear program presented in Equation \eqref{opt:densitylp}. For a point $x$, the value of $y$ yields the log-density and the vector $\alpha$ corresponds to polyhedral statistic.
\begin{align}
\max y \textrm{ s.t. } (x,y) =\sum\limits_i \alpha_i (X_i,y_i), \sum\limits_i \alpha_i = 1, \alpha_i \ge 0 \label{opt:densitylp}
\end{align}

Note that the above combined with tent distributions being exponential families on consistent neighborhoods gives us that the properties from Lemma \ref{lemma:tentlocallyexp} hold true on consistent neighborhoods. We extend the proof to the full result below.
\begin{proof}
Convexity  follows by iteratively applying known operations that preserve convexity of a function.
Since a sum of convex functions is convex (see, e.g., page 79 of ~\cite{boyd2}),
it suffices to show that the function $G(y) =  \ln(\int \exp(h_{X,y}(x)) \mathrm{d} x)$ is convex.
Since $h_{X,y}(x)$ is a convex function of $y$, by definition, $\exp(h_{X,y}(x))$
is log-convex as a function of $y$. Since an integral of log-convex functions
is log-convex (see, e.g., page 106 of ~\cite{boyd2}), it follows that $\int \exp(h_y(x)) \mathrm{d} x$ is log-convex.
Therefore, $G$ is convex. We have therefore established that Equation \eqref{eqn:optformnew} is convex, as desired.

$\mathbb E_{x \sim p_{X,y}}[T_{X,y}(x)] \in \partial_y A(y)$: Note that when $y$ is in the interior of a consistent neighborhood, the polyhedral statistic LP has a unique solution and $\mathbb E_{x \sim p_{X,y}}[T(x)] \in \partial_y A(y)$ (by Fact~\ref{fact:expfam}). When $y$ is on the boundary the solution set to the LP corresponds to the convex hull of solutions corresponding to each adjacent consistent neighborhood. This corresponds to the convex hull of limiting gradients from each neighboring consistent neighborhood and is the set of subgradients.
\end{proof}

\iffalse
\subsection{Generalizing to Tent Distribution MLE \label{sec:tentgeo}}
Understanding tent distributions as ``almost" being an exponential family is exactly what enables the efficient algorithm for computing the log-concave MLE.

Consider the following optimization over tent distributions for some fixed vector $\mu \in [0,1]^n, ||\mu||_1 = 1$. Note the similarity to the exponential family maximum likelihood optimization.
\begin{equation}
    y^\star = \argmax\limits_{y} \left (\langle \mu, y \rangle - A(y) \right )
\end{equation}

By definition, $A (y) = \log \int \exp (\langle \mu, y \rangle) dx$, which is, up to a linear component, exactly the logarithm of the function $\sigma$ studied in \cite{CSS10}. We use the fact that $\exp(A(y))$ is convex combined with the exponential family geometry to prove that $A(y)$ is convex.   This allows us to prove that the geometry of the log-partition function of tent distributions behaves, in many ways, similarly to that of exponential families.
\begin{restatable}{theorem}{thmtentexp}\label{thm:convex}
The analogs of Facts \ref{fact:expfam} (a) (convexity) and \ref{fact:expfam} (b) (subgradients) hold for tent distributions. Namely $A(y)$ is convex and $\mathbb E_{x \sim p_{X,y}}[T(x)] \in \partial_y A(y)$.
\end{restatable}

The proof of Theorem \ref{thm:convex} can be found in Appendix \ref{app:convexity}.

The above suggests that we are able to compute a tent-distribution MLE. However, this will require choosing a polyhedral statistic with respect to which to we should maximize the likelihood. We now characterize the solution to the log-concave MLE in terms of the polyhedral sufficient statistic.

\begin{lemma} \label{lemma:mlesuffstat}
The log-concave MLE is obtained by maximizing the likelihood of data with the uniform polyhedral statistic ($\mu =\frac 1 n \mathbbm 1$).
\end{lemma}
\begin{proof}
Let $\hat y$ be the parameters of the log-concave MLE expressed in the exponential form of tent distributions. Notice that $T(X_i) = e_i$, i.e. the polyhedral statistic is a one-hot vector at the tent poles. Then starting with the log-likelihood maximization we get:
\begin{align}
   \hat y &= \argmax\limits_y \sum\limits_i  \left (\left \langle T(X_i), y \right \rangle   - A(y) \right )
    = \argmax\limits_y \left \langle \frac 1 n \sum\limits_i T(X_i), y \right \rangle   - A(y) \nonumber \\
   &= \argmax\limits_y \left \langle \frac 1 n \mathbbm{1}, y \right \rangle  - A(y) \label{opt:mletentmath}
\end{align}
\end{proof}
One interpretation of this is that the log-concave MLE is the tent distribution which has most even support over its tent poles.  Furthermore, we  observe that since $\mathbbm 1^T y = 0$, Equation \eqref{opt:mletentmath} is equivalent to simply minimizing the log partition function.

\begin{comment}
\subsection{Tent Distributions and Geometric Combinatorics}
The geometric aspect of this paper is related to the recent work by \cite{RSU17}. They observe that solving the log-concave  MLE problem over a \emph{weighted} set of samples has a strong connection to geometric combinatorics.

They examined the relationship between the weight vector and the combinatorial structure of the tent density maximizing the weighted likelihoods. In particular, they showed that different values of the weight vector can induce every regular subdivision.
In the context of our work, the weight vector can be thought of as an expected value of the polyhedral statistic. Then their work can be interpreted as studying the map from the expected value of the polyhedral sufficient statistic to regular subdivisions. The consistent neighborhoods are exactly the dual of the preimages of regular triangulations under this map.

Also of interest is the \emph{Samworth body}, studied by \cite{RSU17}, which is defined as
$S(X) = \left\{ y \mid  \int \exp (h_{X,y} (x)) dx \le 1 \right\}$.
Points on the boundary of the Samworth body correspond to tent densities. This means that parameters of the exponential form of tent distributions are in bijection with the boundary of the Samworth body using the  map $y \rightarrow y - A(y)$.
\end{comment}
\fi

\section{Algorithm and Detailed Analysis \label{sec:alg}}
Recall that we compute the log-concave MLE via a first-order method on the optimization formulation presented in Equation~\eqref{eqn:optformnew}. The complete method is presented in Algorithm~\ref{alg:complete}.
The algorithm is based on the stochastic gradient computation presented in the previous section, a standard application of the stochastic gradient method, and a sampler to be described later in this section.

\begin{comment}
\begin{algorithm}\label{alg:sampling}
\caption{Algorithm to sample from  $p_{X,y}$}
\begin{algorithmic}
\Procedure{Sample}{$X_1,...X_n,y$} \Comment{Sample within $\delta$ Total Variation distance of the normalized tent distribution with poles at $X_i$ and log-densities $y_i$}
\State $M \gets \argmax\limits_i y_i$
\State Define level sets $l_i$ as $\{ x \mid h_{X,y}(x)  \ge M - i\}$
\State Compute approximate volumes $\hat V_i$ s.t. $ \frac{Vol( l_i)}{ 1+ \delta} \le \hat V_i \le ( 1+ \delta) Vol( l_i)$ \State  $\widetilde{c} \gets \sum_{i=1}^m 2^{-i} \hat V_i + 2^{-m} V_m$
\State Sample $I \sim \widetilde{D}$ s.t.
$$
\mathrm{Pr}_{I\sim \widetilde{D}} [I = i] = \left\{\begin{array}{ll}
\widetilde{\mathrm{vol}}(L_i) \cdot 2^{-i} / \widetilde{c} & \text{ if $i\in \{1,\ldots,m-1\}$}\\
2 \cdot \widetilde{\mathrm{vol}}(L_m) \cdot 2^{-m} / \widetilde{c} & \text{ if $i=m$}
\end{array}\right.$$
\State Sample $Z \sim Unif[l_i]$
\State With probability $1 - \frac{\exp (p_{X,y})}{TODO}$ repeat the previous step
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{comment}

\subsection{Analysis}
\label{sec:analysis}

We now provide the main technical ingredients used to prove Theorem \ref{thm:main}.
Specifically, we bound the rate of convergence of the stochastic subgradient method, and we provide an efficient procedure for sampling from a log-concave distribution.

\subsubsection{Stochastic Subgradient Method}
Recall that algorithm \ref{alg:complete} is simply applying the stochastic subgradient method to the following convex program with $\mathbbm 1^T y = 0$: $h(y) = \left \langle \frac 1 n \mathbbm 1_n, y \right \rangle - A(y)$.

We will require a slight strengthening of the following standard result,
see, e.g., Theorem 3.4.11 in~\cite{Duchi16}:
\begin{fact} \label{thm:sgd}
Let $\mathcal{C}$ be a compact convex set of diameter $\mathrm{diam}(\mathcal{C})<\infty$.
Suppose that
the projections $\pi_{\mathcal{C}}$ are efficiently computable, and there exists $M <\infty$ such that
for all $y \in \mathcal{C}$ we have that $\|g\|_2 \leq M$ for all stochastic subgradients.
Then, after $K = \Omega \left( M \cdot \mathrm{diam}(\mathcal{C}) \log(1/\tau)/\epsilon^2 \right)$ iterations
of the projected stochastic subgradient method (for appropriate step sizes),
with probability at least $1-\tau$, we have that
$F\left(\bar{y}^{(K)}\right) - \min_{y \in \mathcal{C}}F(y) \leq \epsilon \;,$
where $\bar{y}^{(K)} = (1/K) \sum_{i=1}^K y^{(i)}$.
\end{fact}

We note that Fact~\ref{thm:sgd} assumes that, in each iteration, we can efficiently calculate
an {\em unbiased} stochastic subgradient, i.e., a vector  $g^{(k)}$ such that
$\mathbb{E}[g^{(k)}] \in \partial_y F(y^{(k)})$.
Unfortunately, this is not the case in our setting,
because we can only {\em approximately} sample from log-concave densities. However,
it is straightforward to verify that the conclusion of Fact~\ref{thm:sgd} continues to hold
if in each iteration we can compute a random vector $\widetilde{g}^{(k)}$ such that
$\|\mathbb{E} [\widetilde{g}^{(k)}] - g^{(k)}\|_2 < \delta \stackrel{{\mathrm {\footnotesize def}}}{=} \epsilon/(2\mathrm{diam}(\mathcal{C}))$,
for some $g^{(k)} \in \partial_y F(y^{(k)})$.
This slight generalization is the basic algorithm we use in our setting.

We now return to the problem at hand. We note that since $T$ represents the coefficients of a convex combination $||T(x)|| < 1$ for all $x$, bounding $M$ by 1.

Lemma \ref{lemma:radiusbound} will show that $\mathrm{diam}(\mathcal C) = O(2n^2d \log (2nd))$. This implies that if we let $c = 8 n^2 d \log (2nd)$ and run SGD for $\frac{2c^2}{\epsilon^2}$ iterations, the resulting point will have objective value within $\epsilon$ of the log-concave MLE.\\

\begin{restatable}{lemma}{lemmaradiusbound}\label{lemma:radiusbound}
Let $X_1, \ldots , X_n$ be a set of points in $\mathbb R^d$ and $\hat f$ be the corresponding log-concave MLE. Then, we have that
$R_\infty \stackrel{{\mathrm {\footnotesize def}}}{=} \frac{\max_{i \in [n]}\hat f(X_i)}{\min_{i \in [n]}\hat f(X_i)}  \leq (2 n d)^{2 n d}$.
Converting to an $\ell_2$ norm yields a bound on the diameter of $\mathcal C$:
$\mathrm{diam}(\mathcal C) \le 2n^2d \log (2nd).$
\end{restatable}

Let us briefly sketch the proof of Lemma \ref{lemma:radiusbound}.
The main idea is to show that if $R_\infty$ were too high, then $\mathop{\widehat{f}_n}$ would have a lower likelihood than the uniform distribution on the convex hull of the samples $S_n$.
More specifically, if the maximum value $M$ of the density $\mathop{\widehat{f}_n}$ is large, then the volume of the set  $\{x\in \mathbb{R}^d: \mathop{\widehat{f}_n}(x) \geq M/R\}$ is small.
For a fixed $R$, this set contains $S_n$ and thus  $R_\infty$ must be large compared to $M\mathrm{vol}(S_n)$. Since $\mathop{\widehat{f}_n}$ has likelihood at least as high as the uniform distribution over $S_n$, $R$ must be small compared to $M\mathrm{vol}(S_n)$. Combining these two observations yields a bound on $R$.

We now proceed with the complete proof.

\begin{proof}[Proof of Lemma~\ref{lemma:radiusbound}]
Let $V = \mathrm{vol}(S_n)$ be the volume of the convex hull of the sample points
and $M =  \max_{x} \mathop{\widehat{f}_n}(x)$ be the maximum pdf value of the MLE.
By basic properties of the log-concave MLE (see, e.g., Theorem~2 of~\cite{CSS10}), we have that
$\mathop{\widehat{f}_n}(x) >0$ for all $x \in S_n$ and $\mathop{\widehat{f}_n}(x)=0$ for all $x \not \in S_n$.
Moreover, by the definition of a tent function, it follows that $\mathop{\widehat{f}_n}$ attains its global maximum value and its global non-zero positive value
in one of the points $X_i$.

We can assume without loss of generality that $\mathop{\widehat{f}_n}$ is not the uniform distribution
on $S_n$, since otherwise $R_\infty = 1$ and the lemma follows.
Under this assumption, we have that $R_\infty > 1$ or $\ln R_\infty > 0$, which implies that $M > 1/V$.
The following fact bounds the volume of upper level sets
of any log-concave density:
\begin{fact}[see, e.g., Lemma~8 in ~\cite{CDSS18}] \label{fact:vol}
Let $f \in \mathcal{F}_d$ with maximum value $M_f$. Then for all $w >0$, we have
$\mathrm{vol}(L_{f}(M_{f} e^{-w})) \leq \nnew{{w}^d / M_{f}}$.
\end{fact}
By Fact~\ref{fact:vol} applied to the MLE $\mathop{\widehat{f}_n}$, for $w = \ln R_\infty$, we get that
$\mathrm{vol}(L_{\mathop{\widehat{f}_n}}(M/R_\infty)) \leq (\ln R_\infty)^d/ M$. Since the pdf value of $\mathop{\widehat{f}_n}$ at
any point in the convex hull $S_n$ is at least that of the smallest sample point
$X_i$, i.e., $M/R_\infty$, it follows that $S_n$ is contained in $L_{\mathop{\widehat{f}_n}}(M/R_\infty)$.
Therefore,
\begin{equation} \label{eqn:volume-ub}
V \leq (\ln R_\infty)^d/M \;.
\end{equation}
On the other hand, the log-likelihood of $\mathop{\widehat{f}_n}$
is at least the log-likelihood of the uniform distribution $U_{S_n}$ on $S_n$.
Since at least one sample point $X_i$ has pdf value $\mathop{\widehat{f}_n}(X_i) = M/R_\infty$
and the other $n-1$ sample points have pdf value $\mathop{\widehat{f}_n}(X_i) \leq M$,
we have that
$$\ln(M/R_\infty) + (n-1) \ln M \geq \ell(\mathop{\widehat{f}_n}) \geq \ell(U_{S_n}) = n \ln (1/V) \;,$$
or $n \ln M - \ln R_\infty \geq - n \ln V$,
and therefore $\ln (M V) \geq (\ln R_\infty)/n$.
This gives that
\begin{equation} \label{eqn:volume-lb}
R_\infty^{1/n} \leq M V  \;.
\end{equation}
Combining \eqref{eqn:volume-ub} and \eqref{eqn:volume-lb} gives
\begin{equation} \label{eqn:R}
R_\infty \leq (\ln R_\infty)^{n d}  \;.
\end{equation}
Since $\ln x < x$, $x \in \mathbb{R}$,  setting $x= R_\infty^{1 \over{2 n d}}$ gives that
$\ln R_\infty < 2 n d \cdot R_\infty^{1 \over{2 n d}}$ or
\begin{equation} \label{eqn:lnR}
(\ln R_\infty)^{n d} < (2 n d)^{n d} \cdot R_\infty^{1/2}\;.
\end{equation}
By \eqref{eqn:R} and \eqref{eqn:lnR} we deduce that
$R_\infty \leq (2 n d)^{n d} \cdot R_\infty^{1/2}$ or
$$R_\infty \leq (2 n d)^{2 n d} \;.$$
This completes the proof of Lemma~\ref{lemma:radiusbound}.
\end{proof}

\subsubsection{Efficient Sampling and Log-Partition Function Evaluation}
\label{sec:sampling}

In this section, we establish the following result,
which gives an efficient algorithm for sampling from the log-concave distribution computed by our algorithm.

\begin{lemma}[Efficient Sampling]\label{lem:sampling}
There exist algorithms ${\cal A}_1$ and ${\cal A}_2$ satisfying the following:
Let $\delta, \tau>0$,
let $X=X_1,\ldots,X_n\in \mathbb{R}^d$,
let $y\in \mathbb{R}^n$ be a parameter of a tent-density in exponential form.
Then the following conditions hold:
\begin{itemize}
\item[(1)]
On input $X$, $y$, $\delta$, and $\tau$, algorithm ${\cal A}_1$ outputs a random vector $Z\in \mathbb{R}^d$,
distributed according to some probability distribution with density $\widetilde{\phi}$, such that
$\|\widetilde{\phi} - p_{X,y}\|_1 = O(\delta)$,
in time
$\mathrm{poly}(n, d, \|y\|_\infty, 1/\delta, \log(1/\tau))$,
with probability at least $1-\tau$.

\item[(2)]
On input $X$, $y$, $\delta$, and $\tau$, algorithm ${\cal A}_2$ outputs some $\gamma'>0$, such that
$\gamma' / (1+O(\delta)) \leq \int \exp(h_{X,y}(x)) \mathrm{d} x \leq \gamma' \cdot (1+O(\delta))$,
in time
$\mathrm{poly}(n, d, \|y\|_\infty, 1/\delta, \log(1/\tau))$,
with probability at least $1-\tau$.
\end{itemize}
\end{lemma}

The algorithm used in the proof of Lemma \ref{lem:sampling} is concerned mainly with part (1) in its statement. The pseudocode of this sampling procedure is given in Algorithm \ref{alg:sampling}.

Using the notation from Algorithm \ref{alg:sampling}, part (2) is easier to describe and we thus omit the pseudocode. We note that the following exposition of Algorithm \ref{alg:sampling} assumes that the input vector $y$ is bounded. In the execution of Algorithm \ref{alg:complete}, $\| y\|_\infty$ is bounded linearly by the number of SGD iterates. Thus, the dependence of the sampling runtime on $\|y\|_\infty$ increases the overall runtime by at most a  polynomial.

\begin{algorithm}
  \caption{Algorithm to sample from $p_{X,y}$}
  \label{alg:sampling}
  \label{alg:pc-sdp}
\begin{algorithmic}
\Procedure{Sample}{$X_1,\ldots, X_n,y$}\\
\textbf{Input:} Sequence of points $X=\{X_i\}_{i=1}^n$ in $\mathbb{R}^d$, vector $y\in \mathbb{R}^n$, parameter $0< \delta < 1$.
\\
\textbf{Output:} A random vector $Z \in \mathbb{R}^d$ sampled from a probability distribution with density function $\widetilde{\phi}$, such that $\|\widetilde{\phi}-p_{X,y}\|_1 \leq \delta$.
\\
\textbf{Step 1.} Let $m = \lceil 1+2\|y\|_\infty\rceil$. Let $M=\max_{x\in \mathbb{R}^d} \exp(h_{X,y}(x))$.
For any $i\in [m]$, let $L_i=\{x\in \mathbb{R}^d: \exp(h_{X,y}(x))\geq M \cdot 2^{-i}\}$.
 For each $i\in [m]$ compute an estimate $\widetilde{\mathrm{vol}}(L_i)$ of $\mathrm{vol}(L_i)$ such that
  \[
  \mathrm{vol}(L_i)/(1+\delta)\leq \widetilde{\mathrm{vol}}(L_i) \leq \mathrm{vol}(L_i)(1+\delta).
  \]\\
\textbf{Step 2.} For $i\in [m]$, let $u_i$ be the uniform probability distribution on $L_i$, and let $\widetilde{u}_i$ be an efficiently samplable probability distribution such that
  \[
  \|\widetilde{u}_i - u_i\|_1 \leq \delta.
  \]\\
\textbf{Step 3.} Let $\widetilde{c} = \sum_{i=1}^m 2^{-i} \widetilde{\mathrm{vol}}(L_i) + 2^{-m} \widetilde{\mathrm{vol}}(L_m)$.\\
\textbf{Step 4.} Let $\widehat{D}$ be the probability distribution on $[m]$ with
\[
\mathrm{Pr}_{I\sim \widetilde{D}} [I = i] = \left\{\begin{array}{ll}
\widetilde{\mathrm{vol}}(L_i) \cdot 2^{-i} / \widetilde{c} & \text{ if $i\in \{1,\ldots,m-1\}$}\\
2 \cdot \widetilde{\mathrm{vol}}(L_m) \cdot 2^{-m} / \widetilde{c} & \text{ if $i=m$}
\end{array}\right.
\]\\
\textbf{Step 5.} Sample $I\sim \widetilde{D}$.\\
\textbf{Step 6.} Sample $Z \sim \widetilde{u}_I$.\\
\textbf{Step 7.} For any $x\in \mathbb{R}^d$ let
\[
G_{X,y}(x) = M \cdot 2^{-\lfloor \log_2(M/\exp(h_{X,y}(x))) \rfloor}
\]\\
\textbf{Step 8.} With probability $1-\exp(h_{X,y}(Z))/G_{X,y}(Z)$ go to Step 5.\\
\Return{$Z$.}
\EndProcedure
\end{algorithmic}
\medskip
\end{algorithm}

We now present the proof of Lemma \ref{lem:sampling}.
The pseudocode of the sampling procedure is given in  Algorithm \ref{alg:sampling}.
As stated in Section~\ref{sec:sampling}, Algorithm \ref{alg:sampling} uses subroutines for approximating the volume of a convex body given by a membership oracle, and a procedure for sampling from the uniform distribution supported on such a body.
For these procedures we use the algorithms by
\cite{kannan1997random},
which are summarized in Theorems \ref{thm:KLS_volume} and \ref{thm:KLS_sampling} respectively.

\begin{theorem}[\cite{kannan1997random}]
\label{thm:KLS_volume}
The volume of a convex body $K$ in $\mathbb{R}^d$, given by a membership oracle, can be approximated to within a relative error of $\delta$ with probability $1-\tau$ using
\[
d^5 \cdot \mathrm{poly}(\log d, 1/\delta, \log(1/\tau))
\]
oracle calls.
\end{theorem}

\begin{theorem}[\cite{kannan1997random}]
\label{thm:KLS_sampling}
Given a convex body $K\subset \mathbb{R}^d$, with oracle access, and some $\delta>0$, we can generate a random point $u \in K$ that is distributed according to a distribution that is at most $\delta$ away from uniform in total variation distance, using
\[
d^5 \cdot \mathrm{poly}(\log d, 1/\delta)
\]
oracle calls.
\end{theorem}

For all $X=X_1,\ldots,X_n\in \mathbb R^d$, $y\in \mathbb{R}^n$, and $x\in \mathbb{R}^d$, we use the notation $H_{X,y}(x) = \exp(h_{X,y}(x))$.

In order to use the algorithms in Theorems \ref{thm:KLS_volume} and \ref{thm:KLS_sampling} in our setting, we need a membership oracle for the superlevel sets of the function $H_{X,y}$.
Such an oracle can clearly be implemented using the LP \eqref{opt:densitylp}.
We also need a separation oracle for these superlevel sets, which is given in the following lemma:

\begin{lemma}[Efficient Separation] \label{lem:sep}
There exists a $\mathrm{poly}(n, d)$ time separation oracle for the superlevel sets of $H_{X,y}(x) = \exp(h_{X,y}(x))$.
\end{lemma}
\begin{proof}
To construct our separation oracle, we will rely on the covering LP that is dual to the packing LP used to evaluate a tent function.
The dual to the packing LP looks for the hyperplane that is above all the $(X_i,y_i)$
that has minimal $y$ at $x$. More specifically, it is the following LP:
\begin{lp} \label{eqn:covering-lp}
\mini{\beta_0 + \sum_{j=1}^d \beta_j x_j}
\mbox{subject to}  \con{\beta \in \mathbb{R}^{d+1}, \beta_0 + \sum_{j=1}^d \beta_j X_{i,j} \geq y_i, i \in [n]\;,}
\end{lp}
where $X_{i,j}$ is the $j$-th coordinate of the vector $X_i$.
Now suppose that we are interested in a super level set $L_{H_{X,y}}(l)$. We can use the above LP
to compute $h_{X,y}(x)$ (and thus $H_{X,y}(x)$) and check if it is in the superlevel set.
Suppose that it is not, then there will be a solution $\beta \in \mathbb{R}^{d+1}$
whose value is below $ \ln l$, say $ \ln l-\delta$ for some $\delta>0$. Consider an $x' $
in the halfspace $\beta_0 + \sum_{j=1}^d \beta_j x'_j \leq \ln l - \delta/2$ which has $x$ in the interior.
Since $x$ does not appear in the objective, $\beta$ is a feasible solution for the dual LP
\eqref{eqn:covering-lp} with $y, x'$, and so $h_y(x') \leq \ln l-\delta/2$, which implies that
$x'$  is not in the superlevel set. Therefore, $\beta_0 + \sum_j \beta_j x'_j = \ln l - \delta/2$
is a separating hyperplane for $x$ and the level set.
This completes the proof.
\end{proof}

\iffalse
\begin{lemma}[Efficient evaluation]
\label{lem:evaluate_Hy}
There exists a polynomial-time algorithm which given $y\in \mathbb{R}^n$ and $x\in \mathbb{R}^d$, computes $\exp(h_y(x))$.
\end{lemma}
\begin{proof}
The value $h_y(x)$ can be computed in polynomial time as the objective value of the following LP:
\begin{align*}
\text{maximize} & \sum_{i=1}^n \lambda_i y_i  \\
\text{subject to} & \lambda_i \in [0,1] & \text{ for all } i\in [n]\\
 & \sum_{i=1}^n \lambda_i x_i = x
\end{align*}
\end{proof}
\fi

Given all of the above ingredients, we are now ready to prove the main result of this section.

\begin{proof}[Proof of Lemma \ref{lem:sampling}]
We first prove part (1) of the assertion.
To that end we analyze the sampling procedure described in Algorithm \ref{alg:sampling}.
Recall that
$m=1+\lceil \|y\|_\infty\rceil$,
and for any $i\in [m]$, we define the superlevel set
\[
L_i = \{x\in \mathbb{R}^d : H_{X,y}(x) \geq M_{H_{X,y}} \cdot 2^{-i}\} \;.
\]
For any $x\in \mathbb{R}^d$ recall that
\[
G_{X,y}(x) = M_{H_{X,y}} 2^{-\lfloor \log_2(M_{H_{X,y}}/H_{X,y}(x)) \rfloor} \;.
\]
For any $A\subseteq \mathbb{R}^d$, let $\chi_A:\mathbb{R}^d\to\{0,1\}$ be the indicator function for $A$.
It is immediate that for all $x\in \mathbb{R}^d$,
\begin{align*}
G_{X,y}(x) &= M_{H_{X,y}} \sum_{i=1}^{\infty} 2^{-i} \chi_{L_i}(x) \\
 &= M_{H_{X,y}} \sum_{i=1}^m 2^{-i} \chi_{L_i}(x) + 2^{-m} \chi_{L_i}(m) & \text{(since $H_{X,y}(x)=0$ for all $x\notin L_m$)}
\end{align*}
Let
\[
c = \sum_{i=1}^m 2^{-i} \mathrm{vol}(L_i) + 2^{-m}  \mathrm{vol}(L_m).
\]
We have
\begin{align}
\int_{\mathbb{R}^d} G_{X,y}(x) \mathrm{d} x &= M_{H_{X,y}} \left(\sum_{i=1}^m 2^{-i} \mathrm{vol}(L_i) + 2^{-m}  \mathrm{vol}(L_m)\right) = M_{H_{X,y}} c. \label{eq:Gy_integral}
\end{align}
Let
\[
\widehat{G}_{X,y}(x) = G_{X,y}(x) / (M_{H_{X,y}} c).
\]
It follows by \eqref{eq:Gy_integral} that $\widehat{G}_{X,y}$ is a probability density function.

Let $D$ be the probability distribution on $\{1,\ldots,m\}$, where
\[
\mathrm{Pr}_{I\sim D}[I = i] = \left\{\begin{array}{ll}
\mathrm{vol}(L_i) \cdot 2^{-i} / c & \text{ if $i\in \{1,\ldots,m-1\}$}\\
2\cdot \mathrm{vol}(L_m) \cdot 2^{-m} / c & \text{ if $i=m$}
\end{array}\right.
\]
For any $i\in [m]$, let $u_i$ be the uniform probability density function on $L_i$.
To sample from $\widehat{G}_{X,y}$, we can first sample $I\sim D$, and then sample $Z\sim u_I$.

Recall that $\widehat{p}_{X,y}:\mathbb{R}^d \to \mathbb{R}_{\geq 0}$ is the probability density function obtained by normalizing $H_{X,y}$;
that is, for all $x\in \mathbb{R}^d$ we have
\[
p_{X,y}(x) = H_{X,y}(x) / c',
\]
where
\[
c' = \int_{\mathbb{R}^d} H_{X,y}(x) \mathrm{d} x.
\]
Consider the following random experiment:
first sample $Z\sim \widehat{G}_y$, and then accept with probability $H_{X,y}(Z)/G_{X,y}(Z)$; conditioning on accepting, the resulting random variable $Z\in \mathbb{R}^d$ is distributed according to $\widehat{H}_{X,y}$.
Note that since for all $x\in \mathbb{R}^d$, $G_{X,y}(x)/2 \leq H_{X,y}(x) \leq G_{X,y}(x)$, it follows that we always accept with probability at least $1/2$.
Let $\alpha$ be the probability of accepting.
Then
\begin{align*}
\alpha &= \int_{\mathbb{R}^d} \widehat{G}_{X,y}(x) (H_{X,y}(x)/G_{X,y}(x))  \mathrm{d} x,
\end{align*}
and thus
\begin{align}
\int_{\mathbb{R}^d} H_{X,y}(x) \mathrm{d} x &= \int_{\mathbb{R}^d} G_{X,y}(x) (H_{X,y}(x)/G_{X,y}(x)) \mathrm{d} x  \notag \\
 &= M_{H_{X,y}} c \int_{\mathbb{R}^d} \widehat{G}_{X,y}(x) (H_{X,y}(x)/G_{X,y}(x)) \mathrm{d} x \notag \\
 &= M_{H_{X,y}} c \alpha \label{eq:mass_Hy} \;.
\end{align}
By Theorem \ref{thm:KLS_volume}, for each $i\in [m]$, we compute an estimate, $\widetilde{\mathrm{vol}}(L_i)$, to  $\mathrm{vol}(L_i)$, to within relative error $\delta$, using $\mathrm{poly}(d, 1/\delta, \log(1/\tau'))$ oracle calls, with probability at least $\tau'$, where $\tau'=\tau/n^b$, for some constant $b>0$ to be determined;
moreover, by Theorem \ref{thm:KLS_sampling}, we can efficiently sample,
using $\mathrm{poly}(d, 1/\delta)$ oracle calls, from a probability distribution $\widetilde{u}_i$
with $\|u_i - \widetilde{u}_i\| \leq \delta$.
Each of these oracle calls is a membership query in some superlevel set of $H_{X,y}$.
This membership query can clearly be implemented
if we can compute that value $H_y$ at the desired query point $x$,
which can be done in time $\mathrm{poly}(n,d)$ using LP~\eqref{opt:densitylp}.
Thus, each oracle call takes time $\mathrm{poly}(n,d)$.
Let
\begin{align}
\widetilde{c} &= \sum_{i=1}^m 2^{-i} \widetilde{\mathrm{vol}}(L_i) + 2^{-m} \widetilde{\mathrm{vol}}(L_m). \label{eq:c_tilde}
\end{align}
Since for all $i\in [m]$, $\mathrm{vol}(L_i)/(1+\delta)\leq \widetilde{\mathrm{vol}}(L_i) \leq \mathrm{vol}(L_i) (1+\delta)$, it is immediate that
\[
c / (1+\delta) \leq \widetilde{c}\leq c (1+\delta) \;.
\]
Recall that Algorithm \ref{alg:sampling} uses the probability distribution $\widetilde{D}$ on $[m]$, where
\[
\mathrm{Pr}_{I\sim \widetilde{D}} [I = i] = \left\{\begin{array}{ll}
\widetilde{\mathrm{vol}}(L_i) \cdot 2^{-i} / \widetilde{c} & \text{ if $i\in \{1,\ldots,m-1\}$}\\
2 \cdot \widetilde{\mathrm{vol}}(L_m) \cdot 2^{-m} / \widetilde{c} & \text{ if $i=m$}
\end{array}\right.
\]
Consider the following random experiment, which corresponds to Steps 5--6 of Algorithm \ref{alg:sampling}:
We first sample $I\sim \widetilde{D}$, and then we sample $Z\sim \widetilde{u}_I$.
The resulting random vector $Z\in \mathbb{R}^d$ is  distributed according to
\[
 \widetilde{G}_{X,y}(x) = \frac{1}{\widetilde{c}} \left ( \sum_{i=1}^m 2^{-i} \widetilde{\mathrm{vol}}(L_i) \widetilde{u}_i(x) + 2^{-m}  \widetilde{\mathrm{vol}}(L_m) \widetilde{u}_m(x) \right).
\]

Next, consider the following random experiment, which captures Steps 5--8 of Algorithm \ref{alg:sampling}:
We sample $Z\sim \widetilde{G}_{X,y}$, and we accept with probability $H_{X,y}(Z)/G_{X,y}(Z)$.
Let $\widetilde{H}_{X,y}$ be the resulting probability density function supported on $\mathbb{R}^d$ obtained by conditioning the above random experiment on accepting.
Let $\widetilde{\alpha}$ be the acceptance probability.
We have
\[
 \widetilde{\alpha} =\int_{\mathbb{R}^d} (H_{X,y}(x)/G_{X,y}(x)) \widetilde{G}(x) \mathrm{d} x.
\]

We have
\begin{align*}
\|D_i - \widetilde{D}_i\|_1 &= \sum_{i=1}^{m-1} 2^{-i} \cdot \left|\frac{\mathrm{vol}(L_i)}{c}-\frac{\widetilde{\mathrm{vol}}(L_i)}{\widetilde{c}}\right| + 2 \cdot 2^{-m} \cdot \left|\frac{\mathrm{vol}(L_m)}{c}-\frac{\widetilde{\mathrm{vol}}(L_m)}{\widetilde{c}}\right|\\
 &= \sum_{i=1}^{m-1} 2^{-i} \cdot \left|\frac{\mathrm{vol}(L_i)}{c}-\frac{\mathrm{vol}(L_i)(1+\delta)}{c/(1+\delta)}\right| + 2 \cdot 2^{-m} \cdot \left|\frac{\mathrm{vol}(L_m)}{c}-\frac{\mathrm{vol}(L_m)(1+\delta)}{c/(1+\delta)}\right|\\
 &\leq \sum_{i=1}^{m-1} 2^{-i} \frac{\mathrm{vol}(L_i)}{c} 3\delta + 2 \cdot 2^{m} \frac{\mathrm{vol}(L_m)}{c} 3\delta \\
 &= 3\delta.
\end{align*}
It follows that
\begin{align*}
\|\widehat{G}_{X,y} - \widetilde{G}_{X,y}\|_1 &\leq \|D_i - \widetilde{D}_i\| + \max_i \| u_i-\widetilde{u}_i\|_1 \leq 3\delta + \delta \leq 4 \delta,
\end{align*}
and so
\[
|\alpha-\widetilde{\alpha}| \leq \int_{\mathbb{R}^d} \frac{H_{X,y}(x)}{G_{X,y}(x)} \left|\widehat{G}_{X,y}(x) - \widetilde{G}_{X,y}(x)\right| \mathrm{d} x \leq \int_{\mathbb{R}^d} \left|\widehat{G}_{X,y}(x) - \widetilde{G}_{X,y}(x)\right| \mathrm{d} x \leq \|\widehat{G}_{X,y} - \widetilde{G}_{X,y} \|_1 \leq 4 \delta.
\]
Note that $p_{X,y}(x)/\alpha = \widehat{G}_{X,y}(x) \frac{H_{X,y}(x)}{G_{X,y}(x)}$ and $\widetilde{H}_{X,y}(x)/\widetilde{\alpha} = \widetilde{G}_{X,y}(x) \frac{H_{X,y}(x)}{G_{X,y}(x) }$
and so
\begin{align*}
\|\widetilde{H}_{X,y} - p_{X,y}\|_1 &\leq \alpha \left(\|\widetilde{H}_{X,y}/\alpha - p_{X,y}/\alpha\|_1 + \|p_{X,y}/\widetilde{\alpha} - p_{X,y}/\alpha\|_1\right) & \text{(by the triangle inequality)}\\
 &= \alpha \left(\|\widetilde{H}_{X,y}/\alpha - p_{X,y}/\alpha \|_1 + |1/\widetilde{\alpha} - 1/\alpha|\right) \\
 &= \alpha \int_{\mathbb{R}^d} (H_{X,y}(x)/G_{X,y}(x)) | \widetilde{G}_{X,y}(x) - p_{X,y}(x) | + |\alpha - \widetilde{\alpha}|/\widetilde{\alpha} \\
 &\leq \|p_{X,y} - \widetilde{G}_{X,y} \|_1 + 2 |\alpha - \widetilde{\alpha}| \\
 &\leq 12 \delta,
\end{align*}
which establishes that the random vector $Z$ that Algorithm \ref{alg:sampling}
outputs is distributed according to a probability distribution
$\widetilde{\phi}$ such that $\|\widetilde{\phi}-p_{X,y}\|_1\leq 10\delta$, as required.

In order to bound the running time, we observe that all the steps of the algorithm
can be implemented in time $\mathrm{poly}(n, d, \|y\|_\infty, 1/\delta, \log(1/\tau))$. The most expensive
operation is approximating the volume of a superlevel set $L_i$ and sampling for $L_i$,
using Theorems \ref{thm:KLS_volume} and \ref{thm:KLS_sampling}.
By the above discussion, using LP \eqref{opt:densitylp} and Lemma \ref{lem:sep}
each of these operations can be implemented in time $\mathrm{poly}(n, d, 1/\delta,\log(1/\tau))$.
The algorithm succeeds if all the invocations of the algorithm of Theorem \ref{thm:KLS_volume}
are successful; by the union bound, this happens with probability
at least $1-\tau'\mathrm{poly}(n) = 1-\tau' n^b \mathrm{poly}(n) \geq 1-\tau$,
where the inequality follows by choosing some sufficiently large constant $b>0$.
This establishes part (1) of the Lemma.

It remains to prove part (2).
By \eqref{eq:mass_Hy} we have that $\gamma = M_{H_{X,y}} c \alpha$.
Algorithm ${\cal A}_2$ proceeds as follows.
First, we compute $M_{H_{X,y}}$.
By the convexity of $h_{X,y}$, it follows that the maximum value of $M_{H_{X,y}}$
is attained on some sample point $x_i$; that is,
$M_{H_{X,y}} = \max_{i\in [n]} H_{X,y}(x_i)$.
Since we can evaluate $H_y$ in polynomial time using
LP \eqref{opt:densitylp}, it follows that we can also compute $M_{H_{X,y}}$ in polynomial time.
Next, we compute $\widetilde{c}$ using formula \ref{eq:c_tilde}.
Arguing as in part (1), this can be done in time $\mathrm{poly}(n, 1/\delta, \log(1/\tau))$, and with probability at least $1-\tau/2$.
Finally, we estimate $\widetilde{\alpha}$.
The value of $\widetilde{\alpha}$ is precisely the acceptance probability of the random experiment described in Steps 5--8 of Algorithm \ref{alg:sampling}.
Since $\alpha\geq 1/2$, and $|\alpha-\widetilde{\alpha}| \leq 4\delta$, it follows that for $\delta<1/16$, we can compute an estimate $\bar{\alpha}$ of the value of $\widetilde{\alpha}$, to within error $1+O(\delta)$,
with probability at least $1-\tau/2$, after $O(\log(1/\tau))$ repetitions of the random experiment.
The output of algorithm ${\cal A}_2$ is $\gamma'=M_{H_{X,y}} \widetilde{c} \bar{\alpha}$.
We obtain that, with probability at least $1-\tau$, we have
\[
\gamma' = M_{H_{X,y}} \widetilde{c} \bar{\alpha}  \leq M_{H_{X,y}} c (1+\delta) \alpha (1+O(\delta))  = \gamma (1+O(\delta)) \;,
\]
and
\[
\gamma' = M_{H_{X,y}} \widetilde{c} \bar{\alpha}  \geq M_{H_{X,y}} (c / (1+\delta)) ( \alpha /(1+O(\delta)) ) = \gamma / (1+O(\delta)) \;,
\]
which concludes the proof.
\end{proof}

\section{Conclusions} \label{sec:conc}
In this paper, we gave a $\mathrm{poly}(n, d, 1/\epsilon)$ time
algorithm to compute an $\epsilon$-approximation of the log-concave
MLE based on $n$ points in $\mathbb{R}^d$. Ours is the first algorithm
for this problem with a sub-exponential dependence in the dimension $d$.
We hope that our approach may lead to more practical methods for computing
the log-concave MLE in higher dimensions than was previously possible.

One concrete open question is whether there exists an algorithm for computing the log-concave MLE that runs in time
$\mathrm{poly}(n, d, \log(1/\epsilon))$, instead of the $\mathrm{poly}(n, d, 1/\epsilon)$ that we achieve. Such an algorithm would likely be technically interesting as it may require going beyond the first-order methods we employ.  More broadly, it seems worth investigating whether the MLE can be efficiently computed for other natural classes of non-parametric distributions.  Alternately, one could hope that there is a simple set of natural properties such that, if a class of distributions satisfies those properties, then the MLE can be efficiently computed.

\medskip

\noindent {\bf Acknowledgments:}
Ilias Diakonikolas was supported by NSF Award CCF-1652862 (CAREER) and a Sloan Research Fellowship. Alistair Stewart was supported by a USC startup grant. Anastasios Sidiropoulos was supported by NSF Award CCF-1453472 (CAREER) and NSF grants CCF-1423230 and CCF-1815145. Brian Axelrod was supported by NSF Fellowship grant DGE-1656518, NSF award CCF-1763299, and a Finch family fellowship. Brian Axelrod and Gregory Valiant were supported by NSF awards CCF-1704417, and an ONR Young Investigator Award (N00014-18-1-2295).

\bibliographystyle{plainnat}

redpajama_set_name: RedPajamaArXiv


Is the DCEU in Trouble? - Are You Not Entertained?
You know who couldn't wait for 2016 to end? WB studios that's who, boy could they not wait for the year to end. Last year wasn't great for WB and their DCEU, well maybe financially, but in terms of how critics and fans alike felt about their movies is a whole other story. Batman v. Superman and Suicide Squad both failed to earn a 'fresh' rating on Rotten Tomatoes, and BvS led all other movies in Razzie nominations (these are awards for the worst movies of the year).
WB always had one trump card up their sleeve though. Ben Affleck, the goddamn Batfleck, was set to direct his very own standalone Batman movie, and boy was it going to be glorious. Starting in early 2017, right around the time Ben's latest movie (Live By Night) was set to premier, it sounded like Ben was getting cold feet. He kept saying things like "the scripts not ready," "I'm not doing this, until things are perfect," and finally early this week news broke that Ben was no longer going to direct Batman. When this news broke the world LOST ITS MIND. Honestly that is the one-thing DC fans had over Marvel, that unlike Marvel, DC was going to have the Oscar winner Ben Affleck directing a standalone Batman movie. Not only is he not directing, there are whispers that he may be out all together as the caped crusader. If that happens, honestly I'm not sure what WB should do about their already fragile DCEU. The standalone Flash movie has already lost three directors (THREE!!!!), and now is getting a page one rewrite. What the hell is going on? These characters and their movies should pretty much write themselves. How much source material do you really need to write a good script? The thing that the DCEU needs is a godfather, Marvel has Kevin Feige and the WB TV division has Greg Berlanti. Both of these guys care about not only the characters, but also the fans. They have a vision of where things should go, and the DCEU is missing that. I don't know if it should be Geoff Johns, Zack Snyder, but they need to get someone in there fast, and clean this mess up. Someone who cares and loves these characters, and that has some idea of where they would like to see this universe go.
Here's the thing, Man of Steel was a great movie, I personally think it was a solid way to kick of this new DCEU, but ever since, WB has tried to play catch up to Marvel. Shoveling so much crap down our throats in BvS. Rome was not built in a day, and neither should comic book universes. They had the new Batman, Wonder Woman, Lex Luthor, Doomsday, and small little cameos from Aquaman, Flash and Cyborg ALL IN THE SAME MOVIE!? They really rushed it, not to mention throwing in the greatest comic book showdown ever between Batman and Superman, which again you had so much source material for and as Billy Madison would say, "YOU BLEW IT"! Oh, and to top it all off, they decided to put in the death of Superman at the end of the movie, just for shits and giggles I guess.
Next up Suicide Squad, which WB promised would be lighter in tone and fun. The trailers made this movie look awesome, but my god towards the end of the movie, it was really hard to sit through. To this day I have only seen it once. Back to back stinkers in a span of 4 months, meanwhile Marvel is crushing it.
Do I think Affleck leaving the directors chair is the end of the world? No. What I think is, he's got a lot going on not only in his work life but in his personal life as well. Maybe he feels that WB is rushing this process and he doesn't want all the blame going onto his shoulders if this thing falls apart. This could actually be a blessing in disguise for the movie. WB is going to hire an A+ director for this project (please god let it be either David Fincher or George Miller) and they could really work well with Ben (who is still writing, producing and starring in this thing by the way). WB just needs to make some fast moves here and replace Ben as director as fast as possible. There is just too much stink on this movie right now, and it could use a dose of good news, before things somehow get even worse. So not all hope can be lost, just because Ben isn't directing anymore. In a year from now, when this movie is ready to released, we all might look back on this and have a nice Joker power laugh about it.
Another reason why I don't think the DCEU is doomed quite yet. That reason is Aquaman, the savior of the DCEU people! Look the cast is fantastic (Jason Mamoa, Patrick Wilson, Amber Heard, Nicole Kidman), James Wan is directing and he did wonders for the Fast and Furious franchise, and I feel pretty confident that he is going to pull this thing off. Aquaman is no joke; he's actually one of the coolest, most badass superheroes in comics today. Read Geoff Johns New 52 comic book run if you don't believe me. Also another amazing thing about Aquaman, we will get to see Black Manta, one of my favorite DC villains of all time. That's right, fish bowl head is awesome and I don't care who knows it. Just look at a photo if you have no clue what I'm talking about.
Look, this could all really fall apart, if Wonder Woman and Justice League don't finally turn this ship around. There is immense pressure on both of these movies, not only to succeed financially but critically as well. I pray one of the reasons Ben didn't drop out is because he knows deep down, that the DCEU is already doomed. If they are both great, this will all be a thing of the past, and no one will care. I have faith in both of these movies, especially Wonder Woman. Zack Snyder is so hit or miss, that I can be supremely confident about Justice League until I have sat in a theatre and watched it. I guess we will all know the answers November 18th.
So take a deep breath people, relax. Remember at the end of the day, these are just movies, I know we all want them to kickass and blow our minds, and theres potential for this to happen. All we can do in the mean time is sit back, and enjoy all the great movies coming out in 2017!
Until then, you'll be seeing more posts about the DCEU!
The whole Ben Affleck as director has been a scary story. I was insanely pumped about it myself. I mean, after his performance in BvS, I just couldn't wait to see more of the guy. I also thought it was a marvelous opportunity for him to direct the movie he stars in after having directed some really amazing ones in the recent years. Leaving the director seat might seem bad, but as long as he co-produces and stars in it, alongside a great director (someone like David Fincher or George Miller indeed), I'll still have hope for the next Batman movie.
I'm going to continue to stay optimist about the whole DCEU even if there's a lot of haters out there on that universe. Great post!


B.Ed Handicapped - Public schools were required to evaluate handicapped children and create an educational plan with parent input that would emulate as closely as possible the educational experience of non-disabled students.The act also required that school districts provide administrative procedures so that parents of disabled children could dispute decisions made about their children's education. Once the administrative efforts were exhausted, parents were then authorized to seek judicial review of the administration's decision. Prior to the enactment of EHA, parents could take their disputes straight to the judiciary under the Rehabilitation Act of 1973. The mandatory system of dispute resolution created by EHA was an effort to alleviate the financial burden created by litigation pursuant to the Rehabilitation Act.


text:
Twin States Forge Ahead on Separate Paths (Valley News)
In its coverage of the U.S. Supreme Court's decision to uphold the Affordable Care Act, the Valley News turned to James Weinstein, the chief executive officer of Dartmouth-Hitchcock, for his reactions and insights on the ruling.
Weinstein, as the Valley News points out, helped write portions of the Affordable Care Act. "The big issue here is that [the Supreme Court's decision] is fantastic, that there's a lot of things in the bill that were really good and were never questioned," Weinstein told the Valley News. "But I still think this country has an awful lot of work to do if we're going to really lower the cost of health care and improve the quality."
Read the full story, published on 6/29/12 by the Valley News.
Dartmouth-Hitchcock Medical Center
Grant Supports Undergraduate's Global Health Translation App
A project by Tinotenda Kuretu '22 has been selected by the Verizon/Clinton Global Initiative.

redpajama_set_name: RedPajamaCommonCrawl


text:
Q: Converting Month name to full date pandas My df is like this
import pandas as pd
import numpy as np

df = pd.DataFrame({'Date data':['actual september 2019', 'September'],
                   'Date':['2019.12','2019.12']})

I would like to create a new columne and if df['Date data'] is 'September' I would like to write df['new_column'] = '2019.09'
the expected output is
import pandas as pd
import numpy as np

df = pd.DataFrame({'Date data':['actual september 2019', 'September'],
                   'Date':['2019.12','2019.12'], 'New_column':['2019.12','2019.09']})

i created a variable
month = ('April', 'December', 'February', 'January', 'July-August', 'June', 'March', 'May', 'November', ' October', 'September')
and
 df.loc[df['Date data'].isin(month) , 'new_col'] = '2019.9

A: IIUC, you want to create a new column similar to Date. Rows where Date data is equal to a month I change the column number in Date and put it in the new column.
If all months start with a capital letter (easy):
months = ['January', 'February', 'March', 'April', 'May', 'June', 'July', 'August', 'September', 'October', 'November', 'December']
df['New_column'] = df['Date']
for nr, month in enumerate(months):
    df.loc[df['Date data'].eq(month), 'New_column'] = df['Date'].str[:5] + str(nr + 1).zfill(2)

If months can be with or without capital letter, use .lower():
months = ['january', 'february', 'march', 'april', 'may', 'june', 'july', 'august', 'september', 'october', 'november', 'december']
df['New_column'] = df['Date']
for nr, month in months:
    df.loc[df['Date data'].str.lower().eq(month), 'New_column'] = df['Date'].str[:5] + str(nr + 1).zfill(2)

Output:
               Date data     Date New_column
0  actual september 2019  2019.12    2019.12
1              September  2019.12    2019.09

A: IIUC, you can use:
from calendar import month_name

mapper = {m.lower(): f'{i:02d}' for i,m in enumerate(month_name)}

df['New_column'] = (df['Date data'].str.lower()
                    .map(mapper)
                    .radd('2019.')
                    .fillna(df['Date'])
                    )

example:
               Date data     Date New_column
0  actual september 2019  2019.12    2019.12
1              September  2019.12    2019.09
2                  ApRil  2019.12    2019.04

redpajama_set_name: RedPajamaStackExchange


A Core Facility for Academic, Industry and Government Research.
Gateway University Research Park. Businesses Begin Here.
Gateway and JSNN work with corporate partners and academic units to create joint R&D projects and spin-off opportunities that are co-located with the academic units on the Gateway campuses.
Nanotechnology is often referred to as convergent technology because it utilizes knowledge from a diverse array of disciplines including biology, chemistry, physics, engineering, and technology. JSNN has six research focus areas—nanobioscience, nanometrology, nanomaterials (with special emphasis on nanocomposite materials), nanobioelectronics, nanoenergy, and computational nanotechnology.
The Joint School of Nanoscience and Nanoengineering (JSNN) mission is to be a catalyst for breakthrough innovations that provide high-impact academic, industry and government research outcomes.
Build-to-suit construction of your new office space or building can be handled by Gateway or alongside trusted contractors. We can provide development services such as ground-up construction, tenant improvement projects and fit-ups, construction management services, design and space planning, renovations, and LEED building options.
Created as a partnership between the Institute for Electronics and Nanotechnology at the Georgia Institute of Technology and the Joint School of Nanoscience and Nanoengineering (JSNN) to provide researchers from academia, small and large companies and government with access to university user facilities with leading-edge fabrication and characterization tools, instrumentation, and expertise within all disciplines of nanoscale science, engineering and technology.
Master of Science in Nanoengineering degree program is a research degree, featuring coursework involving engineering at the nanoscale. For students with a strong background in engineering seeking industrial or government positions utilizing nanotechnology.
The Ph.D. in nanoengineering requires a minimum of 54 credit hours beyond MS degree and is designed to prepare students to take positions in industrial, governmental, or academic research settings by providing a solid background in nanoengineering theory and experimental techniques through course work, laboratory rotations and dissertation research.
Professional Science Master's degree is designed for students with strong background in technical fields who seek additional specialized training to qualify them for positions in companies that work in the field of nanotechnology.
The Ph.D. in nanoscience is designed to prepare students to take positions in industrial, governmental, or academic research settings by providing a solid background in nanoscience theory and experimental techniques through course work and dissertation research.
By joining NIC as a member I added 65 Million dollars of assets to my company. I hired a Ph.D. scientist to work on research and development at JSNN, and in doing so, I was the first to create a job because of the NIC.
I have been to hundreds of facilities and seen thousands of students and there is nothing like the Joint School.


text:
Home » Connect » From the President » Past Messages
Contact: norms@wxxi.org
Sharing the work of Albert Paley with art lovers across the country
By Norm Silverstein ~ Posted Mon, 12/16/2013 - 9:36am
Paley on Park Avenue: New York City, WXXI's hour-long documenary that follows world-renowned sculptor, Albert Paley, as he creates 13 original sculptures for The Fund for Park Avenue's Temporary Public Art Collection in New York City, received such praise from viewers when it premiered on WXXI-TV Thursday, December 12 that we're presenting an encore broadcast Monday, December 16 at 8 p.m. It's also archived on the web at WXXI.org/paleynyc/live for art lovers and Paley fans across the country.
You may remember last May when WXXI launched its first multi-media series that followed world-renowned sculptor Albert Paley as he created 13 original pieces for installation on Park Avenue in New York City. The six-part web-only series shared the behind-the-scenes story. After the installation in mid-June, WXXI's production team continued to shoot the sculptures and events surrounding the project, while capturing personal stories about Paley and his work from Paley himself, as well as his wife Frances, his staff, and community leaders.
Now you can witness the culmination of one of the most ambitious projects that any sculptor in the Fund for Park Avenue's Temporary Public Art Collection has undertaken in Paley on Park Avenue: New York City. The documentary, narrated by two-time Emmy Award winning journalist, artist, and photographer Jay Schadler, will also airs on PBS stations across the country this winter.
Albert Paley
Jay Schadler
Paley on Park Avenue: New York City
The Fund for Park Avenue


An engaging scheme to turn attention to gum disease has launched this week.
The British Society of Periodontology (BSP) hopes to raise the profile of the condition among dental professionals as well as the general public.
Part of a Europe-wide campaign from the European Federation of Periodontology (EFP), new guidelines will advise dentists to examine the gums of every patient over the next two years and perform treatment as a matter of course.
Professor Iain Chapple, head of periodontology at the University of Birmingham and EFP treasurer, calls the condition a "silent disease", and therefore all the more important to address quickly.
The BSP will be targeting dental surgeries in the near future, making sure that dentists and members of the public know the importance of periodontic care.
Shocking figures suggest that eight out of ten people over 35 experience gum complaints, which could have links with diabetes and cardio health.
Such close links with other health conditions could see a rise in dental professionals working closely with cardiologists to spot heart complaints in their early stages.
Dentists should make patients aware of the long-term effects that gum disease can have on oral health and hygiene. A simple dental poster in a practice waiting room could raise awareness of important risk factors.
Although many people are aware of the effects of gum disease, it is worthwhile reinforcing some of the major causes to highlight this important message from the BSP.


text:
Turowo (deutsch Steinau; kaschubisch Tùrowò) ist ein Dorf in der  Woiwodschaft Pommern in Polen. Es gehört zur Gmina Miastko (Gemeinde Rummelsburg) im Powiat Bytowski (Bütower Kreis).

Geographische Lage
Das Dorf liegt in der Pojezierze Bytowski (Bütower Seenplatte) zwischen der früheren Kreisstadt Miastko (Rummelsburg) und der jetzigen Kreisstadt Bytów (Bütow). Eine Nebenstraße führt von Role (Grünwalde) kommend nach Kramarzyny (Kremerbruch), das direkt an der polnischen Landesstraße 20 (ehemalige deutsche Reichsstraße 158) liegt.

Zwischen 1909 und 1945 hatte Steinau über die sechs Kilometer entfernte Station Kremerbruch Anschluss an die Bahnstrecke Bütow–Rummelsburg.

Ortsname
Die Bezeichnung "Steinau" ist ein in Deutschland geläufiger und mehrfach vorkommender Ortsname, nicht weniger als der Name "Turowo" in Polen.

Geschichte
Steinau wurde nach 1843 als ein Vorwerk von Grünwalde angelegt, gleichzeitig wurden einige sogenannte Buschkaten aufgegeben. Das Puttkamersche Gut Grünwalde gehörte damals einer Thekla von Puttkamer, geborene von Oßmann, die es 1840 von ihrem Schwiegervater gekauft hatte. Im Jahre 1905 wurde das Vorwerk Steinau in 15 Rentensiedlungen aufgeteilt. Der Resthof mit 46 Hektar Land blieb bei der Familie von Puttkamer.

1901/08 wurde Steinau eine eigene Landgemeinde.Landkreis Rummelsburg bei gemeindeverzeichnis.de.  Bis 1945 bildete Steinau eine Landgemeinde im Kreis Rummelsburg der preußischen Provinz Pommern. In der Landgemeinde wurden neben Steinau die Wohnplätze Fuchskaten und Pferdebude geführt. Die Gemeinde zählte im Jahre 1910 139 Einwohner, im Jahre 1925 160 Einwohner in 23 Haushaltungen,   und im Jahre 1939 158 Einwohner.

Nach dem Zweiten Weltkrieg kam Steinau an Polen. Der Ortsname wurde zu "Turowo" polonisiert. Hier leben jetzt etwas mehr als 100 Einwohner.

Kirche
Die bis 1945 vorwiegend evangelischen Einwohner von Steinau gehören zu einem von insgesamt zwölf Orten, die in das Kirchspiel Waldow (heute polnisch: Wałdowo) eingepfarrt waren. Es gehörte zum Kirchenkreis Rummelsburg (Miastko) im Ostsprengel der Kirchenprovinz Pommern der Kirche der Altpreußischen Union.

Seit 1945 ist die Bevölkerung von Turowo überwiegend katholischer Konfession. Das Dorf gehört nun zur Kirchengemeinde Wałdowo (Waldow), die in die Pfarrei Piaszczyna (Reinwasser) eingegliedert ist. Sie liegt im Dekanat Miastko im Bistum Köslin-Kolberg der Katholischen Kirche in Polen.

Hier lebende evangelische Kirchenglieder sind der Kreuzkirchengemeinde in Słupsk (Stolp) zugeordnet, deren nächstes Filialkirchdorf Wołcza Wielka (Groß Volz) südwestlich von Miastko liegt. Sie ist Teil der Diözese Pommern-Großpolen der Evangelisch-Augsburgischen Kirche in Polen.

Siehe auch
 Liste der Orte in der Provinz Pommern

Literatur
 Der Kreis Rummelsburg. Ein Heimatbuch. Hamburg 1979, S. 160–161 (bei Grünwalde).

Weblinks

 Steinau bei Meyers Gazetteer (mit historischer Landkarte)
 Steinau auf der Webseite des Verbandes des Geschlechtes v. Puttkamer

Einzelnachweise

Ort in Pommern
Ort der Woiwodschaft Pommern
Gmina Miastko

redpajama_set_name: RedPajamaWikipedia


text:
@LaurelPIO
Audrey Barnes
Audrey Barnes is an Emmy Award winning journalist with more than 30 years of television news experience.
She is currently the Director of Communications for the City of Laurel, Maryland.
One of her primary functions is to oversee the operation of the Laurel TV public access television station.
Audrey brings a wealth of television experience to her new position. She has been a Reporter and Anchor at TV stations in five states, and at three stations in Washington DC, most recently at WTTG TV.
She was one of the first reporters to reach the Pentagon on September 11, 2001 and considers the work she did that day some of her finest.
Ms. Barnes is looking forward to making Laurel TV the first place local residents will turn to for the news they need every day.
‹ Communications
News and Press Releases ›


The Complete Word Study Dictionary: Old Testament is the final volume in AMG's Complete Word Study Series. These Bible study tools are designed to make the original languages of the Bible accessible to every student of the Word of God. This lexicon is a companion volume to The Complete Word Study Old Testament, which identifies the words of the Hebrew text of the Old Testament by the placement of Strong's numbers and grammatical codes over the English text. Together these two volumes represent the Old Testament portion of this series.
Dr.Warren Baker is the Senior Editor of AMG Publishers in Chattanooga, Tennessee. He is the general editor of The Complete Word Study Old Testament. He also served as managing editor of The Complete Word Study New Testament and The Complete Word Study Dictionary: New Testament, and as series editor for The Hebrew-Greek Key Word® Study Bible. Dr. Baker holds several degrees: B.A., Clearwater Christian College; M.Div., S.T.M., and D.R.E., Faith Theological Seminary. He served as Assistant Professor of Old Testament at Faith Seminary until he began his career in Christian publishing more than twenty years ago.
Dr. Eugene Carpenter was the Scholar-in-Residence and Professor of Old Testament, Biblical Theology and Hebrew at Bethel College in Mishawaka, Indiana. Dr. Carpenter authored or contributed to twenty-one books, including a commentary on the Book of Exodus in the NICOT Series and a commentary on the Book of Daniel.
Dr. Carpenter held several degrees: B.A., Bethel College; M.Div., Associated Mennonite Biblical Seminary; Ph.D. in Old Testament and Semitic Studies, Fuller Theological Seminary. He taught at colleges and seminaries around the country. He regularly led academic study trips to Jerusalem University College in Israel.


Help Fund The Department of Geosciences' Educational and Research Efforts!
Gifts like yours help the department in many ways such as funding departmental seminars by outstanding scientists, assisting graduate and undergraduate research and helping new faculty establish their research programs. In addition to contributions ear-marked for a specific purpose, general support helps make it possible for us to continue activities that enrich our educational and research programs.
The Department of Geosciences promotes interdisciplinary approaches to solve problems in the earth sciences and geography. Our faculty are internationally recognized for research in numerous disciplines in both geology and geography.
We believe that innovative and effective instruction goes hand in hand with basic research. The Department is continually seeking to acquire the most advanced instrumentation for its laboratory courses so that students will receive the best possible training. We currently have fifteen active labs, of which three have been added within the last five years. The laboratory course offerings to major and non-majors are viewed by students as important training for independent research projects, preparation for graduate school and for jobs in the geosciences. We are particularly proud of the students who conduct research in faculty laboratories. Their contributions are evident from the many publications that have resulted from research conducted in part by both graduate students and undergraduates.
You may also wish to directly fund department scholarships, student research, or student travel grants. Please contact the Department Head, Julie Brigham-Grette for details.
Visit the University of Massachusetts online donations web site, which will bring you to the Geosciences contributions page, and fill in the form.
Please note that if you want to contribute to a specific Geosciences fund, you will have to click on the "Click here for more options!" link, and scroll about 2/3rds of the way down the list to the Department of Geosciences and click on the drop-down menu.


Discussion in 'iPhone Tips, Help and Troubleshooting' started by jmj, Dec 8, 2010.
Today I received an invoice from Apple for $15 for 6 or 7 apps that I didn't purchase. The strange thing is these apps are in my iTunes under available downloads.
At any rate, I'm assuming this is the downside of a jailbreak. Have a 3G and am on 4.1 and used redsn0w to jb.
I emailed Apple. We'll see if they credit my account.
How is jailbreaking responsible for your account getting hacked?
I just jb for the first time a few weeks and have never had a single issue prior to that. Maybe it's not linked but it does seem like quite the coincidence.
He's brainwashed by Steve Jobs.
there is no way anything to do with JB could download an app from the app store, sign in with username and password. sounds like maybe a spouse, a kid, or a drunk iPhone owner to me "hacked" your iPhone!
out of thousands of JB'ers this is the first time this has been said. not the coinsidence!
JB has nothing to do with your itunes account beeing hacked.
Take your tinfoil hat off.