論文の概要: Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
- arxiv url: http://arxiv.org/abs/2602.24178v1
- Date: Fri, 27 Feb 2026 16:59:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-02 19:48:24.527773
- Title: Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
- Title（参考訳）: 低内在次元の幾何学的概念のためのサンドウィッチポリノミアル
- Authors: Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan,
- Abstract要約: そこで本研究では,いくつかの基本関数クラスと限界分布に対して,大幅に改良された次数境界が得られる低次サンドイッチ構築法を提案する。
我々の証明は比較的単純であり、ターゲット関数の境界の滑らかさを直接利用してサンドイッチング・リプシッツ関数を構築する。
- 参考スコア（独自算出の注目度）: 23.43080600040766
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent work has shown the surprising power of low-degree sandwiching polynomial approximators in the context of challenging learning settings such as learning with distribution shift, testable learning, and learning with contamination. A pair of sandwiching polynomials approximate a target function in expectation while also providing pointwise upper and lower bounds on the function's values. In this paper, we give a new method for constructing low-degree sandwiching polynomials that yield greatly improved degree bounds for several fundamental function classes and marginal distributions. In particular, we obtain degree $\mathrm{poly}(k)$ sandwiching polynomials for functions of $k$ halfspaces under the Gaussian distribution, improving exponentially over the prior $2^{O(k)}$ bound. More broadly, our approach applies to function classes that are low-dimensional and have smooth boundary. In contrast to prior work, our proof is relatively simple and directly uses the smoothness of the target function's boundary to construct sandwiching Lipschitz functions, which are amenable to results from high-dimensional approximation theory. For low-dimensional polynomial threshold functions (PTFs) with respect to Gaussians, we obtain doubly exponential improvements without applying the FT-mollification method of Kane used in the best previous result.
- Abstract（参考訳）: 近年の研究では、分散シフトによる学習、テスト可能な学習、汚染による学習といった学習環境において、低次サンドイッチ多項式近似器の驚くべき力を示している。
一対のサンドイッチ多項式は、期待する対象関数を近似し、関数の値に点方向の上と下の境界を与える。
本稿では,いくつかの基本関数クラスと限界分布に対して,大幅に改善された次数境界が得られる低次サンドイッチ多項式を構築するための新しい方法を提案する。
特に、ガウス分布の下では、$k$半空間の函数に対して次数 $\mathrm{poly}(k)$ サンドイッチ多項式を得ることができ、以前の 2^{O(k)}$ 境界よりも指数関数的に改善される。
より広義に、我々のアプローチは低次元かつ滑らかな境界を持つ函数類に適用される。
従来の研究とは対照的に、我々の証明は比較的単純であり、ターゲット関数の境界の滑らかさを直接利用してサンドイッチング・リプシッツ関数を構築し、これは高次元近似理論から得られる。
ガウス関数に対する低次元多項式しきい値関数 (PTFs) に対して、最前の結果に使用されるKe の FT-mollification 法を適用することなく、二重指数的改善が得られる。
関連論文リスト
- Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysis [13.02728413691724]
複素解析により、基礎となるデンジョイ・カールマンのかなり厳密な類似性を開発する。
分布の一般クラス上の関数に対する近似理論の結果を$L2$に設定する。
別の応用として、Paley-Wiener級関数が$[-,]$にバンド化されることを示し、全ての厳密な部分指数分布に対する近似の超指数率を認める。
論文 参考訳（メタデータ） (2025-12-04T01:40:05Z) - On Uniform Weighted Deep Polynomial approximation [0.0]
本研究では,一方の非対称な振舞いと他方の減衰を有する関数に適した重み付き深部近似剤のクラスを導入,解析する。
このフレームワークがTaylor, Chebyshev, and standard Deep Approximantsより優れていることを示す。
論文 参考訳（メタデータ） (2025-06-26T14:25:32Z) - Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
ユークリッド空間における多くの集合の被覆数について上限を証明する。
本稿では,3つの計算応用における結果のパワーについて説明する。
論文 参考訳（メタデータ） (2023-11-09T03:06:59Z) - Stochastic Submodular Maximization via Polynomial Estimators [13.498923494159312]
未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。
この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
論文 参考訳（メタデータ） (2023-03-17T13:32:33Z) - The Optimality of Polynomial Regression for Agnostic Learning under
Gaussian Marginals [47.81107898315438]
そこで我々は,二元性LPを用いて,多種多様な問題に対するサンプルのハードファミリーを見つける手法を開発した。
L1$-regression は本質的には最適であり、概念クラスを学習する際の計算困難さは、クラスから任意の関数を近似するのに要する次数と密接に関連していることが示される。
論文 参考訳（メタデータ） (2021-02-08T18:06:32Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z) - On Sharpness of Error Bounds for Multivariate Neural Network
Approximation [0.0]
この論文は、このようなリッジ関数の和による最良の非線形近似を扱う。
誤差境界は滑らかさのモジュライで表される。
論文 参考訳（メタデータ） (2020-04-05T14:00:52Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。