論文の概要: Beyond Discretization: Learning the Optimal Solution Path

• arxiv url: http://arxiv.org/abs/2410.14885v1
• Date: Fri, 18 Oct 2024 22:23:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:17:55.321572
• Title: Beyond Discretization: Learning the Optimal Solution Path
• Title（参考訳）: 離散化を超えて - 最適なソリューションパスを学ぶ
• Authors: Qiran Dong, Paul Grigas, Vishal Gupta,
• Abstract要約: 本稿では,解経路を基底関数の集合でパラメータ化し,エンフィングル最適化問題を解く手法を提案する。 我々の手法は、離散化よりも相当に複雑化している。 また、機械学習に共通する特殊なケースに対して、より強力な結果を示す。
• 参考スコア（独自算出の注目度）: 3.9675360887122646
• License:
• Abstract: Many applications require minimizing a family of optimization problems indexed by some hyperparameter $\lambda \in \Lambda$ to obtain an entire solution path. Traditional approaches proceed by discretizing $\Lambda$ and solving a series of optimization problems. We propose an alternative approach that parameterizes the solution path with a set of basis functions and solves a \emph{single} stochastic optimization problem to learn the entire solution path. Our method offers substantial complexity improvements over discretization. When using constant-step size SGD, the uniform error of our learned solution path relative to the true path exhibits linear convergence to a constant related to the expressiveness of the basis. When the true solution path lies in the span of the basis, this constant is zero. We also prove stronger results for special cases common in machine learning: When $\lambda \in [-1, 1]$ and the solution path is $\nu$-times differentiable, constant step-size SGD learns a path with $\epsilon$ uniform error after at most $O(\epsilon^{\frac{1}{1-\nu}} \log(1/\epsilon))$ iterations, and when the solution path is analytic, it only requires $O\left(\log^2(1/\epsilon)\log\log(1/\epsilon)\right)$. By comparison, the best-known discretization schemes in these settings require at least $O(\epsilon^{-1/2})$ discretization points (and even more gradient calls). Finally, we propose an adaptive variant of our method that sequentially adds basis functions and demonstrates strong numerical performance through experiments.
• Abstract（参考訳）: 多くのアプリケーションは、ソリューションパス全体を取得するために、ハイパーパラメータ $\lambda \in \Lambda$ でインデックス付けされた最適化問題の族を最小化する必要がある。 従来のアプローチでは、$\Lambda$を離散化し、一連の最適化問題を解く。 本稿では, 解経路を基底関数の集合でパラメータ化し, 解経路全体を学ぶための確率最適化問題を解く方法を提案する。 我々の手法は、離散化よりも相当に複雑化している。 定数ステップサイズSGDを使用する場合、真経路に対する学習解経路の均一誤差は、基底の表現性に関連する定数に対する線形収束を示す。 真の解経路が基底の幅にあるとき、この定数はゼロである。 $\lambda \in [-1, 1]$と解パスが$\nu$-times differentiable, constant step-size SGDは、少なくとも$O(\epsilon^{\frac{1}{1-\nu}} \log(1/\epsilon))$イテレーションの後、$\epsilon$一様エラーを学習し、解パスが解析されている場合、$O(\log^2(1/\epsilon)\log(1/\epsilon)\right)$のみを必要とする。 対照的に、これらの設定で最もよく知られた離散化スキームは、少なくとも$O(\epsilon^{-1/2})$離散化点(さらに勾配呼び出し)を必要とする。 最後に,基本関数を逐次付加し,実験により強い数値性能を示す適応型手法を提案する。

関連論文リスト

• A quantum central path algorithm for linear optimization [5.450016817940232]
  中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。 このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。 標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
  論文  参考訳（メタデータ） (2023-11-07T13:26:20Z)
• Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem [16.9187409976238]
  凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。 低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
  論文  参考訳（メタデータ） (2023-08-15T02:37:11Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• An algorithmic view of $\ell_2$ regularization and some path-following algorithms [7.6146285961466]
  凸損失関数に対する$ell$-regularized Solution pathと通常の微分方程式(ODE)の解との等価性を確立する。 この等価性は、溶液経路を勾配降下のハイブリッドの流れと見なすことができ、ニュートン法は経験的損失に適用できることを示した。 ホモトピー法と数値ODE解法に基づく新しい経路追従アルゴリズムを提案し,解経路を数値的に近似する。
  論文  参考訳（メタデータ） (2021-07-07T16:00:13Z)
• Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
  サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。 対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。 我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
  論文  参考訳（メタデータ） (2021-03-29T23:03:24Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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