論文の概要: Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters

• arxiv url: http://arxiv.org/abs/2610.33835v1
• Date: Sat, 24 Oct 2026 18:14:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:13.456594
• Title: Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters
• Title（参考訳）: カプセル参加型ヘシアン相似最適化:下界と仮想マスター
• Abstract要約: クライアントチェーンは、適応コホートとランダム停止を備えたゼロ参照ローカルアルゴリズムの低いバウンダリを与える。 Catalystでは、$tilde O(m/s+(sqrtm/s+m3/4/s)sqrtbar/)$の相対的なギャップに到達します。 実験では、9つのディップファミリーの不完全なコホート細胞ではSVRPが調整され、30の細胞のうち2つよりもラウンドが少ないことがわかりました。
• 参考スコア（独自算出の注目度）: 3.744103474408833
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: What is the round complexity of Hessian-similar optimization when each round can contact at most $s$ of $m$ clients? Prior rates permit a free master or full participation and do not characterize strict caps. We count every one-vector query and reply. A hidden-client chain gives a lower bound for zero-respecting local algorithms with adaptive cohorts and random stopping: on strongly convex quadratics, the required rounds are $Ω((m/s)\sqrt{\min\{δ_a,\barδ/\sqrt m\}/μ}\,\log(1/ε))$ for $s\leq(m-2)/2$ in the high-accuracy, high-dissimilarity regime. Here $μ$ is strong convexity, while $δ_a$ and $\barδ$ bound anchor and average Hessian variation. To remove dependence on a poor anchor, virtual-master SVRS uses independent estimator and proximal cohorts and averages the proximal replies. With Catalyst, it reaches relative gap $ε$ in $\tilde O(m/s+(\sqrt{m/s}+m^{3/4}/s)\sqrt{\barδ/μ})$ expected rounds on quadratics with strongly convex clients, independent of $δ_a$. Combining this method with charged analyses of existing algorithms matches the lower bound's polynomial dependence for $s\leq\sqrt m$ and $s=Ω(m)$; the worst gap is $O(m^{1/8})$. A held-out 12-seed synthetic study finds fewer rounds than tuned SVRP in nine of ten dip-family incomplete-cohort cells, versus two of 30 other cells. The lower bounds concern zero-respecting algorithms and do not cover unrestricted messages.
• Abstract（参考訳）: 各ラウンドが少なくとも$m$のクライアントと接触できる場合、Hessian-similar最適化のラウンド複雑さはどのようなものでしょう? プリエントレートは、フリーマスターまたはフル参加を許可し、厳格な上限を特徴づけない。 すべての1-vectorクエリとレスポンスをカウントします。 強い凸二次数では、要求されるラウンドは$Ω((m/s)\sqrt{\min\{δ_a,\barδ/\sqrt m\}/μ}\,\log(1/ε))$s\leq(m-2)/2$である。 ここで$μ$は強い凸性を持ち、$δ_a$ と $\barδ$ は有界なアンカーと平均ヘッセン変動である。 仮想マスターSVRSは、アンカーへの依存を取り除くために、独立推定器と近位コホートを使用し、近位応答を平均化する。 Catalyst は相対ギャップ $ε$ in $\tilde O(m/s+(\sqrt{m/s}+m^{3/4}/s)\sqrt{\barδ/μ})$ $δ_a$ とは無関係に、強い凸クライアントを持つ二次体上の予想ラウンドに到達する。 この方法と既存のアルゴリズムのチャージ解析を組み合わせると、下界の多項式依存は$s\leq\sqrt m$と$s=Ω(m)$と一致し、最悪のギャップは$O(m^{1/8})$である。 SVRPは10のディップファミリーの不完全コホート細胞のうち9つで、他の30の細胞では2つよりもラウンドが少ない。 下位境界はゼロ参照アルゴリズムに関係し、制限のないメッセージをカバーしない。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests [19.221722169368494]
  サンプル複雑性$ot(k2/2+ksqrt d/(varepsilon)$ for $(varepsilon,)$-differential privacy and error at most $2$。 境界は、既存の$ot(k2/2+k3/2sqrt d/(varepsilon))$ citepkumar2026上界のプライバシー依存項を$sqrt k$で改善し、一致させる。
  論文  参考訳（メタデータ） (2026-09-19T05:31:47Z)
• Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness [8.428362872515416]
  我々は、各$_maxgeq 3$に対して、個々の滑らかさの下で下界に一致することを証明した。 また、各$_maxgeq 3$に対して、個々の滑らかさの下で下界が一致することを証明する。
  論文  参考訳（メタデータ） (2026-08-30T02:47:24Z)
• On efficient robust regression with subquadratic samples [2.017649213266693]
  ここでは,$widetildeO(d/4)$サンプルを用いたニア線形時間アルゴリズムが,$lesssim 1$条件下で予測誤差$O(sqrt)$を達成することを示す。 また、$lesssim 1$のような仮定がなければ、効率的なアルゴリズムには$tildeleft(mind22, 2d2right)$サンプルが必要であるという詳細な証拠を与える低次下界も証明する。
  論文  参考訳（メタデータ） (2026-05-18T08:34:07Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Robust learning of halfspaces under log-concave marginals [6.852292115526837]
  線形しきい値関数を学習し、境界体積$O(r+varepsilon)$の分類子を半径摂動$r$で返すアルゴリズムを与える。 dtildeO(1/varepsilon2)$の時間とサンプルの複雑さはブール回帰の複雑さと一致する。
  論文  参考訳（メタデータ） (2025-05-19T20:12:16Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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