Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification

• URL: http://arxiv.org/abs/2602.00634v1
• Date: Sat, 31 Jan 2026 10:05:05 GMT
• Title: Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification
• Authors: Masahito Hayashi,
• Abstract summary: We develop a deterministic zeroth-order mirror descent framework by replacing gradients with a general vector field.<n>Our analysis provides an evaluation template for last-rate inequality evaluations.<n>Together, these results expose a hidden geometric linking Bregman identities, deterministic certification, and robust conic geometry in zeroth-order mirror descent.
• Score: 45.85698554568285
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a deterministic zeroth-order mirror descent framework by replacing gradients with a general vector field, yielding a vector-field-driven mirror update that preserves Bregman geometry while accommodating derivative-free oracles. Our analysis provides a unified evaluation template for last-iterate function values under a relative-smoothness-type inequality, with an emphasis on trajectory-wise (a posteriori) certification: whenever a verifiable inequality holds along the realized iterates, we obtain explicit last-iterate guarantees. The framework subsumes a broad class of information-geometric algorithms, including generalized Blahut-Arimoto-type updates, by expressing their dynamics through suitable choices of the vector field. We then instantiate the theory with deterministic central finite differences in moderate dimension, where constructing the vector field via deterministic central finite differences requires 2d off-center function values (and one reusable center value), i.e., 2d+1 evaluations in total, where d is the number of input real numbers. In this deterministic finite-difference setting, the key interface property is not classical convexity alone but a punctured-neighborhood generalized star-convexity condition that isolates an explicit resolution-dependent error floor. Establishing this property for the finite-difference vector field reduces to a robust conic dominance design problem; we give an explicit scaling rule ensuring the required uniform dominance on a circular cone. Together, these results expose a hidden geometric structure linking Bregman telescoping identities, deterministic certification, and robust conic geometry in zeroth-order mirror descent.

Related papers

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Inverting Self-Organizing Maps: A Unified Activation-Based Framework [39.146761527401424]
  We show that the activation pattern of a SOM can be inverted to recover the exact input under mild geometric conditions.<n>We introduce the Manifold-Aware Unified SOM Inversion and Control (MUSIC) update rule.<n>We validate the approach using synthetic Gaussian mixtures, the MNIST and the Faces in the Wild dataset.
  arXiv  Detail & Related papers  (2026-01-20T11:02:54Z)
• Primal: A Unified Deterministic Framework for Quasi-Orthogonal Hashing and Manifold Learning [0.0]
  We present Primal, a deterministic framework that harnesses the number-theoretic independence of prime square roots to construct robust, tunable vector representations.<n>Our method exploits the Besic property to create irrational frequency modulations that guarantee non-repeating phase trajectories.<n> Empirical evaluations demonstrate that our framework yields superior retention and distribution tightness compared to random matrix projections.
  arXiv  Detail & Related papers  (2025-11-25T20:44:34Z)
• Möbius transforms and Shapley values for vector-valued functions on weighted directed acyclic multigraphs [13.61966594130545]
  We generalize the concept of M"obius inversion and Shapley values to directed acyclic multigraphs and weighted versions thereof.<n>We allow value functions (games) and thus their M"obius transforms (synergy function) and Shapley values to have values in any abelian group that is a module over a ring that contains the graph weights.
  arXiv  Detail & Related papers  (2025-10-07T11:05:25Z)
• Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent [25.846262685970164]
  This paper proposes and analyzes a gradient-type algorithm based on Burer-Monteiro factorization.<n>It reconstructs the point set configuration from partial Euclidean distance measurements.
  arXiv  Detail & Related papers  (2025-04-28T07:13:23Z)
• On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models [11.137244714693779]
  We study the robustness of spectral algorithms against semirandom adversaries.<n>We identify classes of semirandom adversaries under which spectral bisection using the _unnormalized_ Laplacian is strongly consistent.
  arXiv  Detail & Related papers  (2024-12-18T20:35:02Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [67.12679195076387]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression.<n>Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• Householder Projector for Unsupervised Latent Semantics Discovery [58.92485745195358]
  Householder Projector helps StyleGANs to discover more disentangled and precise semantic attributes without sacrificing image fidelity. We integrate our projector into pre-trained StyleGAN2/StyleGAN3 and evaluate the models on several benchmarks.
  arXiv  Detail & Related papers  (2023-07-16T11:43:04Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  We propose a new covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific clustering measured by the bounds number. We derive these results in various contexts and improve the known state-of-the-art label rates.
  arXiv  Detail & Related papers  (2022-09-19T12:11:07Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.