論文の概要: Near-Polynomially Competitive Active Logistic Regression
- arxiv url: http://arxiv.org/abs/2503.05981v3
- Date: Sat, 22 Mar 2025 23:43:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-25 14:29:24.086725
- Title: Near-Polynomially Competitive Active Logistic Regression
- Title（参考訳）: ほぼ多項式的に競合するアクティブロジスティック回帰
- Authors: Yihan Zhou, Eric Price, Trung Nguyen,
- Abstract要約: 能動的学習は受動的学習と比較して指数関数的に少ないラベルクエリを必要とすることはよく知られている。
入力毎に最適なアルゴリズムと競合する最初のアルゴリズムを示す。
我々のアルゴリズムは効率的なサンプリングに基づいており、より一般的な関数のクラスを学習できるように拡張することができる。
- 参考スコア（独自算出の注目度）: 6.600655187282174
- License:
- Abstract: We address the problem of active logistic regression in the realizable setting. It is well known that active learning can require exponentially fewer label queries compared to passive learning, in some cases using $\log \frac{1}{\eps}$ rather than $\poly(1/\eps)$ labels to get error $\eps$ larger than the optimum. We present the first algorithm that is polynomially competitive with the optimal algorithm on every input instance, up to factors polylogarithmic in the error and domain size. In particular, if any algorithm achieves label complexity polylogarithmic in $\eps$, so does ours. Our algorithm is based on efficient sampling and can be extended to learn more general class of functions. We further support our theoretical results with experiments demonstrating performance gains for logistic regression compared to existing active learning algorithms.
- Abstract（参考訳）: 実測可能な環境でのアクティブロジスティック回帰の問題に対処する。
能動的学習は、パッシブラーニングに比べて指数関数的に少ないラベルクエリを必要とすることがよく知られており、時には、最適な値より大きい値にエラーを取得するために$\log \frac{1}{\eps}$を$\poly(1/\eps)$ラベルの代わりに$\eps$を使用する場合もある。
入力インスタンス毎に最適なアルゴリズムと多項式的に競合する最初のアルゴリズムを提案する。
特に、もしあるアルゴリズムが$\eps$でラベル複雑性の多元対数を達成するなら、私たちもそうする。
我々のアルゴリズムは効率的なサンプリングに基づいており、より一般的な関数のクラスを学習できるように拡張することができる。
我々は,既存の能動学習アルゴリズムと比較して,ロジスティック回帰に対する性能向上を示す実験により,理論的結果をさらに支援する。
関連論文リスト
- A Competitive Algorithm for Agnostic Active Learning [5.4579367210379335]
アクティブな学習のための最も一般的なアルゴリズムは、不一致係数と呼ばれるパラメータでその性能を表現する。
我々は、任意の二進仮説クラス$H$と分布$D_X$ over$X$に対して最適なアルゴリズムと競合するアルゴリズムを得る。
我々のアルゴリズムの$O(log |H|)$オーバーヘッドよりは、NPハードである。
論文 参考訳（メタデータ） (2023-10-28T19:01:16Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Turing-Universal Learners with Optimal Scaling Laws [2.7485183218472016]
我々は,全ての学習アルゴリズムにおいて,最適な分布依存率を実現する「ユニバーサル学習者」アルゴリズムの存在を観察する。
構成そのものは、レヴィンの普遍探索の単純な拡張である(Levin, 1973)
論文 参考訳（メタデータ） (2021-11-09T18:44:35Z) - Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。
結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
論文 参考訳（メタデータ） (2021-10-08T08:22:05Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。
正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文 参考訳（メタデータ） (2020-06-22T17:53:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。