論文の概要: Stochastic linear optimization never overfits with quadratically-bounded
losses on general data
- arxiv url: http://arxiv.org/abs/2202.06915v1
- Date: Mon, 14 Feb 2022 18:12:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-15 15:34:51.030528
- Title: Stochastic linear optimization never overfits with quadratically-bounded
losses on general data
- Title（参考訳）: 確率線形最適化は一般データ上の二次有界損失に収まらない
- Authors: Matus Telgarsky
- Abstract要約: この研究は、一般データ上での線形最適化手法の多様なコレクションは、明示的な制約や正規化が欠如しているにもかかわらず、過度に適合しないことを示している。
この分析は、多くの設定を扱える基本的だが柔軟な証明方式によって実現されている。
- 参考スコア（独自算出の注目度）: 20.41989568533313
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work shows that a diverse collection of linear optimization methods,
when run on general data, fail to overfit, despite lacking any explicit
constraints or regularization: with high probability, their trajectories stay
near the curve of optimal constrained solutions over the population
distribution. This analysis is powered by an elementary but flexible proof
scheme which can handle many settings, summarized as follows. Firstly, the data
can be general: unlike other implicit bias works, it need not satisfy large
margin or other structural conditions, and moreover can arrive sequentially
IID, sequentially following a Markov chain, as a batch, and lastly it can have
heavy tails. Secondly, while the main analysis is for mirror descent, rates are
also provided for the Temporal-Difference fixed-point method from reinforcement
learning; all prior high probability analyses in these settings required
bounded iterates, bounded updates, bounded noise, or some equivalent. Thirdly,
the losses are general, and for instance the logistic and squared losses can be
handled simultaneously, unlike other implicit bias works. In all of these
settings, not only is low population error guaranteed with high probability,
but moreover low sample complexity is guaranteed so long as there exists any
low-complexity near-optimal solution, even if the global problem structure and
in particular global optima have high complexity.
- Abstract（参考訳）: この研究は、一般データ上での線形最適化手法の多様なコレクションが、明示的な制約や正規化を欠いているにもかかわらず、過度に適合しないことを示している:高い確率で、それらの軌道は、人口分布に対する最適制約された解の曲線の近くに留まる。
この分析は,多数の設定を処理可能な初歩的かつ柔軟な証明スキームによって実現されている。
第一に、データは一般的なものである: 他の暗黙のバイアスとは違って、大きなマージンやその他の構造条件を満たす必要がなく、さらに、マルコフ連鎖を逐次、バッチとして、そして最後に重い尾を持つことができる。
第二に、ミラー降下の主解析は、強化学習による時間差固定点法にも適用され、これらの設定における事前の高確率解析は、有界な繰り返し、有界な更新、有界なノイズ、等式を必要とする。
第3に、損失は一般的であり、例えば、ロジスティックと二乗損失は、他の暗黙のバイアスとは異なり、同時に処理できる。
これらすべての設定において、高い確率で低い集団誤差が保証されるだけでなく、たとえ大域的な問題構造や特に大域的な最適条件が高複雑性であっても、低複雑さに近い最適解が存在する限り、低いサンプル複雑性が保証される。
関連論文リスト
- Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳（メタデータ） (2024-10-22T10:19:27Z) - High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。
クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
論文 参考訳（メタデータ） (2023-10-03T07:49:17Z) - The Decaying Missing-at-Random Framework: Doubly Robust Causal Inference
with Partially Labeled Data [10.021381302215062]
現実のシナリオでは、データ収集の制限によって部分的にラベル付けされたデータセットが生成されることが多く、信頼性の高い因果推論の描画が困難になる。
半パラメトリック(SS)や欠落したデータ文学における従来のアプローチは、これらの複雑さを適切に扱えないため、偏りのある見積もりにつながる可能性がある。
このフレームワークは、高次元設定における欠落した結果に対処し、選択バイアスを考慮に入れます。
論文 参考訳（メタデータ） (2023-05-22T07:37:12Z) - Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
既存の一般化境界は、現代のニューラルネットワークの一般化を促進する重要な要因を説明することができない。
データ空間における学習予測関数の局所リプシッツ正則性に依存するインスタンス依存の一般化境界を導出する。
ニューラルネットワークに対する一般化境界を実験的に解析し、有界値が有意義であることを示し、トレーニング中の一般的な正規化方法の効果を捉える。
論文 参考訳（メタデータ） (2022-11-02T16:39:42Z) - Support Vector Machines with the Hard-Margin Loss: Optimal Training via
Combinatorial Benders' Cuts [8.281391209717105]
我々は、グローバルな最適性のために、ハードマージンのSVMモデルをトレーニングする方法を示す。
本稿では,この問題を解くための反復サンプリングと部分分解アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-15T18:21:51Z) - Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
我々は、差分プライベート(DP)を保証する重み付きデータに対する差分プライベート凸最適化について検討する。
我々は,制約付きおよび制約なし凸問題に対するAClipped-dpSGDというアルゴリズムに対して,新たな収束結果を確立し,複雑性境界を改善した。
論文 参考訳（メタデータ） (2022-06-27T01:39:15Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳（メタデータ） (2021-06-29T09:48:46Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - The Implicit Bias of Gradient Descent on Separable Data [44.98410310356165]
予測器は最大マージン(シャープマージンSVM)解の方向へ収束することを示す。
これは、トレーニングエラーがゼロになった後もロジスティックまたはクロスエントロピー損失を最適化し続ける利点を説明するのに役立つ。
論文 参考訳（メタデータ） (2017-10-27T21:47:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。