論文の概要: Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization
- arxiv url: http://arxiv.org/abs/2402.09327v2
- Date: Thu, 18 Jul 2024 17:37:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-19 21:31:34.508300
- Title: Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization
- Title（参考訳）: 確率凸最適化の情報複雑性:一般化と記憶への応用
- Authors: Idan Attias, Gintare Karolina Dziugaite, Mahdi Haghifam, Roi Livni, Daniel M. Roy,
- Abstract要約: 我々は,円錐曲線最適化(SCO)の文脈における記憶と学習の相互作用について検討する。
我々は,Steinke と Zakynthinou が提唱した条件付き相互情報(CMI)の枠組みを用いた記憶の定量化(2020年)
L2$ Lipschitz-bounded set and under strong convexity, every learner with a excess error have CMI bounded by $Omega (1/varepsilon2)$ and $Omega (1/varepsilon)$。
- 参考スコア（独自算出の注目度）: 36.28082578445787
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we investigate the interplay between memorization and learning in the context of \emph{stochastic convex optimization} (SCO). We define memorization via the information a learning algorithm reveals about its training data points. We then quantify this information using the framework of conditional mutual information (CMI) proposed by Steinke and Zakynthinou (2020). Our main result is a precise characterization of the tradeoff between the accuracy of a learning algorithm and its CMI, answering an open question posed by Livni (2023). We show that, in the $L^2$ Lipschitz--bounded setting and under strong convexity, every learner with an excess error $\varepsilon$ has CMI bounded below by $\Omega(1/\varepsilon^2)$ and $\Omega(1/\varepsilon)$, respectively. We further demonstrate the essential role of memorization in learning problems in SCO by designing an adversary capable of accurately identifying a significant fraction of the training samples in specific SCO problems. Finally, we enumerate several implications of our results, such as a limitation of generalization bounds based on CMI and the incompressibility of samples in SCO problems.
- Abstract（参考訳）: 本研究では, 記憶と学習の相互作用を, \emph{stochastic convex Optimization} (SCO) の文脈で検討する。
学習アルゴリズムが学習データポイントについて示す情報を介して記憶を定義する。
そこで我々は,Steinke と Zakynthinou (2020) が提唱した条件付き相互情報(CMI)の枠組みを用いて,この情報を定量化する。
我々の主な成果は、Livni (2023) が提示したオープンな質問に答え、学習アルゴリズムの精度と CMI とのトレードオフを正確に評価することである。
L^2$ Lipschitz-bounded set and under strong convexity, with a excess error $\varepsilon$ has CMI bounded by $\Omega(1/\varepsilon^2)$ and $\Omega(1/\varepsilon)$。
さらに,特定のSCO問題におけるトレーニングサンプルのかなりの割合を正確に識別できる敵を設計することで,SCOにおける学習問題における記憶機能の重要性を実証する。
最後に、CMIに基づく一般化境界の制限やSCO問題におけるサンプルの非圧縮など、結果のいくつかの意味を列挙する。
関連論文リスト
- Gauge-optimal approximate learning for small data classification
problems [0.0]
小さなデータ学習問題は、応答変数の観測量が限られたことと大きな特徴空間次元との相違によって特徴づけられる。
本稿では,Gauge-Optimal Approximate Learning (GOAL)アルゴリズムを提案する。
GOALは、合成データと、気候科学やバイオインフォマティクスといった現実世界の応用に挑戦する、最先端の機械学習(ML)ツールと比較されている。
論文 参考訳（メタデータ） (2023-10-29T16:46:05Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - Evaluated CMI Bounds for Meta Learning: Tightness and Expressiveness [14.147617330278662]
評価CMI(e-CMI)を用いたメタ学習のための新しい一般化境界を提案する。
e-CMI フレームワークは、$sqrt の数学カル C(mathcal H)/(nhat n) + 数学カル C(mathcal F)/n $, ここで $mathcal C(cdot)$ は仮説クラスの複雑性測度を表す。
論文 参考訳（メタデータ） (2022-10-12T18:10:59Z) - On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
残余条件付き相互情報(loo-CMI)の新しい尺度に基づく教師付き学習アルゴリズムのための情報理論の一般化境界を導出する。
他のCMI境界とは対照的に、我々のloo-CMI境界は容易に計算でき、古典的なout-out-out-cross-validationのような他の概念と関連して解釈できる。
ディープラーニングのシナリオにおいて予測された一般化ギャップを評価することにより,境界の質を実証的に検証する。
論文 参考訳（メタデータ） (2022-07-01T17:58:29Z) - Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。
特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。
以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文 参考訳（メタデータ） (2022-02-08T16:39:57Z) - Towards a Unified Information-Theoretic Framework for Generalization [43.23033319683591]
まず、このフレームワークを用いて、任意の学習アルゴリズムに対して非自明な(しかし、準最適)境界を表現できることを実証する。
我々は、CMIフレームワークが、ハーフスペースを学習するためのSVM(Support Vector Machines)の予測されるリスクに最適な境界をもたらすことを証明した。
論文 参考訳（メタデータ） (2021-11-09T17:09:40Z) - Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning [15.544041797200045]
ベイズ学習における最小余剰リスク(MER)は、データから学ぶ際に達成可能な最小損失と、基礎となるパラメータ$W$が観測された場合に達成できる最小損失との差として定義される。
我々は、これらの上界と下界の差に関する情報理論的境界を導出し、それらがMERに対して秩序的に厳密なレートを提供できることを示す。
論文 参考訳（メタデータ） (2021-05-10T08:14:10Z) - Learner-Private Online Convex Optimization [24.204781914017758]
オンライン凸最適化において,学習者のクエリを最適に難読化する方法について検討する。
本結果は,全次フィードバックを持つ一般凸関数のよりリッチなファミリに適用できる。
論文 参考訳（メタデータ） (2021-02-23T23:00:44Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳（メタデータ） (2020-06-22T17:58:54Z) - CLUB: A Contrastive Log-ratio Upper Bound of Mutual Information [105.73798100327667]
本稿では,相互情報の対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物
CLUBの特性とその変分近似に関する理論的解析を行う。
この上限に基づいてMI最小化学習手法を導入し、さらに負のサンプリング戦略で加速する。
論文 参考訳（メタデータ） (2020-06-22T05:36:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。