論文の概要: Black-box Methods for Restoring Monotonicity

• arxiv url: http://arxiv.org/abs/2003.09554v1
• Date: Sat, 21 Mar 2020 02:19:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-21 10:14:32.992558
• Title: Black-box Methods for Restoring Monotonicity
• Title（参考訳）: モノトニック性回復のためのブラックボックス法
• Authors: Evangelia Gergatsouli, Brendan Lucier, Christos Tzamos
• Abstract要約: 本研究では,興味のあるパラメータの単調性を復元できるアルゴリズムを開発する。 関数の期待値を少なくとも$varepsilon$で分解しながら、単調性を復元するアルゴリズムを提供する。 要求されるクエリの数は、ほとんどの場合、1/varepsilon$で対数であり、パラメータの数では指数的である。
• 参考スコア（独自算出の注目度）: 22.789204255034115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many practical applications, heuristic or approximation algorithms are used to efficiently solve the task at hand. However their solutions frequently do not satisfy natural monotonicity properties of optimal solutions. In this work we develop algorithms that are able to restore monotonicity in the parameters of interest. Specifically, given oracle access to a (possibly non-monotone) multi-dimensional real-valued function $f$, we provide an algorithm that restores monotonicity while degrading the expected value of the function by at most $\varepsilon$. The number of queries required is at most logarithmic in $1/\varepsilon$ and exponential in the number of parameters. We also give a lower bound showing that this exponential dependence is necessary. Finally, we obtain improved query complexity bounds for restoring the weaker property of $k$-marginal monotonicity. Under this property, every $k$-dimensional projection of the function $f$ is required to be monotone. The query complexity we obtain only scales exponentially with $k$.
• Abstract（参考訳）: 多くの実用的な応用において、ヒューリスティックあるいは近似アルゴリズムは、手元のタスクを効率的に解くために用いられる。 しかし、それらの解は最適解の自然な単調性をしばしば満たさない。 本研究では,興味のあるパラメータの単調性を復元できるアルゴリズムを開発する。 具体的には、(非単調な)多次元実数値関数へのオラクルアクセスを$f$とすると、関数の期待値を少なくとも$\varepsilon$で下げながら単調性を取り戻すアルゴリズムを提供する。 要求されるクエリの数は、1/\varepsilon$で最大対数であり、パラメータ数で指数関数である。 また、この指数依存が必要であることを示す下限を与える。 最後に、$k$-marginal monotonicityの弱い性質を復元するための改善されたクエリ複雑性境界を得る。 この性質の下では、関数 $f$ のすべての $k$-次元射影は単調である必要がある。 取得したクエリの複雑さは指数関数的に$k$でスケールします。

関連論文リスト

• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。 特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
  論文  参考訳（メタデータ） (2024-10-30T10:09:05Z)
• Adaptive approximation of monotone functions [0.0]
  GreedyBox が任意の関数 $f$ に対して,対数因子まで,最適なサンプル複雑性を実現することを証明した。 おそらく予想通り、GreedyBoxの$Lp(mu)$エラーは、アルゴリズムによって予測されるよりもはるかに高速な$C2$関数で減少する。
  論文  参考訳（メタデータ） (2023-09-14T08:56:31Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• On the Complexity of Dynamic Submodular Maximization [15.406670088500087]
  濃度制約の下で$(0.5+epsilon)$-approximateを維持できるアルゴリズムは、任意の定数$epsilon>0$に対して、$mathitpolynomial$ in $n$というアモータイズされたクエリ複雑性を持つ必要がある。 これは、(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexityを達成している[LMNF+20, Mon20]の最近の動的アルゴリズムとは対照的である。
  論文  参考訳（メタデータ） (2021-11-05T00:04:29Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy [26.69391745812235]
  本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。 これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
  論文  参考訳（メタデータ） (2020-11-11T17:48:00Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)

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

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