The Road Less Scheduled — part 6/6

Cleaned-text code points [74670, 90605). Bibliography omitted here; source.md includes it.

Under the same assumptions as Theorem 5 , define ℓ t ​ ( z ) = ⟨ g t , z ⟩ + μ 2 ​ ‖ y t − z ‖ 2 \ell_{t}(z)=\langle g_{t},z\rangle+\frac{\mu}{2}\|y_{t}-z\|^{2} . Define the “regret” of the sequence z t z_{t} as: Regret ℓ ​ ( x ⋆ ) \displaystyle\text{Regret}_{\ell}(x_{\star}) = ∑ t = 1 T w t ​ ( ℓ t ​ ( z t ) − ℓ t ​ ( x ⋆ ) ) . \displaystyle=\sum_{t=1}^{T}w_{t}(\ell_{t}(z_{t})-\ell_{t}(x_{\star})). Then we have for x ⋆ = argmin ​ F x_{\star}=\text{argmin }F : 𝔼 ⁡ [ F ⁡ ( x T ) − F ⁡ ( x ⋆ ) ] \displaystyle\mathbb{E}[F(x_{T})-F(x_{\star})] ≤ 𝔼 [ Regret ℓ ​ ( x ⋆ ) − ∑ t = 1 T w t ​ μ 2 ​ ‖ z t − y t ‖ 2 w 1 : T ] . \displaystyle\leq\mathbb{E}\left[\frac{\text{Regret}_{\ell}(x_{\star})-\sum_{t=1}^{T}\frac{w_{t}\mu}{2}\|z_{t}-y_{t}\|^{2}}{w_{1:T}}\right]. In particular, suppose ‖ x ⋆ ‖ ≤ D \|x_{\star}\|\leq D for some known bound D D and ‖ g t ‖ ≤ G \|g_{t}\|\leq G for all t t for some G G so long as ‖ y t ‖ ≤ D \|y_{t}\|\leq D . Then if we define w t = t w_{t}=t for all t t and set z t z_{t} by: z t + 1 = Π ‖ z ‖ ≤ D ​ [ z t − 2 ​ ( g t + μ ⁡ ( z t − y t ) ) μ ⁡ ( t + 1 ) ] . \displaystyle z_{t+1}=\Pi_{\|z\|\leq D}\left[z_{t}-\frac{2(g_{t}+\mu(z_{t}-y_{t}))}{\mu(t+1)}\right]. then we have: 𝔼 ⁡ [ F ⁡ ( x T ) − F ⁡ ( x ⋆ ) ] \displaystyle\mathbb{E}[F(x_{T})-F(x_{\star})] ≤ 2 ​ ( G + 2 ​ μ ​ D ) 2 μ ⁡ ( T + 1 ) . \displaystyle\leq\frac{2(G+2\mu D)^{2}}{\mu(T+1)}.

###### Proof.

From Theorem 5 , we have: 𝔼 ⁡ [ F ⁡ ( x T ) − F ⁡ ( x ⋆ ) ] \displaystyle\mathbb{E}[F(x_{T})-F(x_{\star})] ≤ 𝔼 [ ∑ t = 1 T w t ​ ⟨ g t , z t − x ⋆ ⟩ w 1 : T − ∑ t = 1 T w t ​ B F ​ ( x ⋆ , y t ) w 1 : T ] . \displaystyle\leq\mathbb{E}\left[\frac{\sum_{t=1}^{T}w_{t}\langle g_{t},z_{t}-x_{\star}\rangle}{w_{1:T}}-\frac{\sum_{t=1}^{T}w_{t}B_{F}(x_{\star},y_{t})}{w_{1:T}}\right]. Now, since F F is μ \mu -strongly convex, we have B F ​ ( x ⋆ , y t ) ≥ μ 2 ​ ‖ y t − x ⋆ ‖ 2 B_{F}(x_{\star},y_{t})\geq\frac{\mu}{2}\|y_{t}-x_{\star}\|^{2} . Further, we have: ∑ t = 1 T w t ​ ⟨ g t , z t − x ⋆ ⟩ \displaystyle\sum_{t=1}^{T}w_{t}\langle g_{t},z_{t}-x_{\star}\rangle = ∑ t = 1 T w t ​ ( ℓ t ​ ( z t ) − ℓ t ​ ( x ⋆ ) ) − w t ​ μ 2 ​ ‖ z t − y t ‖ 2 + w t ​ μ 2 ​ ‖ x ⋆ − y t ‖ 2 . \displaystyle=\sum_{t=1}^{T}w_{t}(\ell_{t}(z_{t})-\ell_{t}(x_{\star}))-\frac{w_{t}\mu}{2}\|z_{t}-y_{t}\|^{2}+\frac{w_{t}\mu}{2}\|x_{\star}-y_{t}\|^{2}. From this we obtain the desired result: 𝔼 ⁡ [ F ⁡ ( x T ) − F ⁡ ( x ⋆ ) ] \displaystyle\mathbb{E}[F(x_{T})-F(x_{\star})] ≤ 𝔼 [ Regret ℓ ​ ( x ⋆ ) − ∑ t = 1 T w t ​ μ 2 ​ ‖ z t − y t ‖ 2 w 1 : T ] . \displaystyle\leq\mathbb{E}\left[\frac{\text{Regret}_{\ell}(x_{\star})-\sum_{t=1}^{T}\frac{w_{t}\mu}{2}\|z_{t}-y_{t}\|^{2}}{w_{1:T}}\right]. For the final statement, observe that with w t = t w_{t}=t , w t ​ ℓ t ​ ( z ) = t ⁡ ⟨ g t , z ⟩ + t ​ μ 2 ​ ‖ z − y t ‖ 2 w_{t}\ell_{t}(z)=t\langle g_{t},z\rangle+\frac{t\mu}{2}\|z-y_{t}\|^{2} is t ​ μ t\mu -strongly convex. Therefore if we use learning rate η t = 1 μ w 1 : t = 2 μ ​ t ​ ( t + 1 ) \eta_{t}=\frac{1}{\mu w_{1:t}}=\frac{2}{\mu t(t+1)} , then standard analysis of projected OGD yields: ∑ t = 1 T t ⁡ ( ℓ t ​ ( z t ) − ℓ t ​ ( x ⋆ ) ) \displaystyle\sum_{t=1}^{T}t(\ell_{t}(z_{t})-\ell_{t}(x_{\star})) ≤ ∑ t = 1 T t ⁡ ⟨ ∇ ℓ t ​ ( z t ) , z t − x ⋆ ⟩ − t ​ μ 2 ​ ‖ z t − x ⋆ ‖ 2 \displaystyle\leq\sum_{t=1}^{T}t\langle\nabla\ell_{t}(z_{t}),z_{t}-x_{\star}\rangle-\frac{t\mu}{2}\|z_{t}-x_{\star}\|^{2} ≤ ‖ z 1 − x ⋆ ‖ 2 ​ ( 1 2 ​ η 1 − μ 2 ​ ‖ z t − x ⋆ ‖ 2 ) − ‖ z T + 1 − x ⋆ ‖ 2 2 ​ η T \displaystyle\leq\|z_{1}-x_{\star}\|^{2}\left(\frac{1}{2\eta_{1}}-\frac{\mu}{2}\|z_{t}-x_{\star}\|^{2}\right)-\frac{\|z_{T+1}-x_{\star}\|^{2}}{2\eta_{T}} + ∑ t = 2 T ∥ z t − x ⋆ ∥ 2 ( 1 2 ​ η t − 1 2 ​ η t − 1 − t ​ μ 2 ) + ∑ t = 1 T η t ​ t 2 ​ ‖ ∇ ℓ t ​ ( z t ) ‖ 2 2 \displaystyle\qquad+\sum_{t=2}^{T}\|z_{t}-x_{\star}\|^{2}\left(\frac{1}{2\eta_{t}}-\frac{1}{2\eta_{t-1}}-\frac{t\mu}{2}\right)+\sum_{t=1}^{T}\frac{\eta_{t}t^{2}\|\nabla\ell_{t}(z_{t})\|^{2}}{2} ≤ ∑ t = 1 T η t ​ t 2 ​ ‖ ∇ ℓ t ​ ( z t ) ‖ 2 2 \displaystyle\leq\sum_{t=1}^{T}\frac{\eta_{t}t^{2}\|\nabla\ell_{t}(z_{t})\|^{2}}{2} ≤ 1 μ ​ ∑ t = 1 T ‖ ∇ ℓ t ​ ( z t ) ‖ 2 \displaystyle\leq\frac{1}{\mu}\sum_{t=1}^{T}\|\nabla\ell_{t}(z_{t})\|^{2} = 1 μ ​ ∑ t = 1 T ‖ g t + μ ⁡ ( z t − y t ) ‖ 2 \displaystyle=\frac{1}{\mu}\sum_{t=1}^{T}\|g_{t}+\mu(z_{t}-y_{t})\|^{2} ≤ T ​ ( G + 2 ​ μ ​ D ) 2 μ . \displaystyle\leq\frac{T(G+2\mu D)^{2}}{\mu}. where in the last inequality we have observed that since ‖ z t ‖ ≤ D \|z_{t}\|\leq D and y t y_{t} is a linear combination of past z z values, ‖ y t ‖ ≤ D \|y_{t}\|\leq D as well. Finally, observing that w 1 : T = T ⁡ ( T + 1 ) 2 w_{1:T}=\frac{T(T+1)}{2} , the result follows. ∎

## Appendix F Large Step size convergence

See 3

###### Proof.

Consider SGD with fixed step size γ \gamma : z t + 1 = z t − γ ​ g t . z_{t+1}=z_{t}-\gamma g_{t}. Let s T + 1 = ∑ t = 1 T γ ​ g t . s_{T+1}=\sum_{t=1}^{T}\gamma g_{t}. Recall from D-Adaptation ( Defazio and Mishchenko,, 2023 ) theory that: ∑ t = 1 T γ ⁡ ⟨ g t , z t − z 1 ⟩ = 1 2 ​ ∑ t = 1 T γ 2 ​ ‖ g t ‖ 2 − 1 2 ​ ‖ s t + 1 ‖ 2 \sum_{t=1}^{T}\gamma\left\langle g_{t},z_{t}-z_{1}\right\rangle=\frac{1}{2}\sum_{t=1}^{T}\gamma^{2}\left\|g_{t}\right\|^{2}-\frac{1}{2}\left\|s_{t+1}\right\|^{2} (31) and: ∑ t = 1 T γ ⁡ ⟨ g t , z t − z ∗ ⟩ ≤ ‖ s T + 1 ‖ ​ D + ∑ t = 1 T γ ⁡ ⟨ g t , z t − z 1 ⟩ . \sum_{t=1}^{T}\gamma\left\langle g_{t},z_{t}-z_{*}\right\rangle\leq\left\|s_{T+1}\right\|D+\sum_{t=1}^{T}\gamma\left\langle g_{t},z_{t}-z_{1}\right\rangle. (32) Now suppose that the regret at time T is negative. Then trivially the theorem holds: 1 T ​ ∑ t = 1 T ⟨ g t , z t − z ∗ ⟩ ≤ 0 = 𝒪 ⁡ ( D T ​ ∑ t = 1 T ‖ g t ‖ 2 ) , \frac{1}{T}\sum_{t=1}^{T}\left\langle g_{t},z_{t}-z_{*}\right\rangle\leq 0=\mathcal{O}\left(\frac{D}{T}\sqrt{\sum_{t=1}^{T}\left\|g_{t}\right\|^{2}}\right), therefore, without loss of generality we may assume that ∑ t = 1 T γ ⁡ ⟨ g t , z t − z ∗ ⟩ ≥ 0 \sum_{t=1}^{T}\gamma\left\langle g_{t},z_{t}-z_{*}\right\rangle\geq 0 . Then from combining Equation 32 with Equation 31 we have: 0 ≤ − 1 2 ​ ‖ s T + 1 ‖ 2 + ‖ s T + 1 ‖ ​ D + 1 2 ​ ∑ t = 1 T γ 2 ​ ‖ g t ‖ 2 . 0\leq-\frac{1}{2}\left\|s_{T+1}\right\|^{2}+\left\|s_{T+1}\right\|D+\frac{1}{2}\sum_{t=1}^{T}\gamma^{2}\left\|g_{t}\right\|^{2}. This is a quadratic equation in ‖ s T + 1 ‖ \left\|s_{T+1}\right\| which we can solve explicitly via the quadratic formula, taking the largest root: ‖ s T + 1 ‖ ≤ − b ± b 2 − 4 ​ a ​ c 2 ​ a . \left\|s_{T+1}\right\|\leq\frac{-b\pm\sqrt{b^{2}-4ac}}{2a}. Plugging in the values a = − 1 2 a=-\frac{1}{2} , b = D b=D , c = 1 2 ​ ∑ t = 1 T γ 2 ​ ‖ g t ‖ 2 c=\frac{1}{2}\sum_{t=1}^{T}\gamma^{2}\left\|g_{t}\right\|^{2} : D ± D 2 + ∑ t = 1 T γ 2 ​ ‖ g t ‖ 2 ≤ 2 ​ D + ∑ t = 1 T γ 2 ​ ‖ g t ‖ 2 . D\pm\sqrt{D^{2}+\sum_{t=1}^{T}\gamma^{2}\left\|g_{t}\right\|^{2}}\leq 2D+\sqrt{\sum_{t=1}^{T}\gamma^{2}\left\|g_{t}\right\|^{2}}. Therefore: ‖ s T + 1 ‖ ≤ 2 ​ D + γ ​ ∑ t = 1 T ‖ g t ‖ 2 . \left\|s_{T+1}\right\|\leq 2D+\gamma\sqrt{\sum_{t=1}^{T}\left\|g_{t}\right\|^{2}}. Substituting this into Equation 32 : ∑ t = 1 T γ ⁡ ⟨ g t , z t − z ∗ ⟩ ≤ 2 ​ D 2 + γ ​ D ​ ∑ t = 1 T ‖ g t ‖ 2 + ∑ t = 1 T γ ⁡ ⟨ g t , z t − z 1 ⟩ . \sum_{t=1}^{T}\gamma\left\langle g_{t},z_{t}-z_{*}\right\rangle\leq 2D^{2}+\gamma D\sqrt{\sum_{t=1}^{T}\left\|g_{t}\right\|^{2}}+\sum_{t=1}^{T}\gamma\left\langle g_{t},z_{t}-z_{1}\right\rangle. Therefore, if ∑ t = 1 T ⟨ g t , z t − z 1 ⟩ ≤ D ​ ∑ t = 1 T ‖ g t ‖ 2 \sum_{t=1}^{T}\left\langle g_{t},z_{t}-z_{1}\right\rangle\leq D\sqrt{\sum_{t=1}^{T}\left\|g_{t}\right\|^{2}} then: ∑ t = 1 T γ ⁡ ⟨ g t , z t − z ∗ ⟩ ≤ 2 ​ D 2 + 2 ​ γ ​ D ​ ∑ t = 1 T ‖ g t ‖ 2 . \sum_{t=1}^{T}\gamma\left\langle g_{t},z_{t}-z_{*}\right\rangle\leq 2D^{2}+2\gamma D\sqrt{\sum_{t=1}^{T}\left\|g_{t}\right\|^{2}}. Plugging in γ = D / G \gamma=D/G : ∑ t = 1 T ⟨ g t , z t − z ∗ ⟩ \displaystyle\sum_{t=1}^{T}\left\langle g_{t},z_{t}-z_{*}\right\rangle ≤ 2 ​ D ​ G + 2 ​ D ​ ∑ t = 1 T ‖ g t ‖ 2 \displaystyle\leq 2DG+2D\sqrt{\sum_{t=1}^{T}\left\|g_{t}\right\|^{2}} ≤ 4 ​ D ​ ∑ t = 1 T ‖ g t ‖ 2 , \displaystyle\leq 4D\sqrt{\sum_{t=1}^{T}\left\|g_{t}\right\|^{2}}, and the theorem follows. ∎

## Appendix G Experimental Setup

### G.1 Convex experiments

Each dataset is obtained from the LIBSVM repository and used without modifications.

Hyper-parameter Value GPUs 1 × \times V100 Batch size 16 Epochs 100 Seeds 10 Schedule-Free β 1 \beta_{1} 0.9 Hyper-parameter Value Decay 0.0 Optimizer Adam Baseline β 1 \beta_{1} 0.9 β 2 \beta_{2} 0.95

### G.2 CIFAR-10

We used custom training code based on the PyTorch tutorial code for this problem. Following standard data-augmentation practises, we appliyed random horizontal flips and random offset cropping down to 32x32, using reflection padding of 4 pixels. Input pixel data was normalized by centering around 0.5.

Hyper-parameter Value Architecture Wide ResNet 16-8 Epochs 300 GPUs 1 × \times V100 Batch size per GPU 128 Cosine/Schedule-Free Warmup 5% Baseline Stepwise LR 0.1 Hyper-parameter Value Seeds 10 decay 0.0001 Baseline Momentum 0.9 Schedule-Free LR 10 Schedule-Free β \beta 0.9 Baseline Cosine LR 0.2

### G.3 CIFAR-100

We used the same codebase as for our CIFAR-10 experiments, with the same data augmentation.

We normalized each input image using fixed mean and standard error values derived from pre-processing the data.

Hyper-parameter Value Architecture DenseNet [6,12,24,16], growth rate 12 Epochs 300 GPUs 1 × \times V100 Schedule-Free β \beta 0.9 Cosine/Schedule-Free Warmup 5% Baseline Stepwise LR 0.05 Hyper-parameter Value Batch size per GPU 64 Seeds 10 Decay 0.0002 Baseline Momentum 0.9 Schedule-Free LR 5 Baseline Cosine LR 0.05

### G.4 SVHN

We used the same codebase as for our CIFAR experiments, and following the same data preprocessing.

Hyper-parameter Value Batch size 32 Weight decay Cosine 0.0001 Weight decay Step Sched 5e-5 Seeds 10 Baseline Stepwise LR 0.1 Hyper-parameter Value Cosine/Schedule-Free Warmup 5% Schedule-Free decay 0.0002 Schedule-Free LR 1.0 Schedule-Free β \beta 0.9 Baseline Cosine LR 0.1

### G.5 ImageNet

We used the same code-base as for our CIFAR-10 experiments, and applied the same preprocessing procedure. The data-augmentations consisted of PyTorch’s RandomResizedCrop, cropping to 224x224 followed by random horizontal flips. Test images used a fixed resize to 256x256 followed by a center crop to 224x224.

Hyper-parameter Value Architecture ResNet50 Epochs 100 GPUs 8 × \times V100 Batch size per GPU 32 Schedule-Free Decay 0.00005 Baseline Stepwise LR 0.1 Baseline Cosine LR 0.05 Hyper-parameter Value Seeds 5 Decay 0.0001 Baseline Momentum 0.9 Schedule-Free β \beta 0.9 Cosine/Schedule-Free Warmup 5% Schedule-Free LR 1.5

### G.6 IWSLT14

We used the FairSeq framework 3 3 3 https://github.com/facebookresearch/fairseq for our experiments. Rather than a vanilla LSTM we use the variant from Wiseman and Rush, (2016) provided in the FairSeq codebase.

Hyper-parameter Value Architecture lstm_wiseman_iwslt_de_en Max Epoch 55 GPUs 1 × \times V100 Tokens per batch 4096 Warmup steps 4000 Dropout 0.3 Label smoothing 0.1 Schedule-Free LR 0.02 Schedule-Free warmup 5% Baseline schedule Linear Decay Hyper-parameter Value Share decoder, input, output embed True Float16 True Update Frequency 1 Seeds 10 Decay 0.05 Baseline β 1 \beta_{1} 0.9 Schedule-Free β 1 \beta_{1} 0.9 β 2 \beta_{2} 0.98 Baseline LR 0.01

### G.7 NanoGPT

We followed the NanoGPT codebase 4 4 4 https://github.com/karpathy/nanoGPT as closely as possible, matching the default batch-size, training length and schedule. Our runs replicate the stated 2.85 loss in the documentation. Disabling gradient norm clipping is crucial for the Schedule-Free runs.

Hyper-parameter Value Architecture transformer_lm_gpt Batch size per gpu 12 Max Iters 600,000 GPUs 40 × \times V100 Tokens per sample 512 Dropout 0.0 Baseline LR 0.0005 Warmup 2,000 Schedule-Free LR 0.005 Schedule-Free β \beta 0.98 Schedule-Free decay 0.05 Hyper-parameter Value Block Size 1024 Num layer 12 Num head 12 Num embd 768 Float16 True Update Frequency 16 Seeds 5 Decay 0.1 Baseline β 1 , β 2 \beta_{1},\beta_{2} 0.9, 0.95 Gradient Clipping 0.0

### G.8 MAE

Our implementation uses the offical code 5 5 5 https://github.com/fairinternal/mae , with hyper-parameters following examples given in the repository.

Hyper-parameter Value Model vit_base_patch16 Epochs 100 GPUs 32 × \times V100 Batch Size 32 Baseline LR 5e-4 Layer Decay 0.65 Weight Decay 0.05 Baseline β 1 \beta_{1} 0.9 Hyper-parameter Value β 2 \beta_{2} 0.999 Schedule-Free LR 0.0.002 Schedule-Free decay 0.05 Schedule-Free β 1 \beta_{1} 0.9 Drop Path 0.1 Reprob 0.25 Mixup 0.8 Cutmix 1.0

### G.9 DLRM

We used a custom implementation of the DLRM model based on the publicly available code. Our optimizer uses dense gradients for implementation simplicity, although sparse-gradients using AdaGrad is a more common baseline on this problem, we consider AdaGrad variants of our scheduling approach as future work.

Hyper-parameter Value Iterations 300 000 Batch Size 128 Emb Dimension 16 GPUs 8 × \times V100 Schedule-Free LR 0.0005 Schedule-Free β 1 \beta_{1} 0.9 β 2 \beta_{2} 0.999 Hyper-parameter Value Seeds 5 Decay 0.0 Baseline β 1 \beta_{1} 0.9 Warmup 0 Baseline LR 0.0002 Baseline schedule Linear Decay

### G.10 MRI

We used the version of the the fastMRI code base at https://github.com/facebookresearch/fastMRI/tree/main/banding_removal . Note that we found that training failed using PyTorch 2 or newer, and so we ran these experiments using PyTorch 1.9.

Hyper-parameter Value Architecture 12 layer VarNet 2.0 Epochs 50 GPUs 8 × \times V100 Batch size per GPU 1 Acceleration factor 4 Baseline Schedule Linear Decay Baseline LR 0.005 β 2 \beta_{2} 0.999 Hyper-parameter Value Low frequency lines 16 Mask type Offset-1 Seeds 5 Decay 0.0 Baseline β 1 \beta_{1} 0.9 Schedule-Free LR 0.005 Schedule-Free β \beta 0.9

### G.11 Algoperf

Our full algoperf entry is availiable at https://github.com/facebookresearch/schedule_free/tree/main/schedulefree/algoperf . The hyper-parameters used for the self-tuning track submission are listed below.

Hyper-parameter Value Learning Rate 0.0025 one-minus Beta1 0.1 Beta2 (default) 0.9955159689799007 Weight Decay (default) 0.08121616522670176 Hyper-parameter Value Dropout Rate 0.1 Warmup Percentage 2% Label Smoothing 0.2 Polynomial in c t c_{t} average 0.75

## Appendix H Polyak and Primal Averaging Runs

These experiments follow the same tuning setup as Figure 5 , where the learning rate and momentum is tuned separately for each method. In each case the c c weighting sequence used for Schedule-Free training is also used to ensure a fair comparison. The Polyak averaging runs include momentum in the base optimizer as we found this gave the best results. We ran the NanoGPT experiment for a shorter 200,000 steps due to computational budget considerations. The NanoGPT Polyak averaging runs show a divergence in test loss for Polyak averaging.

## Appendix I Additional LR Sensitivity Plots

## Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" ( ) button, located in the page header.

Tip: You can select the relevant text first, to include it in your report.

Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .