論文の概要: Smoothed Analysis with Adaptive Adversaries
- arxiv url: http://arxiv.org/abs/2102.08446v1
- Date: Tue, 16 Feb 2021 20:54:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-18 14:43:26.092674
- Title: Smoothed Analysis with Adaptive Adversaries
- Title（参考訳）: アダプティブ・アドバンサリによるスムース分析
- Authors: Nika Haghtalab, Tim Roughgarden, Abhishek Shetty
- Abstract要約: オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。
このモデルでは、敵は各時間に一様分布の$tfrac1sigma$倍の密度関数を持つ入力分布を選択する。
本研究の結果は,アルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて,入力分布を選択可能な適応的敵に対して成り立っている。
- 参考スコア（独自算出の注目度）: 28.940767013349408
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove novel algorithmic guarantees for several online problems in the
smoothed analysis model. In this model, at each time an adversary chooses an
input distribution with density function bounded above by $\tfrac{1}{\sigma}$
times that of the uniform distribution; nature then samples an input from this
distribution. Crucially, our results hold for {\em adaptive} adversaries that
can choose an input distribution based on the decisions of the algorithm and
the realizations of the inputs in the previous time steps.
This paper presents a general technique for proving smoothed algorithmic
guarantees against adaptive adversaries, in effect reducing the setting of
adaptive adversaries to the simpler case of oblivious adversaries. We apply
this technique to prove strong smoothed guarantees for three problems:
-Online learning: We consider the online prediction problem, where instances
are generated from an adaptive sequence of $\sigma$-smooth distributions and
the hypothesis class has VC dimension $d$. We bound the regret by
$\tilde{O}\big(\sqrt{T d\ln(1/\sigma)} + d\sqrt{\ln(T/\sigma)}\big)$. This
answers open questions of [RST11,Hag18].
-Online discrepancy minimization: We consider the online Koml\'os problem,
where the input is generated from an adaptive sequence of $\sigma$-smooth and
isotropic distributions on the $\ell_2$ unit ball. We bound the $\ell_\infty$
norm of the discrepancy vector by $\tilde{O}\big(\ln^2\!\big(
\frac{nT}{\sigma}\big) \big)$.
-Dispersion in online optimization: We consider online optimization of
piecewise Lipschitz functions where functions with $\ell$ discontinuities are
chosen by a smoothed adaptive adversary and show that the resulting sequence is
$\big( {\sigma}/{\sqrt{T\ell}}, \tilde O\big(\sqrt{T\ell}
\big)\big)$-dispersed. This matches the parameters of [BDV18] for oblivious
adversaries, up to log factors.
- Abstract（参考訳）: オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。
このモデルでは、敵が上記の密度関数を持つ入力分布を $\tfrac{1}{\sigma}$ 倍の均一分布で選択するたびに、自然は、この分布から入力をサンプリングする。
重要なことに、我々の結果はアルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて入力分布を選択できる「適応的」敵に対して成り立つ。
本稿では,適応的敵意に対するアルゴリズム的保証の平滑化を実現するための汎用的手法を提案する。
オンライン学習: オンライン予測問題を考えると、インスタンスは$\sigma$-smooth分布の適応シーケンスから生成され、仮説クラスはVC次元が$d$である。
後悔を$\tilde{o}\big(\sqrt{t d\ln(1/\sigma)} + d\sqrt{\ln(t/\sigma)}\big)$ で縛る。
これは[RST11,Hag18]のオープンな質問に答えます。
オンライン差分最小化:$\sigma$-smoothの適応列と$\ell_2$単位球上の等方分布から入力が生成されるオンラインKoml\'os問題を考える。
矛盾ベクトルの $\ell_\infty$ ノルムを $\tilde{O}\big(\ln^2\!\big( \frac{nT}{\sigma}\big) \big)$ でバインドします。
オンライン最適化の分散:$\ell$の不連続関数が滑らかな適応的逆数によって選択される部分的なリプシッツ関数のオンライン最適化を検討し、結果列が$\big( {\sigma}/{\sqrt{t\ell}}, \tilde o\big(\sqrt{t\ell} \big)\big)$-dispersedであることを示す。
これは、[BDV18]の不正な敵のパラメータとログファクターに一致します。
関連論文リスト
- Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳（メタデータ） (2024-03-05T12:28:00Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization [40.19608203064051]
本稿では,SEAモデルに対する楽観的オンラインミラー降下(OMD)の理論的保証について検討する。
強い凸と滑らかな関数に対して、$mathcalO(sigma_max2 + Sigma_max2) log T よりも優れた $mathcalO(sigma_max2 + Sigma_max2) log T を確立する。
非定常シナリオにおける静的な後悔境界よりも有利な凸関数と滑らかな関数を持つモデルに対する最初の動的後悔保証を確立する。
論文 参考訳（メタデータ） (2023-02-09T10:42:11Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - (Nearly) Optimal Private Linear Regression via Adaptive Clipping [22.639650869444395]
固定されたガウス型分布から各データ点をサンプリングする微分プライベート線形回帰問題について検討する。
本稿では,各イテレーションの点を置換せずにサンプリングする1パスのミニバッチ勾配勾配法(DP-AMBSSGD)を提案し,解析する。
論文 参考訳（メタデータ） (2022-07-11T08:04:46Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - 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) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-13T05:00:01Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。