論文の概要: Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond

• arxiv url: http://arxiv.org/abs/2504.07133v1
• Date: Sun, 06 Apr 2025 20:59:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-11 12:22:10.594515
• Title: Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond
• Title（参考訳）: SGDは優れた漁師を選別できるか? : 自己選抜行動とそれを超える地域収束
• Authors: Alkis Kalavasis, Anay Mehrotra, Felix Zhou,
• Abstract要約: 我々は,$doperator次元の自己選択バイアスを持つ線形回帰器を$k$で推定する問題を再検討する。 我々の主な結果は、この問題に対する$namepoly(d,k,1/varepsilon) + kO(k)$ time algorithmである。
• 参考スコア（独自算出の注目度）: 11.884593048693507
• License:
• Abstract: We revisit the problem of estimating $k$ linear regressors with self-selection bias in $d$ dimensions with the maximum selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC'23]. Our main result is a $\operatorname{poly}(d,k,1/\varepsilon) + {k}^{O(k)}$ time algorithm for this problem, which yields an improvement in the running time of the algorithms of [CDIZ23] and [GM24, arXiv]. We achieve this by providing the first local convergence algorithm for self-selection, thus resolving the main open question of [CDIZ23]. To obtain this algorithm, we reduce self-selection to a seemingly unrelated statistical problem called coarsening. Coarsening occurs when one does not observe the exact value of the sample but only some set (a subset of the sample space) that contains the exact value. Inference from coarse samples arises in various real-world applications due to rounding by humans and algorithms, limited precision of instruments, and lag in multi-agent systems. Our reduction to coarsening is intuitive and relies on the geometry of the self-selection problem, which enables us to bypass the limitations of previous analytic approaches. To demonstrate its applicability, we provide a local convergence algorithm for linear regression under another self-selection criterion, which is related to second-price auction data. Further, we give the first polynomial time local convergence algorithm for coarse Gaussian mean estimation given samples generated from a convex partition. Previously, only a sample-efficient algorithm was known due to Fotakis, Kalavasis, Kontonis, and Tzamos [FKKT21, COLT'21].
• Abstract（参考訳）: 我々は,Cherapanamjeri, Daskalakis, Ilyas, Zampetakis [CDIZ23, STOC'23] が導入したように,$d$次元の自己選択バイアスを持つ$k$線形回帰器を最大選択基準で推定する問題を再検討する。 我々の主な結果は、この問題に対する$\operatorname{poly}(d,k,1/\varepsilon) + {k}^{O(k)}$の時間アルゴリズムであり、[CDIZ23] と [GM24, arXiv] のアルゴリズムの実行時間を改善する。 自己選択のための局所収束アルゴリズムを初めて提供し, [CDIZ23] の解答を行う。 このアルゴリズムを得るために、自己選択を、粗大化(coarsening)と呼ばれる、一見無関係な統計問題に還元する。 粗大化は、標本の正確な値を観測しないが、正確な値を含む集合(サンプル空間のサブセット)のみを観察する場合に発生する。 粗いサンプルからの推測は、人間やアルゴリズムによる丸め、楽器の精度の制限、マルチエージェントシステムにおけるラグによる様々な実世界の応用に現れる。 粗大化への還元は直感的であり、従来の分析手法の限界を回避できる自己選択問題の幾何学に依存している。 その適用性を示すために、第2価格オークションデータに関連する他の自己選択基準の下で線形回帰のための局所収束アルゴリズムを提供する。 さらに、凸分割から生成されたサンプルに対して粗いガウス平均推定のための最初の多項式時間局所収束アルゴリズムを与える。 以前はFotakis, Kalavasis, Kontonis, Tzamos [FKKT21, COLT'21] というサンプル効率のよいアルゴリズムしか知られていなかった。

関連論文リスト

• High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm [12.405427902037971]
  本稿では,$mathbbRd$の適切な凸部分集合である対象分布から近似サンプリングを行う1次サンプリング法を提案する。 提案手法は,事前条件付きLangevinアルゴリズムの単一ステップで生成したマルコフ連鎖にメトロポリス・ハスティングスフィルタを適用した結果である。
  論文  参考訳（メタデータ） (2024-12-24T23:21:23Z)
• Sharper Bounds for Chebyshev Moment Matching with Applications to Differential Privacy and Beyond [26.339024618084476]
  我々は、ワッサーシュタイン距離の正確な回復が、以前よりも多くのノイズで可能であることを証明した。 主な応用として、微分プライベートな合成データ分布を構築するための単純な「線形クエリ」アルゴリズムが得られた。 数値線形代数における新たなモーメントベースリカバリの第二の応用について説明する。
  論文  参考訳（メタデータ） (2024-08-22T13:26:41Z)
• Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization [5.900674344455754]
  ランクランダム行列の特性をdで推定する手法を示す。 鋭い収束は、単一のステップで正確な回復を保証する。 我々の分析は、この問題の他のいくつかの特性も明らかにしている。
  論文  参考訳（メタデータ） (2022-07-20T05:31:05Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates [16.54912614895861]
  我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。 我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。 その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
  論文  参考訳（メタデータ） (2020-03-03T03:59:26Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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