論文の概要: Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions

• arxiv url: http://arxiv.org/abs/2611.04171v1
• Date: Tue, 03 Nov 2026 02:01:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-09 22:29:06.666549
• Title: Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions
• Title（参考訳）: Descending Everest, Part II: Oracle Complexity of Minimize aSum of Convex $(L_0,L_1)$-Smooth Function
• Abstract要約: 期待値において精度$varepsilon$に達する複雑さを導出する。 上界は提案手法YETIにより達成される。 下界は、任意の一階法で困難であるインスタンスの族を明示的に構成することで得られる。
• 参考スコア（独自算出の注目度）: 50.90629146297993
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the minimization of the average of $n$ convex $(L_0,L_1)$-smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm. We assume known upper bounds $R$ on the distance from the starting point to a minimizer and $δ$ on the difference between the minimum of the average and the average of the infima of the components. We derive upper and lower bounds on the oracle complexity of reaching accuracy $\varepsilon$ in function value in expectation. Up to logarithmic factors, both bounds are of order $n(1+(L_1R)^{2/3}) +\sqrt{\frac{n(L_0+L_1^2δ)R^2}{\varepsilon}+n(L_1R)^2}$. The upper bound is attained by the proposed method YETI. The method combines ideas of accelerated proximal methods and variance reduction methods with a heuristic for choosing additional points. The number of oracle calls made by the heuristic is bounded, which preserves the upper bound on the total number of queries needed to reach the target accuracy. In the experiments, YETI is compared with first-order methods on synthetic problems and Poisson regression problems. We also examine the stopping criterion and the effect of the heuristic separately. The lower bound is obtained by an explicit construction of families of instances that are hard for any first-order method.
• Abstract（参考訳）: 平均の $n$ convex $(L_0,L_1)$-smooth 関数の最小化について検討する: 各関数のヘッセンノルムはその勾配ノルムのアフィン関数で有界である。 既知の上限は、始点から最小点までの距離で$R$、成分の最小値と不等式の平均との差で$δ$と仮定する。 期待値の関数値において、精度が$\varepsilon$に達するというオラクル複雑性の上限と下限を導出する。 対数因子に関して、両方の境界は次数$n(1+(L_1R)^{2/3}) +\sqrt {\frac{n(L_0+L_1^2δ)R^2}{\varepsilon}+n(L_1R)^2}$である。 上界は提案手法YETIにより達成される。 この方法は、加速された近位法と分散還元法のアイデアと、追加点を選択するヒューリスティックを組み合わせたものである。 ヒューリスティックによってなされるオラクル呼び出しの数は有界であり、ターゲット精度に達するのに必要なクエリの総数に対する上限を保っている。 実験では、YETIを合成問題とポアソン回帰問題に関する一階法と比較した。 また,停止基準とヒューリスティックの効果を別々に検討した。 下界は、任意の一階法で困難であるインスタンスの族を明示的に構成することで得られる。

関連論文リスト

• Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets [23.573040585638765]
  強凸集合上のランダム化一階線形最小化オラクル法に対して$(Lnamediam(S)2/T2)$分布下界を証明した。
  論文  参考訳（メタデータ） (2026-10-09T13:40:50Z)
• Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization [2.834413535942792]
  非畳み込みミニマックス最適化における一階アルゴリズムの下位境界を確立する。 私たちの貢献は、分散還元を許容するゼロ境界クラスに対する下界である。 これらの結果は、凹凸と凹凸構造をまたいだ複雑さの障壁を同定する。
  論文  参考訳（メタデータ） (2026-10-01T13:24:15Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Estimating the minimizer and the minimum value of a regression function under passive design [72.85024381807466]
  最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。 2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
  論文  参考訳（メタデータ） (2022-11-29T18:38:40Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization [7.197233473373693]
  2つの凸関数の和を最小化する問題を考える。 1つはリプシッツ連続勾配を持ち、オークルを介してアクセスでき、もう1つは「単純」である。 我々は、$tildeO (1/ sqrtepsilon)$ iterationsで$epsilon$prialdual gap(期待して)を達成することができることを示す。
  論文  参考訳（メタデータ） (2022-05-25T13:01:09Z)
• Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
  この楽観的な手法は凸凹点問題の解法として人気が高まっている。 我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
  論文  参考訳（メタデータ） (2022-02-19T20:31:05Z)

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

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