論文の概要: Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications

• arxiv url: http://arxiv.org/abs/2311.05116v2
• Date: Thu, 16 Nov 2023 06:20:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-18 01:08:07.968029
• Title: Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications
• Title（参考訳）: 実代数的品種数とそれを超えるもの:改良された境界と応用
• Authors: Yifan Zhang, Joe Kileel
• Abstract要約: 実多様体の被覆数、写像の像、半代数集合の上界を証明した。 境界は、ヨムディン・コンテによる最もよく知られた一般化を著しく改善する。 我々はこの理論を3つの主要な応用分野に適用する。
• 参考スコア（独自算出の注目度）: 9.969227580774815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove an upper bound on the covering number of real algebraic varieties, images of polynomial maps and semialgebraic sets. The bound remarkably improves the best known general bound by Yomdin-Comte, and its proof is much more straightforward. As a consequence, our result gives new bounds on the volume of the tubular neighborhood of the image of a polynomial map and a semialgebraic set, where results for varieties by Lotz and Basu-Lerario are not directly applicable. We apply our theory to three main application domains. Firstly, we derive a near-optimal bound on the covering number of low rank CP tensors. Secondly, we prove a bound on the sketching dimension for (general) polynomial optimization problems. Lastly, we deduce generalization error bounds for deep neural networks with rational or ReLU activations, improving or matching the best known results in the literature.
• Abstract（参考訳）: 実代数多様体の被覆数、多項式写像の像、半代数集合の上界を証明する。 境界はヨムディン・コンテの最もよく知られた一般化を著しく改善し、その証明ははるかに単純である。 その結果、この結果は多項式写像の像の管状近傍の体積と半代数集合の体積に新たな境界を与え、そこでは Lotz と Basu-Lerario の多様体は直接適用できない。 この理論を3つの主要なアプリケーションドメインに適用します。 まず、低ランクCPテンソルの被覆数に準最適境界を導出する。 次に,(一般)多項式最適化問題に対するスケッチ次元の境界を証明した。 最後に,本論文の最もよく知られた結果に合理性あるいはreluアクティベーションを用いたディープニューラルネットワークの一般化誤差境界を推定する。

関連論文リスト

• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。 これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。 制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
  論文  参考訳（メタデータ） (2022-08-23T18:56:05Z)
• Sum-of-Squares Relaxations for Information Theory and Variational Inference [0.0]
  シャノン相対エントロピーの拡張($f$-divergences)を考える。 これらの分岐を計算するための凸緩和列を導出する。 我々は、量子情報理論から発せられるスペクトル情報に基づいて、より効率的な緩和を提供する。
  論文  参考訳（メタデータ） (2022-06-27T13:22:40Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• A block-sparse Tensor Train Format for sample-efficient high-dimensional Polynomial Regression [0.0]
  低ランクテンソルは高次元問題の確立された枠組みである。 ブロックスパーシティの概念を含めることで、このフレームワークを拡張することを提案する。 これにより、既知のサンプル結果に合致するようにアンサッツ空間を適応させることができる。
  論文  参考訳（メタデータ） (2021-04-29T10:57:53Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。 これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。 ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
  論文  参考訳（メタデータ） (2020-05-11T14:52:16Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。 レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
  論文  参考訳（メタデータ） (2019-09-04T11:46:26Z)

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

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