Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning

Technical Summary: Zero-order Parameter-free Optimization for LMO-based Methods

Problem Statement
Fine-tuning Large Language Models (LLMs) is a central application of modern optimization, yet it faces a critical bottleneck: the memory overhead of backpropagation. Storing intermediate activations, gradients, and optimizer states for models like OPT-1.3B requires substantial memory (e.g., ~25 GB), limiting scalability. Zeroth-order (ZO) optimization offers a memory-efficient alternative by replacing gradient computations with finite-difference estimates derived from function-value queries. However, existing ZO methods suffer from two primary limitations:

1. Hyperparameter Sensitivity: Performance is highly dependent on the stepsize and smoothing parameter ($\tau$). Optimal settings typically require knowledge of problem-dependent constants (e.g., Lipschitz constants, distance to the optimum) which are unavailable in practice, necessitating costly task-specific grid searches.
2. Geometric Mismatch: Standard Euclidean updates may not capture the heterogeneous structure of parameter blocks (e.g., matrix-shaped weights in LLMs). Methods utilizing Linear Minimization Oracles (LMOs) can adapt to non-Euclidean geometries (such as spectral norms for matrices), but combining these with parameter-free (PF) adaptation in a ZO setting remains unexplored.

Methodology
The authors propose AdaNAGED (ADAptive Norm-Agnostic Gradient-frEe Descent), a novel algorithm that unifies three paradigms: memory-efficient zeroth-order optimization, parameter-free adaptation, and geometry-aware updates via LMOs.

• Parameter-Free Estimation:

  • Smoothness ($L$): Instead of requiring a prior Lipschitz constant, the method estimates local smoothness iteratively along the optimization trajectory. It computes the ratio of the difference in ZO gradient approximations to the distance between consecutive iterates: $L_t = \|g_t(x_{t+1}, e_t) - g_t(x_t, e_t)\|_* / \|x_{t+1} - x_t\|$. Crucially, the same perturbation direction $e_t$ (stored as a random seed) is used at both points to maintain memory efficiency.
  • Initial Gap ($\Delta$): The method uses a known lower bound of the objective function ($f_{min}$) to estimate the initial gap $\Delta \leq f(x_0) - f_{min}$, avoiding the need to know the distance to the optimum.
  • Adaptive Stepsize: The stepsize $\gamma_t$ is updated using an AdaGrad-Norm style accumulation of the local smoothness estimates ($S_t = S_{t-1} + L_t$), yielding $\gamma_t \propto 1/\sqrt{S_t}$.
  • Smoothing Parameter ($\tau$): To ensure stability, $\tau_t$ is linearly scaled with the stepsize ($\tau_t = \rho C_2 \gamma_t$), derived from the theoretical requirements of the convergence proof.

• LMO-Based Updates:
  The algorithm defines updates via a Linear Minimization Oracle over a norm ball: $v_t = \text{lmo}(g_t)$. This allows the method to adapt to different geometries:

  • Vector Geometry: Using the $\ell_\infty$ norm yields a Sign-SGD-like update.
  • Matrix Geometry: Using the spectral norm yields a Muon-like update. Since exact polar decomposition (SVD) is computationally expensive, the authors introduce AdaMuGED, which approximates the polar operator using a few steps of the Newton–Schulz (N-SS) iteration, avoiding matrix inversion.

Key Contributions

1. Novel Parameter-Free ZO Construction: The paper introduces a method to estimate local smoothness and set stepsizes in the zeroth-order setting without prior knowledge of problem constants. This preserves the memory efficiency of ZO by only storing generator seeds for perturbation directions.
2. Unification of Paradigms: The proposed AdaNAGED algorithm combines memory-efficient ZO, reduced hyperparameter dependence, and geometry-aware LMO updates.
3. Convergence Guarantees: The authors establish convergence rates for Lipschitz continuous, smooth, and convex objectives. The resulting rate is asymptotically optimal ($O(1/\epsilon^2)$), with additional factors accounting for the parameter-free estimation and stochasticity.
4. Practical Variants: The introduction of AdaMuGED extends the framework to matrix-valued parameters using Newton–Schulz iterations, making it applicable to LLM fine-tuning where parameters are structured as matrices.

Experimental Results
The methods were evaluated on fine-tuning the OPT-1.3B model on the SST-2 sentiment classification task, a benchmark for memory-constrained LLM adaptation.

• Baselines: The authors compared against tuned zeroth-order optimizers: ZO-AdaMM, ZO-SignSGD, and ZO-Muon.
• Performance:
  • AdaNAGED (SignSGD-like) achieved 0.903 accuracy, within 0.7 percentage points of the tuned ZO-SignSGD (0.910).
  • AdaMuGED (Muon-like) achieved 0.908 accuracy, reducing the gap to the tuned ZO-SignSGD to 0.2 percentage points and outperforming AdaNAGED by 0.5 percentage points.
  • The tuned ZO-Muon remained the strongest baseline at 0.921, confirming the benefit of matrix-aware geometry.
• Conclusion: The parameter-free methods demonstrated competitive performance against manually tuned baselines, validating that adaptive rules can recover much of the performance of tuned ZO methods without expensive hyperparameter search.

Significance
The paper claims to present the first method operating at the intersection of Zeroth-Order, Parameter-Free, and Linear Minimization Oracle optimization. Its significance lies in demonstrating that:

1. Memory Efficiency: ZO optimization can be made practical for LLMs by avoiding backpropagation.
2. Automation: The reliance on costly, task-specific hyperparameter tuning can be eliminated through adaptive, parameter-free estimation of smoothness and stepsizes.
3. Geometric Flexibility: The framework supports non-Euclidean updates (via LMOs) that align with the structural properties of model parameters (e.g., matrices), improving conditioning and stability.

The authors maintain a modest stance, noting that while their parameter-free approach is competitive, the tuned baselines (particularly ZO-Muon) still hold a slight edge, suggesting that manual tuning remains optimal but that the proposed method offers a robust, automated alternative.