論文の概要: Optimization from Structured Samples for Coverage Functions
- arxiv url: http://arxiv.org/abs/2007.02738v1
- Date: Mon, 6 Jul 2020 13:18:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-13 02:10:09.419382
- Title: Optimization from Structured Samples for Coverage Functions
- Title（参考訳）: カバレッジ関数のための構造化サンプルからの最適化
- Authors: Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang
- Abstract要約: 我々は、データから直接目的関数を研究するサンプル(OPS)モデルから最適化を再考する。
サンプルの3つの一般的な仮定の下で、最大カバレッジ問題に対して効率的なOPSSアルゴリズムを設計できることが示される。
- 参考スコア（独自算出の注目度）: 23.540275997841043
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the optimization from samples (OPS) model, which studies the
problem of optimizing objective functions directly from the sample data.
Previous results showed that we cannot obtain a constant approximation ratio
for the maximum coverage problem using polynomially many independent samples of
the form $\{S_i, f(S_i)\}_{i=1}^t$ (Balkanski et al., 2017), even if coverage
functions are $(1 - \epsilon)$-PMAC learnable using these samples (Badanidiyuru
et al., 2012), which means most of the function values can be approximately
learned very well with high probability. In this work, to circumvent the
impossibility result of OPS, we propose a stronger model called optimization
from structured samples (OPSS) for coverage functions, where the data samples
encode the structural information of the functions. We show that under three
general assumptions on the sample distributions, we can design efficient OPSS
algorithms that achieve a constant approximation for the maximum coverage
problem. We further prove a constant lower bound under these assumptions, which
is tight when not considering computational efficiency. Moreover, we also show
that if we remove any one of the three assumptions, OPSS for the maximum
coverage problem has no constant approximation.
- Abstract（参考訳）: 我々は、サンプルデータから直接目的関数を最適化する問題を研究するサンプル(ops)モデルから最適化を再検討する。
これまでの結果から, 最大カバレッジ問題に対する定数近似比は, $\{s_i, f(s_i)\}_{i=1}^t$ (balkanski et al., 2017) という形で多項式的に多くの独立なサンプルを用いては得られず, カバレッジ関数が(1 - \epsilon)$-pmacで学習可能であっても (badanidiyuru et al., 2012) である。
本研究では,データサンプルが関数の構造情報をエンコードするカバレッジ関数のための,構造化サンプル(structured samples, opss)による最適化と呼ばれるより強力なモデルを提案する。
サンプル分布の3つの一般的な仮定の下では,最大カバレッジ問題の定数近似を実現する効率的なopssアルゴリズムを設計できることを示す。
さらに、計算効率を考慮しない場合、これらの仮定の下で一定の下界を証明します。
さらに,3つの仮定のうちのいずれかを取り除けば,最大被覆問題に対するOPSSは一定の近似を持たないことを示す。
関連論文リスト
- A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Optimize-via-Predict: Realizing out-of-sample optimality in data-driven
optimization [0.0]
本稿では,データ駆動最適化の定式化について検討する。
我々は、規範的なソリューションを、そのようなデータセットを意思決定にマッピングする意思決定者ルールとして定義する。
本稿では,このようなサンプル外最適解に対して,サンプリングアルゴリズムと2分割探索アルゴリズムを組み合わせることで効率よく解ける最適化問題を提案する。
論文 参考訳（メタデータ） (2023-09-20T08:48:50Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳（メタデータ） (2022-08-17T18:49:53Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Bayesian Joint Chance Constrained Optimization: Approximations and
Statistical Consistency [10.20554144865699]
近似した後続分布を用いて計算した最適値の統計的整合性の問題に焦点をあてる。
また、近似最適化問題の実現可能性も証明する。
また,M/M/c待ち行列モデルに対する最適スタッフリング問題に対するアプローチの有用性を示す。
論文 参考訳（メタデータ） (2021-06-23T07:11:39Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Optimal Sampling Gaps for Adaptive Submodular Maximization [28.24164217929491]
アダプティブサブモジュラの文脈における確率サンプリングによる性能損失について検討する。
ポリシワイズ・サブモジュラの性質は、現実世界の幅広いアプリケーションで見つけることができることを示しています。
論文 参考訳（メタデータ） (2021-04-05T03:21:32Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Maximum sampled conditional likelihood for informative subsampling [4.708378681950648]
サブサンプリングは、計算資源が限られているときに大量のデータセットから情報を抽出する、計算学的に効果的な手法である。
そこで本研究では,サンプルデータに基づく最大条件付き確率推定器(MSCLE)を提案する。
論文 参考訳（メタデータ） (2020-11-11T16:01:17Z) - On Differentially Private Stochastic Convex Optimization with
Heavy-tailed Data [18.351352536791453]
本稿では,重み付きデータを用いた凸最適化(SCO)のためのDPアルゴリズムの設計について考察する。
このようなデータの不規則性は、ほとんど全ての既存のDP-SCOおよびDP-ERM法で使われるいくつかの重要な仮定に反する。
我々は,データの不規則性に起因する課題に対して,アルゴリズムが効果的に対処可能であることを示す。
論文 参考訳（メタデータ） (2020-10-21T15:45:27Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。