Fugu-MT 論文翻訳(概要): Online Epsilon Net and Piercing Set for Geometric Concepts

論文の概要: Online Epsilon Net and Piercing Set for Geometric Concepts

arxiv url: http://arxiv.org/abs/2410.07059v1
Date: Wed, 9 Oct 2024 16:58:36 GMT
ステータス: 処理完了
システム内更新日: 2024-10-31 22:47:07.898163
Title: Online Epsilon Net and Piercing Set for Geometric Concepts
Title（参考訳）: 幾何概念のためのオンラインエプシロンネットとピアシングセット
Authors: Sujoy Bhore, Devdan Dey, Satyam Singh,
Abstract要約: 有界VC次元を持つ幾何学的概念に対するオンライン$varepsilon$-net問題について検討する。区間の最適競合比を$mathbbRd$で表した最初の決定論的オンラインアルゴリズムを提案する。我々はまた、$mathbbRd$の定数記述複雑性の類似サイズのオブジェクトを解析するための新しい手法も導入する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: VC-dimension and $\varepsilon$-nets are key concepts in Statistical Learning Theory. Intuitively, VC-dimension is a measure of the size of a class of sets. The famous $\varepsilon$-net theorem, a fundamental result in Discrete Geometry, asserts that if the VC-dimension of a set system is bounded, then a small sample exists that intersects all sufficiently large sets. In online learning scenarios where data arrives sequentially, the VC-dimension helps to bound the complexity of the set system, and $\varepsilon$-nets ensure the selection of a small representative set. This sampling framework is crucial in various domains, including spatial data analysis, motion planning in dynamic environments, optimization of sensor networks, and feature extraction in computer vision, among others. Motivated by these applications, we study the online $\varepsilon$-net problem for geometric concepts with bounded VC-dimension. While the offline version of this problem has been extensively studied, surprisingly, there are no known theoretical results for the online version to date. We present the first deterministic online algorithm with an optimal competitive ratio for intervals in $\mathbb{R}$. Next, we give a randomized online algorithm with a near-optimal competitive ratio for axis-aligned boxes in $\mathbb{R}^d$, for $d\le 3$. Furthermore, we introduce a novel technique to analyze similar-sized objects of constant description complexity in $\mathbb{R}^d$, which may be of independent interest. Next, we focus on the continuous version of this problem, where ranges of the set system are geometric concepts in $\mathbb{R}^d$ arriving in an online manner, but the universe is the entire space, and the objective is to choose a small sample that intersects all the ranges.
Abstract（参考訳）: VC次元と$\varepsilon$-netsは統計学習理論における重要な概念である。直観的には、VC次元は集合のクラスの大きさの尺度である。有名な$\varepsilon$-net定理は、離散幾何の基本的な結果であり、集合系のVC次元が有界であれば、すべての十分大きな集合と交わる小さなサンプルが存在すると断言する。データが順次到着するオンライン学習シナリオでは、VC次元はセットシステムの複雑さを束縛し、$\varepsilon$-netsは小さな代表集合の選択を保証する。このサンプリングフレームワークは,空間データ解析,動的環境における動作計画,センサネットワークの最適化,コンピュータビジョンにおける特徴抽出など,様々な領域において重要である。これらの応用に触発されて、有界VC次元を持つ幾何学的概念に対するオンラインの$\varepsilon$-net問題を研究する。この問題のオフライン版は広く研究されているが、驚くべきことに、現在までのオンライン版の理論的な結果は知られていない。区間の最適競合比を$\mathbb{R}$で表した最初の決定論的オンラインアルゴリズムを提案する。次に、$\mathbb{R}^d$, for $d\le 3$の軸整列箱に対して、ほぼ最適の競合比を持つランダム化オンラインアルゴリズムを提案する。さらに, 独立性のある$\mathbb{R}^d$において, 一定の記述複雑性の類似サイズのオブジェクトを解析するための新しい手法を導入する。次に、この問題の連続バージョンに焦点をあて、そこでは集合系の範囲は$\mathbb{R}^d$における幾何学的概念であるが、宇宙は空間全体であり、目的はすべての範囲を交差する小さなサンプルを選択することである。

関連論文リスト

On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
論文参考訳（メタデータ） (2024-11-16T12:09:37Z)
Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文参考訳（メタデータ） (2024-03-08T18:50:19Z)
Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文参考訳（メタデータ） (2023-07-17T09:55:35Z)
Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文参考訳（メタデータ） (2023-02-03T03:19:14Z)
Scaling up the self-optimization model by means of on-the-fly computation of weights [0.8057006406834467]
この研究は、ノード数$N$に対して$mathcalOleft(N2right)$としてスケールするセルフ最適化(SO)モデルの新たな実装を導入している。我々のオンザフライ計算は、より大規模なシステムサイズを調査するための道を開くもので、将来の研究においてより多様で複雑になる。
論文参考訳（メタデータ） (2022-11-03T10:51:25Z)
Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
論文参考訳（メタデータ） (2022-10-30T22:58:22Z)
A singular Riemannian geometry approach to Deep Neural Networks II. Reconstruction of 1-D equivalence classes [78.120734120667]
入力空間における出力多様体内の点の事前像を構築する。我々は、n-次元実空間から(n-1)-次元実空間へのニューラルネットワークマップの場合の簡易性に焦点をあてる。
論文参考訳（メタデータ） (2021-12-17T11:47:45Z)
Distributed Sparse Feature Selection in Communication-Restricted Networks [6.9257380648471765]
疎線形回帰と特徴選択のための新しい分散スキームを提案し,理論的に解析する。データセット全体から因果次元を推定するために,ネットワーク内の情報共有をシンプルかつ効果的に行う手法を提案する。
論文参考訳（メタデータ） (2021-11-02T05:02:24Z)
Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networks [42.43493635899849]
畳み込み残余ネットワーク(ConvResNet)の理論的保証を関数近似および二項分類の統計的推定の観点から確立する。その結果,ConvResNetsはデータセットの低次元構造に適応していることがわかった。
論文参考訳（メタデータ） (2021-09-07T02:58:11Z)
Deep Networks and the Multiple Manifold Problem [15.144495799445824]
マシンビジョンにおける応用をモデル化した二項分類タスクである多重多様体問題について検討し、深部完全連結ニューラルネットワークを用いて単位球面の2つの低次元部分多様体を分離する。ネットワーク深さ$L$がデータの幾何的および統計的性質に対して大きい場合、ネットワーク幅は$L$で十分大きく成長することを示す。本分析は,実際に動機付けられたモデル問題の文脈における奥行きと幅の具体的な利点を示す。
論文参考訳（メタデータ） (2020-08-25T19:20:00Z)
Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文参考訳（メタデータ） (2020-02-25T23:05:33Z)

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

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