論文の概要: On Learning for Ambiguous Chance Constrained Problems
- arxiv url: http://arxiv.org/abs/2401.00547v1
- Date: Sun, 31 Dec 2023 17:25:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-03 16:59:19.704949
- Title: On Learning for Ambiguous Chance Constrained Problems
- Title（参考訳）: あいまいな確率制約のある問題に対する学習について
- Authors: A Ch Madhusudanarao, Rahul Singh
- Abstract要約: この場合、$theta$のサンプルが$nu$から引き出されるサンプル問題により、元の問題は「適切に近似できる」ことが示される。
また、この近似に関連するサンプルの複雑さ、すなわち$epsilon,delta>0$に対して$nu$から引かなければならないサンプルの数を導出する。
- 参考スコア（独自算出の注目度）: 2.7152798636894193
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study chance constrained optimization problems $\min_x f(x)$ s.t.
$P(\left\{ \theta: g(x,\theta)\le 0 \right\})\ge 1-\epsilon$ where $\epsilon\in
(0,1)$ is the violation probability, when the distribution $P$ is not known to
the decision maker (DM). When the DM has access to a set of distributions
$\mathcal{U}$ such that $P$ is contained in $\mathcal{U}$, then the problem is
known as the ambiguous chance-constrained problem \cite{erdougan2006ambiguous}.
We study ambiguous chance-constrained problem for the case when $\mathcal{U}$
is of the form $\left\{\mu:\frac{\mu (y)}{\nu(y)}\leq C, \forall y\in\Theta,
\mu(y)\ge 0\right\}$, where $\nu$ is a ``reference distribution.'' We show that
in this case the original problem can be ``well-approximated'' by a sampled
problem in which $N$ i.i.d. samples of $\theta$ are drawn from $\nu$, and the
original constraint is replaced with $g(x,\theta_i)\le 0,~i=1,2,\ldots,N$. We
also derive the sample complexity associated with this approximation, i.e., for
$\epsilon,\delta>0$ the number of samples which must be drawn from $\nu$ so
that with a probability greater than $1-\delta$ (over the randomness of $\nu$),
the solution obtained by solving the sampled program yields an
$\epsilon$-feasible solution for the original chance constrained problem.
- Abstract（参考訳）: 確率制約付き最適化問題 $min_x f について検討する。
(x)$ s.t.$P(\left\{ \theta: g(x,\theta)\le 0 \right\})\ge 1-\epsilon$ ここで$\epsilon\in (0,1)$は、分布$P$が意思決定者(DM)に知られていない場合の違反確率である。
DMが$\mathcal{U}$に$P$が$\mathcal{U}$に含まれるような分布の集合にアクセスするとき、問題はあいまいな確率制約問題 \cite{erdougan 2006ambiguous} として知られている。
我々は、$\mathcal{u}$ が $\left\{\mu:\frac{\mu の形である場合の曖昧な確率制約問題を研究する。
(y)}{\nu
(y)}\leq C, \forall y\in\Theta, \mu
(y)\ge 0\right\}$, ここで$\nu$ は ``reference distribution である。
この場合、元の問題は、$n$ i.i.d. の$\theta$ のサンプルが $\nu$ から引き出され、元の制約は $g(x,\theta_i)\le 0,~i=1,2,\ldots,n$ に置き換えられるようなサンプル問題によって ``well-approximated''' となる。
また、この近似に関連するサンプルの複雑さ、すなわち$\epsilon,\delta>0$に対して、$\nu$から引かなければならないサンプルの個数を導出し、($\nu$のランダム性よりも)1-\delta$より大きい確率で、サンプルプログラムを解くことで得られる解は、元の確率制約問題に対して$\epsilon$-feasibleな解が得られる。
関連論文リスト
- Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。
目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
論文 参考訳（メタデータ） (2024-03-14T15:04:45Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Matrix concentration inequalities and efficiency of random universal
sets of quantum gates [0.0]
ランダム集合 $mathcalS の部分集合 U(d)$ に対して、$mathcalS$ が $delta$-approximate $t$-design となる確率の有界性を与える。
正確な$t$-designから引き出された$mathcalS$に対して、$delta$-approximate $t$-designが不等式$mathbbPleft(delta geq x right)leq 2D_tを満たす確率を示す。
論文 参考訳（メタデータ） (2022-02-10T23:44:09Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文 参考訳（メタデータ） (2020-07-16T04:23:57Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。
これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文 参考訳（メタデータ） (2020-04-13T08:06:29Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。