論文の概要: Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension
- arxiv url: http://arxiv.org/abs/2607.12938v1
- Date: Tue, 14 Jul 2026 16:10:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-15 17:08:30.221223
- Title: Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension
- Title（参考訳）: 1次元の微分自由確率凸最適化のためのシャープ最適アルゴリズム
- Authors: Alexandra Carpentier, Chloé Rouyer, Alexandre Tsybakov, Arya Akhavan,
- Abstract要約: 我々は、ガウス雑音の零次オラクルを用いて凸関数 $f : [0,1] から [0,1] への最小化の問題を研究する。
計算効率のよいO(1/sqrtT)$収束率を求めるアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 80.40589035328607
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic convex optimization is a classical problem with well-understood guarantees under first-order feedback. In contrast, for zero-order optimization with noisy function evaluations, a logarithmic gap has persisted between known upper bounds and the $Ω(1/\sqrt{T})$ lower bound, even in the one-dimensional case. In this work, we study the problem of minimizing a convex function $f : [0,1] \to [0,1]$ using a zero-order oracle with subGaussian noise. We propose a computationally efficient algorithm that achieves the optimal $O(1/\sqrt{T})$ convergence rate, matching the lower bound. The result closes the existing gap in one dimension, providing the first sharp rate guarantee in this setting.
- Abstract（参考訳）: 確率凸最適化(Stochastic convex optimization)は、一階フィードバックの下でよく理解された保証を持つ古典的な問題である。
対照的に、雑音関数の評価を伴うゼロ階最適化では、既知の上界と$Ω(1/\sqrt{T})$下界の間の対数的ギャップが1次元の場合においても持続している。
本研究では、ガウス雑音の零次オラクルを用いて凸関数 $f : [0,1] \to [0,1]$ を最小化する問題について検討する。
計算効率のよいO(1/\sqrt{T})$収束率を求めるアルゴリズムを提案する。
その結果、既存のギャップを1次元に閉じ、この設定で最初のシャープレート保証を提供する。
関連論文リスト
- Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise [27.792016944321627]
本稿では、目的関数がリプシッツ連続である非滑らかな問題を考察する。
本稿では,提案アルゴリズムのオンライン応用の枠組みを洗練することを提案する。
提案手法の有効性を示す数値実験を行った。
論文 参考訳（メタデータ） (2026-05-23T10:55:34Z) - 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) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Breaking the Lower Bound with (Little) Structure: Acceleration in
Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。
簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。
また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文 参考訳（メタデータ） (2023-02-14T00:23:42Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。