論文の概要: Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization

• arxiv url: http://arxiv.org/abs/2609.21880v1
• Date: Fri, 18 Sep 2026 15:07:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-21 18:40:17.160129
• Title: Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization
• Title（参考訳）: Smooth $\ell_p$ / $\ell_q$ Nondual Convex 1次Oracle最適化の準最適加速
• Abstract要約: 凸対象を$(L,-1)$-Hlder-continuous in $ell_q$ over $R B_pd$, $1le 2$で最適化する。
• 参考スコア（独自算出の注目度）: 19.52344367809103
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the optimization of convex objectives with $(L,κ-1)$-Hölder-continuous gradients in $\ell_q$ over $R B_p^d$, $1<κ\le 2$. (MG26) provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every $p<q$ and generally reduces Lipschitz convex optimization to bounds on the movement of selectors. We couple that movement with Hölder descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime $T\le d$ and for $p<\min\{q,2\}$, has error $$ \widetilde O_{κ,p,q}\!\left( \frac{LR^κ}{T^{κ(1+1/p-(1/q-1/2)_+)-1}} \right), $$ after $T$ queries to a first-order oracle, solving the COLT 2015 open problem of (Guz15), up to logarithmic factors. At $(p,q)=(1,2)$, the rate is $\widetilde{O}(LR^κ/T^{2κ-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.
• Abstract（参考訳）: 凸対象の最適化を$(L,κ-1)$-Hölder-continuous gradients in $\ell_q$ over $R B_p^d$, $1<κ\le 2$で検討する。 (MG26) は、$p<q$毎の高次元凸ネスト集合を追尾する問題に対して、セレクタにバウンドの移動を与えるとともに、一般に、セレクタの移動上のバウンドにリプシッツ凸最適化を還元する。 我々は、高次元のレジーム$T\le d$ と $p<\min\{q,2\}$ が誤り$$$ \widetilde O_{κ,p,q}\! \left( \frac{LR^κ}{T^{κ(1+1/p-(1/q-1/2)_+)-1}} \right), $T$の1次オラクルへのクエリの後に$$で、COLT 2015の解問題(Guz15)を対数要素まで解決する。 $(p,q)=(1,2)$では、滑らかな場合は$\widetilde{O}(LR^κ/T^{2κ-1})$、$\widetilde{O}(LR^2/T^{3})$立方分解を含む$\widetilde{O}(LR^κ/T^{2κ-1})$である。

関連論文リスト

• Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates [13.0201223534445]
  本稿では,G$-Lipschitz 凸関数の最適化の1次オラクル複雑性を実現するための効率的なアルゴリズムについて検討する。 提案したセレクタのモンテカルロ平均は、高い確率で最適に近い速度を達成する。
  論文  参考訳（メタデータ） (2026-09-17T17:02:55Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• 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)
• Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity [6.309677398331863]
  我々は最適性ギャップの観点から、$Omegaleft( left( fracHsigmaright)frac23(p+nu)$の最悪のオラクル複合体を確立する。 我々の結果は、この一般的な設定における対応する上界と一致する。
  論文  参考訳（メタデータ） (2024-09-16T23:17:33Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
  オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。 非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
  論文  参考訳（メタデータ） (2021-05-04T21:49:15Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• High-Order Oracle Complexity of Smooth and Strongly Convex Optimization [31.714928102950584]
  非常に滑らかな (Lipschitz $k$-thorder derivative) 関数と強い凸関数を$k$-thorder Oracleへの呼び出しによって最適化する複雑性を考える。 我々は、関数を正確に$epsilon$まで最適化するために、固定された$k$で最悪の場合のオラクルの複雑さが$leftの順序にあることを証明している。
  論文  参考訳（メタデータ） (2020-10-13T19:18:15Z)

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

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