論文の概要: Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming

• arxiv url: http://arxiv.org/abs/2002.08841v2
• Date: Fri, 13 Nov 2020 22:04:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 08:20:11.311297
• Title: Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming
• Title（参考訳）: 混合整数プログラミングによるオークションにおけるコンテキスト予約価格最適化
• Authors: Joey Huchette, Haihao Lu, Hossein Esfandiari, Vahab Mirrokni
• Abstract要約: 本研究では,販売者側から期待される収益を最大化するために,価格設定のための線形モデル学習の課題について検討する。 まず,EmphExponential Time仮説が失敗しない限り,この問題を時間内に解決することは不可能であることを示す。 第二に、この問題に対して強力な混合整数型MIPの定式化を提案する。
• 参考スコア（独自算出の注目度）: 28.03051753458544
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. First, we show that it is not possible to solve this problem in polynomial time unless the \emph{Exponential Time Hypothesis} fails. Second, we present a strong mixed-integer programming (MIP) formulation for this problem, which is capable of exactly modeling the nonconvex and discontinuous expected reward function. Moreover, we show that this MIP formulation is ideal (i.e. the strongest possible formulation) for the revenue function of a single impression. Since it can be computationally expensive to exactly solve the MIP formulation in practice, we also study the performance of its linear programming (LP) relaxation. Though it may work well in practice, we show that, unfortunately, in the worst case the optimal objective of the LP relaxation can be O(number of samples) times larger than the optimal objective of the true problem. Finally, we present computational results, showcasing that the MIP formulation, along with its LP relaxation, are able to achieve superior in- and out-of-sample performance, as compared to state-of-the-art algorithms on both real and synthetic datasets. More broadly, we believe this work offers an indication of the strength of optimization methodologies like MIP to exactly model intrinsic discontinuities in machine learning problems.
• Abstract（参考訳）: 本研究では, 販売者側からの期待収益を最大化するために, 価格設定のためのリニアモデルを学ぶ問題を, 文脈情報から検討する。 まず、この問題を多項式時間で解くことは、 \emph{Exponential Time hypothesis} が失敗しない限り不可能であることを示す。 次に,この問題に対して,非凸かつ不連続な期待報酬関数を正確にモデル化できる強混合整数型プログラミング(mip)方式を提案する。 さらに、このMIP定式化は、単一印象の収益関数に理想的であること(すなわち、最強の定式化)を示す。 MIPの定式化を正確に解くには計算コストがかかるため、線形プログラミング(LP)緩和の性能についても検討する。 実際にうまく機能するかもしれないが、残念なことに、最悪の場合、LP緩和の最適目的は、真の問題の最適目的の2倍のO(サンプル数)であることが示される。 最後に,mipの定式化はlp緩和とともに,実データと合成データの両方の最先端アルゴリズムと比較して優れたin-out-of-sample性能を実現できることを示す計算結果を示す。 より広範に、この研究は、機械学習問題における本質的な不連続性を正確にモデル化するために、MIPのような最適化手法の強みを示すと信じている。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  最適公正表現はいくつかの有用な構造特性を持つことを示す。 そこで,これらの近似問題は,凹凸プログラミング法により効率的に解けることを示す。
  論文  参考訳（メタデータ） (2024-09-26T08:46:48Z)
• Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs [16.006893624836554]
  本稿では,VBMLE (Value-Biased Maximum Likelihood Estimation) のレンズによる線形MDPの解法を提案する。 VBMLEは、各時間ステップで1つの最適化問題だけを解決する必要があるため、計算的により効率的である。 後悔する解析では、線形MDPにおけるMLEの一般収束結果が、新しいスーパーマーチンゲール構造を通して提供される。
  論文  参考訳（メタデータ） (2023-10-17T18:27:27Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究 まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。 次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
  論文  参考訳（メタデータ） (2023-06-21T16:04:03Z)
• Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize [57.22851616806617]
  本手法は,文献から得られた4つの領域において,最先端の成果が得られることを示す。 提案手法は, 局所性仮定が破られた場合, 既存手法よりも200%近く性能が向上する。
  論文  参考訳（メタデータ） (2023-05-26T11:17:45Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Portfolio optimization with discrete simulated annealing [0.0]
  離散凸関数と非凸コスト関数の存在下で最適なポートフォリオを求めるための整数最適化法を提案する。 これにより、与えられた品質でソリューションを実現できる。
  論文  参考訳（メタデータ） (2022-10-03T10:39:05Z)
• Learning to Reformulate for Linear Programming [11.628932152805724]
  本稿では,リニアプログラミング(LP)の強化学習に基づく再構成手法を提案する。 本研究では,2つの公共研究用LPデータセットと,実運用シナリオから収集した大規模LPデータセットに対して提案手法を実装した。
  論文  参考訳（メタデータ） (2022-01-17T04:58:46Z)
• Stochastic convex optimization for provably efficient apprenticeship learning [1.0609815608017066]
  コスト関数が不明な大規模マルコフ決定プロセス(MDP)について検討する。 擬似学習の課題に対処するために凸最適化ツールを用いており、これは、限られた専門家による実証からポリシーを学習するものである。
  論文  参考訳（メタデータ） (2021-12-31T19:47:57Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)

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

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