論文の概要、ライセンス

# (参考訳) Submodular + Concave [全文訳有]

Submodular + Concave ( http://arxiv.org/abs/2106.04769v1 )

ライセンス: CC BY 4.0
Siddharth Mitra, Moran Feldman, Amin Karbasi(参考訳) 一階最適化法が凸関数の最大目的値に収束し、(非凸/非凸)連続部分モジュラ函数に対する定数因子近似の保証を提供できることはよく確立されている。 本研究では, 可解凸体上での$f(x) = g(x) +c(x)$ の関数の最大化の研究を開始する。ここでは$g$ は滑らかな dr-サブモジュラー関数であり、$c$ は滑らかな凸関数である。 このクラスの函数は、理論的な保証がないような凹凸および連続DR-部分モジュラ函数の厳密な拡張である。 目的関数の性質(例えば$G$ と $C$ が単調か非負か)と集合 $P$ の性質(下向きの閉か否かに関わらず)により、1-1/e$, $1/e$, $1/2$ の近似保証を提供するフランク・ウルフ型アルゴリズムのスイートを提供する。 次に、我々のアルゴリズムを用いて、与えられた基底集合から多様な要素の選択(決定点過程のモードに対応する)とクラスタ化された要素のセットの選択(適切な凹凸関数の最大値に対応する)を円滑に補間するフレームワークを得る。 さらに, 制約条件と制約条件の両方で, 上記のクラス(DR-submodular + concave)の様々な関数にアルゴリズムを適用し, アルゴリズムが自然ベースラインを一貫して上回ることを示す。

It has been well established that first order optimization methods can converge to the maximal objective value of concave functions and provide constant factor approximation guarantees for (non-convex/non-conc ave) continuous submodular functions. In this work, we initiate the study of the maximization of functions of the form $F(x) = G(x) +C(x)$ over a solvable convex body $P$, where $G$ is a smooth DR-submodular function and $C$ is a smooth concave function. This class of functions is a strict extension of both concave and continuous DR-submodular functions for which no theoretical guarantee is known. We provide a suite of Frank-Wolfe style algorithms, which, depending on the nature of the objective function (i.e., if $G$ and $C$ are monotone or not, and non-negative or not) and on the nature of the set $P$ (i.e., whether it is downward closed or not), provide $1-1/e$, $1/e$, or $1/2$ approximation guarantees. We then use our algorithms to get a framework to smoothly interpolate between choosing a diverse set of elements from a given ground set (corresponding to the mode of a determinantal point process) and choosing a clustered set of elements (corresponding to the maxima of a suitable concave function). Additionally, we apply our algorithms to various functions in the above class (DR-submodular + concave) in both constrained and unconstrained settings, and show that our algorithms consistently outperform natural baselines.
公開日: Wed, 9 Jun 2021 01:59:55 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 9 1 2 0 2 n u J 9 0.85
] . C O h t a m ] . C O h t a m 0.85
[ 1 v 9 6 7 4 0 [ 1 v 9 6 7 4 0 0.85
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Submodular + Concave Submodular + Concave 0.85
Siddharth Mitra Siddharth属 0.62
Yale University Moran Feldman University of Haifa イェール大学 ハイファのモラン・フェルドマン大学 0.66
Amin Karbasi Yale University アミン・カルバシ・イェール大学 0.51
siddharth.mitra@yale .edu siddharth.mitra@yale .edu 0.59
moranfe@cs.haifa.ac. il moranfe@cs.haifa.ac. il 0.47
amin.karbasi@yale.ed u amin.karbasi@yale.ed u 0.59
Abstract It has been well established that first order optimization methods can converge to the maximal objective value of concave functions and provide constant factor approximation guarantees for (non-convex/non-conc ave) continuous submodular functions. 概要 一階最適化法が凸関数の最大目的値に収束し、(非凸/非凸)連続部分モジュラ函数に対する定数因子近似の保証を提供できることはよく確立されている。 0.60
In this work, we initiate the study of the maximization of functions of the form F (x) = G(x) + C(x) over a solvable convex body P , where G is a smooth DR-submodular function and C is a smooth concave function. 本研究では、可解凸体 P 上の F (x) = G(x) + C(x) という形の函数の最大化の研究を開始する。
訳抜け防止モード: 本研究では、F(x) = G(x) という形の関数の最大化の研究を開始する。 可解凸体 P 上の + C(x ) G は滑らかな DR である -部分モジュラー関数と C は滑らかな凹函数である。
0.81
This class of functions is a strict extension of both concave and continuous DR-submodular functions for which no theoretical guarantee is known. このクラスの函数は、理論的な保証がないような凹凸および連続DR-部分モジュラ函数の厳密な拡張である。 0.73
We provide a suite of Frank-Wolfe style algorithms, which, depending on the nature of the objective function (i.e., if G and C are monotone or not, and non-negative or not) and on the nature of the set P (i.e., whether it is downward closed or not), provide 1 − 1/e, 1/e, or 1/2 approximation guarantees. 対象関数の性質(g と c が単調であるかどうか、非負であるかどうか)と集合 p の性質(すなわち、下向きに閉であるかどうか)に応じて、1 − 1/e, 1/e, 1/2 近似保証を与えるフランク・ウルフ型アルゴリズムの一組を提供する。 0.75
We then use our algorithms to get a framework to smoothly interpolate between choosing a diverse set of elements from a given ground set (corresponding to the mode of a determinantal point process) and choosing a clustered set of elements (corresponding to the maxima of a suitable concave function). 次に、我々のアルゴリズムを用いて、与えられた基底集合から多様な要素の選択(決定点過程のモードに対応する)とクラスタ化された要素のセットの選択(適切な凹凸関数の最大値に対応する)を円滑に補間するフレームワークを得る。 0.90
Additionally, we apply our algorithms to various functions in the above class (DR-submodular + concave) in both constrained and unconstrained settings, and show that our algorithms consistently outperform natural baselines. さらに, 制約条件と制約条件の両方で, 上記のクラス(DR-submodular + concave)の様々な関数にアルゴリズムを適用し, アルゴリズムが自然ベースラインを一貫して上回ることを示す。 0.76
Introduction 1 Despite their simplicity, first-order optimization methods (such as gradient descent and its variants, Frank-Wolfe, momentum based methods, and others) have shown great success in many machine learning applications. はじめに 1 単純さにもかかわらず、一階最適化手法(勾配降下とその変種、フランク・ウルフ、モーメントベース手法など)は多くの機械学習アプリケーションで大きな成功を収めている。 0.66
A large body of research in the operations research and machine learning communities has fully demystified the convergence rate of such methods in minimizing well behaved convex objectives [Bubeck, 2015, Nesterov, 2018]. 運用研究と機械学習コミュニティにおける多くの研究機関は、よく行動した凸目標を最小化するためのそのような手法の収束率を完全にデミステレーションした[Bubeck, 2015 Nesterov, 2018]。 0.76
More recently, a new surge of rigorous results has also shown that gradient descent methods can find the global minima of specific non-convex objective functions arisen from non-negative matrix factorization [Arora et al , 2012], robust PCA [Netrapalli et al , 2014], phase retrieval [Chen et al , 2019b], matrix completion [Sun and Luo, 2016], and the training of wide neural networks [Du et al , 2019, Jacot et al , 2018, Allen-Zhu et al , 2019], to name a few. 最近では,非負の行列因子化(Arora et al , 2012),ロバストPCA [Netrapalli et al , 2014], 位相検索 [Chen et al , 2019b], 行列補完 [Sun and Luo, 2016], 広範ニューラルネットワーク(Du et al , 2019, Jacot et al , 2018, Allen-Zhu et al , 2019)から生じる,非凸性目的関数の大域的最小値を求める勾配降下法が新たに出現している。
訳抜け防止モード: より最近では、厳密な結果の新たな急増により、非負の行列因子化(Arora et al, 2012)から生じる特定の非凸目的関数の大域的最小値が勾配降下法で見つかることが示されている。 堅牢PCA [Netrapalli et al, 2014 ], phase search [ Chen et al, 2019b ] 行列補完 [Sun and Luo, 2016 ] と広義ニューラルネットワークのトレーニング [Du et al, ] 2019, Jacot et al, 2018, Allen - Zhu et al, 2019 ] いくつか挙げてみましょう
0.77
It is also very well known that finding the global minimum of a general non-convex function is indeed computationally intractable [Murty and Kabadi, 1987]. また、一般の非凸関数の大域的最小値を見つけることは、確かに計算的に難解である[Murty and Kabadi, 1987]。 0.67
To avoid such impossibility results, simpler goals have been pursued by the community: either developing algorithms that can escape saddle points and reach local minima [Ge et al , 2015] or describing structural properties which guarantee that reaching a local minimizer ensures optimality [Sun et al , 2016, Bian et al , 2017b, このような不可能な結果を避けるため、コミュニティはより単純な目標を追求している: サドルポイントを逃れてローカルミニマ(ge et al , 2015)に到達するアルゴリズムを開発するか、あるいは局所最小化器に到達することを保証する構造的特性を記述するか(sun et al , 2016 bian et al , 2017b)。 0.67
1 1 0.85
英語(論文から抽出)日本語訳スコア
Hazan et al , 2016]. Hazanら、2016年。 0.59
In the same spirit, this paper quantifies a large class of non-convex functions for which first-order optimization methods provably achieve near optimal solutions. 同じ精神で、本論文は一階最適化法が最適解に近いことを証明可能な非凸関数の大きなクラスを定量化する。 0.65
More specifically, we consider objective functions that are formed by the sum of a continuous DRsubmodular function G(x) and a concave function C(x). より具体的には、連続DR部分モジュラー函数 G(x) と凹函数 C(x) の和によって形成される客観的関数を考える。 0.78
Recent research in non-convex optimization has shown that first-order optimization methods provide constant factor approximation guarantees for maximizing continuous submodular functions Bian et al [2017b], Hassani et al [2017], Bian et al [2017a], Niazadeh et al [2018], Hassani et al [2020a], Mokhtari et al [2018a]. 非凸最適化の最近の研究により、一階最適化法は連続部分モジュラ函数 Bian et al [2017b], Hassani et al [2017a], Bian et al [2017a], Niazadeh et al [2018], Hassani et al [2020a], Mokhtari et al [2018a] を最大化するための定数係数近似を保証することが示されている。 0.83
Similarly, such methods find the global maximizer of concave functions. 同様に、そのような方法は凹関数の大域的最大化子を見つける。 0.53
However, the class of F (x) = G(x) + C(x) functions is strictly larger than both concave and continuous DR-submodular functions. しかし、f(x) = g(x) + c(x) 関数の類は、凹凸函数および連続な dr-部分モジュラ函数よりも厳密に大きい。 0.80
More specifically, F (x) is not concave nor continuous DR-submodular in general (Figure 1 illustrates an example). より具体的には、F(x) は一般に凹凸や連続 DR-部分モジュラーではない(図 1 は例を示している)。
訳抜け防止モード: より具体的には、F ( x ) は凹凸でも連続 DR でもない。 (図1は例を示す)
0.75
In this paper, we show that first-order methods provably provide strong theoretical guarantees for maximizing such functions. 本稿では,一階法がそのような関数を最大化するための強力な理論的保証を提供することを示す。 0.65
The combinations of continuous submodular and concave functions naturally arise in many ML applications such as maximizing a regularized submodular function [Kazemi et al , 2020a] or finding the mode of distributions [Kazemi et al , 2020a, Robinson et al , 2019]. 連続部分モジュラ函数と凹函数の組み合わせは、正規化部分モジュラ函数の最大化(Kazemi et al , 2020a)や分布のモードの発見(Kazemi et al , 2020a, Robinson et al , 2019)など、多くのML応用において自然に発生する。 0.77
For instance, it is common to add a regularizer to a D-optimal design objective function to increase the stability of the final solution against perturbations [He, 2010, Derezinski et al , 2020, Lattimore and Szepesvari, 2020]. 例えば、D-最適設計目的関数に正規化子を加えて、摂動に対する最終解の安定性を高めることが一般的である(He, 2010, Derezinski et al , 2020, Lattimore and Szepesvari, 2020]。 0.76
Similarly, many instances of log-submodular distributions, such as determinantal point processes (DPPs), have been studied in depth in order to sample a diverse set of items from a ground set [Kulesza, 2012, Rebeschini and Karbasi, 2015, Anari et al , 2016]. 同様に、決定点過程 (Determinantal point process, DPPs) などの対数-部分モジュラー分布の多くの例は、基底集合(Kulesza, 2012, Rebeschini and Karbasi, 2015, Anari et al , 2016)から様々な項目の集合をサンプリングするために深く研究されている。 0.87
In order to control the level of diversity, one natural recipe is to consider the combination of a log-concave (e g , normal distribution, exponential distribution and Laplace distribution) [Dwivedi et al , 2019, Robinson et al , 2019] and log-submodular distributions [Djolonga and Krause, 2014, Bresler et al , 2019], i.e., Pr(x) ∝ exp(λC(x) + (1 − λ)G(x)) for some λ ∈ [0, 1]. 多様性のレベルを制御するために、1つの自然なレシピは、[Dwivedi et al , 2019, Robinson et al , 2019] と、[Djolonga and Krause, 2014 Bresler et al , 2019], すなわち、あるλ ∈ [0, 1] に対して exp(λC(x) + (1 − λ)G(x)) と対数部分モジュラー分布(Djolonga and Krause, 2014 Bresler et al , 2019] の組み合わせを考えることである。
訳抜け防止モード: 多様性のレベルを制御するために、1つの自然なレシピは、ログ-凹(例:concave)の組み合わせを考えることである。 正規分布,指数分布,ラプラス分布) [dwivedi et al, 2019, robinson et al,] 2019 ] と log - サブモジュラー分布 [djolonga と krause, 2014 bresler et al, 2019 ]、すなわち pr(x ) は exp(λc(x ) + (1 − λ)g(x) である。 ) ) for some λ ∈ [ 0, 1 ] .
0.88
In this way, we can obtain a class of distributions that contains log-concave and log-submodular distributions as special cases. このようにして、log-concave および log-submodular 分布を含む分布のクラスを特別な場合として得ることができる。 0.73
However, this class of distributions is strictly more expressive than both log-concave and log-submodular models, e g , in contrast to log-concave distributions, they are not uni-modal in general. しかし、この分布のクラスは、log-concave と log-submodular model の両方よりも厳密に表現的であり、log-concave 分布とは対照的に、一般にはユニモーダルではない。 0.69
Finding the mode of such distributions amounts to maximizing a combination of a continuous DR-submodular function and a concave function. そのような分布のモードを見つけることは、連続DR-部分モジュラ函数と凹函数の組合せを最大化することである。
訳抜け防止モード: そのような分布のモードを見つける 連続DR-部分モジュラ函数と凹関数の組み合わせを最大化する。
0.85
The contributions of this paper are as follows. 本論文の貢献は以下の通りである。 0.79
• Assuming first-order oracle access for the function F , we develop the algorithms: Greedy Frank-Wolfe (Algorithm 1) and Measured Greedy Frank-Wolfe (Algorithm 2) which achieve constant factors approximation guarantees between 1 − 1/e and 1/e depending on the setting, i.e. egdy frank-wolfe (algorithm 1) と測定されたgreedy frank-wolfe (algorithm 2) というアルゴリズムを開発し、設定によって 1 − 1/e と 1/e の間の定数の近似を保証する。
訳抜け防止モード: • 関数 F のファースト-オーダーオラクルアクセスを仮定する。 アルゴリズムの開発 : Greedy Frank - Wolfe ( Algorithm 1 ) そして、1 − 1 / e と 1 / e の間に一定の因子を近似するグリーディ・フランク - ウルフ (アルゴリズム2 ) を測る。
0.86
depending on the monotonicity and non-negativity of G and C, and depending on the constraint set having the down-closeness property or not. G と C の単調性と非負性に依存し、下限性を持つか否かの制約集合に依存する。 0.78
• Furthermore, if we have access to the individual gradients of G and C, then we are able to make the guarantee with respect to C exact using the algorithms: Gradient Combining Frank-wolfe (Algorithm 3) and Non-oblivious Frank-Wolfe (Algorithm 4). さらに、G と C の個々の勾配にアクセスすることができれば、アルゴリズムを使って C に関する保証を正確に行うことができる: Gradient Combining Frank-wolfe (Algorithm 3) and Non-oblivious Frank-Wolfe (Algorithm 4)。 0.79
These results are summarized and made more precise in Table 1 and Section 3. これらの結果は表1とセクション3でより正確にまとめられている。 0.83
• We then present experiments designed to use our algorithms to smoothly interpolate between contrasting objectives such as picking a diverse set of elements and picking a clustered set of elements. そこで我々は,アルゴリズムを用いて,多様な要素の集合の選択や,クラスタ化された要素の集合の選択といった,対照的な目的を円滑に補間する実験を行った。 0.65
This smooth interpolation provides a way to control the amount of diversity in the final solution. この滑らかな補間は最終解における多様性の量を制御する方法を提供する。 0.75
We also demonstrate the use of our algorithms to maximize a large class of (non-convex/non-conc ave) quadratic programming problems. また,(非凸/非凸)二次計画問題の大きいクラスを最大化するためのアルゴリズムの使用例を示す。 0.68
2 2 0.85
英語(論文から抽出)日本語訳スコア
Figure 1: Left: (continuous) DR-submodular softmax extension. 図1:左:(連続)dr-submodular softmax拡張。 0.86
Middle: concave quadratic function. Right: sum of both. 中間:凸二次関数。 右: 両者の合計。 0.70
Related Work. The study of discrete submodular maximization has flourished in the last decade through far reaching applications in machine learning and and artificial intelligence including viral marketing [Kempe et al , 2003], dictionary learning [Krause and Cevher, 2010], sparse regression [Elenberg et al , 2016], neural network interoperability [Elenberg et al , 2017], crowd teaching [Singla et al , 2014], sequential decision making [Alieva et al , 2021], active learning [Wei et al , 2015], and data summarization [Mirzasoleiman et al , 2013]. 関連作品。 The study of discrete submodular maximization has flourished in the last decade through far reaching applications in machine learning and and artificial intelligence including viral marketing [Kempe et al , 2003], dictionary learning [Krause and Cevher, 2010], sparse regression [Elenberg et al , 2016], neural network interoperability [Elenberg et al , 2017], crowd teaching [Singla et al , 2014], sequential decision making [Alieva et al , 2021], active learning [Wei et al , 2015], and data summarization [Mirzasoleiman et al , 2013]. 0.71
We refer the interested reader to a recent survey by Tohidi et al [2020] and the references therein. 興味ある読者は、Tohidi et al [2020] による最近の調査とその参照を参照する。 0.76
Recently, Bian et al [2017b] proposed an extension of discrete submodular functions to the continuous domains that can be of use in machine learning applications. 最近、bian et al [2017b] は、機械学習アプリケーションで使用可能な連続ドメインへの離散部分モジュラ関数の拡張を提案した。 0.73
Notably, this class of (non-convex/non-conc ave) functions, so called continuous DR-submodular, contains the continuous multilinear extension of discrete submodular functions Călinescu et al [2011] as a special case. 特に、この(非凸/非凸)函数のクラスは、いわゆる連続 dr-サブモジュラーであり、離散部分モジュラー函数の連続的多重線型拡大 c linescu et al [2011] を特別な場合として含む。 0.65
Continuous DR-submodular functions can reliably model revenue maximization [Bian et al , 2017b], robust budget allocation [Staib and Jegelka, 2017], experimental design [Chen et al , 2018], MAP inference for DPPs [Gillenwater et al , 2012, Hassani et al , 2020b], energy allocation [Wilder, 2018a], classes of zero-sum games [Wilder, 2018b], online welfare maximization and online task assignment [Sadeghi et al , 2020], as well as many other settings of interest. 連続DR-サブモジュラー関数は、収益の最大化(Bian et al , 2017b)、堅牢な予算配分(Staib and Jegelka, 2017)、実験設計(Chen et al , 2018)、DPPのMAP推論(Gillenwater et al , 2012Hassani et al , 2020b)、エネルギー配分(Wilder, 2018a)、ゼロサムゲームのクラス(Wilder, 2018b)、オンライン福祉の最大化とオンラインタスク割り当て(Sadeghi et al , 2020)、その他多くの関心の設定を確実にモデル化することができる。 0.76
The research on maximizing continuous DR-submodular functions in the last few years has established strong theoretical results in different optimization settings including unconstrained [Niazadeh et al , 2018, Bian et al , 2019], stochastic Mokhtari et al [2018a], Hassani et al [2017], online [Chen et al , 2018, Zhang et al , 2019, Sadeghi and Fazel, 2019, Raut et al , 2021], and parallel models of computation [Chen et al , 2019a, Mokhtari et al , 2018b, Xie et al , 2019, Ene and Nguyen, 2019]. 過去数年間における連続的なdr-submodular関数の最大化に関する研究は、unconstrained [niazadeh et al , 2018, bian et al , 2019], stochastic mokhtari et al [2018a], hassani et al [2017], online [chen et al , 2018, zhang et al , 2019, sadeghi and fazel, 2019, raut et al , 2021],parallel models of computation [chen et al , 2019a, mokhtari et al , 2018b, xie et al , 2019, ene and nguyen, 2019]を含む、さまざまな最適化設定で強力な理論的結果を確立した。 0.87
A different line of works study the maximization of discrete functions that can be represented as the sum of a non-negative monotone submodular function and a linear function. 異なる作品のラインは、非負の単調な部分モジュラー関数と線形関数の和として表現できる離散関数の最大化を研究する。 0.81
The ability to do so is useful in practice since the linear function can be viewed as a soft constraint, and it also has theoretical applications as is argued by the first work in this line [Sviridenko et al , 2017] (for example, the problem of maximization of a monotone submodular function with a bounded curvature can be reduced to the maximization of the sum of a monotone submodular function and a linear function). 線形関数はソフト制約と見なすことができ、また、この行の最初の仕事である(sviridenko et al , 2017](例えば、有界曲率を持つ単調部分モジュラー関数の最大化問題は、単調部分モジュラー関数と線型関数の和の最大化に還元できる)によって議論される理論的応用もあるので、実際、そのような能力は有用である。 0.70
In terms of the approximation guarantee, the algorithms suggested by Sviridenko et al [2017] were optimal. 近似保証に関しては、sviridenkoらによって提案されたアルゴリズムが最適であった。 0.77
However, more recent works improve over the time complexities of these algorithms [Feldman, 2021, Harshaw et al , 2019, Ene et al , 2020], generalize them to weakly-submodular functions [Harshaw et al , 2019], and adapt them to other computational models such as the data stream and MapReduce models [Kazemi et al , 2020b, Ene et al , 2020]. しかし、より最近の研究は、これらのアルゴリズムの時間的複雑さ(feldman, 2021, harshaw et al , 2019, ene et al , 2020]を改善し、弱劣モジュラ関数(harshaw et al , 2019)に一般化し、データストリームやmapreduceモデル(kazemi et al , 2020b, ene et al , 2020)のような他の計算モデルに適応する。 0.84
3 3 0.85
英語(論文から抽出)日本語訳スコア
2 Setting and Notation Let us now formally define the setting we consider. 2 設定と表記 では、検討する設定を正式に定義しましょう。 0.61
Fix a subset X of Rn of the form(cid:81)n Rn の形式(cid:81)n の部分集合 X を固定する 0.80
i=1 Xi, where Xi is a closed range in R. Intuitively, a function G : X → R is called (continuous) DR-submodular if it exhibits diminishing returns in the sense that given a vector x ∈ X , the increase in G(x) obtained by increasing xi (for any i ∈ [n]) by ε > 0 is negatively correlated with the original values of the coordinates of x. 直観的には、函数 G : X → R は、ベクトル x ∈ X が与えられたときに xi (任意の i ∈ [n] に対して) を ε > 0 で増加させることによって得られる G(x) の増加が x の座標の原値と負の相関を持つという意味で、(連続) DR-部分モジュラー (continuous) と呼ばれる。 0.79
This intuition is captured by the following definition. この直観は以下の定義で捉えられる。 0.68
In this definition ei denotes the standard basis vector in the ith direction. この定義において ei は i 方向の標準基底ベクトルを表す。 0.82
Definition 2.1 (DR-submodular function). 定義 2.1 (DR-submodular function)。 0.66
A function G : X → R is DR-submodular if for every two vectors a, b ∈ X , positive value k and coordinate i ∈ [n] we have G(a + kei) − G(a) ≥ G(b + kei) − G(b) 函数 G : X → R が DR-部分モジュラーであるとは、すべての二つのベクトル a, b ∈ X , 正の値 k と座標 i ∈ [n] に対して G(a + kei) − G(a) ≥ G(b + kei) − G(b) が成り立つことである。 0.87
whenever a ≤ b and a + kei, b + kei ∈ X .1 a ≤ b と a + kei のとき、b + kei ∈ x .1 0.88
It is well known that when G is continuously differentiable, then it is DR-submodular if and only if ∇G(a) ≥ ∇G(b) for every two vectors a, b ∈ X that obey a ≤ b. G が連続微分可能であれば、それは DR-部分モジュラーであることと、a ≤ b に従うすべての 2 つのベクトル a, b ∈ X に対して sG(a) ≥ sG(b) であることは知られている。 0.78
And when G is a twice differentiable function, it is DR-submodular if and only if its hessian is non-positive at every vector x ∈ X . そして、G が 2 つの微分可能関数であるとき、DR-部分モジュラー (DR-submodular) は、そのヘシアンがすべてのベクトル x ∈ X において非正であるときに限る。
訳抜け防止モード: そして、G が 2 つの微分可能関数であるとき、それは DR - submodular if そして、そのヘッセンがすべてのベクトル x ∈ X において非正であるときのみである。
0.62
Furthermore, for the sake of simplicity we assume in this work that X = [0, 1]n. This assumption is without loss of generality because the natural mapping from X to [0, 1]n preserves all our results. X = [0, 1]n. この仮定は、X から [0, 1]n への自然な写像が全ての結果を保存するので、一般性を失うことはない。 0.62
We are interested in the problem of finding the point in some convex body P ⊆ [0, 1]n that maximizes a given function F : [0, 1]n → R that can be expressed as the sum of a DR-submodular function G : [0, 1]n → R and a concave function C : [0, 1]n → R. To get meaningful results for this problem, we need to make some assumptions. 与えられた函数 F : [0, 1]n → R を DR-部分モジュラー函数 G : [0, 1]n → R と凹函数 C : [0, 1]n → R の和として表すことができるような函数 F : [0, 1]n → R を最大化する凸体の点を見つける問題に興味がある。
訳抜け防止モード: 所与の函数 F : [ 0, 1]n → R を DR -部分モジュラー函数 G : [ 0, 1]n → R の和として表すことができるような、ある凸体 P > [ 0, 1]n における点を見つける問題に興味がある。 そして、凹函数 C : [ 0, 1]n → R である。 この問題の有意義な結果を得るために。 いくつかの仮定が必要です
0.78
Here we describe three basic assumptions that we make throughout the paper. ここでは3つの基本的な仮定について述べる。 0.68
The quality of the results that we obtain improves if additional assumptions are made, as is described in Section 3. 第3節で述べたように、追加の仮定が成立すれば、得られた結果の品質が向上する。 0.70
Our first basic assumption is that G is non-negative. 最初の基本的な仮定は、G は非負であるということである。 0.50
This assumption is necessary since we obtain multiplicative approximation guarantees with respect to G, and such guarantees do not make sense when G is allowed to take negative values.2 Our second basic assumption is that P is solvable, i.e., that one can efficiently optimize linear functions subject to it. この仮定は G に関する乗法近似を保証するため必要であり、そのような保証は G が負の値を取ることを許されたときに意味をなさない。
訳抜け防止モード: この仮定は、G に関する乗法近似を保証するため必要である。 このような保証は、Gが負の値を取ることを許されたときに意味がない。 P は可解であり、すなわち、その対象となる線型函数を効率的に最適化することができる。
0.73
Intuitively, this assumption makes sense because one should not expect to be able to optimize a complex function such as F subject to P if one cannot optimize linear functions subject to it (nevertheless, it is possible to adapt our algorithms to obtain some guarantee even when linear functions can only be approximately optimized subject to P ). 直観的には、この仮定は、P を対象とする F のような複素函数を最適化できないと期待できないから理にかなっている(ただし、P を対象とする線型函数をほぼ最適化できるだけであっても、アルゴリズムを適応させることは可能である)。 0.76
Our final basic assumption is that both functions G and C are L-smooth, which means that they are differentiable, and moreover, their gradients are L-Lipschitz, i.e., 我々の最終的な基本的な仮定は、G と C はともに L-滑らかであり、それらは微分可能であり、さらにその勾配は L-Lipschitz である。 0.72
(cid:107)∇f (a) − ∇f (b)(cid:107)2 ≤ L(cid:107)a − b(cid:107)2 ∀ a, b ∈ [0, 1]n . (cid:107)\f (a) − sf (b)(cid:107)2 ≤ l(cid:107)a − b(cid:107)2 は a, b ∈ [0, 1]n である。 0.87
We conclude this section by introducing some additional notation that we need. 我々は、必要な追加の表記法を導入することで、この節を締めくくります。 0.53
We denote by o an arbitrary optimal solution for the problem described above, and define D = maxx∈P (cid:107)x(cid:107)2 . 上記の問題に対する任意の最適解を o で示し、d = maxxjavap (cid:107)x(cid:107)2 と定義する。 0.83
Additionally, given two vectors a, b ∈ Rn, we denote by a (cid:12) b their coordinate-wise multiplication, and by (cid:104)a, b(cid:105) their standard Euclidean inner product. さらに、2つのベクトル a, b ∈ Rn が与えられたとき、座標次乗法 a (cid:12) b と標準ユークリッド内積 (cid:104)a, b(cid:105) で表す。 0.82
1Throughout the paper, inequalities between vectors should be understood as holding coordinate-wise. 1 論文では,ベクトル間の不等式を座標的に考える必要がある。 0.62
2We note that almost all the literature on submodular maximization of both discrete and continuous functions 2我々は、離散関数と連続関数の亜モジュラー最大化に関するほぼ全ての文献に注意する。 0.64
assumes non-negativity for the same reason. 同じ理由で非否定性を仮定する。 0.62
4 4 0.85
英語(論文から抽出)日本語訳スコア
Table 1: Summary of algorithms, settings, and guarantees (“non-neg.” is a shorthand for “nonnegative”). 表1:アルゴリズム、設定、保証のまとめ("non-neg."は"non negative"の略)。 0.60
All of the conditions stated in the table are in addition to the continuity and smoothness of G and C, and the convexity of P . 表に述べられている全ての条件は、g と c の連続性と滑らかさに加えて、p の凸性である。 0.74
α and β are the constants preceding G(o) and C(o) respectively in the lower bound on the output of the algorithm. α と β はそれぞれアルゴリズムの出力の下位境界における G(o) と C(o) の前の定数である。 0.84
Algorithm (Section) Greedy Frank-Wolfe Measured Greedy Frank-Wolfe Measured Greedy Frank-Wolfe Measured Greedy Frank-Wolfe Measured Greedy Frank-Wolfe Gradient Combining Frank-Wolfe Non-Oblivious Frank-Wolfe アルゴリズム (セクション)greedy frank-wolfe測定 greedy frank-wolfe測定 greedy frank-wolfe測定 greedy frank-wolfe測定 greedy frank-wolfe測定 greedy frank-wolfegradient using frank-wolfe non-oblivious frank-wolfe 0.48
G C P α β monotone G C P α β モノトーン 0.79
monotone & non-neg. monotone & non-neg 0.89
& non-neg. monotone & non-neg. と非neg。 monotone & non-neg 0.78
non-neg. non-neg. monotone & non-neg. ない。 ない。 monotone & non-neg 0.68
monotone monotone & non-neg. モノトーン monotone & non-neg 0.70
& non-neg. general down-closed と非neg。 将軍 down‐closed 0.58
down-closed down‐closed 0.56
down-closed down‐closed 0.56
non-neg. non-neg. down-closed ない。 ない。 down‐closed 0.57
monotone & non-neg. monotone & non-neg 0.89
monotone & non-neg. monotone & non-neg 0.89
General non-neg. General General 将軍 ない。 将軍 将軍 0.56
1 − 1/e 1 − 1/e 1 − 1/e 1 − 1/e 0.78
1/e 1 − 1/e 1/e 1 − 1/e 0.69
1/e 1/2 − ε 1/e 1/2 − ε 0.69
1 − 1/e 1/e 1 − 1/e 1/e 0.69
1 − 1/e 1 − 1/e 1 − 1/e 1 − 1/e 0.78
1/e 1 1 − 1/e − ε 1/e 1 1 − 1/e − ε 0.77
1 − ε 3 Main Algorithms and Results In this section we present our (first-order) algorithms for solving the problem described in Section 2. 1 − ε 3 主要なアルゴリズムと本節では,本項で述べる問題を解くための(一階の)アルゴリズムを提案する。 0.81
In general, these algorithms are all Frank-Wolfe type algorithms, but they differ in the exact linear function which is maximized in each iteration (step 1 of the while/for loop), and in the formula used to update the solution (step 2 of the while/for loop). 一般に、これらのアルゴリズムはすべてフランク・ウルフ型アルゴリズムであるが、各反復で最大化される完全線形関数( while/forループのステップ1)と、解の更新に用いられる公式( while/forループのステップ2)では異なる。 0.85
As mentioned previously, we assume everywhere that G is a non-negative L-smooth DR-submodular function, C is an L-smooth concave function, and P is a solvable convex body. 前述したように、G が非負の L-滑らかな DR-部分モジュラ函数、C が L-滑らかな凹函数、P が可解凸体であるとする。 0.68
Some of our algorithms require additional non-negativity and/or monotonicity assumptions on the functions G and C, and occasionally they also require a downward closed assumption on P . 我々のアルゴリズムのいくつかは、函数 G と C に対する追加の非負性および/または単調性仮定を必要とし、時には P 上の下向きの閉仮定も必要である。 0.58
A summary of which settings each algorithm is applicable to can be found in Table 1. 各アルゴリズムが適用可能な設定の要約は、Table 1で見ることができる。 0.77
Each algorithm listed in the table outputs a point x ∈ P which is guaranteed to obey F (x) ≥ α · G(o) + β · C(o) − E for the constants α and β given in Table 1 and some error term E. 表に列挙された各アルゴリズムは点 x ∈ P を出力し、表 1 で与えられた定数 α と β に対して F (x) ≥ α · G(o) + β · C(o) − E に従うことが保証される。 0.86
3.1 Greedy Frank-Wolfe Algorithm In this section we assume that both G and C are monotone and non-negative functions (in addition to their other properties). 3.1 greedy frank-wolfe アルゴリズム この節では、g と c は(他の性質に加えて)単調かつ非負の関数であると仮定する。 0.74
Given this assumption, we analyze the guarantee of the greedy Frank-Wolfe variant appearing as Algorithm 1. この仮定を前提に,アルゴリズム1として現れる欲望のあるフランク・ウルフ変異の保証を解析する。 0.67
This algorithm is related to the Continuous Greedy algorithm for discrete objective functions due to Călinescu et al [2011], and it gets a quality control parameter ε ∈ (0, 1). このアルゴリズムは、C'linescu et al [2011] による離散目的関数に対する連続グリーディアルゴリズムと関連しており、品質制御パラメータ ε ∈ (0, 1) を得る。 0.84
We assume in the algorithm that ε−1 is an integer. ε−1 が整数であると仮定する。 0.59
This assumption is without loss of generality because, if ε violates the assumption, then it can be replaced with a value from the range この仮定は一般性を失うことはない、なぜなら ε が仮定に違反しているなら、その範囲の値に置き換えることができるからである。 0.66
5 5 0.85
英語(論文から抽出)日本語訳スコア
[ε/2, ε] that obeys it. [ε/2,ε]それに従う。 0.79
Algorithm 1: Greedy Frank-Wolfe (ε) アルゴリズム1:Greedy Frank-Wolfe (ε) 0.86
(cid:10)∇F (y(t)), x(cid:11) (cid:10)→F(y(t)),x(cid:11) 0.92
Let t ← 0 and y(t) ← ¯0 while t < 1 do t < 1 であるなら、t を 0 と y(t) と y(t) を 0 とする。 0.54
s(t) ← arg maxx∈P y(t+ε) ← y(t) + ε · s(t) t ← t + ε end while return y(1) s(t) > arg maxx⋅P y(t+ε) > y(t) + ε · s(t) t > t + ε end while return y(1) 0.87
One can observe that the output y(1) of Algorithm 1 is within the convex body P because it is a convex combination of the vectors s(0), s(ε), s(2ε), . アルゴリズム1の出力 y(1) はベクトル s(0), s(ε), s(2ε), の凸結合であるため凸体 P 内にある。
訳抜け防止モード: それを観察できる アルゴリズム1の出力y(1 )は凸体P内にある ベクトル s(0) の凸結合であるからである。 s(ε ) , s(2ε ) , 。
0.75
. . , s1−ε, which are all vectors in P . . . s1-ε は P のすべてのベクトルである。 0.82
Let us now analyze the value of the output of Algorithm 1. では、アルゴリズム1の出力値を分析する。 0.60
The next lemma is the first step towards this goal. 次の補題はこのゴールへの第一歩です。 0.74
It provides a lower bounds on the increase in the value of y(t) as a function of t. Lemma 3.1. これは、t. Lemma 3.1 の関数として y(t) の値の増加に関する下界を与える。 0.74
For every 0 ≤ i < ε−1, F (y(ε(i+1))) − F (y(εi)) ≥ ε · [F (o) − F (y(εi))] − ε2LD2. すべての 0 ≤ i < ε−1 に対して、F (y(ε(i+1))) − F (y(εi)) ≥ ε · [F(o) − F (y(εi))] − ε2LD2 である。 0.89
Proof. Observe that F (y(ε(i+1))) − F (y(εi)) = F (y(εi) + ε · s(εi)) − F (y(εi)) = 証明。 観察する F (y(ε(i+1))) − F (y(εi)) = F (y(εi) + ε · s(εi)) − F (y(εi)) = 0.75
(cid:68) (cid:90) ε (cid:68) (cid:68) (cid:90)ε(cid:68) 0.78
0 (cid:69) (cid:69) − ε2LD2 ≥(cid:68) 0 (cid:69) (cid:69) − ε2LD2 ≥(cid:68) 0.79
(cid:90) ε (cid:110)(cid:68) (cid:90)ε(cid:110)(cid:68) 0.75
0 (cid:90) ε 0 (cid:90)ε 0.82
0 dF (y(εi) + z · s(εi)) 0 dF(y(εi) + z · s(εi)) 0.90
dz (cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:69) − 2rLD2(cid:111) dz (cid:12)(cid:12)(cid :12)(cid:12)z=r(cid:69) − 2rLD2(cid:111) 0.76
dr dr where the last inequality follows since s(εi) is the maximizer found by Algorithm 1. 博士 博士 s(εi) がアルゴリズム 1 で見つかる最大値であることから、最後の不等式が従う。 0.67
Therefore, to = = s(εi),∇F (y(εi)) そのため = = s(εi)、eF(y(εi)) 0.80
εs(εi),∇F (y(εi)) εs(εi), εF(y(εi)) 0.94
s(εi),∇F (y(εi) + r · s(εi)) s(εi) , f (y(εi) + r · s(εi)) 0.95
dr ≥ εo,∇F (y(εi)) dr ≥ εo,\f (y(εi)) 0.97
(cid:69) − ε2LD2 . (cid:69) − ε2LD2。 0.61
prove the lemma it only remains to show that(cid:10)o,∇F (y(εi))(cid:11) ≥ F (o) − F (y(εi)). 補題を証明すれば、 (cid:10)o,\F (y(εi))(cid:11) ≥ F (o) − F (y(εi)) が成り立つ。 0.83
(cid:68) (cid:69) ≤ C(y(εi)) + (cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:69) (cid:68) (cid:69) ≤ c(y(εi)) + (cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:69) 0.76
Since C is concave and monotone, C(o) ≤ C(o ∨ y(εi)) ≤ C(y(εi)) + C は凹凸で単調であるため、C(o) ≤ C(o ) y(εi)) ≤ C(y(εi)) + 0.90
Similarly, since G is DR-submodular and monotone, 同様に、g は dr-submodular かつ monotone である。 0.70
G(o) ≤ G(o ∨ y(εi)) = G(y(εi)) + G(o) ≤ G(o ) y(εi)) = G(y(εi)) + 0.92
dG(y(εi) + z · (o ∨ y(εi) − y(εi))) dG(y(εi) + z · (o ) y(εi) − y(εi)) 0.91
o ∨ y(εi) − y(εi),∇C(y(εi)) o > y(εi) − y(εi) ,\C(y(εi)) 0.87
o ∨ y(εi) − y(εi),∇G(y(εi) + r · (o ∨ y(εi) − y(εi))) o > y(εi) − y(εi) − y(εi) = G(y(εi) + r · (o > y(εi) − y(εi)) 0.83
(cid:90) 1 (cid:68) (cid:90)1 (cid:68) 0.79
dz 0 dr (cid:68) dz 0 博士 (cid:68) 0.79
(cid:90) 1 (cid:68) (cid:90)1(cid:68) 0.74
0 = G(y(εi)) + ≤ G(y(εi)) + 0 = G(y(εi)) + ≤ G(y(εi)) + 0.89
(cid:69) ≤ G(y(εi)) + (cid:69) ≤ G(y(εi)) + 0.96
(cid:68) dr o,∇G(y(εi)) (cid:68) dr o, = G(y(εi)) 0.84
(cid:69) o ∨ y(εi) − y(εi),∇G(y(εi)) (cid:69) o > y(εi) − y(εi) ,\G(y(εi)) 0.83
Adding the last two inequalities and rearranging gives the inequality(cid:10)o, ∇F (y(εi))(cid:11) ≥ F (o)−F (y(εi)) The corollary below follows by showing (via induction) that the inequality F (y(εi)) ≥ (cid:2)1 − (1 − ε)i(cid:3) · F (o) − i · ε2LD2 holds for every integer 0 ≤ i ≤ ε−1, and then plugging in i = ε−1. 最後の2つの不等式を加えて再配置すると、不等式(cid:10)o, εF (y(εi))(cid:11) ≥ F (o)−F (y(εi)) 下記の法則は、不等式 F (y(εi)) ≥ (cid:2)1 − (1 − ε)i(cid:3) · F (o) − i · ε2LD2 がすべての整数 0 ≤ i ≤ ε−1 に対して成り立つことを示す。 0.85
The that we wanted to prove. 証明したかったのです 0.37
. inductive step is proven using Lemma 3.1. . 帰納段階は Lemma 3.1 を用いて証明される。 0.68
(cid:69) o,∇C(y(εi)) (cid:69) o,c(y(εi)) 0.82
. 6 . 6 0.85
英語(論文から抽出)日本語訳スコア
Corollary 3.2. F (y(1)) ≥ (1 − e−1) · F (o) − O(εLD2). 登録番号3.2。 F (y(1)) ≥ (1 − e−1) · F (o) − O(εLD2)。 0.64
Proof. We prove by induction that for every integer 0 ≤ i ≤ ε−1 we have 証明。 すべての整数 0 ≤ i ≤ ε−1 に対して、我々は帰納法によって証明する。
訳抜け防止モード: 証明。 誘導によって証明します すべての整数 0 ≤ i ≤ ε−1 に対して
0.70
F (y(εi)) ≥(cid:104) f(y(εi)) ≥(cid:104) 0.91
1 − (1 − ε)i(cid:105) · F (o) − i · ε2LD2 . 1 − (1 − ε)i (cid:105) · F (o) − i · ε2LD2 である。 0.82
(1) One can note that the corollary follows from this inequality by plugging i = ε−1 since (1−ε)ε−1 ≤ e−1. (1) i = ε−1 をプラグすると、(1−ε)ε−1 ≤ e−1 となる。 0.76
For i = 0, Inequality (1) follows from the non-negativity of F (which follows from the nonnegativity of G and C). i = 0 に対して、不等式 (1) は F の非負性から従う(これは G と C の非負性から従う)。 0.68
Next, let us prove Inequality (1) for 1 ≤ i ≤ ε−1 assuming it holds for i − 1. 次に、1 ≤ i ≤ ε−1 に対して不等式 (1) が i − 1 に対して成り立つことを証明しよう。 0.76
By Lemma 3.1, Lemma 3.1 による。 0.63
F (y(εi)) ≥ F (y(ε(i−1))) + ε · [F (o) − F (y(ε(i−1)))] − ε2LD2 F(y(εi)) ≥ F(y(ε(i−1)) + ε · [F(o) − F(y(ε(i−1)))] − ε2LD2 0.92
= (1 − ε) · F (y(ε(i−1))) + ε · F (o) − ε2LD2 = (1 − ε) · F (y(ε(i−1))) + ε · F (o) − ε2LD2 0.99
≥ (1 − ε) ·(cid:110)(cid:104) ≥(cid:104) 1 − (1 − ε)i(cid:105) · F (o) − i · ε2LD2 , ≥ (1 − ε) ·(cid:110)(cid:104) ≥(cid:104) 1 − (1 − ε)i(cid:105) · f (o) − i · ε2ld2 , 0.93
1 − (1 − ε)i−1(cid:105) · F (o) − (i − 1) · ε2LD2(cid:111) 1 − (1 − ε)i−1(cid:105) · F (o) − (i − 1) · ε2LD2(cid:111) 0.89
+ ε · F (o) − ε2LD2 + ε · F (o) − ε2LD2 0.90
where the second inequality holds due to the induction hypothesis. 2番目の不平等は 帰納仮説によるものです 0.61
We are now ready to summarize the properties of Algorithm 1 in a theorem. 現在、アルゴリズム1の特性を定理で要約する準備ができています。 0.67
Theorem 3.3. Let S be the time it takes to find a point in P maximizing a given liner function, then Algorithm 1 runs in O(ε−1(n + S)) time, makes O(1/ε) calls to the gradient oracle, and outputs a vector y such that F (y) ≥ (1 − 1/e) · F (o) − O(εLD2). 定理3.3。 S を与えられた線形関数の最大化に要する時間とし、アルゴリズム 1 は O(ε−1(n + S)) 時間で実行し、O(1/ε) を勾配オラクルに呼び出し、F (y) ≥ (1 − 1/e) · F (o) − O(εLD2) となるようなベクトル y を出力する。 0.70
Proof. The output guarantee of Theorem 3.3 follows directly from Corollary 3.2. 証明。 Theorem 3.3の出力保証は、Corollary 3.2から直接従う。 0.65
The time and oracle complexity follows by observing that the algorithm’s while loop makes ε−1 iterations, and each iteration requires O(n + S) time, in addition to making a single call to the gradient oracle. 時間とオラクルの複雑さは、アルゴリズムの while loop が ε−1 イテレーションを行い、各イテレーションには o(n + s) の時間が必要であり、勾配 oracle への1回の呼び出しも必要であるということを観察することで従う。 0.71
3.2 Measured Greedy Frank-Wolfe Algorithm In this section we assume that P is a down-closed body (in addition to being convex) and that G and C are both non-negative. 3.2 グリーディ・フランク=ウルフアルゴリズム この節では、P は(凸性に加えて)閉体であり、G と C はともに負でないと仮定する。 0.68
Given these assumptions, we analyze the guarantee of the variant of Frank-Wolfe appearing as Algorithm 2, which is motivated by the Measured Continuous Greedy algorithm for discrete objective functions due to Feldman et al [2011]. これらの仮定を前提に, アルゴリズム2として現れるフランク・ウルフの変種を, フェルドマンらによる離散目的関数の連続的グレディアルゴリズムによって実現し, 検証を行った。 0.71
We again have a quality control parameter ε ∈ (0, 1), and assume (without loss of generality) that ε−1 is an integer. 再び品質制御パラメータ ε ∈ (0, 1) を持ち、ε−1 が整数であると仮定する(一般性を失うことなく)。 0.84
Algorithm 2: Measured Greedy Frank-Wolfe (ε) アルゴリズム2:Greedy Frank-Wolfe(ε)の測定 0.75
Let t ← 0 and y(t) ← ¯0 while t < 1 do t < 1 であるなら、t を 0 と y(t) と y(t) を 0 とする。 0.54
s(t) ← arg maxx∈P(cid:104)(¯1 − y(t)) (cid:12) ∇F (y(t)), x(cid:105) y(t+ε) ← y(t) + ε · (¯1 − y(t)) (cid:12) s(t) t ← t + ε end while return y(1) s(t) = s(t) = s(t) = s(t) = s(t) = s(t) = s(t) + s(t) = y(t) + s(t) = y(t) + s(t) = y(t) + s(t) + t(t) + ε end while return y(1) while return s(t) t t t t t + ε end
訳抜け防止モード: s(t ) が s(t ) で、arg maxxhtmlp(cid:104)( ) ( cid:12 ) (y(t ) ) ) である。 x(cid:105 ) y(t+ε ) は y(t ) + ε · ( ε1 − y(t ) ) ( cid:12 ) s(t ) t である。 + ε 終了し、y(1 ) を返す
0.81
We begin the analysis of Algorithm 2 by bounding the range of the entries of the vectors y(t), 我々は、ベクトル y(t) のエントリの範囲を限定することで、アルゴリズム2の分析を開始する。 0.83
which is proven by induction. 誘導によって証明されます 0.58
7 7 0.85
英語(論文から抽出)日本語訳スコア
Lemma 3.4. For every two integers 0 ≤ i ≤ ε−1 and 1 ≤ j ≤ n, 0 ≤ y(εi) j = 0 by the Proof. レマ3.4。 すべての二つの整数 0 ≤ i ≤ ε−1 と 1 ≤ j ≤ n に対して、証明によって 0 ≤ y(εi) j = 0 となる。
訳抜け防止モード: レマ3.4。 2つの整数 0 ≤ i ≤ ε−1 と 1 ≤ j ≤ n に対して。 0 ≤ y(εi ) j = 0 である。
0.74
We prove the lemma by induction on i. i での帰納による補題の証明を行う。 0.52
For i = 0 the lemma is trivial since y(0) initialization of y(0). i = 0 に対して、補題は y(0) が y(0) の初期化であるため自明である。 0.75
Assume now that the lemma holds for i− 1, and let us prove it for 1 ≤ i ≤ ε−1. ここで、補題が i− 1 に対して成り立つと仮定し、1 ≤ i ≤ ε−1 に対して証明する。 0.71
Observe that j ≤ 1 − (1 − ε)i ≤ 1. 観察する j ≤ 1 − (1 − ε)i ≤ 1 である。 0.81
j = y(ε(i−1)) y(εi) j = y(ε(i−1)) y(εi) 0.97
j + ε · (1 − y(ε(i−1)) j + ε · (1 − y(ε(i−1)) 0.91
j ) · s(εi) j ) · s(εi) 0.91
j ≥ y(ε(i−1)) j ≥ y(ε(i−1)) 0.98
j ≥ 0 , where the first inequality holds since y(ε(i−1)) s(εi) ∈ P . j ≥ 0 , 第一の不等式は y(ε(i−1)) s(εi) ∈ p から成り立つ。 0.81
Similarly, j ≤ 1 by the induction hypothesis and s(εi) 同様に j 帰納仮説とs(εi)による ≤ 1 0.79
j ≥ 0 since j = y(ε(i−1)) y(εi) j ≥ 0 以降 j = y(ε(i−1)) y(εi) 0.89
j + ε · (1 − y(ε(i−1)) j + ε · (1 − y(ε(i−1)) 0.91
j ) · s(εi) j ) · s(εi) 0.91
j ≤ y(ε(i−1)) j ≤ y(ε(i−1)) 0.98
j + ε · (1 − y(ε(i−1)) j + ε · (1 − y(ε(i−1)) 0.91
) j = ε + (1 − ε) · y(ε(i−1)) ) j = ε + (1 − ε) · y(ε(i−1)) 0.88
j ≤ ε + (1 − ε) · [1 − (1 − ε)i−1] = 1 − (1 − ε)i , j ≤ 1 since s(εi) ∈ P , and the second inequality holds by j ≤ ε + (1 − ε) · [1 − (1 − ε)i−1] = 1 − (1 − ε)i , j ≤ 1 since s(εi) ∈ P , そして第二の不等式は成り立つ。 0.88
where the first inequality holds because s(εi) the induction hypothesis. 第一の不等式が成り立つのは s(εi) が帰納仮説であるからである。 0.48
i=1 ε · (¯1 − yε(i−1)) (cid:12) s(εi) ≤ ε ·(cid:80)ε−1 i=1 ε · ( 1 − yε(i−1)) (cid:12) s(εi) ≤ ε ·(cid:80)ε−1 0.80
output of Algorithm 2 is y(1) =(cid:80)ε−1 follows due to Lemma 3.4 and the fact that s(εi) (as a vector in P ) is non-negative. アルゴリズム2の出力は y(1) =(cid:80)ε−1 であり、補題 3.4 と s(εi) が非負であることから従う。 0.73
Since ε·(cid:80)ε−1 ε·(cid:80)ε−1 0.70
Using the last lemma, we can see why the output of Algorithm 2 must be in P . 最後の補題を用いて、アルゴリズム2の出力がなぜ P でなければならないのかが分かる。 0.75
Recall that the i=1 s(εi), where the inequality i=1 s(εi) is a convex combination of points in P , it also belongs to P . 不等式 i=1 s(εi) が P 内の点の凸結合であるような i=1 s(εi) もまた P に属する。 0.80
Since the vector y(1) is coordinate-wise dominated by this combination, the down-closeness of P implies y(1) ∈ P . ベクトル y(1) はこの組合せによって座標的に支配されるので、P のダウンクロース性は y(1) ∈ P を意味する。 0.70
Our next objective is to prove an approximation guarantee for Algorithm 2. 次の目的はアルゴリズム2の近似保証を証明することである。 0.76
Towards this goal, let us define, for every function H, the expression M (H, i) to be 1 when H is monotone and (1 − ε)i when H is non-monotone. この目的に向けて、すべての函数 H に対して、M (H, i) は H が単調で (1 − ε)i が非単調であるときに 1 となるように定義する。 0.81
Using this definition, we can state the following lemma and corollary, which are counterparts of Lemma 3.1 and Corollary 3.2 from Section 3.1. この定義を用いることで、次の補題と、第3.1節のLemma 3.1 と第3.2節の対となる用語を記述できる。
訳抜け防止モード: この定義を使って 下記の補題と補題を述べます 第3.1節から lemma 3.1 と corollary 3.2 に対応する。
0.74
Lemma 3.5. For every integer 0 ≤ i < ε−1, F (y(ε(i+1))) − F (y(εi)) ≥ ε · {[M (G, i) · G(o) − G(y(εi))] + [M (C, i) · C(o) − C(y(εi))]} − ε2LD2. 3.5歳。 すべての整数 0 ≤ i < ε−1 に対して、F (y(ε(i+1)) − F (y(εi)) ≥ ε · {[M (G, i) · G(o) − G(y(εi))] + [M (C, i) · C(o) − C(y(εi))]} − ε2LD2 である。 0.72
Proof. Observe that F (y(ε(i+1))) − F (y(εi)) = F (y(εi) + ε · (¯1 − y(εi)) (cid:12) s(εi)) − F (y(εi)) 証明。 観察する F (y(ε(i+1)) − F (y(εi)) = F (y(εi) + ε · ( ε1 − y(εi)) (cid:12) s(εi)) − F (y(εi))) 0.76
0 (cid:90) ε (cid:90) ε (cid:90) ε (cid:68) 0 (cid:90)ε(cid:90)ε(cid:90)ε(cid:68) 0.79
0 0 = = ≥ = 0 0 = = ≥ = 0.85
(cid:68) (cid:110)(cid:68) (cid:68) (cid:110)(cid:68) 0.74
dF (y(εi) + z · (¯1 − y(εi)) (cid:12) s(εi)) dF (y(εi) + z · ( ε1 − y(εi)) (cid:12) s(εi)) 0.92
dz (¯1 − y(εi)) (cid:12) s(εi),∇F (y(εi) + r · (¯1 − y(t)) (cid:12) s(εi)) dz (1 − y(εi)) (cid:12) s(εi) , f (y(εi) + r · (1 − y(t)) (cid:12) s(εi)) 0.86
(cid:69) dr (cid:69) 博士 0.73
((¯1 − y(εi)) (cid:12) s(εi),∇F (y(εi)) ((1 − y(εi)) (cid:12) s(εi) , f (y(εi)) 0.84
ε(¯1 − y(εi)) (cid:12) s(εi),∇F (y(εi)) ε( ε1 − y(εi)) (cid:12) s(εi), f(y(εi)) 0.94
Furthermore, we also have (cid:68) さらに、私たちは (cid:68) 0.73
(¯1 − y(εi)) (cid:12) s(εi),∇F (y(εi)) (1 − y(εi)) (cid:12) s(εi) , f (y(εi)) 0.87
dr (cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:69) − 2rLD2(cid:111) (cid:69) − ε2LD2 . 博士 (cid:12)(cid:12)(cid :12)(cid:12)z=r(cid:69) − 2rLD2(cid:111) (cid:69) − ε2LD2。 0.65
dr (cid:69) 博士 (cid:69) 0.73
s(εi), (¯1 − y(εi)) (cid:12) ∇F (y(εi)) o, (¯1 − y(εi)) (cid:12) ∇F (y(εi)) s(εi), s(εi), (1 − y(εi)) (cid:12) (y(εi)) o, (1 − y(εi)) (cid:12) (y(εi))) 0.81
, (cid:69) , (cid:69) 0.82
(cid:69) (cid:68) ≥(cid:68) (cid:69) (cid:68)≥(cid:68) 0.85
= 8 = 8 0.85
英語(論文から抽出)日本語訳スコア
Similarly, since G is DR-submodular, 同様に、g は dr-submodular である。 0.63
G(o (cid:12) (¯1 − y(εi)) + y(εi)) − G(y(εi)) = G(o (cid:12) = y1 − y(εi)) + y(εi)) − G(y(εi)) 0.97
dG(y(εi) + z · o (cid:12) (¯1 − y(εi)) dG(y(εi) + z · o (cid:12) ( ε1 − y(εi)) 0.94
(cid:90) 1 0 (cid:90)1 0 0.82
(cid:69) − ε2LD2 . (cid:69) − ε2LD2。 0.61
(cid:69) (cid:69) (cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:69) (cid:69) (cid:12)(cid:12)(cid :12)(cid:12)z=r(cid:69) 0.78
. dr where the inequality holds since s(εi) is the maximizer found by Algorithm 2. . 博士 s(εi) がアルゴリズム2で見つかる最大値であることから不等式が成り立つ。 0.73
Combining the last two inequalities, we get 最後の2つの不等式を組み合わせると 0.67
Let us now find a lower bound on the expression (cid:10)o, (¯1 − y(εi)) (cid:12) ∇F (y(εi))(cid:11) in the above 上述の式 (cid:10)o, ( >1 − y(εi)) (cid:12) >F (y(εi))(cid:11) の下位境界を見つけましょう。 0.79
εo, (¯1 − y(εi)) (cid:12) ∇F (y(εi)) εo, ( ε1 − y(εi)) (cid:12) >F (y(εi)) 0.84
(2) inequality. Since C is concave, (2) 不平等 C は凹凸である。 0.72
F (y(ε(i+1))) − F (y(εi)) ≥(cid:68) C(o (cid:12) (¯1 − y(εi)) + y(εi)) − C(y(εi)) ≤(cid:68) (cid:68) F(y(ε(i+1)) − F(y(εi)) ≥(cid:68) C(o (cid:12) ( ~1 − y(εi)) + y(εi)) − C(y(εi)) ≤(cid:68) (cid:68) 0.97
o (cid:12) (¯1 − y(εi)),∇C(y(εi)) o, (¯1 − y(εi)) (cid:12) ∇C(y(εi)) o (cid:12) ( >1 − y(εi)), >C(y(εi)) o, ( >1 − y(εi)) (cid:12) >C(y(εi)) 0.86
= (cid:68) = (cid:68) 0.82
(cid:90) 1 ≤(cid:68) (cid:90) 1 ≤(cid:68) 0.88
= 0 dz (cid:69) ≤(cid:68) = 0 dz (cid:69) ≤(cid:68) 0.85
o (cid:12) (¯1 − y(εi)),∇G(y(εi) + r · o (cid:12) (¯1 − y(εi))) o (cid:12) ( >1 − y(εi)), >G(y(εi) + r · o (cid:12) ( >1 − y(εi)) 0.92
dr (cid:69) 博士 (cid:69) 0.73
Adding the last two inequalities provides the promised lower bound on(cid:10)o, (¯1 − y(t)) (cid:12) ∇F (y(εi))(cid:11). 最後の2つの不等式を加えると、(cid:10)o, ( >1 − y(t)) (cid:12) >F (y(εi))(cid:11) で約束される下界が得られる。
訳抜け防止モード: 最後の2つの不平等を追加する 約束の下限を (cid:10)o, ( >1 − y(t ) ) ( cid:12 ) (y(εi))(cid:11 )。
0.77
o (cid:12) (¯1 − y(εi)),∇G(y(εi)) o (cid:12) ( >1 − y(εi)), >G(y(εi)) 0.93
o, (¯1 − y(t)) (cid:12) ∇G(y(εi)) o, ( >1 − y(t)) (cid:12) >G(y(εi)) 0.86
. Plugging this lower bound into Inequality (2) yields . この下限を不等式にプラグする(2) 0.71
F (y(ε(i+1))) − F (y(εi)) ≥ ε · {[G(o (cid:12) (¯1 − y(εi)) + y(εi)) − G(y(εi))] f (y(ε(i+1))) − f (y(εi))) ≥ ε · {[g(o (cid:12) ( ]1 − y(εi)) + y(εi)) − g(y(εi))] 0.92
+ [C(o (cid:12) (¯1 − y(εi)) + y(εi)) − C(y(εi))]} − ε2LD2 . + [c(o (cid:12) ( ε1 − y(εi)) + y(εi)) − c(y(εi))]} − ε2ld2 である。 0.86
Given the last inequality, to prove the lemma it remains to show that G(o(cid:12) (¯1− y(εi)) + y(εi)) ≥ M (G, i) · G(o) and C(o (cid:12) (¯1 − y(εi)) + y(εi)) ≥ M (C, i) · C(o). 最後の不等式を仮定すると、G(o(cid:12) ( )1 − y(εi)) + y(εi)) ≥ M (G, i) · G(o) と C(o (cid:12) ( )1 − y(εi)) + y(εi)) ≥ M (C, i) · C(o) が成り立つ。 0.81
Since o (cid:12) (¯1 − y(εi)) + y(εi) ≥ o, these inequalities follow immediately when G and C are monotone, respectively. o (cid:12) ( ~1 − y(εi)) + y(εi) ≥ o であるため、これらの不等式はそれぞれ G と C が単調であるときにすぐに続く。 0.69
Therefore, we concentrate on proving these inequalities when G and C are non-monotone. したがって、G と C が非単調であるときにこれらの不等式を証明することに集中する。 0.49
Since C is concave, C(o (cid:12) (¯1 − y(εi)) + y(εi)) C は凹凸である。 c(o(cid:12) (1 − y(εi)) + y(εi)) 0.83
(cid:18) (cid:19) M (C, i) · o + (1 − M (C, i)) · ((1 − M (C, i)) · ¯1 − y(εi)) (cid:12) o + y(εi) (cid:18) ((1 − M (C, i)) · ¯1 − y(εi)) (cid:12) o + y(εi) (cid:18) (cid:19) M (C, i) · o + (1 − M (C, i)) · ((1 − M (C, i)) · \1 − y(εi)) (cid:12) o + y(εi) (cid:18) ((1 − M (C, i)) · y1 − y(εi)) (cid:12) o + y(εi)) 0.98
1 − M (C, i) 1 − M (C, i) 0.85
(cid:19) = C (cid:19) =C 0.79
≥ M (C, i) · C(o) + (1 − M (C, i)) · C ≥ M (C, i) · C(o) , ≥ M (C, i) · C(o) + (1 − M (C, i)) · C ≥ M (C, i) · C(o) , 0.85
1 − M (C, i) 1 − M (C, i) 0.85
where the second inequality follows from the non-negativity of C. We also note that 二つ目の不等式が c の非負性から従うとき。 0.61
((1 − M (C, i)) · ¯1 − y(εi)) (cid:12) o + y(εi) ((1 − m (c, i))··1 − y(εi))(cid:12) o + y(εi) 0.97
1 − M (C, i) 1 − M (C, i) 0.85
∈ [0, 1]n 9 ∈[0, 1]n 9 0.79
英語(論文から抽出)日本語訳スコア
since 0 ≤ y(εi) ≤ (1 − M (C, i)) · ¯1 by Lemma 3.4. 0 ≤ y(εi) ≤ (1 − m (c, i)) · 1 を補題 3.4 で表すからである。 0.82
Similarly, since G is DR-submodular, 同様に、g は dr-submodular である。 0.63
G(o (cid:12) (¯1 − y(εi)) + y(εi)) = G(o + (¯1 − o) (cid:12) y(εi)) g(o(cid:12) (cid:εi)) + y(εi)) = g(o + (s1 − o) (cid:12) y(εi)) 0.91
dG(o + z · (¯1 − o) (cid:12) y(εi)) dG(o + z · ( ~1 − o) (cid:12) y(εi)) 0.96
(cid:90) 1 (cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:90)1 (cid:12)(cid:12)(cid :12)z=r 0.82
dr = G(o) + 博士 = G(o) + 0.76
0 ≥ G(o) + (1 − M (G, i)) · 0 ≥ G(o) + (1 − M (G, i)) · 0.85
dz (cid:90) (1−M (G,i))−1 (cid:18) dz (cid:90) (1−m (g,i))−1 (cid:18) 0.82
0 = M (G, i) · G(o) + (1 − M (G, i)) · G ≥ M (G, i) · G(o) , 0 M (G, i) · G(o) + (1 − M (G, i)) · G ≥ M (G, i) · G(o) , 0.83
dG(o + z · (¯1 − o) (cid:12) y(εi)) dG(o + z · ( ~1 − o) (cid:12) y(εi)) 0.96
dz o + 1 1 − M (G, i) dz o + 1 1 − M (G, i) 0.85
· (¯1 − o) (cid:12) y(εi) · (1 − o) (cid:12) y(εi) 0.84
(cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:12)(cid:12)(cid :12)z=r 0.86
dr (cid:19) 博士 (cid:19) 0.73
where the second inequality follows from the non-negativity of G, and the first inequality holds since 第二の不等式が G の非負性から続くとき、それ以来最初の不等式が成り立つ。
訳抜け防止モード: 第二の不等式が G の非負性から従うとき、 最初の不平等は
0.78
o + 1 1 − M (G, i) o + 1 1 − M (G, i) 0.85
· (¯1 − o) (cid:12) y(εi) ∈ [0, 1]n · ( ~1 − o) (cid:12) y(εi) ∈ [0, 1]n 0.96
because 0 ≤ y(εi) ≤ (1 − M (C, i)) · ¯1 by Lemma 3.4. 0 ≤ y(εi) ≤ (1 − m (c, i)) · 1 を補題 3.4 で満たすからである。 0.81
Corollary 3.6. (cid:26)1 − e−1 if G is monotone 登録番号3.6。 (cid:26)1 − e−1 G が単調であれば 0.56
(cid:27) F (y(1))≥ (cid:27) F (y(1))≥ 0.72
· G(o) + e−1 ·g(o) + e−1 0.69
otherwise (cid:26)1 − e−1 if C is monotone そうでなければ (cid:26)1 − e−1 C が単調であれば 0.48
e−1 otherwise e−1 そうでなければ 0.46
(cid:27) · C(o) − O(εLD2) . (cid:27) ·C(o) − O(εLD2)。 0.81
Proof. For every function H, let S(H, i) be 1 − (1 − ε)i if H is monotone, and (εi) · (1 − ε)i−1 if H is non-monotone. 証明。 すべての函数 H に対して、S(H, i) を H が単調であれば 1 − (1 − ε)i とし、H が非単調であれば (εi) · (1 − ε)i−1 とする。 0.71
We prove by induction that for every integer 0 ≤ i ≤ ε−1 we have すべての整数 0 ≤ i ≤ ε−1 に対して、我々は帰納法によって証明する。
訳抜け防止モード: 誘導によって証明します すべての整数 0 ≤ i ≤ ε−1 に対して
0.78
F (y(εi)) ≥ S(G, i) · G(o) + S(C, i) · C(o) − i · ε2LD2 . F(y(εi)) ≥ S(G, i) · G(o) + S(C, i) · C(o) − i · ε2LD2 。 0.88
(3) One can note that the corollary follows from this inequality by plugging i = ε−1 since S(H, ε−1) = 1 − (1 − ε)ε−1 ≥ 1 − e−1 when H is monotone and S(H, ε−1) = (1 − ε)ε−1−1 ≥ e−1 when H is non-monotone. (3) S(H, ε−1) = 1 − (1 − ε)ε−1 ≥ 1 − e−1 は単調で、S(H, ε−1) = (1 − ε)ε−1 ≥ e−1 は非単調である。 0.69
For i = 0, Inequality (3) follows from the non-negativity of F since S(H, 0) = 0 both when H is monotone and non-monotone. i = 0 に対して、不等式 (3) は F の非負性から従う。なぜならば S(H, 0) = 0 は H が単調かつ非単調であるときの両方であるからである。
訳抜け防止モード: i = 0 の場合、不等式 (3 ) は S(H) から F の非負性から従う。 0 ) = 0 は H が単調で非単調なときの両方である。
0.70
Next, let us prove Inequality (3) for 1 ≤ i ≤ ε−1 assuming it holds for i − 1. 次に、1 ≤ i ≤ ε−1 に対して不等式(3) が i − 1 に対して成り立つことを仮定して証明する。 0.68
We note that (1 − ε) · S(H, i − 1) + ε · M (H, i − 1) = S(H, i). 1 − ε) · S(H, i − 1) + ε · M(H, i − 1) = S(H, i) である。 0.71
For a monotone H this is true since 単調 h の場合、これは事実である。 0.51
(1 − ε) · S(H, i − 1) + ε · M (H, i − 1) = (1 − ε) · [1 − (1 − ε)i−1] + ε = 1 − (1 − ε)i = S(H, i) , (1 − ε) · S(H, i − 1) + ε · M(H, i − 1) = (1 − ε) · [1 − (1 − ε)i−1] + ε = 1 − (1 − ε)i = S(H, i) ) 0.87
and for a non-monotone H this is true since 単調でない h の場合、これは事実である。 0.45
(1 − ε) · S(H, i − 1) + ε · M (H, i − 1) = (1 − ε) · (ε(i − 1)) · (1 − ε)i−2 + ε · (1 − ε)i−1 (1 − ε) · S(H, i − 1) + ε · M(H, i − 1) = (1 − ε) · (ε(i − 1)) · (1 − ε)i−2 + ε · (1 − ε)i−1 0.91
= (εi) · (1 − ε)i−1 = S(H, i) . = (εi) · (1 − ε)i−1 = S(H, i) 。 0.90
10 10 0.85
英語(論文から抽出)日本語訳スコア
Using Lemma 3.5, we now get Lemma 3.5が利用可能に 0.77
F (y(εi)) ≥ F (y(ε(i−1))) + ε · {[M (G, i − 1) · G(o) − G(y(ε(i−1)))] F(y(εi)) ≥ F(y(ε(i−1))) + ε · {[M(G, i − 1) · G(o) − G(y(ε(i−1)))] 0.86
= (1 − ε) · F (y(ε(i−1))) + ε · {M (G, i − 1) · G(o) + M (C, i − 1) · C(o)} − ε2LD2 ≥ [(1 − ε) · S(G, i − 1) · G(o) + ε · M (G, i − 1) · G(o)] = (1 − ε) · F (y(ε(i−1))) + ε · {M (G, i − 1) · G(o) + M (C, i − 1) · C(o)} − ε2LD2 ≥ [(1 − ε) · S(G, i − 1) · G(o) + ε · M (G, i − 1) · G(o))] 0.88
+ [M (C, i − 1) · C(o) − C(y(ε(i−1)))]} − ε2LD2 + [M (C, i − 1) · C(o) − C(y(ε(i−1)))]} − ε2LD2 0.88
+ [(1 − ε) · S(C, i − 1) · C(o) + ε · M (C, i − 1) · C(o)] − [(1 − ε) · (i − 1) · ε2LD2 + ε2LD2] + [(1 − ε) · S(C, i − 1) · C(o) + ε · M(C, i − 1) · C(o)] − [(1 − ε) · (i − 1) · ε2LD2 + ε2LD2] 0.89
≥ S(G, i) · G(o) + S(C, i) · C(o) − i · ε2LD2 , ≥ S(G, i) · G(o) + S(C, i) · C(o) − i · ε2LD2 , 0.94
where the second inequality holds due to the induction hypothesis. 2番目の不平等は 帰納仮説によるものです 0.61
We are now ready to state and prove our main theorem for Algorithm 2. 現在、アルゴリズム2の主な定理を述べ、証明する準備ができています。 0.69
Theorem 3.7. Let S be the time it takes to find a point in P maximizing a given liner function, then Algorithm 2 runs in O(ε−1(n + S)) time, makes O(1/ε) calls to the gradient oracle, and outputs a vector y such that 定理3.7。 s を与えられたライナー関数を最大化する p の点を見つけるのに要する時間とすると、アルゴリズム2 は o(ε−1(n + s)) 時間で動作し、勾配オラクルに o(1/ε) を呼び出し、ベクトル y を出力する。 0.70
(cid:26)1 − e−1 if G is monotone (cid:26)1 − e−1 G が単調であれば 0.64
(cid:27) e−1 (cid:27) e−1 0.69
otherwise F (y) ≥ そうでなければ F (y) ≥ 0.59
(cid:26)1 − e−1 if C is monotone (cid:26)1 − e−1 C が単調であれば 0.63
(cid:27) e−1 (cid:27) e−1 0.69
otherwise · G(o) + そうでなければ ·g(o) + 0.56
· C(o) − O(εLD2) . ·C(o) − O(εLD2)。 0.84
Proof. The output guarantee for Theorem 3.7 follows from Corollary 3.6. 証明。 Theorem 3.7の出力保証はCorollary 3.6に従っている。 0.66
Like in the analysis of Theorem 3.3, the time and oracle complexities follow from the observation that the algorithm performs ε−1 iterations, and each iteration takes O(n + S) time and makes a single call to the gradient oracle. 定理3.3の分析と同様に、時間とオラクルの複雑さはアルゴリズムがε−1イテレーションを実行し、各イテレーションはo(n + s)時間をかけて勾配オラクルに1回の呼び出しを行うという観察から導かれる。
訳抜け防止モード: Theorem 3.3の分析と同様、時間とオラクルの複雑さは観測結果から導かれる。 アルゴリズムはε−1の繰り返しを実行する 各反復は O(n + S ) 時間を要する グラデーション・オラクルに1回呼び出します
0.82
Remark: The guarantees of Algorithms 1 and 2 apply in general to different settings. 注意:アルゴリズム1と2の保証は、一般的に異なる設定に適用されます。 0.67
However, both guarantees apply in the special case in which the functions G and C are monotone and the polytope P is down-closed. しかし、どちらの保証も関数 g と c が単調であり、ポリトープ p がダウンクローズドである特別な場合に適用できる。 0.68
Interestingly, the two guarantees are identical in this common special case. 興味深いことに、この2つの保証は、この一般的な特別なケースで同一である。 0.52
3.3 Gradient Combining Frank-Wolfe Algorithm Up to this point, the guarantees of the algorithms that we have seen had both α and β that are strictly smaller than 1. 3.3 フランク・ウルフアルゴリズムをこの点まで組み合わせることで、我々が見たアルゴリズムの保証は α と β の両方を持ち、1 より厳密に小さい。 0.82
However, since concave functions can be exactly maximized, it is reasonable to expect also algorithms for which the coefficient β associated with C(o) is equal to 1. しかし、凹函数は正確に最大化できるので、C(o) に付随する係数 β が 1 に等しいアルゴリズムも期待することは妥当である。 0.76
In Sections 3.3 and 3.4, we describe such algorithms. セクション3.3および3.4では、そのようなアルゴリズムを記述する。 0.55
In this section, we assume that G is a monotone and non-negative function (in addition to its other properties). この節では、G が単調で非負な函数であると仮定する(他の性質に加えて)。 0.73
The algorithm we study in this section is Algorithm 3, and it again takes a quality control parameter ε ∈ (0, 1) as input. この節で研究したアルゴリズムはアルゴリズム3であり、再び品質制御パラメータε ∈ (0, 1) を入力とする。 0.76
This time, however, the algorithm assumes that ε−3 is an integer. しかし今回は、このアルゴリズムが ε−3 を整数であると仮定する。 0.81
As usual, if that is not the case, then ε can be replaced with a value from the range [ε/2, ε] 通常のように、もしそうでなければ、ε は [ε/2, ε] の範囲の値に置き換えることができる。 0.82
11 11 0.85
英語(論文から抽出)日本語訳スコア
that has this property. Algorithm 3: Gradient Combining Frank-Wolfe (ε) この性質があります アルゴリズム3:フランクウルフ(ε)を組み合わせた勾配 0.64
Let y(0) be a vector in P maximizing C up to an error of η ≥ 0. for i = 1 to ε−3 do s(i) ← arg maxx∈P y(i) ← (1 − ε2) · y(i−1) + ε2 · s(i) y(0) を c を η ≥ 0 の誤差まで最大化する p のベクトルとし、i = 1 から ε−3 do s(i) に対して、arg maxx guip y(i) , (1 − ε2) · y(i−1) + ε2 · s(i) とする。 0.87
(cid:10)∇G(y(i−1)) + 2∇C(y(i−1)), x(cid:11) (cid:10) =G(y(i−1)) + 2\C(y(i−1)), x(cid:11) 0.83
end for return the vector maximizing F among {y(0), . end for return ベクトルは {y(0), の中で f を最大化する。 0.84
. . , y(ε−3)} . . , y(ε−3)} 0.87
Firstly, note that for every integer 0 ≤ i ≤ ε−3, y(i) ∈ P ; and therefore, the output of Algorithm 3 also belongs to P . まず、すべての整数 0 ≤ i ≤ ε−3, y(i) ∈ P に対してアルゴリズム3の出力は P に属することに注意する。 0.73
For i = 0 this holds by the initialization of y(0). i = 0 の場合、これは y(0) の初期化によって成り立つ。 0.80
For larger values of i, this follows by induction because y(i) is a convex combination of y(i−1) and the point s(i) (y(i−1) belongs to P by the induction hypothesis, and s(i) belongs to P by definition). なぜなら、y(i) は y(i−1) の凸結合であり、点 s(i) (y(i−1) は誘導仮説により p に属し、s(i) は定義により p に属するからである。
訳抜け防止モード: i のより大きな値に対して、y(i) は y(i−1) の凸結合であるため、これは誘導によって従う。 そして、点 s(i ) ( y(i−1 ) は帰納仮説により P に属する。 そして s(i ) は P に属する。
0.76
Our next objective is to lower bound the value of the output point of Algorithm 3. 次の目的は、アルゴリズム3の出力点の値の上限を下げることです。 0.70
For that purpose, it will be useful to define ¯F (x) = G(x) + 2C(x) and H(i) = ¯F (o) − ¯F (y(i)). その目的のために、この式は シュF (x) = G(x) + 2C(x) と H(i) = シュF (o) − シュF (y(i)) を定義するのに有用である。 0.76
To get a bound on the value of the output of Algorithm 3, we first show that H(i) is small for at least some i value. アルゴリズム3の出力値のバウンダリを得るために、まず、H(i) が少なくともいくつかの i 値に対して小さいことを示す。 0.72
We do that using the next lemma, which shows that H(i) decreases as a function of i as longs as it is not already small compared to G(yi). 我々は次の補題を用いて、H(i) が G(yi) と比較して既に小さくないため、i の函数として減少することを示す。
訳抜け防止モード: 私たちは次の補題を使って、H(i ) が i の長の関数として減少することを示す。 それはもう小さくありません G(yi ) と比較する。
0.81
Then, Corollary 3.9 guarantees the existence of a good iteration i∗. そして、Corollary 3.9 は良い反復 i∗ の存在を保証する。 0.68
Lemma 3.8. For every integer 1 ≤ i ≤ ε−3, H(i − 1) − H(i) ≥ ε2 · [G(o) − 2G(y(i−1))] + 2ε2 · [C(o) − C(y(i−1))] − 6ε4LD2 = ε2 · [H(i − 1) − G(y(i−1))] − 6ε4LD2. レマ3.8。 すべての整数 1 ≤ i ≤ ε−3 に対し、H(i − 1) − H(i) ≥ ε2 · [G(o) − 2G(y(i−1))] + 2ε2 · [C(o) − C(y(i−1))] − 6ε4LD2 = ε2 · [H(i − 1) − G(y(i−1))] − 6ε4LD2 である。 0.76
Proof. Observe that H(i − 1) − H(i) = ¯F (y(i)) − ¯F (y(i−1)) = ¯F ((1 − ε2) · y(i−1) + ε2 · s(i)) − ¯F (y(i−1)) 証明。 観察する H(i − 1) − H(i) = シュF(y(i)) − シュF(y(i−1)) = シュF((1 − ε2) · y(i−1) + ε2 · s(i)) − シュF(y(i−1)) 0.73
To make the expression on the rightmost side useful, we need to lower bound the inner product 一番右側の表現を便利にするためには、内積を低くする必要がある 0.60
= (cid:68) ≥(cid:68) (cid:68) = (cid:68)≥(cid:68)(cid:68) 0.85
= s(i),∇G(y(i−1)) + 2∇C(y(i−1)) o,∇G(y(i−1)) + 2∇C(y(i−1)) o − y(i−1),∇G(y(i−1)) = s(i,y(i−1)) + 2/c(y(i−1)) o,2/g(y(i−1)) + 2/c(y(i−1)) o − y(i−1), s(y(i−1)) 0.84
(cid:69) (cid:68) (cid:69) (cid:68) 0.78
+ (cid:69) −(cid:68) (cid:69) −(cid:68) + (cid:69) −(cid:68) (cid:69) −(cid:68) 0.81
y(i−1),∇G(y(i−1)) + 2∇C(y(i−1)) y(i−1),∇G(y(i−1)) + 2∇C(y(i−1)) y(i−1) + 2\C(y(i−1)) y(i−1) + 2\C(y(i−1)) + 2\C(y(i−1)) 0.86
(cid:69) 2(o − y(i−1)),∇C(y(i−1)) (cid:69) 2(o − y(i−1)),c(y(i−1)) 0.86
, (cid:69) , (cid:69) 0.82
(cid:69) 12 (cid:69) 12 0.82
0 = (cid:90) ε2 (cid:90) ε2 (cid:68) (cid:90) ε2 (cid:104)(cid:68) = ε2 ·(cid:68) (cid:10)s(i) − y(i−1),∇ ¯F (y(i−1))(cid:11). 0 = (cid:90) ε2 (cid:90) ε2 (cid:68) (cid:90) ε2 (cid:104)(cid:68) = ε2 ·(cid:68) (cid:10)s(i) − y(i−1) である。 0.88
(cid:69) (cid:68) (cid:69)(cid:68) 0.75
s(i) − y(i−1),∇ ¯F (y(i−1)) s(i) − y(i−1), = yF(y(i−1)) 0.96
≥ = 0 0 ¯F ((1 − z) · y(i−1) + z · s(i)) ≥ = 0 0 f ((1 − z) · y(i−1) + z · s(i)) 0.85
dz s(i) − y(i−1),∇ ¯F ((1 − r) · y(i−1) + r · s(i)) dz s(i) − y(i−1) , s(i) ((1 − r) · y(i−1) + r · s(i)) 0.91
dr dr (cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:69) − 12rLD2(cid:105) (cid:69) − 6ε4LD2 . 博士 博士 (cid:12)(cid:12)(cid :12)(cid:12)z=r(cid:69) − 12rLD2(cid:105) (cid:69) − 6ε4LD2。 0.66
(cid:69) dr (cid:69) 博士 0.73
s(i) − y(i−1),∇ ¯F (y(i−1)) s(i) − y(i−1),∇ ¯F (y(i−1)) s(i) − y(i−1) = y(i−1) = y(i−1) s(i) − y(i−1) = y(i−1) 0.89
英語(論文から抽出)日本語訳スコア
(cid:69) (cid:68) (cid:69) (cid:68) 0.78
ε2(o − y(i−1)),∇G(y(i−1)) ε2(o − y(i−1)),\G(y(i−1)) 0.98
+ 2ε2(o − y(i−1)),∇C(y(i−1)) + 2ε2(o − y(i−1)),\C(y(i−1)) 0.90
where the inequality holds since s(i) is the maximizer found by Algorithm 3. s(i) がアルゴリズム3で見つかる最大値であることから不等式が成り立つ。 0.67
Combining the last two inequalities yields 最後の2つの不等式の組み合わせ 0.60
concavity of C. To prove the other inequality, observe that the DR-submodularity of G implies [0, 1]n, x(1) + x2 ∈ [0, 1]n and x(1) is either non-negative or non-positive. 他の不等式を証明するために、G の DR-部分モジュラリティは [0, 1]n, x(1) + x2 ∈ [0, 1]n, x(1) が非負あるいは非正であることを意味する。 0.83
This observation implies (cid:69) − 6ε4LD2 . この観察は (cid:69) − 6ε4LD2。 0.64
H(i − 1) − H(i) ≥(cid:68) Therefore, to complete the proof of the lemma it remains to prove that(cid:10)o − y(i−1),∇G(y(i−1))(cid:11) ≥ G(o) − 2G(y(i−1)) and(cid:10)o − y(i−1),∇C(y(i−1))(cid:11) ≥ C(o) − C(y(i−1)). H(i − 1) − H(i) ≥(cid:68) なので、補題の証明を完遂するには、(cid:10)o − y(i−1),\G(y(i−1))(cid:11) ≥ G(o) − 2G(y(i−1)) and(cid:10)o − y(i−1))(cid:11) ≥ C(o) − C(y(i−1)) ≥ C(y(i−1)) であることが証明される。 0.87
The inequality (cid:10)o − y(i−1),∇C(y(i−1))(cid:11) ≥ C(o) − C(y(i−1)) follows immediately from the (cid:10)x(1),∇G(x(2))(cid:11) ≥ (cid:10)x(1),∇G(x(1) + x(2))(cid:11) for every two vectors x(1) and x(2) that obey x(2) ∈ (cid:68) (cid:68) (cid:90) 1 (cid:68) (cid:90) 1 不等式 (cid:10)o − y(i−1))(cid:11) ≥ C(o) − C(y(i−1)) は、x(2) ∈ (cid:68) (cid:90) 1 (cid:68) (cid:90) 1 (cid:68) 1 (cid:90) 1 (cid:90) 1 (cid:10) x(1),\G(x(1) + x(2))(cid:11)x(1),\G (x(1) + x(2))(cid:11) 0.86
o ∧ y(i−1) − y(i−1),∇G(y(i−1) + r · (o ∧ y(i−1) − y(i−1))) dG(y(i−1) + z · (o ∨ y(i−1) − y(i−1))) + dG(y(i−1) + z · (o ∧ y(i−1) − y(i−1))) y(i−1) − y(i−1) + dg(y(i−1) − y(i−1)) + dg(y(i−1) − y(i−1)) + dg(y(i−1) − y(i−1)) + dg(y(i−1) + z · (o ) y(i−1) − y(i−1)))) 0.86
o − y(i−1),∇G(y(i−1)) o ∨ y(i−1) − y(i−1),∇G(y(i−1)) o − y(i−1) , , G(y(i−1)) , y(i−1) − y(i−1) , y(i−1)) 0.91
o ∨ y(i−1) − y(i−1),∇G(y(i−1) + r · (o ∨ y(i−1) − y(i−1))) y(i−1) − y(i−1), y(i−1) + r · (o ) y(i−1) − y(i−1))) 0.92
o ∧ y(i−1) − y(i−1),∇G(y(i−1)) o > y(i−1) − y(i−1),\G(y(i−1)) 0.80
(cid:69)(cid:105) (cid:69)(cid:105) 0.75
(cid:69) dr (cid:69) 博士 0.73
(cid:104)(cid:68) (cid:104)(cid:68) 0.75
(cid:69) (cid:68) (cid:69) (cid:68) 0.78
+ (cid:69) + (cid:69) 0.82
= ≥ 0 + = = [G(o ∨ y(i−1)) + G(o ∧ y(i−1))] − 2G(y(i−1)) ≥ G(o) − 2G(y(i−1)) , = ≥ 0 + = [G(o ) y(i−1)) + G(o ) y(i−1))] − 2G(y(i−1)) ≥ G(o) − 2G(y(i−1)) , 0.87
dz 0 where the last inequality follows from the monotonicity and non-negativity of G. Corollary 3.9. dz 0 最後の不等式は G. Corollary 3.9 の単調性と非負性から従う。 0.79
There is an integer 0 ≤ i∗ ≤ ε−3 obeying H(i∗) ≤ G(y(i∗)) + ε· [G(o) + 2η + 6LD2]. H(i∗) ≤ G(y(i∗)) + ε· [G(o) + 2η + 6LD2] に従う整数 0 ≤ i∗ ≤ ε−3 が存在する。 0.94
Proof. Assume towards a contradiction that the corollary does not hold. 証明。 従属が持たない矛盾を仮定する。 0.56
By Lemma 3.8, this implies 補題3.8からすると 0.70
H(i − 1) − H(i) ≥ ε2 · [H(i − 1) − G(y(i−1))] − 6ε4LD2 ≥ ε3 · [G(o) + 2η] − 6ε4LD2 H(i − 1) − H(i) ≥ ε2 · [H(i − 1) − G(y(i−1))] − 6ε4LD2 ≥ ε3 · [G(o) + 2η] − 6ε4LD2 0.95
for every integer 1 ≤ i ≤ ε−3. すべての整数 1 ≤ i ≤ ε−3 に対して。 0.70
Adding up this inequality for all these values of i, we get これらのiの値にこの不等式を加えると、 0.61
H(0) − H(ε−3) ≥ [G(o) + 2η] − 6εLD2 . H(0) − H(ε−3) ≥ [G(o) + 2η] − 6εLD2 。 0.84
However, by the choice of y(0), H(0) is not too large. しかし、y(0) の選択により、H(0) はそれほど大きくない。 0.67
Specifically, H(0) = [G(o) + 2C(o)] − [G(y(0)) + 2C(y(0))] ≤ [G(o) + 2C(o)] − {0 + 2[C(o) − η]} = G(o) + 2η , where the inequality holds since o is one possible candidate to be y(0) and G is non-negative. 具体的には、H(0) = [G(o) + 2C(o)] − [G(y(0)) + 2C(y(0))] ≤ [G(o) + 2C(o)] − {0 + 2[C(o) − η]} = G(o) + 2η である。
訳抜け防止モード: 具体的には、H(0 ) = [ G(o ) + 2C(o ) ] − [ G(y(0 ) ) + 2C(y(0 ) ) ] ≤ [ G(o ) + 2C(o ) ] − { 0 + 2[C(o ) − η ] } = G(o ) o からの不等式が成り立つ 2η は y(0) の候補の1つである。 G は非負である。
0.85
Therefore, we get [G(o) + 2η] − H(ε−3) ≥ [G(o) + 2η] − 6εLD2 , したがって、我々は [G(o) + 2η] − H(ε−3) ≥ [G(o) + 2η] − 6εLD2 , 0.89
which by the non-negativity of G and η implies g と η の非否定性によって 0.76
H(ε−3) ≤ 6εLD2 ≤ G(ε−3) + ε · [G(o) + 2η + 6LD2] H(ε−3) ≤ 6εLD2 ≤ G(ε−3) + ε · [G(o) + 2η + 6LD2] 0.84
(which contradicts our assumption). (これは私たちの仮定と矛盾する)。 0.53
13 (cid:69) 13 (cid:69) 0.82
(cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:12)(cid:12)(cid :12)z=r 0.86
dr 博士 0.68
英語(論文から抽出)日本語訳スコア
We are now ready to summarize the properties of Algorithm 3 in a theorem. 現在、アルゴリズム3の特性を定理で要約する準備ができています。 0.63
Theorem 3.10. Let S1 be the time it takes to find a point in P maximizing a given linear function and S2 be the time it takes to find a point in P maximizing C(·) up to an error of η, then Algorithm 3 runs in O(ε−3 · (n + S1) + S2) time, makes O(1/ε3) gradient oracle calls, and outputs a vector y such that 理論3.10。 s1 を与えられた線型関数を最大化する p の点を見つけるのに要する時間とし、s2 を η の誤差まで c(·) を最大化する p の点を見つけるのに要する時間とすると、アルゴリズム 3 は o(ε−3 · (n + s1) + s2) で動作し、o(1/ε3) 勾配 oracle の呼び出しを行い、ベクトル y を出力する。 0.69
F (y) ≥ 1 2 (1 − ε) · G(o) + C(o) − ε · O(η + LD2) . F (y) ≥ 1 2 (1 − ε) · G(o) + C(o) − ε · O(η + LD2) である。 0.86
Proof. We begin the proof by analyzing the time and oracle complexities of Algorithm 3. 証明。 アルゴリズム3の時間とオラクルの複雑さを分析して証明を開始する。 0.68
Every iteration of the loop of Algorithm 3 takes O(n + S1) time. アルゴリズム3のループの全てのイテレーションはo(n + s1)時間を要する。 0.79
As there are ε−3 such iterations, the entire algorithm runs in O(ε−3(n + S1) + S2) time. ε−3の反復が存在するので、アルゴリズム全体が o(ε−3(n + s1) + s2) 時間で実行される。 0.75
Also note that each iteration of the loop requires 2 calls to the gradient oracles (a single call to the oracle corresponding to G, and a single call to the oracle corresponding to C), so the overall oracle complexity of the algorithm is O(1/ε3). また、ループの各イテレーションは勾配オラクルへの2回の呼び出し(gに対応するオラクルへの1回の呼び出しとcに対応するオラクルへの1回の呼び出し)を必要とするので、アルゴリズム全体のオラクルの複雑さはo(1/ε3)である。 0.74
Consider now iteration i∗, whose existence is guaranteed by Corollary 3.9. 現在、i∗ は Corollary 3.9 で保証されている。 0.60
Then, H(i∗) ≤ G(y(i∗)) + ε · [G(o) + 2η + 6LD2] そしたら H(i∗) ≤ G(y(i∗)) + ε · [G(o) + 2η + 6LD2] 0.77
=⇒ [G(o) + 2C(o)] − [G(y(i∗)) + 2C(y(i∗))] ≤ G(y(i∗)) + ε · [G(o) + 2η + 6LD2] =⇒ (1 − ε) · G(o) + 2C(o) ≤ 2[G(y(i∗)) + C(y(i∗))] + ε · [2η + 6LD2] =⇒ F (y(i∗)) ≥ 1 G(o) + 2C(o)] − [G(y(i∗)) + 2C(y(i∗))] ≤ G(y(i∗)) + ε · [G(o) + 2η + 6LD2] = } (1 − ε) · G(o) + 2C(o) ≤ 2[G(y(i∗))) + C(y(i∗))] + ε · [2η + 6LD2] = ≤ F (y(i∗)) ≥ 1 である。 0.87
2 (1 − ε) · G(o) + C(o) − ε · [η + 3LD2] . 2 (1 − ε) · G(o) + C(o) − ε · [η + 3LD2] である。 0.89
The theorem now follows since the output of Algorithm 3 is at least as good as y(i∗). この定理は、アルゴリズム3の出力が少なくとも y(i∗) と同程度であるから従う。 0.63
3.4 Non-oblivious Frank-Wolfe Algorithm As mentioned in the beginning of Section 3.3, our objective in this section is to present another algorithm that has β = 1 (i.e., it maximizes C “exactly” in some sense). 3.4 非聖書的フランク・ウルフアルゴリズム 3.3の冒頭で述べたように、本節の我々の目標は、β = 1 を持つ別のアルゴリズムを提示することである(つまり、ある意味では c を最大化する)。 0.71
In Section 3.3, we presented Algorithm 3, which achieves this goal with α = 1/2. 第3節3では、α = 1/2でこの目標を達成するアルゴリズム3を提示した。 0.62
The algorithm we present in the current section achieves the same goal with an improved value of 1 − 1/e for α. 現在のセクションにあるアルゴリズムは、α に対して 1 − 1/e の改善値で同じ目標を達成する。 0.81
However, the improvement is obtained at the cost of requiring the function C to be non-negative (which was not required in Section 3.3). しかし、この改善は関数Cが非負であることを要求するコストで得られる(第3条3項では不要)。 0.74
Additionally, like in the previous section, we assume here that G is a monotone and non-negative function (in addition to its other properties). さらに、前節と同様に、G は単調で非負な函数である(他の性質に加えて)と仮定する。 0.66
The algorithm we study in this section is a non-oblivious variant of the Frank-Wolfe algorithm, appearing as Algorithm 4, which takes a quality control parameter ε ∈ (0, 1/4) as input. 本節で検討したアルゴリズムは,品質制御パラメータε ∈ (0, 1/4) を入力として,アルゴリズム4として現れるfrank-wolfeアルゴリズムの非聖書的変種である。 0.85
As usual, we assume without loss of generality that ε−1 is an integer. 通常のように、ε−1 が整数であることを一般性を失うことなく仮定する。 0.64
Algorithm 4 also employs the non-negative auxiliary function: アルゴリズム4は非負の補助関数も採用している。 0.59
¯G(x) = ε · ε−1(cid:88) G(x) = ε · ε−1(cid:88) 0.74
j=1 eεj · G(εj · x) j=1 eεj · G(εj · x) 0.74
εj . This function is inspired by the non-oblivious objective function used by Filmus and Ward [2012]. εj . この機能は、filmusとwardが2012年に使用した非聖書的目的関数にインスパイアされている。 0.75
Algorithm 4: Non-Oblivious Frank-Wolfe (ε) Algorithm 4: Non-Oblivious Frank-Wolfe (ε) 0.81
Let y(0) be an arbitrary vector in P , and let β(ε) ← e(1 − ln ε). y(0) を P 内の任意のベクトルとし、β(ε) を e(1 − ln ε) とする。 0.83
for i = 0 to (cid:100)e−1 · β(ε)/ε2(cid:101) do s(i) ← arg maxx∈P y(i+1) ← (1 − ε) · y(i) + ε · s(i) i = 0 から (cid:100)e−1 · β(ε)/ε2(cid:101) do s(i) > arg maxx⋅P y(i+1) > (1 − ε) · y(i) + ε · s(i) 0.89
(cid:10)e−1·∇ ¯G(y(i)) + ∇C(y(i)), x(cid:11) (cid:10)e−1·sg(y(i)) + sc(y(i)), x(cid:11) 0.88
end for return the vector maximizing F among {y(0), . end for return ベクトルは {y(0), の中で f を最大化する。 0.84
. . , y((cid:100)e−1· β(ε) . . , y((cid:100)e−1·β(ε) 0.84
ε2 (cid:101))} ε2 (cid:101) である。 0.66
14 14 0.85
英語(論文から抽出)日本語訳スコア
Note that any call to the gradient oracle of ¯G can be simulated using ε−1 calls to the gradient oracle of G. The properties of Algorithm 4 are stated in Theorem 3.18. G の勾配オラクルへの任意の呼び出しは、G の勾配オラクルへのε−1呼び出しを使ってシミュレートできる。 0.34
We begin the analysis of Algorithm 4 by observing that for every integer 0 ≤ i ≤ (cid:100)e−1 · β(ε)/ε2(cid:101), y(i) ∈ P ; and therefore, the output of Algorithm 4 also belongs to P . 我々は、すべての整数 0 ≤ i ≤ (cid:100)e−1 · β(ε)/ε2(cid:101), y(i) ∈ p に対して、アルゴリズム4の解析を開始する。
訳抜け防止モード: アルゴリズム4の解析を始める すべての整数 0 ≤ i ≤ ( cid:100)e−1 · β(ε)/ε2(cid:101 ) y(i ) ∈ P に対して したがって、アルゴリズム4の出力もPに属する。
0.74
The proof for this is identical to the corresponding proof in Section 3.3. この証明は、セクション3.3の対応する証明と同一である。 0.70
Let us now analyze the auxiliary function ¯G. さて、補助関数を解析してみましょう。 0.73
Specifically, we need to show that ¯G is almost as smooth as the original function G, and that for every given vector x ∈ [0, 1], the value of ¯G(x) is not very large compared to G(x). 具体的には、n が元の函数 G とほぼ同程度の滑らかさで、任意のベクトル x ∈ [0, 1] に対して、g(x) の値は G(x) と比較してあまり大きくないことを示す必要がある。 0.78
We mention these as observations below. 以下に観察として述べる。 0.68
Observation 3.11. The auxiliary function ¯G is eL-smooth. 観測3.11 補助関数は eL-smooth である。 0.69
Proof. For every two vectors x, y ∈ [0, 1]n, 証明。 すべての二つのベクトル x, y ∈ [0, 1]n に対して 0.75
(cid:107)∇ ¯G(x) − ∇ ¯G(y)(cid:107)2 = (cid:107) > > G(x) − > > G(y)(cid:107)2 = 0.71
eεj · [∇G(εj · x) − ∇G(εj · y)] eεj · [sg(εj · x) − sg(εj · y)] 0.95
(cid:13)(cid:13)(cid :13)(cid:13)(cid:13) (cid:13)ε · ε−1(cid:88) (cid:13)(cid:13)(cid :13)(cid:13)(cid:13) ε · ε−1(cid:88) 0.81
j=1 ≤ ε · ε−1(cid:88) j=1 ≤ ε · ε−1(cid:88) 0.69
j=1 eεj · (cid:107)∇G(εj · x) − ∇G(εj · y)(cid:107)2 j=1 eεj · (cid:107) =G(εj · x) − εj · y)(cid:107)2 0.72
εj e · Lεj · (cid:107)x − y(cid:107)2 εj e · Lεj · (cid:107)x − y(cid:107)2 0.81
εj = eL · (cid:107)x − y(cid:107)2 . εj = eL · (cid:107)x − y(cid:107)2。 0.83
εj ≤ ε · ε−1(cid:88) εj ≤ ε · ε−1(cid:88) 0.78
j=1 (cid:13)(cid:13)(cid :13)(cid:13)(cid:13) (cid:13)2 j=1 (cid:13)(cid:13)(cid :13)(cid:13)2 0.75
Observation 3.12. For every vector x ∈ [0, 1]n, ¯G(x) ≤ β(ε) · G(x). 観測3.12 任意のベクトル x ∈ [0, 1]n に対して、g(x) ≤ β(ε) · G(x) である。 0.78
Proof. Note that, by the monotonicity of G, 証明。 注意すべきは g の単調性によって 0.64
¯G(x) = ε · ε−1(cid:88) G(x) = ε · ε−1(cid:88) 0.74
eεj · G(εj · x) eεj · G(εj · x) 0.88
≤ ε · ε−1(cid:88) ≤ ε · ε−1(cid:88) 0.78
j=1 e · G(x) j=1 e · G(x) 0.72
εj εj j=1 = e · G(x) · ε−1(cid:88) (cid:90) ε−1 ε−1(cid:88) εj εj j=1 e · G(x) · ε−1(cid:88) (cid:90) ε−1 ε−1(cid:88) 0.73
1 j j=1 ≤ 1 + 1J j=1 ≤ 1 + 0.73
1 j j=1 1 ≤ e(1 − ln ε) · G(x) = β(ε) · G(x) , 1J j=1 1 ≤ e(1 − ln ε) · g(x) = β(ε) · g(x) , , 0.76
dx x = 1 + [ln x]ε−1 dx x = 1 + [ln x]ε−1 0.91
1 = 1 − ln ε . 1 = 1 − ln ε . 0.85
where the last inequality holds since We now define ¯F (x) = e−1 · ¯G(x) + C(x). 最後の不平等が f (x) = e−1 · sg(x) + c(x) と定義する。 0.58
To get a bound on the value of the output of Algorithm 4, we need to show that there exists at least one value of i for which ¯F (y(i+1)) is not much larger than ¯F (y(i)), which intuitively means that y(i) is roughly a local maximum with respect to ¯F . アルゴリズム4の出力の値のバウンドを得るには、少なくとも1つの i の値が存在し、y(i) が y(i) に対して大まかに局所的な最大値であることを示す必要がある。
訳抜け防止モード: アルゴリズム4の出力値のバウンダリを得る。 i の少なくとも 1 つの値が存在することを示す必要があるが、ここでは yF ( y(i+1 ) ) が yF ( y(i+1 ) ) よりもそれほど大きくない。 これは直観的には y(i ) が大まかに局所極大であることを意味する。
0.77
The following lemma proves that such an i value indeed exists. 以下の補題は、そのような i の値が実際に存在することを証明している。 0.48
Lemma 3.13. There is an integer 0 ≤ i∗ < (cid:100)e−1·β(ε)/ε2(cid:101) such that ¯F (y(i∗+1))− ¯F (y(i∗)) ≤ ε2·F (o). 補題3.13。 整数 0 ≤ i∗ < (cid:100)e−1·β(ε)/ε2(cid:101) が存在して、 ε2·F (o) ≤ ε2·F (y(i∗+1)) である。 0.61
Proof. Assume towards a contradiction that the lemma does not hold. 証明。 補題が持たない矛盾に対して仮定する。 0.61
This implies ¯F (y((cid:100)β(ε)/ε2(cid:101))) − ¯F (y(0)) = これは f (y((cid:100)β(ε)/ε2(cid:101)) − sf (y(0)) = 0.77
[ ¯F (y(i+1)) − ¯F (y(i))] (y(i+1))−f(y(i))] 0.61
(cid:100)β(ε)/ε2(cid:101)−1(cid:88) (cid:100)β(ε)/ε2(cid:101)−1(cid:88) 0.75
i=0 > (cid:100)e−1 · β(ε)/ε2(cid:101) · ε2 · F (o) ≥ e−1 · β(ε) · F (o) . i=0 > (cid:100)e−1 · β(ε)/ε2(cid:101) · ε2 · F (o) ≥ e−1 · β(ε) · F (o) 。 0.71
15 15 0.85
英語(論文から抽出)日本語訳スコア
Furthermore, using the non-negativity of ¯F , the last inequality implies さらに、f の非否定性を用いて、最後の不等式が示唆する。 0.50
e−1 · ¯G(y((cid:100)β(ε)/ε2(cid:101))) + C(y((cid:100)β(ε)/ε2(cid:101))) = ¯F (y((cid:100)β(ε)/ε2(cid:101))) e−1 · εG(y((cid:100)β(ε)/ε2(cid:101))) + C((cid:100)β(ε)/ε2(cid:101))) = εF(y((cid:100)β(ε)/ε2(cid:101)) 0.86
Let us now upper bound the two terms on the leftmost side of the above inequality. さて、上の不等式の最左側の2つの項を上限にしましょう。 0.74
By Observation 3.12, we can upper bound ¯G(y((cid:100)β(ε)/ε2(cid:101))) by β(ε) · G(y((cid:100)β(ε)/ε2(cid:101))). 観測 3.12 により、β(ε) · G((cid:100)β(ε)/ε2(cid:101)) による上界 yG((cid:100)β(ε)/ε2(cid:101)) が可能である。 0.88
Additionally, since β(ε) ≥ e because ε < 1, we can upper bound C(y((cid:100)β(ε)/ε2(cid:101))) by e−1 · β(ε) · C(y((cid:100)β(ε)/ε2(cid:101))). さらに、ε < 1 であるから β(ε) ≥ e であるから、e−1 · β(ε) · C(((cid:100)β(ε)/ε2(cid:101)) で上界 C(y((cid:100)β(ε)/ε2(cid:101)) が成り立つ。 0.89
Plugging both these upper bounds into the previous inequalities and dividing by e−1 · β(ε) gives これらの上界を以前の不等式に差し込み、e−1 · β(ε) で割ることにより得られる。 0.57
F (y((cid:100)β(ε)/ε2(cid:101))) = G(y((cid:100)β(ε)/ε2(cid:101))) + C(y((cid:100)β(ε)/ε2(cid:101))) > F (o) , f(y((cid:100)β(ε)/ε2(cid:101)) = g(y((cid:100)β(ε)/ε2(cid:101)) + c(y(((cid:100)β(ε)/ε2(cid:101)) > f(o) , 0.90
≥ ¯F (y((cid:100)β(ε)/ε2(cid:101))) − ¯F (y(0)) > e−1 · β(ε) · F (o) . ≥ f (y((cid:100)β(ε)/ε2(cid:101)) − e−1 · β(ε) · f (o) である。 0.77
The preceding lemma shows that y(i∗) is roughly a local optimum in terms of ¯F . 前述の補題は y(i∗) が概して局所最適化であることを示している。 0.60
We now show which contradicts the definition of o, and thus, completes the proof of the lemma. ご覧いただくのは これは o の定義と矛盾し、補題の証明を完結させる。 0.55
an upper bound on(cid:10)(o − y(i∗)),∇ ¯G(y(i∗))(cid:11) that is implied by this property of y(i∗). 上界 (cid:10)(o − y(i∗)) , y(i∗))(cid:11) は y(i∗) のこの性質によって暗示される。 0.60
Lemma 3.14. (cid:10)e−1 · (o − y(i∗)),∇ ¯G(y(i∗))(cid:11) ≤ ε · F (o) + [C(y(i∗)) − C(o)] + 4εLD2. 補題3.14。 (cid:10)e−1 · (o − y(i∗)), (cid:11) ≤ ε · F (o) + [C(y(i∗)) − C(o)] + 4εLD2 である。
訳抜け防止モード: 補題3.14。 ( cid:10)e−1 · ( o − y(i∗)), = εG(y(i∗))(cid:11 ) ≤ ε · F ( o ) + [ C(y(i∗ ) ) − C(o ) ] + 4εLD2 。
0.66
Proof. Observe that (cid:90) ε (cid:90) ε (cid:90) ε 証明。 観察する (cid:90)ε(cid:90)ε(cid:90)ε 0.67
0 0 (cid:68) (cid:104)(cid:68) 0 0 (cid:68) (cid:104)(cid:68) 0.81
= = ≥ ¯F (y(i∗+1)) − ¯F (y(i∗)) = ¯F ((1 − ε) · y(i∗) + ε · s(i∗)) − ¯F (y(i∗)) = = ≥ y(i∗+1)) − yF(y(i∗)) = yF((1 − ε) · y(i∗) + ε · s(i∗)) − yF(y(i∗)) 0.82
¯F ((1 − z) · y(i∗) + z · s(i∗)) f ((1 − z) · y(i∗) + z · s(i∗)) 0.74
dz s(i∗) − y(i∗),∇ ¯F ((1 − r) · y(i∗) + r · s(i∗+1)) dz s(i∗) − y(i∗) , s(i∗) ((1 − r) · y(i∗) + r · s(i∗+1)) 0.89
dr (cid:12)(cid:12)(cid :12)(cid:12)z=r (cid:69) − 8rLD2(cid:105) 博士 (cid:12)(cid:12)(cid :12)(cid:12)z=r(cid:69) − 8rLD2(cid:105) 0.68
(cid:69) dr (cid:69) 博士 0.73
(cid:68) s(i∗) − y(i∗),∇ ¯F (y(i∗)) (cid:68) s(i∗) − y(i∗) = y(i∗) 0.69
dr = ε · (s(i∗) − y(i∗)),∇ ¯F (y(i∗)) Dr = ε · (s(i∗) − y(i∗)) , . . ε · (y(i∗)) 0.77
(cid:69) − 4ε2LD2 . (cid:69) − 4ε2LD2。 0.56
To make the expression in the rightmost side useful, we need to lower bound the expression 右端の表現を便利にするためには 表現の限界を低くする必要があります 0.76
0 (cid:10)s(i∗) − y(i∗),∇ ¯F (y(i∗))(cid:11). 0 (cid:10)s(i∗) − y(i∗) = y (i∗))(cid:11)。 0.79
= (cid:68) ≥(cid:68) (cid:68) = (cid:68)≥(cid:68)(cid:68) 0.85
(s(i∗) − y(i∗)) · ∇ ¯F (y(i∗)) (s(i∗) − y(i∗)) · シュ・F(y(i∗)) 0.78
s(i∗), e−1 · ∇ ¯G(y(i∗)) + ∇C(y(i∗)) o, e−1 · ∇ ¯G(y(i∗)) + ∇C(y(i∗)) e−1 · (o − y(i∗)),∇ ¯G(y(i∗)) s(i∗), s(i∗), e−1, e−1, e−1 · sg(y(i∗)) + sc(y(i∗)) o, e−1 · sg(y(i∗)) + sc(y(i∗)) e−1 · (o − y(i∗)), sg(y(i∗))) 0.84
(cid:69) ε2 · F (o) ≥ ¯F (y(i∗+1)) − ¯F (y(i∗)) ≥(cid:68) (cid:69) ε2 · F (o) ≥ > F (y(i∗+1)) − >F (y(i∗)) ≥(cid:68) 0.92
+ = (cid:69) −(cid:68) (cid:69) −(cid:68) (cid:68) + = (cid:69) −(cid:68) (cid:69) −(cid:68) (cid:68) 0.82
y(i∗), e−1 · ∇ ¯G(y(i∗)) + ∇C(y(i∗)) y(i∗), e−1 · > > G(y(i∗)) + >C(y(i∗)) 0.79
y(i∗), e−1 · ∇ ¯G(y(i∗)) + ∇C(y(i∗)) y(i∗), e−1 · > > G(y(i∗)) + >C(y(i∗)) 0.79
(cid:69) o − y(i∗),∇C(y(i∗)) (cid:69) o − y(i∗) , =C(y(i∗)) 0.80
, (cid:69) , (cid:69) 0.82
(cid:69) where the inequality holds since s(i) is the maximizer found by Algorithm 4. (cid:69) s(i) がアルゴリズム 4 で見つかる最大値であるため、不等式は成立する。 0.73
Combining the last two inequalities and the guarantee on i∗ from Lemma 3.13, we now get ε · (s(i∗) − y(i∗)),∇ ¯F (y(i∗)) 最後の2つの不等式とLemma 3.13 からの i∗ の保証を組み合わせることで、ε · (s(i∗) − y(i∗)) と y (i∗)) を得られる。 0.79
≥ ε ·(cid:104)(cid:68) ≥ ε ·(cid:104)(cid:68) ≥ ε ·(cid:104)(cid:68) ≥ ε ·(cid:104)(cid:68) 0.83
e−1 · (o − y(i∗)),∇ ¯G(y(i∗)) e−1 · (o − y(i∗)),∇ ¯G(y(i∗)) e−1 · (o − y(i∗)), e−1 · (o − y(i∗)), e−1(y(i∗)), e−1(o − y(i∗)), e−1(y(i∗)) 0.85
o − y(i∗),∇C(y(i∗)) o − y(i∗) , =C(y(i∗)) 0.81
+ + C(o) − C(y(i−1)) + + C(o) − C(y(i−1)) 0.96
(cid:68) (cid:69) (cid:69) (cid:68) (cid:69)(cid:69) 0.76
(cid:69) − 4ε2LD2 (cid:69)(cid:105) − 4ε2LD2 (cid:105) − 4ε2LD2 , (cid:69) − 4ε2LD2 (cid:69)(cid:105) − 4ε2LD2 (cid:105) − 4ε2LD2 , 0.59
where the last inequality follows from the concavity of C. The lemma now follows by rearranging the last inequality (and dividing it by ε). 最後の不等式が c の凹凸から続くとき、補題は最後の不等式を再配置し、それを ε で割ることで従う。 0.57
16 16 0.85
英語(論文から抽出)日本語訳スコア
We now wish to lower bound (cid:10)(o − y(i∗)),∇ ¯G(y(i∗))(cid:11) and we do so by separately analyzing (cid:10)o,∇ ¯G(y(i∗))(cid:11) and(cid:10)y(i∗),∇ ¯G(y(i∗))(cid:11) in the following two lemmas. 以下の2つの補題で (cid:10)(o − y(i∗)) と (cid:10)(y(i∗))(cid:11) を別々に解析することで、下界 (cid:10)(o − y(i∗)) と下界 (cid:10)(y(i∗))(cid:11) を下げることを望んでいる。 0.73
Lemma 3.15. (cid:10)o,∇ ¯G(y(i∗))(cid:11) ≥ (e − 1) · G(o) − ε ·(cid:80)ε−1 補題3.15。 (cid:10)o, > > G(y(i∗))(cid:11) ≥ (e − 1) · G(o) − ε ·(cid:80)ε−1 0.70
j=1 eεj · G(εj · y(i∗)). j=1 eεj · g(εj · y(i∗))。 0.88
Proof. For brevity, we use in this proof the shorthand u(j) = εj · y(i∗). 証明。 簡潔性については、この証明において略式 u(j) = εj · y(i∗) を用いる。 0.62
Then, for every integer 0 ≤ j ≤ ε−1, we get (in these calculations, the expression ∇G(εj · y(i∗)) represents the gradient of the function G(εj · x) at the point x = y(i∗)). すると、すべての整数 0 ≤ j ≤ ε−1 に対して、得られる(これらの計算では、点 x = y(i∗) における函数 G(εj · x) の勾配を表す式は、 εG(εj · y(i∗)) である)。 0.81
(cid:10)o,∇G(εj · y(i∗))(cid:11) (cid:90) 1 (cid:10)o,\G(εj · y(i∗))(cid:11) (cid:90) 1 0.95
εj (cid:10)o ∨ u(j) − u(j),∇G(εj · y(i∗))(cid:11) (cid:12)(cid:12)(cid :12)(cid:12)z=r εj (cid:10)o u(j) − u(j)\G(εj · y(i∗))(cid:11))(cid:12)( cid:12)(cid:12)(cid: 12)z=r 0.82
≥ dG(u(j) + z · (o ∨ u(j) − u(j))) ≥ dg(u(j) + z · (o ) u(j) − u(j))) 0.82
dz εj ≥ = G(o ∨ u(uj)) − G(εj · y(i∗)) ≥ G(o) − G(εj · y(i∗)) , dz εj ≥ = G(o ) u(uj)) − G(εj · y(i∗)) ≥ G(o) − G(εj · y(i∗)) , 0.83
dr = 0 = (cid:104) Dr = 0 = (cid:104) 0.81
dG(u(j) + z(o ∨ u(j) − u(j))) dG(u(j) + z(o ) u(j) − u(j))) 0.85
dz G(u(j) + z · (o ∨ u(j) − u(j))) dz G(u(j) + z · (o ) u(j) − u(j))) 0.85
(cid:12)(cid:12)(cid :12)(cid:12)z=0 (cid:105)1 (cid:12)(cid:12)(cid :12)(cid:12)z=0(cid:105)1 0.70
0 where the first and last inequalities follow from the monotonicity of G and the second inequality follows from the DR-submodularity of G. Using the last inequality, we now get 0 第一の不等式と最後の不等式が g の単調性から続き、第二の不等式が g の dr-準モジュラリティから続くとき。 0.73
(cid:68) o,∇ ¯G(y(i∗)) (cid:68) オ・・・G(y(i∗)) 0.69
(cid:69) (cid:10)eεj · o,∇G(εj · y(i∗))(cid:11) (cid:69) (cid:10)eεj · o,\G(εj · y(i∗))(cid:11) 0.85
= ε · ε−1(cid:88) ≥ (e − 1) · G(o) − ε · ε−1(cid:88) = ε · ε−1(cid:88) ≥ (e − 1) · G(o) − ε · ε−1(cid:88) 0.90
j=1 εj ≥ ε · ε−1(cid:88) j=1 εj ≥ ε · ε−1(cid:88) 0.72
j=1 eεj · G(εj · y(i∗)) , j=1 eεj · G(εj · y(i∗)) , 0.78
where the second inequality holds since the fact that(cid:80)ε−1 第2の不等式は (cid:80)ε−1 が 0.71
j=1 eεj · [G(o) − G(εj · y(i∗))] j=1 eεj · [G(o) − G(εj · y(i∗))] 0.74
j=1 eεj is a geometric sum implies j=1 eεj は幾何和である 0.66
ε · h=1 eεh = ε · eε · eεj − 1 eε − 1 ε · h=1 eεh = ε · eε · eεj − 1 eε − 1 0.75
= ε 1 − e−ε · (eεj − 1) ≥ eεj − 1 . = ε 1 − e-ε · (eεj − 1) ≥ eεj − 1 である。 0.81
17 Lemma 3.16. 17 補題3.16。 0.67
(cid:10)y(i∗),∇ ¯G(y(i∗))(cid:11) ≤ (e + 6ε ln ε−1) · G(y(i∗)) − ε ·(cid:80)ε−1 (cid:10)y(i∗) , sg(y(i∗))(cid:11) ≤ (e + 6ε ln ε−1) · g(y(i∗)) − ε ·(cid:80)ε−1 0.97
j=1 eεj = ε · eε · e − 1 eε − 1 j=1 eεj = ε · eε · e − 1 eε − 1 0.74
= ε 1 − e−ε · (e − 1) ≥ e − 1 . = ε 1 − e−ε · (e − 1) ≥ e − 1 である。 0.85
j=1 eεj · G(εj · y(i∗)). j=1 eεj · g(εj · y(i∗))。 0.88
Proof. In the following calculation, the expression ∇G(εj · y(i∗)) again represents the gradient of the function G(εj · x) at the point x = y(i∗)). 証明。 次の計算では、式 εG(εj · y(i∗)) は再び点 x = y(i∗) における函数 G(εj · x) の勾配を表す。 0.70
Thus, (cid:10)eεj · y(i∗),∇G(εj · y(i∗))(cid:11)  dG(z · y(i∗)) したがって (cid:10)eεj · y(i∗)、\G(εj · y(i∗))(cid:11) > dG(z · y(i∗)) 0.81
= ε · ε−1(cid:88) + ε · eεh · ε−1(cid:88) = ε · ε−1(cid:88) + ε · eεh · ε−1(cid:88) 0.74
j=1 εj (cid:12)(cid:12)(cid :12)(cid:12)z=εh j=1 εj (cid:12)(cid:12)(cid :12)z=εh 0.73
dz j=h dG(z · y(i∗)) dz j=h dG(z · y(i∗)) 0.73
dz (cid:12)(cid:12)(cid :12)(cid:12)z=εj  , dz (cid:12)(cid:12)(cid :12)(cid:12)z=εj , 0.78
dz (cid:12)(cid:12)(cid :12)(cid:12)z=εj dz (cid:12)(cid:12)(cid :12)z=εj 0.83
eεj · dG(z · y(i∗)) eεj · dG(z · y(i∗)) 0.92
(4) (cid:68) (4) (cid:68) 0.82
y(i∗),∇ ¯G(y(i∗)) y(i∗) = yG(y(i∗)) 0.62
where the inequality holds because 不平等が持ちこたえるのは 0.58
ε · ε−1(cid:88) ε · ε−1(cid:88) 0.75
j=1 (cid:69) j=1 (cid:69) 0.69
= ε · ε−1(cid:88) ≤ ε · ε−1(cid:88) j(cid:88) = ε · ε−1(cid:88) ≤ ε · ε−1(cid:88) j(cid:88) 0.77
h=1 h=1 0.59
英語(論文から抽出)日本語訳スコア
We now observe also that the DR-submodularity of G implies, for every integer 1 ≤ h ≤ ε−1, G の DR-部分モジュラリティは、すべての整数 1 ≤ h ≤ ε−1 に対して意味する。 0.76
that ε · ε−1(cid:88) あれ ε · ε−1(cid:88) 0.71
j=h dG(z · y(i∗)) j=h dG(z · y(i∗)) 0.68
dz ≤ h−1 · dG(z · y(i∗)) dz ≤h−1 · dG(z · y(i∗)) 0.78
0 dz dG(z · y(i∗)) 0 dz dG(z · y(i∗)) 0.82
dx + εh dz dx + εh dz 0.83
(cid:12)(cid:12)(cid :12)(cid:12)z=εj (cid:12)(cid:12)(cid :12)z=εj 0.81
(cid:90) εh (cid:90)εh 0.72
(cid:12)(cid:12)(cid :12)(cid:12)z=x (cid:12)(cid:12)(cid :12)z=x 0.86
(cid:90) 1 (cid:12)(cid:12)(cid :12)(cid:12)z=x (cid:90)1 (cid:12)(cid:12)(cid :12)z=x 0.82
dx = h−1 · [G(x · y(i∗))]εh = h−1 · G(εh · y(i∗)) − h−1 · G(¯0) + G(y(i∗)) − G(εh · y(i∗)) ≤ G(y(i∗)) − (1 − h−1) · G(εh · y(i∗)) , dx = h−1 · [G(x · y(i∗))]εh = h−1 · G(εh · y(i∗)) − h−1 · G(εh · y(i∗)) + G(y(i∗)) − G(εh · y(i∗)) ≤ G(y(i∗)) − (1 − h−1) · G(εh · y(i∗)) , 0.90
0 + [G(x · y(i∗))]1 0 + [G(x · y(i∗))]1 0.74
εh where the last inequality follows from the non-negativity of G. Plugging the last inequality now into Inequality (4) yields εh 最後の不等式が g の非負性から続くとき、最後の不等式を不等式 (4) に差し込む 0.65
(cid:69) ≤ G(y(i∗)) + ε · ε−1(cid:88) (cid:104) (cid:69) ≤ G(y(i∗)) + ε · ε−1(cid:88) (cid:104) 0.89
eεj · {G(y(i∗)) − (1 − j−1) · G(εj · y(i∗))}(cid:105) eεj · {G(y(i∗)) − (1 − j−1) · G(εj · y(i∗))} (cid:105) 0.96
y(i∗),∇ ¯G(y(i∗)) y(i∗) = yG(y(i∗)) 0.62
(cid:68) (5) (cid:68) (5) 0.82
(1 − j−1) · eεj · G(εj · y(i∗)) (1 − j−1) · eεj · G(εj · y(i∗)) 0.96
j=1 eεj · G(y(i∗)) − ε · ε−1(cid:88) ε−1(cid:88) j=1 eεj · G(y(i∗)) − ε · ε−1(cid:88) ε−1(cid:88) 0.70
eεj · G(y(i∗)) − ε2 · eεj · G(y(i∗)) − ε2 · 0.98
j=1 j=1 = G(y(i∗)) + ε · ε−1(cid:88) ≤ G(y(i∗)) + ε · ε−1(cid:88) ≤ G(y(i∗)) + ε · ε−1(cid:88) ≤ G(y(i∗)) +(cid:0)ε − 2ε2 ln ε(cid:1) · ε−1(cid:88) j=1 j=1 = G(y(i∗)) + ε · ε−1(cid:88) ≤ G(y(i∗)) + ε · ε−1(cid:88) ≤ G(y(i∗)) + ε · ε−1(cid:88) ≤ G(y(i∗)) + (cid:0)ε − 2ε2 ln ε(cid:1) · ε−1(cid:88) 0.70
j=1 j=1 j=1 j=1 j=1 j=1 0.59
eεj · G(y(i∗)) − ε(1 + 2ε ln ε) · ε−1(cid:88) eεj · G(y(i∗)) − ε · ε−1(cid:88) eεj · G(y(i∗)) − ε(1 + 2ε ln ε) · ε−1(cid:88) eεj · G(y(i∗)) − ε · ε−1(cid:88) 0.92
j=1 (1 − j−1) j=1 (1 − j−1) 0.74
j=1 j=1 eεj · G(εj · y(i∗)) j=1 j=1 eεj · G(εj · y(i∗)) 0.72
  · ε−1(cid:88)   · ε−1(cid:88) 0.77
j=1 eεj · G(εj · y(i∗)) j=1 eεj · G(εj · y(i∗)) 0.79
eεj · G(εj · y(i∗)) , eεj · G(εj · y(i∗)) , 0.98
where the last inequality follows from the monotonicity of G (since 2ε ln ε < 0) and the second inequality follows from Chebyshev’s sum inequality because the monotonicity of G implies that both 1 − j−1 and eεj · G(εj · y(i∗)) are non-decreasing functions of j. Additionally, the penultimate inequality follows due to the following calculation, which holds for every ε ∈ (0, 1/3). 最後の不等式が G の単調性 (since 2ε ln ε < 0) から、第二の不等式がチェビシェフの和の不等式から従うのは、G の単調性は 1 − j−1 と eεj · G(εj · y(i∗)) が j の非減少函数であることを意味するからである。
訳抜け防止モード: 最後の不等式がGの単調性から従う場合(2ε ln ε < 0 ) 2番目の不等式は、G の単調性はどちらも 1 − j−1 であることを意味するため、チェビシェフの和の不等式から従う。 そして eεj · G(εj · y(i∗ ) ) は j の非減少函数である。 下記の計算による不等式 すべての ε ∈ ( 0, 1/3 ) に対して成り立つ。
0.69
(1 − x−1)dx = ε[x − ln x]ε−1 (1 − x−1)dx = ε[x − ln x]ε−1 0.94
1 = 1 − ε + ε ln ε ≥ 1 + 2ε ln ε . 1 = 1 − ε + ε ln ε ≥ 1 + 2ε ln ε . 0.90
To complete the proof of the lemma, it remains to show that the coefficient of G(y(i∗)) in the rightmost side of Inequality (5) is upper bounded by e + 6ε ln ε−1. 補題の証明を完遂するために、不等式 (5) の右辺における G(y(i∗)) の係数が e + 6ε ln ε−1 で上界であることはいまだ証明されていない。 0.74
To do that, we note that this coefficient is そのために、この係数は、 0.51
ε · ε−1(cid:88) ε · ε−1(cid:88) 0.75
(1 − j−1) ≥ ε · (1 − j−1) ≥ ε · 0.96
j=1 1 (cid:90) ε−1 j=1 1 (→90)ε−1 0.69
1 + (ε − 2ε2 ln ε) · ε−1(cid:88) 1 + (ε − 2ε2 ln ε) · ε−1(cid:88) 0.84
j=1 eεj = 1 + (ε − 2ε2 ln ε) · eε · e − 1 eε − 1 1 − 2ε ln ε 1 − ε/2 j=1 eεj = 1 + (ε − 2ε2 ln ε) · eε · e − 1 eε − 1 1 − 2ε ln ε 1 − ε/2 0.74
1 − e−ε · (e − 1) ≤ 1 + (1 − 2ε ln ε)(1 + ε)(e − 1) 1 − e−ε · (e − 1) ≤ 1 + (1 − 2ε ln ε)(1 + ε)(e − 1) 0.94
≤ 1 + = e + ε(e − 1) · [1 − 2(1 + ε) ln ε] ≤ e + 6ε ln ε−1 , ≤ 1 + = e + ε(e − 1) · [1 − 2(1 + ε) ln ε] ≤ e + 6ε ln ε−1 , 0.93
= 1 + ε(1 − 2ε ln ε) = 1 + ε(1 − 2ε ln ε) 0.90
· (e − 1) 18 ·(e − 1) 18 0.85
英語(論文から抽出)日本語訳スコア
where the first inequality and inequalities hold because e−ε ≤ 1 − ε + ε2/2 and (1 − ε/2)−1 ≤ (1 + ε) for ε ∈ (0, 1), and the last inequality holds for ε ∈ (0, 1/4). e-ε ≤ 1 − ε + ε2/2 and (1 − ε/2)−1 ≤ (1 + ε) for ε ∈ (0, 1) であり、最後の不等式は ε ∈ (0, 1/4) である。 0.84
Combining the above lemmas then leads to the following corollary. 上記の補題を組み合わせることで、以下の結論が導かれる。 0.60
Corollary 3.17. G(y(i∗)) + C(y(i∗)) ≥ (1 − 1/e − 4ε ln ε−1) · G(o) + (1 − 4ε ln ε−1) · C(o) − 4εLD2. 登録番号3.17。 G(y(i∗)) + C(y(i∗)) ≥ (1 − 1/e − 4ε ln ε−1) · G(o) + (1 − 4ε ln ε−1) · C(o) − 4εLD2。 0.68
Proof. Observe that (1 − 1/e) · G(o) − (1 + 3ε ln ε−1) · G(y(i∗)) 証明。 観察する (1 − 1/e) · G(o) − (1 + 3ε ln ε−1) · G(y(i∗)) 0.75
≤ e−1 · {[(e − 1) · G(o) − ε · ε−1(cid:88) ≤ e−1 · {[(e − 1) · G(o) − ε · ε−1(cid:88) 1.00
≤ e−1 ·(cid:68) ≤ e−1 ·(cid:68) 0.75
o − y(i∗),∇ ¯G(y(i∗)) o − y(i∗) , = yG(y(i∗)) 0.73
eεj · G(j · y(i∗))] eεj · G(j · y(i∗))] 0.85
− [(e + 6ε ln ε−1) · G(y(i∗)) − ε · ε−1(cid:88) − [(e + 6ε ln ε−1) · G(y(i∗)) − ε · ε−1(cid:88) 0.98
j=1 (cid:69) ≤ ε · F (o) + [C(y(i∗)) − C(o)] + 4εLD2 , j=1 (cid:69) ≤ ε · F (o) + [C(y(i∗)) − C(o)] + 4εLD2 , 0.76
eεj · G(εj · y(i∗))]} eεj · g(εj · y(i∗))]} 0.84
j=1 where the second inequality follows from Lemmata 3.15 and 3.16, and the last inequality follows from Lemma 3.14. j=1 第二の不等式は lemmata 3.15 と 3.16 から、最後の不等式は lemma 3.14 から続く。 0.58
Rearranging the above inequality now yields 上記の不等式を再設定する 0.56
G(y(i∗)) + C(y(i∗)) ≥ (1 − 1/e − ε) · G(o) + (1 − ε) · C(o) − 3ε ln ε−1 · G(y(i∗)) − 4εLD2 G(y(i∗)) + C(y(i∗)) ≥ (1 − 1/e − ε) · G(o) + (1 − ε) · C(o) − 3ε ln ε−1 · G(y(i∗)) − 4εLD2 0.93
≥ (1 − 1/e − 4ε ln ε−1) · G(o) + (1 − 4ε ln ε−1) · C(o) − 4εLD2 , ≥ (1 − 1/e − 4ε ln ε−1) · G(o) + (1 − 4ε ln ε−1) · C(o) − 4εLD2 , 0.88
where the second inequality holds since G(o) + C(o) ≥ G(y(i∗)) + C(y(i∗)) ≥ G(y(i∗)) due to the choice of the vector o and the non-negativity of C. 第二の不等式は G(o) + C(o) ≥ G(y(i∗)) + C(y(i∗)) ≥ G(y(i∗)) から成り立つ。
訳抜け防止モード: 2番目の不等式は、ベクトル o の選択により G(o ) + C(o ) ≥ G(y(i∗ ) ) + C(y(i∗ ) ) ≥ G(y(i∗ ) ) から成り立つ。 そして、C の非負性。
0.90
We are now ready to state and prove Theorem 3.18. 私たちは現在、Theorem 3.18を宣言し、証明する準備ができています。 0.52
Theorem 3.18. Let S be the time it takes to find a point in P maximizing a given linear function, then Algorithm 4 runs in O(ε−2(n/ε + S) ln ε−1) time, makes O(ε−3 ln ε−1) gradient oracle calls, and outputs a vector y such that: 定理3.18。 S を与えられた線型関数の最大化に要する時間を P とし、アルゴリズム4 を O(ε−2(n/ε + S) ln ε−1) 時間で実行し、O(ε−3 ln ε−1) 勾配のオラクル呼び出しを行い、そのようなベクトル y を出力する。 0.72
F (y) ≥ (1 − 1/e − 4ε ln ε−1) · G(o) + (1 − 4ε ln ε−1) · C(o) − 4εLD2 . F (y) ≥ (1 − 1/e − 4ε ln ε−1) · G(o) + (1 − 4ε ln ε−1) · C(o) − 4εLD2 。 0.84
Proof. Once more, we begin by analyzing the time and oracle complexities of the algorithm. 証明。 もう一度、アルゴリズムの時間とoracleの複雑さを分析することから始めます。 0.68
Every iteration of the loop of Algorithm 4 takes O(n/ε + S) time. アルゴリズム4のループの繰り返しは、O(n/ε + S) 時間を要する。 0.79
As there are (cid:100)e−1 · β(ε)/ε−2(cid:101) = O(ε−2 ln ε−1) such iterations, the entire algorithm runs in O(ε−2(n/ε + S) ln ε−1) time. そのような繰り返しが (cid:100)e−1 · β(ε)/ε−2(cid:101) = O(ε−2 ln ε−1) であるように、全アルゴリズムはO(ε−2(n/ε + S) ln ε−1) 時間で実行される。 0.72
Furthermore, as each iteration of the loop requires O(ε−1) oracle calls (a single call to the oracle corresponding to C, and ε−1 calls to the oracle corresponding to G), the overall oracle complexity is O(ε−3 ln ε−1). さらに、ループの各イテレーションはo(ε−1)oracleコール(cに対応するoracleへの単一呼び出し、gに対応するoracleへのε−1呼び出し)を必要とするため、全体的なoracleの複雑さはo(ε−3 ln ε−1)である。
訳抜け防止モード: さらに、ループの各イテレーションでo(ε−1 ) oraclecall(cに対応するoracleへの単一の呼び出し)が必要となる。 そして ε−1 は g に対応する神託を呼び出す オラクル全体の複雑さは o(ε−3 ln ε−1 ) である。
0.83
The theorem now follows since the value of the output of Algorithm 4 is at least as good as F (y(i∗)), and Corollary 3.17 guarantees that F (y(i∗)) ≥ (1− 1/e− 4ε ln ε−1)· G(o) + (1− 4ε ln ε−1)· C(o) − 4εLD2. この定理はアルゴリズム4の出力の値が少なくとも F(y(i∗)) と同程度であることから、Corollary 3.17 は F (y(i∗)) ≥ (1− 1/e− 4ε ln ε−1)· G(o) + (1− 4ε ln ε−1)· C(o) − 4εLD2 を保証する。 0.86
4 Experiments In this section we describe some experiments pertaining to our algorithms for maximizing DRsubmodular + concave functions. 4 実験 この節では、DRsubmodular + concave 関数を最大化するアルゴリズムに関するいくつかの実験について述べる。 0.75
All experiments are done on a 2015 Apple MacBook Pro with a quad-core 2.2 GHz i7 processor and 16 GB of RAM. 2015年のApple MacBook Proにはクアッドコア2.2GHzのi7プロセッサと16GBのRAMが搭載されている。 0.71
19 19 0.85
英語(論文から抽出)日本語訳スコア
Interpolating Between Constrasting Objectives 4.1 We use our algorithms for maximizing the sum of a DR-submodular function and a concave function to provide a way to achieve a trade-off between different objectives. 断定対象間の補間 4.1 当社のアルゴリズムは,dr-submodular関数とconcave関数の和を最大化し,異なる目的間のトレードオフを実現する手段を提供する。 0.80
For example, given a ground set X and a DPP supported on the power set 2X, the maximum a posteriori (MAP) of the DPP corresponds to picking the most likely (diverse) set of elements according to the DPP. 例えば、パワーセット2Xで支持される基底集合 X と DPP が与えられたとき、DPP の最大 A 後部 (MAP) は DPP に従って最も可能性の高い(様々な)要素の集合を選ぶことに対応する。 0.87
On the other hand, concave functions can be used to encourage points being closer together and clustered. 一方、concave関数は、ポイントがより近くなり、クラスタ化されるように促すのに使うことができる。 0.62
a concave function which promotes similarity among elements is C(x) =(cid:80) 要素間の類似性を促進する凹凸関数は、C(x) =(cid:80) 0.80
Finding the MAP of a DPP is an NP-hard problem. DPPのMAPを見つけることはNPハード問題である。 0.85
However, continuous approaches employing the multilinear extension [Călinescu et al , 2011] or the softmax extension [Bian et al , 2017a, Gillenwater et al , 2012] provide strong approximation guarantees for it. しかし、マルチリニア拡張 [c linescu et al , 2011] や softmax extension [bian et al , 2017a, gillenwater et al , 2012] を用いた連続的なアプローチは、それに対する強い近似保証を提供する。 0.83
The softmax approach is usually preferred as it has a closed form solution which is easier to work with. softmaxのアプローチは、作業が容易なクローズドフォームソリューションを持つため、通常は好まれる。 0.69
Now, suppose that |X| = n, and let L be the n × n kernel of the DPP and I be the n × n identity matrix, then G(x) = log det[diag(x)(L − I) + I] is the softmax extension for x ∈ [0, 1]n. Here, diag(x) corresponds to a diagonal matrix with the entries of x along its diagonal. ここで、|X| = n で L を DPP の n × n 個の核とし、I を n × n 個の恒等行列とし、G(x) = log det[diag(x)(L − I) + I] を x ∈ [0, 1]n のソフトマックス拡大とする。
訳抜け防止モード: さて、|x| = n と仮定し、l を dpp の n × n 核とする。 私は n × n の同一性行列です このとき g(x ) = log det[diag(x)(l − i ) + i ] は x ∈ [ 0 のソフトマックス拡大である。 ここでdiag(x)は、その対角線に沿ってxのエントリを持つ対角行列に対応する。
0.77
Observe now that, given a vector x ∈ [0, 1]n, xi can be thought of as the likelihood of picking element i. 現在では、ベクトル x ∈ [0, 1]n が与えられたとき、xi は元 i を選ぶ可能性と考えることができる。 0.71
Moreover, Lij captures the similarity between elements i and j. さらに、Lij は元 i と j の類似性を捉えている。 0.62
Hence, our choice for i,j Lij(1 − (xi − xj)2). したがって、i,j Lij(1 − (xi − xj)2) を選択する。 0.80
The rationale behind this is as follows. その背景にある根拠は次のとおりである。 0.53
For a particular pair of elements i and j, if Lij is large, that means that i and j are similar, so we would want C to be larger when Lij is high, provided that we are indeed picking both i and j (i.e., provided that (xi − xj)2 is small). ある特定の一対の要素 i と j に対して、lij が大きければ、i と j は似ているので、lij が大きければ c も大きければよい(つまり (xi − xj)2 が小さければ)。
訳抜け防止モード: 特定の元 i と j の対に対して、Lij が大きければ、 つまり、i と j は似ているので、Lij が高ければ C をもっと大きくしたい。 i と j (i.e.) の両方を選択しているとすれば xi − xj)2 が小さいと仮定する。
0.75
One can verify that the function C(x) is indeed concave as its Hessian is negative semidefinite. 関数 c(x) が真に凹凸であることは、ヘッシアンが負半定義であることから証明できる。 0.70
In our first experiment we fix the ground set to be the set of 20 × 20 = 400 points evenly spaced in [0, 1] × [0, 1] ⊂ R2. 最初の実験では、基底集合を[0, 1] × [0, 1] × r2 に等間隔に 20 × 20 = 400 個の点の集合とする。 0.71
We also choose L to be the Gaussian kernel Lij = exp(−d(i, j)2/2σ2), where d(i, j) is the Euclidean distance between points i and j, and σ = 0.04. また、L をガウス核 Lij = exp(−d(i, j)2/2σ2) とし、d(i, j) は点 i と j の間のユークリッド距離であり、σ = 0.04 である。 0.77
But to define points i and j, we need some ordering of the 400 points on the plane. しかし、点 i と j を定義するには、平面上の400点の順序が必要となる。 0.69
So, we call point 0 to be at the origin and the index increases till we reach point 19 at (1, 0). したがって、点 0 は原点であり、点 19 が (1, 0) に達するまで指数は増加する。
訳抜け防止モード: したがって、我々は点 0 を原点とみなす。 そして指数は 19 点 ( 1, 0 ) に達するまで増加する。
0.74
Then we have point 20 at (0, 1/20) and so on till we finally reach point 399 at (1, 1). そして、ポイント20を (0, 1/20) とし、最終的にポイント399 at (1, 1) に達する。 0.74
Given the functions G and C defined above, we optimize in this experiment a combined objective formally specified by F = λG + (1 − λ)C, where λ ∈ [0, 1] is a control parameter that can be used to balance the contrasting objectives represented by G and C. For example, setting λ = 1 produces the (spread out) pure DPP MAP solution, setting λ = 0 produces the (clustered) pure concave solution and λ = 0.5 produces a solution that takes both constraints into consideration to some extent. ここで λ ∈ [0, 1] は g と c で表される対照的な目的のバランスをとるのに使用できる制御パラメータである。 例えば、λ = 1 を設定すると (spread out) 純粋な dpp マップの解が生成され、λ = 0 が (クラスタ化された) 純粋な凸解となり、λ = 0.5 は両方の制約をある程度考慮した解を生成する。
訳抜け防止モード: 上述の関数 G と C が与えられたとき、この実験において F = λG + ( 1 − λ)C で正式に定義された組合せ目的を最適化する。 λ ∈ [ 0, 1 ] が制御パラメータであり G と C で表される対照的な目的のバランスをとるために使うことができる。 λ = 1 を設定すると、純粋な DPP MAP 解が生成される。 λ = 0 を設定する クラスターされた)純粋な凹凸溶液を生成し λ = 0.5 は両制約をある程度考慮した解を生成する。
0.85
It is important to note, however, that the effect of changing λ on the importance that each type of constraint gets is not necessarily linear—although it becomes linear when the ranges of G and C happen to be similar. しかしながら、各種類の制約が与える重要性に対するλの変化の影響は必ずしも線型ではない—ただし、g と c の範囲が似ていると線形になる。 0.73
In Figure 2, we can see how changing λ changes the solution. 図2では、λ の変化が解をどう変えるかがわかる。 0.78
The plots in the figure show the final output of Algorithm 3 when run on just the submodular objective G (left plot), just the concave objective C (right plot), and a combination of both (middle plot). 図中のプロットは、サブモジュラー対象g(左プロット)、コンケーブ対象c(右プロット)、および両方の組み合わせ(中間プロット)のみで動作するアルゴリズム3の最終出力を示す。
訳抜け防止モード: 図中のプロットは、サブモジュラー目的g(左プロット)だけを実行するとアルゴリズム3の最終出力を示す。 concave objective c ( right plot ) と both ( middle plot ) の組み合わせだけである。
0.72
The algorithm is run with the same cardinality constraint of 25 in all plots, which corresponds to imposing that the (cid:96)1 norm of each iteratation must be at most 25. このアルゴリズムはすべてのプロットにおいて25の濃度制約で実行され、これは各反復の (cid:96)1 ノルムが25 以上でなければならないことを示すものである。 0.74
It is important to note that we represent the exact (continuous) output of the algorithm here. ここではアルゴリズムの正確な(連続的な)出力を表すことに注意する必要がある。 0.81
To get a discrete solution, a rounding method should be applied. 離散解を得るには、丸め法を適用する必要がある。 0.67
Also, all of the runs of the algorithm begin from the same fixed starting point inside the cardinality constrained polytope. また、アルゴリズムの全ての実行は、濃度制限されたポリトープ内の同じ固定開始点から開始される。 0.74
The step sizes used by the different runs are all constant, and were chosen empirically. 異なるランで使用されるステップサイズはすべて一定であり、経験的に選択される。 0.69
20 20 0.85
英語(論文から抽出)日本語訳スコア
Figure 2: Outputs of the experiment described in Section 4.1. 図2: セクション4.1に記載された実験の成果。 0.70
Left Plot: λ = 1 (just the submodular objective). 左プロット: λ = 1 (ただのモジュラー対象)。 0.65
Right Plot: λ = 0 (just the concave objective). 右プロット (right plot): λ = 0 (concave objective)。 0.88
Middle Plot: 0 < λ < 1 (combination of both objectives). 中間プロット: 0 < λ < 1 (両方の目的の組合せ)。 0.72
A darker square corresponds to a larger entry in the final output of Algorithm 3 for the corresponding element. より暗い二乗は、対応する要素に対するアルゴリズム3の最終出力のより大きなエントリに対応する。 0.75
4.2 Other Submodular + Concave Objectives In this section we compare our algorithms with two baselines: the Frank-Wolfe algorithm [Frank and Wolfe, 1956] and the projected gradient ascent algorithm. 4.2 その他の部分モジュラー + concave 目的 この節では、我々のアルゴリズムをフランク・ウルフアルゴリズム [frank and wolfe, 1956] と投影勾配上昇アルゴリズムの2つのベースラインと比較します。 0.72
In all the experiments done in this section, the objective function is again F = λG + (1 − λ)C, where G and C are a DR-submodular function and a concave function, respectively. この節で行ったすべての実験において、目的関数は再び F = λG + (1 − λ)C であり、G と C はそれぞれ DR-部分モジュラ函数と凹函数である。 0.83
For simplicity, we set λ = 1/2 throughout the section. 単純性のため、区間全体を通して λ = 1/2 を定める。 0.64
4.2.1 Quadratic Programming 2 x(cid:62)Hx + h(cid:62)x + c. Note that by choosing an appropriate matrix In this section, we define G(x) = 1 H and vector h, this objective can be made to be monotone or non-monotone DR-submodular. 4.2.1 二次計画法 2 x(cid:62)Hx + h(cid:62)x + c. この節では、適切な行列を選択することにより、G(x) = 1 H とベクトル h を定義することにより、この目的を単調あるいは非単調なDR-部分モジュラーにすることができる。
訳抜け防止モード: 4.2.1 二次計画法 2 x(cid:62)Hx + h(cid:62)x + c. 適切な行列を選択することで注意。 我々は G(x ) = 1 H とベクトル h を定義する。 to be monotone or non-monotone DR - submodular.
0.82
We +}. we +} である。 0.69
, b ∈ Rm also define the down-closed constraint set to be P = {x ∈ Rn Following Bian et al [2017a], we choose the matrix H ∈ Rn×n to be a randomly generated symmetric matrix with entries uniformly distributed in [−1, 0], and the matrix A to be a random matrix with entries uniformly distributed in [0.01, 1.01] (the 0.01 addition here is used to ensure that the entries are all positive). Bian et al [2017a] に従えば、行列 H ∈ Rn×n を [−1, 0] に一様に分布する成分を持つランダムな対称行列とし、行列 A を [0.01, 1.01] に一様に分布する成分を持つランダムな行列とする(ここでの 0.01 の追加は、成分がすべて正であることを保証するために用いられる)。
訳抜け防止モード: ,b ∈ Rm はまた、下向き閉制約集合を P = { x ∈ Rn と定義する。 行列 H ∈ Rn×n を [ −1, 0 ] に一様に分布するランダムに生成される対称行列として選ぶ。 そして行列 A は [ 0.01, 1.01 ] に一様に分布する成分を持つランダム行列となる(ここでの 0.01 の追加は、成分がすべて正であることを保証するために使われる)。
0.84
The vector b is chosen as the all ones vector, and the vector u is a tight upper bound on P whose ith coordinate is defined as ui = minj∈[m] bj/Aji. ベクトル b はすべてのベクトルとして選ばれ、ベクトル u は p 上のタイトな上界であり、その ih 座標は ui = minjhtml[m] bj/aji と定義される。 0.86
We let h = −0.2 · H(cid:62)u which makes G non-monotone. G を非単調にする h = −0.2 · H(cid:62)u とする。 0.70
Finally, although this does not affect the results of our experiments, we take c to be a large enough additive constant (in this case 10) to make G non-negative. 最後に、これは我々の実験の結果には影響しないが、我々は c を G を非負にするために十分大きい加法定数(この場合 10)とする。 0.79
+ | Ax ≤ b, x ≤ u, A ∈ Rm×n + | Ax ≤ b, x ≤ u, A ∈ Rm×n 0.85
+ It is know that when the Hessian of a quadratic program is negative semidefinite, the resulting 20 x(cid:62)Dx, where D is a negative semidefinite objective is concave. + 二次プログラムの Hessian が負半定値であるとき、結果として得られる 20 x(cid:62)Dx は D が負半定値の目的である。 0.80
Accordingly, we let C(x) = 1 matrix defined by the negation of the product of a random matrix with entries in [0, 1] with its transpose. したがって、c(x) = 1 行列を、[0, 1] のエントリとその転置を持つランダム行列の積の否定によって定義される。 0.69
As one can observe, the generality of DR-submodular + concave objectives allows us to consider quadratic programming with very different Hessians. 観察できるように、dr-submodular + concave の目的の一般性は、非常に異なるヘッシアンを持つ二次計画を考えることができる。
訳抜け防止モード: 観察できるように、dr-submodular + concave objectives の一般性は 全く異なるヘッシアンを持つ二次計画を考えること。
0.64
We hope that our ability to do this will motivate future work about quadratic programming for a broader class of Hessian matrices. 我々は、これを行う能力が、より広範なヘッセン行列のクラスに対する二次プログラミングの将来の仕事の動機となることを望んでいる。 0.57
In the current experiment, we let n ∈ {8, 12, 16} and m ∈ {0.5n, n, 1.5n}, and run each algorithm for 50 iterations. 現在の実験では、n ∈ {8, 12, 16} と m ∈ {0.5n, n, 1.5n} を各アルゴリズムで50回の反復を行う。 0.89
Note that having fixed the number of iterations, the maximum step size for Algorithms 1 and 2 is upper bounded by (number of iterations)−1 = 1/50 to guarantee that these algorithms remain within the polytope. 反復数を固定すると、アルゴリズム1とアルゴリズム2の最大ステップサイズは(反復数)−1 = 1/50で上限され、これらのアルゴリズムがポリトープ内に留まることを保証する。 0.76
To ensure consistency, we set the step sizes for the other algorithms to be 1/50 as well, except for Algorithm 4 for which we set to the value of ε given by solving e−1 · β(ε)/ε2 = 50. 一貫性を確保するため、e−1 · β(ε)/ε2 = 50 を解くことによって与えられる ε の値に設定するアルゴリズム 4 を除いて、他のアルゴリズムのステップサイズも 1/50 に設定する。 0.85
This ensures that the gradient computation in Algorithm 4 is not too time consuming. これにより、アルゴリズム4の勾配計算に時間がかかりすぎないことが保証される。 0.63
We start Algorithms 1 and 2 from the starting point their pseudocodes specify, 擬似コードが指定した開始点からアルゴリズム1と2を起動する。 0.74
21 21 0.85
英語(論文から抽出)日本語訳スコア
and the other algorithms from the same arbitrary point. 同じ任意の点の他のアルゴリズムもです 0.69
We show the results for the aforementioned values of n and m in Figure 3. 上述した n および m の値の結果を図 3 に示す。 0.67
The appropriate values of n and m are mentioned below each plot, and each plot graphs the average of 50 runs of the experiment. n と m の適切な値は各プロットの下に記述され、各プロットは実験の50ランの平均をグラフ化する。 0.78
We also note that since Algorithms 3 and 4 output the best among the results of all their iterations, we just plot the final output of these algorithms instead of the entire trajectory. また、アルゴリズム3と4は、すべてのイテレーションの結果の中で最良の結果を出力するので、軌道全体ではなく、これらのアルゴリズムの最終出力をプロットするだけです。 0.79
4.2.2 D-optimal Experimental Design Following Chen et al [2018], the DR-submodular objective function for the D-optimal experimental 4.2.2 D-optimal Experimental Design following Chen et al [2018], the DR-submodular objective function for the D-optimal experimental 0.82
(cid:1). Here, Yi is an n dimensional row-vector in which (cid:1)。 ここで、Yi は n 次元の行ベクトルである。 0.71
design problem is G(x) = log det(cid:0)(cid:80)n 設計上の問題は G(x) = log det(cid:0)(cid:80)n 0.81
each entry is drawn independently from the standard Gaussian distribution. 各エントリは標準ガウス分布から独立して引き出される。 0.80
The choice of concave function is C(x) = 1 i=1 log(xi). 凹函数の選択は C(x) = 1 i=1 log(xi) である。 0.86
In this experiment there is no combinatorial constraint. この実験では組合せ制約は存在しない。 0.78
Instead, we are interested in maximization over a box constraint, i.e., over [1, 2]n (note that the box is shifted compared to the standard [0, 1]n to ensure that G is defined everywhere as it is undefined at x = 0). 代わりに、ボックス制約、すなわち[1, 2]n 上の最大化に関心があります(x = 0 で定義されていないように g がどこでも定義されるように、ボックスが標準 [0, 1]n と比較されるように注意してください)。 0.75
The final outputs of all the algorithms for n = 8, 12, 16 appear in Figure 3j. n = 8, 12, 16 の全てのアルゴリズムの最終的な出力は図 3j に現れる。 0.89
Like in Section 4.2.1, each algorithm was run for 50 iterations, and each plot is the average of 50 runs. セクション4.2.1のように、各アルゴリズムは50回実行され、各プロットは平均50回実行された。 0.75
The step sizes and starting points used by the algorithms are set exactly like in Section 4.2.1. ステップサイズとアルゴリズムが使用するスタートポイントは、セクション4.2.1と全く同じである。 0.68
10 (cid:80)n 10 (cid:80)n 0.85
i=1 xiY(cid:62) i=1 xiY(cid:62) 0.71
i Yi Takeaways. i Yi 持ち帰り。 0.66
Based on our experiments, we can observe that Algorithms 1 and 4 consistently outperform the other algorithms. 実験結果から, 1 と 4 のアルゴリズムが他のアルゴリズムよりも一貫して優れていることが分かる。 0.76
We can also see (especially in the D-optimal experimental design problem where they almost superimpose) that the difference between Algorithm 3 and the standard Frank-Wolfe algorithm are minimal, but we believe that the difference between the two algorithms can be made more pronounced by considering settings in which the gradient of C dominates the gradient of G. Finally, one can note that the output values in the plots corresponding to the quadratic programming problem discussed in Section 4.2.1 tend to decrease when the number of constraints increases, which matches our intuitive expectation. We can also see (especially in the D-optimal experimental design problem where they almost superimpose) that the difference between Algorithm 3 and the standard Frank-Wolfe algorithm are minimal, but we believe that the difference between the two algorithms can be made more pronounced by considering settings in which the gradient of C dominates the gradient of G. Finally, one can note that the output values in the plots corresponding to the quadratic programming problem discussed in Section 4.2.1 tend to decrease when the number of constraints increases, which matches our intuitive expectation. 0.96
5 Conclusion In this paper, we have considered the maximization of a class of objective functions that is strictly larger than both DR-submodular functions and concave functions. 5 結論 この論文では,DR-部分モジュラ関数と凹関数の双方よりも厳密に大きい対象関数のクラスを最大化することを検討した。 0.79
The ability to optimize this class of functions using first-order information is interesting from both theoretical and practical points of view. このクラスの関数を一階情報を用いて最適化する能力は、理論的および実践的な観点から興味深い。 0.77
Our results provide a step towards the goal of efficiently analyzing structured non-convex functions—a goal that is becoming increasingly relevant. この結果から,非凸関数を効率的に解析する目標に向けてのステップが得られた。 0.59
(a) n = 8, m = 4 (a)n = 8, m = 4 0.84
(b) n = 8, m = 8 (b)n = 8, m = 8 0.84
22 22 0.85
英語(論文から抽出)日本語訳スコア
(c) n = 8, m = 12 (c)n = 8, m = 12 0.84
(d) n = 12, m = 6 (d)n = 12, m = 6 0.84
(e) n = 12, m = 12 (e)n = 12, m = 12 0.84
(f) n = 12, m = 18 (f)n = 12, m = 18 0.84
(g) n = 16, m = 8 (g)n = 16,m = 8 0.83
(h) n = 16, m = 16 (h)n = 16,m = 16 0.82
(i) n = 16, m = 24 (i)n = 16,m = 24 0.83
(j) Final outputs for the D-optimal design problem. (j) D-最適設計問題の最終的な出力。 0.81
Figure 3: All the plots except for 3j correspond to the quadratic programming experiment from Section 4.2.1. 図3: 3j以外のプロットはすべて、セクション4.2.1の二次プログラミング実験に対応する。 0.69
For these plots, the dimension (n) and the number of constraints (m) is mentioned below each plot. これらのプロットに対して、次元 (n) と制約数 (m) は各プロットの下に記述される。 0.77
Plot 3j pertains to the D-optimal experimental design problem from Section 4.2.2. Plot 3jはセクション4.2.2のD最適設計問題に関連する。 0.57
23 23 0.85
英語(論文から抽出)日本語訳スコア
References Ayya Alieva, Aiden Aceves, Jialin Song, Stephen Mayo, Yisong Yue, and Yuxin Chen. 参照: Ayya Alieva, Aiden Aceves, Jialin Song, Stephen Mayo, Yisong Yue, Yuxin Chen。 0.74
Learning In International Conference on Learning 学習に関する国際会議に参加して 0.70
to make decisions via submodular regularization. サブモジュラー正規化による決定を行う。 0.59
Representations, 2021. Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. 表題は2021年。 zeyuan allen-zhu, yuanzhi li, yingyu liang。 0.62
Learning and generalization in overparameterized neural networks, going beyond two layers. 過パラメータ化されたニューラルネットワークの学習と一般化。 0.60
In Advances in Neural Information Processing Systems, 2019. 2019年 ニューラル・インフォメーション・プロセッシング・システムの進歩。 0.46
Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. Nima Anari, Shayan Oveis Gharan, Alireza Rezaei 0.57
Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes. 強いレイリー分布と行列点過程をサンプリングするためのモンテカルロマルコフ連鎖アルゴリズム 0.71
In 29th Annual Conference on Learning Theory, 2016. 第29回学習理論会議(2016年)に参加して 0.67
Sanjeev Arora, Rong Ge, Ravi Kannan, and Ankur Moitra. sanjeev arora, rong ge, ravi kannan, and ankur moitra。 0.62
Computing a nonnegative matrix factorization – provably. 非負行列分解の計算 – 確実に。 0.72
In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012. 第44回年次acmコンピューティング理論シンポジウムの開催にあたって 0.61
An Bian, Kfir Y. ビアン、Kfir Y。 0.61
Levy, Andreas Krause, and Joachim M. Buhmann. Levy, Andreas Krause, Joachim M. Buhmann 0.72
Continuous dr-submodular maximization: Structure and algorithms. dr-submodular maximization: 構造とアルゴリズム。 0.82
In Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017a. 第31回神経情報処理システム国際会議(2017a)に参加して 0.72
An Bian, Joachim M. Buhmann, and Andreas Krause. ビアン、joachim m. buhmann、andreas krause。 0.42
Optimal dr-submodular maximization and applications to provable mean field inference. 最適dr-submodular maximizationと証明可能な平均場推論への応用 0.72
In Proceedings of the 36th International Conference on Machine Learning, 2019. 第36回In Proceedings of the 36th International Conference on Machine Learning, 2019 0.87
Andrew An Bian, Baharan Mirzasoleiman, Joachim M. Buhmann, and Andreas Krause. Andrew An Bian, Baharan Mirzasoleiman, Joachim M. Buhmann, and Andreas Krause 0.81
Guaranteed non-convex optimization: Submodular maximization over continuous domains. 保証された非凸最適化: 連続領域に対する部分モジュラ最大化。 0.54
In AISTATS, 2017b. 2017年、AISTATS。 0.69
Guy Bresler, Frederic Koehler, Ankur Moitra, and Elchanan Mossel. Guy Bresler、Frederic Koehler、Ankur Moitra、Elchanan Mossel。 0.68
Learning restricted boltzmann machines via influence maximization. 影響最大化による制限ボルツマンマシンの学習 0.72
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019. 第51回ACM SIGACT Symposium on Theory of Computing, 2019 に参加して 0.70
Sébastien Bubeck. Sébastien Bubeck 0.57
Convex optimization: Algorithms and complexity. 凸最適化: アルゴリズムと複雑性。 0.77
Found. Trends Mach. 見つかった トレンドマッハ。 0.58
Learn., 2015. Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. 学ぶ。 2015. Gruia C'linescu、Chandra Chekuri、Martin Pál、Jan Vondrák。 0.71
Maximizing a monotone submodular function subject to a matroid constraint. モノトーンの最大化 マトロイド制約を受ける部分モジュラー関数。 0.63
SIAM J. Comput., 2011. SIAM J。 2011年、同上。 0.71
Lin Chen, Hamed Hassani, and Amin Karbasi. リン・チェン、ハメド・ハッサーニ、アミン・カルバシ。 0.45
Online continuous submodular maximization. オンライン連続サブモジュラー最大化。 0.61
In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, 2018. 2018年、第21回人工知能と統計に関する国際会議が開催された。 0.67
Lin Chen, Moran Feldman, and Amin Karbasi. リン・チェン、モラン・フェルドマン、アミン・カルバシ。 0.47
Unconstrained submodular maximization with constant adaptive complexity. 一定の適応複雑性を持つ非制約部分モジュラー最大化。 0.57
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, 2019a. 第51回ACM SIGACT Symposium on Theory of Computing, STOC 2019, 2019a に参加して 0.78
Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma 0.63
Gradient descent with random initialization: ランダム初期化による勾配降下: 0.77
fast global convergence for nonconvex phase retrieval. 非凸位相探索のための高速グローバル収束 0.72
Mathematical Programming, 2019b. 数学プログラミング、2019年。 0.75
24 24 0.85
英語(論文から抽出)日本語訳スコア
Michal Derezinski, Feynman Liang, and Michael Mahoney. Michal Derezinski、Feynman Liang、Michael Mahoney。 0.70
Bayesian experimental design using regularized determinantal point processes. 正規化決定点過程を用いたベイズ実験設計 0.78
In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 2020. 第20回人工知能・統計国際会議(2020年)に参加して 0.58
Josip Djolonga and Andreas Krause. josip djolongaとandreas krause。 0.44
From map to marginals: Variational inference in bayesian 地図から縁まで:ベイジアンにおける変分推論 0.71
submodular models. サブモジュラーモデル。 0.74
In Advances in Neural Information Processing Systems, 2014. ニューラル情報処理システム(2014年)の進歩 0.70
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Simon S. Du, Xiyu Zhai, Barnabas Poczos, Aarti Singh 0.72
Gradient descent provably optimizes over-parameterized neural networks. 勾配降下は、過剰パラメータ化されたニューラルネットワークを最適化する。 0.42
In International Conference on Learning Representations, 2019. International Conference on Learning Representations, 2019に参加。 0.86
Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, and Bin Yu. Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, Bin Yu 0.69
Log-concave sampling: Metropolis- ログコンケーブサンプリング:メトロポリス- 0.58
hastings algorithms are fast. ヘイスティングスアルゴリズムは高速です。 0.73
Journal of Machine Learning Research, 2019. Journal of Machine Learning Research、2019年。 0.80
Ethan R. Elenberg, Rajiv Khanna, Alexandros G. Dimakis, and Sahand Negahban. Ethan R. Elenberg, Rajiv Khanna, Alexandros G. Dimakis, Sahand Negahban 0.79
Restricted strong convexity implies weak submodularity. 制限された強い凸性は弱い部分モジュラリティを意味する。 0.40
In Proceedings of the 30th Conference on Neural Information Processing Systems, 2016. 2016年度第30回ニューラル情報処理システム学会講演会報告 0.58
Ethan R. Elenberg, Alexandros G. Dimakis, Moran Feldman, and Amin Karbasi. Ethan R. Elenberg, Alexandros G. Dimakis, Moran Feldman, Amin Karbasi 0.79
Streaming weak submodularity: Interpreting neural networks on the fly. streaming weak submodularity: ニューラルネットワークをオンザフライで解釈する。 0.78
In Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017. 2017年第31回ニューラル情報処理システム国際会議の開催報告 0.63
Alina Ene and Huy L. Nguyen. アリーナ・エネとHuy L. Nguyen。 0.59
Parallel algorithm for non-monotone dr-submodular maximization. 非単調drサブモジュラー最大化のための並列アルゴリズム 0.58
In Proceedings of the 37th International Conference on Machine Learning, 2019. 第37回In Proceedings of the 37th International Conference on Machine Learning, 2019 0.86
Alina Ene, Sofia Maria Nikolakaki, and Evimaria Terzi. アリナ・エネ、ソフィア・マリア・ニコラカキ、エヴィマリア・テルジ。 0.60
Team formation: Striking a balance between チーム形成: バランスをとる 0.63
coverage and cost. カバレッジとコスト。 0.50
CoRR, 2020. CoRR、2020年。 0.86
Moran Feldman. モラン・フェルドマン。 0.58
Guess free maximization of submodular and linear sums. 準モジュラー和と線型和の誘導自由最大化。 0.58
Algorithmica, 2021. アルゴリズム、2021年。 0.70
Moran Feldman, Joseph Naor, and Roy Schwartz. Moran Feldman、Joseph Naor、Roy Schwartz。 0.70
A unified continuous greedy algorithm for submodular maximization. 部分モジュラ最大化のための統一的連続グリードアルゴリズム 0.72
In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011. 2011年、IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011。 0.83
Yuval Filmus and Justin Ward. ユーバル・フィルムスとジャスティン・ウォード。 0.46
A tight combinatorial algorithm for submodular maximization In 2012 IEEE 53rd Annual Symposium on Foundations of 2012年度ieee第53回年次シンポジウムにおける亜モジュラー最大化のためのタイトコンビネーションアルゴリズム 0.73
subject to a matroid constraint. マトロイドの制約を受ける。 0.60
Computer Science, 2012. コンピュータ科学、2012年。 0.80
Marguerite Frank and Philip Wolfe. マルグリット・フランクとフィリップ・ウルフ 0.63
An algorithm for quadratic programming. 二次プログラミングのためのアルゴリズム。 0.71
Naval Research Logistics Quarterly, 1956. 海軍研究 昭和31年(1956年) 0.56
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Rong Ge,Furong Huang,Chi Jin,Yang Yuan。 0.67
Escaping from saddle points — online stochastic gradient for tensor decomposition. サドルポイントからの脱出 – テンソル分解のためのオンライン確率勾配。 0.57
In Proceedings of The 28th Conference on Learning Theory, 2015. 2015年、第28回学習理論会議を開催。 0.71
J. Gillenwater, A. Kulesza, and B. Taskar. J. Gillenwater、A. Kulesza、B. Taskar。 0.91
Near-Optimal MAP Inference for Determinantal Point 決定点に対する近接最適MAP推定 0.73
Processes. In Proc. プロセス。 Proc。 0.64
Neural Information Processing Systems (NIPS), 2012. Neural Information Processing Systems (NIPS) 2012年。 0.79
Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. クリス・ハーショー、モラン・フェルドマン、ジャスティン・ウォード、アミン・カルバシ。 0.52
Submodular maximization beyond 部分モジュラー最大化 0.60
non-negativity: Guarantees, fast algorithms, and applications. 非否定性:保証、高速アルゴリズム、アプリケーション。 0.69
In ICML, 2019. 2019年、ICML入社。 0.80
25 25 0.85
英語(論文から抽出)日本語訳スコア
Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. ハメド・ハサニ、マフディー・ソルタノールコタビ、アミン・カルバシ。 0.43
Gradient methods for submodular maximization. サブモジュラー最大化のための勾配法 0.64
In Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017. 2017年第31回ニューラル情報処理システム国際会議の開催報告 0.63
Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Hamed Hassani、Amin Karbasi、Aryan Mokhtari、Zebang Shen。 0.63
Stochastic conditional gradient++: (non)convex minimization and continuous submodular maximization. 確率条件勾配++:(非)凸最小化と連続部分モジュラ最大化。 0.63
SIAM Journal on Optimization, 2020a. SIAM Journal on Optimization, 2020a 0.79
Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Hamed Hassani、Amin Karbasi、Aryan Mokhtari、Zebang Shen。 0.63
Stochastic conditional gradi- ent++, 2020b. 確率条件グラディ ent++, 2020b。 0.73
Elad Hazan, Kfir Y. Elad Hazan, Kfir Y。 0.82
Levy, and Shai Shalev-Shwartz. LevyとShai Shalev-Shwartz。 0.87
On graduated optimization for stochastic non-convex problems. 確率的非凸問題に対する逐次最適化について 0.47
In Proceedings of The 33rd International Conference on Machine Learning, 2016. 2016年、第33回機械学習国際会議が開催された。 0.80
Xiaofei He. Xiaofei (複数形 Xiaofeis) 0.45
Laplacian regularized d-optimal design for active learning and its application to image ラプラシアン正則化d-optimal design for active learning and its application to image 0.82
retrieval. IEEE Transactions on Image Processing, 2010. 検索。 IEEE Transactions on Image Processing, 2010 (英語) 0.70
Arthur Jacot, Franck Gabriel, and Clément Hongler. アーサー・ジャコット、フランク・ガブリエル、クレマン・ホンラー。 0.50
Neural tangent kernel: Convergence and generalization in neural networks. ニューラルタンジェントカーネル:ニューラルネットワークの収束と一般化。 0.67
In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018. 第32回神経情報処理システム国際会議に参加して 0.60
Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Ehsan Kazemi、Shervin Minaee、Moran Feldman、Amin Karbasi。 0.66
Regularized submodular 正規化部分モジュラー 0.52
maximization at scale. CoRR, 2020a. 規模の最大化です CRR、2020年。 0.77
Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Ehsan Kazemi、Shervin Minaee、Moran Feldman、Amin Karbasi。 0.66
Regularized submodular 正規化部分モジュラー 0.52
maximization at scale. CoRR, 2020b. 規模の最大化です CoRR、2020年。 0.78
David Kempe, Jon Kleinberg, and Éva Tardos. David Kempe、Jon Kleinberg、Éva Tardos。 0.66
Maximizing the spread of influence through a social network. ソーシャルネットワークによる影響力の広がりを最大化する。 0.77
In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03. 第9回ACM SIGKDD国際知識発見・データマイニング会議(KDD'03)の開催報告 0.61
Association for Computing Machinery, 2003. アソシエーション・フォー・コンピューティング・マシンズ、2003年。 0.53
Andreas Krause and Volkan Cevher. アンドレアス・クラウスとヴォルカン・セヴァー。 0.49
Submodular dictionary selection for sparse representation. スパース表現のための部分モジュラ辞書選択 0.61
In Proceedings of the 27th International Conference on International Conference on Machine Learning, 2010. 2010年第27回国際機械学習会議(international conference on machine learning)開催。 0.76
Alex Kulesza. Alex Kulesza 0.58
Determinantal point processes for machine learning. 機械学習のための決定点プロセス。 0.77
Foundations and Trends® in Machine Learning, 2012. 基礎とトレンド® 2012年、機械学習。 0.74
Tor Lattimore and Csaba Szepesvari. Tor LattimoreとCsaba Szepesvari。 0.80
Bandit algorithms. バンディットアルゴリズム。 0.61
Cambridge University Press, 2020. ケンブリッジ大学出版局、2020年。 0.66
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Baharan Mirzasoleiman、Amin Karbasi、Rik Sarkar、Andreas Krause。 0.65
Distributed submodular In Advances in Neural 神経の進歩における分散サブモジュラー 0.62
maximization: Identifying representative elements in massive data. 最大化: 大規模データにおける代表要素の識別。 0.67
Information Processing Systems, 2013. 情報処理システム、2013年。 0.77
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Aryan Mokhtari, Hamed Hassani, Amin Karbasi 0.60
Conditional gradient method for stochastic submodular maximization: Closing the gap. 確率的部分モジュラー最大化のための条件勾配法:ギャップを閉じる 0.65
In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, 2018a. 第20回人工知能・統計国際会議(2018a)に参加して 0.51
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Aryan Mokhtari, Hamed Hassani, Amin Karbasi 0.60
Decentralized submodular maximization: Bridging discrete and continuous settings. 分散サブモジュラー最大化:離散的かつ連続的な設定をブリッジする。 0.52
In Proceedings of the 35th International Conference on Machine Learning, 2018b. 第35回In Proceedings of the 35th International Conference on Machine Learning, 2018b 0.83
26 26 0.85
英語(論文から抽出)日本語訳スコア
K. G. Murty and S. N. Kabadi. k. g. murtyとs. n. kabadi。 0.47
Some np-complete problems in quadratic and nonlinear programming. 二次および非線形計画におけるnp完全問題。 0.54
Mathematical Programming, 1987. 1987年、数学教授。 0.68
Yurii Nesterov. Yurii Nesterov 0.58
Lectures on Convex Optimization. 凸最適化に関する講義 0.70
Springer Publishing Company, Incorporated, Springer Publishing Company, Incorporated 0.70
2018. Praneeth Netrapalli, U N Niranjan, Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain. 2018. Praneeth Netrapalli, U N Niranjan, Sujay Sanghavi, Animashree Anandkumar, Prateek Jain 0.77
Non-convex robust pca. 非凸ロバストpca。 0.44
In Advances in Neural Information Processing Systems, 2014. ニューラル情報処理システム(2014年)の進歩 0.70
Rad Niazadeh, Tim Roughgarden, and Joshua R. Wang. Rad Niazadeh、Tim Roughgarden、Joshua R. Wang。 0.71
Optimal algorithms for continuous nonmonotone submodular and dr-submodular maximization. 連続非単調部分モジュラーおよびDrサブモジュラー最大化のための最適アルゴリズム 0.62
In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018. 第32回神経情報処理システム国際会議に参加して 0.60
Prasanna Sanjay Raut, Omid Sadeghi, and Maryam Fazel. Prasanna Sanjay Raut、Omid Sadeghi、Maryam Fazel。 0.69
Online dr-submodular maximization オンラインDrサブモジュラー最大化 0.44
with stochastic cumulative constraints, 2021. 2021年の確率的累積制約で 0.65
Patrick Rebeschini and Amin Karbasi. Patrick RebeschiniとAmin Karbasi。 0.76
Fast mixing for discrete point processes. 離散点過程に対する高速混合 0.68
In Proceedings of in Proceedings of ~ 0.79
The 28th Conference on Learning Theory, 2015. 第28回学習理論会議2015参加報告 0.70
Joshua Robinson, Suvrit Sra, and Stefanie Jegelka. Joshua Robinson、Suvrit Sra、Stefanie Jegelka。 0.59
Flexible modeling of diversity with strongly 強靭な多様性のフレキシブルモデリング 0.81
log-concave distributions. log-concave 分布。 0.68
In Advances in Neural Information Processing Systems, 2019. 2019年 ニューラル・インフォメーション・プロセッシング・システムの進歩。 0.46
Omid Sadeghi and Maryam Fazel. オミド・サデギとメアリー・ファゼル。 0.46
Online continuous DR-submodular maximization with long-term budget constraints. 長期予算制約を伴うオンライン連続DR-サブモジュラー最大化 0.61
In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 2019. 第23回人工知能と統計に関する国際会議の議事録、2019年。 0.69
Omid Sadeghi, Prasanna Raut, and Maryam Fazel. Omid Sadeghi, Prasanna Raut, Maryam Fazel。 0.70
A single recipe for online submodular maximization with adversarial or stochastic constraints. 逆あるいは確率的制約を伴うオンラインサブモジュラー最大化のための単一のレシピ。 0.66
In Advances in Neural Information Processing Systems, 2020. ニューラル情報処理システムの進歩 -2020年- 0.68
Adish Singla, Ilija Bogunovic, Gábor Bartók, Amin Karbasi, and Andreas Krause. Adish Singla、Ilija Bogunovic、Gábor Bartók、Amin Karbasi、Andreas Krause。 0.68
Near-optimally teaching the crowd to classify. 群衆に分類を最適に教える。 0.64
In Proceedings of the 31st International Conference on International Conference on Machine Learning, 2014. 第31回機械学習国際会議(international conference on machine learning, 2014)で開催。 0.83
Matthew Staib and Stefanie Jegelka. マシュー・ステイブと ステファニー・ジェルカ 0.47
Robust budget allocation via continuous submodular functions. 連続サブモジュラー関数によるロバストな予算割り当て。 0.64
In Proceedings of the 34th International Conference on Machine Learning, 2017. 2017年度第34回機械学習国際会議の開催報告 0.61
Ju Sun, Qing Qu, and John Wright. Ju Sun、Qing Qu、John Wright。 0.68
When are nonconvex problems not scary?, 2016. 非凸問題はいつ、怖くないのか? 0.52
Ruoyu Sun and Zhi-Quan Luo. ルオユ・サンとジ・クァン・ルオ。 0.41
Guaranteed matrix completion via non-convex factorization. 非凸因子化による行列補完の保証 0.59
IEEE Transactions on Information Theory, 2016. IEEE transactions on information theory、2016年。 0.81
Maxim Sviridenko, Jan Vondrák, and Justin Ward. Maxim Sviridenko、Jan Vondrák、Justin Ward。 0.66
Optimal approximation for submodular and 部分モジュラーと最適近似 0.59
supermodular optimization with bounded curvature. 有界曲率による超モジュラー最適化 0.67
Math. Oper. Res., 2017. 数学。 Oper 2017年、退団。 0.62
Ehsan Tohidi, Rouhollah Amiri, Mario Coutino, David Gesbert, Geert Leus, and Amin Karbasi. Ehsan Tohidi, Rouhollah Amiri, Mario Coutino, David Gesbert, Geert Leus, Amin Karbasi 0.71
Submodularity in action: From machine learning to signal processing applications. 動作のサブモジュール性: マシンラーニングから信号処理アプリケーションまで。 0.80
IEEE Signal Processing Magazine, 2020. IEEE Signal Processing Magazine、2020年。 0.88
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Kai Wei、Rishabh Iyer、Jeff Bilmes。 0.61
Submodularity in data subset selection and active learning. データサブセット選択とアクティブラーニングのサブモジュラリティ。 0.70
In Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37, 2015. 第32回機械学習国際会議(第37巻、2015年)開催。 0.50
27 27 0.85
英語(論文から抽出)日本語訳スコア
Bryan Wilder. ブライアン・ワイルダー。 0.48
Risk-sensitive submodular optimization. リスクに敏感なサブモジュール最適化。 0.39
Proceedings of the AAAI Conference on aaai会議の議事録 0.42
Artificial Intelligence, 2018a. 人工知能、2018年。 0.59
Bryan Wilder. ブライアン・ワイルダー。 0.48
Equilibrium computation and robust optimization in zero sum games with submodular 部分モジュラを持つゼロ和ゲームにおける平衡計算とロバスト最適化 0.63
structure. Proceedings of the AAAI Conference on Artificial Intelligence, 2018b. 構造。 AAAI Conference on Artificial Intelligence, 2018b に参加して 0.81
Jiahao Xie, Chao Zhang, Zebang Shen, Chao Mi, and Hui Qian. Jiahao Xie, Chao Zhang, Zebang Shen, Chao Mi, Hui Qian 0.64
Decentralized gradient tracking for continuous dr-submodular maximization. 連続Drサブモジュラー最大化のための分散勾配追跡 0.64
In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, 2019. 第21回人工知能と統計に関する国際会議の議事録、2019年。 0.70
Mingrui Zhang, Lin Chen, Hamed Hassani, and Amin Karbasi. Mingrui Zhang, Lin Chen, Hamed Hassani, Amin Karbasi 0.64
Online continuous submodular maximization: From full-information to bandit feedback. online continuous submodular maximization: from full-information to bandit feedback。 0.90
In Advances in Neural Information Processing Systems, 2019. 2019年 ニューラル・インフォメーション・プロセッシング・システムの進歩。 0.46
28 28 0.85
                                                         ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。