Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates

In this paper, we develop provable parameter-free and adaptive fixed-point algorithms for contractive mappings, with an emphasis on automatically exploiting hidden contractivity without requiring prior knowledge of the contraction factor. Our first method is a completely parameter-free variant of the Halpern fixed-point iteration. It requires no line search, bisection, or prior estimate of the contraction factor, while retaining essentially the same per-iteration computational cost as classical fixed-point schemes. We establish explicit linear convergence rates for both the fixed-point residual and the distance to the unique fixed point. The second algorithm is an adaptive Halpern method that requires only an upper bound on the contraction factor and reduces to an existing adaptive Halpern scheme in the nonexpansive case. This method also enjoys explicit linear convergence guarantees. We further extend these ideas in two directions. First, by combining the proposed fixed-point schemes with Tikhonov regularization, we obtain a parameter-free method for solving co-coercive equations and establish an iteration complexity of $\mathcal{O}({ε^{-1}\ln(ε^{-1})})$ for computing an $ε$-solution. Second, using the relation between Halpern iterations and Nesterov's accelerated fixed-point schemes, we derive parameter-free Nesterov's accelerated variants that inherit linear convergence in the contractive setting. Numerical experiments on several examples demonstrate that the proposed algorithms are competitive with, and often outperform, existing adaptive fixed-point methods. In particular, the methods successfully exploit contractive behavior when it is present while remaining effective on nonexpansive problems.

Adaptivity via a Parallel Architecture for Stochastic Gradient Methods

Let $\mathrm{A}(x_0,y)$ be an algorithm with two inputs: an initial point $x_0$ and an integer parameter $y$, which specifies that $\mathrm{A}(.,.)$ executes at most $y$ iterations or steps. Given an integer $p\ge 1$, $p$ parallel processors search an appropriate value of $T$ for for $A(.)$. Each processor executes an infinite sequence of stages indexed by $i=0,1,2,\ldots$. At stage $i$, processor $j$ is assigned $T_{j,i}=h(j,i),$ where $h:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{R}^{+}$ is a prescribed function. Processor $j$ $(j=0,1,\ldots,p-1)$ then executes $\mathrm{A}(x_0,T_{j,i})$. The efficiency of the parallel framework is characterized by its $(p,α_p)$-approximation guarantee. Specifically, for every integer $T\ge T_0$, there exist a processor $j$ and a stage $i$ such that $T\le T_{j,i}\le T_{j,i}^*<α_p T,$ where $T_{j,i}^*=\sum_{t=0}^{i}T_{j,t}$ denotes the cumulative number of iterations executed by processor $j$ from the beginning to stage $i$. We prove that this framework achieves a $(p,α_p)$-approximation, and a tight lower bound for $α_p$ for all large $p$. We develop arithmetically simple stochastic gradient methods in which every division is of the form $x/2^t$ for some integer $t$, and integrate them into the proposed parallel framework.

AdaGrad does not adapt to Hölder-smoothness for composite objectives

We exhibit a simple deterministic one-dimensional convex composite optimization problem for which AdaGrad scheme does not achieve the classical convergence rate $\mathcal{O}(n^{-(1+ν)/2})$ associated with Hölder-smooth objectives. The example highlights a basic mismatch between classical AdaGrad accumulation and composite optimality. A main insight is that the gradient of the smooth term may not vanish at the optimum, causing AdaGrad to keep reducing its stepsize excessively and converge more slowly. We also discuss why alternative accumulation mechanisms based on gradient mappings or on successive gradient differences, avoid this pathology.

Anon: Extrapolating Optimizer Adaptivity Across the Real Spectrum

Adaptive optimizers such as Adam have achieved great success in training large-scale models like large language models and diffusion models. However, they often generalize worse than non-adaptive methods, such as SGD on classical architectures like CNNs. We identify a key cause of this performance gap: adaptivity in pre-conditioners, which limits the optimizer's ability to adapt to diverse optimization landscapes. To address this, we propose Anon (Adaptivity Non-restricted Optimizer with Novel convergence technique), a novel optimizer with continuously tunable adaptivity in R, allowing it to interpolate between SGD-like and Adam-like behaviors and even extrapolate beyond both. To ensure convergence across the entire adaptivity spectrum, we introduce incremental delay update (IDU), a novel mechanism that is more flexible than AMSGrad's hard max-tracking strategy and enhances robustness to gradient noise. We theoretically establish convergence guarantees under both convex and non-convex settings. Empirically, Anon consistently outperforms state-of-the-art optimizers on representative image classification, diffusion, and language modeling tasks. These results demonstrate that adaptivity can serve as a valuable tunable design principle, and Anon provides the first unified and reliable framework capable of bridging the gap between classical and modern optimizers and surpassing their advantageous properties.