論文の概要: On a Gradient Approach to Chebyshev Center Problems with Applications to Function Learning
- arxiv url: http://arxiv.org/abs/2601.06434v1
- Date: Sat, 10 Jan 2026 05:34:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-13 19:08:00.813667
- Title: On a Gradient Approach to Chebyshev Center Problems with Applications to Function Learning
- Title（参考訳）: チェビシェフ中心問題へのグラディエントアプローチと関数学習への応用
- Authors: Abhinav Raghuvanshi, Mayank Baranwal, Debasish Chatterjee,
- Abstract要約: 私たちはChebyshevセンター問題を解決するための最初の勾配ベースの最適化フレームワークである$textsfgradOL$を紹介します。
$textsfgradOL$hinges on reformulating the semi-infinite problem as a finitary max-min optimization。
経験的に、$textsfgradOL$は34のベンチマークChebyshev中心問題の精度と効率を大幅に向上させる。
- 参考スコア（独自算出の注目度）: 3.9826635165229223
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce $\textsf{gradOL}$, the first gradient-based optimization framework for solving Chebyshev center problems, a fundamental challenge in optimal function learning and geometric optimization. $\textsf{gradOL}$ hinges on reformulating the semi-infinite problem as a finitary max-min optimization, making it amenable to gradient-based techniques. By leveraging automatic differentiation for precise numerical gradient computation, $\textsf{gradOL}$ ensures numerical stability and scalability, making it suitable for large-scale settings. Under strong convexity of the ambient norm, $\textsf{gradOL}$ provably recovers optimal Chebyshev centers while directly computing the associated radius. This addresses a key bottleneck in constructing stable optimal interpolants. Empirically, $\textsf{gradOL}$ achieves significant improvements in accuracy and efficiency on 34 benchmark Chebyshev center problems from a benchmark $\textsf{CSIP}$ library. Moreover, we extend $\textsf{gradOL}$ to general convex semi-infinite programming (CSIP), attaining up to $4000\times$ speedups over the state-of-the-art $\texttt{SIPAMPL}$ solver tested on the indicated $\textsf{CSIP}$ library containing 67 benchmark problems. Furthermore, we provide the first theoretical foundation for applying gradient-based methods to Chebyshev center problems, bridging rigorous analysis with practical algorithms. $\textsf{gradOL}$ thus offers a unified solution framework for Chebyshev centers and broader CSIPs.
- Abstract（参考訳）: 我々は,Chebyshev中心問題を解決するための最初の勾配に基づく最適化フレームワークである$\textsf{gradOL}$を紹介した。
$\textsf{gradOL}$ hinges on reformed the semi-infinite problem as a finitary max-min optimization。
正確な数値勾配計算に自動微分を利用することで、$\textsf{gradOL}$は数値安定性とスケーラビリティを保証し、大規模設定に適している。
周囲ノルムの強い凸性の下で、$\textsf{gradOL}$は、関連する半径を直接計算しながら最適なチェビシェフ中心を確実に回復する。
このことは、安定な最適補間体を構築する上で重要なボトルネックに対処する。
経験的に、$\textsf{gradOL}$は、34ベンチマークのChebyshev中心の問題をベンチマークの$\textsf{CSIP}$ライブラリから大幅に改善する。
さらに、$\textsf{gradOL}$を一般凸半無限プログラミング(CSIP)に拡張し、67のベンチマーク問題を含むライブラリでテストされた、最先端の$\texttt{SIPAMPL}$を最大4000\times$スピードアップする。
さらに、チェビシェフ中心問題に勾配法を適用し、厳密な解析を実用的なアルゴリズムで行うための最初の理論的基礎を提供する。
したがって、Chebyshevセンタとより広範なCSIPのための統合ソリューションフレームワークを提供する。
関連論文リスト
- OGF: An Online Gradient Flow Method for Optimizing the Statistical Steady-State Time Averages of Unsteady Turbulent Flows [0.0]
乱流はカオス的で非定常であるが、その統計分布は統計的に安定な状態に収束する。
既存の計算手法では、グリッド点の物理的に代表される数へのスケーリングが不可能である。
我々は,大規模自由度システムにスケーラブルな新しいオンライン勾配流(OGF)法を開発した。
論文 参考訳（メタデータ） (2025-07-07T16:00:15Z) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
双レベル最適化は階層型機械学習問題に対処するための基本的な数学的枠組みとなっている。
従来の勾配に基づく二段階最適化アルゴリズムは、大規模アプリケーションの要求を満たすには不適である。
両レベル最適化のためのメタ勾配の偏りのない近似を実現するための$(textFG)2textU$を導入する。
論文 参考訳（メタデータ） (2024-06-20T08:21:52Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
本研究は、目的関数が他の最適化問題に依存する二段階最適化問題を解く最初のプロジェクションフリーアルゴリズムを示す。
提案されている$textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$)は、凸目的に対して$mathcalO(epsilon-2)$のサンプル複雑性を実現するために示されている。
論文 参考訳（メタデータ） (2021-10-22T11:49:15Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm [50.50545326342971]
複数の長期目標の非線形凹関数を最大化する問題を定式化する。
この問題に対してポリシー段階に基づくモデルフリーアルゴリズムを提案する。
提案アルゴリズムは,グローバルオプティマの$epsilon$以内に収束することが示されている。
論文 参考訳（メタデータ） (2021-05-28T22:20:54Z) - 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) - 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) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。