論文の概要: Noise misleads rotation invariant algorithms on sparse targets

• arxiv url: http://arxiv.org/abs/2403.02697v1
• Date: Tue, 5 Mar 2024 06:25:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-06 16:02:33.391611
• Title: Noise misleads rotation invariant algorithms on sparse targets
• Title（参考訳）: スパースターゲットにおけるノイズミスリード回転不変アルゴリズム
• Authors: Manfred K. Warmuth (1), Wojciech Kot{\l}owski (2), Matt Jones (3), Ehsan Amid (1) ((1) Google Inc., (2) Institute of Computing Science, Poznan University of Technology, Poznan, Poland, (3) University of Colorado Boulder, Colorado, USA)
• Abstract要約: 回転不変アルゴリズムのクラスは疎線形問題を学習するのに最適であることを示す。 回転対称問題に対してベイズ最適アルゴリズムの下位境界を用いてこれを証明する。 次に、単純な非回転不変アルゴリズムに対して、同じ問題に対してより低い上限を証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It is well known that the class of rotation invariant algorithms are suboptimal even for learning sparse linear problems when the number of examples is below the "dimension" of the problem. This class includes any gradient descent trained neural net with a fully-connected input layer (initialized with a rotationally symmetric distribution). The simplest sparse problem is learning a single feature out of $d$ features. In that case the classification error or regression loss grows with $1-k/n$ where $k$ is the number of examples seen. These lower bounds become vacuous when the number of examples $k$ reaches the dimension $d$. We show that when noise is added to this sparse linear problem, rotation invariant algorithms are still suboptimal after seeing $d$ or more examples. We prove this via a lower bound for the Bayes optimal algorithm on a rotationally symmetrized problem. We then prove much lower upper bounds on the same problem for simple non-rotation invariant algorithms. Finally we analyze the gradient flow trajectories of many standard optimization algorithms in some simple cases and show how they veer toward or away from the sparse targets. We believe that our trajectory categorization will be useful in designing algorithms that can exploit sparse targets and our method for proving lower bounds will be crucial for analyzing other families of algorithms that admit different classes of invariances.
• Abstract（参考訳）: 回転不変アルゴリズムのクラスは、例の数が問題の「次元」以下であるとき、スパース線形問題を学習しても準最適であることが知られている。 このクラスは、完全に接続された入力層(回転対称分布で初期化)を持つ勾配降下訓練ニューラルネットを含む。 最も単純な問題は、$d$の機能からひとつの機能を学ぶことです。 この場合、分類エラーや回帰損失は、1-k/n$で増加する。 これらの下限は、例の$k$が次元$d$に達すると空白になる。 このスパース線形問題にノイズを加えると、回転不変量アルゴリズムは$d$以上の例を見ても最適でないことが分かる。 我々は、回転対称性問題に対するベイズ最適アルゴリズムの下限を通してこれを証明する。 すると、単純非回転不変アルゴリズムの同じ問題において、より低い上限が証明される。 最後に、多くの標準最適化アルゴリズムの勾配流れの軌跡を単純なケースで解析し、スパースターゲットへの進入や遠ざかる方法を示す。 我々は、軌道分類はスパース目標を活用できるアルゴリズムを設計するのに有用であると信じており、より低い境界を証明できる手法は、異なる不変性のクラスを許容する他のアルゴリズム群を分析するのに不可欠である。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• 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)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Robust estimation via generalized quasi-gradients [28.292300073453877]
  最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。 我々は「一般化された準次数」の存在を識別する 一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-05-28T15:14:33Z)
• Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
  多次元回帰を用いた固定設計の基本問題について検討する。 我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。 提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
  論文  参考訳（メタデータ） (2020-03-24T19:39:34Z)

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

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