論文の概要: A numerical algorithm for attaining the Chebyshev bound in optimal learning

• arxiv url: http://arxiv.org/abs/2307.01304v1
• Date: Mon, 3 Jul 2023 19:20:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-06 19:15:53.300687
• Title: A numerical algorithm for attaining the Chebyshev bound in optimal learning
• Title（参考訳）: 最適学習におけるchebyshevバウンド獲得のための数値解法
• Authors: Pradyumna Paruchuri, Debasish Chatterjee
• Abstract要約: 有限なデータ点集合からの最適学習の文脈において,チェビシェフ中心問題を解くための数値的に抽出可能なアルゴリズムを確立する。 バナッハ空間の有限次元部分空間のコンパクトであるが必ずしも凸部分集合として実現される仮説空間に対して、このアルゴリズムは仮説空間のチェビシェフ半径とチェビシェフ中心を計算する。
• 参考スコア（独自算出の注目度）: 1.0406659081400353
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a compact subset of a Banach space, the Chebyshev center problem consists of finding a minimal circumscribing ball containing the set. In this article we establish a numerically tractable algorithm for solving the Chebyshev center problem in the context of optimal learning from a finite set of data points. For a hypothesis space realized as a compact but not necessarily convex subset of a finite-dimensional subspace of some underlying Banach space, this algorithm computes the Chebyshev radius and the Chebyshev center of the hypothesis space, thereby solving the problem of optimal recovery of functions from data. The algorithm itself is based on, and significantly extends, recent results for near-optimal solutions of convex semi-infinite problems by means of targeted sampling, and it is of independent interest. Several examples of numerical computations of Chebyshev centers are included in order to illustrate the effectiveness of the algorithm.
• Abstract（参考訳）: バナッハ空間のコンパクト部分集合が与えられたとき、チェビシェフ中心問題は集合を含む極小周球を見つけることである。 本稿では、有限個のデータ点から最適学習の文脈において、チェビシェフ中心問題を解くための数値的扱いやすいアルゴリズムを定式化する。 バナッハ空間の有限次元部分空間のコンパクトだが必ずしも凸部分集合として実現されていない仮説空間に対して、このアルゴリズムは、仮説空間のチェビシェフ半径とチェビシェフ中心を計算し、データから関数を最適に回復する問題を解決する。 このアルゴリズム自体は、ターゲットサンプリングによる凸半無限問題のほぼ最適解に対する最近の結果に基づいて、さらに大幅に拡張されている。 チェビシェフ中心の数値計算のいくつかの例は、アルゴリズムの有効性を説明するために含まれている。

関連論文リスト

• A cutting plane algorithm for globally solving low dimensional k-means clustering problems [4.5594982923247995]
  我々は、低次元データを持つインスタンスのk-means問題を考え、これを構造的凹面割り当て問題として定式化する。 これにより、低次元構造を利用して、妥当な時間で大域的最適性に問題を解くことができる。 本論文は,グローバル最適化理論の手法を組み合わせて手順を高速化し,数値的な結果を提供する。
  論文  参考訳（メタデータ） (2024-02-21T07:55:33Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• An Improved Greedy Algorithm for Subset Selection in Linear Estimation [5.994412766684842]
  有限個の予測位置において、観測値の最もよい推定値を与えるような k 個の位置の集合を求める空間場における部分選択問題を考える。 観測選択の1つのアプローチは、空間の格子離散化を行い、グリードアルゴリズムを用いて近似解を得ることである。 本稿では,予測位置と予測位置によって形成される傾斜角の遠心点のみからなる探索空間を考慮し,計算複雑性を低減する手法を提案する。
  論文  参考訳（メタデータ） (2022-03-30T05:52:16Z)
• Projection Robust Wasserstein Barycenter [36.97843660480747]
  ワッサースタイン・バリセンターの 近似は 次元の呪いのため 数値的に困難です 本稿では,次元の呪いを緩和するプロジェクションロバストなワッサーシュタインバリセンタ(PRWB)を提案する。
  論文  参考訳（メタデータ） (2021-02-05T19:23:35Z)
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds [9.632674803757475]
  距離における凸問題と非最適化問題の解法を提案する。 提案アルゴリズムは,目的関数における複雑性のレベルに適応する。
  論文  参考訳（メタデータ） (2020-10-18T02:48:22Z)
• Communication-efficient distributed eigenspace estimation [31.69089186688224]
  我々は,データ行列の先頭不変部分空間を計算するための通信効率のよい分散アルゴリズムを開発した。 提案アルゴリズムは局所解と参照解の間のプロクリスト距離を最小化する新しいアライメント方式を用いる。 本アルゴリズムは,集中型推定器と同様の誤差率を示す。
  論文  参考訳（メタデータ） (2020-09-05T02:11:22Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Ball k-means [53.89505717006118]
  Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。 高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
  論文  参考訳（メタデータ） (2020-05-02T10:39:26Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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