論文の概要: Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach

• arxiv url: http://arxiv.org/abs/2106.05445v1
• Date: Thu, 10 Jun 2021 01:08:51 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-11 14:06:34.225162
• Title: Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
• Title（参考訳）: 準ニュートン法の局所収束のグローバル化:適応サンプルサイズアプローチ
• Authors: Qiujiang Jin, Aryan Mokhtari
• Abstract要約: 準ニュートン法の超線形収束を利用する適応型サンプルサイズスキームを, 学習過程を通じて, 全世界的に活用する。 初期サンプルサイズが十分に大きく、準ニュートン法を用いて各サブプロブレムを解くと、サブプロブレムは超直線的に高速に解けることを示す。
• 参考スコア（独自算出の注目度）: 33.21301562890201
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the application of quasi-Newton methods for solving empirical risk minimization (ERM) problems defined over a large dataset. Traditional deterministic and stochastic quasi-Newton methods can be executed to solve such problems; however, it is known that their global convergence rate may not be better than first-order methods, and their local superlinear convergence only appears towards the end of the learning process. In this paper, we use an adaptive sample size scheme that exploits the superlinear convergence of quasi-Newton methods globally and throughout the entire learning process. The main idea of the proposed adaptive sample size algorithms is to start with a small subset of data points and solve their corresponding ERM problem within its statistical accuracy, and then enlarge the sample size geometrically and use the optimal solution of the problem corresponding to the smaller set as an initial point for solving the subsequent ERM problem with more samples. We show that if the initial sample size is sufficiently large and we use quasi-Newton methods to solve each subproblem, the subproblems can be solved superlinearly fast (after at most three iterations), as we guarantee that the iterates always stay within a neighborhood that quasi-Newton methods converge superlinearly. Numerical experiments on various datasets confirm our theoretical results and demonstrate the computational advantages of our method.
• Abstract（参考訳）: 本稿では,大規模なデータセット上で定義された経験的リスク最小化(ERM)問題に対する準ニュートン法の適用について検討する。 従来の決定論的および確率的準ニュートン法はそのような問題を解決するために実行することができるが、その大域収束率は一階法よりも良くなく、局所超線形収束は学習プロセスの終わりにのみ現れることが知られている。 本稿では,準ニュートン法の超線形収束を利用する適応的サンプルサイズスキームを用いて,学習過程全体を通して学習を行う。 提案する適応型サンプルサイズアルゴリズムの主な考え方は,まずデータポイントの小さなサブセットから出発し,その統計的精度で対応するEMM問題を解き,次いで,サンプルサイズを幾何的に拡大し,それに対応する問題の最適解を,その後のERM問題をより多くのサンプルで解くための初期点として利用することである。 初期サンプルサイズが十分に大きく、準ニュートン法を用いて各サブプロブレムを解くと、準ニュートン法が超直線的に収束する近傍で常にイテレートが維持されることを保証するため、サブプロブレムは超直線的に(少なくとも3回の反復で)解ける。 各種データセットの数値実験により理論的結果を確認し,提案手法の計算上の利点を実証した。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Model-Free Active Exploration in Reinforcement Learning [53.786439742572995]
  強化学習における探索問題について検討し,新しいモデルフリーソリューションを提案する。 我々の戦略は、最先端の探査アプローチよりも高速に効率的な政策を特定できる。
  論文  参考訳（メタデータ） (2024-06-30T19:00:49Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Robust empirical risk minimization via Newton's method [9.797319790710711]
  実験的リスク最小化のためのニュートン法の新しい変種について検討した。 目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。 また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T18:54:54Z)
• A Neural Network Warm-Start Approach for the Inverse Acoustic Obstacle Scattering Problem [7.624866197576227]
  本稿では,逆散乱問題の解法として,ニューラルネットワークのウォームスタート手法を提案する。 トレーニングされたニューラルネットワークを用いて最適化問題の初期推定を求める。 このアルゴリズムは散乱場の測定においてノイズに対して頑健であり、また限られた開口データに対して真の解に収束する。
  論文  参考訳（メタデータ） (2022-12-16T22:18:48Z)
• 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)
• New Methods for Detecting Concentric Objects With High Accuracy [0.0]
  デジタルデータに幾何学的オブジェクトを適合させることは、虹彩検出、自律ナビゲーション、産業ロボット操作など、多くの分野において重要な問題である。 データに幾何学的形状を合わせるには、幾何学的(定形)アプローチと代数的(非定形)アプローチの2つの一般的なアプローチがある。 他の反復的手法の信頼性の高い初期推定として使用できる新しい推定器を開発した。
  論文  参考訳（メタデータ） (2021-02-16T08:19:18Z)
• Deep Magnification-Flexible Upsampling over 3D Point Clouds [103.09504572409449]
  本稿では,高密度点雲を生成するためのエンドツーエンド学習ベースのフレームワークを提案する。 まずこの問題を明示的に定式化し、重みと高次近似誤差を判定する。 そこで我々は,高次改良とともに,統一重みとソート重みを適応的に学習する軽量ニューラルネットワークを設計する。
  論文  参考訳（メタデータ） (2020-11-25T14:00:18Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• On Newton Screening [14.040371216692645]
  我々はNewton Screening (NS) と呼ばれる新しいスクリーニング手法を開発した。 NSは、一段階局所収束を達成するという意味で、最適収束特性を有することを示す。
  論文  参考訳（メタデータ） (2020-01-27T11:25:33Z)

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

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