論文の概要: Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications
- arxiv url: http://arxiv.org/abs/2311.05116v3
- Date: Sat, 11 May 2024 23:25:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-15 01:02:54.912739
- Title: Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications
- Title（参考訳）: 実代数的品種数とそれを超えるもの:改良された境界と応用
- Authors: Yifan Zhang, Joe Kileel,
- Abstract要約: ユークリッド空間における集合の被覆数について上限を証明する。
ここでは、イムディン・コントによる最もよく知られた一般境界が改善されることが示される。
本稿では,3つの計算応用における結果のパワーについて説明する。
- 参考スコア（独自算出の注目度）: 8.438718130535296
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Covering numbers are a powerful tool used in the development of approximation algorithms, randomized dimension reduction methods, smoothed complexity analysis, and others. In this paper we prove upper bounds on the covering number of numerous sets in Euclidean space, namely real algebraic varieties, images of polynomial maps and semialgebraic sets in terms of the number of variables and degrees of the polynomials involved. The bounds remarkably improve the best known general bound by Yomdin-Comte, and our proof is much more straightforward. In particular, 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 illustrate the power of the result on three computational applications. Firstly, we derive a near-optimal bound on the covering number of low rank CP tensors, quantifying their approximation properties and filling in an important missing piece of theory for tensor dimension reduction and reconstruction. Secondly, we prove a bound on the required dimension for the randomized sketching of polynomial optimization problems, which controls how much computation can be saved through randomization without sacrificing solution quality. Finally, we deduce generalization error bounds for deep neural networks with rational or ReLU activation functions, improving or matching the best known results in the machine learning literature while helping to quantify the impact of architecture choice on generalization error.
- Abstract（参考訳）: 被覆数は近似アルゴリズム、ランダム化次元減少法、滑らか化複雑性解析などの開発に使用される強力なツールである。
本稿では、ユークリッド空間における多数の集合の被覆数、すなわち実代数多様体、多項式写像の像および多項式の変数の数と次数の観点から半代数集合の上限を証明する。
境界はヨムディン・コンテの最もよく知られた一般化を著しく改善し、我々の証明ははるかに単純である。
特に、この結果は多項式写像と半代数集合の像の管状近傍の体積に新たな境界を与える。
本稿では,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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。