論文の概要: Adaptive Online Learning with Varying Norms
- arxiv url: http://arxiv.org/abs/2002.03963v1
- Date: Mon, 10 Feb 2020 17:22:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 08:00:18.046324
- Title: Adaptive Online Learning with Varying Norms
- Title（参考訳）: Varying Normsによる適応型オンライン学習
- Authors: Ashok Cutkosky
- Abstract要約: オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。
この結果を用いて新しい「完全行列」型後悔境界を得る。
- 参考スコア（独自算出の注目度）: 45.11667443216861
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given any increasing sequence of norms $\|\cdot\|_0,\dots,\|\cdot\|_{T-1}$,
we provide an online convex optimization algorithm that outputs points $w_t$ in
some domain $W$ in response to convex losses $\ell_t:W\to \mathbb{R}$ that
guarantees regret $R_T(u)=\sum_{t=1}^T \ell_t(w_t)-\ell_t(u)\le \tilde
O\left(\|u\|_{T-1}\sqrt{\sum_{t=1}^T \|g_t\|_{t-1,\star}^2}\right)$ where $g_t$
is a subgradient of $\ell_t$ at $w_t$. Our method does not require tuning to
the value of $u$ and allows for arbitrary convex $W$. We apply this result to
obtain new "full-matrix"-style regret bounds. Along the way, we provide a new
examination of the full-matrix AdaGrad algorithm, suggesting a better learning
rate value that improves significantly upon prior analysis. We use our new
techniques to tune AdaGrad on-the-fly, realizing our improved bound in a
concrete algorithm.
- Abstract（参考訳）: R_T(u)=\sum_{t=1}^T \ell_t(w_t)-\ell_t(u)\le \tilde O\left(\|u\|_{T-1}\sqrt {\sum_{t=1}^T \|g_t\|_{t-1,\star}^2right) ここで、$g$は$R_t(u)=\sum_{t=1}^T \ell_t(w_t)-\ell_t(u)\le \tilde O\left(\|u\|_{T-1}\sqrt {\sum_{t=1}^T \|g_t\|_{t-1,\star}^2right)である。
このメソッドは$u$の値のチューニングを必要とせず、任意の凸$w$を許容する。
この結果を用いて新しい「完全行列」型後悔境界を得る。
その過程で,AdaGradアルゴリズムの完全行列を新たに検討し,事前解析によりより優れた学習率値が得られたことを示唆する。
新しい手法を使ってAdaGradをオンザフライでチューニングし、具体的なアルゴリズムで改善したバウンドを実現する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Partially Unitary Learning [0.0]
ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。
この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-05-16T17:13:55Z) - Minimax Optimal Submodular Optimization with Bandit Feedback [13.805872311596739]
単調な部分モジュラー集合関数 $f: 2[n] rightarrow [0,1]$ をバンドイットフィードバックの下で最大化する。
具体的には、$f$は学習者には知られていないが、各時点で$t=1,dots,T$は、$|S_t| leq k$でセットの$S_tサブセット[n]$を選択し、$eta_t$が平均ゼロのサブガウスノイズである場合に、$f(S_t) + eta_t$を受け取る。
論文 参考訳（メタデータ） (2023-10-27T20:19:03Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。
ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
論文 参考訳（メタデータ） (2021-06-15T02:05:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。