論文の概要: Random Separating Hyperplane Theorem and Learning Polytopes

• arxiv url: http://arxiv.org/abs/2307.11371v1
• Date: Fri, 21 Jul 2023 06:03:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-24 13:32:00.296336
• Title: Random Separating Hyperplane Theorem and Learning Polytopes
• Title（参考訳）: ランダム分離超平面定理と学習多面体
• Authors: Chiranjib Bhattacharyya and Ravindran Kannan and Amit Kumar
• Abstract要約: 最初の結果、Random Separating Hyperplane Theorem (RSH)は、ポリトープの強化である。 我々は、ハウスドルフ距離$delta$内の単位径ポリトープ$K$を学習する「ハウスドルフ問題」という基本的な問題を考える。 我々の知る限り、これはハウスドルフ問題に対する最初の証明可能なアルゴリズムである。
• 参考スコア（独自算出の注目度）: 21.034285948433098
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Separating Hyperplane theorem is a fundamental result in Convex Geometry with myriad applications. Our first result, Random Separating Hyperplane Theorem (RSH), is a strengthening of this for polytopes. $\rsh$ asserts that if the distance between $a$ and a polytope $K$ with $k$ vertices and unit diameter in $\Re^d$ is at least $\delta$, where $\delta$ is a fixed constant in $(0,1)$, then a randomly chosen hyperplane separates $a$ and $K$ with probability at least $1/poly(k)$ and margin at least $\Omega \left(\delta/\sqrt{d} \right)$. An immediate consequence of our result is the first near optimal bound on the error increase in the reduction from a Separation oracle to an Optimization oracle over a polytope. RSH has algorithmic applications in learning polytopes. We consider a fundamental problem, denoted the ``Hausdorff problem'', of learning a unit diameter polytope $K$ within Hausdorff distance $\delta$, given an optimization oracle for $K$. Using RSH, we show that with polynomially many random queries to the optimization oracle, $K$ can be approximated within error $O(\delta)$. To our knowledge this is the first provable algorithm for the Hausdorff Problem. Building on this result, we show that if the vertices of $K$ are well-separated, then an optimization oracle can be used to generate a list of points, each within Hausdorff distance $O(\delta)$ of $K$, with the property that the list contains a point close to each vertex of $K$. Further, we show how to prune this list to generate a (unique) approximation to each vertex of the polytope. We prove that in many latent variable settings, e.g., topic modeling, LDA, optimization oracles do exist provided we project to a suitable SVD subspace. Thus, our work yields the first efficient algorithm for finding approximations to the vertices of the latent polytope under the well-separatedness assumption.
• Abstract（参考訳）: 分離超平面定理は、無数の応用を伴う凸幾何学の基本的な結果である。 我々の最初の結果であるランダム分離超平面定理(rsh)は、ポリトープに対するこの強化である。 $\rsh$ は、$a$ と $k$ のポリトープ $k$ との間の距離が少なくとも$\delta$ であり、$\delta$ は $(0,1)$ の固定定数であるなら、ランダムに選択された超平面は $a$ と $k$ を少なくとも $1/poly(k)$ で分離し、少なくとも $\omega \left(\delta/\sqrt{d} \right)$ となる。 この結果の即時的な結果は、分離オラクルからポリトープ上の最適化オラクルへの還元における誤差増加に関する最初の最適境界である。 RSHはポリトープの学習にアルゴリズム的応用がある。 我々は「ハウスドルフ問題」と表記される基本的な問題を考えると、単位直径のポリトープがハウスドルフ距離で$k$であり、最適化されたオラクルが$k$である。 RSHを用いて、最適化オラクルに対して多項式的に多くのランダムクエリを適用すれば、$K$はエラー$O(\delta)$内で近似できることを示す。 我々の知る限り、これはハウスドルフ問題の証明可能な最初のアルゴリズムである。 この結果に基づいて、$K$ の頂点が十分に分離された場合、最適化オラクルを使って点のリストを生成することができ、それぞれが Hausdorff distance $O(\delta)$ of $K$ 内にあり、リストが $K$ の各頂点に近い点を含むという性質を持つ。 さらに、このリストをpruneして、ポリトープの各頂点に(unique)近似を生成する方法を示す。 適切なSVD部分空間にプロジェクションすれば、トピックモデリング、LDA、最適化オラクルなど、多くの潜時変数設定で存在することが証明できる。 したがって,本研究は,潜在ポリトープの頂点への近似を求める最初の効率的なアルゴリズムである。

関連論文リスト

• Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
  $ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。 我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。 我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
  論文  参考訳（メタデータ） (2024-07-03T16:49:28Z)
• Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes [23.94542304111204]
  勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。 規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
  論文  参考訳（メタデータ） (2023-06-16T17:00:51Z)
• List-Decodable Covariance Estimation [1.9290392443571387]
  共分散推定アルゴリズムを初めて提案する。 この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
  論文  参考訳（メタデータ） (2022-06-22T09:38:06Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain [11.562923882714093]
  Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。 我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
  論文  参考訳（メタデータ） (2021-10-08T07:46:18Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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