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

• arxiv url: http://arxiv.org/abs/2108.06808v1
• Date: Sun, 15 Aug 2021 20:12:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-17 14:54:10.963905
• 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はBregman分散を誘導する距離生成関数の条件数に密接に依存する非自明なマージンを持つことを示す。 本研究は,ミラー降下(MD)に拡張し,マージンとブレグマンの分岐点との類似の関連性を確立した。
• 参考スコア（独自算出の注目度）: 32.9787286303952
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bregman proximal point algorithm (BPPA), as one of the centerpieces in the optimization toolbox, has been witnessing emerging applications. With simple and easy to implement update rule, the algorithm bears several compelling intuitions for empirical successes, yet rigorous justifications are still largely unexplored. We study the computational properties of BPPA through classification tasks with separable data, and demonstrate provable algorithmic regularization effects associated with BPPA. We show that BPPA attains non-trivial margin, which closely depends on the condition number of the distance generating function inducing the Bregman divergence. We further demonstrate that the dependence on the condition number is tight for a class of problems, thus showing the importance of divergence in affecting the quality of the obtained solutions. In addition, we extend our findings to mirror descent (MD), for which we establish similar connections between the margin and Bregman divergence. We demonstrate through a concrete example, and show BPPA/MD converges in direction to the maximal margin solution with respect to the Mahalanobis distance. Our theoretical findings are among the first to demonstrate the benign learning properties BPPA/MD, and also provide corroborations for a careful choice of divergence in the algorithmic design.
• Abstract（参考訳）: bregman proximal point algorithm (bppa) は最適化ツールボックスの中心的要素の一つであり、新しいアプリケーションを見てきた。 シンプルで実装が容易なアップデートルールでは、このアルゴリズムには経験的成功に対する説得力のある直観がいくつかあるが、厳格な正当化はいまだにほとんど解明されていない。 BPPAの計算特性について,分離可能なデータを用いた分類タスクを用いて検討し,BPPAに関連するアルゴリズム正則化効果を示す。 BPPAはBregman分散を誘導する距離生成関数の条件数に密接に依存する非自明なマージンを持つことを示す。 さらに, 条件数依存性が問題の種類に密着していることを示し, 得られた解の質に影響を与えるため, 発散の重要性を示した。 さらに,鏡面下降 (mirror descend, md) にも知見を拡張し,マージンとブレグマンの発散との類似性を確立した。 我々は,具体的な例を通して,BPPA/MDがマハラノビス距離に対して最大辺解に収束することを示す。 我々の理論的な知見は、BPPA/MDの良性学習特性を初めて証明し、アルゴリズム設計における相違点の選択を慎重に行うためのコロンボレーションを提供するものである。

関連論文リスト

• 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)

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

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