유형: 논문 · 저자: L´eon Bottou, Olivier Bousquet · 출처: NEC Laboratories of America, Google · 별점: ⭐️⭐️⭐️⭐️⭐️

개요

---

결론

• 소규모 학습(small-scale) : 근사–추정 트레이드오프가 지배적

• 대규모 학습(large-scale) : 최적화 오차(optimization error)와 Tmax 제약 때문에 “가장 좋은 최적화 알고리즘”이 “가장 좋은 학습 알고리즘”이 아닐 수 있다.

• 학습 성능은 최적화(훈련 손실을 얼마나 더 낮추느냐)만으로 결정되지 않음

• 데이터 규모가 커질수록 ‘계산 시간 안에서 어디까지 최적화하는 게 의미가 있느냐’가 핵심

  ⇒ 컴퓨팅 시간 복잡도가 매우 중요한 대규모 문제에서는 형편없는 최적화 알고리즘인(stochastic gradient descent)이 매우 잘 작동한다

통념

• 더 좋은 최적화 알고리즘(Newton, TRON, L-BFGS 등) → 더 낮은 훈련 손실 → 더 좋은 모델

문제 의식

• 테스트 성능까지 포함하면 언제까지 훈련 손실을 더 낮추는 게 의미가 있는가
• 데이터가 매우 많을 때, 훈련 손실을 아주 정밀하게 줄이는 것보다 더 많은 데이터를 ‘대충 충분히’** **학습하는 게 더 낫다

용어

한글	영어	뜻	쉬운 해석
대규모 학습	Large-scale Learning	사용 가능한 계산 시간(Tmax)에 의해 제약받는 학습 상황으로, 제한된 시간 안에 더 많은 데이터를 처리하기 위해 최적화 정확도(ρ)를 일부 포기하는 근사 최적화가 일반화 성능을 높일 수 있는 학습 체계	시간이 부족한 대신 데이터를 많이 써야 하는 상황이라, 완벽하게 푸는 것보다 “빨리 많이 푸는 것”이 더 유리한 학습
소규모 학습	Small-scale Learning	사용 가능한 데이터 수(nmax)에 의해 제약받는 학습 상황으로, 계산 시간이 충분하여 최적화 오차를 거의 제거할 수 있고 근사·추정 오차가 성능을 좌우하는 학습 체계	데이터가 적어서 계산을 아무리 오래 해도 성능이 데이터 한계에 묶이는 상황
최적화 오차	Optimization Error (Eopt)	최적화 알고리즘이 경험적 위험을 완벽히 최소화하지 못해 발생하는 일반화 성능 저하	답을 찾는 방법이 미숙해서, 풀 수 있었던 문제도 덜 맞힌 손실
근사 오차	Approximation Error (Eapp)	허용한 함수 집합 F 안에서, 진짜 최적 함수 f*를 얼마나 잘 표현할 수 없는지로 인해 생기는 오차	애초에 너무 단순한 모델만 허용해서, 아무리 잘 맞춰도 진짜 답을 표현 못하는 손실
추정 오차	Estimation Error (Eest)	유한한 샘플로 학습하면서, 전체 분포에 대해 최적이 아닌 함수를 선택해 생기는 오차	연습문제가 적어서, 실력을 잘못 추정해 생긴 손실
근사-추정-최적화 절충	Approximation–Estimation–Optimization Tradeoff	일반화 오차를 근사·추정·최적화 오차의 합으로 보고, 데이터·계산·모델 복잡도 간의 균형을 맞추려는 이론적 프레임	모델을 복잡하게 할지, 데이터 늘릴지, 계산 더 할지의 균형 게임
기대 위험	Expected Risk E(f)	실제 데이터 생성 분포 P(x,y)에 대해 평균적으로 발생하는 손실로, 모델의 진짜 성능	세상에 무한히 데이터가 있을 때의 진짜 평균 성적
경험적 위험	Empirical Risk En(f)	우리가 가진 유한한 학습 데이터에서 측정한 평균 손실로, 기대 위험의 근사치	지금 가진 문제지에서의 평균 점수
계산 복잡도	Computational Complexity	알고리즘이 학습을 수행하는 데 필요한 계산 자원의 양, 특히 데이터 수에 따른 시간 증가율	데이터가 늘 때 학습 시간이 얼마나 같이 늘어나는가
일반화 성능	Generalization Performance	보지 않은 새로운 데이터에 대해 얼마나 잘 작동하는지를 나타내는 성능 지표	처음 보는 문제에서도 얼마나 잘 맞히는지
함수 집합 F (가설 공간)	Hypothesis Space F	학습 과정에서 선택할 수 있는 모델 후보들의 전체 집합	“우리는 이런 종류의 답만 허용한다”라고 미리 정한 답안 범위

본문 (테스트 성능이 나빠지는 이유)

---

1. 진짜 목표 vs 우리가 실제로 푸는 목표

먼저, 학습에서 우리가 진짜로 줄이고 싶은 것은 훈련 성능이 아니라 새로운 데이터에서의 평균 성능

• 진짜 목표: 기대 위험 (Expected Risk) E(f)
  • 세상 전체 데이터 분포에서 모델 f가 평균적으로 얼마나 틀리는지를 나타내는 값
  • 실제 상황에서는 “앞으로 들어올 모든 사용자, 모든 경우에 대해 평균 성능이 얼마나 되는가”
  • 하지만 우리는 이 “세상 전체 분포”를 직접 알 수 없음
• 현실에서 푸는 목표: 경험 위험 (Empirical Risk) En(f)
  • 지금 손에 쥔 훈련 데이터 n개에서의 평균 손실 = “지금 가진 샘플 기준에서 얼마나 잘 맞추는가”
  • 우리는 기대 위험 E(f)를 직접 줄일 수 없어서 경험 위험 En(f)를 대신 최소화하는 문제로 바꿔서 푼다
• 함수 집합 F라는 제약
  • 우리는 “모든 가능한 함수” 중에서 고를 수 없기 때문에 후보 모델의 범위를 함수 집합 F로 제한함
    • 예: 선형 모델, 특정 깊이의 신경망, 특정 구조의 트리 등
  • 실제로 푸는 문제는 “F 안에서 En(f)를 최소화하는 f를 찾는 것

2. 전통적인 성능 저하 원인 2가지 → 근사 오차 + 추정 오차

• 최적 함수 구분
  • f*
    • 세상 전체에서 진짜로 가장 좋은 함수
    • 기대 위험 E(f)를 최소로 만드는 함수
  • f*_F
    • 우리가 허용한 함수 집합 F 안에서 가장 좋은 함수
  • f_n
    • 훈련 데이터 n개 기준으로 경험 위험 En(f)를 최소로 만드는 함수

⇒ f* → f*_F → fn 으로 갈수록 현실 제약이 하나씩 추가된다고 보면 됨

• 테스트 오차2항 분해
  1. 근사 오차 (Approximation Error, Eapp)
     • 내가 고른 함수 집합 F가 너무 단순해서 진짜 최적 함수 f*를 담을 수 없을 때 생기는 손해
       • 예: 실제 문제는 복잡한 커널이 필요한데 선형 모델만 쓰는 경우
       • 더 복잡한 모델을 쓰면 줄어들 수 있음
  2. 추정 오차 (Estimation Error, Eest)
     • 훈련 데이터 n개가 너무 적어서 f*_F(전체 데이터 기준으로 F에서 최적)를 정확히 못 찾고 훈련 데이터에 과적합하거나 흔들리는 손해
       • 데이터가 적어서 생기는 불안정성
       • 예: 학습은 잘 됐는데 테스트 데이터에서 성능이 확 떨어지는 경우
       • n이 커질수록 줄어듦

⇒ 테스트 오차 = 모델이 부족해서 생기는 손해 + 데이터가 부족해서 생기는 손해

• E(f_n) - E(f*) ≈ E_app + E_est

3. 실제로는 f_n을 정확히 찾지 함 → 최적화 오차 등장

1. 최적화 오차 (Optimization Error, E_opt) = 더 줄일 수 있었던 훈련 손실을 계산 비용 때문에 줄이지 못하고 멈춘 손해
   • 기존 이론의 암묵적 가정 = “fn은 충분히 정확하게 구해진다”
     • 하지만 현실에서는 fn을 정확히 찾는 건 계산적으로 매우 비쌈
     • 계산 시간이나 자원 제약 때문에 f_n을 정확히 못 찾고, 대충 좋은 함수 f̃_n에서 멈춤
   • ρ (rho), 최적화 허용 오차
     • 얼마나 덜 정확해도 괜찮다고 볼 것인가
     • “훈련 손실을 fn보다 ρ만큼 더 높여도 괜찮다” 라는 기준

• E(f̃_n) - E(f*) ≈ E_app + E_est + E_opt

4. n과 시간 T의 이중 제약

• 우리가 조절할 수 있는 것

  • 모델 복잡도 F
    • 모델이 가질 수 있는 모든 후보 형태들의 집합
      • 얼마나 복잡한 패턴까지 표현할 것인가
    • 예시
      • 선형 회귀만 허용 → F가 매우 좁음
      • 3층 MLP 허용 → F가 넓어짐
      • ResNet, Transformer 허용 → F가 매우 넓어짐
    • F를 조절한다는 것
      • 레이어 수, 노드 수, 활성화 함수 종류, 커널 구조, 파라미터 수 등을 수정하는 것
      • 주로 근사 오차(E_app)를 통제함
    • 실패 사례
      • 광고 클릭 예측에서 선형 모델만 쓰는 경우 → 상호작용 패턴 자체를 표현 불가능
      • 이미지 분류에 로지스틱 회귀 사용 → 데이터가 아무리 많아도 근사 자체가 안 됨
  • 사용할 데이터 수 n (전체가 있어도 일부만 쓸 수 있음)
    • 모델이 학습 중 실제로 보게 되는 데이터의 개수
    • n을 조절한다는 것
      • 훈련에 포함할 로그 양, 사용 기간, 필터링 기준, 샘플링 전략 등을 바꿈
      • 주로 추정 오차(E_est)를 통제한다
    • 실패 사례
      • 쇼핑몰 클릭 예측을 하루치 로그로 학습 → 이벤트나 우연에 과도하게 맞춰서 다음날 무너짐
      • 고객 이탈 모델을 특정 캠페인 기간만 사용 → 일반화 불가한 모델이 됨
  • 최적화 정확도 Optimization tolerance (ρ) (얼마나 정밀하게 최적화할지)
    • 훈련 손실을 어디까지 줄일 것인지에 대한 허용 기준
    • ρ를 조절한다는 것
      • Early stopping 기준, 손실 감소량 임계치, 최대 반복 횟수, 미니배치 반복 횟수, 학습률 등을 바꿈
      • 주로 최적화 오차(E_opt)를 통제한다
    • 실패 사례
      • 손실이 조금씩 줄어들고 있는데도 너무 일찍 멈추는 경우 → 더 맞출 수 있었던 구조를 버림
      • 반대로 손실이 거의 줄지 않는데 끝까지 돌리는 경우 → 계산 낭비 + 테스트 성능은 그대로거나 악화

• 변수의 방향성

  • F ↑ ⇒ 근사 오차 ↓ / 비용 ↑
  • n ↑ ⇒ 추정 오차 ↓ / 비용 ↑
  • ρ ↑ ⇒ 최적화 오차 ↑ / 시간↓

조정 요소	영향
F (모델 복잡도) ↑	근사 오차$(E_{\text{app}})$ ↓ / 추정 오차$(E_{\text{est}})$ ↑ / 계산 비용 $(C)$ ↑
n (데이터 수) ↑	추정 오차$(E_{\text{est}})$ ↓ / 계산 비용 $(C)$ ↑
ρ (정밀도↓, 대충함↑) ↑	최적화 오차$(E_{\text{opt}})$ ↑ / 계산 시간$(T)$↓

• 제약 조건

  • n ≤ n_max → 쓸 수 있는 데이터 총량 제한
  • T(F, ρ, n) ≤ T_max → 전체 학습을 수행할 수 있는 시간 제한 (컴퓨팅 리소스 포함)

• 최적화 알고리즘의 시간복잡도가 학습 성능을 결정하는 요인이 됨 승격

  • 시간 복잡도 : 입력 크기나 설정이 커질 때, 계산량이 얼마나 늘어나는가

⇒ 테스트 성능을 최소화하는 문제: 기존 통계적 문제(F, n)에 계산 문제(ρ, 시간 복잡도) 가 동시에 얽힘

5. 소규모 vs 대규모 학습 (small-scale vs large-scale)

• 소규모 학습 문제 (small-scale)

  • 병목: 데이터 한도 nmax
  • 특징
    • 데이터가 부족해서 성능이 제한됨
    • 시간이 남아서 ρ를 매우 작게 만들어 최적화 오차 Eopt를 거의 0으로 만들 수 있음
  • 기존에 쓰던 “근사–추정 트레이드오프”가 유효함

• 대규모 학습 문제 (large-scale)

  • 병목: 시간 한도 Tmax
  • 특징
    • 데이터는 충분하지만 같은 시간 안에 얼마나 처리할 수 있는지가 성능을 좌우
    • ρ를 너무 작게 잡으면 정밀 최적화 때문에 처리 가능한 데이터 n이 줄어듦
  • 더 정밀한 최적화 vs 더 많은 데이터 사이에서 균형이 필요
    • 알고리즘의 계산 복잡도가 핵심이 됨 (ρ)

SGD

---

“형편없는 최적화 알고리즘”

• SGD는 동일 시간 내에 매우 정교하게 loss를 줄이는 것에서는 경쟁력이 떨어진다
• 정밀한 최적화 관점에서는 좋은 알고리즘이 아님

논문의 주장

• 같은 시간내에 얼마나 많은 데이터를 훑느냐가 대규모 테스트 성능 관점에서는 더 중요할 수 있다
• SGD처럼 1개 혹은 작은 배치로 빠르게 업데이트하는 방식이 대규모에서는 정교한 배치 기반 최적화보다 성능이 더 좋다

사고 흐름

1. 논문에서 정의한 테스트 오차 = 근사 오차 + 추정 오차 + 최적화 오차
2. 시간제약(T_max) 아래에서는 “최적화를 끝까지 하는 것(ρ→0) vs 데이터를 많이 훑는 것(n↑)” 사이에서 트레이드오프가 생김
3. SGD는 정밀한 최소화까지 가지 않고도 빠르게 많은 데이터를 처리할 수 있는 구조
4. 그래서 대규모 문제에서는 SGD가 더 나은 일반화 성능으로 이어질 수 있다

⇒ SGD는 시간제약과 상호작용하면서 정교함보다 처리량(throughput)이 우선되는 상황에서 최고의 선택지 중 하나

근거

A) 최적화 관점 속도 vs 학습 관점 속도

• 최적화 속도: 훈련 손실 En(f) → 얼마나 빠르게 줄이는가
• 학습 속도: 테스트 성능 기준에서 성능 임계선에 도달하는 데 걸리는 시간
• SGD
  • 최적화 속도(절대 정밀도 관점)에서는 떨어질 수 있다
  • 반면 학습 속도(테스트 성능 관점)에서는 같은 시간에 더 넓은 데이터를 반영하기 때문에 경쟁력이 있다

B) 배치 기반 최적화 vs SGD

• Batch GD (전체 데이터 기반) : 한 번 업데이트마다 전체 데이터(n)를 훑어야 함 → 비용 크다
• SGD : 매번 1개 혹은 작은 배치로 업데이트 → 비용 작다

C) 대규모 학습에서는 “아주 낮은 ρ”가 테스트 성능을 크게 개선하지 않는다.

• TRON은 훈련 목적함수를 매우 정밀하게 낮출 수 있지만, 테스트 손실은 그 훨씬 이전에 개선이 멈춘다는 점 관찰
• 훈련 손실을 10자리 정밀도로 더 낮추는 시간이 테스트 성능에 거의 기여하지 않는 구간이 존재