論文の概要: Faster Convergence with Multiway Preferences
- arxiv url: http://arxiv.org/abs/2312.11788v1
- Date: Tue, 19 Dec 2023 01:52:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-20 17:23:52.226415
- Title: Faster Convergence with Multiway Preferences
- Title（参考訳）: マルチウェイ優先によるより高速な収束
- Authors: Aadirupa Saha, Vitaly Feldman, Tomer Koren, Yishay Mansour
- Abstract要約: 本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
- 参考スコア（独自算出の注目度）: 99.68922143784306
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of convex optimization with preference feedback, where
the goal is to minimize a convex function given a weaker form of comparison
queries. 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. Here we consider the sign-function-based comparison feedback model and
analyze the convergence rates with batched and multiway (argmin of a set
queried points) comparisons. Our main goal is to understand the improved
convergence rates owing to parallelization in sign-feedback-based optimization
problems. Our work is the first to study the problem of convex optimization
with multiway preferences and analyze the optimal convergence rates. Our first
contribution lies in designing efficient algorithms with a convergence rate of
$\smash{\widetilde O}(\frac{d}{\min\{m,d\} \epsilon})$ for $m$-batched
preference feedback where the learner can query $m$-pairs in parallel. We next
study a $m$-multiway comparison (`battling') feedback, where the learner can
get to see the argmin feedback of $m$-subset of queried points and show a
convergence rate of $\smash{\widetilde O}(\frac{d}{ \min\{\log m,d\}\epsilon
})$. We show further improved convergence rates with an additional assumption
of strong convexity. Finally, we also study the convergence lower bounds for
batched preferences and multiway feedback optimization showing the optimality
of our convergence rates w.r.t. $m$.
- Abstract（参考訳）: 本稿では,比較クエリの弱い形式を与えられた凸関数を最小化することを目的として,選好フィードバックによる凸最適化の問題に対処する。
各クエリは2つのポイントで構成され、デュエルフィードバックは2つのクエリポイントの関数値の(ノイズの多い)単一ビットバイナリ比較を返す。
ここでは、符号関数に基づく比較フィードバックモデルを検討し、バッチおよびマルチウェイ比較による収束率の解析を行う。
我々の主な目標は、符号フィードバックに基づく最適化問題の並列化による収束率の向上を理解することである。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
最初のコントリビューションは効率の良いアルゴリズムを設計することであり、コンバージェンスレートは$\smash{\widetilde O}(\frac{d}{\min\{m,d\} \epsilon})$ for $m$-batched preference feedback ここで学習者は$m$-pairsを並列にクエリできる。
次に、$m$-multiway comparison (`battling') フィードバックについて研究し、そこでは、学習者がクエリされた点の$m$-subsetのargminフィードバックを見て、$\smash{\widetilde o}(\frac{d}{ \min\{\log m,d\}\epsilon })$の収束率を示すことができる。
より強い凸性を仮定して収束率をさらに向上させる。
最後に,収束率w.r.t.$m$の最適性を示すバッチ選択の収束下限とマルチウェイフィードバック最適化についても検討した。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Zero-Order One-Point Estimate with Distributed Stochastic
Gradient-Tracking Technique [23.63073074337495]
本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。
分散勾配追跡法を,勾配推定のない帯域設定に拡張する。
近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
論文 参考訳（メタデータ） (2022-10-11T17:04:45Z) - Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。
本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。
私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
論文 参考訳（メタデータ） (2022-10-06T17:50:42Z) - Dueling Convex Optimization with General Preferences [85.14061196945599]
本研究の目的は, エンフィロンリングフィードバックの弱い形を条件として, 凸関数を最小化することである。
我々の主な貢献は、滑らかな凸対象関数に対する収束$smashwidetilde O(epsilon-4p)$と、その目的が滑らかで凸であるときに効率$smashwidetilde O(epsilon-2p)を持つ効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-27T11:10:41Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - A New One-Point Residual-Feedback Oracle For Black-Box Learning and
Control [28.679167097106813]
本稿では,各反復で関数値を1回クエリし,2つの連続点間の残差を用いて勾配を推定する新しい一点フィードバック方式を提案する。
提案アルゴリズムは,制御不能なデータサンプルを持つ2点スキームと同じ収束率が得られることを示す。
論文 参考訳（メタデータ） (2020-06-18T19:31:13Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。