論文の概要: Dueling Convex Optimization with General Preferences
- arxiv url: http://arxiv.org/abs/2210.02562v1
- Date: Tue, 27 Sep 2022 11:10:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-09 17:11:29.704204
- Title: Dueling Convex Optimization with General Preferences
- Title（参考訳）: 一般化した凸最適化
- Authors: Aadirupa Saha, Tomer Koren, Yishay Mansour
- Abstract要約: 本研究の目的は, エンフィロンリングフィードバックの弱い形を条件として, 凸関数を最小化することである。
我々の主な貢献は、滑らかな凸対象関数に対する収束$smashwidetilde O(epsilon-4p)$と、その目的が滑らかで凸であるときに効率$smashwidetilde O(epsilon-2p)を持つ効率的なアルゴリズムである。
- 参考スコア（独自算出の注目度）: 85.14061196945599
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We address the problem of \emph{convex optimization with dueling feedback},
where the goal is to minimize a convex function given a weaker form of
\emph{dueling} feedback. Each query consists of two points and the dueling
feedback returns a (noisy) single-bit binary comparison of the function values
of the two queried points. The translation of the function values to the single
comparison bit is through a \emph{transfer function}. This problem has been
addressed previously for some restricted classes of transfer functions, but
here we consider a very general transfer function class which includes all
functions that can be approximated by a finite polynomial with a minimal degree
$p$. Our main contribution is an efficient algorithm with convergence rate of
$\smash{\widetilde O}(\epsilon^{-4p})$ for a smooth convex objective function,
and an optimal rate of $\smash{\widetilde O}(\epsilon^{-2p})$ when the
objective is smooth and strongly convex.
- Abstract（参考訳）: ここでは, より弱いフィードバック形式を与えられた凸関数の最小化を目標とする, デュエルリングフィードバックによるemph{convex最適化の問題に対処する。
各クエリは2つのポイントで構成され、デュエルフィードバックは2つのクエリポイントの関数値の(ノイズの多い)単一ビットバイナリ比較を返す。
関数値の単一の比較ビットへの変換は \emph{transfer function} を通して行われる。
この問題は以前いくつかの制限された転送関数のクラスに対して解決されてきたが、ここでは極小次数$p$の有限多項式で近似できるすべての関数を含む非常に一般的な転送関数クラスを考える。
我々の主な貢献は、滑らかな凸目的関数に対して$\smash{\widetilde O}(\epsilon^{-4p})$の収束率と、その目的が滑らかで強凸であるときに$$\smash{\widetilde O}(\epsilon^{-2p})$の最適率を持つ効率的なアルゴリズムである。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳（メタデータ） (2023-12-19T01:52:13Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - 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) - Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。
また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
論文 参考訳（メタデータ） (2022-02-15T16:02:32Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Parameter-free Stochastic Optimization of Variationally Coherent
Functions [19.468067110814808]
我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。
この2つを同時に実現したのは初めてである。
論文 参考訳（メタデータ） (2021-01-30T15:05:34Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。