論文の概要: Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data

• arxiv url: http://arxiv.org/abs/2108.06808v5
• Date: Fri, 25 Aug 2023 03:48:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-28 18:33:04.255985
• Title: Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data
• Title（参考訳）: bregman近位点アルゴリズムの暗黙的正則化と分離可能データによるミラー降下
• Authors: Yan Li, Caleb Ju, Ethan X. Fang, Tuo Zhao
• Abstract要約: 本稿では,Bregman近位点アルゴリズム(BPPA)の線形分類器を分離可能なデータで学習し,計算特性について検討する。 固定されたブレグマン発散を持つ任意のBPPAに対して、任意に選択されたノルムに対してBPPAによって得られるマージンの低い境界を与える。 条件数への依存がきついことを示し、学習した分類器の品質に影響を及ぼすためのばらつきの重要性を示す。
• 参考スコア（独自算出の注目度）: 34.47041199362242
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Bregman proximal point algorithm (BPPA) has witnessed emerging machine learning applications, yet its theoretical understanding has been largely unexplored. We study the computational properties of BPPA through learning linear classifiers with separable data, and demonstrate provable algorithmic regularization of BPPA. For any BPPA instantiated with a fixed Bregman divergence, we provide a lower bound of the margin obtained by BPPA with respect to an arbitrarily chosen norm. The obtained margin lower bound differs from the maximal margin by a multiplicative factor, which inversely depends on the condition number of the distance-generating function measured in the dual norm. We show that the dependence on the condition number is tight, thus demonstrating the importance of divergence in affecting the quality of the learned classifiers. We then extend our findings to mirror descent, for which we establish similar connections between the margin and Bregman divergence, together with a non-asymptotic analysis. Numerical experiments on both synthetic and real-world datasets are provided to support our theoretical findings. To the best of our knowledge, the aforementioned findings appear to be new in the literature of algorithmic regularization.
• Abstract（参考訳）: Bregman近点アルゴリズム(BPPA)は、新しい機械学習アプリケーションを見てきたが、その理論的理解はほとんど解明されていない。 本稿では,線形分類器を分離可能なデータで学習することでBPPAの計算特性を検証し,BPPAのアルゴリズム正則化を実証する。 固定されたブレグマン発散を持つ任意のBPPAに対して、任意に選択されたノルムに対してBPPAによって得られるマージンの低い境界を与える。 得られたマージン下限は乗算係数によって最大辺と異なるが、これは逆に双対ノルムで測定された距離生成関数の条件数に依存する。 条件数への依存がきついことを示し、学習した分類器の品質に影響を及ぼす上でのばらつきの重要性を示す。 そして、この知見をミラー降下に拡張し、非漸近解析とともに、マージンとブレグマン分岐の類似した関係を確立する。 理論的研究を支援するために, 合成データセットと実世界のデータセットの数値実験を行った。 私たちの知る限りでは、上記の知見はアルゴリズム正規化の文献に新しいものと思われる。

関連論文リスト

• Pareto Set Identification With Posterior Sampling [14.121842087273167]
  本稿では,PSIを有意な相関性を有する線形変換系で検討する。 既存のオラクルベースのアルゴリズムの計算コストを負担することなく,構造と相関を同時に扱うPSIPSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-07T18:15:38Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。 本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。 低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
  論文  参考訳（メタデータ） (2022-11-03T16:42:40Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Self-Certifying Classification by Linearized Deep Assignment [65.0100925582087]
  そこで我々は,PAC-Bayesリスク認定パラダイム内で,グラフ上のメトリックデータを分類するための新しい深層予測器のクラスを提案する。 PAC-Bayesの最近の文献とデータに依存した先行研究に基づいて、この手法は仮説空間上の後続分布の学習を可能にする。
  論文  参考訳（メタデータ） (2022-01-26T19:59:14Z)
• From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits [0.0]
  本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。 この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
  論文  参考訳（メタデータ） (2021-11-18T14:34:21Z)
• Counterfactual Maximum Likelihood Estimation for Training Deep Networks [83.44219640437657]
  深層学習モデルは、予測的手がかりとして学習すべきでない急激な相関を学習する傾向がある。 本研究では,観測可能な共同設立者による相関関係の緩和を目的とした因果関係に基づくトレーニングフレームワークを提案する。 自然言語推論(NLI)と画像キャプションという2つの実世界の課題について実験を行った。
  論文  参考訳（メタデータ） (2021-06-07T17:47:16Z)
• Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization [39.35822033674126]
  生成ガウス混合モデルに基づく二項線形分類について検討する。 後者の分類誤差に関する新しい非漸近境界を導出する。 この結果は, 確率が一定である雑音モデルに拡張される。
  論文  参考訳（メタデータ） (2020-11-18T07:59:55Z)
• On the Convergence Rate of Projected Gradient Descent for a Back-Projection based Objective [58.33065918353532]
  我々は、最小二乗(LS)の代替として、バックプロジェクションに基づく忠実度項を考える。 LS項ではなくBP項を用いることで最適化アルゴリズムの繰り返しを少なくすることを示す。
  論文  参考訳（メタデータ） (2020-05-03T00:58:23Z)
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes [40.31139355952393]
  一般化エンベロープを用いて滑らかなリャプノフ函数を構築し、そのリャプノフ函数に対してSAの反復体が負のドリフトを持つことを示す。 特に、政治以外のTD学習において、Vトレースアルゴリズムの最初の既知収束率を確立するためにこれを用いる。 また、TD学習を現場で研究し、既存の最先端の成果を$Q$ラーニングで回収する。
  論文  参考訳（メタデータ） (2020-02-03T16:42:01Z)
• On Low-rank Trace Regression under General Sampling Distribution [9.699586426043885]
  クロスバリデード推定器は一般仮定でほぼ最適誤差境界を満たすことを示す。 また, クロスバリデーション推定器はパラメータ選択理論に着想を得た手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2019-04-18T02:56:00Z)

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

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