論文の概要: Scale-free Unconstrained Online Learning for Curved Losses
- arxiv url: http://arxiv.org/abs/2202.05630v1
- Date: Fri, 11 Feb 2022 14:10:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-14 15:24:49.222416
- Title: Scale-free Unconstrained Online Learning for Curved Losses
- Title（参考訳）: 曲線損失に対するスケールフリー無拘束オンライン学習
- Authors: Jack J. Mayo, H\'edi Hadiji and Tim van Erven
- Abstract要約: コンパレータのノルム$U$と勾配の最大ノルム$G$に同時に適応する可能性を検討する。
意外なことに、最近の研究では1ドル=Lipschitz損失の特定のケースにおいて、適応性に対するそのような価格が不要であることが示されている。
- 参考スコア（独自算出の注目度）: 1.5147172044848798
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A sequence of works in unconstrained online convex optimisation have
investigated the possibility of adapting simultaneously to the norm $U$ of the
comparator and the maximum norm $G$ of the gradients. In full generality,
matching upper and lower bounds are known which show that this comes at the
unavoidable cost of an additive $G U^3$, which is not needed when either $G$ or
$U$ is known in advance. Surprisingly, recent results by Kempka et al. (2019)
show that no such price for adaptivity is needed in the specific case of
$1$-Lipschitz losses like the hinge loss. We follow up on this observation by
showing that there is in fact never a price to pay for adaptivity if we
specialise to any of the other common supervised online learning losses: our
results cover log loss, (linear and non-parametric) logistic regression, square
loss prediction, and (linear and non-parametric) least-squares regression. We
also fill in several gaps in the literature by providing matching lower bounds
with an explicit dependence on $U$. In all cases we obtain scale-free
algorithms, which are suitably invariant under rescaling of the data. Our
general goal is to establish achievable rates without concern for computational
efficiency, but for linear logistic regression we also provide an adaptive
method that is as efficient as the recent non-adaptive algorithm by Agarwal et
al. (2021).
- Abstract（参考訳）: 制約のないオンライン凸最適化における一連の研究は、コンパレータのノルム$U$と勾配の最大ノルム$G$に同時に適応する可能性を検討した。
完全な一般性では、上界と下界の一致は知られており、これは前もって$g$または$u$が知られている場合には不要な$g u^3$の不可避なコストであることを示している。
驚くべきことに、Kempka et al. (2019) による最近の結果は、ヒンジ損失のような1ドルLipschitz損失の特定のケースでは、適応性に対するそのような価格が不要であることを示している。
我々の結果は、ログ損失、(線形および非パラメトリック)ロジスティック回帰、(線形および非パラメトリック)最小二乗回帰、(線形および非パラメトリック)最小二乗回帰をカバーしている。
また、u$ への明示的な依存を伴う下限のマッチングを提供することで、文学におけるいくつかのギャップを埋める。
いずれの場合も、データの再スケーリングにおいて好ましく不変なスケールフリーなアルゴリズムが得られます。
我々のゴールは計算効率を気にせずに達成可能なレートを確立することですが、線形ロジスティック回帰では、Agarwalらによる最近の非適応アルゴリズム(2021年)と同等の効率の適応方法も提供します。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Optimal Multiclass U-Calibration Error and Beyond [31.959887895880765]
オンラインマルチクラス境界U-キャリブレーションの問題は、予測器がU-キャリブレーション誤差の低いクラスをK$で逐次分布予測することを目的としている。
最適U校正誤差は$Theta(sqrtKT)$である。
論文 参考訳（メタデータ） (2024-05-28T20:33:18Z) - Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
論文 参考訳（メタデータ） (2023-09-27T21:54:52Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - One Step of Gradient Descent is Provably the Optimal In-Context Learner
with One Layer of Linear Self-Attention [31.522320487765878]
最近の研究は、文脈内学習を実証的に分析している。
線形自己アテンションを持つ一層変圧器は勾配降下の一段階を実装することを学習する。
論文 参考訳（メタデータ） (2023-07-07T13:09:18Z) - Asymptotic Characterisation of Robust Empirical Risk Minimisation
Performance in the Presence of Outliers [18.455890316339595]
我々は,次元$d$とデータ点数$n$が固定比$alpha=n/d$で分岐した場合,高次元の線形回帰について検討し,出力率を含むデータモデルについて検討する。
我々は、$ell$-regularized $ell$, $ell_$, Huber損失を用いて、経験的リスク最小化(ERM)のパフォーマンスの正確性を提供する。
論文 参考訳（メタデータ） (2023-05-30T12:18:39Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum
Minimization [52.25843977506935]
有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。
そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
論文 参考訳（メタデータ） (2022-11-03T14:41:46Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - An efficient projection neural network for $\ell_1$-regularized logistic
regression [10.517079029721257]
本稿では, $ell_$-regularized logistics regression のための単純な投影ニューラルネットワークを提案する。
提案したニューラルネットワークは、余分な補助変数や滑らかな近似を必要としない。
また、リアプノフ理論を用いて、提案したニューラルネットワークの収束について検討し、任意の初期値を持つ問題の解に収束することを示す。
論文 参考訳（メタデータ） (2021-05-12T06:13:44Z) - Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。
近勾配法はOWL回帰を解くための標準手法として用いられる。
未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
論文 参考訳（メタデータ） (2020-06-29T23:35:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。