Fugu-MT 論文翻訳(概要): Distributionally Robust Linear Regression With Block Lewis Weights

論文の概要: Distributionally Robust Linear Regression With Block Lewis Weights

arxiv url: http://arxiv.org/abs/2607.00252v1
Date: Tue, 30 Jun 2026 23:01:08 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-02 19:56:07.658305
Title: Distributionally Robust Linear Regression With Block Lewis Weights
Title（参考訳）: ブロックルイス重みを用いた分布ロバスト線形回帰
Abstract要約: 群分布ロバスト(GDR)最小二乗問題に対するアルゴリズムを提案する。我々のアルゴリズムは、適度な精度を実現するために、既知の内部点法よりも改善する。また,最小二乗損失の最小化と分布的ロバスト損失の最小化とを円滑に補間するアルゴリズムも提供する。
参考スコア（独自算出の注目度）: 4.787652251527859
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present an algorithm for the group distributionally robust (GDR) least squares problem. Given $m$ groups, a parameter vector in $\mathbb{R}^d$, and stacked design matrices and responses $\mathbf{A}$ and $\mathbf{b}$, our algorithm obtains a $(1+\varepsilon)$-multiplicative optimal solution using $\widetilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})$ linear-system-solves of matrices of the form $\mathbf{A}^{\top}\mathbf{B}\mathbf{A}$ for block-diagonal $\mathbf{B}$. Our technical methods follow from a recent geometric construction, block Lewis weights, that relates the empirical GDR problem to a carefully chosen least squares problem and an application of accelerated proximal methods. Our algorithm improves over known interior point methods for moderate accuracy regimes and matches the state-of-the-art guarantees for the special case of $\ell_{\infty}$ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.
Abstract（参考訳）: 群分布ロバスト(GDR)最小二乗問題に対するアルゴリズムを提案する。 m$ 群、$\mathbb{R}^d$ のパラメータベクトル、およびスタックされた設計行列と応答 $\mathbf{A}$ と $\mathbf{b}$ が与えられたとき、このアルゴリズムは $\widetilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})$ のような形の行列の線形系解を$\mathbf{A}^{\top}\mathbf{B}\mathbf{A}$ で得られる。我々の技術的手法は、経験的GDR問題と慎重に選択された最小二乗問題と関連する最近の幾何学的構造であるルイス重みをブロックする手法と、加速された近近法の適用から従う。我々のアルゴリズムは、適度な精度のレギュレーションのための既知のインテリアポイント法よりも改善され、$\ell_{\infty}$レグレッションの特別な場合の最先端保証と一致する。また,最小二乗損失の最小化と分布的ロバスト損失の最小化とを円滑に補間するアルゴリズムも提供する。

関連論文リスト

Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文参考訳（メタデータ） (2025-10-12T15:42:44Z)
Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model [5.101318208537081]
線形系を解くための準線形時間アルゴリズムについて研究し、$Sz = b$, ここでは$S$は対角的に支配的な行列である。任意の$u in [n]$に対して、加算誤差のある$z_u$ of $z*_u$を返します。また、一致する下界を証明し、$S_max$ に対する線型依存が最適であることを示す。
論文参考訳（メタデータ） (2025-09-16T14:13:31Z)
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure [16.324043075920564]
線形システムと回帰問題を解くための新しい高精度ランダム化アルゴリズムを提供する。我々のアルゴリズムは、これらの問題に対する高密度な入力の下で、自然の複雑さの限界をほぼマッチングする。特異値の$k$を除くすべての値が有界な一般化平均を持つというより弱い仮定の下でも、これらの実行時間を得る方法を示す。
論文参考訳（メタデータ） (2025-07-15T20:48:30Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文参考訳（メタデータ） (2024-02-06T15:39:09Z)
Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。 mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文参考訳（メタデータ） (2023-10-02T16:44:47Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
論文参考訳（メタデータ） (2023-01-08T21:46:27Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
論文参考訳（メタデータ） (2021-06-06T14:19:43Z)

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

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