論文の概要: Active Learning For Contextual Linear Optimization: A Margin-Based Approach

• arxiv url: http://arxiv.org/abs/2305.06584v2
• Date: Thu, 30 Jan 2025 04:08:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-31 15:12:31.000744
• Title: Active Learning For Contextual Linear Optimization: A Margin-Based Approach
• Title（参考訳）: 文脈線形最適化のためのアクティブラーニング
• Authors: Mo Liu, Paul Grigas, Heyuan Liu, Zuo-Jun Max Shen,
• Abstract要約: ラベル取得アルゴリズムを導入し、ラベルなしデータからラベルの特徴サンプルの要求を逐次決定する。 ラベルが取得されたサンプルの数として定義されるラベル複雑性の上限を導出する。 提案アルゴリズムは,教師付き学習手法よりもラベルの複雑さがはるかに小さいことを示す。
• 参考スコア（独自算出の注目度）: 6.09977411428684
• License:
• Abstract: We develop the first active learning method for contextual linear optimization. Specifically, we introduce a label acquisition algorithm that sequentially decides whether to request the ``labels'' of feature samples from an unlabeled data stream, where the labels correspond to the coefficients of the objective in the linear optimization. Our method is the first to be directly informed by the decision loss induced by the predicted coefficients, referred to as the Smart Predict-then-Optimize (SPO) loss. Motivated by the structure of the SPO loss, our algorithm adopts a margin-based criterion utilizing the concept of distance to degeneracy. In particular, we design an efficient active learning algorithm with theoretical excess risk (i.e., generalization) guarantees. We derive upper bounds on the label complexity, defined as the number of samples whose labels are acquired to achieve a desired small level of SPO risk. These bounds show that our algorithm has a much smaller label complexity than the naive supervised learning approach that labels all samples, particularly when the SPO loss is minimized directly on the collected data. To address the discontinuity and nonconvexity of the SPO loss, we derive label complexity bounds under tractable surrogate loss functions. Under natural margin conditions, these bounds also outperform naive supervised learning. Using the SPO+ loss, a specialized surrogate of the SPO loss, we establish even tighter bounds under separability conditions. Finally, we present numerical evidence showing the practical value of our algorithms in settings such as personalized pricing and the shortest path problem.
• Abstract（参考訳）: 文脈線形最適化のための最初の能動的学習法を開発した。 具体的には、ラベル付けされていないデータストリームから特徴サンプルの `labels'' を要求するかどうかを逐次決定するラベル取得アルゴリズムを導入し、そのラベルは線形最適化における目的の係数に対応する。 本手法は,予測係数によって引き起こされる決定損失によって直接的に伝達される最初の手法であり,これをSmart Predict-then-Optimize(SPO)損失と呼ぶ。 提案アルゴリズムは,SPO損失の構造に触発され,縮退までの距離という概念を生かしたマージンベースの基準を採用する。 特に,理論的過剰リスク(一般化)を保証した効率的な能動学習アルゴリズムを設計する。 SPOリスクの最小レベルを達成するためにラベルが取得されたサンプルの数として定義されるラベル複雑性の上限を導出する。 これらのバウンダリは,SPO損失が収集したデータに直接最小限に抑えられる場合,全てのサンプルをラベル付けする単純な教師付き学習手法よりも,アルゴリズムのラベル複雑性がはるかに小さいことを示している。 SPO損失の不連続性と非凸性に対処するため、トラクタブル・サロゲート損失関数の下でラベルの複雑性境界を導出する。 自然の限界条件下では、これらの境界は教師あり学習よりも優れている。 SPO+損失は、SPO損失の特別なサロゲートであるSPO+損失を用いて、分離性条件下ではさらに厳密な境界を確立する。 最後に、パーソナライズされた価格設定や最短経路問題などの設定において、アルゴリズムの実用的価値を示す数値的なエビデンスを示す。

関連論文リスト

• Offline RL via Feature-Occupancy Gradient Ascent [9.983014605039658]
  大規模無限水平割引マルコフ決定過程(MDP)におけるオフライン強化学習の研究 我々は,特徴占有空間における勾配上昇の形式を実行する新しいアルゴリズムを開発した。 結果として得られた単純なアルゴリズムは、強い計算とサンプルの複雑さの保証を満たすことを示す。
  論文  参考訳（メタデータ） (2024-05-22T15:39:05Z)
• Easy Learning from Label Proportions [17.71834385754893]
  Easyllpは、アグリゲーションラベルに基づいた、柔軟で簡単に実装可能なデバイアス方式である。 我々の手法は、任意のモデルが個々のレベルで予想される損失を正確に見積もることができる。
  論文  参考訳（メタデータ） (2023-02-06T20:41:38Z)
• Interpolation-based Contrastive Learning for Few-Label Semi-Supervised Learning [43.51182049644767]
  半教師付き学習(SSL)は,ラベルが限定された強力なモデルを構築する上で,有効な手法であることが長年証明されてきた。 摂動サンプルを元のものと類似した予測を強制する正規化に基づく手法が注目されている。 本稿では,学習ネットワークの埋め込みを誘導し,サンプル間の線形変化を誘導する新たな対照的な損失を提案する。
  論文  参考訳（メタデータ） (2022-02-24T06:00:05Z)
• Neural Active Learning with Performance Guarantees [37.16062387461106]
  非パラメトリックなレシエーションにおけるストリーミング環境におけるアクティブラーニングの問題について検討する。 我々は最近提案されたニューラル・タンジェント・カーネル(NTK)近似ツールを用いて、アルゴリズムが操作する特徴空間と学習したモデルを上から計算する適切なニューラル埋め込みを構築する。
  論文  参考訳（メタデータ） (2021-06-06T20:44:23Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。 本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。 政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
  論文  参考訳（メタデータ） (2021-06-03T09:50:13Z)
• RATT: Leveraging Unlabeled Data to Guarantee Generalization [96.08979093738024]
  ラベルのないデータを利用して一般化境界を生成する手法を紹介します。 境界が0-1経験的リスク最小化に有効であることを証明します。 この作業は、見えないラベル付きデータが利用できない場合でも、ディープネットの一般化を証明するためのオプションを実践者に提供します。
  論文  参考訳（メタデータ） (2021-05-01T17:05:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  半教師付き学習における簡単なメタ学習アルゴリズムを提案する。 その結果,提案アルゴリズムは最先端の手法に対して良好に動作することがわかった。
  論文  参考訳（メタデータ） (2020-07-08T08:48:56Z)
• Gradient Descent in RKHS with Importance Labeling [58.79085525115987]
  我々は重要ラベル付け問題について研究し、ラベルなしデータが多く与えられている。 ラベルなしデータの情報サブセットを効果的に選択できる新しい重要ラベル方式を提案する。
  論文  参考訳（メタデータ） (2020-06-19T01:55:00Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。 既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。 本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-19T08:35:15Z)

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

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