論文の概要: Regret minimization in stochastic non-convex learning via a
proximal-gradient approach
- arxiv url: http://arxiv.org/abs/2010.06250v1
- Date: Tue, 13 Oct 2020 09:22:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-08 00:58:27.136528
- Title: Regret minimization in stochastic non-convex learning via a
proximal-gradient approach
- Title(参考訳): 近位勾配アプローチによる確率的非凸学習における後悔の最小化
- Authors: Nadav Hallak and Panayotis Mertikopoulos and Volkan Cevher
- Abstract要約: 機械学習やオペレーションの応用によって動機づけられた私たちは、オンラインで制約された問題を最小化するために、一階のオラクルフィードバックを後悔しています。
我々は、近位複雑性低減技術を保証する新しいプロキシグレードを開発する。
- 参考スコア(独自算出の注目度): 80.59047515124198
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by applications in machine learning and operations research, we
study regret minimization with stochastic first-order oracle feedback in online
constrained, and possibly non-smooth, non-convex problems. In this setting, the
minimization of external regret is beyond reach for first-order methods, so we
focus on a local regret measure defined via a proximal-gradient mapping. To
achieve no (local) regret in this setting, we develop a prox-grad method based
on stochastic first-order feedback, and a simpler method for when access to a
perfect first-order oracle is possible. Both methods are min-max order-optimal,
and we also establish a bound on the number of prox-grad queries these methods
require. As an important application of our results, we also obtain a link
between online and offline non-convex stochastic optimization manifested as a
new prox-grad scheme with complexity guarantees matching those obtained via
variance reduction techniques.
- Abstract(参考訳): 機械学習と運用研究の応用に動機づけられ、オンライン制約付き、おそらくは非スムースな非凸問題におけるオラクルの確率的第一次フィードバックによる後悔の最小化について研究した。
この設定では、外部後悔の最小化は一階法には届かないので、近位勾配写像によって定義される局所後悔測度に焦点をあてる。
この設定で(局所的な)後悔を起こさないために、確率的一階フィードバックに基づくプロキシグレード法と、完全一階オラクルへのアクセスが可能な場合の簡易な方法を開発する。
どちらの手法も min-max オーダー最適であり、これらの手法が要求するprox-grad クエリの数にも制約を設けます。
また, オンラインとオフラインの非凸確率最適化を, 分散低減手法によって得られるものに適合する複雑さを保証する新しいprox-gradスキームとして表現した。
関連論文リスト
- Adaptive multi-gradient methods for quasiconvex vector optimization and
applications to multi-task learning [1.03590082373586]
線形探索手法を含まない適応的なステップサイズ法を提案する。
我々は、控えめな仮定に基づく非有界収束を証明した。
提案手法をマルチタスク実験に適用し,大規模課題に対する有効性を示す。
論文 参考訳(メタデータ) (2024-02-09T07:20:14Z) - Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳(メタデータ) (2023-11-04T11:12:24Z) - Restarts subject to approximate sharpness: A parameter-free and optimal
scheme for first-order methods [2.513785998932353]
シャープネス(Sharpness)は、目的関数の準最適性によってミニマからの距離を束縛する連続最適化における仮定である。
シャープネスは、通常不明な問題固有の定数を伴い、以前の再起動スキームは収束率を減少させる。
対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
論文 参考訳(メタデータ) (2023-01-05T19:01:41Z) - Self-adaptive algorithms for quasiconvex programming and applications to
machine learning [0.0]
凸線探索技術や,軽微な仮定の下での汎用的アプローチを含まない,自己適応的なステップサイズ戦略を提案する。
提案手法は,いくつかの計算例から予備的な結果によって検証される。
大規模問題に対する提案手法の有効性を実証するため,機械学習実験に適用した。
論文 参考訳(メタデータ) (2022-12-13T05:30:29Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2022-02-09T19:22:34Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.71361250701075]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応するのは, 既往の結果よりも厳密であり, 最悪の場合, 同一の値が保証されるためである。
論文 参考訳(メタデータ) (2021-12-29T02:42:59Z) - On Constraints in First-Order Optimization: A View from Non-Smooth
Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。
提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。
結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文 参考訳(メタデータ) (2021-07-17T11:45:13Z) - Exact Stochastic Second Order Deep Learning [0.0]
ディープラーニングは、主にバックプロパゲーションの中心概念を中心に構築されたファーストオーダーメソッドによって支配される。
二階法では、一階法よりも使われない二階微分を考慮に入れる。
論文 参考訳(メタデータ) (2021-04-08T14:29:31Z) - Improper Learning with Gradient-based Policy Optimization [62.50997487685586]
未知のマルコフ決定過程に対して学習者がmベースコントローラを与えられる不適切な強化学習設定を考える。
制御器の不適切な混合のクラス上で動作する勾配に基づくアプローチを提案する。
論文 参考訳(メタデータ) (2021-02-16T14:53:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。