論文の概要: Tilted Convexity and an Exact Offline-Online Separation

• arxiv url: http://arxiv.org/abs/2611.03472v1
• Date: Mon, 02 Nov 2026 17:13:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 04:19:41.081757
• Title: Tilted Convexity and an Exact Offline-Online Separation
• Title（参考訳）: Tilted Convexity and an Exact Offline-Online separation (特集:電気化学)
• Abstract要約: 凸性は、アフィン関数によるサポート、部分微分の単調性、セカント勾配の増加の3つの等価な記述を持つ。 これら3つ全てをパラメータ $in(0,1) で1つの歪みで弱め、正の変化を$$で乗算し、負の変化を$で割る。 結果として生成されるクラスは、$=1の凸関数であり、$$1の値は区別され、ネストされる。
• 参考スコア（独自算出の注目度）: 51.97268646814437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convexity has three equivalent descriptions: support by affine functions, monotonicity of the subdifferential, and increasing secant slopes. We weaken all three by one distortion with parameter $γ\in(0,1]$, which multiplies positive changes by $γ$ and divides negative ones by $γ$. The resulting classes are the convex functions at $γ=1$ and, for $γ<1$, are distinct and nested, with the parameter dropping by at most a square along the chain. For proper lower semicontinuous functions in these classes, the effective domain is convex, local minimizers are global, and the function is locally Lipschitz on the relative interior of its domain. The classes separate offline from online optimization over compact convex sets with efficient projection, with access to function values and bounded support vectors. A smooth member of any class can be minimized to additive accuracy $\varepsilon$ with $\mathrm{poly}(1/\varepsilon)$ first-order queries and projections. Online, with nonpositive losses and $α$-regret measured against $α$ times the best fixed point, a polynomial-time algorithm achieves $γ$-regret $O(\sqrt T)$ on the largest class. For every fixed, effectively specified $γ\in(0,1)$ and every $α\in(γ,1]$, no randomized polynomial-time algorithm has sublinear expected $α$-regret unless $\mathbf{NP}=\mathbf{RP}$, already for smooth concave polynomial losses in the smallest class, each minimized by one linear optimization. Thus, unless $\mathbf{NP}=\mathbf{RP}$, $γ$ is the exact online coefficient of each class, while the offline coefficient is one.
• Abstract（参考訳）: 凸性は、アフィン関数によるサポート、部分微分の単調性、セカント勾配の増加の3つの等価な記述を持つ。 パラメータ $γ\in(0,1]$ は正の変化を$γ$ で乗算し、負の変化を$γ$ で割る。 結果として得られるクラスは、$γ=1$の凸関数であり、$γ<1$の場合、パラメータは鎖に沿って少なくとも正方形に減少する。 これらのクラスにおける適切な下半連続函数に対して、有効領域は凸であり、局所最小化子は大域であり、その函数はその領域の相対的な内部上の局所リプシッツである。 クラスは、関数値と有界サポートベクトルへのアクセスにより、効率的なプロジェクションを持つコンパクト凸集合に対するオンライン最適化からオフラインを分離する。 任意のクラスの滑らかなメンバーは、加算精度$\varepsilon$と$\mathrm{poly}(1/\varepsilon)$ 1次クエリとプロジェクションで最小化できる。 非正の損失と$α$-regretが最良の固定点のα$倍に対して測定された場合、多項式時間アルゴリズムは最大のクラスで$γ$-regret$O(\sqrt T)$を達成する。 固定された任意の$γ\in(0,1)$とすべての$α\in(γ,1]$に対して、ランダム化された多項式時間アルゴリズムは、最小クラスにおける滑らかな凹凸多項式損失に対して既に1つの線形最適化によって最小化されている$α$-regretがなければ、サブ線形予想$α$-regretを持たない。 したがって、$\mathbf{NP}=\mathbf{RP}$ がなければ、$γ$ は各クラスの正確なオンライン係数であり、オフライン係数は 1 である。

関連論文リスト

• Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls [1.4975436239088316]
  Follow-the-regularized-leaderアルゴリズムは、損失シーケンス毎に、$T$や$_T$を知らずに、後悔する$O_pを達成する。 平均がゼロ座標を持たない i.d. 損失に対しては、期待される後悔の正確な$log T$係数を計算する。
  論文  参考訳（メタデータ） (2026-10-26T18:15:38Z)
• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
  普遍性と適応性の両方を達成する新しいアプローチであるUniGradを紹介し、UniGrad.CorrectとUniGrad.Bregmanの2つの異なる実現法を提案する。 どちらのメソッドも勾配の変動に適応し、強い凸関数に対する $mathcalO(log V_T)$ regret とexp-concave関数に対する $mathcalO(d log V_T)$ regret を同時に達成する。
  論文  参考訳（メタデータ） (2025-11-25T05:23:10Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions [44.655316553524855]
  我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。 それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
  論文  参考訳（メタデータ） (2023-11-17T22:07:18Z)
• 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)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)

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

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