論文の概要: A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions

• arxiv url: http://arxiv.org/abs/2510.27177v1
• Date: Fri, 31 Oct 2025 05:02:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-03 17:52:15.984314
• Title: A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions
• Title（参考訳）: 重み条件下でのRegret境界の改善によるオンラインスパース線形回帰の多項式時間アルゴリズム
• Authors: Junfan Li, Shizhong Liao, Zenglin Xu, Liqiang Nie,
• Abstract要約: オンラインスパース線形回帰(OSLR)では,予測のために1インスタンスあたり$d$あたり$k$しかアクセスできない。 提案手法では, 過去の後悔点を大幅に改善する拡張時間アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 75.69959433669244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only $k$ out of $d$ attributes per instance for prediction, which was proved to be NP-hard. Previous work gave polynomial-time algorithms assuming the data matrix satisfies the linear independence of features, the compatibility condition, or the restricted isometry property. We introduce a new polynomial-time algorithm, which significantly improves previous regret bounds (Ito et al., 2017) under the compatibility condition that is weaker than the other two assumptions. The improvements benefit from a tighter convergence rate of the $\ell_1$-norm error of our estimators. Our algorithm leverages the well-studied Dantzig Selector, but importantly with several novel techniques, including an algorithm-dependent sampling scheme for estimating the covariance matrix, an adaptive parameter tuning scheme, and a batching online Newton step with careful initializations. We also give novel and non-trivial analyses, including an induction method for analyzing the $\ell_1$-norm error, careful analyses on the covariance of non-independent random variables, and a decomposition on the regret. We further extend our algorithm to OSLR with additional observations where the algorithms can observe additional $k_0$ attributes after each prediction, and improve previous regret bounds (Kale et al., 2017; Ito et al., 2017).
• Abstract（参考訳）: 本稿では,Sparse linear regression (OSLR) の問題について検討し,アルゴリズムは1インスタンスあたり$d$属性のうち$k$しかアクセスできず,NPハードであることが判明した。 以前の研究は、データ行列が特徴の線型独立性、互換性条件、あるいは制限された等尺性を満たすことを仮定する多項式時間アルゴリズムを与えた。 我々は,他の2つの仮定よりも弱い互換性条件下で,過去の後悔境界(Ito et al , 2017)を大幅に改善する新しい多項式時間アルゴリズムを導入する。 この改善は、推定器の$\ell_1$-norm誤差のより厳密な収束率の恩恵を受ける。 提案アルゴリズムは、よく研究されているDantzig Selectorを活用するが、特に、共分散行列を推定するアルゴリズム依存サンプリングスキーム、適応パラメータチューニングスキーム、慎重に初期化したバッチオンラインニュートンステップなど、いくつかの新しい手法を用いている。 また,$\ell_1$-norm誤差を解析するための帰納法,非独立確率変数の共分散の慎重な解析,後悔の分解など,新規かつ非自明な分析も行う。 我々はさらにOSLRにアルゴリズムを拡張し、予測後に追加の$k_0$属性を観測し、過去の後悔境界を改善する(Kale et al , 2017; Ito et al , 2017)。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Convergence analysis of online algorithms for vector-valued kernel regression [0.0]
  回帰関数 $f_mu:, Omega to Y$ from noisy $mu$-distributed vector-valued data。 標準正規化オンライン近似アルゴリズムにより得られた近似値$f(m) in H$のRKHSノルムの2乗誤差を推定する。
  論文  参考訳（メタデータ） (2023-09-14T15:10:47Z)
• Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
  分離可能な近似フレームワークを用いて,機械学習モデルのクラスに対するオンライン学習アルゴリズムを提案する。 提案アルゴリズムは,他の一般的な学習アルゴリズムと比較して,より堅牢でテスト性能が高いことを示す。
  論文  参考訳（メタデータ） (2023-05-12T13:53:03Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge [24.880035784304834]
  オンラインリッジ回帰とフォワードアルゴリズムに対して高い確率的後悔境界を導出する。 これにより、オンライン回帰アルゴリズムをより正確に比較し、有界な観測と予測の仮定を排除できる。
  論文  参考訳（メタデータ） (2021-11-02T13:57:53Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• A polynomial-time algorithm for learning nonparametric causal graphs [18.739085486953698]
  この分析はモデルフリーであり、線形性、付加性、独立ノイズ、忠実さを前提としない。 我々は、同値な分散を持つ線形模型の以前の研究と密接に関連する残差に条件を課す。
  論文  参考訳（メタデータ） (2020-06-22T02:21:53Z)

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

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