論文の概要: Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions

• arxiv url: http://arxiv.org/abs/2205.13056v1
• Date: Wed, 25 May 2022 21:31:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-28 08:59:38.565429
• Title: Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions
• Title（参考訳）: 一般化線形関数に対する効率良く, ほぼ最適なオンライン学習
• Authors: Adam Block and Max Simchowitz
• Abstract要約: 我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。 一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
• 参考スコア（独自算出の注目度）: 28.30744223973527
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Due to the drastic gap in complexity between sequential and batch statistical learning, recent work has studied a smoothed sequential learning setting, where Nature is constrained to select contexts with density bounded by 1/{\sigma} with respect to a known measure {\mu}. Unfortunately, for some function classes, there is an exponential gap between the statistically optimal regret and that which can be achieved efficiently. In this paper, we give a computationally efficient algorithm that is the first to enjoy the statistically optimal log(T/{\sigma}) regret for realizable K-wise linear classification. We extend our results to settings where the true classifier is linear in an over-parameterized polynomial featurization of the contexts, as well as to a realizable piecewise-regression setting assuming access to an appropriate ERM oracle. Somewhat surprisingly, standard disagreement-based analyses are insufficient to achieve regret logarithmic in 1/{\sigma}. Instead, we develop a novel characterization of the geometry of the disagreement region induced by generalized linear classifiers. Along the way, we develop numerous technical tools of independent interest, including a general anti-concentration bound for the determinant of certain matrix averages.
• Abstract（参考訳）: 逐次的統計学習とバッチ的統計学習の複雑さの劇的なギャップにより、最近の研究はスムーズな逐次学習環境を研究しており、Nature は既知の測度 {\mu} に対して 1/{\sigma} で束縛された密度のコンテキストを選択することを制約している。 残念ながら、いくつかの関数クラスでは、統計的に最適な後悔と効率的に達成できる後悔の間に指数関数的なギャップがある。 本稿では,K-wise線形分類において,統計的に最適なログ(T/{\sigma})を初めて楽しむ計算効率の良いアルゴリズムを提案する。 我々は、実分類器が文脈の過度なパラメータ化多項式分解において線型であるような設定に拡張し、適切なERMオラクルへのアクセスを仮定する、実現可能な断片的回帰設定に拡張する。 驚くべきことに、標準不一致に基づく分析は1/{\sigma} における後悔の対数を達成するには不十分である。 代わりに、一般化線形分類器によって引き起こされる不一致領域の幾何学の新たな特徴付けを開発する。 その過程で、ある行列平均の行列式に対する一般の反集中を含む、独立した興味を持つ多数の技術ツールを開発する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。 インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。 これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
  論文  参考訳（メタデータ） (2023-09-27T21:54:52Z)
• Nonlinear Feature Aggregation: Two Algorithms driven by Theory [45.3190496371625]
  現実世界の機械学習アプリケーションは、膨大な機能によって特徴付けられ、計算やメモリの問題を引き起こす。 一般集約関数を用いて特徴量の非線形変換を集約する次元還元アルゴリズム(NonLinCFA)を提案する。 また、アルゴリズムを合成および実世界のデータセット上でテストし、回帰および分類タスクを実行し、競合性能を示す。
  論文  参考訳（メタデータ） (2023-06-19T19:57:33Z)
• Scalable Bayesian Meta-Learning through Generalized Implicit Gradients [64.21628447579772]
  Inlicit Bayesian Meta-learning (iBaML) 法は、学習可能な事前のスコープを広げるだけでなく、関連する不確実性も定量化する。 解析誤差境界は、明示的よりも一般化された暗黙的勾配の精度と効率を示すために確立される。
  論文  参考訳（メタデータ） (2023-03-31T02:10:30Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。 任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
  論文  参考訳（メタデータ） (2023-01-16T02:57:37Z)
• Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning [90.8576971748142]
  閉形式解によって最適化できる新しいサロゲートを開発する。 そこで我々は, 上向きの相関関係を利用して, 適応的相関学習モデルを構築した。
  論文  参考訳（メタデータ） (2022-03-04T08:50:50Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses [0.0]
  動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。 文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
  論文  参考訳（メタデータ） (2021-09-28T15:06:31Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Expectation propagation on the diluted Bayesian classifier [0.0]
  本稿では,二項分類の文脈におけるスパース特徴選択の問題に対処する統計力学にインスパイアされた戦略を導入する。 予測伝搬(EP)として知られる計算スキームは、分類規則を学習する連続重みの知覚を訓練するために用いられる。 EPは、変数選択特性、推定精度、計算複雑性の点で頑健で競争力のあるアルゴリズムである。
  論文  参考訳（メタデータ） (2020-09-20T23:59:44Z)

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

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