論文の概要: A simple and improved algorithm for noisy, convex, zeroth-order optimisation
- arxiv url: http://arxiv.org/abs/2406.18672v1
- Date: Wed, 26 Jun 2024 18:19:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-28 18:07:31.644617
- Title: A simple and improved algorithm for noisy, convex, zeroth-order optimisation
- Title（参考訳）: 雑音,凸,ゼロ次最適化のための単純で改良されたアルゴリズム
- Authors: Alexandra Carpentier,
- Abstract要約: 我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
- 参考スコア（独自算出の注目度）: 59.51990161522328
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the problem of noisy, convex, zeroth order optimisation of a function $f$ over a bounded convex set $\bar{\mathcal X}\subset \mathbb{R}^d$. Given a budget $n$ of noisy queries to the function $f$ that can be allocated sequentially and adaptively, our aim is to construct an algorithm that returns a point $\hat x\in \bar{\mathcal X}$ such that $f(\hat x)$ is as small as possible. We provide a conceptually simple method inspired by the textbook center of gravity method, but adapted to the noisy and zeroth order setting. We prove that this method is such that the $f(\hat x) - \min_{x\in \bar{\mathcal X}} f(x)$ is of smaller order than $d^2/\sqrt{n}$ up to poly-logarithmic terms. We slightly improve upon existing literature, where to the best of our knowledge the best known rate is in [Lattimore, 2024] is of order $d^{2.5}/\sqrt{n}$, albeit for a more challenging problem. Our main contribution is however conceptual, as we believe that our algorithm and its analysis bring novel ideas and are significantly simpler than existing approaches.
- Abstract（参考訳）: 本稿では、有界凸集合$\bar{\mathcal X}\subset \mathbb{R}^d$ 上の関数 $f$ の雑音、凸、ゼロ次最適化の問題を考察する。
f(\hat x)$ が可能な限り小さいような点 $\hat x\in \bar{\mathcal X}$ を返すアルゴリズムを構築するのが目的です。
本稿では,重み付け方式の教科書中心に着想を得た概念的簡便な手法を提案する。
この方法は、$f(\hat x) - \min_{x\in \bar{\mathcal X}} f(x)$ が、多対数項まで$d^2/\sqrt{n}$ より小さい順序であることを証明する。
我々は既存の文献をわずかに改善し、最もよく知られたことは[Lattimore, 2024]の順に$d^{2.5}/\sqrt{n}$である。
しかし、我々の主な貢献は概念的であり、我々のアルゴリズムとその分析は、新しいアイデアをもたらし、既存のアプローチよりもはるかに単純であると考えている。
関連論文リスト
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳（メタデータ） (2021-03-29T23:03:24Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。