論文の概要: Online Convex Optimization with Sublinear Noisy Probes
- arxiv url: http://arxiv.org/abs/2606.14640v1
- Date: Fri, 12 Jun 2026 17:05:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-15 16:00:43.005389
- Title: Online Convex Optimization with Sublinear Noisy Probes
- Title（参考訳）: 非線形ノイズプローブを用いたオンライン凸最適化
- Authors: Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo,
- Abstract要約: オンライン凸最適化(OCO)を凸集合として$Ksubseteq mathbb Rd$で検討する。
我々は最近の2つの作業の行を一般化する統一された探索モデルを導入する: 専門家設定におけるサブ線形ベストエキスパートクエリと、OCOの各ラウンドで利用できるペアワイズフィードバックである。
本研究の主目的は, サブリニアでノイズの多いプローブ予算であっても, OCO体制の完全なフィードバックにおける最悪の後悔を確実に改善できることである。
- 参考スコア（独自算出の注目度）: 6.998574163422056
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study Online Convex Optimization (OCO) over a convex set $K\subseteq \mathbb R^d$, where in each round $t$ the learner selects $x_t\in K$ and then observes a convex loss $f_t:K\to[0,1]$, with the goal of minimizing regret to the best fixed decision in hindsight. We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise (comparison-based) feedback available every round in OCO. In our framework, the learner has a budget of $k\le T$ pairwise probes; on a probed round it may query two points and learn which one has smaller loss. Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime. With $k$ $δ$-noisy pairwise probes, we obtain: $ \text{Reg}_T \le O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2δ|}\right\}\right) $, which is tight (up to logarithmic factors in $T$) across $T$, $k$ and $δ$. Specifically regarding the noise parameter $δ\in [0,1]$, the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., $δ$ is close to $\frac{1}{2}$. When applying the same techniques to a finite $K$ for the prediction with $d$ experts setting, the resulting rates are instead completely tight in all parameters, including $d$. Our analysis gives a streamlined treatment of pairwise probing in OCO by quantifying the benefit of probing via a variance reduction effect, combined with a second-order (variance-based) analysis of Continuous Exponential Weights.
- Abstract（参考訳）: オンライン凸最適化 (Online Convex Optimization, OCO) を凸集合$K\subseteq \mathbb R^d$で研究し、各ラウンド$t$で学習者が$x_t\in K$を選択して凸損失$f_t:K\to[0,1]$を観測する。
我々は最近の2つの作業ラインを一般化する統一された探索モデルを導入し、エキスパート設定におけるサブ線形ベストエキスパートクエリと、OCOの各ラウンドで利用可能なペアワイズ(ペアベース)フィードバックを紹介した。
私たちのフレームワークでは、学習者には$k\le T$ペアワイズプローブの予算があります。
本研究の主目的は, サブリニアでノイズの多いプローブ予算であっても, OCO体制の完全なフィードバックにおける最悪の後悔を確実に改善できることである。
$k$ $δ$-noisy pairwise probes, $ \text{Reg}_T \le O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2δ|}\right\right\right) $T$, $k$ と $δ$ の対数係数に対して、厳密である。
具体的には、ノイズパラメータ $δ\in [0,1]$ について、オラクル応答がコインフリップに近づくと、後悔の保証は円滑に低下する。
同じテクニックを$d$のエキスパート設定で予測に有限の$K$に適用する場合、結果のレートは$d$を含むすべてのパラメータで完全に厳格になる。
本分析では, 連続指数重みの2次(分散に基づく)解析と相まって, 分散還元効果による探索の利点を定量化することにより, OCOにおけるペアワイズ探索の合理化処理を行う。
関連論文リスト
- Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction [7.798233121583888]
我々は、逆選択された制約を伴う制約付きオンライン制約(COCO)について検討する。
強い凸損失に対して、我々のアルゴリズムは、$O(sqrtT)$後悔を維持しながら$mathsfCCV$を$O(sqrtT)$に改善する。
論文 参考訳（メタデータ） (2026-05-20T12:40:27Z) - Convex Optimization with Nested Evolving Feasible Sets [4.67724003380452]
両ケースに対して$o(T)$ regretのオンラインアルゴリズムが$(logT)$の移動コストを持ち、Frugalの最適性を証明していることを示す。
また、$o(T)$ regretのオンラインアルゴリズムは、両方のケースに対して$(logT)$の移動コストを持ち、Frugalの最適性を証明することも示している。
論文 参考訳（メタデータ） (2026-05-08T07:42:15Z) - Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
論文 参考訳（メタデータ） (2025-02-11T19:54:11Z) - Online Convex Optimization with a Separation Oracle [10.225358400539719]
本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
論文 参考訳（メタデータ） (2024-10-03T13:35:08Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。