Fugu-MT 論文翻訳(概要): Line Search for Convex Minimization

論文の概要: Line Search for Convex Minimization

arxiv url: http://arxiv.org/abs/2307.16560v1
Date: Mon, 31 Jul 2023 10:39:01 GMT
ステータス: 処理完了
システム内更新日: 2023-08-01 15:02:01.755400
Title: Line Search for Convex Minimization
Title（参考訳）: 凸最小化のための線探索
Authors: Laurent Orseau, Marcus Hutter
Abstract要約: ゴールデンセクションサーチとバイセクションサーチは1d準関数の2つの主要なアルゴリズムである。収束保証を提供し、数個の単変数および多変数凸関数上の準エクサクサクサクサクタラインの効率を確認する。
参考スコア（独自算出の注目度）: 31.668598805887587
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Golden-section search and bisection search are the two main principled algorithms for 1d minimization of quasiconvex (unimodal) functions. The first one only uses function queries, while the second one also uses gradient queries. Other algorithms exist under much stronger assumptions, such as Newton's method. However, to the best of our knowledge, there is no principled exact line search algorithm for general convex functions -- including piecewise-linear and max-compositions of convex functions -- that takes advantage of convexity. We propose two such algorithms: $\Delta$-Bisection is a variant of bisection search that uses (sub)gradient information and convexity to speed up convergence, while $\Delta$-Secant is a variant of golden-section search and uses only function queries. While bisection search reduces the $x$ interval by a factor 2 at every iteration, $\Delta$-Bisection reduces the (sometimes much) smaller $x^*$-gap $\Delta^x$ (the $x$ coordinates of $\Delta$) by at least a factor 2 at every iteration. Similarly, $\Delta$-Secant also reduces the $x^*$-gap by at least a factor 2 every second function query. Moreover, the $y^*$-gap $\Delta^y$ (the $y$ coordinates of $\Delta$) also provides a refined stopping criterion, which can also be used with other algorithms. Experiments on a few convex functions confirm that our algorithms are always faster than their quasiconvex counterparts, often by more than a factor 2. We further design a quasi-exact line search algorithm based on $\Delta$-Secant. It can be used with gradient descent as a replacement for backtracking line search, for which some parameters can be finicky to tune -- and we provide examples to this effect, on strongly-convex and smooth functions. We provide convergence guarantees, and confirm the efficiency of quasi-exact line search on a few single- and multivariate convex functions.
Abstract（参考訳）: ゴールデンセクション探索とバイセクション探索は、準凸関数の1d最小化のための2つの基本アルゴリズムである。 1つは関数クエリのみを使用し、もう1つは勾配クエリも使用する。他のアルゴリズムはニュートン法のようなより強い仮定の下で存在する。しかしながら、我々の知る限りでは、凸関数のピースワイドや最大構成を含む一般凸関数に対する厳密な直線探索アルゴリズムは、凸性を利用するものはない。我々は,2つのアルゴリズムを提案する。$\Delta$-Bisectionは,(部分)次情報と凸性を用いて収束を高速化するバイセクション検索の変種であり,$\Delta$-Secantはゴールデンセクション検索の変種であり,関数クエリのみを使用する。 bisection searchは、各イテレーションで1つのファクタ2で$x$の間隔を減少させるが、$\delta$-bisectionは、各イテレーションで少なくとも1つのファクタ2で$x^*$-gap$\delta^x$($x$座標は$\delta$)を小さくする。同様に、$\delta$-secant は、秒関数クエリ毎に少なくとも 2 倍の $x^*$-gap を減少させる。さらに、$y^*$-gap $\delta^y$($y$座標は$\delta$)は洗練された停止基準を提供し、他のアルゴリズムでも使用できる。いくつかの凸関数の実験では、我々のアルゴリズムは常に準凸関数よりも高速であることが確認されている。さらに$\delta$-secant に基づく準実数線探索アルゴリズムを設計する。逆追跡線探索の代替として勾配降下を用いることができ、パラメータによってはチューニングが難しい場合もあり、この効果の例として、強凸および滑らかな関数を挙げる。収束保証を提供し,数個の単変量および多変量凸関数上での準エクサクサクタライン探索の効率を確認する。

関連論文リスト

A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems with Optimal Iteration Complexity [2.815239177328595]
凸凹極小最適化問題の解法として,Lipschitz-free Cubal regularization (LF-CR)アルゴリズムを提案する。また,この問題のパラメータを必要としない完全パラメータフリー立方正則化(FF-CR)アルゴリズムを提案する。我々の知る限り、FF-CRアルゴリズムは凸凹極小最適化問題の解法として初めて完全にパラメータフリーな2次アルゴリズムである。
論文参考訳（メタデータ） (2024-07-04T01:46:07Z)
Comparisons Are All You Need for Optimizing Smooth Functions [12.097567715078252]
微分自由法を用いてスムーズな関数を最適化するためには,エンファラリソンがすべて必要であることを示す。さらに,サドル点をエスケープし,エプシロン$秒の定常点に到達するためのアルゴリズムも提供する。
論文参考訳（メタデータ） (2024-05-19T05:39:46Z)
Adaptive approximation of monotone functions [0.0]
GreedyBox が任意の関数 $f$ に対して,対数因子まで,最適なサンプル複雑性を実現することを証明した。おそらく予想通り、GreedyBoxの$Lp(mu)$エラーは、アルゴリズムによって予測されるよりもはるかに高速な$C2$関数で減少する。
論文参考訳（メタデータ） (2023-09-14T08:56:31Z)
Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文参考訳（メタデータ） (2023-06-16T17:00:51Z)
Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文参考訳（メタデータ） (2023-02-16T13:57:19Z)
A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文参考訳（メタデータ） (2021-10-28T14:19:30Z)
Parameter-free Stochastic Optimization of Variationally Coherent Functions [19.468067110814808]
我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。この2つを同時に実現したのは初めてである。
論文参考訳（メタデータ） (2021-01-30T15:05:34Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文参考訳（メタデータ） (2020-04-16T19:16:38Z)
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)

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

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