論文の概要、ライセンス

# (参考訳) 動的kクラスタリングのための効率的なオンライン学習 [全文訳有]

Efficient Online Learning for Dynamic k-Clustering ( http://arxiv.org/abs/2106.04336v1 )

ライセンス: CC BY 4.0
Dimitris Fotakis, Georgios Piliouras, Stratis Skoulakis(参考訳) オンライン学習の観点から動的クラスタリング問題を考察する。 オンライン学習問題である \textit{dynamic $k$-clustering} を考えると、k$センターは時間とともにメートル空間で維持され(センターは位置を変える可能性がある)、例えば動的に変化する$r$クライアントのセットは最善の方法で提供されます。 ラウンド$t$の接続コストは、ある$p\geq 1$または$p = \infty$に対して、各クライアントからラウンド$t$の最も近い中心までの距離からなるベクトルの \textit{$p$-norm} によって与えられる。 我々は、多項式時間オンライン学習アルゴリズム \textit{$\theta\left( \min(k,r) \right)$-regret} を提示し、いくつかの確立された計算複雑性予想の下では、多項式時間において \textit{constant-regret} は達成できないことを示す。 Dynamic $k$-Clusteringの効率的なソリューションに加えて、我々の研究は組合せオンライン学習に関する長い研究に寄与している。

We study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called \textit{Dynamic $k$-Clustering}, in which $k$ centers are maintained in a metric space over time (centers may change positions) such as a dynamically changing set of $r$ clients is served in the best possible way. The connection cost at round $t$ is given by the \textit{$p$-norm} of the vector consisting of the distance of each client to its closest center at round $t$, for some $p\geq 1$ or $p = \infty$. We present a \textit{$\Theta\left( \min(k,r) \right)$-regret} polynomial-time online learning algorithm and show that, under some well-established computational complexity conjectures, \textit{constant-regret} cannot be achieved in polynomial-time. In addition to the efficient solution of Dynamic $k$-Clustering, our work contributes to the long line of research on combinatorial online learning.
公開日: Tue, 8 Jun 2021 13:53:12 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] G L . 8 ] G L。 0.81
s c [ 1 v 6 3 3 4 0 sc [ 1 v 6 3 3 4 0 0.68
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Efficient Online Learning for Dynamic k-Clustering 動的kクラスタリングのための効率的なオンライン学習 0.56
Dimitris Fotakis Georgios Piliouras Dimitris属 Georgios属 0.63
National Technical University Singapore University of Technology 国立工業大学 シンガポール工科大学 0.62
of Athens fotakis@cs.ntua.gr アテネの fotakis@cs.ntua.gr 0.59
and Design george.piliouras@gma il.com デザインは george.piliouras@gma il.com 0.60
Stratis Skoulakis Stratis Skoulakis 0.85
Singapore University of Technology シンガポール工科大学 0.58
and Design efstratios@sutd.edu. sg デザインは efstratios@sutd.edu. sg 0.60
Abstract We study dynamic clustering problems from the perspective of online learning. 概要 オンライン学習の観点から動的クラスタリング問題を考察する。 0.59
We consider an online learning problem, called Dynamic k-Clustering, in which k centers are maintained in a metric space over time (centers may change positions) such as a dynamically changing set of r clients is served in the best possible way. 我々は,動的kクラスタと呼ばれるオンライン学習問題を考える。kセンタは時間とともに計量空間(中心が位置を変える)で維持され,動的に変化するrクライアントのセットが最善の方法で提供される。 0.79
The connection cost at round t is given by the p-norm of the vector consisting of the distance of each client to its closest center at round t, for some p ≥ 1 or p = ∞. ラウンド t における接続コストは、ある p ≥ 1 または p = ∞ に対して、各クライアントからラウンド t の最も近い中心までの距離からなるベクトルの p-ノルムによって与えられる。 0.86
We present a Θ (min(k, r))-regret polynomial-time online learning algorithm and show that, under some well-established computational complexity conjectures, constant-regret cannot be achieved in polynomial-time. 本稿では, θ (min(k, r))-regret多項式時間オンライン学習アルゴリズムを示し, 定値回帰は多項式時間では達成できないことを示す。 0.67
In addition to the efficient solution of Dynamic kClustering, our work contributes to the long line of research on combinatorial online learning. 動的kClusteringの効率的なソリューションに加えて、我々の研究は組合せオンライン学習に関する長い研究に寄与している。 0.83
1 Introduction Clustering problems are widely studied in Combinatorial Optimization literature due to their vast applications in Operational Research, Machine Learning, Data Science and Engineering [49, 39, 10, 6, 9, 31, 36, 51, 38, 11, 37, 3]. 1 はじめに クラスタリング問題は,運用研究,機械学習,データサイエンス,エンジニアリング[49,39,10,6,9,31,36,5 1,38,11,37,3]における膨大な応用から,組合せ最適化文学において広く研究されている。 0.75
Typically a fixed number of centers must be placed in a metric space such that a set of clients is served the best possible way. 通常、一定の数のセンターは、クライアントのセットが最善の方法で提供されるように、計量空間に置かれなければならない。 0.69
The quality of a clustering solution is captured through the p-norm of the vector consisting of the distance of each client to its closest center, for some p ≥ 1 or p = ∞. クラスタリングソリューションの品質は、ある p ≥ 1 または p = ∞ に対して、各クライアントから最も近い中心までの距離からなるベクトルの p-ノルムを通して取得される。 0.87
For example k-median and k-means assume p = 1 and 2 respectively, while k-center assumes p = ∞ [39, 37, 3]. 例えば、k-median と k-means はそれぞれ p = 1 と 2 を、k-center は p = ∞ [39, 37, 3] を仮定する。 0.76
Today’s access on vast data (that may be frequently updated over time) has motivated the study of clustering problems in case of time-evolving clients, which dynamically change positions over time [14, 19, 18, 4]. 今日の巨大なデータへのアクセス(時間とともに頻繁に更新される)は、時間とともに動的に位置を変える時間発展するクライアント(14,19,18,4]の場合のクラスタリング問題の研究の動機となっている。 0.77
In time-evolving clustering problems, centers may also 時間発展型クラスタリング問題でも、センターは 0.73
1 1 0.85
英語(論文から抽出)日本語訳スコア
change position over time so as to better capture the clients’ trajectories. クライアントの軌跡をよりよく捉えるために、時間とともに位置を変更する。 0.70
For example, a city may want to reallocate the units performing rapid tests for Covid-19 so as to better serve neighborhoods with more cases, the distribution of which may substantially change from day to day. 例えば、都市はコビッド19の迅速検査を行うユニットを再配置して、より多くのケースを抱える地区により良いサービスを提供し、その分布は日々大きく変化する可能性がある。 0.74
Other interesting applications of dynamic clustering include viral marketing, epidemiology, facility location (e g schools, hospitals), conference planning etc. ダイナミッククラスタリングの他の興味深い応用としては、バイラルマーケティング、疫学、施設(例えば学校、病院)、会議計画などがある。 0.68
[43, 18, 40, 41, 48]. [43, 18, 40, 41, 48]. 0.78
Our work is motivated by the fact that in most settings of interest, clients can move in fairly complicated and unpredictable ways, and thus, an a-priori knowledge on such trajectories is heavily under question (most of the previous work assumes perfect knowledge on clients’ positions over time [18, 4, 14, 19]). 私たちの仕事の動機は、ほとんどの設定において、クライアントはかなり複雑で予測不可能な方法で動きますので、そのような軌道に関するアプリオリの知識は、非常に疑問視されています(前回の作業のほとんどは、時間の経過とともにクライアントの位置に関する完全な知識を前提としています [18, 4, 14 19])。 0.62
To capture this lack of information we cast clustering problems under the perspective of online learning [23]. この情報の欠如を捉えるため、オンライン学習の視点でクラスタリングの問題を提起した[23]。 0.76
We study an online learning problem called Dynamic k-Clustering in which a learner selects at each round t, the positions of k centers trying to minimize the connection cost of some clients, the positions of which are unknown to the learner prior to the selection of the centers. 我々は,学習者が各ラウンドtで選択する動的kクラスタリング(Dynamic k-Clustering)と呼ばれるオンライン学習問題について検討する。
訳抜け防止モード: 学習者が各ラウンドtで選択する動的kクラスタリングと呼ばれるオンライン学習問題について検討する。 kセンターの位置は 一部のクライアントの接続コストを最小化する。 その地位は センターの選定に先立ち 学習者に知られていません
0.78
Online Learning Problem 1 (Dynamic k-Clustering). オンライン学習問題1(Dynamic k-Clustering)。 0.80
Given a metric space d : V × V (cid:55)→ R≥0. 計量空間 d : V × V (cid:55) → R≥0 が与えられる。 0.78
At each round t, 1. 各Tラウンドで。 1. 0.74
The learner selects a set Ft ⊆ V , with |Ft| = k, at which centers are placed. 学習者は、中心が置かれた |Ft| = k の集合 Ft > V を選択する。 0.75
2. The adversary selects the positions of the clients, denoted as Rt (after the selection of 2. 相手はクライアントの位置を選択し、Rt(選択後)と表される。 0.74
the positions of the centers by the learner). センターの位置は学習者)。 0.52
3. The learner suffers the connection cost of the clients, 3. 学習者はクライアントの接続コストに悩まされる。 0.82
(cid:32)(cid:88) (cid:32)(cid:88) 0.75
j∈Rt (cid:33)1/p jjrt (cid:33)1/p 0.60
CRt(Ft) = d(j, Ft)p CRt(Ft) = d(j, Ft)p 0.85
where d(j, Ft) is the distance of client j to the closest center, d(j, Ft) = mini∈Ft dij. ここで d(j, Ft) は、クライアント j から最も近い中心への距離 d(j, Ft) = mini∂Ft dij である。 0.84
Based on the past positions of the clients R1, R2, . クライアントR1,R2,.の過去の位置に基づく。 0.73
. . , Rt−1 an online learning algorithm must select at each round t, a set of k centers Ft ⊆ V such that the connection cost of the clients over time is close to the connection cost of the optimal (static) solution F ∗. . . rt−1 オンライン学習アルゴリズムは、各ラウンド t において、時間経過中のクライアントの接続コストが最適(静的)解 f ∗ の接続コストに近くなるような k センタ ft * v の集合を選択する必要がある。 0.82
If the cost of the online learning algorithm is at most α times the cost of F ∗, the algorithm is called α-regret, whereas in case α = 1, the algorithm is called no-regret [23]. オンライン学習アルゴリズムのコストが f ∗ のコストの最大 α 倍であれば、このアルゴリズムは α-regret と呼ばれ、α = 1 の場合、このアルゴリズムは no-regret [23] と呼ばれる。 0.88
Intuitively, a low-regret online learning algorithm converges to the optimal positions of the centers (with respect to the overall trajectories of the clients) by just observing the clients’ dynamics. 直感的には、低レベルのオンライン学習アルゴリズムは、クライアントのダイナミクスを観察するだけで、(クライアントの全体的な軌道に関して)中心の最適な位置に収束する。 0.77
tribution with radius 0.3 and center following the periodic trajectory(cid:0)sin ( 2π·t 周期軌道(cid:0)sin(2π·t)に続く半径0.3と中心を持つ配位 0.67
Example 1. The clients are randomly generated according to a time-varying uniform dis- 例1。 クライアントは時間変化の均一なdis-に従ってランダムに生成される 0.70
T )(cid:1) for t )(cid:1) 0.91
T ), cos( 2π·t T) cos(2π·t) 0.76
t = 1, . t = 1 である。 0.90
. . , T . The centers placed by a (sufficiently) low-regret algorithm would converge to positions similar in structure to the ones illustrated in Figure 1 (for k = 1, 2, 4 and k = 8) which are clearly close to the optimal (static) solution for the different values of k. . . T。 十分(十分)低回帰アルゴリズムによって配置された中心は、図1(k = 1, 2, 4, k = 8)に示されるような構造上の位置に収束し、k の異なる値に対する最適(静的)解に明らかに近い。 0.75
Efficient Online Learning for Dynamic k-Clustering. 動的kクラスタリングのための効率的なオンライン学習 0.62
The existence of no-regret online learning algorithms for Dynamic k-Clustering immediately follows by standard results in online learning literature [23]. 動的kクラスタリングのためのノンレグレットオンライン学習アルゴリズムの存在は、オンライン学習文学の標準結果によってすぐに従う[23]。 0.78
Dynamic k-Clustering is a special case of Learning from 動的kクラスタリングは学習の特別な例である 0.83
2 2 0.85
英語(論文から抽出)日本語訳スコア
Figure 1: The figure depicts the actual centers at which a low-regret algorithm, that we subsequently propose, converges. 図1: この図は、次に提案した低回帰アルゴリズムが収束する実際の中心を描いている。 0.77
For further details see Section 6. 詳細は第6節を参照。 0.68
3 3 0.85
英語(論文から抽出)日本語訳スコア
keeps a different weight (probability) for each of the possible(cid:0)|V | 可能な(cid:0)|v | ごとに異なる重み(確率)を保持する 0.81
Expert Advice problem for which the famous Multiplicative Weights Update Algorithm achieves no-regret [23]. 有名な乗法重み更新アルゴリズムがno-regret[23]を達成するエキスパートアドバイス問題。 0.77
Unfortunately using the MWU for Dynamic k-Clustering is not really an option due to the huge time and space complexity that MWU requires. 残念ながら、MWU for Dynamic k-Clusteringは、MWUが必要とする膨大な時間と空間の複雑さのため、実際には選択肢ではない。 0.63
In particular MWU k centers, rendering it inapplicable even for small values of |V | and k. 特に MWU k の中心であり、|V | と k の小さな値であっても適用できない。 0.77
(cid:1) possible placements of the (cid:1) 配置の可能性 0.78
k Our work aims to shed light on the following question. k 私たちの仕事は次の質問に光を当てることを目的としています。 0.68
Question 1. Is there an online learning algorithm for Dynamic k-Clustering that runs in polynomial time and achieves α-regret? 質問1。 多項式時間で実行し、α-regretを達成する動的k-Clusteringのためのオンライン学習アルゴリズムはあるか? 0.67
Our Contribution and Techniques. We first show that constant regret cannot be achieved in polynomial time for Dynamic k-Clustering. 貢献と技術。 まず,動的kクラスタ化の多項式時間では,一定の後悔は達成できないことを示した。
訳抜け防止モード: 貢献と技術。 最初に示すのは 定数後悔は動的 k - クラスタリングの多項式時間では達成できない。
0.59
In particular we prove that any O(1)-regret polynomial-time online learning algorithm for Dynamic k-Clustering implies the existence of an O(1)-approximation algorithm for the Minimum-p-Union problem [12]. 特に、動的k-クラスタリングのための任意のO(1)-regret多項式時間オンライン学習アルゴリズムは、最小p-ユニオン問題 [12] に対するO(1)-近似アルゴリズムの存在を示唆する。 0.82
Recent works on the theory of computational complexity establish that unless well-established cryptographic conjectures fail, there is no O(1)-approximation algorithm for Min-p-Union [12, 5, 13]. 計算複雑性理論に関する最近の研究は、確立された暗号予想が失敗しなければ、min-p-union [12, 5, 13] に対するo(1)近似アルゴリズムは存在しないことを証明している。 0.66
This result narrows the plausible regret bounds achievable in polynomial time, and reveals an interesting gap between Dynamic k-Clustering and its offline counterparts, which admit polynomial-time O(1)-approximation algorithms. この結果は多項式時間で達成可能な可算後悔境界を狭め、動的k-クラスタリングと、多項式時間 O(1)-近似アルゴリズムを許容するそのオフラインとの興味深いギャップを明らかにする。 0.70
Our main technical contribution consists of polynomial-time online learning algorithms for Dynamic k-Clustering with non trivial regret bounds. 我々の主な技術貢献は多項式時間オンライン学習アルゴリズムによる動的k-Clusteringと非自明な後悔境界からなる。 0.67
We present a Θ(k)-regret polynomialtime deterministic online learning algorithm and a Θ(r)-regret polynomial-time randomized online learning algorithm, where r is the maximum number of clients appearing in a single round (r = max1≤t≤T |Rt|). 本稿では, θ(k)-regret多項式時間決定論的オンライン学習アルゴリズムとθ(r)-regret多項式時間ランダムオンライン学習アルゴリズムを提案する。
訳抜け防止モード: 本稿では, 時間ランダム化オンライン学習アルゴリズムと, 時間ランダム化オンライン学習アルゴリズムについて述べる。 r は 1 つのラウンド (r = max1≤t≤T |Rt| ) に存在するクライアントの最大数である。
0.73
Combining these algorithms, one can achieve Θ (min(k, r))-regret for Dynamic k-Clustering, which (to the best of our knowledge) is the first guarantee on the regret achievable in polynomial time. これらのアルゴリズムを組み合わせることで、動的k-クラスタリングに対して、(私たちの知る限りでは)多項式時間で達成可能な後悔に対する最初の保証となる(min(k, r))-regretを達成できる。 0.77
The regret bounds above are independent of the selected p-norm, and hold for any p ≥ 1 and for p = ∞. 上記の後悔境界は選択された p-ノルムとは独立であり、任意の p ≥ 1 と p = ∞ に対して成り立つ。 0.75
At a technical level, our approach consists of two major steps. 技術的なレベルでは、私たちのアプローチは2つの大きなステップで構成されています。 0.51
In the first step, we consider an online learning problem, that can be regarded as the fractional relaxation of the Dynamic k-Clustering (see Section 3), where the fractional connection cost is given by the optimal value of an appropriate convex program and the action space of the learner is the |V |-dimensional simplex. 最初のステップでは、動的k-クラスタリングの分数緩和と見なせるオンライン学習問題を考える(第3節参照)。そこでは、適切な凸プログラムの最適値によって分数接続コストが与えられ、学習者の行動空間は |V |-次元単純さである。 0.72
For this intermediate problem, we design a no-regret polynomial-time online learning algorithm through the use of the subgradients of the fractional connection cost. この中間問題に対して,分数接続コストの下位値を用いて,非線形多項式時間オンライン学習アルゴリズムを設計する。 0.76
We show that such subgradient vectors can be computed in polynomial time via the solution of the dual program of the fractional connection cost. これらの部分次ベクトルは、分数接続コストの双対プログラムの解を用いて多項式時間で計算できることを示す。 0.81
In the second step of our approach (see Section 4 and Section 5), we provide computationally efficient online (deterministic and randomized) rounding schemes converting a vector lying in the |V |-dimensional simplex (the action space of Fractional Dynamic k-Clustering) into k locations for the centers on the metric space V (the action space of Dynamic k-Clustering). 第2段階(第4節および第5節参照)では、 |v |-dimensional simplex(分数動的k-クラスターの作用空間)にあるベクトルを計量空間v(動的k-クラスターの作用空間)上の中心のk位置に変換する計算効率の高いオンライン(決定論的かつランダム化された)丸めスキームを提供する。 0.86
In Section 4, we present a deterministic rounding scheme that, combined with the noregret algorithm for Fractional Dynamic k-Clustering, leads to a Θ(k)-regret polynomial-time deterministic online learning algorithm for the original Dynamic k-Clustering. 第4節では,Fractional Dynamic k-Clusteringのnoregretアルゴリズムと組み合わさって,元のDynamic k-Clusteringの多項式時間決定論的オンライン学習アルゴリズムを実現できる決定論的ラウンドリング方式を提案する。 0.88
Interestingly, this regret bound is approximately optimal for all deterministic algorithms. 興味深いことに、この後悔の境界は決定論的アルゴリズムにほぼ最適である。 0.55
In Section 5, we show that combining the no-regret algorithm for Fractional Dynamic k-Clustering with a 第5節では、フラクショナル動的k-クラスタリングの非レグレットアルゴリズムとaの組み合わせが示される。
訳抜け防止モード: 第5節では、 Fractional Dynamic k - Clustering と a を組み合わせた no- regret アルゴリズム
0.84
4 4 0.85
英語(論文から抽出)日本語訳スコア
randomized rounding scheme proposed in [11]1 leads to a Θ(r)-regret randomized algorithm running in polynomial time. 11]1で提案されたランダム化丸めスキームは、θ(r)-regret ランダム化アルゴリズムを多項式時間で実行する。 0.80
Combining these two online learning algorithms, we obtain a Θ(min(k, r))-regret polynomial-time online learning algorithm for Dynamic k-Clustering, which is the main technical contribution of this work. これら2つのオンライン学習アルゴリズムを組み合わせることで,この研究の主な技術的貢献である動的kクラスタリングのための多項式時間オンライン学習アルゴリズムが得られた。 0.80
Finally, in Section 6, we present the results of an experimental evaluation, indicating that for client locations generated in a variety of natural and practically relevant ways, the realized regret of the proposed algorithms is way smaller than Θ (min(k, r)). 最後に, 第6節では, 様々な自然的かつ実用的な方法で生成されたクライアント位置について, 提案したアルゴリズムの後悔は, (min(k, r)) よりもはるかに小さいことを示す実験結果を示す。 0.84
Remark 1. Our two-step approach provides a structured framework for designing polynomialtime low-regret algorithms in various combinatorial domains. 備考1。 2段階のアプローチは,様々な組合せ領域における多項式時間ローレグレットアルゴリズムを設計するための構造化フレームワークを提供する。 0.54
The first step extends far beyond the context of Dynamic k-Clustering and provides a systematic approach to the design of polynomial-time no-regret online learning algorithms for the fractional relaxation of the combinatorial online learning problem of interest. 最初のステップは動的kクラスタ化の文脈をはるかに越え、多項式時間非回帰オンライン学習アルゴリズムの設計に体系的なアプローチを提供し、興味のある組合せ型オンライン学習問題の分数緩和を提供する。 0.77
Combining such no-regret algorithms with online rounding schemes, which convert fractional solutions into integral solutions of the original online learning problem, may lead to polynomial time low-regret algorithms for various combinatorial settings. このような非回帰アルゴリズムと、元のオンライン学習問題の分数解を積分解に変換するオンライン丸めスキームを組み合わせると、様々な組合せ設定に対する多項式時間低回帰アルゴリズムにつながる可能性がある。 0.67
Obviously, designing such rounding schemes is usually far from trivial, since the specific combinatorial structure of each specific problem must be taken into account. 当然、そのような丸めのスキームの設計は、個々の問題の特定の組合せ構造を考慮する必要があるため、通常、自明ではない。 0.62
Related Work. Our work relates with the research line of Combinatorial Online Learning. 関連作品。 我々の研究は、 Combinatorial Online Learningの研究ラインに関連している。 0.65
There exists a long line of research studying low-regret online learning algorithms for various combinatorial domains such that online routing [28, 7], selection of permutations [46, 50, 20, 2, 29], selection of binary search trees [47], submodular optimization [25, 32, 44], matrix completion [26], contextual bandits [1, 17] and many more. オンラインルーティング [28, 7]、置換の選択 [46, 50, 20, 2, 29]、二項探索木の選択 [47]、サブモジュラー最適化 [25, 32, 44]、マトリックス補完 [26]、コンテクストバンド [1, 17] など、様々なコンビネートドメインのオンライン学習アルゴリズムを研究する長い研究がある。
訳抜け防止モード: オンラインルーティング[28,7]など,さまざまな組み合わせドメインを対象とした,低レベルの後悔のオンライン学習アルゴリズムの研究は,数多く行われている。 置換の選択[46, 50, 20, 2, 29 ] 二分探索木[47 ]の選択, 部分モジュラ最適化[25] 32,44 ],行列完備[26 ],文脈的包帯[1, 17 ] 他にもたくさん
0.88
Finally, in combinatorial games agents need to learn to play optimally against each other over complex domains [30, 15]. 最後に、in combinatorial gamesエージェントは複雑なドメイン[30, 15]上で最適な対戦を学ばなければなりません。 0.74
As in the case of Dynamic k-Clustering in all the above online learning problems, MWU is not an option, due to the exponential number of possible actions. 上記のオンライン学習問題すべてにおいて動的kクラスタ化の場合と同様に、mwuは指数関数的なアクション数のため選択肢ではない。 0.62
Another research direction of Combinatorial Online Learning studies black-box reductions converting polynomial time offline algorithm (full information on the data) into polynomial time online learning algorithms. コンビネートリアルオンライン学習研究の別の研究方向 ブラックボックスリダクションは、多項式時間オフラインアルゴリズム(データに関する完全な情報)を多項式時間オンライン学習アルゴリズムに変換する。 0.78
[34] showed that any (offline) algorithm solving optimally and in polynomial time the objective function, that the Follow the Leader framework suggests, can be converted into a no-regret online learning algorithm. [34] は,Follow the Leaderフレームワークが提案する目的関数を最適かつ多項式時間で解いた任意の(オフライン)アルゴリズムが,オンライン学習アルゴリズムに変換可能であることを示した。 0.88
[33] extended the previous result for specific class of online learning problems called linear optimization problems for which they showed that any α-approximation (offline) can be converted into an α-regret online learning algorithm. [33] は, 線形最適化問題と呼ばれるオンライン学習の特定のクラスに対して, α-近似(オフライン)をα-回帰オンライン学習アルゴリズムに変換することができることを示した。 0.80
They also provide a surprising counterexample showing that such black-box reductions do not hold for general combinatorial online learning problems. また、このようなブラックボックスの削減が一般的な組合せオンライン学習問題に当てはまらないことを示す驚くべき反例も提示されている。 0.54
Both the time efficiency and the regret bounds of the reductions of [34] and [33] were subsequently improved by [42, 45, 35, 8, 16, 27, 21, 22, 24]. その後, [34] と [33] の削減の時間効率と後悔限度を [42, 45, 35, 8, 16, 27, 21, 22, 24] で改善した。 0.79
We remark that the above results do not apply in our setting since Dynamic k-Clustering can neither be optimally solved in polynomial-time nor is a linear optimization problem. この結果は、動的k-クラスタリングが多項式時間で最適に解けず、線形最適化問題でもないため、我々の設定では適用できない。 0.73
Our works also relates with the more recent line of research studying clustering problems with time-evolving clients. また,この研究は,時間発展型クライアントによるクラスタリング問題の研究の最近の動向とも関係している。 0.64
[18] and [4] respectively provide Θ (log(nT )) and O(1)approximation algorithm for a generalization of the facility location problem in which clients change their positions over time. [18] と [4] はそれぞれ、クライアントが時間とともに位置を変化させる施設配置問題の一般化のために シュ (log(nT )) と O(1) 近似アルゴリズムを提供する。 0.87
The first difference of Dynamic k-Clustering with this これによる動的k-クラスタリングの最初の違い 0.76
1This randomized rounding scheme was part of a 4-approximation algorithm for k-median [11] 1このランダムな丸めスキームはk-medianの4近似アルゴリズムの一部であった [11] 0.70
5 5 0.85
英語(論文から抽出)日本語訳スコア
setting is that in the former case there is no constraint on the number of centers that can open and furthermore, crucially perfect knowledge of the positions of the clients is presumed. 設定は、前者の場合、オープン可能なセンターの数に制約はなく、さらに、クライアントの位置に関する極めて完全な知識が推定されるということです。 0.74
More closely related to our work are [14, 19], where the special case of Dynamic k-Clustering on a line is studied (the clients move on a line over time). 14, 19]では、ライン上の動的kクラスタ化の特別なケースについて検討しています(クライアントは時間とともにライン上を移動します)。
訳抜け防止モード: 私たちの仕事とより密接な関係は[14, 19]です。 そこで Dynamic k の特別なケース - 直線上のクラスタリングの研究 (クライアントは時間とともに一列に進む)。
0.78
Despite the fact that both works study online algorithms, which do not require knowledge on the clients’ future positions, they only provided positive results for k = 1 and 2. どちらも、クライアントの将来のポジションに関する知識を必要としないオンラインアルゴリズムを研究しているにもかかわらず、彼らはk = 1 と 2 のポジティブな結果しか提供していない。 0.64
2 Preliminaries and Our Results 2 予備試験とその結果 0.71
In this section we introduce notation and several key notions as long as present the formal Statements of our results. この節では、結果の形式的記述を示す限り、表記法といくつかの重要な概念を紹介します。 0.61
We denote by D the diameter of the metric space, D = maxi∈V,j∈V dij. d は距離空間の直径、d = maxiبv,jبv dij で表される。 0.66
We denote with n the cardinality of the metric space (|V | = n) and with r the maximum number of clients appearing in a single round, r = max1≤t≤T |Rt|. n を計量空間 (|V | = n) の濃度とし、r を単一のラウンドで現れるクライアントの最大数 r = max1≤t≤T |Rt| とする。 0.82
Finally we denote with ∆k n the n-dimensional simplex, ∆k 最終的に、我々は n-次元単純集合 sk n で表す 0.62
n = {y ∈ Rn : (cid:80) n = {y ∈ Rn : (cid:80) 1.00
i∈V yi = k and yi ≥ 0}. ijavav yi = k と yi ≥ 0} である。 0.79
Following the standard notion of regret in online learning [23], we provide the formal オンライン学習における後悔の標準概念[23]に従えば、我々は形式を提供する。 0.70
definition of an α-regret online learning algorithm for Dynamic k-Clustering. 動的kクラスタリングのためのα-regretオンライン学習アルゴリズムの定義 0.78
Definition 1. An online learning algorithm for the Dynamic k-Clustering is α-regret if and only if for any sequence of clients’ positions R1, . 定義1。 動的kクラスタリングのためのオンライン学習アルゴリズムは、任意のクライアントの位置R1, . のシーケンスに対してのみ、α-regretである。 0.70
. . , RT ⊆ V , . . RT は V である。 0.78
T(cid:88) t=1 t(cid:88) t=1。 0.63
CRt(Ft) ≤ α · min |F ∗|≤k CRt(Ft) ≤ α · min |F ∗|≤k 1.00
T(cid:88) t=1 t(cid:88) t=1。 0.63
CRt(F ∗) + Θ(cid:0)poly(n, D) · T β(cid:1) CRt(F ∗) + s(cid:0)poly(n, D) · T β(cid:1) 0.94
where F1, . . . f1、f1。 . . 0.77
, FT are the positions of the centers produced by the algorithm for the sequence R1, . , FTは, シーケンスR1のアルゴリズムによって生成された中心の位置である。 0.77
. . , RT and β < 1. . . , rtおよびβ<1。 0.78
Next, we introduce the Minimum-p-Union problem, the inapproximability results of which allow us to establish that constant regret cannot be achieved in polynomial time for Dynamic k-Clustering. 次に、最小p結合問題(英語版)を紹介し、その近似可能性の結果により、動的kクラスター化の多項式時間では、一定の後悔が達成できないことを証明できる。
訳抜け防止モード: 次に、最小-p-ユニオン問題を導入する。 不適応性の結果は 絶え間ない後悔が動的 k - クラスタリングの多項式時間で達成できないことを示す。
0.67
Problem 1 (Min−p−Union). 問題1(min-p-union)。 0.57
Given a universe of elements E and a collection of sets U = {S1, . 要素 e の宇宙と集合 u = {s1, .} の集合が与えられる。 0.81
. . , Sm} where Si ⊆ E. Select U(cid:48) ⊆ U such that |U(cid:48)| = p and | ∪Si∈U(cid:48) Si| is minimized. . . u(cid:48)| = p と |u(cid:48) si| が最小となるように u(cid:48) を選択。 0.79
As already mentioned, the existence of an O(1)-approximation algorithm for Min−p−Union violates several widely believed conjectures in computational complexity theory[12, 5, 13]. 既に述べたように、Min-p-Union に対する O(1)-近似アルゴリズムの存在は、計算複雑性理論[12, 5, 13] において広く信じられているいくつかの予想に反する。 0.70
In Theorem 1 we establish the fact that the exact same conjectures are violated in case there exists an online learning algorithm for Dynamic k-Clustering that runs in polynomial-time and achieves O(1)-regret. Theorem 1 では、多項式時間で実行され、O(1)-regret を達成する動的k-Clustering のオンライン学習アルゴリズムが存在する場合、全く同じ予想が破られるという事実を確立する。 0.75
Theorem 1. Any c-regret polynomial-time online learning algorithm for the Dynamic kClustering implies a (c + 1)-approximation polynomial-time algorithm for Min−p−Union. 理論1。 動的kClusteringに対する任意のc-regret多項式時間オンライン学習アルゴリズムは、Min−p−Unionに対する(c + 1)近似多項式時間アルゴリズムを意味する。 0.61
In Section 4, we present a polynomial-time deterministic online learning algorithm achiev- 第4節では多項式時間決定論的オンライン学習アルゴリズムについて述べる。 0.63
ing Θ(k)-regret. ing θ(k)-レグレット。 0.49
6 6 0.85
英語(論文から抽出)日本語訳スコア
Theorem 2. There exists a 6k-regret deterministic online learning algorithm for Dynamic k-Clustering that runs in polynomial time (Algorithm 4). 定理2。 動的kクラスタ化のための6k-regret決定論的オンライン学習アルゴリズムが多項式時間で動作する(algorithm 4)。 0.65
More precisely, T(cid:88) より正確には t(cid:88) 0.78
t=1 CRt(Ft) ≤ 6k · min |F ∗|=k t=1。 CRt(Ft) ≤ 6k · min |F ∗|=k 0.69
CRt(F ∗) + Θ CRt(F ∗) + ... 0.69
T(cid:88) t=1 t(cid:88) t=1。 0.63
(cid:16) kDn(cid:112)log nT (cid:16) kDn(cid:112)log nT 0.85
(cid:17) where F1, . (cid:17) f1、f1。 0.70
. . , FT are the positions in which Algorithm 4 places the centers for the sequence of clients’ positions R1, . . . FTは、アルゴリズム4がクライアントの位置R1, のシーケンスの中心を置く位置である。 0.77
. . , RT . . . rt である。 0.72
In Theorem 3 we prove that the Θ(k) bound on the regret of Algorithm 4 cannot be significantly ameliorated with deterministic online learning algorithm even if the algorithm uses exponential time and space. Theorem 3 では,アルゴリズムが指数時間と空間を使用する場合でも,アルゴリズム4 の後悔に縛られた s(k) が決定論的オンライン学習アルゴリズムで著しく改善できないことを証明している。 0.80
Theorem 3. For any deterministic online learning algorithm for Dynamic k-Clustering problem, there exists a sequence of clients R1, . 理論3。 動的kクラスタリング問題に対する決定論的オンライン学習アルゴリズムには、クライアントR1のシーケンスが存在する。 0.71
. . , RT such as the regret is at least k + 1. . . , 後悔のようなRTは少なくとも k + 1 である。 0.82
In Section 5 we present a randomized online learning algorithm the regret of which depends 第5節では,無作為なオンライン学習アルゴリズムを提示する。 0.71
on the parameter r. パラメータ r について 0.61
Theorem 4. There exists a Θ(r)-regret randomized algorithm that runs in polynomial time (Algorithm 5). 理論4。 多項式時間 (Algorithm 5) で実行される シュ(r)-regret ランダム化アルゴリズムが存在する。 0.72
For any sequence of clients’ positions R1, . クライアントの位置R1の任意のシーケンスに対して。 0.71
. . , RT with |Rt| ≤ r, . . , RT with |Rt| ≤ r, 0.88
T(cid:88) t=1 t(cid:88) t=1。 0.63
E [CRt(Ft)] = 4r · min |F ∗|=k E [CRt(Ft)] = 4r · min |F ∗|=k 0.97
CRt(F ∗) T(cid:88) (cid:16) kDn(cid:112)log nT CRt(F ∗) T(cid:88) (cid:16) kDn(cid:112)log nT 0.77
t=1 (cid:17) t=1。 (cid:17) 0.62
+ Θ where Ft is the random variable denoting the k positions at which Algorithm 5 places the centers at round t. + Θ ここで Ft は k の位置を表すランダム変数であり、アルゴリズム5 は中心を円 t に配置する。 0.82
By combining Algorithm 4 and Algorithm 5 we can achieve Θ (min(k, r))-regret in poly- アルゴリズム4とアルゴリズム5を組み合わせることで、ポリ-でθ(min(k, r)-regretを実現できる。 0.74
nomial time. Theorem 5. ノミナルタイム。 理論5。 0.57
There exists an online learning algorithm for Dynamic k-Clustering that runs in polynomial-time and achieves min (6k, 4r)-regret. 多項式時間で動作し、min (6k, 4r)-regretを達成する動的kクラスタのためのオンライン学習アルゴリズムがある。
訳抜け防止モード: 多項式時間で動作する動的kクラスタリングのためのオンライン学習アルゴリズムが存在する min (6k , 4r)-regret。
0.80
Remark 2. In case the value r = min1≤t≤T |Rt| is initially known to the learner, then Theorem 5 follows directly by Theorem 2 and 4. 備考2。 r = min1≤t≤T |Rt| の値が最初に学習者に知られている場合、定理5 は定理2 と 4 によって直接従う。 0.58
However even if r is not initially known, the learner can run a Multiplicative Weight Update Algorithm that at each round follows either Algorithm 4 or Algorithm 5 with some probability distribution depending on the cost of each algorithm so far. しかし、初期rが知られていなくても、学習者は各ラウンドにおいてアルゴリズム4またはアルゴリズム5のいずれかに従う乗法重み更新アルゴリズムを実行することができる。 0.66
By standard results for MWU [23], this meta-algorithm admits time-average cost less than the best of Algorithm 4 and 5. mwu [23]の標準的な結果により、このメタアルゴリズムはアルゴリズム4とアルゴリズム5よりも時間平均コストが低くなる。 0.64
3 Fractional Dynamic k-Clustering 3 フラクショナル動的k-クラスタリング 0.70
In this section we present the Fractional Dynamic k-Clustering problem for which we provide a polynomial-time no-regret online learning algorithm. 本稿では,多項式時間非回帰オンライン学習アルゴリズムを提供する分数動的kクラスタリング問題を提案する。 0.81
This online learning algorithm serves このオンライン学習アルゴリズムは 0.90
7 7 0.85
英語(論文から抽出)日本語訳スコア
as a primitive for both Algorithm 4 and Algorithm 5 of the subsequent sections concerning the original Dynamic k-Clustering. 元の動的k-クラスタリングに関する後続のセクションのアルゴリズム4とアルゴリズム5のプリミティブとして。 0.78
The basic difference between Dynamic k-Clustering and Fractional Dynamic k-Clustering is that in the second case the learner can fractionally place a center at some point of the metric space V . 動的kクラスタ化と分数動的kクラスタ化の基本的な違いは、第二のケースでは学習者が距離空間 v のある点に分数的に中心を置くことができることである。 0.64
Such a fractional opening is described by a vector y ∈ ∆k n. Online Learning Problem 2. そのような分数開きはベクトル y ∈ yk n. オンライン学習問題 2 によって記述される。 0.66
[Fractional Dynamic k-Clustering]At each round t ≥ 1, [Fractional Dynamic k-Clustering]各ラウンド t ≥ 1 について 0.86
1. The learner selects a vector yt ∈ ∆k 1. 学習者はベクトル yt ∈ sk を選択する 0.83
center that the learner opens in position i ∈ V . 学習者がi ∈ Vの位置で開く中心となる。 0.77
n. The value yt i stands for the fractional amount of n. yt の値 私はその分の一の量を表します 0.72
2. The adversary selects the positions of the clients denoted by Rt ⊆ V (after the selection 2. 相手は選択後、Rt > Vで示されるクライアントの位置を選択する 0.74
of the vector yt). ベクトル yt について)。 0.68
3. The learner incurs fractional connection cost FCRt(yt) described in Definition 2. 3. 学習者は、定義2に記載された分数接続コストFCRt(yt)を発生させる。 0.74
Definition 2 (Fractional Connection Cost). 定義2(Fractional Connection Cost)。 0.72
Given the positions of the clients R ⊆ V , we define the fractional connection cost FCR(·) of a vector y ∈ ∆k n as the optimal value of the following convex program. クライアント R > V の位置が与えられたとき、ベクトル y ∈ >k n の分数接続コスト FCR(·) を次の凸プログラムの最適値として定義する。 0.73
minimize s.t. (cid:17)1/p 最小化 s.t. (cid:17)1/p 0.68
(cid:16)(cid:80) βj = (cid:80) (cid:80) (cid:16)(cid:80) βj = (cid:80) (cid:80) 0.74
i∈V xij ≤ yi xij ≥ 0 i・V xij ≤ yi xij ≥ 0 0.86
j j∈R βp dij · xij j jjr βp dij · xij 0.82
i∈V xij = 1 I・V・xij = 1 0.53
∀j ∈ R ∀j ∈ R ∀j ∈ R, ∀i ∈ V ∀j ∈ R, ∀i ∈ V ~j ∈ R また、r, r, v, v, v, v, v が成立する。 0.56
(1) It is not hard to see that once the convex program of Definition 2 is formulated with respect to an integral vector y ∈ ∆k n (yi is either 0 or 1) the fractional connection cost FCR(y) equals the original connection cost CR(y). (1) 定義 2 の凸プログラムが積分ベクトル y ∈ (yi は 0 または 1) に対して定式化されると、分数接続コスト FCR(y) は元の接続コスト CR(y) と等しいことが分かる。
訳抜け防止モード: (1) 定義 2 の凸プログラムが積分ベクトル y ∈ yk n に関して定式化されると、容易には見つからない。 (yi は 0 または 1 ) の分数接続コスト FCR(y ) 元の接続コスト CR(y ) と等しい。
0.80
As a result, the cost of the optimal solution y∗ ∈ ∆n k of Fractional Dynamic k-Clustering is upper bounded by the cost of the optimal positioning of the centers F ∗ in the original Dynamic k-Clustering. その結果、フラクショナル・ダイナミック k-クラスタリングの最適解 y∗ ∈ yn k のコストは、元の動的 k-クラスタリングにおける中心 F ∗ の最適位置決めのコストによって上限づけられる。 0.84
Lemma 1. For any sequence of clients’ positions R1, . レマ1号。 クライアントの位置R1の任意のシーケンスに対して。 0.62
. . , RT , the cost of the optimal fractional solution y∗ for Fractional Dynamic k-Clustering is smaller than the cost of the optimal positioning F ∗ for Dynamic k-Clustering, . . RT, フラクショナル動的k-クラスタリングにおける最適分数解 y∗ のコストは, 動的k-クラスタリングにおける最適位置決め F ∗ のコストよりも小さい。 0.84
min y∗∈∆k min (複数形 mins) 0.27
n FCRt(y∗) ≤ min |F ∗|=k n FCRt(y∗) ≤ min |F ∗|=k 0.91
CRt(F ∗) T(cid:88) CRt(F ∗) t(cid:88) 0.76
t=1 T(cid:88) t=1。 t(cid:88) 0.63
t=1 Lemma 1 will be used in the next sections where the online learning algorithms for the original Dynamic k-Clustering are presented. t=1。 Lemma 1は、オリジナルのDynamic k-Clusteringのためのオンライン学習アルゴリズムが提示される次のセクションで使用される。 0.63
To this end, we dedicate the rest of this section to design a polynomial time no-regret algorithm for Fractional Dynamic k-Clustering. この目的のために, この節の残りを, 分数動的kクラスタ化のための多項式時間no-regretアルゴリズムの設計に充てる。 0.65
A key step towards this direction is the use of the subgradient vectors of FCRt(·). この方向に向かう重要なステップは、FCRt(·) の下位ベクトルの利用である。 0.78
8 8 0.85
英語(論文から抽出)日本語訳スコア
Definition 3 (Subgradient). Given a function f : Rn (cid:55)→ R, a vector g ∈ Rn belongs in the subgradient of f at point x ∈ Rn,g ∈ ∂f (x), if and only if f (y) ≥ f (x) + g(cid:62)(y − x) , for all y ∈ Rn. 定義3(下位)。 函数 f : Rn (cid:55) → R が与えられたとき、ベクトル g ∈ Rn が点 x ∈ Rn,g ∈ ∂f (x) における f の部分次数に属することは、すべての y ∈ Rn に対して f (y) ≥ f (x) + g(cid:62)(y − x) が成り立つことを言う。 0.76
Computing the subgradient vectors of functions, as complicated as FCRt(·), is in general a computationally hard task. FCRt(·)のように複雑な関数の次数次ベクトルの計算は、一般に計算的に難しい作業である。 0.82
One of our main technical contributions consists in showing that the latter can be done through the solution of an adequate convex program corresponding to the dual of the convex program of Definition 2. 私たちの主な技術貢献の1つは、定義2の凸プログラムの双対に対応する適切な凸プログラムの解によって後者が実現できることを示すことである。 0.84
Lemma 2. Consider the convex program of Definition 2 formulated with respect to a vector y ∈ ∆k レマ2号。 定義 2 の凸プログラムをベクトル y ∈ yk に対して定式化して考える。 0.70
n and the clients’ positions R. Then the following convex program is its dual. 次に、次の凸プログラムはその双対である。 0.40
maximize (cid:80) 最大化(cid:80) 0.64
j∈R Aj −(cid:80) jjr aj −(cid:80) 0.67
i∈V (cid:80) I-V (cid:80) 0.61
j∈R kij · yi j~R Kij·yi 0.56
s.t. p ≤ 1 ||λ||∗ dij · λj + kij ≥ Aj kij ≥ 0 p is the dual norm of || · ||p s.t. p ≤ 1 ||λ||∗ dij · λj + kij ≥ aj kij ≥ 0 p は || · ||p の双対ノルムである。 0.76
where || · ||∗ ここで || · ||∗ 0.67
∀i ∈ V, j ∈ R シュイ ∈ V, j ∈ R 0.68
∀i ∈ V, j ∈ R シュイ ∈ V, j ∈ R 0.68
(2) In the following lemma we establish the fact that a subgradient vector of ∂FCRt(·) can be (2) 次の補題において、 ∂FCRt(·) の劣次ベクトルが可算であるという事実を確立する。 0.76
computed through the optimal solution of the convex program in Lemma 2. Lemma 2の凸プログラムの最適解によって計算される。 0.77
Lemma 3. Let k∗ program in Lemma 2 formulated with respect to vector y ∈ ∆k Then for any vector y(cid:48) ∈ ∆k n, 第3弾。 Lemma 2 における k∗ プログラムを、任意のベクトル y(cid:48) ∈ yk n, 0.62
ij denote the value of the variables kij in the optimal solution of the convex n and the clients’ positions R. ij は、凸 n とクライアントの位置 R の最適解における変数 Kij の値を表す。 0.66
FCRt(y(cid:48)) ≥ FCRt(y) + FCRt(y(cid:48)) ≥ FCRt(y) + 0.97
k∗ ij · (y(cid:48) k∗ ij ·(y(cid:48) 0.84
i − yi) (cid:88) i − yi) (cid:88) 0.82
i∈V (cid:32) −(cid:88) I-V (cid:32)-(cid:88) 0.66
j∈R (cid:33) jjr (cid:33) 0.61
Moreover there exits an Θ(r · |V |) algorithm for solving the dual program (Algorithm 1) and additionally |k∗ さらに、双対プログラム (Algorithm 1) と |k∗ を解くための シュ(r · |V |) アルゴリズムを出力する。 0.87
ij| ≤ D. 9 ij| ≤ D。 9 0.89
英語(論文から抽出)日本語訳スコア
Algorithm 1 A time-efficient algorithm for solving the dual program of Lemma 2 1: Input: A vector y ∈ ∆k 2: Output: An optimal solution for the convex program of Lemma 2. アルゴリズム 1 レンマ 2 の双対プログラムを解くための時間効率の良いアルゴリズム: 入力: a vector y ∈ sk 2: output: a optimal solution for the convex program of lemma 2 0.78
3: for each client j ∈ R, do 3: 各クライアント j ∈ R に対して、do 0.90
n and a set of clients R ⊆ V . n とクライアントの集合 R は V である。 0.71
Sort the nodes i ∈ V in increasing order according to dij. ノード i ∈ V を dij に従って増加順にソートする。 0.82
Rem ← 1 for each each i ∈ V do xij ← min(yi, Rem). 各 i ∈ V に対して、各 i ∈ V は min(yi, Rem) である。 0.47
Rem ← Rem − xij. 通称「rem-xij」。 0.23
4: 5: 6: 7: 8: 9: 10: end for 11: for each client j ∈ R do 4: 5: 6: 7: 8: 9: 10: end for 11: for each client j ∈ R do do 0.88
end for j ← {i ∈ V : xij > 0} and Dj ← maxi∈V + V + 終止符 j は {i ∈ V : xij > 0} で、Dj は maxi∂V + V + 0.70
dij. j βj ←(cid:80) λj ←(cid:104) βj ディジー j βj(cid:80) λj(cid:104) βj 0.62
(cid:105)p−1 i∈V dij · xij (cid:16) ||β||p Aj ← λj · Dj kij ← min (cid:105)p−1i・V dij · xij (cid:16) ||β||p Aj · λj · Dj Kij · min 0.58
λj · xij yi 16: 17: end for λj·xij ユイ 16:17:終了 0.62
(cid:17) · (Dj − dij) , 0 (cid:17) ·(Dj − dij) , 0。 0.82
12: 13: 14: 12: 13: 14: 0.85
15: 3: 4: 5: 6: 7: 8: 15: 3: 4: 5: 6: 7: 8: 0.85
Remark 3. Algorithm 1 is not only a computationally efficient way to solve the convex program of Lemma 2, but most importantly guarantees that the value k∗ ij are bounded by D (this is formally Stated and proven in Lemma 2). 第3話。 アルゴリズム 1 は、Lemma 2 の凸プログラムを解くための計算学的に効率的な方法であるだけでなく、最も重要なことは、k∗ ij が D で有界であることを保証している(これは正式には Lemma 2 で証明されている)。
訳抜け防止モード: 第3話。 アルゴリズム1は、レンマ2の凸プログラムを解く計算効率のよい方法である。 しかし最も重要なのは k∗ ij の値は d で有界である(これは形式的に記述され、補題 2 で証明される)。
0.55
The latter property is crucial for developing the no-regret algorithm for Fractional Dynamic k-Clustering. 後者の特性は分数動的kクラスタ化のためのno-regretアルゴリズムの開発に不可欠である。 0.63
Up next we present the no-regret algorithm for Fractional Dynamic k-Clustering. 次に、Fractional Dynamic k-Clusteringのためのno-regretアルゴリズムを示す。 0.66
Algorithm 2 A no-regret algorithm for Fractional Dynamic k-Clustering アルゴリズム2 分数動的kクラスタ化のためのno-regretアルゴリズム 0.67
i = k/n for all i ∈ V . すべての i ∈ V に対して i = k/n となる。 0.62
1: Initially, the learner selects y1 2: for rounds t = 1··· T do The learner selects yt ∈ ∆k n. The adversary selects the positions of the clients Rt ⊆ V . 1: まず、学習者は y1 2 を選択する: ラウンド t = 1··· t に対して、学習者は yt ∈ sk n を選択する。 0.67
The learner receives cost, FCRt(yt). 学習者はコスト、FCRt(yt)を受け取る。 0.81
The learner runs Algorithm 1 with input yt and Rt and sets gt for each i ∈ V do 学習者は入力ytとRtでアルゴリズム1を実行し、各i ∈ V doに対してgtを設定する。
訳抜け防止モード: 学習者は入力ytとRtとセットでアルゴリズム1を実行する 各 i ∈ V do に対する gt
0.87
i = −(cid:80) i = −(cid:80) 0.92
j∈Rt kt ij jjrt kt ij 0.69
where  = 9: 10: end for ここで は = 9:10:終了 0.58
end for √ √ log n T 終止符 √ ~ log n T 0.72
Dr yt+1 i = 博士 yt+1 i = 0.78
(cid:80) i · e−gt yt i∈V yt (cid:80) i · e−gt yt ihtmlv yt 0.73
i · e−gt i · e − gt 0.64
i i We conclude the section with Theorem 6 that establishes the no-regret property of 私は 私は 我々は、no-regret特性を定式化する定理6でこの節を締めくくる。 0.48
Algorithm 2 and the proof of which is deferred to the Appendix C. アルゴリズム2と、その証明は、Appendix Cに延期される。 0.67
10 10 0.85
英語(論文から抽出)日本語訳スコア
Theorem 6. Let y1, . 理論6。 y1 とする。 0.65
. . , yT be the sequence of vectors in ∆k clients’ positions R1, . . . yT は yk クライアントの位置 R1, におけるベクトルの列である。 0.83
. . , RT . . . rt である。 0.72
Then, n produced by Algorithm 2 for the そしたら アルゴリズム2で生成されたn 0.69
(cid:16) kDn(cid:112)log nT (cid:16) kDn(cid:112)log nT 0.85
(cid:17) T(cid:88) (cid:17) t(cid:88) 0.79
t=1 FCRt(yt) ≤ min y∗∈∆k t=1。 FCRt(yt) ≤ min yの臨床 0.57
FCRt(y∗) + Θ FCRt(y∗) + ... 0.76
T(cid:88) t=1 t(cid:88) t=1。 0.63
4 A Θ(k)-Regret Deterministic Online Learning Algo- 4 A >(k)-Regret Deterministic Online Learning Algo- 0.82
rithm The basic idea is to use a rounding scheme that given a vector y ∈ ∆k リスム 基本的な考え方は、ベクトル y ∈ yk を与える丸めスキームを使うことである。 0.54
In this section we show how one can use Algorithm 2 described in Section 3 to derive Θ(k)-regret for the Dynamic k-Clustering in polynomial-time. 本節では,3節で記述されたアルゴリズム2を用いて,多項式時間における動的k-クラスタリングの解法について述べる。 0.76
n produces a placement of the k centers Fy ⊆ V (with |Fy| ≤ k) such that for any set of clients’ positions R, the connection cost CR(Fy) is approximately bounded by the factional connection cost FCR(y). n は、任意のクライアントの位置 R に対して、接続コスト CR(Fy) が派閥接続コスト FCR(y) に略有界となるような k 中心の配置(|Fy| ≤ k)を生成する。 0.69
This rounding scheme is described in Algorithm 3. この丸め方式はアルゴリズム3に記述されている。 0.61
Algorithm 3 Deterministic Rounding Scheme 1: Input: A vector y ∈ ∆k n. 2: Output: A set Fy ⊆ V at which centers are opened. アルゴリズム 3 決定論的円周スキーム 1: 入力: ベクトル y ∈ .k n. 2: 出力: 中心が開となる集合 Fy, V 。 0.82
3: Run Algorithm 1 with input y and R = V . 3: 入力 y と R = V でアルゴリズム 1 を実行する。 0.84
4: Sort the positions i ∈ V according to the values βi produced by Algorithm 1. 4: アルゴリズム 1 によって生成される値 βi に従って位置 i ∈ v を並べ替える。 0.81
5: Fy ← ∅ 6: for i = 1 to V do 7: Fy ← Fy ∪ {i} 8: 9: 10: end for 5: Fy = 1 to V do 7: Fy > Fy > {i} 8: 9: 10: end for i = 1 to V do 7 0.65
if minj∈Fy dij > 6k · βi then minjhtmlfy dij > 6k · βi ならば 0.79
end if Lemma 4. [Rounding Lemma] Let Fy denote the positions of the centers produced by Algorithm 3 for input y ∈ ∆k 終われば 第4回。 [ラウンド補題] fy を入力 y ∈ ...k のアルゴリズム 3 が生成する中心の位置とする。 0.65
n. Then the following properties hold, n. すると、以下の性質が成立する。 0.57
• For any set of clients R, • クライアントの任意の集合 r に対して 0.82
CR(Fy) ≤ 6k · FCR(y) CR(Fy) ≤ 6k · FCR(y) 0.92
• The cardinality of Fy is at most k, |Fy| ≤ k. • Fy の濃度は最大 k, |Fy| ≤ k である。 0.74
Up next we show how the deterministic rounding scheme described in Algorithm 3 can be combined with Algorithm 2 to produce an Θ(k)-regret deterministic online learning algorithm that runs in polynomial-time. 次に、アルゴリズム3で記述された決定論的丸めスキームをアルゴリズム2と組み合わせて、多項式時間で実行するθ(k)-regret決定論的オンライン学習アルゴリズムを作成する方法を示す。 0.76
The overall online learning algorithm is described in Algorithm 4 and its regret bound is formally Stated and proven in Theorem 2. オンライン学習アルゴリズムの全体はアルゴリズム4で記述され、その後悔の境界は定理2で正式に記述され証明される。 0.71
11 11 0.85
英語(論文から抽出)日本語訳スコア
Algorithm 4 A Θ(k)-regret deterministic online learning algorithm for Dynamic k-Clustering 1: for rounds t = 1··· T do アルゴリズム4 動的k-クラスタリング 1:ラウンド t = 1··· T do に対するアルゴリズムA(k)-regret決定論的オンライン学習アルゴリズム 0.77
n by running Algorithm 2 for the sequence of n by run Algorithm 2 for the sequence of the sequence 0.92
The learner computes the vector yt ∈ ∆k 学習者はベクトル yt ∈ yk を計算する 0.82
clients’ positions (R1, . クライアントの位置 (R1, . 0.85
. . , Rt−1). . . , Rt−1)。 0.81
The learner places centers to the positions Fyt produced by Algorithm 3 given input The adversary selects the clients’ positions Rt ⊆ V . 学習者は、入力されたアルゴリズム3で生成された位置Fytを中心に配置する。
訳抜け防止モード: 学習者はアルゴリズム3が入力した位置Fytに中心を置く 相手は、クライアントの位置Rt〜Vを選択する。
0.69
The learner suffers connection cost CRt(Fyt) 学習者は接続コストCRt(Fyt)を被る 0.84
2: 3: yt. 4: 5: 6: end for 2: 3: ytだ 4: 5: 6: end for 0.81
We conclude the section with the proof of Theorem 2 in which the regret bounds of 我々は,この節を,後悔が束縛される定理2の証明で締めくくる。 0.59
Algorithm 4 are established. アルゴリズム4が確立される。 0.70
Proof of Theorem 2. The second case of Lemma 4 ensures that |Ft| ≤ k and thus Algorithm 4 opens at most k facilities at each round. 定理2の証明。 Lemma 4 の第二のケースは |Ft| ≤ k であることを保証するので、アルゴリズム 4 は各ラウンドで最大 k 個の施設で開く。 0.63
Applying the first case of Lemma 4 for R = Rt we get that CRt(Ft) ≤ 6k · FCRt(yt). R = Rt に対して Lemma 4 の最初のケースを適用すると、CRt(Ft) ≤ 6k · FCRt(yt) が得られる。 0.84
As a result, where the last inequality follows by Theorem 6. その結果である。 最後の不等式は Theorem 6 で従う。 0.74
However Lemma 1 ensures that しかし lemma 1 は 0.44
T(cid:88) t=1 t(cid:88) t=1。 0.63
CRt(Ft) ≤ T(cid:88) T(cid:88) CRt(Ft) ≤ T(cid:88) T(cid:88) 0.92
t=1 ≤ 6k min y∗∈∆k t=1。 ≤6k分。 0.58
t=1 6k · FCRt(yt) (cid:16) t=1。 6k · fcrt(yt) (cid:16) 0.63
FCRt(y∗) + Θ FCRt(y∗) + ... 0.76
T(cid:88) t=1 t(cid:88) t=1。 0.63
min y∗∈∆k min (複数形 mins) 0.27
FCRt(y∗) ≤ min F ∗:|F ∗|=k FCRt(y∗) ≤ min F ∗:|F ∗|=k 0.85
(cid:17) kDn(cid:112)log nT T(cid:88) (cid:17) kDn(cid:112)log nT T(cid:88) 0.82
CRt(F ∗) t=1 CRt(F ∗) t=1。 0.58
5 A Θ(r)-Regret Randomized Online Learning Algo- 5 A >(r)-Regret Randomized Online Learning Algo- 0.80
rithm In this section we present a Θ(r)-regret randomized online learning algorithm. リスム 本稿では、θ(r)-regretランダム化オンライン学習アルゴリズムを提案する。 0.58
This algorithm is described in Algorithm 5 and is based on the randomized rounding developed by Charikar and Li for the k-median problem [11]. このアルゴリズムはアルゴリズム5で記述され、k-メディア問題[11]のためにcharikarとliによって開発されたランダムな丸みに基づいている。 0.66
Lemma 5 ([11]). lemma 5 ([11]) である。 0.55
There exists a polynomial-time randomized rounding scheme that given a vector y ∈ ∆k n produces a probability distribution, denoted as CL(y), over the subsets of V such that, 多項式時間ランダム化された丸めスキームがあり、ベクトル y ∈ yk n が与えられたとき、V の部分集合上の確率分布 CL(y) が生成される。 0.83
1. with probability 1 exactly k facilities are opened, PF∼CL(y) [|F| = k] = 1. 1 の確率 1 のちょうど k 個の施設が開かれれば、PF =CL(y) [|F| = k] = 1 となる。 0.67
2. for any position j ∈ V , 2 任意の位置 j ∈ v に対して 0.75
(cid:2)C{j}(Fy)(cid:3) ≤ 4 · FC{j}(y). (cid:2)C{j}(Fy)(cid:3) ≤ 4 · FC{j}(y)。 0.96
EF∼CL(y) EF (複数形 EFs) 0.65
12 12 0.85
英語(論文から抽出)日本語訳スコア
Similarly with the previous section, combining the randomized rounding of Charikar-Li with Algorithm 1 produces a Θ(r)-regret randomized online learning algorithm that runs in polynomial-time. 前節と同様に、charikar-liのランダム化ラウンドとアルゴリズム1を組み合わせると、多項式時間で動作するθ(r)-regretランダム化オンライン学習アルゴリズムが生成される。 0.70
Algorithm 5 A Θ(r)-regret randomized online learning algorithm 1: for rounds t = 1··· T do アルゴリズム 5 a θ(r)-regret randomized online learning algorithm 1: for rounds t = 1···t do 0.91
clients’ positions (R1, . クライアントの位置 (R1, . 0.85
. . , Rt−1). . . , Rt−1)。 0.81
randomized rounding with input yt, Ft ∼ CL(yt). 入力 yt, Ft > CL(yt) でランダム化された丸め。 0.63
The learner computes the vector yt ∈ ∆k n by running Algorithm 2 for the sequence of The learner places centers to the positions Ft ⊆ V produced by the Charikar-Li The adversary selects a request Rt ⊆ V . 学習者は、学習者のシーケンスのアルゴリズム2を実行してベクトルyt ∈ sk nを計算し、敵が要求rt s vを選択するカリカーliが生成するft s vの位置に中心を置く。 0.66
The learner suffers connection cost CRt(Ft) 学習者は接続コストCRt(Ft)を被る 0.84
2: 3: 4: 5: 6: end for 2: 3: 4: 5: 6: end for 0.85
The proof of Theorem 4 that establishes the regret bound of Algorithm 5 follows by アルゴリズム5の後悔境界を確立する定理4の証明は次のようになる 0.76
Lemma 5 and Theorem 6 and is deferred to the Appendix E. Lemma 5およびTheorem 6はAppendix Eに延期される。 0.77
6 Experimental Evaluations In this section we evaluate the performance of our online learning algorithm against adversaries that select the positions of the clients according to time-evolving probability distributions. 6実験的評価 本稿では,オンライン学習アルゴリズムの性能を,時間発展する確率分布に応じてクライアントの位置を選択する敵に対して評価する。 0.87
We remark that the regret bounds established in Theorem 2 and Theorem 4 hold even if the adversary maliciously selects the positions of the clients at each round so as to maximize the connection cost. 我々は、敵が各ラウンドでクライアントの位置を悪意的に選択して接続コストを最大化しても、Theorem 2 と Theorem 4 に設定された後悔境界が保持されていることを述べる。 0.69
As a result, in case clients arrive according to some (unknown and possibly time-varying) probability distribution that does not depend on the algorithm’s actions, we expect the regret of to be way smaller. 結果として、アルゴリズムの動作に依存しないいくつかの(未知の、おそらくは時間的変動)確率分布に従ってクライアントが到着した場合、後悔はずっと小さくなることを期待します。 0.75
In this section we empirically evaluate the regret of Algorithm 4 for Dynamic k-Clustering in case p = ∞. この節では、p = ∞ の場合の動的 k-クラスタ化に対するアルゴリズム4の後悔を実証的に評価する。 0.67
We assume that at each round t, 20 clients arrive according to several static or time-varying two-dimensional probability distributions with support on the [−1, 1] × [−1, 1] square and the possible positions for the centers being the discretized grid with  = 0.1. 各円tにおいて、[−1, 1] ×[−1, 1] の正方形を支えた静的あるいは時間変化の2次元確率分布に従って20のクライアントが到着し、中心が 0.1 の離散格子となる可能性のある位置を仮定する。 0.81
In order to monitor the quality of the solutions produced by Algorithm 4, we compare the time-average connection cost of Algorithm 4 with the time-average fractional connection cost of Algorithm 2. アルゴリズム4が生成する解の品質を監視するために,アルゴリズム4の時間平均接続コストとアルゴリズム2の時間平均分数接続コストを比較した。 0.77
Theorem 6 ensures that for T = Θ(k2D2/2) the time-average fractional connection cost of Algorithm 2 is at most  greater than the time-average connection cost of the optimal static solution for Dynamic k-Clustering. 定理6は、t = θ(k2d2/\2) の場合、アルゴリズム2の時間平均分数接続コストは、動的kクラスタ化のための最適な静的解の時間平均接続コストよりも最大で大きいことを保証している。 0.62
In the following simulations we select  = 0.1 and track the ratio between the time-average cost of Algorithm 4 and of Algorithm 2 which acts as an upper bound on the regret. 以下のシミュレーションでは,アルゴリズム4の時間平均コストと,後悔の上限として機能するアルゴリズム2の時間平均コストの比率を追跡する。 0.65
Uniform Square In this case the 20 clients arrive uniformly at random in the [−1, 1] × [−1, 1] square. 一様正方形 この場合、20のクライアントは [−1, 1] × [−1, 1] の二乗においてランダムにランダムに到着する。 0.73
Figure 2 illustrates the solutions at which Algorithm 4 converges for k = 2, 3 and 8 as long as the achieved regret. 図2は、アルゴリズム4がk = 2, 3, 8に対して達成された後悔の限り収束する解を示します。 0.75
Uniform Distribution with Time-Evolving Centers In this case the 20 clients arrive according to the uniform distribution with radius 0.3 and a time-varying center that periodically follows the trajectory described in Example 1. 時間進化中心を用いた均一分布 この場合、20のクライアントは半径0.3の均一分布に従って到着し、例1に示す軌道を周期的に追従する時間変化中心となる。 0.77
Figure 1 depicts the centers at which Algorithm 4 converges after 100k2 rounds which are clearly close to the optimal ones. 図1は、アルゴリズム4が最適なものに近い100k2ラウンドの後に収束する中心を示しています。 0.75
13 13 0.85
英語(論文から抽出)日本語訳スコア
Figure 2: The green curve depicts the time-average connection cost Algorithm 4, the red curve depicts the time-average fractional connection cost of Algorithm 2 and the blue curve depicts their ratio that acts as an upper bound on the regret. 図2:緑曲線は時間平均接続コストアルゴリズム4を、赤曲線はアルゴリズム2の時間平均分数接続コストを、青曲線は後悔の上限となるそれらの比率を描いている。 0.69
Moving-Clients on the Ellipse In this case the 20 clients move in the ellipse(cid:0) x (cid:1)2 + (cid:1)2 = 1 with different speeds and initial positions. 楕円上の移動クライアント この場合、20のクライアントは、速度と初期位置の異なる楕円(cid:0) x (cid:1)2 + (cid:1)2 = 1 に移動する。 0.72
The position of client i is given by クライアント i の位置が与えられる 0.67
1.2 (cid:0) y 1.2 (cid:0)y 0.63
0.6 (xi(t), yi(t)) = (1.2 cos(2πfit + θi), 0.6 sin (2πfit + θi)) where each fi, θi was selected uniformly 0.6 (xi(t), yi(t)) = (1.2 cos(2πfit + θi), 0.6 sin(2πfit + θi) それぞれのfi, θiが一様に選択される。 0.71
14 14 0.85
英語(論文から抽出)日本語訳スコア
at random in [0, 1]. ランダムな[0, 1]. 0.56
Figure 3 illustrates how Algorithm 4 converges to the underlying ellipse as the number of rounds increases. 図3は、ラウンド数の増加に伴ってアルゴリズム4がelipseにどのように収束するかを示しています。 0.62
Figure 3: The solution produced by Algorithm 4 for k = 8 after 100, 1000 and 10000 rounds. 図3: 100, 1000, 10000ラウンドの後、k = 8のアルゴリズム4によって生成されるソリューション。 0.79
Mixture of Multivariate Guassians In this case 15 clients arrive according to the Gaussian with µ1 = (−0.7, 0.7) and Σ1 = [[0.3, 0], [0, 0.3]] and 5 according to the Gaussian with µ2 = (0.7,−0.7) and Σ2 = [[0.3, 0], [0, 0.3]]. 多変量ガウスの混合 この場合、15のクライアントは、μ1 = (−0.7, 0.7) と Σ1 = [[0.3, 0], [0, 0.3]] と 5 と、μ2 = (0.7, −0.7) と Σ2 = [[0.3, 0], [0, 0.3]] でガウスに到達する。 0.80
All the clients outside the [−1, 1] × [−1, 1] are projected back to the square. 外部のすべてのクライアント [−1, 1] × [−1, 1] は正方形に投影される。 0.74
Figure 4 illustrates the solutions at which Algorithm 4 converges for k = 2, 8 and 16. 図4は、k = 2, 8, 16 に対してアルゴリズム4が収束する解を示す。 0.82
7 Conclusion This work studies polynomial-time low-regret online learning algorithms for Dynamic kClustering, an online learning problem capturing clustering settings with time-evolving clients for which no information on their locations over time is available. 7 結論 この研究は、動的kClusteringのための多項式時間低レベルのオンライン学習アルゴリズムについて研究する。これは、時間とともに位置情報が得られない時間進化クライアントによるクラスタリング設定をキャプチャするオンライン学習問題である。 0.65
We show that, under some well-established conjectures, O(1)-regret cannot be achieved in polynomial time and we provide a Θ(min(k, r))-regret polynomial time algorithm with r being the maximum number of clients appearing in a single round. いくつかのよく確立された予想の下では、O(1)-regretは多項式時間では達成できないことを示し、単一のラウンドに出現するクライアントの最大数 r を持つ シュ(min(k, r))-regret 多項式時間アルゴリズムを提供する。 0.77
At a technical level, we present a two-step approach where in the first step we provide a no-regret algorithm for the Fractional Dynamic k-Clustering while in the second step we provide online rounding scheme converting the 技術的レベルでは、2段階のアプローチを示し、第1段階ではフラクショナルダイナミックk-クラスタリングのための非回帰アルゴリズムを提供し、第2段階ではオンラインラウンドリングスキームを変換する。 0.79
15 15 0.85
英語(論文から抽出)日本語訳スコア
Figure 4: On the left, the solutions which Algorithm 4 converges for k = 2, 8 and k = 16. 図4: 左側では、アルゴリズム4の解は k = 2, 8 と k = 16 に対して収束する。 0.83
On the right, the time-average cost of Algorithm 4, Algorithm 2 and the regret bounds. 右側では、アルゴリズム4、アルゴリズム2の時間平均コストと後悔の限界がある。 0.74
sequence of fractional solutions, produced by the no-regret algorithm, into solutions of Dynamic k-Clustering. no-regretアルゴリズムによって生成される分数解の列は、動的k-クラスタリングの解となる。 0.58
Applying the same approach to other combinatorial online learning problems is an interesting research direction. 同じアプローチを他の組合せオンライン学習問題に適用することは、興味深い研究方向である。
訳抜け防止モード: 同じアプローチを他の組合せオンライン学習問題に適用する 興味深い研究の方向性です
0.84
16 16 0.85
英語(論文から抽出)日本語訳スコア
References [1] Alekh Agarwal, Daniel J. Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire. 参考文献 [1] Alekh Agarwal, Daniel J. Hsu, Satyen Kale, John Langford, Lihong Li, Robert E. Schapire 0.73
Taming the monster: A fast and simple algorithm for contextual bandits. taming the monster: コンテキストバンディットの高速でシンプルなアルゴリズム。 0.66
In Proceedings of the 31th International Conference on Machine Learning, ICML 2014. 第31回In Proceedings of the 31th International Conference on Machine Learning, ICML 2014に参加して 0.75
[2] Nir Ailon. Improved bounds for online learning over the permutahedron and other ranking polytopes. [2]ナイロン。 permutahedronや他のランキングポリトープに対するオンライン学習の限界の改善。 0.60
In Proceedings of the 17th International Conference on Artificial Intelligence and Statistics, AISTATS 2014. 第17回人工知能・統計国際会議(AISATS 2014)に参加して 0.65
[3] Soroush Alamdari and David Shmoys. Soroush Alamdari氏とDavid Shmoys氏。 0.60
A Bicriteria Approximation Algorithm for the ビクトリリア近似アルゴリズム 0.28
k-Center and k-Median Problems, pages 66–75. k-Center and k-Median Problems, page 66-75。 0.64
01 2018. [4] Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. 01 2018. [4]Hyung-Chan An、Ashkan Norouzi-Fard、Ola Svensson。 0.83
Dynamic facility location via exponential clocks. 動的施設位置 指数時計を使って 0.66
ACM Trans. Algorithms, 13(2):21:1–21:20, 2017. ACMトランス。 アルゴリズム 13(2):21:1:21:20, 2017 0.68
[5] Benny Applebaum. ベニー・アップルバウム(Benny Applebaum)。 0.51
Pseudorandom generators with long stretch and low locality from random local one-way functions. ランダムな局所的片方向関数からの長いストレッチと低い局所性を持つ擬似乱数生成器 0.61
In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 805–816. 第44回 ACM Symposium on Theory of Computing, STOC ’12, page 805–816 に参加して 0.73
Association for Computing Machinery, 2012. アソシエーション・フォー・コンピューティング・マシンズ、2012年。 0.52
[6] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. 6] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit。 0.71
Local search heuristic for k-median and facility location problems. k-メディアと施設位置問題に対する局所探索ヒューリスティック 0.73
In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC ’01, page 21–29. 第33回年次acmコンピューティング理論シンポジウムの議事録において、soc ’01, page 21-29。 0.73
Association for Computing Machinery, 2001. アソシエーション・フォー・コンピューティング・マシンズ、2001年。 0.51
[7] Baruch Awerbuch and Robert Kleinberg. Baruch Awerbuch氏とRobert Kleinberg氏。 0.63
Online linear optimization and adaptive routing. オンライン線形最適化と適応ルーティング。 0.80
J. Comput. Syst. J.Comput シスト。 0.65
Sci., 2008. [8] Maria-Florina Balcan and Avrim Blum. 2008年、同上。 8]maria-florina balcanとavrim blum。 0.64
Approximation algorithms and online mecha- 近似アルゴリズムとオンラインメカ 0.82
nisms for item pricing. In ACM Conference on Electronic Commerce, 2006. 商品価格のニム。 2006年、acm電子商取引会議に参加。 0.63
[9] Moses Charikar and Sudipto Guha. 9]モーゼス・チャリカーとスディプト・グハ。 0.47
Improved combinatorial algorithms for the facility location and k-median problems. 施設配置とk-median問題の組合せアルゴリズムの改善 0.77
In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99. 第40回コンピュータ科学基礎シンポジウム(FOCS'99)に参加して 0.60
IEEE Computer Society, 1999. IEEE Computer Society、1999年。 0.89
[10] Moses Charikar, Sudipto Guha, ´Eva Tardos, and David B. Shmoys. 10]Moses Charikar, Sudipto Guha, ́Eva Tardos, David B. Shmoys。 0.74
A constant-factor approximation algorithm for the k-median problem (extended abstract). k中間問題に対する定数係数近似アルゴリズム(拡張抽象)。 0.73
In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99, page 1–10. 第30回 ACM Symposium on Theory of Computing, STOC '99, page 1–10 に参加して 0.75
Association for Computing Machinery, 1999. アソシエーション・フォー・コンピューティング・マシンズ、1999年。 0.52
[11] Moses Charikar and Shi Li. [11]モーゼス・チャリカーとシーリ。 0.57
A dependent lp-rounding approach for the k-median problem. k中間問題に対する依存的なlp-roundingアプローチ 0.68
In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, volume 7391 of Lecture Notes in Computer Science, pages 194–205. Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012 volume 7391 of Lecture Notes in Computer Science, page 194–205 0.80
Springer, 2012. [12] Eden Chlamt´ac, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca. 2012年春。 Eden Chlamt ́ac, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca. 0.59
The densest k-subhypergraph problem. 最も密度の高いk-サブハイパーグラフ問題。 0.38
Leibniz International Proceedings in Informatics (LIPIcs). Leibniz International Proceedings in Informatics (LIPIcs) の略。 0.83
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2016 0.89
17 17 0.85
英語(論文から抽出)日本語訳スコア
[13] Eden Chlamt´aˇc, Michael Dinitz, and Yury Makarychev. 13] エデン・クラムト・アシック、マイケル・ディニッツ、ユーリー・マカリチェフ。 0.43
Minimizing the union: Tight approximations for small set bipartite vertex expansion. 和の最小化:小集合二部頂点展開に対する密接な近似。 0.72
In Proceedings of the TwentyEighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, page 881–899. TwentyEighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, page 881–899 (英語) 0.79
Society for Industrial and Applied Mathematics, 2017. 工業・応用数学会、2017年。 0.63
[14] Bart de Keijzer and Dominik Wojtczak. 14] Bart de Keijzer と Dominik Wojtczak。 0.73
Facility reallocation on the line. 路線上の施設再配置。 0.53
In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, pages 188–194. 第27回人工知能国際合同会議(IJCAI 2018)において、188-194頁。 0.62
[15] Sina Dehghani, MohammadTaghi Hajiaghayi, Hamid Mahini, and Saeed Seddighin. 15]Sina Dehghani, MohammadTaghi Hajiaghayi, Hamid Mahini, Saeed Seddighin。 0.61
Price of competition and dueling games. arXiv preprint arXiv:1605.04004, 2016. 競争と決闘の価格。 arXiv preprint arXiv:1605.04004, 2016 0.67
[16] Miroslav Dud´ık, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan. 16] Miroslav Dud ́ık, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan 0.77
Oracle-efficient online learning and auction design. Oracle効率のよいオンライン学習とオークションデザイン。 0.67
In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017. 第58回IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017に参加して 0.84
[17] Miroslav Dud´ık, Daniel J. Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. 15] Miroslav Dud ́ık, Daniel J. Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang 0.78
Efficient optimal learning for contextual bandits. コンテキストバンディットの効率的な最適学習 0.70
In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI 2011. 人工知能における不確実性に関する第27回国際会議(UAI 2011)に参加して 0.55
[18] David Eisenstat, Claire Mathieu, and Nicolas Schabanel. 18]ダヴィッド・アイゼンスタット、クレア・マチュー、ニコラス・シャバネル 0.41
Facility location in evolving metrics. 進化するメトリクスにおける施設の位置。 0.47
In Automata, Languages, and Programming - 41st International ColloquiumICALP 2014, volume 8573 of Lecture Notes in Computer Science, pages 459–470. Automata, Languages, and Programming - 41st International ColloquiumICALP 2014 volume 8573 of Lecture Notes in Computer Science, page 459–470。 0.83
Springer. [19] Dimitris Fotakis, Loukas Kavouras, Panagiotis Kostopanagiotis, Philip Lazos, Stratis Skoulakis, and Nikos Zarifis. Springer Dimitris Fotakis, Loukas Kavouras, Panagiotis Kostopanagiotis, Philip Lazos, Stratis Skoulakis, Nikos Zarifis. 0.58
Reallocating multiple facilities on the line. 沿線に複数の施設を配置する。 0.62
In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, pages 273–279, 2019. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, pages 273–279, 2019 0.94
[20] Dimitris Fotakis, Thanasis Lianeas, Georgios Piliouras, and Stratis Skoulakis. Dimitris Fotakis, Thanasis Lianeas, Georgios Piliouras, Stratis Skoulakis. 0.57
Efficient online learning of optimal rankings: Dimensionality reduction via gradient descent. 最適ランキングの効率的なオンライン学習:勾配降下による次元化 0.81
In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020. in advances in neural information processing systems 33: annual conference on neural information processing systems 2020, neurips 2020, 2020 (英語) 0.78
[21] Takahiro Fujita, Kohei Hatano, and Eiji Takimoto. [21]藤田孝広、波多野幸平、滝本英二 0.43
Combinatorial online prediction via metarounding. metaroundingによるコンビネートリアルオンライン予測。 0.58
In 24th International Conference on Algorithmic Learning Theory, ALT 2013. 第24回アルゴリズム学習理論国際会議(ALT 2013)に参加して 0.69
[22] Dan Garber. ダン・ガーバー(Dan Garber)。 0.61
Efficient online linear optimization with approximation algorithms. 近似アルゴリズムを用いた効率的なオンライン線形最適化 0.68
In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS 2017. 第30回ニューラル情報処理システム国際会議(NEPS 2017)に参加して 0.61
[23] Elad Hazan. [23]エラード・ハザン。 0.47
Introduction to online convex optimization. オンライン凸最適化入門 0.63
Found. Trends Optim., 見つかった トレンドオプティマイト。 0.56
2(3–4):157–325, 2016. 2(3–4):157–325, 2016. 0.76
18 18 0.85
英語(論文から抽出)日本語訳スコア
[24] Elad Hazan, Wei Hu, Yuanzhi Li, and Zhiyuan Li. [24]Elad Hazan、Wei Hu、Yuanzhi Li、Zhiyuan Li。 0.59
Online improper learning with an approximation oracle. 近似オラクルを用いたオンライン不適切な学習 0.67
In Advances in Neural Information Processing Systems, NeurIPS 2018. ニューラル情報処理システムの進歩,NeurIPS 2018 0.59
[25] Elad Hazan and Satyen Kale. [25]Elad HazanとSatyen Kale。 0.70
Online submodular minimization. オンラインサブモジュラー最小化。 0.65
J. Mach. Learn. J. Mach 学ぶ。 0.72
Res., 2012. Res. 2012. 0.75
[26] Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz. [26]Elad Hazan、Satyen Kale、Shai Shalev-Shwartz。 0.71
Near-optimal algorithms for online オンラインの準最適アルゴリズム 0.71
matrix prediction. In 25th Annual Conference on Learning Theory, COLT 2012. マトリックス予測 第25回学習理論会議(COLT 2012)に参加して 0.61
[27] Elad Hazan and Tomer Koren. [27]Elad HazanとTomer Koren。 0.68
The computational power of optimization in online learning. オンライン学習における最適化の計算能力 0.83
In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, STOC 2016. 第48回 ACM Symposium on Theory of Computing, STOC 2016 に参加して 0.72
[28] David P. Helmbold, Robert E. Schapire, and M. Long. [28]David P. Helmbold、Robert E. Schapire、M. Long。 0.84
Predicting nearly as well as the ほぼ同じ程度に予測し 0.58
best pruning of a decision tree. 決定の木の 最高の刈り取りだ 0.71
In Machine Learning, 1997. 1997年、機械学習を専攻。 0.73
[29] David P. Helmbold and Manfred K. Warmuth. 29] david p. helmboldとmanfred k. warmuth。 0.71
Learning permutations with exponential weights. 指数重み付き置換を学習する。 0.56
In Proceedings of the 20th Annual Conference on Learning Theory, COLT 2007. 第20回学習理論会議(COLT 2007)に参加して 0.66
[30] Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz. Nicole Immorlica氏、Adam Tauman Kalai氏、Brendan Lucier氏、Ankur Moitra氏、Andrew Postlewaite氏、Moshe Tennenholtz氏。 0.66
Dueling algorithms. デュエルアルゴリズム。 0.36
In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 215–224, New York, NY, USA, 2011. The Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 215–224, New York, NY, USA, 2011 に参加して 0.91
Association for Computing Machinery. アソシエーション・フォー・コンピューティング・マシンズ(Association for Computing Machinery)の略。 0.36
[31] Kamal Jain and Vijay V. Vazirani. 31]kamal jainとvijay v. vazirani。 0.55
Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. 原始双対スキーマとラグランジュ緩和を用いた計量施設位置とk-メディア問題に対する近似アルゴリズム 0.76
J. ACM, 48(2):274–296, 2001. J. ACM, 48(2):274-296, 2001 0.86
[32] Stefanie Jegelka and Jeff A. Bilmes. Stefanie Jegelka氏とJeff A. Bilmes氏。 0.72
Online submodular minimization for combinatorial structures. 組合せ構造のためのオンラインサブモジュラー最小化。 0.78
In Proceedings of the 28th International Conference on Machine Learning, ICML 2011. 第28回In Proceedings of the 28th International Conference on Machine Learning, ICML 2011に参加して 0.73
[33] Sham Kakade, Adam Tauman Kalai, and Katrina Ligett. [33]Sham Kakade、Adam Tauman Kalai、Katrina Ligett。 0.63
Playing games with approximation algorithms. 近似アルゴリズムでゲームをする。 0.77
In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC 2007. 第39回 ACM Symposium on Theory of Computing, STOC 2007 に参加して 0.73
[34] Adam Kalai and Santosh Vempala. [34]Adam KalaiとSantosh Vempala。 0.74
Efficient algorithms for online decision problems. オンライン意思決定問題の効率的なアルゴリズム。 0.69
In J. Comput. 院 J.Comput 0.58
Syst. Sci. Springer, 2003. シスト。 Sci 2003年、春。 0.56
[35] Wouter M. Koolen, Manfred K. Warmuth, and Jyrki Kivinen. [35]Wouter M. Koolen、Manfred K. Warmuth、Jyrki Kivinen。 0.73
Hedging structured concepts. ヘッジ構造 コンセプトだ 0.66
In the 23rd Conference on Learning Theory, COLT 2010, 2010. 第23回学習理論会議(COLT 2010, 2010)に参加。 0.79
[36] Amit Kumar. Amit Kumar (複数形 Amit Kumars) 0.61
Constant factor approximation algorithm for the knapsack median problem. knapsack中央値問題に対する定数係数近似アルゴリズム 0.68
In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, page 824–832. Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, page 824–832 (英語) 0.85
Society for Industrial and Applied Mathematics, 2012. 工業・応用数学会、2012年。 0.61
19 19 0.85
英語(論文から抽出)日本語訳スコア
[37] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes [37]Amit Kumar,Yogish Sabharwal,Sandeep Sen.線形時間近似法 0.74
for clustering problems in any dimensions. あらゆる次元の クラスタリング問題に対してです 0.65
J. ACM, 57(2), 2010. j. acm, 57(2), 2010年。 0.76
[38] Shi Li and Ola Svensson. [38]Shi LiとOla Svensson。 0.77
Approximating k-median via pseudo-approximation . 擬似近似によるk-median近似 0.56
SIAM J. Comput., 45(2):530–547, 2016. SIAM J。 背番号45(2):530-547, 2016。 0.71
[39] Jyh-Han Lin and Jeffrey Scott Vitter. [39]jyh-han linとjeffrey scott vitter。 0.72
Approximation algorithms for geometric median 幾何中央値の近似アルゴリズム 0.78
problems. Information Processing Letters, 44(5):245 – 249, 1992. 問題だ Information Processing Letters, 44(5):245 – 249, 1992 0.73
[40] M.E.J. [40]M.E.J. 0.68
Newman. The structure and function of complex networks. 新人。 複雑なネットワークの構造と機能。 0.59
SIAM review, 45(2):167–256, 2003. SIAM参照。 45(2):167–256, 2003. 0.72
[41] Romualdo Pastor-Satorras and Alessandro Vespignani. [41] romualdo pastor-satorras と alessandro vespignani 0.79
Epidemic Spreading in Scale-Free スケールフリーのエピデミック・スプレッド 0.51
Networks. Physical Review Letters, 86(14):3200–3203, 2001. ネットワーク。 Physical Review Letters, 86(14):3200–3203, 2001 0.86
[42] Holakou Rahmanian and Manfred K. K Warmuth. 42] holakou rahmanianとmanfred k. k warmuth。 0.68
Online dynamic programming. オンライン動的プログラミング。 0.90
In Advances in Neural Information Processing Systems, NIPS 2017. 院 ニューラル情報処理システムの進歩 - NIPS 2017 0.53
[43] Juliette Stehl´e, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-Fran¸cois Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne R´egis, Bruno Lina, and Philippe Vanhems. 43] Juliette Stehl ́e, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-Fran scois Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne R ́egis, Bruno Lina, Philippe Vanhems 0.90
High-resolution measurements of face-to-face contact patterns in a primary school. 小学校における対面接触パターンの高分解能計測 0.77
PLOS ONE, 6(8), 2011. PLOS ONE, 6(8) 2011年。 0.77
[44] Matthew J. Streeter and Daniel Golovin. 44]Matthew J. StreeterとDaniel Golovin。 0.77
An online algorithm for maximizing submodular functions. サブモジュラー関数を最大化するオンラインアルゴリズム。 0.73
In 22nd Annual Conference on Neural Information Processing Systems, NIPS 2008. 第22回神経情報処理システム年会(nips 2008)に参加して 0.67
[45] Daiki Suehiro, Kohei Hatano, Shuji Kijima, Eiji Takimoto, and Kiyohito Nagano. 【45】末広大樹・波多野幸平・木島周司・滝本英司・長野清人 0.39
Online prediction under submodular constraints. サブモジュール制約下でのオンライン予測 0.60
In Algorithmic Learning Theory, ALT 2012. アルゴリズム学習理論において、alt 2012。 0.80
[46] Eiji Takimoto and Manfred K. Warmuth. [46]滝本英治とマンフレッド・K・ウォーマス 0.53
Predicting nearly as well as the best pruning 最善の刈り取りと ほぼ同等の予測を 0.67
of a planar decision graph. 平面的な決定グラフです 0.70
In Theoretical Computer Science, 2000. 理論計算機科学、2000年。 0.74
[47] Eiji Takimoto and Manfred K. Warmuth. [47]滝本英治とマンフレッド・K・ウォーマス 0.50
Path kernels and multiplicative updates. パスカーネルと乗法的な更新。 0.44
J. Mach. Learn. J。 Mach 学ぶ。 0.64
Res., 2003. 2003年、デビュー。 0.59
[48] Chayant Tantipathananandh, Tanya Berger-Wolf, and David Kempe. [48]Tantipathananandh、Tanya Berger-Wolf、David Kempe。 0.66
A framework for community identification in dynamic social networks. 動的ソーシャルネットワークにおけるコミュニティ識別のためのフレームワーク 0.89
In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’07, page 717–726. 第13回 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’07, page 717–726 に参加して 0.85
Association for Computing Machinery, 2007. アソシエーション・フォー・コンピューティング・マシンズ、2007年。 0.46
[49] David P. Williamson and David B. Shmoys. David P. Williamson and David B. Shmoys 0.63
The Design of Approximation Algorithms. 近似アルゴリズムの設計。 0.56
Cambridge University Press, USA, 1st edition, 2011. ケンブリッジ大学出版局、2011年、第1版。 0.59
[50] Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto, and Masayuki Takeda. [50]正太安武、波多野幸平、木島周二、滝本英治、武田正之 0.44
Online linear optimization over permutations. 置換によるオンライン線形最適化。 0.63
In Proceedings of the 22nd International Conference on Algorithms and Computation, ISAAC 2011. 第22回International Conference on Algorithms and Computation, ISAAC 2011に参加して 0.82
20 20 0.85
英語(論文から抽出)日本語訳スコア
[51] Neal E. Young. [51] ニール・e・ヤング 0.65
K-medians, facility location, and the chernoff-wald bound. k-medians, facility location, and the chernoff-wald bound。 0.76
In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00, page 86–95. 第11回 ACM-SIAM Symposium on Discrete Algorithms, SODA ’00, page 86–95 に参加して 0.80
Society for Industrial and Applied Mathematics, 2000. 工業・応用数学会、2000年。 0.64
21 21 0.85
英語(論文から抽出)日本語訳スコア
Appendix A Proof of Theorem 1 Problem 2 (k−CenterUniform). 付録 定理 1 問題 2 (k-CenterUniform) の証明。 0.60
Given a uniform metric space d : V ×V (cid:55)→ R≥0 (d(u, v) = 1 in case (u (cid:54)= v)) and a set of requests R1, . 一様距離空間 d : V × V (cid:55) → R≥0 (d(u, v) = 1 のとき (u (cid:54)= v)) と要求の集合 R1, が与えられる。 0.83
. . , Rm ⊆ V . . . と、RmはV。 0.78
Select F ⊆ V such as |F| = k and f| = k や k のような f を選べばよい。 0.56
(cid:80)m s=1 CRs(F ) is minimized where p is ∞. (cid:80)m s=1 CRs(F ) は p が ∞ であるときに最小化される。 0.70
Lemma 6. Any c-approximation algorithm for k − CenterUniform implies a c-approximation algorithm for Min − p − Union. 第6回。 k − centeruniform の任意の c-近似アルゴリズムは min − p − union の c-近似アルゴリズムを意味する。 0.64
Proof. Given the collection U = {S1, . 証明。 集合 U = {S1, が与えられた。 0.63
. . , Sm} of the Min− p− Union, we construct a uniform metric space V of size m, where each node of V corresponds to a set Si. . . , Sm} of the Min− p− Union, we construct a uniform metric space V of size m, where each node of V is correspond to a set Si. 0.88
For each elements e ∈ E of the Min − p − Union we construct a request Re ⊆ V for the k − CenterUniform that is composed by the nodes corresponding to the sets Si that containt e. Observe that due to the uniform metric and the fact that p = ∞, for any V (cid:48) ⊆ V min − p − union の各元 e ∈ e に対して、k − centeruniform に対する要求 re s v を構成するが、これは e を含む集合 si に対応するノードによって構成される。
訳抜け防止モード: Min − p − Union の各元 e ∈ E に対して、一様計量により観測される集合 Si に対応するノードによって構成される k − CenterUniform に対する要求 Re > V を構築する。 そして p = ∞ であるという事実は、任意の V ( cid:48 ) > V に対してである。
0.89
(cid:88) e∈E (cid:88) e.e.e. 0.50
CRe(V (cid:48)) = | ∪Si /∈V (cid:48) Si| CRe(V (cid:48)) = | >Si /∂V (cid:48) Si| 0.70
Lemma 7. Any polynomial time c-regret algorithm for the online k-Center implies a (c + 1)approximation algorithm (offline) for the k − CenterUniform. 第7回。 オンラインk-Centerに対する任意の多項式時間c-regretアルゴリズムは、k − CenterUniformに対する(c + 1)近似アルゴリズム(オフライン)を意味する。 0.66
Proof. Let assume that that there exists a polynomial-time online learning algorithm such that for any request sequence R1, . 証明。 任意の要求シーケンス R1 に対して多項式時間オンライン学習アルゴリズムが存在すると仮定する。 0.71
. . , RT , . . RT, RT。 0.78
T(cid:88) t=1 t(cid:88) t=1。 0.63
E[CRt(Ft)] ≤ c min |F ∗|=k E[CRt(Ft)] ≤ c min |F ∗|=k 0.92
E[CRt(F ∗)] + Θ(poly(n, D) · T α) E[CRt(F ∗)] + >(ポリ(n, D) · T α) 0.72
T(cid:88) t=1 t(cid:88) t=1。 0.63
m(cid:88) s=1 m(cid:88) s=1 0.71
for some α < 1. Now let the requests lie on the uniform metric, p = ∞ and that the adversary at each round t selects uniformly at random one of the requests R1, . α < 1 の場合 このとき、要求は一様計量 p = ∞ に置き、各円 t の敵は要求 R1, のランダムな 1 で一様選択する。 0.60
. . , Rm that are given by the instance of k − CenterUniform. . . k − CenterUniform のインスタンスによって与えられる Rm である。 0.83
In this case the above equation takes the following form, この場合、上記の方程式は以下の形を取る。 0.77
T(cid:88) m(cid:88) t(cid:88) m(cid:88) 0.82
1 m E[CRs(Ft)] ≤ c 1m E[CRs(Ft)] ≤ c 0.78
T m t=1 s=1 Tm t=1。 s=1 0.52
E[CRs(OPT∗)] + Θ(nβ · T α) E[CRs(OPT∗)] + (nβ · T α) 0.78
where OPT∗ is the optimal solution for the instance of k − CenterUniform and Ft is the random set that the online algorithm selects at round t. ここで OPT∗ は k − CenterUniform のインスタンスの最適解であり、Ft はオンラインアルゴリズムが円 t で選択するランダム集合である。 0.81
Now consider the following randomized algorithm for the k − CenterUniform. さて、次の k − centeruniform のランダム化アルゴリズムを考える。 0.76
1. Select uniformly at random a t from {1, . 1. a t を {1, からランダムに選択する。 0.78
. . , T}. 2. . . , T。 2. 0.77
Select a set F ⊆ V according to the probability distribution Ft. 確率分布Ftに応じて集合 F × V を選択する。 0.74
22 22 0.85
英語(論文から抽出)日本語訳スコア
The expected cost of the above algorithm, denoted by E[ALG], is 上記のアルゴリズムの予測コストは、E[ALG]で表される。 0.66
T(cid:88) m(cid:88) t(cid:88) m(cid:88) 0.82
t=1 i=1 1 T t=1。 i=1 1T 0.60
EF∼Ft [CRi(F )] = m · ≤ c · m EF-Ft [CRi(F )] = m · ≤ c · m 0.86
1 m EF∼Ft [CRi(F )] 1m EF\Ft [CRi(F )] 0.84
CRi(OPT∗) (cid:32) CRi(OPT∗) (cid:32) 0.82
m(cid:88) T(cid:88) m(cid:88) (cid:18) m · nβ (cid:19) m(cid:88) T(cid:88) m(cid:88) (cid:18) m · nβ (cid:19) 0.78
1 T · T m t=1 1T·Tm t=1。 0.52
i=1 i=1 T + Θ i=1 i=1 T + Θ 0.72
T 1−α (cid:33) t1α (cid:33) 0.72
By selecting T = Θ(m t = θ(m) を選択することで 0.63
1 1−α · n β 1−α ) we get that E[ALG] ≤ (c + 1) · OPT∗. 1 1−α·n β 1−α ) e[alg] ≤ (c + 1) · opt∗ となる。 0.80
B Proof of Theorem 3 Let the metric space be composed by k + 1 points with the distance between any pair of (different) points being 1. b 定理の証明 3 距離空間を、任意の対(異なる)点の間の距離が 1 である k + 1 個の点で構成する。 0.75
At each round t, there exists a position at which the learner has not placed a facility (there are k + 1 positions and k facilities). 各ラウンドtには、学習者が施設を設置していない位置(k + 1 の位置と k の施設がある)が存在する。 0.71
If the adversary places one client at the empty position of the metric space, then the deterministic online learning algorithm admits overall connection cost equal to T . 相手が1つのクライアントを計量空間の空の位置に置くと、決定論的オンライン学習アルゴリズムは全体の接続コストをTに等しいと認める。 0.77
However the optimal static solution that leaves empty the position with the least requests pays at most T /(k + 1). しかし、最も要求の少ない位置を空にする最適の静的解は、T/(k + 1) で支払う。 0.67
C Omitted Proof of Section 3 第3節のCオミテッド証明 0.66
C.1 Proof of Lemma 2 C.1 Lemma 2の証明 0.80
The Langragian of the convex program of Definition 2 is, 定義 2 の凸プログラムのラングラジアンは、 0.58
(cid:32) 1 −(cid:88) (cid:88) (cid:32) 1 −(cid:88) (cid:88) 0.78
i∈V µij · xij I・V μij·xij 0.54
Aj · (cid:33) Aj · (cid:33) 0.82
xij i∈V j∈R Xij I-V jjr 0.55
L(β, y, x, A, k, λ) = L(β, y, x, A, k, λ) = 0.85
+ + Rearranging the terms we get, + + 条件を再設定する。 0.69
L(β, y, x, A, k, λ) = L(β, y, x, A, k, λ) = 0.85
+ + (cid:33)1/p + + (cid:33)1/p 0.78
(cid:32)(cid:88) (cid:88) (cid:88) (cid:32)(cid:88)(cid :88) 0.93
j∈R i∈V j∈V jjr I-V jjv 0.45
βp j j∈R (cid:88) βp j jjr (cid:88) 0.70
j∈R λj · (dijxij − βj) + jjr λj · (dijxij − βj) + 0.89
(cid:88) kij · (xij − yi) −(cid:88) (cid:88) Aj −(cid:88) (cid:88) (cid:88) (cid:33)1/p (cid:32)(cid:88) (cid:88) Kij · (xij − yi) −(cid:88) (cid:88) Aj −(cid:88) (cid:88) (cid:33)1/p (cid:32)(cid:88) 0.84
(cid:88) kij · yi (cid:88) Kij ·yi 0.72
−(cid:88) j∈R -(cid:88) jjr 0.66
j∈R i∈V βp j jjr I-V βp j 0.58
j∈R j∈R λj · βj jjr jjr λj · βj 0.55
23 j∈R i∈V xij · (kij − µij + dij · λj − Aj) 23 jjr i・V xij ·(kij − μij + dij · λj − Aj) 0.72
英語(論文から抽出)日本語訳スコア
In order for the function g(A, k, λ) = minβ,y,x,M +,M− L(β, y, x, A, k, λ) to get a finite value the following constraints must be satisfied, 関数 g(a, k, λ) = minβ,y,x,m +,m−l(β, y, x, a, k, λ) が有限値を得るためには、以下の制約を満たす必要がある。 0.80
• kij + dij · λj − Aj = µij p ≤ 1 since otherwise • ||λ||∗ • Kij + dij · λj − Aj = μij p ≤ 1 である。 0.81
(cid:16)(cid:80) j∈R Aj −(cid:80) (cid:16)(cid:80)jjav ar aj −(cid:80) 0.72
(cid:17)1/p −(cid:80) (cid:80) j∈R kij · yi. (cid:17)1/p −(cid:80) (cid:80) jhtmlr kij · yi。 0.75
Using the fact that the Lagragian multipliers µij ≥ 0, we get the constraints of the convex program of Lemma 2. Lagragian multipliers μij ≥ 0 であるという事実を用いて、Lemma 2 の凸プログラムの制約を得る。 0.73
The objective comes from the fact that once g(A, k, λ) admits a finite 目的は、g(A, k, λ) が有限であるという事実に由来する。 0.78
value then g(A, k, λ) =(cid:80) 値 g(a, k, λ) =(cid:80) 0.85
i∈V j∈R βp ihtmlv jjrβp 0.46
j j∈R λj · βj can become −∞. j jjr λj · βj は −∞ となる。 0.77
FCR(y(cid:48)) = FCR(y(cid:48)) = 0.96
C.2 Proof of Lemma 3 j , k∗ j , A∗ Let λ∗ ij denote the values of the respective variables in the optimal solution of the convex program of Lemma 2 formulated with respect to the vector y = (y1, . C.2 Lemma 3 j , k∗ j , A∗ の証明 λ∗ ij は、ベクトル y = (y1, ) に対して定式化された Lemma 2 の凸プログラムの最適解における各変数の値を表す。 0.85
. . , yn). . . , yn)。 0.81
Respectively consider λ(cid:48) j, k(cid:48) j, A(cid:48) ij denote the values of the respective variables in the optimal solutions of the convex program of Lemma 2 formulated with respect to the vector y(cid:48) = (y(cid:48) それぞれλ(cid:48) j, k(cid:48) j, a(cid:48) ij はベクトル y(cid:48) = (y(cid:48) に対して定式化された lemma 2 の凸プログラムの最適解における各変数の値を表す。 0.83
1, . . . , y(cid:48) 1, . . . , y(cid:48) 0.86
n). (cid:88) ≥ (cid:88) (cid:88) n)。 (cid:88) ≥ (cid:88) (cid:88) 0.76
j∈R j∈R = A(cid:48) jjr jjr = A(第48回) 0.57
A∗ i∈V j∈R A∗ I-V jjr 0.55
(cid:88) j −(cid:88) (cid:88) j −(cid:88) (cid:88) j −(cid:88) (cid:88) (cid:88) (cid:88) j −(cid:88) (cid:88) j −(cid:88) (cid:88) j −(cid:88) (cid:88) (cid:88) 0.78
j∈R j∈R i∈V jjr jjr I-V 0.43
i∈V i i ij · y(cid:48) k(cid:48) ij · y(cid:48) k∗ (cid:88) ij · y(cid:48) k∗ i∈V ij · (yi − y(cid:48) k∗ i) I-V 私は 私は ij · y(cid:48) k(cid:48) ij · y(cid:48) k∗ (cid:88) ij · y(cid:48) k∗ i⋅V ij · (yi − y(cid:48) k∗ i) 0.58
i + j∈R A∗ i + jjr A∗ 0.69
(cid:88) = FCR(y) + (cid:88) = FCR(y) + 0.82
ij · yi −(cid:88) Equations 5 and 6 follow by strong duality, more precisely FCR(y) =(cid:80) (cid:80) j −(cid:80) which defines FCR(y(cid:48)) (respectively for FCR(y(cid:48)) =(cid:80) (cid:80) j∈R Aj −(cid:80) ij · yi −(cid:88) 方程式 5 と 6 は、より正確には fcr(y) =(cid:80) (cid:80) (cid:80) j −(cid:80) であり、fcr(y(cid:48)) を定義する(fcr(y(cid:48)) =(cid:80) (cid:80) に対して)。 0.75
ij· j∈R k∗ yi since the convex program of Lemma 2 is the dual of the convex program the solution of i). Lemma 2 の凸プログラムは、i の解である凸プログラムの双対であるからである。 0.53
Equation 4 is implied by the fact that the solution (λ(cid:48), k(cid:48), A(cid:48)) is optimal when the objective function is i. 方程式 4 は、解 (λ(cid:48), k(cid:48), A(cid:48)) が目的関数が i であるときに最適であるという事実によって表される。 0.78
Notice that the constraints of the convex program in Lemma 2 do not depend on the y-values. 補題 2 における凸プログラムの制約は y-値に依存しないことに注意。 0.78
As a result, the solution (λ∗, k∗, A∗) (that is optimal for the dual convex program formulated for y) is feasible for the dual program formulated for the values y(cid:48). その結果、解 (λ∗, k∗, A∗) (y で定式化された双対凸プログラムに最適) は y(cid:48) で定式化された双対プログラムに対して実現可能である。 0.84
Thus Equation 4 follows by the optimality of (λ(cid:48), k(cid:48), A(cid:48)). したがって方程式 4 は (λ(cid:48), k(cid:48), a(cid:48)) の最適性によって従う。 0.76
(cid:88) j∈R (cid:88) jjr 0.61
ij · yi k∗ ij · yi k∗ 0.98
j∈R A∗ j∈R k(cid:48) jjr a∗ jhtmlr k(cid:48) 0.44
i∈V ij · y(cid:48) ijavav ij · y(cid:48) 0.65
j−(cid:80) j-(cid:80) 0.76
j∈R kij · y(cid:48) jjrkij·y(cid:48) 0.66
j∈R A(cid:48) jjr a(cid:48) 0.63
(cid:80) (cid:80) (cid:80) (cid:80) 0.78
j∈R j∈R k∗ jjr jjr k∗ 0.55
i∈V i∈V i∈V I-V I-V I-V 0.43
i∈V Up next we prove the correctness of Algorithm 1. I-V 次に,アルゴリズム1の正しさを証明する。 0.58
Notice that the the solution β, x that Algorithm 1 constructs is feasible for the primal convex program of Definition 2. アルゴリズム 1 が構成する解 β, x が定義 2 の主凸プログラムに対して実現可能であることに注意せよ。 0.83
We will prove that the dual solution that Algorithm 1 constructs is feasible for the dual of Lemma 2 while the exact same value is obtained. アルゴリズム1が構成する双対解は、全く同じ値が得られながら、Lemma 2の双対に対して実現可能であることを証明します。 0.70
(3) (4) (5) (3) (4) (5) 0.85
(6) • ||λ||∗ • dij · λj + kij ≥ Aj : In case dij < D∗ (6) • ||λ||∗ • dij · λj + Kij ≥ Aj : 例えば dij < D∗ 0.87
p = 1: It directly follows by the fact that λj = p = 1: λj = であることから直接従う。 0.85
inequality directly follows. In case dij ≤ D∗ 不平等は直接続く dij ≤ D∗ の場合 0.75
24 (cid:104) βj 24 (cid:104)βj 0.77
||β||p (cid:105)p−1 |β|p (cid:105)p−1 0.55
(cid:104)(cid:80) (cid:104)(cid:80) 0.75
(cid:105) p−1 (cid:105)p−1 0.62
p . and ||λ||∗ p . および ||λ||∗ 0.75
p = p p−1 j∈R λ j p = pp−1jhtmlr λj 0.80
j , Algorithm 1 implies that xij = yi and the j the inequality holds trivially since kij = 0. j , アルゴリズム 1 は xij = yi であり、j の不等式は kij = 0 であるため自明である。 0.80
英語(論文から抽出)日本語訳スコア
Now consider the objective function, さて、目的関数を考える。 0.73
(cid:88) j∈R (cid:88) jjr 0.61
Aj −(cid:88) Aj −(cid:88) 0.88
(cid:88) i∈V (cid:88) I-V 0.61
j∈R yi · kij = jjr yi · kij = 0.64
= = = = j∈R = = = = jjr 0.77
j∈R (cid:88) (cid:88) (cid:88) (cid:88) (cid:32)(cid:88) jjr (cid:88) (cid:88) (cid:88) (cid:88) (cid:32)(cid:88) 0.58
j∈R j∈R j∈R jjr jjr jjr 0.43
Aj −(cid:88) (cid:88) λj · Dj −(cid:88) (cid:88) Aj −(cid:88) (cid:88) λj · Dj −(cid:88) (cid:88) 0.80
j∈R j∈R dij · xij jjr jjr dij · xij 0.48
i∈V + λj j yi · kij i・V+ λj j yi · kij 0.75
(cid:88) yi (cid:88) ユイ 0.69
i∈V + j i∈V + λj · βj i・V+ j ihtmlv + λj · βj 0.68
j (cid:33)1/p j (cid:33)1/p 0.75
βp j (cid:20) βp j (cid:20) 0.83
λj · xij yi λj · xij yi 0.98
(Dj − dij) (Dj − dij) 0.85
(cid:21) (7) (cid:21) (7) 0.82
where Equation 8 follows by the fact that xij = 0 for all j /∈ V + xij = 1. ここで方程式8は、すべての j に対して xij = 0 であるという事実によって従う。 0.77
Finally notice that |λj| ≤ 1 and thus kij ≤ D where D is the diameter of the metric space. 最後に |λj| ≤ 1 であることに気付き、従って kij ≤ d は距離空間の直径である。 0.75
j∈V + j j and thus(cid:80) jjv+ j j と so(cid:80) 0.76
C.3 Proof of Theorem 6 By Lemma 3, |gt that c.3 補題 3 |gt による定理 6 の証明 0.82
j∈Rt kt∗ i| = | −(cid:80) jjrt kt∗ i| = | −(cid:80) 0.72
i∈V Applying Lemma 3 for y(cid:48) = y∗, y(cid:48) = y∗ に対して Lemma 3 を適用する。 0.58
t=1 T(cid:88) t=1。 t(cid:88) 0.63
(cid:0)FCRt(yt) − FCRt(y∗)(cid:1) ≤ T(cid:88) (cid:0)FCRt(yt) − FCRt(y∗)(cid:1) ≤ T(cid:88) 0.95
t=1 t=1 i ) ≤ Θ (cid:88) t=1。 t=1。 i ) ≤ θ (cid:88) 0.60
i∈V T(cid:88) ihtmlv t(cid:88) 0.59
ij| ≤ Dr since |Rt| ≤ r. Applying Theorem 1.5 of [23] we get (cid:88) ij| ≤ Dr since |Rt| ≤ r. Applying Theorem 1.5 of [23] we get (cid:88) 0.84
kDr(cid:112)log nT kDr(cid:112)log nT 0.92
(cid:16) (cid:17) (cid:16) (cid:17) 0.78
i − y∗ gt i(yt i − y∗ gt i(yt) 0.95
gt i(yt i − y∗ gt i(yt) i − y∗ 0.95
i ) ≤ Θ (cid:16) i ) ≤ θ (cid:16) 0.78
kDr(cid:112)log nT kDr(cid:112)log nT 0.92
(cid:17) D Omitted Proof of Section 4 (cid:17) 第4節の疑似証明 0.68
D.1 Proof of Lemma 4 D.1 Lemma 4 の証明 0.80
The following claim trivially follows by Step 10 of Algorithm 4. 以下の主張はアルゴリズム4のステップ10で自明に従う。 0.73
Claim 1. For any node j ∈ V , d(j, Fy) ≤ 6k · β∗ j . クレーム1。 任意のノード j ∈ V に対して d(j, Fy) ≤ 6k · β∗ j である。 0.64
We are now ready to prove the first item of Lemma 4. 私たちは現在、Lemma 4の最初の項目を証明する準備ができています。 0.57
Let a request R ⊆ V , 要求 R を V とする。 0.62
CR(Fy) = d(j, Fy)p CR(Fy) = d(j, Fy)p 0.85
(6k)p · β ∗p j (6k)p·β ∗p j 0.84
= 6k · ∗p β j 6k · ∗p β j 0.85
(cid:33)1/p (cid:33)1/p 0.65
(cid:33)1/p (cid:33)1/p 0.65
(cid:32)(cid:88) (cid:32)(cid:88) 0.75
j∈R (cid:32)(cid:88) jjr (cid:32)(cid:88) 0.59
j∈R (cid:33)1/p jjr (cid:33)1/p 0.54
(cid:32)(cid:88) (cid:32)(cid:88) 0.75
j∈R ≤ 25 jjr ≤ 25 0.71
英語(論文から抽出)日本語訳スコア
(cid:88) We proceed with the second item of Lemma 4. (cid:88) 以下はLemma 4の2番目の項目である。 0.70
For a given node j ∈ S, let Bj = {i ∈ V : 与えられたノード j ∈ S に対して、Bj = {i ∈ V : 0.82
dij ≤ 3k · β∗ dij ≤ 3k · β∗ 0.88
j}. It is not hard to see that for any j ∈ Fy, j}。 任意の j ∈ Fy に対してそれを見るのは難しくない。 0.80
Observe that in case the latter is not true then (cid:80) 後者が真実でない場合は観察する(cid:80) 0.72
i∈Bj yi ≥ 1 − 1 3k ijavabj yi ≥ 1 − 1 3k 0.72
j > β∗ β∗ j . j>β∗ β∗ j。 0.79
The second important step of the proof is that for any j, j(cid:48) ∈ Fy, 証明の第二の重要なステップは、任意の j に対して j(cid:48) ∈ Fy である。 0.73
i /∈Bj ij ≥ 1 x∗ i‐Bj ij ≥ 1 x∗ 0.79
3k , which would imply that Bj ∩ Bj(cid:48) = ∅. 3kというのは Bj (cid:48) = Bj (cid:48)。 0.64
Observe that in case there was m ∈ Bj∩Bj(cid:48) would imply d(j, m) ≤ 3k·β∗ By the triangle inequality we get d(j, j(cid:48)) ≤ 6k · β∗ j(cid:48) (without loss of generality β∗ latter contradicts with the fact that both j and j(cid:48) belong in set Fy. d(j, m) ≤ 3k·β∗ 三角形の不等式により d(j, j(cid:48)) ≤ 6k · β∗ j(cid:48) が得られる(一般性の欠如なしに、β∗ の後者は、j と j(cid:48) が共に集合 Fy に属するという事実と矛盾する)。 0.84
yi ≥ |Fy| · (1 − 1 i∈V yi = k. As a result, |Fy| ≤ k. yi ≥ |fy| · (1 − 1 iبv yi = k) 結果として |fy| ≤ k となる。
訳抜け防止モード: yi ≥ |Fy| · ( 1 − 1 i∂V yi = k となる。 |Fy| ≤ k。
0.90
Now assume that |Fy| ≥ k + 1. ここで |Fy| ≥ k + 1 とする。 0.73
Then(cid:80) But the latter contradicts with the fact that(cid:80) では (cid:80) しかし後者は (cid:80) 0.73
j ≤ β∗ 3k ) ≥ (k + 1) · (1 − 1 j ≤ β∗ 3k ) ≥ (k + 1) · (1 − 1) 0.97
j and d(j(cid:48), m) ≤ 3k·β∗ j(cid:48). j と d(j(cid:48), m) ≤ 3k·β∗ j(cid:48) である。 0.76
j(cid:48)). j (cid:48)。 0.90
The 3k ) > k. i∈Fy 3k)>k。 I-FY 0.52
E Omitted Proofs of Section 5 Proof of Theorem 4. E Omitted Proofs of Section 5 Proof of Theorem 4 0.75
To simplify notation the quantity EF∼CL(yt)[CRt(F )] is denoted as E[CRt(Ft)]. 表記を簡略化するために、EF\CL(yt)[CRt(F )]をE[CRt(Ft)]と表記する。 0.67
At first notice that by the first case of Lemma 5, Algorithm 5 ensures that exactly k facilities are opened at each round t. まず、lemma 5の最初の場合、アルゴリズム5は、各ラウンドtで正確にk個の施設が開いていることを保証する。 0.66
Concerning its overall expected connection cost we get, 全体的な接続コストについてです 0.49
E [CRt(Fyt)] ≤(cid:88) E [CRt(Fyt)] ≤(cid:88) 0.85
E[C{j}(Fyt)] ≤ 4 E[C{j}(Fyt)] ≤ 4 0.78
j∈Rt where the fist inequality is due to the fact that(cid:80) (cid:88) T(cid:88) T(cid:88) jjrt フィストの不等式は、(cid:80) (cid:88) T(cid:88) T(cid:88) 0.65
E[CRt(Fyt)] ≤ 4 E[CRt(Fyt)] ≤ 4 0.77
T(cid:88) t=1 t(cid:88) t=1。 0.63
t=1 j∈Rt (cid:88) d(j, F )p ≤(cid:16)(cid:80) t=1。 jjrt (cid:88) d(j, F )p ≤(cid:16)(cid:80) 0.64
FC{j}(yt) j∈Rt FC{j}(yt) jjrt 0.69
second is derived by applying the second case of Lemma 5. 第2はLemma 5の2番目のケースを適用して導かれる。 0.58
We overall get, (cid:17)p 全体としては (cid:17)p 0.73
d(j, F ) and the d(j, F) そして... 0.59
j∈Rt ≤ 4 t=1 jjrt ≤ 4 t=1。 0.62
≤ 4r min y∗ ≤ 4r min y∗ 0.84
+ Θ FC{j}(yt) + Θ FC{j}(yt) 0.85
FCRt(y∗) j∈Rt |Rt| · FCRt(yt) T(cid:88) (cid:17) kDr(cid:112)log nT T(cid:88) (cid:17) kDr(cid:112)log nT FCRt(y∗) j・Rt |Rt| · FCRt(yt) T(cid:88) (cid:17) kDr(cid:112)log nT T(cid:88) (cid:17) kDr(cid:112)log nT 0.82
t=1 t=1 (cid:16) (cid:16) t=1。 t=1。 (cid:16)(cid:16) 0.55
≤ 4r min |F ∗|=k ≤ 4r min |F ∗|=k 0.78
E[CRt(F ∗)] E[CRt(F ∗)] 0.66
+ Θ 26 (8) + Θ 26 (8) 0.85
英語(論文から抽出)日本語訳スコア
where inequality 3 follows by the fact that FC{j}(y) ≤ FC{R}(y) for all j ∈ R and the last two inequalities follow by Theorem 6 and Lemma 1 respectively. ここでの不等式 3 は、すべての j ∈ R に対して FC{j}(y) ≤ FC{R}(y) と最後の 2 つの不等式はそれぞれ Theorem 6 と Lemma 1 に従うという事実によって従う。 0.78
27 27 0.85
                                                       ページの最初に戻る

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