Fugu-MT 論文翻訳(概要): Sample Efficient Graph-Based Optimization with Noisy Observations

論文の概要: Sample Efficient Graph-Based Optimization with Noisy Observations

arxiv url: http://arxiv.org/abs/2006.02672v1
Date: Thu, 4 Jun 2020 07:22:28 GMT
ステータス: 処理完了
システム内更新日: 2022-11-25 09:14:49.554552
Title: Sample Efficient Graph-Based Optimization with Noisy Observations
Title（参考訳）: 雑音観測によるグラフベース最適化
Authors: Tan Nguyen, Ali Shameli, Yasin Abbasi-Yadkori, Anup Rao, Branislav Kveton
Abstract要約: グラフのサイズに依存しない少数のクエリの後に、ベストアーム識別の変種が、ほぼ最適解を見つけることができることを示す。グラフベース近傍分類の問題に対して,再起動によるグリーディアルゴリズムの有効性とシミュレーションアニーリングの有効性を示す。
参考スコア（独自算出の注目度）: 17.91308664586981
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study sample complexity of optimizing "hill-climbing friendly" functions defined on a graph under noisy observations. We define a notion of convexity, and we show that a variant of best-arm identification can find a near-optimal solution after a small number of queries that is independent of the size of the graph. For functions that have local minima and are nearly convex, we show a sample complexity for the classical simulated annealing under noisy observations. We show effectiveness of the greedy algorithm with restarts and the simulated annealing on problems of graph-based nearest neighbor classification as well as a web document re-ranking application.
Abstract（参考訳）: 雑音観測の下で, グラフ上に定義された「ヒルクライミングフレンドリー」関数を最適化するサンプル複雑性について検討した。我々は凸性の概念を定義し、グラフのサイズに依存しない少数のクエリの後にベストアーム識別の変種が最適に近い解を見つけることができることを示す。局所最小値を持ち凸に近い関数に対しては,ノイズ観測下での古典的擬似アニーリングのサンプル複雑性を示す。本稿では,再起動を伴うグリーディアルゴリズムの有効性と,グラフベース近傍の分類問題とWebドキュメントの再分類問題に対するシミュレーションアニーリングについて述べる。

関連論文リスト

Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文参考訳（メタデータ） (2024-06-28T02:56:22Z)
Neural Gaussian Similarity Modeling for Differential Graph Structure Learning [24.582257964387402]
微分不可能近傍サンプリングを微分可能サンプリングに置き換えることで、微分グラフ構造学習モデルを構築する。この問題を緩和するために、ベル形状のガウス類似性(Gaussian similarity, GauSim)モデリングが、非アネレスト近傍のサンプルとして提案されている。我々は,大規模グラフを遷移グラフに転送することで,複雑さを著しく低減し,スケーラブルな手法を開発した。
論文参考訳（メタデータ） (2023-12-15T02:45:33Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文参考訳（メタデータ） (2023-06-21T17:03:22Z)
On the Optimal Recovery of Graph Signals [10.098114696565865]
グラフ信号処理問題に対して最適あるいはほぼ最適な正規化パラメータを演算する。本結果は,グラフに基づく学習における古典的最適化手法の新しい解釈を提供する。半合成グラフ信号処理データセットの数値実験における本手法の可能性について述べる。
論文参考訳（メタデータ） (2023-04-02T07:18:11Z)
Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文参考訳（メタデータ） (2023-02-08T08:17:43Z)
Joint graph learning from Gaussian observations in the presence of hidden nodes [26.133725549667734]
本稿では,隠れ変数の存在を考慮した共同グラフ学習法を提案する。従来の考察から得られた構造を利用して凸最適化問題を提案する。提案したアルゴリズムを異なるベースラインで比較し、合成グラフと実世界のグラフ上での性能を評価する。
論文参考訳（メタデータ） (2022-12-04T13:03:41Z)
Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
論文参考訳（メタデータ） (2022-10-30T22:04:32Z)
Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文参考訳（メタデータ） (2022-05-06T03:37:00Z)
Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
論文参考訳（メタデータ） (2021-03-25T09:31:41Z)
Reinforcement Learning with Feedback Graphs [69.1524391595912]
エージェントがステップ毎に追加のフィードバックを受けた場合,決定過程におけるエピソード強化学習について検討する。状態-作用対上のフィードバックグラフを用いてこの設定を定式化し、モデルベースのアルゴリズムが追加のフィードバックを利用してよりサンプル効率のよい学習を行うことを示す。
論文参考訳（メタデータ） (2020-05-07T22:35:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。