7 papers · 1 filter
Two Answers on Heavy-Ball Dynamics
Dmitry Pasechnyuk-Vilensky, Martin Takáč
We determine the worst-case behavior of the heavy-ball method on smooth strongly convex functions, first for Polyak's quadratic-optimal parameters and then for arbitrary constant p…
Chebyshev-Exact Acceleration under Hessian Variation, II: Computer-Assisted Variational Lower Bound
Dmitry Pasechnyuk-Vilensky, Martin Takáč, Takáč
We study two-step recurrences with positive step sizes and nonnegative momentum coefficients whose terminal residual is the Chebyshev minimax polynomial on a prescribed spectral in…
Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method
Dmitry Pasechnyuk-Vilensky, Martin Takáč
We study finite-horizon one-gradient realizations with the Chebyshev minimax terminal residual on . Under time-dependent Hessian perturbations, the terminal first variation…
Heterogeneous-Horizon Exact-Weight Local SGD
Dmitry Pasechnyuk-Vilensky, Martin Takáč
We study adaptive aggregation for heterogeneous local SGD in convex finite-sum optimization, allowing heterogeneous local horizons, minibatch sizes, gradient noise, and participati…
Moduli space of optimization algorithms
Dmitry Pasechnyuk-Vilensky, Martin Takáč
We introduce a geometric and operator-theoretic formalism viewing optimization algorithms as discrete connections on a space of update operators. Each iterative method is encoded b…
Cubic Regularized Newton Method with Variance Reduction for Finite-sum Non-convex Problems
Dmitry Pasechnyuk-Vilensky, Dmitry Kamzolov, Martin Takáč
We study finite-sum non-convex optimization and analyze a variance-reduced cubic Newton method based on EMA-smoo…
Information-Theoretic Upper Bounds for Deterministic Noise in Zeroth-Order Convex Optimization
Dmitry Pasechnyuk-Vilensky, Igor Pavlov, Martin Takáč +1
We study zeroth-order convex optimization on Euclidean balls with function values corrupted by a fixed, uniformly bounded deterministic perturbation. For a query budget , the ma…