Exact objectives of random linear programs and mean widths of random
polyhedrons
- URL: http://arxiv.org/abs/2403.03637v1
- Date: Wed, 6 Mar 2024 11:51:52 GMT
- Title: Exact objectives of random linear programs and mean widths of random
polyhedrons
- Authors: Mihailo Stojnic
- Abstract summary: We consider emphrandom linear programs (rlps) as a subclass of emphrandom optimization problems (rops)
Our particular focus is on appropriate linear objectives which connect the rlps to the mean widths of random polyhedrons/polytopes.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider \emph{random linear programs} (rlps) as a subclass of
\emph{random optimization problems} (rops) and study their typical behavior.
Our particular focus is on appropriate linear objectives which connect the rlps
to the mean widths of random polyhedrons/polytopes. Utilizing the powerful
machinery of \emph{random duality theory} (RDT) \cite{StojnicRegRndDlt10}, we
obtain, in a large dimensional context, the exact characterizations of the
program's objectives. In particular, for any
$\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}\in(0,\infty)$, any unit vector
$\mathbf{c}\in{\mathbb R}^n$, any fixed $\mathbf{a}\in{\mathbb R}^n$, and $A\in
{\mathbb R}^{m\times n}$ with iid standard normal entries, we have
\begin{eqnarray*}
\lim_{n\rightarrow\infty}{\mathbb P}_{A} \left ( (1-\epsilon)
\xi_{opt}(\alpha;\mathbf{a})
\leq \min_{A\mathbf{x}\leq \mathbf{a}}\mathbf{c}^T\mathbf{x} \leq
(1+\epsilon) \xi_{opt}(\alpha;\mathbf{a}) \right ) \longrightarrow 1,
\end{eqnarray*}
where
\begin{equation*} \xi_{opt}(\alpha;\mathbf{a}) \triangleq \min_{x>0}
\sqrt{x^2- x^2 \lim_{n\rightarrow\infty} \frac{\sum_{i=1}^{m} \left (
\frac{1}{2} \left (\left ( \frac{\mathbf{a}_i}{x}\right )^2 + 1\right )
\mbox{erfc}\left( \frac{\mathbf{a}_i}{x\sqrt{2}}\right ) -
\frac{\mathbf{a}_i}{x} \frac{e^{-\frac{\mathbf{a}_i^2}{2x^2}}}{\sqrt{2\pi}}
\right )
}{n} }. \end{equation*}
For example, for $\mathbf{a}=\mathbf{1}$, one uncovers
\begin{equation*}
\xi_{opt}(\alpha)
=
\min_{x>0} \sqrt{x^2- x^2 \alpha \left ( \frac{1}{2} \left ( \frac{1}{x^2} +
1\right ) \mbox{erfc} \left ( \frac{1}{x\sqrt{2}}\right ) - \frac{1}{x}
\frac{e^{-\frac{1}{2x^2}}}{\sqrt{2\pi}} \right ) }. \end{equation*}
Moreover, $2 \xi_{opt}(\alpha)$ is precisely the concentrating point of the
mean width of the polyhedron $\{\mathbf{x}|A\mathbf{x} \leq \mathbf{1}\}$.
Related papers
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization.
Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires.
We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
arXiv Detail & Related papers (2024-06-07T08:26:31Z) - Capacity of the Hebbian-Hopfield network associative memory [0.0]
In citeHop82, Hopfield introduced a emphHebbian learning rule based neural network model and suggested how it can efficiently operate as an associative memory.
We study two famous pattern's basins of attraction: textbfemph(i) The AGS one from citeAmiGutSom85; and textbfemph(ii) The NLT one from citeNewman88,Louk94,Louk94a,Louk97,Tal
arXiv Detail & Related papers (2024-03-04T10:10:23Z) - Provably learning a multi-head attention layer [55.2904547651831]
Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models.
In this work, we initiate the study of provably learning a multi-head attention layer from random examples.
We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
arXiv Detail & Related papers (2024-02-06T15:39:09Z) - Convergence Rates of Stochastic Zeroth-order Gradient Descent for \L
ojasiewicz Functions [6.137707924685666]
We prove convergence rates of Zeroth-order Gradient Descent (SZGD) algorithms for Lojasiewicz functions.
Our results show that $ f (mathbfx_t) - f (mathbfx_infty) _t in mathbbN $ can converge faster than $ | mathbfx_infty.
arXiv Detail & Related papers (2022-10-31T00:53:17Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss
Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$ [0.24366811507669117]
Let $mathcalM$ be a compact $d$-dimensional submanifold of $mathbbRN$ with reach $tau$ and volume $V_mathcal M$.
We prove that a nonlinear function $f: mathbbRN rightarrow mathbbRmm exists with $m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math
arXiv Detail & Related papers (2022-06-07T15:10:46Z) - Matrix concentration inequalities and efficiency of random universal
sets of quantum gates [0.0]
For a random set $mathcalS subset U(d)$ of quantum gates we provide bounds on the probability that $mathcalS$ forms a $delta$-approximate $t$-design.
We show that for $mathcalS$ drawn from an exact $t$-design the probability that it forms a $delta$-approximate $t$-design satisfies the inequality $mathbbPleft(delta geq x right)leq 2D_t
arXiv Detail & Related papers (2022-02-10T23:44:09Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets.
Two types of structural assumptions lead to better pseudo-regret bounds.
arXiv Detail & Related papers (2021-03-10T07:33:03Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist.
We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
arXiv Detail & Related papers (2020-11-24T22:39:21Z) - A matrix concentration inequality for products [0.0]
We show that for small enough positive $alpha$, $Z_n$ satisfies the concentration inequality beginequationlabeleq:CTbound mathbbPleft(leftVert Z_n-mathbbEleft[Z_nright]rightVert geq tright) leq 2d2cdotexpleft(frac-t2alpha sigma2 right) quad textfor all
arXiv Detail & Related papers (2020-08-12T04:39:12Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals.
Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
arXiv Detail & Related papers (2020-06-29T17:10:10Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.