論文の概要: Exact objectives of random linear programs and mean widths of random
polyhedrons
- arxiv url: http://arxiv.org/abs/2403.03637v1
- Date: Wed, 6 Mar 2024 11:51:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 15:15:17.932782
- Title: Exact objectives of random linear programs and mean widths of random
polyhedrons
- Title（参考訳）: ランダム線形プログラムの厳密な目的とランダム多面体の平均幅
- Authors: Mihailo Stojnic
- Abstract要約: 我々は、エンフレアンドム最適化問題(rops)のサブクラスとして、エンフレアンドム線形プログラム(rlps)を考える。
我々の特に焦点は、rpsをランダムなポリヘドロン/ポリトープの平均幅に接続する適切な線形目的性である。
- 参考スコア（独自算出の注目度）: 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}\}$.
- Abstract（参考訳）: 我々は, \emph{random linear programs} (rlps) を \emph{random optimization problems} (rops) のサブクラスと考え,それらの典型的な挙動を考察する。
我々の特に焦点は、rpsをランダムなポリヘドロン/ポリトープの平均幅に接続する適切な線形目的性である。
emph{random duality theory} (rdt) \cite{stojnicregrnddlt10}の強力な機構を利用して、大きな次元の文脈において、プログラムの目的の正確な特徴付けを得る。
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} }.
例えば、$\mathbf{a}=\mathbf{1}$ に対して、ある発見は \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 } である。
さらに、2 \xi_{opt}(\alpha)$ はちょうど多面体 $\{\mathbf{x}|a\mathbf{x} \leq \mathbf{1}\}$ の平均幅の集中点である。
関連論文リスト
- Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。
ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-11-11T03:43:52Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Capacity of the Hebbian-Hopfield network associative memory [0.0]
Hop82の引用でHopfieldは、emphHebbianの学習ルールに基づくニューラルネットワークモデルを導入し、連想メモリとして効率的に動作する方法を提案した。
textbfemph(i) AGS one from citeAmiGutSom85; textbfemph(ii) NLT one from citeNewman88,Louk94,Louk94a,Louk97,Tal
論文 参考訳（メタデータ） (2024-03-04T10:10:23Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Convergence Rates of Stochastic Zeroth-order Gradient Descent for \L
ojasiewicz Functions [6.137707924685666]
Lojasiewicz関数に対するゼロ階勾配 Descent (SZGD) アルゴリズムの収束率を証明する。
その結果, mathbbN $ における f (mathbfx_t) - f (mathbfx_infty) _t は $ | mathbfx_infty よりも早く収束できることがわかった。
論文 参考訳（メタデータ） (2022-10-31T00:53:17Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (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]
$mathcalM$ を $mathbbRN$ のコンパクト $d$-次元部分多様体とし、リーチ $tau$ とボリューム $V_mathcal M$ とする。
非線形関数 $f: mathbbRN rightarrow mathbbRmm が存在し、$m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math が存在することを証明します。
論文 参考訳（メタデータ） (2022-06-07T15:10:46Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - A matrix concentration inequality for products [0.0]
十分小さな正の$alpha$, $Z_n$は、濃度不等式を満足する:CTbound mathbbPleft(leftVert Z_n-mathbbEleft[Z_nright]rightVert geq tright) leq 2d2cdotexpleft(frac-t2alpha sigma2 right) quad text for all。
論文 参考訳（メタデータ） (2020-08-12T04:39:12Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。