論文の概要: Learning Smooth Distance Functions via Queries

• arxiv url: http://arxiv.org/abs/2412.01290v1
• Date: Mon, 02 Dec 2024 09:03:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-04 15:51:53.747207
• Title: Learning Smooth Distance Functions via Queries
• Title（参考訳）: クエリによるスムース距離関数の学習
• Authors: Akash Kumar, Sanjoy Dasgupta,
• Abstract要約: 問合せに基づく学習フレームワークにおける学習距離関数の問題について検討する。 我々は、スムースに学習するために必要なクエリの複雑さに関する公式な保証を確立するが、そうでなければ距離関数の一般性は保証する。
• 参考スコア（独自算出の注目度）: 11.242483654173327
• License:
• Abstract: In this work, we investigate the problem of learning distance functions within the query-based learning framework, where a learner is able to pose triplet queries of the form: ``Is $x_i$ closer to $x_j$ or $x_k$?'' We establish formal guarantees on the query complexity required to learn smooth, but otherwise general, distance functions under two notions of approximation: $\omega$-additive approximation and $(1 + \omega)$-multiplicative approximation. For the additive approximation, we propose a global method whose query complexity is quadratic in the size of a finite cover of the sample space. For the (stronger) multiplicative approximation, we introduce a method that combines global and local approaches, utilizing multiple Mahalanobis distance functions to capture local geometry. This method has a query complexity that scales quadratically with both the size of the cover and the ambient space dimension of the sample space.
• Abstract（参考訳）: 本研究は,クエリベースの学習フレームワークにおける距離関数の学習問題について検討し,学習者が三重項クエリを提示することができる。 '`Is $x_i$ close to $x_j$ or $x_k$?'' 私たちは,2つの近似概念の下で,スムーズな学習に必要なクエリ複雑性に関する公式保証を確立する: $\omega$-additive approximation と $(1 + \omega)$-multiplicative approximation。 加法近似では,クエリの複雑性が標本空間の有限被覆の大きさの2次的な大域的手法を提案する。 本稿では,大域的および局所的アプローチを組み合わせた(ストロンガー)乗法について,複数のマハラノビス距離関数を用いて局所幾何学を捉える手法を提案する。 この方法は、カバーのサイズとサンプル空間の周囲空間次元の両方で2次スケールのクエリ複雑性を持つ。

関連論文リスト

• A Theory of Interpretable Approximations [61.90216959710842]
  我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。 任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。 解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
  論文  参考訳（メタデータ） (2024-06-15T06:43:45Z)
• Integrated Variational Fourier Features for Fast Spatial Modelling with Gaussian Processes [7.5991638205413325]
  トレーニングポイントが$N$の場合、正確な推論は$O(N3)$コストを持ち、$M ll N$機能により、アートスパース変分メソッドの状態は$O(NM2)$コストを持つ。 近年、空間モデリングのような低次元タスクにおいて優れた性能を持つ$O(M3)$コストを約束する手法が提案されているが、最もよく使われるカーネルを除いて、非常に限られた種類のカーネルでしか動作しない。 本稿では,Fourier機能の統合について提案する。これは,これらのパフォーマンスのメリットを,より広範な定常的コのクラスに拡張するものである。
  論文  参考訳（メタデータ） (2023-08-27T15:44:28Z)
• Manifold Free Riemannian Optimization [4.484251538832438]
  滑らかな多様体 $mathcalM$ を用いて最適化問題を解くための原理的枠組みを提案する。 代数学M におけるコスト関数 $(x_i, y_i) の雑音のないサンプル集合 mathbbR$ と多様体 $mathcalM$ の固有次元を用いる。
  論文  参考訳（メタデータ） (2022-09-07T16:19:06Z)
• Target Network and Truncation Overcome The Deadly triad in $Q$-Learning [7.532013242448151]
  本稿では,ターゲットネットワークとトランケーションを用いた線形関数近似を用いた$Q$-learningの安定設計を提案する。 この結果から,関数近似誤差まで,$mathcalO(epsilon-2)$サンプルの複雑さが示唆された。 これは線形関数近似による$Q$-learningの最初の変種であり、強い仮定や問題パラメータの変更を必要とせず、確実に安定である。
  論文  参考訳（メタデータ） (2022-03-05T00:54:58Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
  一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。 我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。 我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
  論文  参考訳（メタデータ） (2020-05-21T17:36:09Z)
• Low Complexity Sequential Search with Size-Dependent Measurement Noise [19.201555109949677]
  本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。 アレイ処理における初期ビームアライメント、ネットワークにおける重ヒッタ検出、ロボット工学におけるビジュアルサーチといった実用的応用により、我々は事実上重要な複雑さの制約/指標を考察する。 新規検索戦略として$dyaPM$と$hiePM$が提案されている。
  論文  参考訳（メタデータ） (2020-05-15T22:40:18Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。