論文の概要: Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

• arxiv url: http://arxiv.org/abs/2610.13590v1
• Date: Fri, 09 Oct 2026 13:40:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.60335
• Title: Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
• Title（参考訳）: 強凸集合上のランダム化線形Oracle最適化のための下界
• Abstract要約: 強凸集合上のランダム化一階線形最小化オラクル法に対して$(Lnamediam(S)2/T2)$分布下界を証明した。
• 参考スコア（独自算出の注目度）: 23.573040585638765
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order $1/T^2$ after $T$ linear minimization oracle (LMO) calls, matching the upper bound [arXiv:1406.1305] in its dependence on $T$ and thereby resolving a long-standing open question. Upon close inspection, however, both lower bounds are somewhat brittle. The first [arXiv:2602.04378] applies only to the standard Frank--Wolfe algorithm, and, as we show, its prescribed slow exact-line-search trajectories can amplify sufficiently small initialization errors exponentially, corresponding to roughly one additional bit of initialization accuracy per iteration. The second [arXiv:2602.22608] obtains lower bounds for any deterministic LMO-based first-order method via a resisting oracle that adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds; in particular, neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an $Ω(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound for randomized first-order linear minimization oracle methods over strongly convex sets. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We further show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound.
• Abstract（参考訳）: 最近の結果 (arXiv:2602.04378, arXiv:2602.22608] は、$T$の線形最小化オラクル (LMO) コール後の1/T^2$の最悪の対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物(対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物 しかし、綿密な検査では、両方の下限はやや不安定である。 最初の[arXiv:2602.04378] は、標準のフランク・ウルフアルゴリズムにのみ適用され、我々が示すように、その所定の遅い直線探索軌道は、イテレーション毎の約1ビットの初期化精度に応じて、十分に小さな初期化誤差を指数関数的に増幅することができる。 第2の[arXiv:2602.22608]は、アルゴリズムのクエリに逆順に適応する抵抗オラクルを介して、決定論的LMOベースの一階法に対する下界を求める。 どちらの場合も、ランダム化はこれらの下界を回避できると考えられており、特に、制限なしのランダム化一階 LMO 法に対する下界を確立しない。 強凸集合上のランダム化された一階線形最小化オラクル法に対して、$Ω(L\operatorname{diam}(S)^2/T^2)$分布下界を証明して、このギャップを埋める。 提案手法は[arXiv:2602.22608] の族を再利用するが, 適応クエリ後の隠れ置換の条件分布を特徴付けるとともに, 組合せ統計量によるオプティマイザ分散の予測減少を制限している。 さらに、同じ誤差閾値が少なくとも3/4$の確率で保持され、停止時間テールバウンドが得られることを示す。

関連論文リスト

• A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization [66.48718943929202]
  非強凸二値問題の場合、既存の一階法はネストループに依存するのが一般的である。 2つの相補成分を組み合わせたSingle-loop Constant-1次ペナルティ法(ICOS)を提案する。
  論文  参考訳（メタデータ） (2026-10-05T19:26:20Z)
• 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)
• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。 予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
  論文  参考訳（メタデータ） (2025-11-17T23:58:11Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Norm [12.579063422860072]
  我々は,この問題に対する2座標更新と,1ノルムにおける等式制約付き急降下との接続を利用する。 次に、サポートベクトルマシン双対問題において生じるような、和制約と有界制約の両方で最小化を検討する。
  論文  参考訳（メタデータ） (2023-07-03T17:27:18Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。 非テンション依存データ設定の下で, 各種手法の収束点を求める。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)

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

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