論文の概要: From $O(\sqrt{n})$ to $O(\log(n))$ in Quadratic Programming
- arxiv url: http://arxiv.org/abs/2306.15079v3
- Date: Wed, 19 Jul 2023 11:45:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-20 16:56:18.575128
- Title: From $O(\sqrt{n})$ to $O(\log(n))$ in Quadratic Programming
- Title（参考訳）: 擬似プログラミングにおける$O(\sqrt{n})$から$O(\log(n))$へ
- Authors: Liang Wu
- Abstract要約: 特に "direct" メソッドのように振る舞う$O(log(n)$ 反復複雑性QPアルゴリズムを提示するのは、これが初めてである。
このブレークスルーにより、$O(sqrtn)$から$O(log(n))$最適化アルゴリズムに移行することができます。
- 参考スコア（独自算出の注目度）: 5.083671091332159
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A "dark cloud" hangs over numerical optimization theory for decades, namely,
whether an optimization algorithm $O(\log(n))$ iteration complexity exists.
"Yes", this paper answers, with a new optimization algorithm and strict theory
proof. It starts with box-constrained quadratic programming (Box-QP), and many
practical optimization problems fall into Box-QP. General smooth quadratic
programming (QP), nonsmooth Lasso, and support vector machine (or regression)
can be reformulated as Box-QP via duality theory. It is the first time to
present an $O(\log(n))$ iteration complexity QP algorithm, in particular, which
behaves like a "direct" method: the required number of iterations is
deterministic with exact value
$\left\lceil\log\left(\frac{3.125n}{\epsilon}\right)/\log(1.5625)\right\rceil$.
This significant breakthrough enables us to transition from the $O(\sqrt{n})$
to the $O(\log(n))$ optimization algorithm, whose amazing scalability is
particularly relevant in today's era of big data and artificial intelligence.
- Abstract（参考訳）: 暗雲」は数十年間、数値最適化理論、すなわち、最適化アルゴリズム $o(\log(n))$ の反復複雑性が存在するかどうかにかかっている。
この論文は,新たな最適化アルゴリズムと厳密な理論証明を用いて答える。
ボックス制約付き二次プログラミング(Box-QP)から始まり、多くの実用的な最適化問題はBox-QPに該当する。
一般的な滑らかな二次計画法(QP)、非滑らかなラッソ、サポートベクターマシン(または回帰)は双対性理論によりBox-QPとして再構成できる。
特に "direct" メソッドのように振る舞う$o(\log(n))$ 反復複雑性 qp アルゴリズムを提示するのは初めてである: 必要なイテレーション数は、正確な値 $\left\lceil\log\left(\frac{3.125n}{\epsilon}\right)/\log(1.5625)\right\rceil$ で決定論的である。
この大きなブレークスルーによって、$o(\sqrt{n})$から$o(\log(n))$の最適化アルゴリズムへの移行が可能になります。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing [47.32366699399839]
近似第二エピシロン依存(SOSP)の発見は、よく研究され基礎的な問題である。
本稿では,低次元センサマシン最適化問題に適用する。
論文 参考訳（メタデータ） (2024-03-12T01:27:44Z) - Anytime-Constrained Reinforcement Learning [6.981971551979697]
制約付きマルコフ決定過程(cMDP)を任意の制約で導入・研究する。
累積コストを付加した最適決定主義的政策が存在することを示す。
非自明な概略的ポリシーの計算は一般にNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-09T16:51:26Z) - Sub-linear Regret in Adaptive Model Predictive Control [56.705978425244496]
本稿では,STT-MPC (Self-Tuning tube-based Model Predictive Control) について述べる。
システム力学を最初に認識したアルゴリズムと比較して,アルゴリズムの後悔を解析する。
論文 参考訳（メタデータ） (2023-10-07T15:07:10Z) - Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。
この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
論文 参考訳（メタデータ） (2022-05-16T15:47:41Z) - Learning Infinite-Horizon Average-Reward Markov Decision Processes with
Constraints [39.715977181666766]
本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。
我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。
これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
論文 参考訳（メタデータ） (2022-01-31T23:52:34Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Deterministic Approximation for Submodular Maximization over a Matroid
in Nearly Linear Time [16.26380955876814]
マトロイド制約を受ける非単調で非負な部分モジュラ函数を最大化する問題について検討する。
この決定論的比は、$mathcalO(nr)$時間複雑さの下で$frac14$に改善できることを示す。
次に、TwinGreedyFastというより実用的なアルゴリズムを提案し、ほぼ直線的な実行時間で$frac14-epsilon$決定率を達成する。
論文 参考訳（メタデータ） (2020-10-22T03:52:08Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。