A SYSTEM FOR MASSIVELY PARALLEL HYPERPARAMETER TUNING (ASHA)

• Abstract: A System for Massively Parallel Hyperparameter Tuning

  Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt, Benjamin Recht, Ameet TalwalkarModern learning models are characterized by large hyperparameter spaces and long training times. These properties, coupled with the rise of parallel computing and the growing demand to productionize machine learning workloads, motivate the need to develop mature hyperparameter optimization functionality in distributed computing settings. We address this challenge by first introducing a simple and robust hyperparameter optimization algorithm called ASHA, which exploits parallelism and aggressive early-stopping to tackle large-scale hyperparameter optimization problems. Our extensive empirical results show that ASHA outperforms existing state-of-the-art hyperparameter optimization methods; scales linearly with the number of workers in distributed settings; and is suitable for massive parallelism, as demonstrated on a task with 500 workers. We then describe several design decisions we encountered, along with our associated solutions, when integrating ASHA in Determined AI’s end-to-end production-quality machine learning system that offers hyperparameter tuning as a service. arXiv 2018

• ASHA제안

1. Related work
   1. Sequential Method
   2. Hybrid approach
      1. Fabola
      2. 베이지안 하이브리드 어프로치
         1. 2017 ICML에 제안된 베이지안 뉴럴넷+하이퍼밴드 조합
            1. 베이지안뉴럴넷 학습을 토해 러닝커브 예측 → 가장 유망한 HP Config. 선택→하이퍼밴드의 인풋으로 활용
         2. 2018년 ICML에 제안된 BOHB
            1. 베이지안 최적화+하이퍼밴드
            2. 하이퍼밴드의 서브루틴인 SHA에 프로모션 되지 않은 트라이얼들에 대해Synchronized Elimination을 제안함
   3. 병렬 메소드
      1. PBT(population based training2017, 2019)
         1. SOTA 하이브리드 진화알고리즘 기반 접근법
         2. 모델의 파퓰레이션 의 적합도를 증가시키기위해 부분학습을 반복적으로 수행함
         3. 하이퍼밴드에 비해 이론적 검증이 부족함
         4. 하이퍼밴드랑 비교하기보단 SHA와 비교하는게 적절함 왜냐하면 둘 다 early stopping 비율을 인풋으로 받기 때문에
      2. Visor는 구글의 블랙박스 최적화 서비스
         1. 얼리스톱 옵션과 함께 멀티플 하이퍼파라미터 최적화 기능을 지원함
         2. 세부 알고리즘 비공개 그러나 early stopping기능 제공 (룰 및 전략 설정 가능)
         3. SHA대비 수렴속도가 3배 빠름
   4. HP최적화 시스템
      1. 싱글머신/싱글유저 HPO시스템: AutoWEKA (Kotthoff et al., 2017) and AutoSklearn (Feurer et al., 2015)
      2. 분산 시스템: Vizier (Golovin et al., 2017), RayTune (Liaw et al., 2018), CHOPT (Kim et al., 2018) and Optuna (Akiba et al.).
      3. RayTune and Optuna는 ASHA 지원
      4. ASHA가 특히 massively parallel hyperparameter optimization에 가장 적절하다고 주장
      5. 프로덕션 환경 도입을 위해 성능, 사용성, 간건성 개선
      6. 자동화된 오토스케일링 리밋 기능, 적응적 스케줄링을 통해 효율적은 자원 할당 제안

2. ASHA 알고리즘
   1. SHA오버뷰 → SHA를 페러렐세팅에 채택하게 된 모티베이션 → ASHA vs Synchronous SHA 디스커션
   2. SHA
      1. Figure 1(a)shows the rungs for bracket 0 for an example setting with n = 9, r = 1, R = 9, and η = 3,
      2. Figure 1(b) shows how resource allocations change for different brackets s.
      3. Fig1을 통해 초기 설정에 따른 SHA동작 과정을 보여줌
      4. 직관적으로 이를 활용하기에는 병렬체제에 부적합함
      5. Fig1(a)를 예로 들면, 소요시간이 3*time(R)이므로
      6. 상기 시간을 time(R)로 줄이는 알고리즘을 제안함
      7. BOHB에서는 SHA 병렬화를 위해 현재 브라켓에 돌릴 잡이 없을 경우 신규 브라켓을 추가하는 방식으로 병렬화 전략을 설계함. 그러나 SHA본연의 두가지 이슈
         1. (1) SHA는 필수적으로 다음 rung로 넘어가기 위해선 현재rung의 모든 trial을 완료해야함
         2. (2) 브라켓간에 평가가 상호간에 교류가 안되고 독립적으로 평가 및 활용함. (프로모션은 각 브래킷에 대해 독립적으로 수행되므로 더 많은 브래킷이 실행될수록 주어진 초기 패리티 비율에 대한 상위 1/슬롯 구성의 추정치는 개선되지 않습니다)

            

   3. Asynchronous SHA (ASHA)
      1. ASHA는 현재 rung의 모든 HP설정(이하 설정) 종료를 기다리는 대신 프로모션 가능한 설정을 프로모션한다. (다음 rung의 시작을 기다리지 않고)
      2. 만약 프로모션 가능한 설정이 없을 시, 간단하게 base rung의 설정을 추가하여 학습한다. 이를 통해 더 많은 설정이 상위 rung으로 프로모션 된다
      3. 비동기방식으로 인해 유저는 설정 수를 사전 정의할 필요가 없어짐 (작업속도에따라 자연스럽게 bottom rung의 설정을 늘리므로) 그러나 SHA와 동일한 인풋을 요구함.
      4. 비동기 파트는 run_then_return_val_loss서브르틴에 포함되며, job이 워커에게 넘어간 이후에 실행됨
      5. ASHA의 프로모션 스킴은 get_job서브루틴에 위치함
      6. ASHA는 wall-clock time이 제약된 단일모델 학습을 위한 대규모 시스템에 적절함
      7. SHA와 비교 위해 학습시간은 자원과 선형관계 가정
      8. 브라켓0는 fig1에 제시된 대로 ASHA, 9개머신(워커)로 가정하면, ASHA는 학습완료된 설정을 13/9*time(R)안에 리턴하기에 충분함.
         1. 9개의 머신이면 단일 설정을 학습하는데 걸리는 시간에 다른 설정을 다음 rung로 프로모션하기에 충분하기 때문에
         2. (13개 설정이면 9개 동시 시작→ 프로모션된 3개 시작 → 1개 9epoches 시작) rung1-2사이에 6개의 머신 가용
         3. rung0: 소요시간=1/9*time(R)
         4. rung1: 소요시간=1/3*time(R)
         5. rung2: 소요시간=time(R)
         6. 일반적으로 $η^{log_η(R)−s}$ 대의 머신은 설정을 다음 rung으로 진전시키는데 필요하며 이는 단일 설정을 교육하는데 걸리는 시간과 동일
         7. 위를 대입해보면 $3^{log_3 9 - 0}=3^2=9$대 머신
         8. rung i에서 소요시간은 $η^{s+i−log_η (R)} × time(R)$
         9. $3^{0+0-log_39}*time(9)=3^{-2}-time(9)=time(1)$
         10. 따라서 ASHA의 소요시간은

             

         11. 또한 체크포인트-리줌기능을 활용하면 $time(R)$ 이하로 소요됨
      9. SHA를 다양한 조합의 멀티플 브라켓으로 병렬화 해주는 하이퍼밴드를 동일한 목적으로 활용함→ ASHA의 멀티플 브라켓 병렬화

         

   4. algorithm discussion
      1. ASHA는 소수의 부정확한 프로모션을 유발하므로써 동기프로모션의 보틀넥을 없앤다. 다시말해 1/에타안에 들지 못한 설정을 프로모션함
      2. 큰수의 법칙에 의해 설정 수가 증가함에 다라 각 rung에서 탈락하는 설정의 일부를 잘못 프로모션 할 것으로 예상됨
      3. 직관적으로 첫번째 rung에서 n개의 평가된 설정들이 있다고 가정할때 mispromoted된 설정은 러프하게 $\sqrt{n}$
      4. early stopping rate는 hyperband의 bracket 시작 index와도 같음
         1. s=0인 경우 n도 커짐 $n\ge \eta ^{s_{max}-s}=\eta ^{\log_\eta{R\over r}-s}=\eta ^{\log_\eta{R\over r}}\times \eta^{-s}={R\over r\eta^s}$
         2. 그러므로 초기설정수는 S에 따라 다르고 S=1이라고 하면 하이퍼밴드에서 가장 넓게 탐색하는 브라켓 하나를 스킵하고 진행하는것과 동일함 → S가 클수록 좁가 탐색하기시작
      5. SHA의 대비 개선점 (두가지 변형에 대해서 개선함)
         1. finite horizon: 설정당 한정된 자원 R이 할당되는 경우
            1. ASHA에서는 이미 R만큼 학습된 설정은 프로모트 하지 않음 → rungs 수를 제한함
         2. infinite horizon: 자원제약 없음
            1. ASHA에서 자원제약 R을 없애면 설정이 더 높은 rung으로 프로모션 됨으로서 약간 일반화될 수 있음 → 프로모션 할 설정이 더이상 없으면 바텀렁의 설정들을 자연스럽게 키워주기 때문에 위아래로 자연스럽게 확장됨
            2. 이와 대조적으로 SHA는 자연스럽게 infinite horizon으로 확장되지 않음 → max budget을 늘리면 bracket을 재실행 해야함
         3. SHA의 싱글 브라켓 완료때까지 아웃풋을 반환하지 않음 → ASHA는 종료되지 않았다면 싱글브라켓 자체를 점점 키우므로써 기다리는 시간이 없음 → 지속적으로 실행 가능함 → 중간에 현재 베트스 성능을 보이는 설정을 참조하여 아웃풋으로 사용할 수 있음

3. empirical evaluation
   1. sequential experiment
      1. 대상 알고리즘: ASHA, PBT, BOHB, (Sync.)SHA
      2. 벤치마크 대상: CIFAR-10
         1. CNN with cuda-convnet architecture, 동일 탐색공간
         2. CNN구조 튜닝: 다양한 레이어 수, 배치사이즈, 필터 수
      3. BOHB는 early-stopping을 위해 SHA를 활용하고 다른점은 설정을 샘플링 할 때 베이지안 최적화 활용하여 경험적/적응적으로 신규 설정을 샘플링함 (SHA, HB, ASHA등은 랜덤샘플)
      4. SHA, ASHA, BOHB는 동일한 early-stopping방식 사용

         

      5. 벤치마크 1에서는 하이퍼밴드 및 SHA변형이 PBT보다 3배 이상 좋은 성능을 보임
      6. 벤치마크2에서는 모든 알고리즘이 랜덤서치보다 좋은 성능 보이며 나머지 성능은 대부분 비슷하나 미세하게 하이퍼밴드보다 나은 성능을 보임
      7. 가장 어그레시브하게 얼리스톱을 수행한 브라켓이 가장 좋은 성능을 보임
      8. PBT는 하이퍼밴드보다는 SHA와 유사함
         1. 둘 다 사용자가 명시한 early-stopping rate를 입력받음
      9. SHA, ASHA가 BOHB와 비등비등함 (BOHB는 adaptive 샘플링임에도 불구하고..)
      10. Async.는 성능에 영향을 미치지 않음(싱글워커 때문인듯 → 섹션3.3에 논의)
   2. limited-scale distributed experiments
      1. ASHA vs SHA, BOHB, PBT 비교
      2. 2가지 테스크, 25워커머신에 대해 150분 수행
      3. SHA, BOHB, ASHA 모두 동일한 에타값 사용

         

      4. 그림3의 벤치마크1에서는 탐색방법마다 5개의 트라이얼에 따른 평균 테스트에러를 보여줌
      5. ASHA는 1000개 넘는 설정값을 평가했고 40분이 지나는 시점에 25개의 워커로 좋은 설정(error rate < 0.21)을 찾아냄.
      6. 대략적으로 싱글모델을 R까지 학습하는 시간쯤 소요됨
      7. 반면 fig2에서는 (single worker) 400분가량 소요됨. → 간단한 task의 경우 10x speed up with 25worker
      8. 벤치마크2에서는 복잡한 테스크에 대한 성능시험 fig2에서(싱글워커) 시험 시 0.23아래로 도달하는데 소요시간이 대략 700분이었고, 25워커로 시험 시 25분 쯤 도달했다.
      9. 벤치마크1에서 SHA, BOHB와 비교해서 좋은 설정을 찾는 속도가 대략 1.5배정도 빠름 (BOHB가 final 성능은 약간 더 좋음)
      10. 벤치마크2에서 복잡한 테스트의 경우 학습시간의 분산이 커짐으로 인해 SHA, BOHB대비 상당히 더 나은 성능을 보임. (R까지 학습시간 30분, 표준편차: 27분)
      11. 큰 분산의 학습시간은 Sync SHA의 straggler에 대한 민감도를 더 악화시킴 (동일 타임프레임 안에 rung의 학습이 끝나지 않을 가능성이 커짐→ 대기시간 증가)→ 이를 활용하는 SHA 및 BOHB성능 저하
      12. 벤치마크1에서 ASHA는 PBT보다 좋은 성능을 보임 심지어 MIN/MAX라인도 PBT의 평균 실선과 겹치지 않음 → 최악의 trial도 평균PBT성능보다 좋음
      13. 벤치마크2에서 PBT는 ASHA와 비등한 성능을 보임 → 민맥스 레인지도 대부분 오버랩 됨 → 동등한 성능으로 판단.
      14. 따라서 벤치마크1, 2를 통해 PBT, BOHB보다 ASHA가 간단/복잡한 테스크 모두 전반적으로 우수하다고 판단 (25워커)
   3. Tuning neural network architectures (NAS)
      1. 2가지 벤치마크
         1. CIFAR-10을 위한 CNN구조 설계
         2. Penn Treebank를 위한 RNN 설계
      2. ASHA, SHA, BOHB모두 16워커, 에타=4, R=300에포크로 실험함

         

      3. 모든 벤치마크에서 ASHA가 다른 알고리즘보다 좋은 성능을 보임
      4. 벤치마크1에서 ASHA는 두배 빠르게 에러10%미만에 도달함
      5. 평균 test error 최종 결과 ASHA가 가장 우수함
         1. ASHA: 3.24%
         2. SHA: 3.42%
         3. BOHB: 3.36%
      6. 벤치마크2에서 80미만의 복잡도를 달성하는 시간 3배 빠름
      7. 최종 복잡도 결과
         1. ASHA: 63.5
         2. SHA: 64.3
         3. BOHB: 64.2
      8. PBT는 호환되지 않는 시험이라 수행치 않음 appendix에 모두 호환되는 벤치마크로 비교하긴 함 → ASHA가 더 뛰어남
   4. Tuning Large-scale language models
      1. 500대 워커노드
      2. 대규모 LSTM (Zaremba, W., Sutskever, I., and Vinyals, O. Recurrent neural network regularization. arXiv preprint arXiv:1409.2329, 2014.)
      3. ASHA, 에타=4, r=R/64, s=0
      4. 비동기 하이퍼밴드는 모든 브라켓을 루프 도는 형식으로 구동, s=0~3
      5. Google vizier 서비스(without early-stopping rule)와 성능비교

         

      6. ASHA, 하이퍼밴드 1R 안에 좋은 설정을 찾음 복잡도 80미만을 달성하는데 Vizier대비 3배 빠르게 도달함 (간단하고 쉬운 구현 기반으로도)
      7. 최종 모델은 ASHA: 76.6으로 벤치마크 원문의 LSTM(78.4)보다 좋은 성능을 보임
      8. 초기에는 하이퍼밴드가 ASHA에 비해 뒤쳐졌지만 1.5R부근에서 따라잡음