論文の概要: Online $\mathrm{L}^{\natural}$-Convex Minimization

• arxiv url: http://arxiv.org/abs/2404.17158v1
• Date: Fri, 26 Apr 2024 05:03:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-29 14:04:24.273899
• Title: Online $\mathrm{L}^{\natural}$-Convex Minimization
• Title（参考訳）: オンライン $\mathrm{L}^{\natural}$-Convex 最小化
• Authors: Ken Yokoyama, Shinji Ito, Tatsuya Matsuoka, Kei Kimura, Makoto Yokoo,
• Abstract要約: オンライン意思決定問題は、プレイヤーが長期的損失に対して繰り返し意思決定を行う学習問題である。 既存の最小化のための一般的なフレームワークは、オンラインのサブモジュール化である。 本稿では,オンラインの$mathrmLnatural$-サブセットをサブモジュール関数として導入し,ドメインサブセットが単位ハイパーキューブのサブセットとなるようにする。
• 参考スコア（独自算出の注目度）: 31.045112870480537
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: An online decision-making problem is a learning problem in which a player repeatedly makes decisions in order to minimize the long-term loss. These problems that emerge in applications often have nonlinear combinatorial objective functions, and developing algorithms for such problems has attracted considerable attention. An existing general framework for dealing with such objective functions is the online submodular minimization. However, practical problems are often out of the scope of this framework, since the domain of a submodular function is limited to a subset of the unit hypercube. To manage this limitation of the existing framework, we in this paper introduce the online $\mathrm{L}^{\natural}$-convex minimization, where an $\mathrm{L}^{\natural}$-convex function generalizes a submodular function so that the domain is a subset of the integer lattice. We propose computationally efficient algorithms for the online $\mathrm{L}^{\natural}$-convex function minimization in two major settings: the full information and the bandit settings. We analyze the regrets of these algorithms and show in particular that our algorithm for the full information setting obtains a tight regret bound up to a constant factor. We also demonstrate several motivating examples that illustrate the usefulness of the online $\mathrm{L}^{\natural}$-convex minimization.
• Abstract（参考訳）: オンライン意思決定問題は、プレイヤーが長期的損失を最小限に抑えるために繰り返し意思決定を行う学習問題である。 アプリケーションに現れるこれらの問題は、しばしば非線形組合せ目的関数を持ち、そのような問題に対するアルゴリズムの開発は、かなりの注目を集めている。 そのような目的関数を扱うための既存の一般的なフレームワークは、オンラインのサブモジュラー最小化である。 しかし、部分モジュラ函数の領域は単位ハイパーキューブの部分集合に限られているため、実際的な問題はこのフレームワークの範囲外であることが多い。 既存のフレームワークのこの制限を管理するために、オンラインの$\mathrm{L}^{\natural}$-convex最小化を導入し、$\mathrm{L}^{\natural}$-convex関数は部分モジュラ函数を一般化して、その領域が整数格子の部分集合となるようにする。 本稿では,オンラインの$\mathrm{L}^{\natural}$-convex関数最小化のための計算効率のよいアルゴリズムを提案する。 我々はこれらのアルゴリズムの後悔を分析し、特に、完全な情報設定のためのアルゴリズムが一定の要因に縛られた厳密な後悔を得ることを示す。 また、オンライン$\mathrm{L}^{\natural}$-convex最小化の有用性を示すいくつかのモチベーション例を示す。

関連論文リスト

• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。 この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
  論文  参考訳（メタデータ） (2024-06-26T18:19:10Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets [13.23676270963484]
  DR-サブモジュラー連続関数は、機械学習、通信システム、研究、経済学の分野において多くの実世界の応用を持つ。 tfrac14 (1 - m)$-the-art offline algorithmと一致する時間オンラインアルゴリズムを提示する。 また、我々のアルゴリズムとDuの(2022)オフラインはどちらも強い意味で最適であることを示す。
  論文  参考訳（メタデータ） (2022-10-12T07:04:24Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Efficient Online-Bandit Strategies for Minimax Learning Problems [21.300877551771197]
  いくつかの学習問題は、例えば、実験的な分散ロバスト学習や、非標準集約的損失による最小化といった、min-max問題の解決に関係している。 具体的には、これらの問題は、モデルパラメータ$winmathcalW$と、トレーニングセットの実証分布$pinmathcalK$で学習を行う凸線型問題である。 効率的な手法を設計するために、オンライン学習アルゴリズムを(組合せ)帯域幅アルゴリズムと対戦させる。
  論文  参考訳（メタデータ） (2021-05-28T16:01:42Z)
• Decomposable Submodular Function Minimization via Maximum Flow [6.993741009069205]
  本稿では,分解可能な部分モジュラー関数の最小化に対する離散最適化と連続最適化のアプローチを橋渡しする。 我々は、最大フローオラクルに対する多数の呼び出しに還元することで、この問題に対する実行時間を改善する。
  論文  参考訳（メタデータ） (2021-03-05T18:46:38Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-28T23:18:58Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。