論文の概要: Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective

• arxiv url: http://arxiv.org/abs/2502.10292v1
• Date: Fri, 14 Feb 2025 16:52:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-17 14:47:43.262552
• Title: Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective
• Title（参考訳）: オンライン学習分離関数クラスのための小さな損失境界:ガウス過程の視点
• Authors: Adam Block, Abhishek Shetty,
• Abstract要約: そこで本研究では,従来の研究よりも高い一般化率で低損失境界を達成できるオラクル効率のアルゴリズムを提案する。 また,この分離条件下では,最適な学習率が得られる差分プライベート学習の変種も提示する。
• 参考スコア（独自算出の注目度）: 9.867914513513453
• License:
• Abstract: In order to develop practical and efficient algorithms while circumventing overly pessimistic computational lower bounds, recent work has been interested in developing oracle-efficient algorithms in a variety of learning settings. Two such settings of particular interest are online and differentially private learning. While seemingly different, these two fields are fundamentally connected by the requirement that successful algorithms in each case satisfy stability guarantees; in particular, recent work has demonstrated that algorithms for online learning whose performance adapts to beneficial problem instances, attaining the so-called small-loss bounds, require a form of stability similar to that of differential privacy. In this work, we identify the crucial role that separation plays in allowing oracle-efficient algorithms to achieve this strong stability. Our notion, which we term $\rho$-separation, generalizes and unifies several previous approaches to enforcing this strong stability, including the existence of small-separator sets and the recent notion of $\gamma$-approximability. We present an oracle-efficient algorithm that is capable of achieving small-loss bounds with improved rates in greater generality than previous work, as well as a variant for differentially private learning that attains optimal rates, again under our separation condition. In so doing, we prove a new stability result for minimizers of a Gaussian process that strengthens and generalizes previous work.
• Abstract（参考訳）: 過度に悲観的な計算下界を回避しつつ、実用的で効率的なアルゴリズムを開発するために、最近の研究は、様々な学習環境において、オラクル効率のアルゴリズムを開発することに興味を持っている。 このような、特定の関心の2つの設定は、オンラインと差分的にプライベートな学習である。 特に最近の研究では、パフォーマンスが有益な問題インスタンスに適応するオンライン学習のためのアルゴリズムが、いわゆる小さな損失境界に達するためには、差分プライバシーと同様の安定性を必要とすることが示されている。 本研究では,この強い安定性を実現するために,分子効率の高いアルゴリズムの分離が果たす重要な役割を明らかにする。 私たちの考えは、$\rho$-セパレーション(英語版)と呼ばれ、小さな分離集合の存在や最近の$\gamma$-approximability(英語版)の概念を含む、この強い安定性を強制するためのいくつかの以前のアプローチを一般化し、統一する。 本稿では,従来の研究よりも高い一般化率で低損失境界を達成できるオラクル効率のアルゴリズムと,この分離条件下でも最適な学習率が得られる差分プライベート学習のための変種を提案する。 このようにして、ガウス過程の最小化子に対する新しい安定性の結果を証明し、従来の作業を強化し一般化する。

関連論文リスト

• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  線形関数近似を用いた強化学習について検討する。 既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。 我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
  論文  参考訳（メタデータ） (2021-06-22T08:48:56Z)
• Machine Unlearning via Algorithmic Stability [31.809738694273623]
  我々はマシンアンラーニングの問題を研究し、総変動(TV)安定性の概念を特定します。 凸リスク最小化問題に対して、ノイズグラディエントDescent(SGD)に基づくTV安定アルゴリズムを設計する。 我々のアルゴリズムを一般化する手法も微分プライベートである。
  論文  参考訳（メタデータ） (2021-02-25T21:16:56Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)

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

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