論文の概要: Lower Bounds for Greedy Teaching Set Constructions

• arxiv url: http://arxiv.org/abs/2505.03223v1
• Date: Tue, 06 May 2025 06:30:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-07 18:50:11.237317
• Title: Lower Bounds for Greedy Teaching Set Constructions
• Title（参考訳）: グリーディ・インストラクション・セット構築のための下界
• Authors: Spencer Compton, Chirag Pabbaraju, Nikita Zhivotovskiy,
• Abstract要約: 我々は、小さな$k$に対してgreedyアルゴリズムの性能の低いバウンダリを証明した。 ほとんどの場合、我々の下界は小さな定数$c>0$に対して$k le lceil c d rceil$まで伸びる。
• 参考スコア（独自算出の注目度）: 12.186950360560145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fundamental open problem in learning theory is to characterize the best-case teaching dimension $\operatorname{TS}_{\min}$ of a concept class $\mathcal{C}$ with finite VC dimension $d$. Resolving this problem will, in particular, settle the conjectured upper bound on Recursive Teaching Dimension posed by [Simon and Zilles; COLT 2015]. Prior work used a natural greedy algorithm to construct teaching sets recursively, thereby proving upper bounds on $\operatorname{TS}_{\min}$, with the best known bound being $O(d^2)$ [Hu, Wu, Li, and Wang; COLT 2017]. In each iteration, this greedy algorithm chooses to add to the teaching set the $k$ labeled points that restrict the concept class the most. In this work, we prove lower bounds on the performance of this greedy approach for small $k$. Specifically, we show that for $k = 1$, the algorithm does not improve upon the halving-based bound of $O(\log(|\mathcal{C}|))$. Furthermore, for $k = 2$, we complement the upper bound of $O\left(\log(\log(|\mathcal{C}|))\right)$ from [Moran, Shpilka, Wigderson, and Yuhudayoff; FOCS 2015] with a matching lower bound. Most consequentially, our lower bound extends up to $k \le \lceil c d \rceil$ for small constant $c>0$: suggesting that studying higher-order interactions may be necessary to resolve the conjecture that $\operatorname{TS}_{\min} = O(d)$.
• Abstract（参考訳）: 学習理論における根本的な開問題は、有限VC次元$d$を持つ概念クラス$\mathcal{C}$の最良のケースの教育次元$\operatorname{TS}_{\min}$を特徴づけることである。 この問題の解決は、特に[Simon and Zilles; COLT 2015] が提起した再帰的指導次元に関する予想上界を決着させる。 以前の研究では、自然なグリーディアルゴリズムを用いて教育セットを再帰的に構築し、$\operatorname{TS}_{\min}$の上界を証明し、最もよく知られた境界は$O(d^2)$ [Hu, Wu, Li, and Wang; COLT 2017] である。 各反復において、この欲求アルゴリズムは、概念クラスを最も制限する$k$ラベル付き点を追加することを選択する。 この研究では、この欲求的アプローチのパフォーマンスに小さな$k$でより低い限界を証明します。 具体的には、$k = 1$の場合、このアルゴリズムは$O(\log(|\mathcal{C}|))$の半値で改善されないことを示す。 さらに、$k = 2$の場合、[Moran, Shpilka, Wigderson, Yuhudayoff; FOCS 2015] から$O\left(\log(\log(|\mathcal{C}|))\right)$の上限を補完する。 大抵の場合、我々の下界は、小さな定数$c>0$に対して$k \le \lceil c d \rceil$まで伸びる: $\operatorname{TS}_{\min} = O(d)$という予想を解決するためには、高次の相互作用を研究する必要があることを示唆する。

関連論文リスト

• Partially Unitary Learning [0.0]
  ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。 この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-16T17:13:55Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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