論文の概要: Efficient Agnostic Learning with Average Smoothness
- arxiv url: http://arxiv.org/abs/2309.17016v2
- Date: Tue, 13 Feb 2024 10:03:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 19:33:12.692439
- Title: Efficient Agnostic Learning with Average Smoothness
- Title（参考訳）: 平均平滑度をもつ効率的無依存学習
- Authors: Steve Hanneke, Aryeh Kontorovich, Guy Kornowski
- Abstract要約: 分布のない一様収束を,非依存的条件における平均平滑性クラスに限定する。
以上の結果から,最近得られた平均平滑関数の認識能力の保証が,非依存的な環境に伝達されることが示唆された。
証明の核心は、そのブラケットエントロピーの観点から関数クラスの一様収束率を確立することである。
- 参考スコア（独自算出の注目度）: 29.856963741898007
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study distribution-free nonparametric regression following a notion of
average smoothness initiated by Ashlagi et al. (2021), which measures the
"effective" smoothness of a function with respect to an arbitrary unknown
underlying distribution. While the recent work of Hanneke et al. (2023)
established tight uniform convergence bounds for average-smooth functions in
the realizable case and provided a computationally efficient realizable
learning algorithm, both of these results currently lack analogs in the general
agnostic (i.e. noisy) case.
In this work, we fully close these gaps. First, we provide a
distribution-free uniform convergence bound for average-smoothness classes in
the agnostic setting. Second, we match the derived sample complexity with a
computationally efficient agnostic learning algorithm. Our results, which are
stated in terms of the intrinsic geometry of the data and hold over any totally
bounded metric space, show that the guarantees recently obtained for realizable
learning of average-smooth functions transfer to the agnostic setting. At the
heart of our proof, we establish the uniform convergence rate of a function
class in terms of its bracketing entropy, which may be of independent interest.
- Abstract（参考訳）: ashlagi et al. (2021) によって始められた平均平滑性の概念に従い, 任意の未知の分布に対する関数の「効果的な」平滑性を測定する分布自由非パラメトリック回帰について検討した。
Hanneke et al. (2023) の最近の研究は、現実化可能なケースにおける平均滑らかな関数に対する厳密な一様収束境界を確立し、計算効率の良い実化可能な学習アルゴリズムを提供したが、これらの結果はどちらも一般的な無依存(すなわち雑音)の場合のアナログを欠いている。
この作業では、これらのギャップを完全に埋めます。
まず, 分布を伴わない一様収束を, 平均-smoothness クラスに限定して提供する。
第2に,抽出したサンプル複雑性を,計算効率のよい非依存学習アルゴリズムとマッチングする。
この結果は,データの内部幾何学的に記述され,任意の全有界距離空間を包含するものであるが,最近得られた平均スムース関数の学習を不可知な設定に移すための保証が示されている。
証明の核心では、関数クラスの一様収束率は、その括弧エントロピー(独立興味を持つかもしれない)の観点から定まる。
関連論文リスト
- Statistical Inference for Temporal Difference Learning with Linear Function Approximation [62.69448336714418]
時間差差(TD)学習は、おそらく政策評価に最も広く使用されるものであり、この目的の自然な枠組みとして機能する。
本稿では,Polyak-Ruppert平均化と線形関数近似によるTD学習の整合性について検討し,既存の結果よりも3つの重要な改善点を得た。
論文 参考訳（メタデータ） (2024-10-21T15:34:44Z) - Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation [23.89036529638614]
近似(SA)におけるパラメータの時間一様統計的推測について検討する。
線形および非線形のSA問題の両方において,平均的反復のほぼ無限収束率をガウスのスケールした和に解析する。
論文 参考訳（メタデータ） (2024-10-19T10:27:26Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。
本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
論文 参考訳（メタデータ） (2023-06-13T01:18:16Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-08-22T16:00:45Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Functions with average smoothness: structure, algorithms, and learning [12.362670630646804]
各点における局所勾配を定義し、これらの値の平均として関数複雑性を測る。
平均は最大よりも劇的に小さくなるので、この複雑性測度はよりシャープな一般化境界が得られる。
私たちは定義した関数クラスにおいて驚くほどリッチで解析的な構造を発見します。
論文 参考訳（メタデータ） (2020-07-13T10:06:58Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳（メタデータ） (2020-03-27T05:13:29Z) - StochasticRank: Global Optimization of Scale-Free Discrete Functions [28.224889996383396]
本稿では,ランキングメトリクスを直接最適化する強力な,効率的なフレームワークを提案する。
古典的平滑化アプローチは偏見を導入し, 適切な偏見の普遍解を示す。
我々のフレームワークは任意のスケールフリー離散損失関数に適用できる。
論文 参考訳（メタデータ） (2020-03-04T15:27:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。