論文の概要: Safe Learning under Uncertain Objectives and Constraints
- arxiv url: http://arxiv.org/abs/2006.13326v1
- Date: Tue, 23 Jun 2020 20:51:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 21:33:19.269289
- Title: Safe Learning under Uncertain Objectives and Constraints
- Title(参考訳): 不確かな目的と制約の下での安全な学習
- Authors: Mohammad Fereydounian, Zebang Shen, Aryan Mokhtari, Amin Karbasi,
Hamed Hassani
- Abstract要約: 我々は、テキスト不明で安全クリティカルな制約の下で、非テクスト無知かつ安全クリティカルな最適化問題を考察する。
このような問題は、ロボティクス、製造、医療などの様々な領域で自然に発生する。
我々の分析の重要な要素は、安全な最適化の文脈で収縮と呼ばれる手法を導入し、適用することである。
- 参考スコア(独自算出の注目度): 66.05180398174286
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider non-convex optimization problems under
\textit{unknown} yet safety-critical constraints. Such problems naturally arise
in a variety of domains including robotics, manufacturing, and medical
procedures, where it is infeasible to know or identify all the constraints.
Therefore, the parameter space should be explored in a conservative way to
ensure that none of the constraints are violated during the optimization
process once we start from a safe initialization point. To this end, we develop
an algorithm called Reliable Frank-Wolfe (Reliable-FW). Given a general
non-convex function and an unknown polytope constraint, Reliable-FW
simultaneously learns the landscape of the objective function and the boundary
of the safety polytope. More precisely, by assuming that Reliable-FW has access
to a (stochastic) gradient oracle of the objective function and a noisy
feasibility oracle of the safety polytope, it finds an $\epsilon$-approximate
first-order stationary point with the optimal ${\mathcal{O}}({1}/{\epsilon^2})$
gradient oracle complexity (resp. $\tilde{\mathcal{O}}({1}/{\epsilon^3})$ (also
optimal) in the stochastic gradient setting), while ensuring the safety of all
the iterates. Rather surprisingly, Reliable-FW only makes
$\tilde{\mathcal{O}}(({d^2}/{\epsilon^2})\log 1/\delta)$ queries to the noisy
feasibility oracle (resp. $\tilde{\mathcal{O}}(({d^2}/{\epsilon^4})\log
1/\delta)$ in the stochastic gradient setting) where $d$ is the dimension and
$\delta$ is the reliability parameter, tightening the existing bounds even for
safe minimization of convex functions. We further specialize our results to the
case that the objective function is convex. A crucial component of our analysis
is to introduce and apply a technique called geometric shrinkage in the context
of safe optimization.
- Abstract(参考訳): 本稿では,textit{unknown}の下での非凸最適化問題について考察する。
このような問題は、ロボット工学、製造、医療などの様々な領域で自然に発生し、すべての制約を知ることも特定することも不可能である。
したがって、パラメータ空間は、安全な初期化点から始めると、最適化プロセス中にどの制約も違反しないように、保守的な方法で探索すべきである。
そこで我々は,Reliable Frank-Wolfe (Reliable-FW) と呼ばれるアルゴリズムを開発した。
一般凸関数と未知のポリトープ制約が与えられた場合、Reliable-FWは目的関数のランドスケープと安全ポリトープの境界を同時に学習する。
より正確には、Reliable-FW が目的関数の(確率的な)勾配オラクルと安全ポリトープのノイズの多い実現可能性オラクルにアクセスできると仮定することで、最適な ${\mathcal{O}}({1}/{\epsilon^2})$勾配オラクル複雑性(resp)を持つ$\epsilon$-approximate 1次定常点が見つかる。
確率勾配設定では、$\tilde{\mathcal{o}}({1}/{\epsilon^3})$(最適)であり、全ての反復の安全性を保証する。
意外なことに、Reliable-FWは$\tilde{\mathcal{O}}(({d^2}/{\epsilon^2})\log 1/\delta)$クエリをノイズの多い折りたたみオラクル(resp)にのみ生成します。
$\tilde{\mathcal{O}}(({d^2}/{\epsilon^4})\log 1/\delta)$ in the stochastic gradient setting) ここで$d$は次元、$\delta$は信頼性パラメータであり、凸関数の安全な最小化さえも既存の境界を締め付ける。
さらに,目的関数が凸である場合に,結果をさらに専門化する。
我々の分析の重要な要素は、安全な最適化の文脈で幾何収縮と呼ばれる手法を導入し適用することである。
関連論文リスト
- Universal Online Learning with Gradient Variations: A Multi-layer Online
Ensemble Approach [65.10444843694003]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $widehatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳(メタデータ) (2023-07-17T09:55:35Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
General Utilities [12.104551746465932]
安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。
我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。
サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
論文 参考訳(メタデータ) (2023-05-27T20:08:35Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-01-01T18:51:29Z) - Efficient Private SCO for Heavy-Tailed Data via Clipping [31.37972684061572]
差分プライベート(DP)の勾配を保証した重み付きデータの凸最適化について検討する。
一般的な凸問題では、過剰な集団リスクを$TildeOleft(fracd1/7sqrtlnfrac(n epsilon)2beta d(nepsilon)2/7right)$と$TildeOleft(fracd1/7lnfrac(nepsilon)2beta d(nepsilon)2
論文 参考訳(メタデータ) (2022-06-27T01:39:15Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳(メタデータ) (2022-04-11T15:08:09Z) - Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method [54.93433440034386]
実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
論文 参考訳(メタデータ) (2020-10-05T08:16:56Z) - Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文 参考訳(メタデータ) (2020-08-13T08:56:24Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。