Fugu-MT 論文翻訳(概要): Near-Optimal Convex Optimization with Lazy Second-Order Oracles

論文の概要: Near-Optimal Convex Optimization with Lazy Second-Order Oracles

arxiv url: http://arxiv.org/abs/2610.03222v1
Date: Fri, 02 Oct 2026 12:38:28 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-06 00:14:30.370708
Title: Near-Optimal Convex Optimization with Lazy Second-Order Oracles
Title（参考訳）: 遅延2次Oracleによるニア最適凸最適化
Abstract要約: 本稿では,遅延二階オラクルを用いた凸最適化の複雑さについて検討する。合計反復数に対して、$(m+ m1/7 -2/7) の低い境界を示し、$-solution を求める。次に,新しい上限を$tildemathcalO(m+ m1/7 -2/7)$とする手法を提案する。
参考スコア（独自算出の注目度）: 33.30176677509747
License: http://creativecommons.org/publicdomain/zero/1.0/
Abstract: This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per $m$ iterations. Under this setting, we show a lower bound of $Ω(m+ m^{1/7} ε^{-2/7})$ on the number of total iterations to find an $ε$-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of $\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7})$ and is tight up to logarithmic factors.
Abstract（参考訳）: 本稿では,遅延2次オラクル (Doikov, Chayti, Jaggi, ICML 2023) を用いた凸最適化の複雑さについて検討する。この設定の下では、新しいブロックゼロ鎖構造を用いて、合計反復数に対して$Ω(m+ m^{1/7} ε^{-2/7})の低い境界を示す。次に,新しい上限値である$\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7})$(Chen, Liu, Luo, Zhang, COLT 2026)と$\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7})$(m+ m^{13/21} ε^{-2/7})$(Chen, Liu, Luo, Zhang, COLT 2026)を大幅に改善し,対数的因子に強く依存する新しい手法を提案する。

関連論文リスト

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文参考訳（メタデータ） (2026-09-09T10:13:43Z)
Halpern Iteration Achieves $\tilde{\mathcal{O}}(ε^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities [32.010107520858995]
滑らかな単調変分不等式(MVI)の2次および高次解法について検討する。 MVIを解くために,より高速な$tildemathcalO(T-2)$を実現するHalpern-NPE法を提案する。
論文参考訳（メタデータ） (2026-08-09T04:13:20Z)
Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文参考訳（メタデータ） (2026-07-08T17:49:40Z)
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)
Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity [27.760400553380823]
凸最適化のための最適二階法を一般化することにより,$tildemathcalO(epsilon-4/7)$の改善された上限を示す。さらに,遅延ヘシアンアルゴリズムに類似した手法を適用し,提案アルゴリズムが二階触媒の枠組みであることを示す。
論文参考訳（メタデータ） (2025-06-10T02:20:48Z)
Second-Order Min-Max Optimization with Lazy Hessians [17.17389531402505]
本稿では,凸凹型最小値最適化のための2次法について検討する。計算コストは反復的にヘッセンによって削減できることを示す。
論文参考訳（メタデータ） (2024-10-12T15:30:17Z)
Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
論文参考訳（メタデータ） (2023-02-07T22:58:12Z)
The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-19T16:04:40Z)
Perseus: A Simple and Optimal High-Order Method for Variational Inequalities [81.32967242727152]
VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
論文参考訳（メタデータ） (2022-05-06T13:29:14Z)
Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
論文参考訳（メタデータ） (2021-01-15T18:52:02Z)

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