論文の概要: On Reductions and Representations of Learning Problems in Euclidean Spaces
- arxiv url: http://arxiv.org/abs/2411.10784v1
- Date: Sat, 16 Nov 2024 12:09:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-19 14:35:37.785371
- Title: On Reductions and Representations of Learning Problems in Euclidean Spaces
- Title（参考訳）: ユークリッド空間における学習問題の削減と表現について
- Authors: Bogdan Chornomaz, Shay Moran, Tom Waknine,
- Abstract要約: 多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。
我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。
また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
- 参考スコア（独自算出の注目度）: 15.07787640047213
- License:
- Abstract: Many practical prediction algorithms represent inputs in Euclidean space and replace the discrete 0/1 classification loss with a real-valued surrogate loss, effectively reducing classification tasks to stochastic optimization. In this paper, we investigate the expressivity of such reductions in terms of key resources, including dimension and the role of randomness. We establish bounds on the minimum Euclidean dimension $D$ needed to reduce a concept class with VC dimension $d$ to a Stochastic Convex Optimization (SCO) problem in $\mathbb{R}^D$, formally addressing the intuitive interpretation of the VC dimension as the number of parameters needed to learn the class. To achieve this, we develop a generalization of the Borsuk-Ulam Theorem that combines the classical topological approach with convexity considerations. Perhaps surprisingly, we show that, in some cases, the number of parameters $D$ must be exponentially larger than the VC dimension $d$, even if the reduction is only slightly non-trivial. We also present natural classification tasks that can be represented in much smaller dimensions by leveraging randomness, as seen in techniques like random initialization. This result resolves an open question posed by Kamath, Montasser, and Srebro (COLT 2020). Our findings introduce new variants of \emph{dimension complexity} (also known as \emph{sign-rank}), a well-studied parameter in learning and complexity theory. Specifically, we define an approximate version of sign-rank and another variant that captures the minimum dimension required for a reduction to SCO. We also propose several open questions and directions for future research.
- Abstract（参考訳）: 多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1の分類損失を実数値の代理損失に置き換え、分類タスクを確率的最適化に効果的に還元する。
本稿では,このような削減の表現性について,次元とランダム性の役割を含む重要な資源の観点から検討する。
我々は、最小ユークリッド次元$D$で、VC次元$d$をStochastic Convex Optimization (SCO)問題に還元するために必要な概念クラスを$\mathbb{R}^D$で定め、クラスを学ぶのに必要なパラメータの数としてVC次元の直観的な解釈を公式に扱う。
これを達成するために、古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。
意外なことに、あるケースではパラメータの数がVC次元の$d$よりも指数関数的に大きくなければならない。
また、ランダム初期化のような手法で見られるように、ランダム性を利用して、はるかに小さな次元で表現できる自然な分類タスクも提示する。
この結果は、Kamath、Montasser、Srebro(COLT 2020)によるオープンな質問を解決する。
本研究は, 学習と複雑性理論のパラメータとして, 新たな変種である 'emph{dimension complexity}('emph{sign-rank}' とも呼ばれる)を紹介した。
具体的には、符号ランクの近似バージョンと、SCO への還元に必要な最小次元をキャプチャする別の変種を定義する。
また,今後の研究に向けて,いくつかのオープンな質問や方向性も提案する。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Trading off Consistency and Dimensionality of Convex Surrogates for the
Mode [6.096888891865663]
結果が$n$以上の多重クラス分類では、結果は少なくとも次元が$n-1$の実数に埋め込まれなければならない。
本稿では,サロゲート損失次元のトレードオフ,問題インスタンス数,単純度における一貫性領域の制限について検討する。
整合性を持つ各点の質量分布の周りには、単純体の実次元部分集合が存在するが、$n-1$次元に満たない場合、幻覚と呼ばれる現象が起こる分布が存在することを示す。
論文 参考訳（メタデータ） (2024-02-16T16:42:09Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms [17.12280360174073]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
論文 参考訳（メタデータ） (2022-01-31T18:17:25Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Adversarial Classification: Necessary conditions and geometric flows [0.7614628596146599]
本研究では,ある逆数分類法を用いて,ある距離から最大$varepsilon$までデータ入力を不正に入力する逆数分類法について検討する。
我々は、分類境界の変化を$varepsilon$の変分として追跡するために使用できる幾何学的進化方程式を導出する。
論文 参考訳（メタデータ） (2020-11-21T14:14:12Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。