論文の概要: 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$における幾何学的概念であるが、宇宙は空間全体であり、目的はすべての範囲を交差する小さなサンプルを選択することである。
関連論文リスト
- The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
連続状態と行動空間を持つ非線形力学系に対するオンライン強化学習のサンプル複雑性について検討した。
我々のアルゴリズムは、その単純さ、事前知識を組み込む能力、そして良心的な過渡的行動のために、実際に有用である可能性が高い。
論文 参考訳（メタデータ） (2025-01-27T10:01:28Z) - On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。
我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。
また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
論文 参考訳（メタデータ） (2024-11-16T12:09:37Z) - Neural Networks and (Virtual) Extended Formulations [5.762677915745415]
私たちは、$P$を最適化するニューラルネットワークのサイズに対して、より低い境界を証明します。
我々は、$mathrmxc(P)$が任意のモノトーンや入力ニューラルネットワークのサイズの低い境界であることを示し、$P$を超える線形最適化問題を解く。
論文 参考訳（メタデータ） (2024-11-05T11:12:11Z) - 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) - 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) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。