論文の概要: Iterative Hard Thresholding with Adaptive Regularization: Sparser
Solutions Without Sacrificing Runtime
- arxiv url: http://arxiv.org/abs/2204.08274v1
- Date: Mon, 11 Apr 2022 19:33:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-24 15:46:33.525981
- Title: Iterative Hard Thresholding with Adaptive Regularization: Sparser
Solutions Without Sacrificing Runtime
- Title（参考訳）: 適応正則化による反復的ハードThresholding:Scrificing Runtimeのないスペーサーソリューション
- Authors: Kyriakos Axiotis and Maxim Sviridenko
- Abstract要約: 本稿では,条件数関数としてスペーサー解を復元する反復型ハードしきい値決定アルゴリズムの簡単な修正を提案する。
提案するアルゴリズムである正規化IHTは、疎度$O(skappa)$の解を返す。
我々のアルゴリズムはARHTよりも大幅に改善され、またスパーシティ$O(skappa)$の解も見つかる。
- 参考スコア（独自算出の注目度）: 17.60502131429094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a simple modification to the iterative hard thresholding (IHT)
algorithm, which recovers asymptotically sparser solutions as a function of the
condition number. When aiming to minimize a convex function $f(x)$ with
condition number $\kappa$ subject to $x$ being an $s$-sparse vector, the
standard IHT guarantee is a solution with relaxed sparsity $O(s\kappa^2)$,
while our proposed algorithm, regularized IHT, returns a solution with sparsity
$O(s\kappa)$. Our algorithm significantly improves over ARHT which also finds a
solution of sparsity $O(s\kappa)$, as it does not require re-optimization in
each iteration (and so is much faster), is deterministic, and does not require
knowledge of the optimal solution value $f(x^*)$ or the optimal sparsity level
$s$. Our main technical tool is an adaptive regularization framework, in which
the algorithm progressively learns the weights of an $\ell_2$ regularization
term that will allow convergence to sparser solutions. We also apply this
framework to low rank optimization, where we achieve a similar improvement of
the best known condition number dependence from $\kappa^2$ to $\kappa$.
- Abstract（参考訳）: 条件数の関数として漸近的にスペーサー解を復元する反復型ハードしきい値付けアルゴリズム(IHT)の簡単な修正を提案する。
コンベックス関数 $f(x)$ を条件数 $\kappa$ を$x$ にすると、標準 IHT 保証は緩和された疎度 $O(s\kappa^2)$ の解であり、提案アルゴリズムは正規化 IHT でスパース性 $O(s\kappa)$ の解を返す。
このアルゴリズムはarhtよりも大幅に改善され、またsparsity $o(s\kappa)$の解も発見される。各イテレーションで再最適化を必要とせず、決定論的であり、最適な解値$f(x^*)$ や最適なsparsity level $s$ の知識を必要としない。
我々の主要な技術ツールは適応正規化フレームワークであり、アルゴリズムはスペーサー解への収束を可能にする$\ell_2$正規化項の重みを徐々に学習する。
また、このフレームワークを低ランク最適化に適用し、最もよく知られた条件数依存性を$\kappa^2$から$\kappa$へ同様の改善を達成する。
関連論文リスト
- Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。
本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。
微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
論文 参考訳（メタデータ） (2024-10-23T18:00:01Z) - Online Convex Optimization with a Separation Oracle [10.225358400539719]
本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
論文 参考訳（メタデータ） (2024-10-03T13:35:08Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文 参考訳（メタデータ） (2021-12-21T01:54:17Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。
我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
論文 参考訳（メタデータ） (2021-01-15T18:52:02Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Sparse Convex Optimization via Adaptively Regularized Hard Thresholding [17.60502131429094]
本稿では,適応正規化ハードThresholding (ARHT) アルゴリズムを提案する。
また、OMP with Replacement (OMPR) for general $f$, under the condition $s > s* frackappa24$。
論文 参考訳（メタデータ） (2020-06-25T17:16:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。