論文の概要: Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression

• arxiv url: http://arxiv.org/abs/2412.07999v1
• Date: Wed, 11 Dec 2024 00:48:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-12 14:01:31.062606
• Title: Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression
• Title（参考訳）: データ拡張アルゴリズムの高速混合 - Bayesian Probit, Logit, Lasso Regression
• Authors: Holden Lee, Kexin Zhang,
• Abstract要約: 本稿では,3つの重要なDAアルゴリズム(ProbitDA,LogitDA,LassoDA)の混合時間に関する非漸近上界を初めて証明する。 結果は一般に、ProbitとLogitのレグレッションで高度に不均衡なレスポンスデータを含む、大きな$n$と大きな$d$の設定に適用できる。
• 参考スコア（独自算出の注目度）: 8.925628430885572
• License:
• Abstract: Despite the widespread use of the data augmentation (DA) algorithm, the theoretical understanding of its convergence behavior remains incomplete. We prove the first non-asymptotic polynomial upper bounds on mixing times of three important DA algorithms: DA algorithm for Bayesian Probit regression (Albert and Chib, 1993, ProbitDA), Bayesian Logit regression (Polson, Scott, and Windle, 2013, LogitDA), and Bayesian Lasso regression (Park and Casella, 2008, Rajaratnam et al., 2015, LassoDA). Concretely, we demonstrate that with $\eta$-warm start, parameter dimension $d$, and sample size $n$, the ProbitDA and LogitDA require $\mathcal{O}\left(nd\log \left(\frac{\log \eta}{\epsilon}\right)\right)$ steps to obtain samples with at most $\epsilon$ TV error, whereas the LassoDA requires $\mathcal{O}\left(d^2(d\log d +n \log n)^2 \log \left(\frac{\eta}{\epsilon}\right)\right)$ steps. The results are generally applicable to settings with large $n$ and large $d$, including settings with highly imbalanced response data in the Probit and Logit regression. The proofs are based on the Markov chain conductance and isoperimetric inequalities. Assuming that data are independently generated from either a bounded, sub-Gaussian, or log-concave distribution, we improve the guarantees for ProbitDA and LogitDA to $\tilde{\mathcal{O}}(n+d)$ with high probability, and compare it with the best known guarantees of Langevin Monte Carlo and Metropolis Adjusted Langevin Algorithm. We also discuss the mixing times of the three algorithms under feasible initialization.
• Abstract（参考訳）: データ拡張(DA)アルゴリズムが広く使われているにもかかわらず、その収束挙動の理論的理解はいまだ不完全である。 3つの重要なDAアルゴリズムの混合時間に関する最初の非漸近多項式上界を証明した: DA algorithm for Bayesian Probit regression (Albert and Chib, 1993, ProbitDA), Bayesian Logit regression (Polson, Scott, and Windle, 2013 LogitDA), Bayesian Lasso regression (Park and Casella, 2008 Rajaratnam et al , 2015 LassoDA)。 具体的には、$\eta$-warm start, parameter dimension $d$, sample size $n$, the ProbitDA and LogitDA requires $\mathcal{O}\left(\frac{\log \eta}{\epsilon}\right)\right)$ steps to obtain sample with at least $\epsilon$ TV error, and the LassoDA requires $\mathcal{O}\left(d^2(d\log d +n \log n)^2 \log \left(\frac{\eta}{\epsilon}\right)\right)$ steps。 結果は一般に、ProbitとLogitのレグレッションで高度に不均衡なレスポンスデータを含む、大きな$n$と大きな$d$の設定に適用できる。 証明はマルコフ連鎖のコンダクタンスと等尺不等式に基づいている。 データが有界、準ガウス分布、あるいは対数凹分布から独立に生成されると仮定すると、ProbitDAとLogitDAの保証を高い確率で$\tilde{\mathcal{O}}(n+d)$に改善し、ランゲバンモンテカルロとメトロポリス調整ランゲバンアルゴリズムの保証と比較する。 また,3つのアルゴリズムの混合時間についても検討した。

関連論文リスト

• Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
  2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。 2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
  論文  参考訳（メタデータ） (2024-10-31T13:51:59Z)
• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-06-01T07:33:41Z)
• Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
  多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。 我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
  論文  参考訳（メタデータ） (2024-03-05T12:28:00Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization [14.69450310695133]
  signSGDの既存の分析は、データが各イテレーションで置き換えられていることを前提にしている。 Signは同じ$O(log(nT)/stnT + log (nT)sqrtn/sT)$を持つことを示す。 実世界のシミュレートされた問題に関する実験を通じて理論的知見を裏付ける。
  論文  参考訳（メタデータ） (2023-10-24T16:25:13Z)
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model [38.66115499136791]
  局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。 そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。 その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
  論文  参考訳（メタデータ） (2023-10-11T10:34:52Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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