論文の概要: Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
- arxiv url: http://arxiv.org/abs/2606.17319v1
- Date: Mon, 15 Jun 2026 22:00:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-17 17:15:32.15418
- Title: Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
- Title（参考訳）: L_\infty$ Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
- Authors: Jasper van Doornmalen, Mathieu Molina, Victor Verdugo, José Verschae,
- Abstract要約: ブールハイパーキューブ上でのサロゲートの学習問題について検討する。
通常の$L$型保証よりも、均一な$L_infty$-error保証が必要です。
本結果は,最適化セーフなサロゲートを学習する際のサンプルの複雑さの厳密な証明を提供する。
- 参考スコア（独自算出の注目度）: 2.5199066832791535
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform $L_\infty$-error guarantees rather than the usual $L_2$-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most $d$ on $n$ variables, the sample complexity scales as $n^{d+1}$. Second, for $s$-sparse Fourier-Walsh polynomials with $s \leq n$, it scales as $ns^2$. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as $n^d$ and $ns$, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the $L_2$-norm do not naturally extend to the $L_\infty$-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the $L_\infty$-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.
- Abstract（参考訳）: 境界二元ブラックボックス関数の最適化により、ブールハイパーキューブ上の多項式代理を学習する問題を研究する。
シュロゲートを最適化するためには、通常の$L_2$-type保証よりも、均一な$L_\infty$-error保証が必要である。
有界多項式の2つのクラスに対する準ガウス雑音下での一様推定のミニマックス標本複雑性を特徴づける。
まず、$n$変数の次数多項式に対して、サンプル複雑性は$n^{d+1}$としてスケールする。
第二に、$s$-sparse Fourier-Walsh 多項式に対して $s \leq n$ は $ns^2$ となる。
これらの値は、それぞれ$n^d$と$ns$の均一な回復スケールを持つノイズレス設定と構造的に異なる。
我々の下限は任意の適応学習者であっても保たれており、付加的な要因が雑音のケースに固有のものであることを示す。
L_2$-normの標準フーリエ解析ツールは、一様保証をもたらす方法で$L_\infty$-settingに自然に拡張するわけではない。
我々の証明は、$L_\infty$-errorを制御するプロキシとして機能する適切な選択された補助規範に頼ることで、この難しさを克服する。
この結果から, 最適化安全多項式代理学習におけるサンプルの複雑さを, より厳密に評価した。
関連論文リスト
- SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳（メタデータ） (2026-06-14T14:11:07Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning [46.80389197344682]
マルチレベルモンテカルロ推定器を用いた自然ポリシー勾配アルゴリズムを開発した。
提案手法は,最適な$widetildemathcalO(-2)$サンプル複雑性を,$$-optimal Policyを演算する上で達成する。
論文 参考訳（メタデータ） (2026-03-09T15:49:10Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - The $L^\infty$ Learnability of Reproducing Kernel Hilbert Spaces [3.2931415075553576]
カーネル空間の学習可能性(RKHS)を$Linfty$ノルムで解析する。
球面上のドット積核に対しては、ヒルベルトサンプルを用いて$Linfty$学習が達成できる条件を特定する。
論文 参考訳（メタデータ） (2023-06-05T12:29:13Z) - Toward $L_\infty$-recovery of Nonlinear Functions: A Polynomial Sample
Complexity Bound for Gaussian Random Fields [35.76184529520015]
多くの機械学習アプリケーションは、入力ドメイン全体、すなわち$L_infty$-errorで最小ケースエラーの関数を学習する必要がある。
既存の理論的研究の多くは、$L$-errorのような平均エラーの回復を保証するだけである。
本稿では, 地絡関数のランダム性を生かして, 不合理性以外のいくつかの初期ステップについて述べる。
論文 参考訳（メタデータ） (2023-04-29T18:33:39Z) - A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。
ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。
これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文 参考訳（メタデータ） (2023-02-26T01:15:32Z) - 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) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。